Deblur Automat al Imaginilor

Cuprins

1. Introducere 1

1.1. Blurring 1

1.2. Cauzele care provoacă blurring 1

1.3. Utilitatea deblurring-ului 2

1.4. Deblurring 2

1.5. Rolul transformatei Fourier în procesarea imaginilor 4

2. Abordări precedente 6

2.1. Funcții Matlab 7

2.2. Fergus et al. – Prima abordare 10

2.3. Estimarea kernelului utilizând neregularitățile din spectru de putere 11

2.4. Deconvoluție folosind raportul normelor 13

2.5. Deblurringul unei imagini folosind filtre direcționale 15

2.6. Deblurring de calitate folosind o singură imaginie 16

3. Metode de îmbunătățire ale rezultatelor după deblurring 18

3.1. Criterii folosite pentru îmbunătațirea imaginii după deblurring 18

3.2. Analiza datelor 19

3.3. Rezultate analiză 19

3.4. Alegerea celei mai bune imagini 21

3.5. Imbunătățire amplitudine 21

4. Implementare 24

4.1. Detaliere implementare utilizând Matlab 24

4.2. Paralelizare 25

4.3. Interfața grafică 25

4.3.1. Descriere interfață grafică 26

4.3.2. Descriere calitate și viteză 26

5. Testare 28

5.1. Exemplu de faze si amplitudini 28

5.2. Paralelizare 30

6. Concluzii și îmbunătățiri viitoare 32

Într-o imagine blurată sunt greu de observat detaliile, iar de cele mai multe ori acestea sunt foarte importante. Deblurring pentru o imagine reprezintă procesul prin care o fotografie neclară (blurată) ajunge sa fie clară.

În momentul actual nu există o modalitate care să facă deblurring, pentru orice fel de imagine, am încercat să îmbunătățesc rezultatele algoritmililor de până acum, astfel încât să obțin o imagine mai clară, în urma deblurringului unei singure fotografii. În continuare voi prezenta modul în care incerc să cresc calitatea imaginilor.

Introducere

Prin deblurring, se dorește obținerea unei imagini cu o vizibilitate cât mai bună, în care se pot vedea cu ușurintă toate componentele unei fotografii, pornind de la o imagine blurată (neclară). Deblurring este operația inversă față de cea de blur în care o imagine clară devine neclară în urma aplicării unui flitru. Există două tipuri de metode pentru deblurring: deblurring pentru imagini cu kernelul cunoscut și pentru kernel necunoscut.

Kernelul unei imagini reprezintă o mască (o matrice de dimensiune mică în compartație cu dimensiunea imaginii), prin care se pot aplica diverse efecte asupra unei fotografii, cum ar fi:

Detectarea conturului obiectelor dintr-o imagine

Blur (încețoșarea fotografiilor)

Imprimări în relief

Accentuări pentru obiectele din imagine

Blurring

Blurring reprezintă procesul prin care o imagine în care obiectele sunt reprezentate perfect ajunge sa fie o imagine încețoșată, în care nu se poate distinge conturul obiectelor. De exemplu o fotografie cu fața unei personae este clară dacă se pot indentifica cu ușurință ochii, nasul, gura, urechile, dacă poza este blurată aceste detalii nu sunt ușor de remarcat.

Uneori se face confuzie între blurring și zooming. Zooming este un caz particular de blurring, în care se adugă pixeli pentru a aproxima unele valori, chiar dacă în cele mai multe cazuri imaginea normală și cea blurată au aceelași număr de pixeli, zomming-ul este un tip de blurring.

Tipuri de filtre cu care se poate face blurring:

Filtru medie

Filtru medie ponderată

Filtru Gaussian

Filtru medie are următoarele proprietăți: trebuie sa fie de dimensiune impară, suma elementelor să fie 1, iar toate elementele să aibă aceeași valoare. Exemplu cel mai simplu pentru un filtru medie este o matrice de 3×3 în care toate elementele au valoare 1/9. Cu cât dimensiunea este mai mare, cu atât imaginea este mai blurată, dar și timpul de procesare este mai mare.

Filtru medie ponderată este asemănator cu flitru medie, doar că elementul din centru are cea mai mare valoare, iar celelalte elemente au aceeași valoare. Trebuie să fie de dimensiune impară și să aibă suma elementelor 1.

Filtru Gaussian folosește o funcție gaussiană pentru a blura imaginea. Exemplu de funcție gaussiană:

Cauzele care provoacă blurring

De cele mai multe ori imaginile blurate apar din cauza:

Mișcării camerei foto în timp ce este facută poza

Obiectele din imagine se mișcă prea repede

Focus incorect

Calitatea lentilelor

Lipsa unui trepied

Zoom in prea mare

Unghi larg al obiectivului camerei foto

Timp lung de expunere

Tulburențe atmosferice

Refocalizare

Utilitatea deblurring-ului

Din cauza efectelor din subcapitolul 1.2 imaginile ajung să fie blurate. Există situații în care ne dorim să avem imaginii cât mai clare, cum ar fi:

Documente istorice (al căror scris nu se poate descifra)

Numărul unei masini (poate ajuta poliția pentru a prinde un criminal)

Medicină (ecografii, tomografii)

Transmiterea imaginilor prin zone nesigure (imaginile se pot blura de către sursă și destinatoarul poate face deblurring pentru a vedea imaginea inițială)

Imagine care surprind peisaje din natură (se poate promova turismul mai bine)

Amintiri cu familia și prietenii

Imagini cu sportivi in glorie (linia de sosirea a unui concurs de ciclism)

Imagini în care sursa este în mișcare (fotografii din mașină, tren, avion)

Deblurring

