Алгоритм количественной оценки различий путей сегмента линии - PullRequest
2 голосов
/ 05 ноября 2010

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

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

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

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

Ответы [ 4 ]

2 голосов
/ 05 ноября 2010

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

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

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

1 голос
/ 06 ноября 2010

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

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

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

1 голос
/ 05 ноября 2010

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

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

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

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

1 голос
/ 05 ноября 2010

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

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

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

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

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

...