Alternativa a distanza metrica in algoritmo vicino più prossimo?

Question

mi sono imbattuto in un'implementazione dell'algoritmo vicino più prossimo per la ricerca di corrispondenze tra alcuni punti chiave in due immagini simili. I punti chiave sono stati generati dall'algoritmo SIFT. I punti sono descritti da un vettore 128 dimensione, e ci sono molti punti in entrambe le immagini.

L'algoritmo di corrispondenza utilizza la ricerca vicino più prossimo e per ciascun punto in un'immagine, calcola il punto più vicino corrispondente nell'altra immagine. La 'vicinanza' è rappresentato dalla distanza euclidea minima tra i vettori dei punti. Per tali partite sono scelti tenendo solo le coppie di punti la cui si trova sotto una certa soglia di distanza.

Tuttavia all'attuazione mi sono tutti moltiplica tutti i vettori dei punti chiave in un'immagine, con quelli nell'altra immagine, formando così una matrice di prodotti. Quindi trova i punti il ??cui prodotto è superiore ad una determinata soglia.

Questa implementazione dà risultati corretti, ma mi piacerebbe sapere come funziona. La usa correlazione tra i vettori come metrica o c'è qualcos'altro qui.

Answer 1

Sembra che non è una questione di diversi prodotti interni, dopo tutto, non è nemmeno una questione di prodotto scalare in sé. Si scopre che si tratta di una questione di semplice matematica.

In sostanza ...

Si supponga abs (A + B) = C, dove C è una costante. Il valore massimo di un * b sarà sempre il risultato (s) dove a == b == + - C / 2. Pertanto, la distanza tra A e B sarà minimo quando il loro prodotto è massima, e viceversa. Questo funziona per tutti i numeri reali (positivi e negativi) e si estende anche in più dimensioni, quindi probabilmente funziona con i numeri complessi nonché (se non ho provato con tale).

Esempio con C = 20:

((a, b), distanza, prodotto)

((0, 20), 20.0, 0)
((1, 19), 18.0, 19)
((2, 18), 16.0, 36)
((3, 17), 14.0, 51)
((4, 16), 12.0, 64)
((5, 15), 10.0, 75)
((6, 14), 8.0, 84)
((7, 13), 6,0, 91)
((8, 12), 4,0, 96)
((9, 11), 2,0, 99)
((10, 10), 0.0, 100) (Come si può vedere, la distanza è minima, mentre il prodotto è massima.)
((11, 9), 2,0, 99)
((12, 8), 4,0, 96)
((13, 7), 6.0, 91)
((14, 6), 8.0, 84)
((15, 5), 10.0, 75)
((16, 4), 12.0, 64)
((17, 3), 14,0, 51)
((18, 2), 16.0, 36)
((19, 1), 18,0, 19)
((20, 0), 20,0, 0)