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

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

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 (среднеквадратичное значение) между ними как меру "шум" /разницу).

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