Corrispondenza della posizione più vicina di una sequenza da un'altra

Question

Corrispondenza della posizione più vicina di una sequenza da un'altra

#1 da (2 voti)
#2 da (1 voti)

2

Ho 2 sequenze:

Uno è un videoclip con l'immagine scattata dalla fotocamera di un drone
L'altro è un file con un elenco di dati cronologici dai sensori

Esempio:

time 0: speed_x=1, latitude=0.001, longitude=0.2, altitude=40 
time 112: speed_x=3, latitude=0.0021, longitude=0.221, altitude=30 
time 232: speed_x=3, latitude=0.0021, longitude=0.221, altitude=35 
time 425: speed_x=3.1, latitude=0.0024, longitude=0.222, altitude=40 
…

* il tempo arriva in millisecondi

Ho creato un'applicazione che riproduce il video (questa è la parte facile) ma Voglio visualizzare le informazioni sul volo in una data posizione del video.

Il problema è che, per visualizzare i dati del sensore in una data posizione del video (in un dato momento), dovrei attraversare l'elenco dei dati del sensore per trovare i dati del sensore che è più vicino a quella posizione

Ad esempio:

Se il video mostra il frame a 150 millisecondi e nell'elenco dei dati del sensore ho questi elementi nell'elenco dei dati del sensore:

time 0:
time 90: …
time 120: …
time 200: …
time 230: …

Quindi, dovrei scegliere di mostrare i dati del sensore sull'oggetto con time=120 , perché è quello che è più vicino a 150 ms.

Posso fare un algoritmo di ricerca per effettuare la ricerca, ma sarò davvero inefficiente a percorrere l'intera lista di dati dai sensori calcolando le distanze e scegliendo quella con la distanza minima.

Quindi, ho pensato di creare una sorta di dizionario / tabella hash che, data una posizione nel video, avrebbe recuperato i dati del sensore appropriati.

Tuttavia, non ho mai creato una struttura dati di ricerca suck. Non so nemmeno che sia fattibile! Ho usato dizionari e tabelle hash che hanno dato una chiave discreta, si ottiene un risultato. Ma nel mio caso, ho un insieme di valori virtualmente infinito che si tradurrà nello stesso articolo.

Puoi, per favore, dirmi come risolvere questo problema?

Grazie!

algorithms

posta SuperJMN 08.10.2018 - 22:31

fonte

2 risposte

Leggi altre domande sui tag algorithms

Restringi il modello di dominio se il servizio non viene utilizzato In che modo gli eventi nel contesto di Event Sourcing sono diversi dai comandi?

score 2 · Answer 1

Se dovessi creare una tabella hash, dovresti avere una voce per ogni possibile time code video.

Ma puoi certamente usare una mappa ordinata. Devi cercare il codice temporale e se non c'è una corrispondenza esatta, prendi l'elemento prima.

In C ++ potresti ad esempio usare un std::map , usare lower_bound() per ottenere un iteratore sul primo elemento non inferiore al time code. Se non corrisponde esattamente, decrementa semplicemente l'iteratore.

In Java, ad esempio, utilizzi un TreeMap e utilizza floorEnry() per ottenere primo elemento più piccolo o uguale al codice temporale che stai cercando.

score 1 · Answer 2

L'algoritmo di ricerca che stai cercando si chiama ricerca binaria , che è abbastanza efficiente.

Nota durante la riproduzione del video, in genere devi controllare ripetutamente l'indice temporale del fotogramma successivo, in ordine crescente. Quindi, una volta effettuata una ricerca iniziale, trovando un indice i nell'elenco dei dati del sensore per un indice temporale t , la successiva ricerca di t+t0 (dove t0 è l'intervallo di tempo tra due fotogrammi) può essere efficientemente fatto controllando successivamente i record di dati i , i+1 , i+2 , ..., e prendi quello più vicino (fermandosi quando la distanza temporale da t+t0 inizia ad aumentare). Supponendo che gli intervalli di tempo tra i record nell'elenco dei dati del sensore non siano molto inferiori a t0 , questa ricerca terminerà dopo uno o due passaggi (se l'intervallo è garantito superiore a t0 , si può interrompere la ricerca in i+1 ).

Se ti aspetti che il posizionamento casuale nel tuo video (e quindi la necessità di una ricerca casuale nei tuoi record di dati) avvenga di rado, e giochi in avanti come caso d'uso standard, potrebbe risultare che non hai nemmeno bisogno della ricerca binaria . Non ottimizzare qualcosa se non è necessario.