allineare un set di punti 2D con un altro utilizzando solo traslazione e rotazione

Question

Sto lavorando in OpenCV ma non penso che ci sia una funzione per questo. Posso trovare una funzione per trovare trasformazioni affini, ma le trasformazioni affini includono il ridimensionamento e voglio solo considerare la rotazione + la traduzione.

Immaginate di avere due serie di punti in 2D - diciamo che ogni set ha esattamente 50 punti.

E.g. imposta A = {x1, y1, x2, y2, ..., x50, y50}

set B = {x1 ', y1', x2 ', y2', ..., x50 ', y50'}

Voglio trovare la combinazione di rotazione e traduzione che si avvicina al set di mappatura A sul set B. Immagino che definirei "più vicino" come minimizza la distanza media tra i punti in A e i punti corrispondenti in BIe, minimizza la media distanza tra (x1, y1) e (x1 ', y1'), ecc.

Immagino che potrei usare la forza bruta per verificare tutte le traduzioni e le rotazioni possibili, ma questo sarebbe estremamente inefficiente. Qualcuno sa un modo più semplice?

Grazie!

Answer 1

Questo problema ha una soluzione molto elegante in termini di decomposizione del valore singolare della matrice di prossimità (distanze tra coppie di punti). Il nome di questo è il orthogonal Procrustes problem, dopo la leggenda greca su un compagno che offriva ai viaggiatori un letto adatto a chiunque.

La soluzione deriva dal trovare la matrice ortogonale più vicina a una determinata matrice (non necessariamente ortogonale).

Answer 2

Il modo in cui lo farei in Excel è creare un paio di colonne che rappresentano i punti. Celle che rappresentano rotazione/traduzione di un set (non è necessario ruotare e tradurre entrambi). Quindi le colonne che rappresentano quegli stessi punti ruotati/tradotti.
Quindi un'altra colonna per la distanza tra i punti dei punti ruotati/tradotti.
Quindi una cella della somma delle distanze tra i punti. Infine, utilizzare il Risolutore per ottimizzare le celle di rotazione e di traduzione.

Answer 3

Se si corregge qualche rotazione è possibile ottenere una risposta utilizzando ternary search. Esegui la ricerca in xe per ogni x testato eseguilo in y per ottenere il valore migliore. Questo ti darà la risposta corretta poiché la funzione (somma delle distanze corrispondenti) è convessa (questo può essere provato osservando che la restrizione della funzione a qualsiasi linea è una funzione convessa unidimensionale, e l'ultimo è un fatto standard: il la somma di diverse funzioni convesse è convessa). Invece di forza bruta oltre l'angolo, posso proporre un tale metodo basato sulla ricerca ternaria. Scegli un passo non molto grande S. Calcola la funzione bersaglio per ogni angolo in (0, S, 2S, ...). Quindi, se S è abbastanza piccolo, possiamo escludere alcuni segmenti (iS, (i + 1) S) dalla considerazione. Vale a dire quelli con valori relativamente grandi di funzione con gli angoli iS e (i + 1) S. Essendo implementato con attenzione questo può dare una risposta e può farlo più velocemente della forza bruta.