Prestazioni OpenCV sulla corrispondenza dei modelli

Question

Sto provando a fare la corrispondenza dei modelli fondamentalmente su java. Ho usato un algoritmo semplice per trovare la corrispondenza. Ecco il codice:

minSAD = VALUE_MAX; 
// loop through the search image 
for (int x = 0; x <= S_rows - T_rows; x++) { 
    for (int y = 0; y <= S_cols - T_cols; y++) { 
     SAD = 0.0; 

     // loop through the template image 
     for (int i = 0; i < T_rows; i++) 
      for (int j = 0; j < T_cols; j++) { 

       pixel p_SearchIMG = S[x+i][y+j]; 

       pixel p_TemplateIMG = T[i][j]; 

       SAD += abs(p_SearchIMG.Grey - p_TemplateIMG.Grey); 
      } 
    } 

    // save the best found position 
    if (minSAD > SAD) { 
     minSAD = SAD; 
     // give me VALUE_MAX 
     position.bestRow = x; 
     position.bestCol = y; 
     position.bestSAD = SAD; 
    } 
} 

Ma questo è un approccio molto lento. Ho provato 2 immagini (768 × 1280) e immagini secondarie (384 x 640). Questo dura per secoli. openCV esegue la corrispondenza dei modelli molto più velocemente o meno con la funzione ready cvMatchTemplate()?

Answer 1

Troverete openCV cvMatchTemplate() è molto più veloce del metodo che avete implementato. Quello che hai creato è un metodo di corrispondenza dei modelli statistici. È il più comune e il più semplice da implementare, tuttavia è estremamente lento su immagini di grandi dimensioni. Diamo un'occhiata alla matematica di base che hai un'immagine che è 768x1280 fai un loop su ognuno di questi pixel meno il bordo dato che questo è il tuo limite di template (768 - 384) x (1280 - 640) che 384 x 640 = 245 ' 760 operazioni in cui passi in loop ogni pixel del tuo modello (altre 245'760 operazioni) quindi prima di aggiungere qualsiasi matematica nel tuo loop hai già (245'760 x 245'760) 60'397'977'600 operazioni. Oltre 60 miliardi di operazioni solo per scorrere l'immagine È più sorprendente il modo in cui le macchine veloci possono farlo.

Ricorda tuttavia il suo 245'760 x (245'760 x operazioni matematiche) quindi ci sono molte più operazioni.

Ora cvMatchTemplate() utilizza effettivamente l'operazione di corrispondenza del modello di analisi di Fourier. Questo funziona applicando una trasformazione Fast Fourier (FFT) sull'immagine in cui i segnali che compongono il pixel cambia di intensità sono segmentati in ciascuna delle forme d'onda corrispondenti. Il metodo è difficile da spiegare bene ma l'immagine viene trasformata in una rappresentazione del segnale di numeri complessi. Se desideri saperne di più, cerca su goggle per lo fast fourier transform. Ora la stessa operazione viene eseguita sul modello, i segnali che formano il modello vengono utilizzati per filtrare qualsiasi altro segnale dall'immagine.

In semplice sopprime tutte le funzionalità all'interno dell'immagine che non hanno le stesse caratteristiche del modello. L'immagine viene quindi riconvertita usando una trasformata di Fourier veloce inversa per produrre immagini in cui valori alti significano una corrispondenza e valori bassi significano il contrario. Questa immagine è spesso normalizzata, quindi 1 rappresenta una corrispondenza e 0 o 0 significa che l'oggetto non è vicino.

Attenzione però se l'oggetto non è nell'immagine ed è normalizzato, il rilevamento falso si verificherà poiché il valore più alto calcolato verrà considerato come una corrispondenza. Potrei andare avanti per anni su come funziona il metodo e sui suoi vantaggi o problemi, ma ...

Il motivo per cui questo metodo è così veloce è: 1) opencv è un codice C++ altamente ottimizzato. 2) La funzione fft è facile da gestire per il processore poiché la maggior parte ha la capacità di eseguire questa operazione in hardware. Le schede grafiche GPU sono progettate per eseguire milioni di operazioni FFT ogni secondo, poiché questi calcoli sono altrettanto importanti nella grafica di gioco ad alte prestazioni o nella codifica video. 3) La quantità di operazioni richieste è molto inferiore.

Nel metodo di corrispondenza dei modelli statistici estivi è lento e richiede anni, mentre opencv FFT o cvMatchTemplate() è veloce e altamente ottimizzato.

La corrispondenza del modello statistico non produce errori se un oggetto non è presente mentre FFT opencv può essere utilizzato a meno che non si prenda cura della sua applicazione.

