Алгоритм для сопоставления пар из двух наборов

У меня есть два набора, каждый набор представляет собой список пары чисел

Set1 =[(x1, y1), (x2, y2), ..., (xN, yN)]
Set2 =[(a1, b1), (a2, b2), ..., (aN, bN)]

При построении графика на плоскости XY Set1 и Set2 имеют одинаковую базовую форму, однако точки данных set2 являются развернутой/переведенной/масштабированной/шумной/перекошенной версией set1. Порядок пар в каждом наборе случайный. Есть ли эффективный способ определить, какие точки в set1 соответствуют их аналогам в set2?

Ответ 1

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

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

Надеюсь, это поможет!

Ответ 2

Да, при условии, что это можно сделать только с помощью Rotations, Scalings and Translations (за исключением части "шум" и "перекос", о которой я не уверен).

Один подход:

Определите Centroid (среднее значение 2D) для каждого набора.
Определите крутизну наименьших квадратов (2D) каждого набора.
Определите двумерный разброс каждого набора.
Перенесите первый набор, используя разницу Centroid для перевода, разности наклона для поворота (*) и разницы в вариациях к шкале, так что оба набора теперь имеют одинаковые Centroid, Slope и Variance.
Сортируйте оба набора, а затем сравните точки для равенства/подобия. (В качестве альтернативы вы можете сделать разницу RSM (среднеквадратичное значение) между ними как меру "шум" /разницу).

(* - Обратите внимание, что отражения и/или симметрии могут вызвать проблемы с частью вращения.)