Să folosim acest ultim exemplu pentru a explora mai detaliat convoluția bidimensională. La fel ca în cazul semnalelor unidimensionale, convoluția imaginii poate fi văzută din partea de intrare sau din partea de ieșire. Așa cum vă reamintiți din capitolul 6, punctul de vedere spre intrare este cea mai bună descriere a modului în care lucrează convoluția, în timp ce punctul de vedere al ieșirii este modul în care majoritatea matematicii și algoritmilor sunt scrise. Trebuie să vă simțiți confortabil în ambele moduri de a privi operația.

Figura 24-14 prezintă descrierea părții de intrare a convoluției imaginii. Fiecare pixel din imaginea de intrare duce la adăugarea unei PSF scalate și deplasate la imaginea de ieșire. Imaginea de ieșire este apoi calculată ca suma tuturor PSF-urilor care contribuie. Această ilustrare prezintă contribuția la imaginea de ieșire din punctul de la locația [r,c] din imaginea de intrare. PSF este deplasată astfel că pixelul [0,0] din PSF se aliniază cu pixelul [r,c] în imaginea de ieșire. Dacă PSF este definită doar cu indici pozitivi, cum ar fi în acest exemplu, PSF-ul deplasată va fi în întregime în dreapta-jos a lui [r,c]. Nu fiți derutați de fața care apare cu susul în jos în această figură; această față cu fața în jos este PSF pe care o folosim în acest exemplu (figura 24-13a). În vederea pe partea de intrare, nu există rotație a PSF, aceasta este pur și simplu schimbată.

Figura 24-14 Convoluția imaginii văzută dinspre partea de intrare.

Fiecare pixel din imaginea de intrare contribuie cu o PSF scalată și deplasată la imaginea de ieșire. Imaginea de ieșire este suma acestor contribuții. Fața este răsturnată în această ilustrație deoarece aceasta este PSF pe care o utilizăm.

Convoluția imaginii văzută de la ieșire este ilustrată în figura 24-15. Fiecare pixel din imaginea de ieșire, așa cum este arătat de eșantion la [r, c], primește o contribuție de la mai mulți pixeli din imaginea de intrare. PSF se rotește cu 180° în jurul pixelului [0,0] și apoi se deplasează astfel încât pixelul [0,0] din PSF este aliniat cu pixelul [r, c] din imaginea de intrare. Dacă PSF utilizează numai indici pozitivi, va fi în stânga-sus a pixelului [r, c] din imaginea de intrare. Valoarea pixelului la [r, c] în imaginea de ieșire se găsește prin înmulțirea pixelilor în PSF rotită cu pixelii corespunzători din imaginea de intrare și prin însumarea produselor. Această procedură este dată de Ec. 24-3, și în programul din tabelul 24-1.

Observați că rotația PSF care rezultă din convoluție a anulat rotația făcută în proiectarea PSF. Aceasta face ca fața să apară vertical în fig. 24-15, permițându-i să fie în aceeași orientare cu modelul de detectat în imaginea de intrare. Adică, am folosit cu succes convoluția pentru a implementa corelația. Comparați fig. 24-13c cu fig. 24-15 pentru a vedea cum pata luminată din imaginea de corelație semnifică faptul că ținta a fost detectată.

Figura 24-15 Convoluția imaginii văzută dinspre partea de ieșire.

Fiecare pixel din semnalul de ieșire este egal cu suma pixelilor din PSF rotită, multiplicată cu pixelii corespondenți în imaginea de intrare.

Convoluția FFT oferă aceeași imagine de ieșire ca programul convoluției convenționale din tabelul 24-1. Timpul de execuție redus furnizat de convoluția FFT merită cu adevărat complexitatea suplimentară a programului? Să aruncăm o privire mai atentă. Figura 24-16 arată o comparație a timpului de execuție între convoluția convențională folosind virgula mobilă (etichetată FP), convoluția convențională folosind numere întregi (etichetate INT) și convoluția FFT folosind virgula mobilă (etichetată FFT). Sunt prezentate date pentru două dimensiuni diferite de imagine, 512×512 și 128×128.

În primul rând, observați că timpul de execuție necesar pentru convoluția FFT nu depinde de dimensiunea nucleului, rezultând linii plate în acest grafic. Pe un computer personal Pentium de 100 MHz, o imagine de 128×128 poate fi pusă în convoluție în aproximativ 15 secunde utilizând convoluție FFT, în timp ce o imaginede 512×512 necesită mai mult de 4 minute. Adunând numărul de calcule se arată că timpul executării pentru convoluția FFT este proporțional cu N²Log₂(N), pentru o imagine N×N. Adică, o imagine de 512×512 necesită aprox. de 20 de ori atâta timp cât o imagine de 128×128 pixeli.

Convoluția convențională are o durată de execuție proporțională cu N²M² pentru o imagine N×N în convoluție cu un nucleu de M×M. Acest lucru poate fi înțeles prin examinarea programului din tabelul 24-1. Cu alte cuvinte, timpul de execuție pentru convoluția convențională depinde foarte puternic de dimensiunea kernelului utilizat. Așa cum se poate vedea în grafic, convoluția FFT este mai rapidă decât convoluția convențională utilizând virgula mobilă dacă kernelul este mai mare de aprox. 10×10 pixeli. În majoritatea cazurilor, întregii pot fi utilizați pentru convoluția convențională, crescând pragul de rentabilitate la aprox. 30×30 pixeli. Aceste puncte de rentabilitate depind ușor de dimensiunea imaginii de pus în convoluție, așa cum se pot vedea în grafic. Conceptul de rememorat este că convoluția FFT este utilă numai pentru nuclee (kernel) largi de filtrare.