Deblurring este modalitatea prin care o imagine neclară (care se vede în ceață) ajunge în urma procesării sa devină clară. Deblurring-ul este un process fundamental pentru a face o imagine clară și folositoare. Acest proces se aplică imaginilor blurate. O imagine digitală este blurată de obicei folosind convoluția cu un kernel și adăugând zgomot pentru fiecare pixel în parte.

B – imaginea blurată

I – imaginea clară

K – kernelul cu care a fost blurată imaginea

N – zgomotul care a apărut pentru fiecare pixel în parte

X – (x,y) fiecare pixel din imagine

Din (1) rezultă blurring-ul pentru o imagine. Pentru fiecare pixel din imagine are loc o înmultire cu kernelul, la care se adaugă și zgomot (diferit pentru fiecare pixel în parte). Deblurring este operația inversă blurring-ului, deci trebuie rezolvat un sistem foarte mare de ecuații (numărul de pixeli din imagine) și cu un număr mai mare de necunoscute față de numărul de ecuații (fiecare pixel este înmulțit cu kernelul, la care se aduga zgomotul). Sumarizand trebuie rezolvată ecuația (2).

B – imaginea finală

I – imaginea blurată

K – kernelul cu care a fost blurată imaginea

N – zgomotul care a apărut pentru fiecare pixel în parte

X – (x,y) fiecare pixel din imagine

Pentru imaginiile în care nu se cunoaște cum a fost blurtă fotografia trebuie parcurse două etape: estimarea kernelului cu care a fost blurată imaginea, apoi deconvoluția pe baza nucleului estimat. Pentru a afla sau estima cu ce kernel a fost blurtă o imagine se utilizează domeniul frecvență, în care se ajunge cu ajutorul transformatei Fourier.

Domeniul frecvență este folositor, pentru că se pot observa cu ușurință anumite modele și direcția în care se mișcă obiectele în imagine. În acest domeniu se poate procesa imaginea pentru a descoperi modele care apar în imagine astfel încât să se poată reconstrui o imagine clară.

Etapele prin care trece o imagine în procesul de deblurring:

În cadrul lucrării de licența am tratat cazul în care nu se cunoaște kernelul cu care a fost blurată imaginea. Această metodă are nevoie de doi pași: primul pas este estimarea kernelului cu care a fost blurată poza, apoi cel de-al doilea este deconvoluția pe baza kernelului estimat.

Deblurring-ul reprezintă o metoda de procesare a imaginilor, astfel cel mai potrivit mediu de dezvolatare este Matlab/Octave, deoarece oferă un mod simplu de lucru cu funcții și operații matematice, mai ales cu vectori și matrici (imagini), multe funcții matematice gata implementate și multe alte facilități, printre care și o interfață grafică simplu de creat.

Există câteva metode pentru deblurring implementate chiar în Matlab: deconvblind, deconvlucy, deconvreg, deconvwnr. Aceste metode fac estimarea kernelului și deconvoluția folosind filtre sau metode simple, din această cauză rezultatele nu sunt foarte bune (mai ales pentru imagini blurate mult).

De-a lungul anilor cât mai multe persoane au încercat să facă un algoritm pentru deblurring automat, însă până în ziua de astăzi nu există un algoritm care să poată face deblurring automat bun pentru orice fotografie. Prima încercare de algoritm pentru deblurring automat îi aparține lui Rob Fergus în anul 2006, atunci cand a publicat lucrarea [3]. Cu timpul au început să apară diverse abordări care încearcă să facă deblurring automat.

Scopul acestei lucrări îl reprezintă modul în care se poate ajunge ca, o imagine blurată (indiferent de dimensiune sau modul în care a fost blurată) să fie transformată într-o imagine clară. Punctul de plecare îl reprezintă 4 algoritmi pentru deblurring [6], [12], [15], [16]. Pe baza rezultatelor acestor algoritmi încerc să obțin o imagine mai bună, alegând din fiecare poză parțile bune. Toate îmbunătățirile le fac cu ajutorul transformatei Fourier.

Rolul transformatei Fourier în procesarea imaginilor

Una dintre cele mai bune și folosite metode pentru procesarea imaginilor este transformata Fourier, mai exact FFT (Fast Fourier Transform). Această transformare convertește imaginea din domeniul real în domeniul complex, unde se împarte în doua comonente amplitudine și fază.

În domeniul frecvență fiecare pixel al imaginii reprezintă frecvența din domeniul real.

Utilizările acestei transformate acoperă o arie mare de aplicații:

Analiza de imagini

Filtre de imagini

Reconstrucție de imagini

Compresie de imagini

În lucrearea mea am folosit transformata fourier pentru filtre de imagini, analiză de imagini (stabilirea unor criterii), reconstrucția unei imaginii blurate.

Transformata Fourier pentru o imagine de dimensiune NxN

f(a,b) – imaginea în domeniul spațial

F(k,l) – imaginea în domeniul Fourier

Inversa transformatei Fourier pentru o imagine de dimensiune NxN

f(a,b) – imaginea în domeniul spațial

F(k,l) – imaginea în domeniul Fourier

Etapele reconstrucției imaginii folosind transformarea Fourier în general:

Imagine în domeniul spațial

Pre-procesare

Transformare Forier

Prelucrare imagine în amplitudine și fază

Inversa transformatei Fourier

Post-procesare

Imagine reconstruită în domeniul spațial

Exemplu: imagini preluate din [17]

Imagine inițială Imagine în Fourier

Editare imagine în Fourier Imagine finală

În exemplu de mai sus este prezentat modul în care se pot elimina zgomotele foarte ușor dintr-o imagine folosind transformata Fourier. Se observă că există un model în domeniu spatial, care în frecvență este reprezentat de către cele 4 puncte albe.

Abordări precedente

Cea mai simplă metodă de abordare, dar și cu șanse ceva mai mici de reușită este abordarea propusă de Matlab prin 4 funcții.

Abordări pentru care se cunoaște kernelul cu care s-a blurat imaginea inițială:

