|
|
сравнение геометрических фигур.
Добавлено: 24 апр 11 16:24
|
Кто-нибудь знаком с каким-нибудь алгоритмом который можно применить для сравнения двух геометрических фигур. Фигуры заданы множествами точек.
Point := x and y
Countur := Set of Points
Object := Set of Points and Countur
На выходе надо получить 2 вещи:
1. расстояние (степень подобности) фигур
2. пары точек, которые можно считать одной и той же точкой
Грубый алгоритм у меня есть, но он очень медленный получается (т.е. если длинна первого контура N1, а второго N2 и размер S1 и S2 (соответственно), то мой алгоритм делает К*N1*N2*Log(S1)*Log(S2) действий (К здесь коэффициент отражающий размер окна при сравнении двух точек). Ну вероятно я могу увеличить скорость до N1*N2+К*N1*Log(S1)+К*N2*Log(S2) если кешировать кое какие данные ну или даже убрать Log'и заменив их на +S1+S2. Но этого все равно мало.
Я не спрашиваю про конкретный алгоритм, но может кто-то сталкивался с подобным и есть идеи в какую сторону капать.
P.S.
О фигурах известно, что они в общем похожи (ну типа резиновая трансформация) и ориентированны более или менее одинаково (в пределах 10 градусов)
|
|
|
|
| На: сравнение геометрических фигур.
Добавлено: 24 апр 11 17:05
|
Я некоторое время назад написал алгоритм многомерного синтаксического анализа для контекстно-зависимых и контекстно-свободных грамматик в виде плагина для моей программы AIAssistant.
Кое-что почерпнул из:
Fu K.S. Syntactic methods in pattern recognition (AP, 1974)(ISBN 0122695607
Fu K.S. Syntactic pattern recognition and applications (PH, 1982)(ISBN 0138801207)
Мой алгоритм основан на самообучении онтологического синтаксического анализатора. В основе лежит не метод переборов, а продукционные правила. Это позволяет срабатывать им при появлении в рабочей памяти нового факта, в данном случае факта нового паттерна. А т.к. сами синтаксические правила созданы в виде фактов, то эти самые новые правила можно получать из анализируемых данных.
К сожалению, я проверил и отладил эту технологию на небольших ЕЯ текстах и то без самообучения. А они одномерны. И лишь сейчас перехожу к многомерному анализу, в частности 2 и 3 мерным изображениям. Надеюсь, что что нибудь из описанного мною будет вам полезным.
|
|
|
NO.
Сообщений: 10700 |
 |
|
| На: сравнение геометрических фигур.
Добавлено: 24 апр 11 17:17
|
Наверно быстрее и не получится. Либо от общего сравнения нужно переходить к распознаванию в небольшом классе фигур, а там возможно будет какое-то их представление сразу ложащееся на метрику. Я делал грубое сравнение, находим центр массы и потом в полярных координатах по 8 секторам тоже просто массу точек. Повороты и отражения так тоже быстро сопоставляются. Перекодировать тоже занимает N^2, а само сравнение работает мгновенно. Я двигал мышь по экрану с буквами и они все сразу перекрашивась по уровню подобия букве на которую показываю. тут что получалось нужно щелкнуть по 00b.bmp и двигать по картинке внизу
|
|
|
|
| На: сравнение геометрических фигур.
Добавлено: 24 апр 11 17:35
|
Суть моего метода такова:
1. Если в памяти нет СП (синтаксических правил), то подавая на вход изображение первой фигуры можно добиться создания относительно простых СП основываясь лишь на поступившей информации. Если же какие-то СП уже имелись, то СА (синтаксический анализатор) может использовать эти СП для более глубокого анализа.
2. Подавая на вход СА изображение второй фигуры, программа может использовать имеющиеся в ней знания о первой фигуре в виде СП.
3. По полученному одному или нескольким деревьям анализа можно судить о степени схожести фигур. Если при этом добавить новую информацию в СП, полученные от второго изображения, то можно его сразу после этого использовать для сравнения с любым последующим изображением фигуры.
|
|
|
|
| На: сравнение геометрических фигур.
Добавлено: 24 апр 11 21:20
|
Автор: NO.
находим центр массы и потом в полярных координатах по 8 секторам тоже просто массу точек. Повороты и отражения так тоже быстро сопоставляются. |
|
Забавно, я именно это хотел предложить... Только кривую из точек обрабатывать сплайн-функцией. А смещение от центра компенсируется довеском-циклоидой.
|
|
|
|
| На: сравнение геометрических фигур.
Добавлено: 24 апр 11 22:42
|
daner 24 апр 11 16:24
[...Кто-нибудь знаком с каким-нибудь алгоритмом который можно применить для сравнения двух геометрических фигур. Фигуры заданы множествами точек...]
У Вайнцвайга была очень красивая и эффективная процедура для такого, если фигуры выделены из фона. Если нет, то возникали разумные переборные потребности
|
|
|
NO.
Сообщений: 10700 |
|
|
| На: сравнение геометрических фигур.
Добавлено: 24 апр 11 22:48
|
Вроде хорошо работает. Где-то тут была тема, там Андрей предложил преобразование Просолвера, а такое намного проще. Только там задача была ещё и находить эти фирурки на изображении, а не просто сравнивать. Я тут много лишнего наделал, слишком дискретно получилось, строгие контуры и заливка. Лишняя работа. Нужно как-то помягче всю картинку сводить к структуре особенностей. Но потом опять трудно искать кучу возможных фигур в такой же мешанине разных элементов и признаков.
|
|
|
|
| На: сравнение геометрических фигур.
Добавлено: 24 апр 11 23:02
|
Автор: гость
daner 24 апр 11 16:24
[...Кто-нибудь знаком с каким-нибудь алгоритмом который можно применить для сравнения двух геометрических фигур. Фигуры заданы множествами точек...]
У Вайнцвайга была очень красивая и эффективная процедура для такого, если фигуры выделены из фона. Если нет, то возникали разумные переборные потребности
|
|
О! Спасибо. Вот только как этот Вайнцвайг на английском пишется, а то ничего не могу найти в Интернете.
|
|
|
|
| На: сравнение геометрических фигур.
Добавлено: 24 апр 11 23:04
|
Автор: NO.
Вроде хорошо работает. Где-то тут была тема, там Андрей предложил преобразование Просолвера, а такое намного проще. Только там задача была ещё и находить эти фирурки на изображении, а не просто сравнивать. Я тут много лишнего наделал, слишком дискретно получилось, строгие контуры и заливка. Лишняя работа. Нужно как-то помягче всю картинку сводить к структуре особенностей. Но потом опять трудно искать кучу возможных фигур в такой же мешанине разных элементов и признаков. |
|
Что именно работает?
|
|
|
|
| На: сравнение геометрических фигур.
Добавлено: 24 апр 11 23:47
|
daner 24 апр 11 23:02
[...О! Спасибо. Вот только как этот Вайнцвайг на английском пишется, а то ничего не могу найти в Интернете...]
А хрен его знает - он по-русски пишет. Думаю, что это было опубликовано в журнале Ю.Журавлева - PRIA. Лет десять назад плюс-минус сколько-то
|
|
|
NO.
Сообщений: 10700 |
|
| |
| |
| |
NO.
Сообщений: 10700 |
|
| |
| |
|