Struttura dei dati per unire punti per misura di similarità

Question

Struttura dei dati per unire punti per misura di similarità

#1 da (1 voti)

0

Ho una serie di punti (x,y) e ogni punto ha un colore ( nello spazio colore LAB ). Devo associare i punti con un colore simile e poi spazialmente. Quindi il risultato finale è che ciascun punto diventa parte di un cluster o segmento locale.

Esiste una struttura dati specifica adatta a tale scenario? Sto cercando di trovare una struttura dati in grado di trovare in modo efficiente i n punti circostanti di un punto specifico.

Essenzialmente ho bisogno di selezionare il punto P e trovare i punti circostanti. Per ciascun punto circostante ( Q ); misurare la distanza del colore euclideo tra P e Q , se la distanza è all'interno di una soglia, questi punti ottengono la stessa etichetta. Quindi ripeti per il punto Q fino a quando Q è circondato da punti della sua stessa etichetta o punti che sono troppo diversi per accumularsi.

Sono a conoscenza di algoritmi di apprendimento automatico che potrebbero ottenere ciò che voglio; SVM (Support Vector Machines) tuttavia non è abbastanza veloce. Se esiste una struttura dati che può eseguire questo più velocemente è più desiderabile.

design c++ data-structures

posta Jake M 28.10.2018 - 15:28

fonte

1 risposta

Leggi altre domande sui tag design c++ data-structures

Parametri vs Funzioni specializzate Attività del ciclo di eventi e esecuzione di ordini di micro compiti

score 1 · Answer 1

Sembra che tu stia descrivendo un algoritmo di clustering gerarchico basato sul linkage. Tuttavia, hai una metrica insolita: due punti non hanno una distanza scalare, ma una distanza-coordinata separata e una distanza colore. Questo potrebbe o potrebbe non essere un problema.

L'atto di trovare tutti gli elementi all'interno di una determinata distanza è una gamma di ricerca o intervallo di query . Ciò richiede un concetto di distanza / metrica. Potrebbe quindi essere necessario eseguire prima ricerche di intervalli basate sulla metrica delle coordinate e filtrare il set di risultati per tenere conto della metrica del colore. Sebbene questo approccio non sia generalmente possibile, funziona bene perché il componente della distanza del colore aumenta strettamente la distanza totale.

Anche in assenza di metrica, gli alberi k-d possono essere utilizzati per organizzare dati multidimensionali. Un albero k-d è un albero binario che partizioni su una dimensione diversa per ogni livello. Ciò consente query di intervallo un po 'efficienti perché possiamo ignorare i sottoalberi se tutti i loro elementi devono essere fuori intervallo, data la metrica. Lo spazio di ricerca è effettivamente delimitato da un ipercubo anziché da un'ipersfera definita dall'intervallo della query. Esistono strutture di dati spaziali più efficienti come le palle, ma gli alberi k-d sono facili da implementare.

Sebbene le strutture di dati ad albero abbiano interessanti complessità algoritmiche, queste non sono necessariamente importanti. Per insiemi di dati più piccoli, una serie di coordinate piatte che si esegue la scansione lineare potrebbe avere prestazioni migliori a causa degli effetti della cache. Se le coordinate si trovano su una griglia densamente popolata (ad esempio perché stai elaborando una bitmap), puoi eliminare le coordinate esplicite in quanto puoi facilmente calcolare gli offset di tutti i vicini.