Extragerea Conturului - ArtMuseum Style
Introducere
ArtMuseum este un sistem dezvoltat pentru prelucrarea unei colectii de imagini color:
Principiile de stau la baza ART Museum sunt:
1. Spatiu prelucrarii contine imaginile de contur ale imaginii initiale.
2. C onturul unei imagini este construit prin extragerea tuturor punctelor proieminente de pe muchii din cadrul imaginii.
3. Utilizatorul formeaza o baza de date desenand o schita a imaginii dorite. "Matchingul" se realizeaza printr-o evaluare a similaritatilor intre schita oferita de utilizator si conturul stocat in baza de date.
Proiectul de fata se va ocupa de extragerea conturului unei imagini. Aceasta extragere de contur va contine doi pasi. Primul in care se va extrage un contur la nivel global, care de altfel are si importanta pentru utilizator si apoi se va putea extrage un contur local dar al carui scop este furnizarea de informatie necesara realizarii unui matching.
Aspecte Tehnice
Conturul unei imagini este extras efectuand doua operatii de detectare de muchii (edge- detection). Astfel se efectueaza o detectare globala, si o detectare locala.
La procesul de detectare globala a muchiilor se calculeaza gradientii intesitatii RGB pentru fiecare puct (i,j) in urmatoarele 4 directii.
(1)
(2)
(3)
(4)
Unde pij este intensitatea RGB in punctu (i,j), si |Iij| este intesitatea puterii definita astfel:
(5)
Magnitudinea gradientului in punctul (I,j) este definita ca:
(6)
In sfarsit, punctele de muchii la nivel global sunt definite pe urmatorul criteriu:
(7)
unde 
si 
reprezinta media si deviatia gradientilor, si sunt calculate cu formula:
(8)
(9)
Dupa ce am obtinut punctele globale ale muchiilor, urmatorul pas este efectuarea unei detectari a muchiilor la nivel local pentru punctele de la nivel global.
Mai intai calculam deviatia medie si cea locala a gradientilor dupa formulele:
(10)
(11)
mij si sij sunt diferite de m si s. In implementarea ART MUSEUM, marimea ferestrei locale este m = n = 3.
Conditia pentru punctele locale este urmatoarea:
(12)
Pe imaginea binara formata din punctele locale de pe muchii, operatiile de subtiere si micsorare sunt aplicate in vederea obtinerii de muchii cu grosime de un singur pixel. Rezultatul final este inregistrat ca un contur al imaginii originale in baza de date.
La implementarea algoritmului de detectare a conturului, propunerile pentru cresterea vitezei de executie ar fi urmatoarele:
- Calcularea gradientilor pentru toata imaginea si retinerea valorilor obtinute intr-o matrice tri-dimensionala M X N X 4
- Retinerea rezultatelor obtinutede la detectarea globala intr-o noua matrice. Astfel in matricea respectiva vor fi marcate doar punctele care indeplinesc conditia (7) si doar pe aceste puncte aplicandu-se formulele de la (10) si (11).
Implementare logica
Dupa cum se vede din prezentarea anterioara din capitolul anterior, algoritmul ArtMuseum este un algoritm destul de strict ce nu lasa loc la multe variatii. Ceea ce permite insa la prima vedere este o imbunatatire a performantelor, deoarece se observa ca avem de-a face cu clacule de dimensiuni foarte mari.
Totusi algoritmului i se pot aplica o suma de imbunatatiri si in ceea ce priveste calitatea rezultatelor. Astfel pentru inceput sa observam niste rezultatele rularii asupra unor imagini.
Imagine Sursa
Rezultat
ImagineSursa
Rezultat
In urma acestor imagini prezentate doua observatii merita retinute. in ce priveste prima imagine se observa pierderea de informatie. Astfel acolo unde culorile aflate in confluente aveau nuante aproximativ asemanatoare nu s-a detectat conturul. Acest fapt fiind critic.
A doua observatie priveste a doua imagine si faptul ca algoritmul nu ofera un contur prea exact in cazul in care exista zgomote in imaginea sursa. De aici o concluzie ar fi ca algoritmul ArtMuseum este ideal pentru forme exacte (fapt explicabil prin scopul principal al algoritmului - matching) dar nu ofera rezultate prea satisfacatoare pentru imagini mai neregulate. Totusi autorii acestui program au considerat ca si aceste imagini ar trebui sa beneficieze de niste rezultate de o calitate cat mai ridicata. Astfel in ce priveste imaginea a doua se observa ca o subtiere a conturului ar mari mult calitatea informatiei. Astfel ca una dintre uneltele anexe ale programului va fi cea de subtiere de contur.
Structuri de date
Acestea fiind zise sa vedem cum s-a implementat algoritmul de extragere de contur. Dupa cum ziceam esential era cresterea vitezei de executie. tehnica ArtMuseum recomanda scalarea imaginii la 64x64 pixeli si aplicarea lagoritmului. Dar pentru ca aceasta insemna pierdere de informatie esentiala am aplicat algoritmul pe imaginea initiala (viteza scazand mult). Totusi am aplicat o limitare a dimensiunii imaginilor. Acesta deoarece am alocat structurile de date in mod static. Alocarea statica fiind mai rapida decat cea dinamica. Prin urmare am facut o medie intre viteza si calitate. Am limitat imaginile la 1000/1000 pixeli si am folosit structuri statice.
Pentru folosirea acestor structuri era necesara redimensionarea stivei. (40M)
La implementarea algoritmului de detectare a conturului, propunerile pentru cresterea vitezei de executie ar fi urmatoarele:
1.Calcularea gradientilor pentru toata imaginea si retinerea valorilor obtinute intr-o matrice tri-dimensionala M X N X 4
2.Retinerea rezultatelor obtinutede la detectarea globala intr-o noua matrice. Astfel in matricea respectiva vor fi marcate doar punctele care indeplinesc conditia (7) si doar pe aceste puncte aplicandu-se formulele de la (10) si (11).
float PowIntensity[1000][1000];
float Gradients[1000][1000][4];
float GradMagnitude[1000][1000];
float GradAverage, GradDeviation;
Iata intr-un pseudocod mult simplificat pasii ce se efectueaza:
function ArtMuseum( in SrcImg, out DestImg)
1. Check image Size. If imageSize bigger than 1000x1000 exit
2. Calculate the Power Intensity
3.Calculate Gradients and store results in Gradients[][] matrix
4.Calculate the Gradients Magnitude and store results in GradientMagnitude[][][ matrix
5. Calculate GradientAverage
6.Calculate the Deviation
7. If if (GradientMagnitude[i][j] >= (GradAverage + GradDeviation)
then P(i,j) belongs to contour)
else P(i,j) is background
end function
Dar sa ne intoarcem asupra problemei ce a aparut la prima imagine. Vorbeam acolo de o pierdere de informatie. Deci in cazul in care variatia intre cele doua culori vecina era mica nu se detecta conturul. O studiere amanuntita amodului in care lucreaza algoritmul ne-a dus la o solutie pentru aceasta problema. Astfel am observat unde se poate stabili sensitivitate entru acest algoritm. Si anume la calculul Deviatiei locale. Iata transormarea formulei (7) in codul imbunatatit.
if (GradMagnitude[i][j] >= (GradAverage + GradDeviation)/m_sensitivity)
lpDst[i*w+j] = 0;
else lpDst[i*w+j] = 255;
Se observa introducerea marimii m_sensitivity cu valori reale intre 0.25 si 1000. Cu cat valoarea va fi mai mare, va creste si sesibilitatea. Acesta modificare poate furniza rezultate mai apropiate de cele dorite.
Vezi capitolul de rezultate pentru a observa eficacitatea imbunatatirilor aduse.
Unelte anexe
Dupa cum ziceam utilizatorului ii sunt puse la dispozitie si o multime de unelte ce pot imbunatatii rezultatele. Dintre acestea amintim: erodarea (in cazul contururilor groase), dilatarea (pentru acoperirea golurilor), eliminarea zgomotelor (necesar in pregatirea imaginilor complexe cu forme neregulate ce contin zgomotele). Trebuie precizat caacest algoritm este foarte sensibil la zgomote, existand sansa de a le reproduce in imaginea destinatie, scazand calitatea imaginii.
Una din aceste unelte este aceea de subtiere a conturului la un pixel. Pentru aceasta se va executa o operatie de eroziune si dupa aceea sa scoate rezultatul din imaginea initiala. Rezultatul va fi o imagine care arata o conturare de un pixel pentru toate obiectele prezente in imagine. Daca sunt executate doua operatii de eroziune inainte ca sa se execute extragerea imaginii obtinute din imaginea initiala , atunci se va obtine un contur de 2 pixeli al obiectelor din imaginea initiala.
Rezultate
|
Original |
Contur - Sensitivitate mica |
Contur - Sensitivitate mare |
|
Original |
Extragere Contur |
|
Extragere Contur + Subtiere
|
|
Original |
|
Contour extraction + Noise Reduction |
Concluzii
In ce priveste concluziile asupra acestui program ele ar putea fi sintetizate in cateva fraze.
Algoritmul ArtMuseum este ideal pentru extragerea conturului din imagini ce contin frome cat mai exacte, dar rezultatele scazand pe masura ce imaginile devin mai complicate. De asemenea cele mai slabe rezultate se obtin in imaginile in care se gasesc zgomote. Aceste rezultate sunt oarecum asteptate daca ne gandim ca scopul principal al acestui algoritm este furnizarea datelor necesare "matchingului" de contururi. Totusi o sudiere atenta a algorimului ne-a permis sa stabilim o scala de sensibilitate a algorimului la datele de intrare, lucru ce imbunatateste mult calitatea rezulatelor. Prin acest mod putand fi evitate o parte din zgomote, sau accentuate variatii foarte mici ale culorii.
Pentru imbunatatirea rezultatelor am anexat aplicatiei o colectie de unelte, care isi gasesc aplicabilitatea in functie de necesarul utilizatorului.