Chiar dacă transformata Fourier este lentă, este totuși cel mai rapid mod de a face convoluția unei imagini cu un kernel mare de filtrare. De exemplu, convoluția unei imagini de 512×512 cu un PSF de 50×50 este de aproximativ 20 de ori mai rapidă folosind FFT comparativ cu convoluția convențională. Capitolul 18 discută modul în care funcționează convoluția FFT pentru semnale unidimensionale. Versiunea bidimensională este o simplă extensie.

Vom demonstra convoluția FFT cu un exemplu, un algoritm pentru a localiza un model predeterminat într-o imagine. Să presupunem că vom construi un sistem pentru inspectarea hârtiilor de un dolar, cum ar fi cele utilizate pentru controlul calității imprimării, detectarea contrafacerii sau verificarea plății într-un automat. Așa cum se arată în figura 24-11, este obținută o imagine de 100×100 pixeli a bancnotei, centrate pe portretul lui George Washington. Scopul este să căutați această imagine pentru un model cunoscut, în acest exemplu, imaginea de 29×29 pixeli a feței. Problema este aceasta: dat fiind o imagine achiziționată și un model cunoscut, care este cel mai eficient mod de a localiza unde (sau dacă) apare modelul în imagine? Dacă ați acordat atenție în capitolul 6, știți că soluția la această problemă este corelația (un filtru compatibil) și că poate fi implementată prin utilizarea unei convoluții.

Înainte de a efectua convoluția reală, există două modificări care trebuie făcute pentru a transforma imaginea țintă într-o PSF. Acestea sunt ilustrate în figura 24-12. Figura (a) arată semnalul țintă, modelul pe care încercăm să îl detectăm. În (b), imaginea a fost rotită cu 180°, la fel ca și când a fost rotită din stânga-dreapta și apoi răsturnată de sus-jos. Așa cum am discutat în capitolul 7, atunci când efectuăm corelația prin utilizarea convoluției, semnalul țintă trebuie inversat pentru a contracara inversarea care are loc în timpul convoluției. Vom reveni la această problemă în scurt timp.

Figura 24-11 Exemplu de detectare țintă.

Problema este de a cerceta imaginea de 100x100 pixeli a lui George Washington, (a), pentru modelul țintă (b), fața de 29x29 pixeli. Soluția optimă este corelația, care poate fi realizată prin convoluție.

A doua modificare este un truc pentru îmbunătățirea eficacității algoritmului. În loc să încercați să detectați fața din imaginea originală, este mai eficient să detectați muchiile feței în muchiile imaginii originale. Acest lucru se datorează faptului că muchiile sunt mai clare decât caracteristicile originale, ceea ce face ca corelația să aibă un vârf mai clar. Acest pas nu este necesar, dar rezultatele sunt semnificativ mai bune. În forma cea mai simplă, se aplică un filtru de detecție a muchiilor de 3×3 atât la imaginea originală, cât și la semnalul țintă, înainte de efectuarea corelării. Din proprietatea asociativă a convoluției, aceasta este aceeași ca și aplicarea filtrului de detecție muchii la semnalul țintă de două ori și lăsarea imaginii originale singure. În practică, aplicarea unui kernel 3x3 de detectare muchii numai odată este, în general, suficientă. Acesta este modul în care (b) este schimbat în (c) în figura 24-12. Acest lucru face (c) ca PSF să fie utilizată în convoluție.

Figura 24-12 Dezvoltarea unui kernel filtru de corelație.

Semnalul țintă este arătat în (a). În (b) este rotit cu 180° pentru a anula rotația inerentă în convoluție, permițând să fie realizată corelația. Aplicarea unui filtru detector de margine rezultă în (c), kernelul de filtru utilizat pentru a cest exemplu.

Figura 24-13 ilustrează detaliile despre convoluția FFT. În acest exemplu, vom face convoluția imaginii (a) cu imaginea (b) pentru a produce imaginea (c). Faptul că aceste imagini au fost alese și preprocesate pentru a pune în aplicare corelația este irelevant; aceasta este o diagramă de flux a convoluției. Primul pas este acela de a umple ambele semnale din convoluție cu suficiente zerouri pentru a le face o putere a lui doi în dimensiune și suficient de mare pentru a ține imaginea finală. Astfel, atunci când imaginile de 100×100 și 29×29 pixeli sunt în convoluție, imaginea rezultată va fi de 128×128 pixeli. Prin urmare, trebuie adăugate suficiente zerouri la (a) și (b) pentru a le face pe fiecare cu dimensiune de 128×128 pixeli. Dacă acest lucru nu se face, are loc convoluția circulară și imaginea finală va fi distorsionată. Dacă întâmpinați dificultăți în înțelegerea acestor concepte, mergeți înapoi și revizuiți Capitolul 18, unde este discutat în detaliu cazul unidimensional.

Figura 24-13 Diagrama flux a convoluției imaginii FFT.

Imaginile din (a) și (b) sunt transformate în domeniul frecvență prin utilizarea FFT. Aceste două spectre de frecvență sunt multiplicate și FFT Inversă este utilizată pentru a muta înapoi în domeniul spațial. În acest exemplu, imaginile originale au fost alese și procesate pentru a implementa corelația prin acțiunea convoluției.

Algoritmul FFT este folosit pentru a transforma (a) și (b) în domeniul frecvență. Aceasta are ca rezultat patru matrice de 128×128, părțile reală și imaginară ale celor două imagini fiind în convoluție. Înmulțirea părților reală și imaginară ale lui (a) cu părțile reală și imaginară ale lui (b), generează părțile reală și imaginară ale lui (c). (Dacă trebuie să vi se reamintească cum se face acest lucru, a se vedea Ec. 9-1).Aplicarea FFT inverse finalizează algoritmul prin producerea imaginii finale în convoluție.

Valoarea fiecărui pixel într-o imagine de corelație este o măsură a cât de bine imaginea țintă se potrivește cu imaginea căutată în acel moment. În acest exemplu particular, imaginea de corelație din (c) este compusă din zgomot plus un singur vârf luminos, indicând o bună potrivire cu semnalul țintă. Pur și simplu localizarea celui mai strălucitor pixel în această imagine ar specifica coordonatele detectate ale feței. Dacă nu am fi utilizat modificarea detectării muchiilor pe semnalul țintă, vârful ar fi prezent, dar mult mai puțin distinct.

În timp ce corelația este un instrument puternic în procesarea imaginilor, ea suferă de o limitare semnificativă: imaginea țintă trebuie să fie exact de aceeași dimensiune și orientare rotativă ca suprafața corespunzătoare în imaginea căutată. Zgomotul și alte variații ale amplitudinii fiecărui pixel sunt relativ neimportante, dar o potrivire spațială exactă este critică. De exemplu, acest lucru face ca metoda să fie aproape inutilă pentru găsirea tancurilor inamice în fotografii militare de recunoaștere, tumori în imagini medicale și pistoale în scanarea bagajelor aeroportuare. O abordare este de a corela imaginea de mai multe ori cu o varietate de forme și rotații ale imaginii țintă. Acest lucru funcționează în principiu, dar timpul de execuție vă va face să vă pierdeți interesul în grabă.

Secțiunea următoare: O privire mai aprofundată la convoluția imaginilor