Algoritmul iterativ Van Cittert

Algoritmul iterativ Landweber

Alogritmul intertiv Richardson-Lucy

Filtru Wiener

Estimare Maximum-a-Posteriori (MAP)

Abordari pentru care nu se cunoaște kernelul cu care s-a blurat imaginea inițială:

Detectarea zgomotului utilizând filtru median

Detectarea dungilor de lumină (mai ales pentru imagini nocturne sau cu luminozitate scăzută)

Interfață Bayesian

Metode bazate pe variații

Metode bazate pe regiuni

Metode bazate pe date statistice

Metode bazate pe direcția de mișcare

Transformarea Radon

Una dintre cele mai simple si rapide abordări este algoritmul Van Cittert, pentru că folosește puține variabile si operații, dar principalul dezavantaj îl constituie faptul că în loc să scadă zgomotul din imagine de multe ori îl crește.

– estimare la pasul n+1 pornind de la imaginea de la pasul n

B – imaginea blurată

K – kernelul cu care a fost blurată imaginea

Estimarea inițială este de obicei chiar imagiena blurată.

O îmbuntățire a algoritmului Van Cittert este algoritmul Landweber care se folosește în plus și de transpusa kernelului, dar și de o constantă pentru un control mai bun asupra zgomotului.

– estimare la pasul n+1 pornind de la imaginea de la pasul n

B – imaginea blurată

K – kernelul cu care a fost blurată imaginea

– transpunsa kernelului

– o constantă

Unul dintre cei mai populari algoritmi (pentru cazul în care se cunoaște kernelul cu care a fost blurată imaginea) este Richardson-Lucy pentru că poate să reducă zgomotele și rulează mai repede față de majoritatea algoritmilor.

– estimare la pasul n+1 pornind de la imaginea de la pasul n

B – imaginea blurată

K – kernelul cu care a fost blurată imaginea

– adjuncta kernelului

Metodele bazate pe regiuni, încearcă să gaseasă câte un kernel local pentru fiecare regiune, dar aceste metode necesită mult timp și multă memorie mai ales pentru imagini mari sau foarte mari.

Estimare Maximum-a-Posteriori (MAP)

Uneori există date (date statistice sau dovezi empirice) despre un process fizic anterior și vrem să estimăm un alt proces. Pentru a face o astfel de estimare ne putem folosi de inferența Bayesian:

– posterior(termenul rezultat in urma predicției)

– termenul probabil

– probabilitatea termenul anterior

P(x) – probablilitatea in punctual x

Din (7) rezulta estimarea MAP.

Funcții Matlab

Pentru următoarele funcții am pornit de la următorul scenariu:

Imagine originală preluată din [12] Imagine blurată

deconvwnr

Face deblur utilizând filtru Wiener.

Funcția are următoarea sintaxă:

J – imaginea rezultată în urma aplicării algoritmului de deblur folosind filtru Wiener

I – imaginea blurată

PSF – kernelul cu care a fost blurată imaginea I

NSR – zgomotul care a apărut pentru fiecare pixel în parte

Imagine după deblur

deconvreg

Face deblur utilizând filtru de regularizare.

Funcția are următoarea sintaxă:

J – imaginea rezultată în urma aplicării algoritmului de deblur folosind filtru de regularizare

I – imaginea blurată

PSF – kernelul cu care a fost blurată imaginea I

NOISEPOWER – zgomotul care a apărut pentru fiecare pixel în parte

Imagine după deblur

deconvlucy

Face deblur utilizând metoda Lucy-Richardson.

Funcția are următoarea sintaxă:

J – imaginea rezultată în urma aplicării algoritmului de deblur folosind algoritmul Lucy-Richardson.

I – imaginea blurată

PSF – kernelul cu care a fost blurată imaginea I

NUMIT – numărul de iterații

Imagine după deblur(40 de iterații)

deconvblind

Singura metodă din matlab care face deblur pentru imagini cu kernel necunoscut.

Funcția are urmatoare sintaxă:

J – imaginea rezultată în urma aplicării algoritmului de deblur

PSF – estimarea kernelului cu care a fost blurată imaginea I

I – imaginea blurată

INITPSF – estimare inițială a kernelului

NUMIT – numărul de iterații

Imagine după deblur (INITPSF=matricea identitate, 40 de iterații)

Fergus et al. – Prima abordare

Prima încercare de a face deblurring pornind de la o imagine blurată îi aparține lui Rob Fergus, care împreuna cu Barun Singh, Aaron Hertzmann, Sam T. Roweis  și William T. Freeman a publicat articolul [3], în anul 2006.

Prin acest alogoritm se încearcă creșterea calității imaginilor care surprind momente din natură, cauzate de lipsa unui trepied, atunci când a fost făcută fotografia sau din cauza timpului lung de expunere sau a unor fenomene atmosferice.

Premisele de la care pornește această abordare sunt:

Imaginea blurată s-a format în urma unei singure convoluții

Orice rotire a aparatului foto a fost mică, atunci când a fost făcută poza

Nu se deplasează nici o parte a scenei relativ la altă parte a scenei

Aceasta abordare are 2 pași mari: estimarea kernelului cu care imaginea a fost blurată, apoi deconvoluția.

În afară de imaginea blurată, utilizatorul trebuie să introducă și zona în care imaginea este blurată, dimensiunea kernelului cu care a fost blurată imaginea (o estimare) si direcția kernelului (orizontală sau verticală).

Accentul a fost pus pe partea de estimare a kernelului. Pornind de la un nucleu de 3×3 se face o estimare în mai multe faze, până la dimesiunea introdusă de utilizator. În fiecare fază se face o aproximare în funcție de gradient pe baza unei inferențe Bayesian, folosind estimarea

Maximum-a-Posteriori (MAP).

Etapele prin care are loc reconstrucția imaginii:

