Алгоритм количественной оценки различий путей сегмента линии

Question

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

Вы все равно сможете использовать расстояние Левенштейна, все еще находясь в 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.

Answer 3

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

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

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

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

Answer 4

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

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

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

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

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