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

У меня есть два набора точек A и B, при этом точки могут быть 2D или 3D. Оба набора имеют одинаковый размер n, что довольно мало (5 - 20).

Я хотел бы знать, насколько хорошо эти наборы согласуются. То есть в идеале я бы нашел такие пары между точками, чтобы сумма всех евклидовых парных расстояний d(A,B) была минимальной. Так

d(A,B) = \sum_{i=1}^n ||A_i - B_i||_2

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

  • A = (1,1), (1,2), (1,3)
  • B = (1,1), (2,2), (1,3)

дал бы мне d(A,B) = 1.

  • C = (1,1), (2,1), (3,1)
  • D = (2,1), (2,2), (3,1)

дал бы мне d(C,D) = 1.414.

Есть хорошие идеи?


algorithm geometry dynamic-programming mathematical-optimization
person ypnos    schedule 20.01.2015    source источник
comment
Как вы достигаете d(C,D) = 2 ? Какое межточечное расстояние вы используете? Проверьте cs.smith.edu/~orourke/TOPP/P6.html.   -  person Yves Daoust    schedule 20.01.2015
comment
Извините, это была ошибка. Я бы использовал евклидово расстояние.   -  person ypnos    schedule 20.01.2015
comment
Формула, которую вы используете для вычисления d(a,b), совсем не очевидна. Просьба уточнить.   -  person RBarryYoung    schedule 20.01.2015
comment
Ваша ссылка привела меня к этой статье, содержащей компактное описание алгоритма: Саян Бхаттачарья. Обзор алгоритмов евклидова сопоставления. db.cs.duke.edu/courses/cps234/fall08/ проекты/sayan_proj.pdf   -  person ypnos    schedule 20.01.2015
comment
За кулисами здесь скрыта проблема графа (двудольное сопоставление с минимальной стоимостью): en.wikipedia.org/wiki /венгерский_алгоритм   -  person Rerito    schedule 21.01.2015

Ответы (1)


arrow_upward
4
arrow_downward

Например, вы можете смоделировать свою проблему как задачу с заданием (ссылка на Википедию ), где вы определяете стоимость C_ij назначения точки A_i (из набора A) точке B_j (из набора B) равной расстоянию между ними. Затем эту проблему присваивания можно решить с помощью венгерского алгоритма (ссылка на Википедию).

person Fanfan    schedule 20.01.2015
comment
Ваш ответ уже очень полезен. Алгоритм O (n ^ 3). Было бы здорово, если бы для моего случая был более быстрый алгоритм. - person ypnos; 21.01.2015
comment
Я понял, что Earth Mover's Distance, о котором я упоминал в своем вопросе, также использует венгерский алгоритм. Однако он использует оптимизацию (например, тот факт, что затраты зависят от метрики). Так что для меня это лучший выбор. - person ypnos; 21.01.2015