Modo rapido per implementare la convoluzione 2D in C

Question

Sto cercando di implementare un algoritmo di visione, che include uno stadio di pre-filtraggio con un filtro di 9x9 Laplacian-of-Gaussian. Puoi indicare un documento che spiega brevemente le implementazioni rapide dei filtri? Penso che dovrei fare uso di FFT per il filtraggio più efficiente.

Answer 1

Sei sicuro di voler utilizzare FFT? Questa sarà una trasformazione dell'intero array, che sarà costosa. Se hai già deciso un filtro a convoluzione 9x9, non hai bisogno di FFT.

In genere, il modo più economico per eseguire la convoluzione in C è impostare un ciclo che sposta un puntatore sull'array, sommando i valori convoluti in ogni punto e scrivendo i dati in un nuovo array. Questo ciclo può quindi essere parallelizzato usando il tuo metodo preferito (vettorizzazione del compilatore, librerie MPI, OpenMP, ecc.).

Per quanto riguarda i confini:

• Se si assume i valori da 0 al di fuori dei confini, quindi aggiungere un bordo 4 elemento da 0 a vostra matrice 2D di punti. Ciò eviterà la necessità di istruzioni `if` per gestire i limiti, che sono costosi.
• Se i dati si sovrappongono ai limiti (cioè sono periodici), quindi utilizzare un modulo o aggiungere un bordo di 4 elementi che copia il lato opposto della griglia (abcdefg -> fgabcdefgab per 2 punti). ** Nota: questo è quello che stai assumendo implicitamente con qualsiasi tipo di trasformata di Fourier, inclusa FFT **. Se questo non è il caso, dovresti tenerne conto prima che venga eseguita qualsiasi FFT.

I 4 punti sono perché la sovrapposizione limite massima di un kernel 9x9 è di 4 punti all'esterno della griglia principale. Quindi, n punti di confine necessari per un kernel 2n + 1 x 2n + 1.

Se hai bisogno di questa convoluzione per essere molto veloce e/o la tua griglia è grande, prova a suddividerla in parti più piccole che possono essere conservate nella cache del processore, e quindi calcolate molto più rapidamente. Questo vale anche per qualsiasi offload della GPU che potresti voler fare (sono ideali per questo tipo di calcolo in virgola mobile).

Answer 2

Ecco un link teoria http://hebb.mit.edu/courses/9.29/2002/readings/c13-1.pdf

Ed ecco un link per FFTW, che è una libreria piuttosto bene FFT che ho usato in passato (licenze di controllo per assicurarsi che sia adatto) http://www.fftw.org/

Tutto ciò che fai è FFT, la tua immagine e il tuo kernel (la matrice 9x9). Moltiplica insieme, quindi torna a trasformare.

Tuttavia, con una matrice 9x9 potrebbe essere ancora meglio farlo in coordinate reali (solo con un doppio ciclo sopra i pixel dell'immagine e la matrice). Prova in entrambe le direzioni!

Answer 3

In realtà non è necessario utilizzare una dimensione FFT abbastanza grande da contenere l'intera immagine. Puoi fare molti piccoli fd 2d sovrapposti più piccoli. È possibile cercare "convoluzione rapida" "sovrapposizione salva" "sovrapposizione aggiungi".

Tuttavia, per un kernel 9x9. Potresti non vedere molto vantaggio in velocità.