Conversia imaginii în grayscale

Corectare gamma

Selectarea zonei în care se face estimarea kernelului

Inițializarea kernelului

Estimarea kernelului în mai multe faze, până se ajunge la dimensiunea introdusă de utilizator (la fiecare fază se folosește estimarea MAP)

Kernel final

Deconvoluție utilizând metoda Richardson-Lucy

Imaginea rezultată

Exemplu: imagine preluată din [3], utilizând algoritmul [3]:

Imagine blurată (în chenar este zona selectată)

Imagine reconstruită (în stânga este kernelul rezultat)

Se poate observa că zona selectată este reconstruită destul de bine, dar mâna stangă a copilului din imagine este în continuare blurată.

Avantajele acestei abordari sunt:

Se face o estimare a kernelului mai bună, față de funcția deconvblind din matlab

Corecție gamma

Utilizatorul poate alege zona în care se face estimarea kernelului

Dezavantaje:

Pentru alegerea unei zone mari sau pentru imagini mai mari ca 800×600 pixeli, algoritmul durează destul de mult (peste 10-20 minute).

In reconstrucție se pierde saturația.

Estimarea kernelului utilizând neregularitățile din spectru de putere

O abordare cu rezultate foarte bune și cu un timp de rulare bun este lucrarea [15], realizată de către Amit Goldstein și Raanan Fattal.

Această abordare se bazează pe neregularitățile care apar în spectrul de putere din punct de vedere statistic. Lucrează foarte bine pe imaginile în care zonele blurate apar în părțile importante ale imagini și de dimensiuni mari (cel puțin 512×512 pixeli). Reconstruirea kernelului se bazează pe un algoritm care rulează în mai multe faze (dar nu pe o estimare de tipul MAP), cu o convergență imbunatățită, dar față de multe alte abordări precedente, această abordare nu se bazeaza pe reconstrucția imaginii în mai multe faze, astfel are un timp de rulare mai bun, față de alte metode.

Premisele de la care pornește această metodă de estimare a kernelului sunt:

Kernelul cu care a fost blurată imaginea este proporțional cu mișcarea camerei în timpul de expunere.

Cât timp mișcarea camerei în timpul expuneri este finită, kernelul ar trebui sa fie compact

Blur-ul nu afectează toată lumina carea ajunge la cameră, toată imaginea.

Pe scurt estimarea kernelului se bazeaza pe comutarea din domeniu Fourier în domeniu real și invers până este îndeplinită condiția de convergență, începând de la o estimare inițială. Pentru estimarea inițială se folosește ca filtru d = [3, − 32, 168, − 672, 0, 672, − 168, 32, − 3]/840, acest filtru se aplică pentru a afla proiecția 1D a kernelului. Algoritmul obține un set de statistici după ce este scazută luminozitatea în spectrul de putere.

Avantaje:

Rulare mai rapida față de alți algoritmi (mai ales pe imagini mari)

Abordare nouă, care funcționează pe imagini unde estiamrea MAP nu dă rezultate prea bune

Dezavantaje:

Nu poate fi rulat pe imagini mai mici de 512×512 pixeli sau rezultatele sunt foarte proaste

Exemplu: imagine preluată din [15], utilizând algoritmul [15]

Imagine blurată

Imagine după deblur

Deconvoluție folosind raportul normelor

În 2012 D. Krishnan, T. Tay, R. Fergus, descoperă o nouă metodă prin care se poate face deblur [12].

Această abordare are la bază raportul dintre norma l1 și norma l2, în frecvență pentru a estima kernelul cu care a fost blurată imaginea.

Norma l1

A – Matricea corespunzatoare imaginii în frecvență

i – fiecare pixel (element al matricii A) din imagine

Se mai numește si normă Manhattan.

Norma l2

A – Matrice corespunzatoare imaginii în frecvență

i – fiecare pixel (element al matricii A) din imagine

Se mai numește și normă Euclidiană.

Pentru reconstrucția imaginii trebuie parcurse urmatoarele etape:

Trecerea imaginii în domeniul frecvență

Estimarea kernelului pornind de la imaginea rezultată la pasul anterior

Imbunătățește imaginea în frecvență la fiecare pas în funcție de raportul dintre l1/l2

Imbunătățește estimarea kernelului la fiecare pas

Deconvoluție utilizând metoda Richardson-Lucy

Avantaje:

Timp mai scurt de rulare față de MAP

Funcționează pe orice dimensiune de imagini (de la mari la mici)

Dezavantaj:

Timp mai mare de rularea față de algoritmului lui Amit Goldstein și Raanan Fattal

Exemplu: imagine preluată din [15], utilizând algoritmul [15]

Imagine blurată

Imagine după deblur

Deblurringul unei imagini folosind filtre direcționale

Un rol important în procesarea imaginilor îl are transformarea Radon. Chiar dacă se folosește în special pentru tomografii, în 2013 L. Zhong, S. Cho, D. Metaxas, S. Paris și J. Wang propun o noua metoda pentru deblurring folosind transformata Radon [16].

Aceasta abordare are la baza câteva filtere (gauss sau bilateral), dar cel mai important este că folosește transformarea Radon și inversa transformatei Radon.

Transformarea Radon

Inversa transformatei Radon

Exemplu

Imagine normala Imagine dupa transformarea Radon