Spero che questo ti dia una comprensione di base e risponda alla tua domanda.

Acclamazioni

Chris

[EDIT]

Per rispondere ulteriormente i Domande:

Hi,

cvMatchTemplate può lavorare con CCOEFF_NORMED e CCORR_NORMED e SQDIFF_NORMED tra cui la non versione normalizzata di questi. Here mostra il tipo di risultati che puoi aspettarti e ti dà il tuo codice con cui giocare.

http://dasl.mem.drexel.edu/~noahKuntz/openCVTut6.html#Step%202

I tre metodi sono ben citati e molti articoli sono disponibili attraverso Google scholar. Ho fornito alcuni documenti qui sotto. Ognuno usa semplicemente un'equazione diversa per trovare la correlazione tra i segnali FFT che formano il modello e i segnali FFT presenti nell'immagine. Il coefficiente di correlazione tende a produrre risultati migliori nella mia esperienza ed è più facile trovare riferimenti. La somma della differenza al quadrato è un altro metodo che può essere utilizzato con risultati comparabili. Spero che alcuni di questi aiuti:

Fast normalized cross correlation for defect detection Du-Ming Tsai; Chien-Ta Lin; Pattern Recognition Letters Volume 24, Numero 15, Novembre 2003, Pages 2625-2631

Template Matching using Fast Normalised Cross Correlation Kai Briechle; Uwe D. Hanebeck;

Relative performance of two-dimensional speckle-tracking techniques: normalized correlation, non-normalized correlation and sum-absolute-difference Friemel, B.H .; Bohs, L.N .; Trahey, G.E .; Ultrasonics Symposium, 1995. Proceedings. 1995 IEEE

A Class of Algorithms for Fast Digital Image Registration Barnea, Daniel I .; Silverman, Harvey F .;
Computer, IEEE Transactions on Feb. 1972

Si è spesso favorito per utilizzare la versione normalizzata di questi metodi come tutto ciò che equivale a un 1 è una partita se non oggetto è presente si può ottenere falsi positivi. Il metodo funziona velocemente semplicemente a causa del modo in cui è istigato nel linguaggio del computer. Le operazioni coinvolte sono ideali per l'architettura del processore, il che significa che è in grado di completare ciascuna operazione con pochi cicli di clock anziché spostare la memoria e le informazioni su più cicli di clock. I processori hanno risolto i problemi FFT da molti anni e, come ho detto, c'è un hardware integrato per farlo. L'hardware basato è sempre più veloce del software e il metodo statistico di corrispondenza dei modelli è basato su software di base.Buona lettura per l'hardware può essere trovato qui:

Digital signal processor Anche se una pagina Wiki i riferimenti sono la pena dare un'occhiata un modo efficace questo è l'hardware che esegue i calcoli FFT

A new Approach to Pipeline FFT Processor Shousheng Lui; Mats Torkelson; Uno dei miei preferiti in quanto mostra che cosa sta succedendo all'interno del processore

An Efficient Locally Pipelined FFT Processor Liang Yang; Kewei Zhang; Hongxia Liu; Jin Huang; Shitan Huang;

Questi documenti mostrano davvero quanto sia complessa la FFT quando viene implementata, tuttavia il rivestimento del tubo del processo è ciò che consente di eseguire l'operazione in pochi cicli di clock. Questo è il motivo per cui i sistemi basati sulla visione in tempo reale utilizzano FPGA (in particolare progettare processori che è possibile progettare per implementare un task impostato) in quanto possono essere progettati in modo estremamente parallelo nell'architettura e il rivestimento dei tubi è più facile da implementare.

Anche se devo menzionare che per FFT di un'immagine in realtà stai usando FFT2 che è la FFT della pianura orizzontale e la FFT della pianura verticale solo così non c'è confusione quando trovi un riferimento ad essa. Non posso dire di avere una conoscenza approfondita del modo in cui le equazioni sono state implementate e la FFT è stata implementata Ho cercato di trovare delle buone guide ma trovare una buona guida è molto difficile, tanto che non ne ho ancora trovato una (non una che posso capire a meno). Un giorno potrei capirli ma per sapere ho una buona comprensione di come funzionano e del tipo di risultati che ci si può aspettare.

Oltre a questo, non posso davvero aiutarti di più se vuoi implementare la tua versione o capire come funziona è ora di colpire la libreria ma ti avverto che il codice opencv è ottimizzato così bene che farai fatica ad aumentare la sua performance comunque chi lo sa può trovare un modo per ottenere risultati migliori e buona fortuna

Chris