Алгоритм Для Количественной оценки Разницы Траекторий отрезков линии

Question

Допустим, у меня есть два пути отрезка линии, например, подмножество приведенных ниже примеров.Как я могу количественно оценить разницу между ними?

1. |__
2. \_
3. __
4. /\
5. \/
6. |
7. _

Два пути могут иметь разное количество сегментов, и длина каждого сегмента и угол между ними являются переменными.

Я подумал, что было бы неплохо установить систему координат и определить сегменты как узлы и ребра.Различие, возможно, могло бы быть количественно оценено операциями, необходимыми для преобразования одного в другое, аналогично Расстояние Левенштейна алгоритм.К сожалению, операционное пространство огромно.Есть какие-нибудь идеи?Спасибо!

Answer 1

Я пойду немного дальше того, на что указал @awoodland:от того, как вы это оцениваете, зависит полностью о том, почему вы хотите количественно оценить разницу.

Вы хотите получить уникальный (по крайней мере, вероятно, уникальный) номер, подобный хэш-коду для пути отрезка линии?Или вы пытаетесь количественно определить траектории линейных сегментов, чтобы сказать: "этот путь более сложный (или длиннее, или имеет более острые углы), чем этот путь"?

Если вы хотите создать хэш-код, я бы предложил создать два 32-разрядных CRC (или что-то подобное):один для длины сегмента и один для углов.После того как вы вычислили эти CRC, сведите их вместе в 64-битное значение с углами в старших 32 битах и длинами в младших 32 битах.В зависимости от количества сегментов, возможно, подойдет одно значение CRC:для каждого сегмента добавьте длину, а затем угол между ним и следующим сегментом.

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

Если вы хотите количественно оценить сложность пути линейного сегмента ...У меня не так уж много идей.

Answer 2

Вы можете нарисовать их в изображения с фиксированным размером, а затем использовать евклидовое расстояние, чтобы сравнить изображения.

Или вы могли бы измерить общую длину и суммировать абсолютное значение углов (а также подписанных углов, возможно) в качестве меры. Что-то основанное на этом, имело бы приятное свойство, будучи инвариантной ориентацией формы (если бы вы этого хотели!).

Как вы оцениваете его несколько, зависит от Зачем Вы хотите определить изменение разницы между ними.

Answer 3

Вы можете посмотреть на эту статью:

http://www.vision.ee.ethz.ch/~calvin/publications/ferrari07pami.pdf.

В этой статье мы используем KAS (обобщение пар сегментов: вы можете иметь несколько сегментов, связанных друг с другом) для обнаружения объектов. Мы вводим дескриптор для этих наборов сегментов, которые вы можете использовать для описания ваших пар.

Наш дескриптор не является вращением инвариант, так что это может не соответствовать вам.

Answer 4

Если вы используете операции:

• Добавить угол и сегмент
• Снимите угол и сегмент
• Сегмент растяжения (с весом разницы)
• Угол изгиба (с весом разницы)

Вы все равно сможете использовать расстояние Левенштейна, все еще находясь в N ^ 2 времени.

Закомите сегменты как следующие [сегмент, угол] *. Так было бы:

[length, rotation] [length, rotation]...

Где вращение соответствует направлению указывающего сегмента.

Расчет растяжения и изгиба довольно очевидно. Value[i-1, j-1] + stretch + bend.

Расчет добавления / удаления. Добавлять Value[i,j-1] + Cost of adding, удалять Value[i-1, j] + cost of removal.