Come si moltiplicano gli spettri di due immagini di dimensioni diverse?

Question

Questa non è una domanda di "programmazione". Ma sono sicuro che è qualcosa che è ampiamente conosciuto e compreso in questa comunità.

Ho un'immagine, x, e un'immagine molto più piccola, y, e ho bisogno di convolvolare i due moltiplicando i loro FFT. Ma dal momento che non sono della stessa dimensione, non so come fare la moltiplicazione del dominio della frequenza.

Prendo la FFT (bidimensionale) di x (che è una matrice di numeri interi 4096 x 4096), che mi dà la rappresentazione del dominio di frequenza, X (che è una matrice di numeri complessi e penso che sia la sua dimensione è 2048 x 2048).

Analogamente, prendo la (FFT bidimensionale di y (che è una matrice intera di dimensione 64 x 64), che mi dà la rappresentazione del dominio della frequenza, Y (che è anche una matrice di numeri complessi e penso la dimensione è 32 x 32.

Sto usando la funzione fourn in Ricette numeriche, quindi le mie matrici di input, xey devono essere compresse in matrici unidimensionali, che vengono sostituite dalle loro trasformate di Fourier discrete, X e Y. Il punto è che anche se questo è un problema bidimensionale con le immagini, sto lavorando con array monodimensionali

Se stavo cercando di convolvolare due immagini delle stesse identiche dimensioni, xey. esso sarebbero tutti molto semplice:

X = FFT(x) 

Y = FFT(y) 

Z = X * Y (term by term multiplication) 

Convolution of x and y = IFFT(Z) 

Ma se X e Y sono diverse lunghezze, come faccio a fare la moltiplicazione?

Una possibilità è di estrarre y per avere le stesse dimensioni di x. Ma questo sembra orribilmente inefficiente. Un'altra possibilità è di estrarre Y per avere le stesse dimensioni di X. Ma non so cosa significhi nello spazio delle frequenze.

Ecco un altro modo di porre questa domanda: Se voglio convogliare due immagini di dimensioni molto diverse usando FFT così posso fare moltiplicazione dei loro spettri (rappresentazione del dominio della frequenza), come faccio a fare quella moltiplicazione?

Grazie,

~ Michael.

Answer 1

Il riempimento dell'array più piccolo (il kernel della convoluzione, y nel tuo caso) con zeri per corrispondere alla dimensione dell'immagine in ingresso (la matrice x) è l'approccio standard. Che sarebbe essere orribilmente inefficiente se si stesse facendo la convoluzione nel dominio spaziale, ma se si stanno moltiplicando gli FFT, è necessario, e il costo del calcolo della FFT dell'array imbottito non è poi così male.

Answer 2

Hai ragione nel pensare che le due spaziature di frequenza debbano essere le stesse. Prendete un esempio 1D (sto usando la sintassi Matlab):

N = 4096; 
M = 64; 

x = randn(N, 1); 
y = hann(M, 'symmetric'); 

zLinear = conv(x,y); 
zCircular = ifft(fft(x) .* fft(y,N)); 

disp(max(abs(zLinear(65:4096) - zCircular(65:4096)))); 

La differenza tra le due tecniche è ~ 2e-14, errore di arrotondamento così. Si noti che è necessario saltare i primi 64 campioni a causa della differenza tra la convoluzione lineare e circolare.

Nel calcolo di zCircolare, nota fft (y, N), che è la sintassi di Matlab per il riempimento del segnale y con zeri fino a N prima del calcolo del fft.Questo potrebbe essere considerato inefficiente di utilizzo di memoria, ma confrontare la velocità:

convoluzione lineare: 4096 moltiplica/aggiunge di 64 ciascuna = 262144 moltiplicare/aggiunge

convoluzione circolare: 2 FFT di 4096 + 1 complessa moltiplicare di 2 * 4096 elementi + 1 FFT inversa
= 3 * 4096 * log2 (4096) + 4096 * 6 = 172032 (supponendo 6 operazioni per il complesso moltiplicano)

Fondamentalmente, la velocità NlogN della FFT, anche quando si servono tre di essi, batte l'operazione di convoluzione N * M a meno che M sia molto breve.

EDIT stima di velocità Aggiungi per caso 2D

Vale la pena di aggiungere che per i dati 2D il vantaggio della velocità viene ingrandita. Una FFT 2D prende le operazioni N * N * log2 (N * N), quindi l'FFT 3 + N^2 complesso si moltiplica per N = 4096 e le operazioni 1.3e10. Ma la convoluzione diretta è N^2 * M^2 = 6.9e10 operazioni, alcune 50 volte più lente.