`

Etapele pe care le parcurge această abordare:

La început sunt aplicate filtru Gaussian sau Bilateral pentru a elimina o parte din zgomote.

Se aplică transformarea Radon pentru estiamarea kernelului în mai multe faze.

Deconvoluția se face folosind inversa transformatei Radon.

Avantaje:

Reușește să obțină imagini în care se pot vedea elemente pentru imaginile blurate foarte tare.

Dejavantaje:

Nu oferă claritate.

Timp mare de rulare, apropiat de algoritmi care folosesc estimarea MAP.

Exemplu: imagine preluată din [16], utilizând algoritmul [16]

Imagine blurata Imagine dupa deblur

Deblurring de calitate folosind o singură imaginie

Această abordarea se bazeaza pe un model probabilistic. Folosește o metoda de tip MAP optimizată, iar atât estimarea kernelului cât și a imaginii se face în mai multe faze. Se pune accentul pe claritatea imaginilor.

Avantaje:

Claritatea imaginilor dupa deconvoluție.

Dezavantaje:

Timp mare de rulare.

Nu funcționează pe imagini mari

Exemplu: imagine preluată din [16], utilizând algoritmul [6]

Imagine blurată

Imagine după deblur

Metode de îmbunătățire ale rezultatelor după deblurring

Cateva metode care se aplică după deconvoluție (după ce se termină efectic deblurring-ul), cu rol de post-procesare sunt:

Eliminarea zgomotelor

Eliminarea undelor circulare

Corectarea saturației

Eliminarea zonelor în care intensitatea luminoasă este prea mare

Pentru a observa ce nu este bine pentru metodele prezentate în capitolul precedent am plecat de la urmatorul scenariu:

Am creeat un set de date (33 de imagini blurate)

Am aplicat mai multe criterii pe datele de intrare

Am aplicat criteriile în mai multe domenii: real, fourier, fourier de fourier

Metoda pe care am ales-o pentru a observa care din rezultate este mai bun se compune din mai multe etape:

Deblur folosind abordarile [3], [12], [15], [16].

Aplicare criterii pe cele 4 imaginile rezultate

Analiza rezultatelor

Concluzii pentru fiecare criteriu în parte

Criterii folosite pentru îmbunătațirea imaginii după deblurring

Criteriile folosite pentru a analiza sunt [22]:

Media pixelilor din imagine (în domeniul spațial, Fourier, Fourier de Fourier)

Deviația minimă standard (în domeniul spațial, Fourier, Fourier de Fourier)

Coeficientul de corelare între imagine și deviația standard locală (în domeniul spațial, Fourier, Fourier de Fourier)

Gradient (în domeniul spațial)

Formula Coeficientului de corelare

A,B reprezintă cele 2 imagini

– media pixelilor din imaginea A

– media pixelilor din imaginea B

Media pixelilor reprezinta cel mai simplu criteriu care se poate aplica pentru o imagine și este utilizat pentru a reduce zgomotele dint-o fotografie și variații locale.

Deviația minimă standard este un criteriu puțin mai mai complex ca media pixelilor și este folosit pentru a descoperi anumite modele din imagine.

Gradientul unei imaginii reprezintă o modalitate prin care se pot observa schimbările în intensitate sau croamtică a imaginii (exemplu forma obiectelor din imagine).

Coeficientul de corelare reprezintă o metoda prin care se observa gradul de asemanare intre 2 imaginii, o astfel de masură este relația dintre o imagine după deblur și deviația standard locală a acestei imaginii (o imaginie puțin blurată).

Avantaje:

Compară două imagini, nu doar una

Este invatiant pentru o transformare liniară pentru A sau B în (16)

Dezavantaje:

Timp mare de procesare

În unele cazuri e posibil sa se ajungă la împărțiri la 0

Analiza datelor

În momentul în care am pornit să fac o analiza pe baza statisticilor, am plecat de la urmatoarele premise:

Un set de imagini (33 imagini blurate,atât natural cât și artificial)

Patru metode folosite pentru deblurring (prezentate în capitolul 2)

Patru criterii folosite pentru analiza în mai multe domenii (subcapitolul 3.1).

Pentru o analiza cât mai precisă am folosit 3 domenii în care am procesat toate criteriile: spațial, frecvență, Fourier de Fourier.

Am rulat cele 4 criterii în 3 domenii (spațial, Fourier, Fourier de Fourier), pentru rezultatele celor 4 algoritmilor ([3], [12], [15], [16]), pentru cele 33 de imagini blurate.

În total au fost imagini rezultate pentru a ajunge la conclizii despre fiecare criteriu în parte, dacă este util sau nu, dacă poate să prezică dacă un algoritm e bun sau nu într-o anumită situație.

Rezultate analiză

Rezultatele testelor sunt prezentate în tabelul de mai jos (pentru fiecare criteriu am considerat minimul sau maximul dintre valori un subcriteriu).

Tabel 1

Analiza datelor de test

În urma rezultatelor din tabelul de mai sus se poate observa că exista cateva criterii după care se poate prezice dacă o imagine este bună după deblur sau nu.

Criterii care pot prezice dacă o imagine este bună:

Minim aplicat pe media pixelilor în fourier (în amplitudine)

Minim aplicat pe deviația minimă standard în fourier (în amplitudine)

Minim aplicat pe deviația minimă standard în fourier de fourier (în amplitudine)

Maxim aplicat pe coeficientul de corelare în fourier(în amplitudine)

Criterii care pot prezice când o imagine nu este buna:

Maxim aplicat pe media pixelilor în fourier (în amplitudine)

Maxim aplicat pe coeficientul de corelare în domeniul spațial

Maxim aplicat pe coeficientul de corelare în fourier de fourier(în amplitudine)

Aceste criterii le-am folosit în abordarea mea pentru reconstrucția imaginilor blurate. Mai multe detalii în capitolele următoare.

Alegerea celei mai bune imagini

Pentru a obține o imagine cât mai bună este nevoie de o fază care să se lege cât mai mult între pixeli. Astfel cu ajutorul criteriilor obținute în capitolul 3 am votat care fază este cea mai bună.

Fiecare algoritm primește o notă calculată astfel (pentru fiecare algoritm valorile sunt sortate crescător):

pondere_criteriu = procent al predicțiilor bune – procent al predicțiilor proaste

În final algoritmul va alege faza algoritmului cu nota cea mai mare (în caz de egalitate ordinea este urmatoarea: “Blur-kernel estimation from spectral irregularities” [15], ”Blind deconvolution using a normalized sparsity measure” [12], ”Handling Noise in Single Image Deblurring using Directional Filters” [16], “High-quality motion deblurring from a single image” [3]).

Imbunătățire amplitudine

Fiecare algoritm are pe langă avantaje, bineînțeles și anumite dezavantaje. Unul din lucrurile unde se poate aduce un plus pentru a avea în final o imagine cât mai bună este amplitudinea (la care se ajunge după ce imaginea este adusă în domeniul frecvență).

Am încercat tot felul de criterii pentru a îmbunătăți amplitudinea (pornind de la cele 4 imagini rezultate):

Amplitudinea minimă

Ampitudinea medie

Amplitudinea medie între a doua și a treia valoare

Mai multe ponderi (exemplu 0.4, 0.3, 0.2, 0.1pe amplitudinii sortate crescator)

Distanța față de un anumit pixel să fie mai mică decat o valoare X

În final (în urma testelor pentru toate aceste criterii) am observant că există 4 criterii care dau rezultatele cele mai bune: amplitudinea minima, amplitudinea media între pixel 2 și 3, o medie ponderată (0.4, 0.3, 0.2, 0.1), o medie ponderată în funcție de distanta față de pixelul 2 (toate criteriile au cele 4 amplitudini sortate crescator).

Pentru a alege cel mai bun criteriu folosesc algoritmul de la 4.1

Exemplu:

Imagine initială (preluată din [12]) Imagine [15]

Imagine [16] Imagine [12]

Imagine [6] Imagine finală

Implementare

După cum am prezentat în capitolul 2 există numeroase abordări și metode pentru a face deblurring, pentru imaginile al căror kernel nu este cunoscut, dar fiecare dintre acestea are dezavantajele sale. În continuare voi prezenta o implementare care poate să facă deblurring mai bine decât toate metodele de mai sus, în cel mai rău caz reușind doar să obțină un rezultat similar cu cea mai bună din ultimele 4 abordari prezentate în capitolul 2.

Pornind de la 4 din abordarile prezentate in capitolul 2 ([3], [12] ,[15], [16]) și de la criteriile din capitolul 3 care pot decide într-o măsură destul de bună care este cea mai bună imagine din cele 4,

am combinat rezultatele astfel încât să obțin o imagine mai clară. Pe scurt sunt 2 etape mari: prima votarea celei mai bune faze, iar a doua combinare amplitudinilor pentru a obține o amplitudine mai bună.

Etapele pe care le parcurg pentru a ajunge la imaginea finală sunt:

Citire imagine blurată

Deburring folosind cei 4 algoritmi

Aplic transformata Fourier pentru cele 4 imagini

Pre-procesare (trec din domeniul frecvență în amplitudine și fază)

Votez cea mai bună fază (subcapitolul 3.4)

Pentru fiecare pixel în parte aplic 4 filtre pentru a obține o nouă amplitudine (subcapitolul 3.4)

Obțin 4 imagini în amplitudine și fază

Post-procesare (trec în domeniul frecvență din amplitudine și fază)

Aplic Inversa transformatei Fourier

Votez cea mai bună imagine dintre cele rezultate (la fel ca la pasul 5)

Imagine finală

Detaliere implementare utilizând Matlab

Pentru implementarea abordarii descrise mai sus am folosit ca mediu de dezvoltare Matlab R2012a, versiunea pe 64 de biți.

Implementare etape în Matlab:

Citire imagine folosind funcția imread și conversie la double folosind funcția im2double

Pentru deblurring am creeat 4 funcții care au antetul deblur_x unde x poate sa fie: fattal [15], fergus [12], dir [16], hq [6], care seteaza parametrii în funcție de algoritm și care salveza rezultatul în fișere cu numele deblur_x_nume_imagine_inițială, unde x este fattal [15], fergus [12], dir [16], hq [6].

În cazul în care dimensiunea imaginii este mare am creeat și funcții de forma deblur_x_with_resize, care fac resize înainte să ruleze algoritmul, unde x este fattal [15], dir [16], hq [6]. Pentru fergus [12], nu există o astfel de funcție pentru că această abordare face resize imaginii în etapa de pre-procesare.

Transform cele 4 imagini din domeniu real în frecvență (aplic transformata Fourier).

Pentru fiecare imagine în domeniul frecvență rezultă două componente: amplitudine și fază. Pentru fiecare componetă a imaginii în frecvență , amplitudinea este , iar faza este .

Rulez funcția de votare a fazei, care primește ca input cele 4 imagini rezultate după deblur și returneză numele algoritmului cu nota cea mai mare conform descrierii de la 3.5 .

Combin amplitudiniile imaginilor rezultate după rularea celor 4 algoritmi care fac deblurring, utilizând cele 4 criterii de la 3.5, în acest punct există 4 matrici reprezentând 4 amplitudinii diferite și o matrice cu faza votată la etapa anterioară.

Transform din nou în domeniul frecvență din amplitudine (A) și fază (). Fiecare element al matrcii în domeniul frecvență este format astfel:

Aplic inversa transformatei Fourier pe cele 4 imagini în frecvență.

Votez cea mai bună imagine folosind funcția de votare fază.

Obțin o imagine finală pe care o salvez cu numele deblur_nume_imagine_inițială.

Toate aceste etape sunt incluse intr-o funcție care primește ca parametru calea către imaginiea blurată. Se poate creea foarte ușor un script, în cazul în care se dorește să se facă deblur pentru mai multe fotografii, nu doar pentru una singură.

Paralelizare

În zilele noastre majoritatea aplicațiilor rulează pe procesoare cu mai multe core-uri. Astfel m-am gândit că ar fi bine să paralelizez și această aplicație. Pentru că am folosit ca mediu de dezvoltare Matlab, cel mai potrivit mod de a face acest lucru a fost să utilizez chiar metodele din Matlab.

Utilitarul pe care îl pune la dispozitie Matlab este matlabpool.

Comenzi utilizate pentru paralelizare:

matlabpool open [numar de core-uri] – deschide o sesiune în care se poate rula in paralel utilizând maxim numarul de core-uri care au fost date ca paramteru

matlabpool size – returnează numarul de core-uri cu care a fost deschisă sesiunea sau 0, în cazul în care nu este deschisă o sesiune

matlabpool close – închide o sesiune în execuție și toate insanțele care rulează în paralel

Pentru a paraleliza o sectiune for se utilizează comanda parfor.

În lucrarea mea am folosit proprietățile de mai sus pentru a paraleliza algoritmul de votare al celei mai bune faze și pentru combinarea amplitudinii (am paralelizat după linii). Astfel am reușit să îmbunătațesc timpul de rulare în cazul în care aplicția rulează pe un sistem cu mai multe core-uri.

Interfața grafică

În unele cazuri scripturile și rularea din linia de comanda nu sunt cele mai potrivite metode pentru cineva care nu a dezvoltat o aplicație și vrea doar să o utilizeze, așadar o interfață grafică este utilă într-un astfel de caz, pentru că facilitează utilizatorului un mod mai ușor de a folosi aplicația.

În imaginea de mai jos este prezentată interfața grafică a acestei aplicații în momentul în care este deschisă.

Etapele pe care trebuie să le parcurgă un utilizator pentru a procesa o imagine sunt:

Alegerea fotografiei

Alegerea vitezei și calității

Procesarea imaginii

Salvare(opțional)

Descriere interfață grafică

Butonul “Choose Image” deschide o fereastră, în care utilizatorul poate naviga prin sistemul de fișiere și alege imaginea pe care o dorește pentru procesare. După alegerea facută, în partea stângă a acestui buton este afișată calea absolută către imagine.

Butonul “OK” proceseaza imaginea selectată (care apare în câmpul “Filename”), în funcție de opțiunile pentru viteză și calitate, iar la final afișează mesajul “Deblurring is done” într-o nouă fereastră. În cazul în care nu este selectată nici o imagine sau calea nu este corectă se va afișa un mesaj de eroare.

Butonul “Save” salvează imaginea după deblurring. La apăsare va deschide o nouă fereastră în care utilizatorul poate să își aleagă locul unde vrea să salveze noua imagine și numele pe care dorește să îl pună.

Descriere calitate și viteză

Pentru a oferi utilizatorului mai multe variante în ceea ce privește calitatea și timpul de procesare pentru o imagine aplicația oferă urmatoarele combinații între viteză și calitate:

Testare

Am testat posibilele criterii pentru votare, exemplu Anexa 1, dar și modul în care pot să combin datele din mai mulți algoritmi (amplitudinile), pentru a obține rezultate cât mai bune.

Analiza algoritmului de votare pentru setul de imagini cu care am lucrat.

În graficul de mai sus sunt prezentare predicțiile pentru fiecare imagine al algoritmului de votare a fazei.

Tipuri de predicții (pe axa Oy):

2 – predicție bună (a fost aleasă faza celei mai bune imagini)

1 – predicție medie (a fost aleasă o fază bună, dar nu cea mai bună, însă diferența între ele este foarte mică)

0 –predicție proastă(nu a fost aleasă o fază bună)

Exemplu de faze si amplitudini

Imagine preluată din [15]

Faza după aplicarea algoritmului [15] Faza după aplicarea algoritmului [12]

Faza după aplicarea algoritmului [16] Faza dupa aplicarea algoritmului [6]

Din cele 4 faze nu se pot obține prea multe informatii, dar se poate observa că fazele pentru [15] și [6] par mai bune (au mai puțin zgomot). Algoritmul de votare a ales în acest caz faza algoritmului [15].

Amplitudinea după aplicarea algoritmului [15] Amplitudinea după aplicarea algoritmului [12]

Amplitudinea după aplicarea algoritmului [16] Amplitudinea după aplicarea algoritmului[6]

Amplitudinea dupa votare si combinarea celor 4 amplitudini, folosind media dintre pixelul 2 și 3 la fiecare iterație (pe un vector sortat de ampitudini).

Se poate observa că este o amplitudine medie(mai ales in partea centrala a imaginii).

Paralelizare

În graficul de mai jos am ilustrat timpul de rulare pentru calcularea unei noi amplitudini atât în serial, cât și in paralel (cu două core-uri).

Din grafic se poate observa foarte ușor că în serie timpul de rulare este mai mare față de paralel cu 2 core-uri, dar nu se poate observa foarte ușor scalabilitatea pentru că sunt diferențe asupra timpului de rulare între poze mici (300×300 pixeli) și poze mari (1200×2400), astfel am ilustrat mai jos un grafic pentru scalabilitate.

Utilizând paralelizarea din matlab se poate obține o scalabilitate medie de aproximativ 1,5-1,55 pe majoritatea imaginilor (indiferent de dimensiune). Detalii despre timpii de rulare se găsesc în Anexa 2.

Concluzii și îmbunătățiri viitoare

Am reușit să găsesc o modalitate, astfel încât pentru foarte multe imagini blurate să pot obține o imagine clară, indiferent de dimesiunea ei sau de modul în care a fost blurată imaginea ințială, după ce parcurg două etape importante: votez cea mai bună fază pe imaginile rezultate în urma rularii abordarilor [6], [12], [15], [16], apoi combin amplitudinile astfel încât să elimin elementele care strică imaginea după deblur. Se pot aduce imbunatățiri, cât timp se folosește ca mediu de dezvoltare Matlab, în plus se pot face ușor scripturi care să ruleze un set de poze, nu doar o imagine. Această metodă se bazează pe date statistice.

S-a dovedit că în urma unei analize asupra statisticilor bazate pe criterii precum media pixelilor dintr-o imagine, deviația minimă standard, gradient sau coeficient de corelare între imaginea după deblurring și imaginea corespunzătoare deviației locale standard se pot obține rezultate care să îmbunătățească calitatea imaginilor după deblurring. În plus, transformata fourier și inversa ei și-au dovedit utilitatea încă o dată în procesarea imaginilor, mai ales pentru a aduce imaginea într-o stare cât mai bună pentru procesare.

Interfața grafică oferă utilizatorului mai multe moduri în care poate să ruleze, în funcție de timpul pe care îl dorește să aștepete și de calitatea pe care vrea să o obțină utilizatorul, în cazul în care cineva are un set de poze poate creea un script care să proceseze toate imaginile, dar asta necesită, mai mult timp dacă sunt multe poze (de dimesiuni mari) și dacă se rulează pe un sistem cu un singur core.

Am test, pentru urmatoare configurație hardware: Intel Core i5 2,4 GHz, 8GB RAM, placa grafică NVIDIA GeForce GT 540M, 2GB VRAM, utilizând Matlab R2012a 64 biti și sistem de operare Windows 8.1 64 biți.

În viitor, ar fi util dacă această aplicație poate fi portată pentru platformele mobile. Multe persoane doresc să își editeze pozele blurate imediat după ce acestea sunt făcute. O altă abordare viitoare interesantă ar fi să pot rula codul direct pe GPU. În plus, adăugând unul sau mai mulți alogritmi, eventual metode diferite sau să schimb unul din algoritmi cu unul mai bun, este posibil să obțin rezultate mai bune.

Anexa 1

Media amplitunii în mediul Fourier

Cu verde sunt reprezentate rezultatele bune, cu galben cele medii, iar cu roșu cele proaste.

Anexa 2

Timp de rulare serial versus paralel

bibliograFIE

[1] R. C. Gonzalez & R. E. Woods, "Digital Image Processing" Ediția a II-a, Addison-Wesley , (1992) p.220-280

[2] Biggs, D.S.C. "Acceleration of Iterative Image Restoration Algorithms." Applied Optics. Vol. 36. , (1997), p. 1766–1775.

[3] R. Fergus, B. Singh, A. Hertzmann, S. T. Roweis, W. T. Freeman “Removing Camera Shake from a Single Photograph”, SIGGRAPH (2006)

[4] J. MISKIN , D. J. C. MACKAY, “Ensemble Learning for Blind Image Separation and Deconvolution. In Adv. in Independent Component Analysis”, Ed. Springer-Verlag (2000)

[5] B.BASCLE, A.BLAKE, A. ZISSERMAN, “Motion Deblurring and Superesolution from an Image Sequence”, In (1996), Conferința Europeană în Computer Vision

[6] Q. Shan,J. Jia ,A. Agarwala “High-quality motion deblurring from a single image”, ACM SIGGRAPH papers, New York ACM (2008)

[7] A. Levin, Y. Weiss, F. Durand, W.T. Freeman “Understanding and evaluating blind deconvolution algorithms” Conferința în Computer Vision și recunoașterea modelelor, IEEE (2009) p. 1964–1971

[8] D. Krishnan, R. Fergus “Fast image deconvolution using hyper-laplacian priors”, NIPS. Volumul 22, (2009),p. 1033–1041

[9] Y. Yitzhaky, I. Mor,A. Lantzman, N.S. Kopeika “Direct method for restoration of motion-blurred images” Journal of Opt. Soc. Am. 15 (1998), p. 1512–1519

[10] S. Cho, S. Lee “Fast motion deblurring.”, ACM SIGGRAPH Asia papers, New York, (2009) p. 145–145

[11] N. Joshi, R. Szeliski, și D. J. Kriegman. “Psf estimation using sharp edge prediction”. Conferința în Computer Vision și recunoașterea modelelor, (2008)

[12] D. Krishnan, T. Tay, R. Fergus “Blind deconvolution using a normalized sparsity measure”, Conferința în Computer Vision și recunoașterea modelelor (2011) p. 233–240

[13] O.Whyte, J. Sivic,A. Zisserman, J. Ponce “Non-uniform deblurring for shaken images” Conferința în Computer Vision și recunoașterea modelelor, IEEE (2010) p. 491–498

[14] T.S. Cho, S. Paris, B.K.P. Horn, W.T. Freeman “Blur kernel estimation using the radon transform”, Conferința în Computer Vision și recunoașterea modelelor. (2011) p. 241–248

[15] A. Goldstein, R. Fattal, “Blur-kernel estimation from spectral irregularities”, Conferința Europeană în Computer Vision, (2012).

[16] L. Zhong, S. Cho, D. Metaxas, S. Paris și J. Wang, “Handling Noise in Single Image Deblurring using Directional Filters”, Conferința în Computer Vision și recunoașterea modelelor. (2013)

[17] E. F. Glynn, “Fourier Analysis and Image Processing”, (2007)

[18] N. Joshi, C. L. Zitnicky, R. Szeliskiy, and D. J. Kriegman. Image deblurring and denoising using color priors. Conferința în Computer Vision și recunoașterea modelelor,(2009).

[19] A. Zohair Al-Ameen, S. Ghazali Sulong, J. Gapar “A Comprehensive Study on Fast image Deblurring Techniques”, (2012)

[20] M. Zaharescu, C. A. Boiangiu “Image Deblurring: Challenges and Solutions”, (2013)

[21] R. Wang D. Tao “Recent Progress in Image Deblurring” , (2014)

[22] V. Kumar, P. Gupta, “Importance of Statistical Measures in Digital Image Processing”, (2012)