Нужен лучший алгоритм для нахождения отображения между 2 наборами точек с минимальным расстоянием

Question

Проблема: У меня есть две перекрывающиеся 2D фигуры, A и B, каждая из которых имеет одинаковое количество пикселей, но отличается по форме. Некоторая часть фигур перекрывается, и есть некоторые части каждой, которые не перекрываются. Моя цель состоит в том, чтобы переместить все неперекрывающиеся пиксели в форме A в непересекающиеся пиксели в форме B. Поскольку число пикселей в каждой форме одинаково, я должен быть в состоянии найти отображение 1-в-1 пиксели. Ограничение состоит в том, что я хочу найти отображение, которое минимизирует общее расстояние, пройденное всеми перемещенными пикселями.

Грубая сила: Подход о грубой силе к решению этой проблемы, очевидно, исключен, поскольку мне пришлось бы вычислять общее расстояние всех возможных отображений, которых, как мне кажется, n! (где n - количество неперекрывающихся пикселей в одной фигуре), умноженное на вычисление для вычисления расстояния для каждой пары точек в отображении, n, что дает общее количество O (n * n!) или что-то подобное.

Backtracking: Единственное «лучшее» решение, о котором я мог подумать, это использовать backtracking, где я бы отслеживал текущий минимум до сих пор и в любой момент, когда я оцениваю определенное отображение, если я достигаю или превышаю этот минимум, я перехожу к следующему отображению. Даже это не будет лучше, чем O (n!).

Есть ли способ решить эту проблему с разумной сложностью?

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

Упрощенный подход?: В качестве вторичного вопроса, если выполнимого решения не существует, одной из возможностей может быть разбиение каждого непересекающегося раздела на небольшие области и сопоставление этих областей, что значительно сокращает количество отображений. Чтобы рассчитать расстояние между двумя регионами, я бы использовал центр масс (среднее положение пикселей в регионе). Тем не менее, это создает проблему, связанную с тем, как я должен выполнить разбиение, чтобы получить почти оптимальный ответ.

Любые идеи приветствуются !!

Answer 1

Это проблема минимального соответствия, и вы правы, что это сложная проблема в целом. Однако для случая 2D евклидова двойного минимального соответствия это разрешимо близко к O (n²) (см. Ссылку).

Для быстрого приближения FryGuy находится на правильном пути с имитацией отжига. Это один из подходов.

Также взгляните на Алгоритмы аппроксимации для двудольного и недвудольного сопоставления в плоскости для O ((n / ε) ^ 1.5 * log ^ 5 (n)) (1 + ε) -рандомизированная схема аппроксимации.

Answer 2

Вы можете рассмотреть имитированный отжиг для этого. Начните с случайного назначения A [x] -> B [y] для каждого пикселя и вычислите сумму квадратов расстояний. Затем случайным образом поменяйте местами пару отображений x <-> y. Затем выберите принять это с вероятностью Q, где Q выше, если новое отображение лучше, и стремится к нулю с течением времени. См. Статью в Википедии для лучшего объяснения.

Answer 3

1. Сортировка пикселей по форме A: в порядке возрастания ординат «x» и «y»
2. Сортировка пикселей по форме B: в порядке убывания «x» и последующего увеличения «y»

Сопоставить пиксели с тем же индексом: в отсортированном списке первый пиксель в A будет сопоставлен с первым пикселем в B. Разве это не отображение, которое вы ищете?