Алгоритм сравнения строк

Question

Линия - это массив точек (две или более).Каждая точка имеет координаты X и Y (двойные).У меня есть самолет, полный линий.Мне нужна некоторая мера, которая скажет мне, насколько близки и насколько похожи любые две линии от плоскости.Мне нужно, чтобы эта мера была равна 0, когда линии абсолютно одинаковы, и ее значение должно увеличиваться, когда линия вращается, смещается или имеет совершенно другую геометрию.Для начала, если кто-то знает имя хорошего алгоритма для этого, было бы хорошо.

ОБНОВЛЕНИЕ: Возможное использование таково: у меня есть дорога с приблизительной геометрией.У меня есть дорожная сеть.Я должен найти другую дорогу в дорожной сети, которая, вероятно, является дорогой, которую я ищу.Но по некоторым другим причинам, я требую эту меру также.Недостаточно найти дорогу, я должен указать число, которое показывает, насколько мой матч хорош и насколько близки другие матчи.

Обратите внимание, что две линии не должны быть разными, если точки разные.

Также, если кто-то знает, где я могу найти код или библиотеку для этого алгоритма в C #, было бы здорово.

Answer 1

предупреждение: графическое распознавание образов не мое любимое хобби, так что это может быть полная чушь ...

Я бы попытался найти некоторую эвристику, которая может кое-что рассказать об определенных сходствах между сравниваемыми строками ...

Сначала тривиальные проверки:

равны ли наборы точек?

посмотрите на количество очков:
если обе линии имеют одинаковое количество точек:
измерить относительные расстояния от точки к точке в обеих линиях ...
измерять изменение угла при ходьбе от точки к точке по обеим линиям ...
... суммируйте различия (и их абсолюты), и вы получите некоторые показатели

если обе линии не имеют одинакового количества точек:

положите линии над сеткой и отметьте ячейки этой сетки, которых коснулась линия ... сосчитайте различия ... попробуйте различные разрешения сетки

пройти по линиям, отследить направление ходьбы и удалить точки, которые имеют небольшое угловое отклонение от направления ходьбы ... как только вы достигнете точки с большим угловым изменением, сделайте это новым направлением ходьбы и оставьте точку ... потом попробуйте другие метрики

чтобы найти вращение и масштаб:

попробуйте рассчитать / найти 3 скопления точек или характерных точек (точек с одинаковым угловым изменением, предпочтительно не близко друг к другу и с необычным угловым изменением) и попытаться повернуть / растянуть / отразить ... вы, вероятно, хотите рассчитать все остальные показатели для каждой возможной версии и получить наилучший результат, если применимо

если подобные вещи не дают полезных вам результатов ... похоже, вас ждет много математики ...

http://en.wikipedia.org/wiki/Image_registration
http://en.wikipedia.org/wiki/Scale-invariant_feature_transform