Sto lavorando con la correlazione 2d per le tecniche di elaborazione delle immagini (riconoscimento dei pattern ecc ...). Mi chiedevo se ci fosse un approccio teorico su come dire quando usare la moltiplicazione nello spazio di frequenza sulla correlazione nello spazio temporale. Per le dimensioni di 2 x lo spazio di frequenza è ovviamente più veloce, ma per quanto riguarda le dimensioni piccole e prime come per es. 11?
Suppongo che questo venga fatto su una CPU convenzionale, un core, eseguendo un thread semplice, senza hardware di fantasia. Se c'è più di quello che sta succedendo, probabilmente può essere spiegato con aggiustamenti al ragionamento per un sistema più semplice. Non si può dire molto di più senza un sistema specifico da discutere o un intero libro di testo o di ricerca per coprire una serie di possibilità.
Non mi preoccuperei della potenza di due dimensioni. Non importa. Algoritmi FFT con le unità a farfalla e tutto ciò che esiste per fattori di 3 o qualsiasi piccolo numero, non solo 2. Esistono anche algoritmi intelligenti per le serie di dati di dimensioni primarie. Non mi piace citare Wikipedia su questo a causa della sua natura impermanente, ma comunque:
there are FFTs with O(N log N) complexity for all N, even for prime N
Le implementazioni di FFT per N arbitrari possono essere trovate nella libreria GPL'a FFTW .
L'unico modo affidabile in termini di ingegneria seria è quello di costruire e misurare, ma certamente possiamo ottenere un'idea dalla teoria, per vedere le relazioni tra le variabili. Abbiamo bisogno di stime di quante operazioni aritmetiche sono coinvolte per ogni metodo.
Moltiplicare è ancora più lento dell'aggiunta sulla maggior parte delle CPU, anche se la differenza si è notevolmente ridimensionata nel corso degli anni, quindi contiamo solo le moltiplicazioni. Anche la contabilità per addizioni richiede un po 'più di riflessione e tiene traccia di tutto.
Una semplice convoluzione, in realtà moltiplicando e aggiungendo usando il kernel della convoluzione, ripetendo per ogni pixel in uscita, ha bisogno di moltiplicazioni W² · K², dove W è il numero di pixel lungo un lato dell'immagine (assumendo il quadrato per semplicità), e K è la dimensione del kernel della convoluzione, come pixel lungo un lato. Sono necessarie moltiplicazioni K² per calcolare un pixel di uscita utilizzando il kernel e la porzione di dimensioni uguali dell'immagine di input. Ripeti l'operazione per tutti i pixel di uscita, che corrispondono come nell'immagine di input.
(N mults ) direct = W² · K²
Per fare il lavoro nello spazio di Fourier, dobbiamo trasformare l'immagine in Fourier. Questo viene fatto applicando una FFT a ciascuna colonna separatamente, e quindi a ciascuna riga. La FFT per N data point richiede circa 2N · log (N) moltiplicazioni; vogliamo che N sia W, la lunghezza di una colonna o riga. Tutti i logaritmi qui sono di base due.
Ci sono colonne W e W, quindi dopo che tutte le FFT sono state fatte, abbiamo fatto moltiplicazioni di 2W · (2W · log (W)). Raddoppia quello, perché dopo che ci siamo moltiplicati per la trasformata di Fourier del kernel, dobbiamo inversione - Fourier i dati per tornare all'immagine sensibile. Quello è 8W² · log (W). Ovviamente, si deve moltiplicare per la trasformata di Fourier del kernel, un'altra moltiplicazione W². (Fatto una volta, non una volta per pixel di uscita, per riga o altro.) Si tratta di moltiplicazioni complesse, quindi si tratta di moltiplicazioni reali di 4 W².
Quindi, a meno che non mi sia sforzato (e probabilmente l'ho fatto) abbiamo
(N mults ) Fourier = 4W² · (2 · log (W) + 1)
Quando vogliamo fare le cose in modo diretto? Quando K è sufficientemente piccolo per rendere W² · K² più piccolo di 4W² · (2 · log (W) + 1). Un fattore comune di W² è facilmente scomposto. Probabilmente possiamo eliminare il "+1" poiché abbiamo a che fare con stime idealizzate. Il +1 è probabilmente perso in errori relativi alle implementazioni reali, dal non contare aggiunte, overhead del loop e così via. Questo lascia:
K² < 8·log(W)
Questa è la condizione approssimativa per la scelta di un approccio diretto su un approccio spaziale di frequenza.
Si noti che la correlazione di due immagini della stessa dimensione è simile alla convoluzione con un kernel di dimensioni K = W. Lo spazio di Fourier è sempre il modo per farlo.
Questo può essere ridefinito e discusso per tener conto di overhead, pipelining di opcode, float vs. fixed point e gettato fuori dalla finestra con GPGPU e hardware specializzato.
Leggi altre domande sui tag complexity image-processing