Segmentarea imaginilor

Segmentarea imaginilor

O metoda de extragere a caracteristicilor din imagini se bazeaza pe determinarea zonelor din imagine care contin pixeli cu caracteristici similare de stralucire, culoare sau textura.

Clasificare

Metodele de segmentare se impart in urmatoarele categorii:

1.  Segmentarea prin divizare (" splitting " )

Se pleaca de la o zona mare, de exemplu intreaga imagine care se sparge in mai multe regiuni. Daca regiunile obtinute nu sunt

omogene, se continua spargerea pana cand se obtin regiuni omogene (care satisfac un anumit criteriu de omogenitate).

2.  Segmentarea prin divizare si unificare (" split & merge ")

Se pleaca de la regiuni de marime medie, de exemplu patrate de marime fixa, se unifica regiunile similare si apoi se divizeaza

regiunile care nu au fost unificate (nesatisfacand criteriul de unificare).

3.  Segmentarea prin extindere ("merging")

Pornind de la o regiune mica, de exemplu de un pixel, se dezvolta regiunea treptat, pana cand criteriul de extindere nu mai este

satisfacut.

4. Segmentarea prin extindere si unificare

O imagine segmentata contine mai multe regiuni, pixelii fiecarei regiuni avand aceeasi intensitate, culoare sau textura

Algoritm de segmentare prin divizare recursiva

Se porneste de la premisa ca intreaga imagine este omogena. Daca nu este adevarat, atunci imaginea este divizata in patru regiuni. Procedura de divizare este aplicata recursiv pana cand se obtin numai regiuni omogene.

Implementare in C prezentata la curs 

Applet - segmentarea prin spargere recursiva

Algoritmul de segmentare prin divizare recursiva produce o imagine segmentata care poate fi reprezentata printr-un arbore cuadric

Fiecare nod are patru fii, corespunzatori celor patru regiuni in care se face divizarea de fiecare data. Este suficient sa se memoreze in fiecare nod al arborelui intensitatea care a fost atribuita pixelilor regiunii corespunzatoare nodului.

Algoritmul are insa un dezavantaj major : poate produce regiuni adiacente similare

Astfel:

daca P(R) este un predicat logic care defineste regula de segmentare (de exemplu Imax - Imin < prag ),

atunci

daca P(Ri U Rj) = TRUE

=>  Ri si Rj sunt regiuni similare.

Regiunile adiacente similare trebuie sa fie unificate.

Segmentarea prin divizare si unificare ("split & merge")

Algoritmul "split & merge" este o procedura iterativa care include in fiecare iteratie divizare si unificare :

daca o regiune este neomogena (P(R) = FALSE ), ea este sparta in 4 regiuni.

daca doua regiuni adiacente Ri, Rj sunt similare (P(R_i U R_j) = TRUE ), ele sunt unificate.

algoritmul se termina atunci cand nu mai este posibila nici spargere, nici unificare.

Algoritmul este recursiv:

daca regiunea curenta nu este omogena, ea este divizata in 4 si procedura este apelata recursiv.

daca regiunea este omogena, se calculeaza media sa si se compara cu mediile regiunilor vecine. Se verifica posibilele unificari.

daca mai multe unificari sunt posibile, se alege cea mai buna, adica unificarea cu regiunea vecina care are valoarea medie cea mai apropiata de valoarea medie a regiunii curente.

Avantaj:

Algoritmul produce regiuni mai compacte decat cel prezentat anterior (bazat numai pe divizare).

Dezavantaj :

Algoritmul nu produce o reprezentare prin arbore cuadric.

O posibilitate :

Se aplica algoritmul de segmentare prin divizare obtinandu-se arborele cuadric al imaginii.

Se unifica regiunile similare care sunt adiacente in arbore (fiii de pe acelasi nivel) la sfarsit.

In implementarea prezentata in continuare se folosesc urmatoarele structuri de date :

A - imaginea de intrare

B - imaginea segmentata, in care toti pixelii unei regiuni au aceeasi intensitate obtinuta ca medie a intensitatilor pixelilor corespunzatori din imaginea de intrare.

NREG - matrice avand acelasi numar de elemente cu A si B, unde NREG[i][j] = numarul (eticheta) regiunii din care face parte pixelul B[i][j]

MED - vector cu un numar de elemente egal cu numarul de regiuni, unde MED [k] = intensitatea atribuita pixelilor regiunii cu numarul k.

BMED

Cod Java

Applet - Segmentarea prin divizare si unificare

Segmentarea prin divizare bazata pe praguri

1. Se aleg valorile de prag ca puncte de minim local ale functiei histograma :

Daca f(x, y) este functia imagine de intrare, atunci imaginea segmentata este definita de :

g(x, y) = R_i daca T_i-1 f(x,y) < T_i cu i = 1,N

In multe cazuri, "lobii" histogramei nu sunt clari datorita contributiei pixelilor aflati la frontiera dintre doua regiuni. Daca se elimina sau se modereaza contributia acestor pixeli in calculul histogramei, atunci lobii vor fi mai clari. Metoda cea mai simpla de modificare a histogramei in acest scop este de a detecta fronturile din imaginea de intrare, excluzand apoi in calculul histogramei pixelii de front.

Divizarea in N regiuni distincte, fiecareia corespunzandu-i un domeniu de intensitati.

f(x, y) - imaginea de intrare

g(x,y) - imaginea segmentata

g(x,y) =  

, i = 0,1..N-2

De exemplu,

N = 4, L = 256, L/N = 64

g(x,y) =  

Daca histograma imaginii este concentrata intr-un domeniu mic de intensitati, atunci segmentarea prin aplicarea unui prag uniform (metoda a 2-a) nu da rezultate bune deoarece majoritatea pixelilor vor fi repartizati intr-un numar foarte mic de regiuni.

In astfel de cazuri se poate folosi un prag neuniform pentru segmentare. Pentru aceasta, asupra imaginii de intrare se aplica transformarea de egalizare a histogramei.

Daca G(f(x,y)) este transformarea utilizata in egalizarea histogramei, atunci imaginea segmentata este

g(x,y) =

Tehnicile de segmentare bazate pe aplicarea de praguri garanteaza omogenitatea regiunilor, dar nu si conectivitatea lor, deoarece aplicarea pragurilor se face pixel cu pixel, fara sa se tina cont de vecinatatea fiecarui pixel.

Vecinatatea geometrica joaca un rol important in segmentarea imaginilor. Pixelii dintr-o vecinatate au in general proprietati statistice similare si deci apartin aceleiasi regiuni. De aceea, algoritmii de segmentare trebuie sa incorporeze, daca este posibil, atat criterii de similaritate cat si criterii de vecinatate.

Algoritmii de spargere recursiva adaptiva precum si algoritmii de spargere si unificare produc regiuni conectate deoarece ele provin din divizarea unei regiuni.

Segmentarea prin extindere

Se pleaca de la pixeli "germen" in jurul carora se vor forma regiunile. Acestia sunt de regula alesi de catre utilizator intr-un mod controlat.

Plecand de la pixelii germen se formeaza in jurul lor regiuni adaugand iterativ pixelii vecini care satisfac criteriul de similaritate.

Segmentarea prin extindere se bazeaza pe :

O regula care descrie mecanismul de extindere

O regula de verificare a omogenitatii regiunilor dupa fiecare pas de extindere

Mecanismul de extindere este simplu :

In fiecare pas K:

Pentru fiecare regiune R_i^(k) cu i = 1, N

Se verifica daca exista pixeli neclasificati in vecinatatea de 8 pixeli a fiecarui pixel de pe frontiera regiunii.

Un pixel vecin, X, este adaugat la regiune daca P (R_i^(k) U = TRUE), unde P este criteriul de similaritate:

P = unde T este un prag dat

Algoritmul se termina atunci cand intr-o iteratie numarul de pixeli clasificati nu s-a modificat (nici o regiune nu s-a mai putut extinde).

Pixelii germen pot fi alesi interactiv de catre utilizator sau automat ca pixeli a caror intensitate corespunde unuia dintre varfurile histogramei.

Cod Java

Applet - segmentarea prin extindere

Observatie:

Performanta algoritmului depinde mult de alegerea pixelilor germen.

Unificarea regiunilor

In urma segmentarii prin extindere ("cresterea" regiunilor) pot rezulta regiuni adiacente cu proprietati statistice similare. Ele pot fi reunite printr-un algoritm de unificare ("merging").

Ca proprietati statistice se pot folosi media si deviatia standard. Pentru o regiune Ri de n pixeli, acestea sunt definite astfel :

- media

- deviatia standard

Doua regiuni adiacente, R1 si R2, pot fi unificate daca mediile lor aritmetice sunt suficient de apropiate

, cu i = 1, 2

Unificarea poate fi inglobata in mecanismul de extindere.

Algoritm de extindere si unificare

Nu sunt disponibile informatii despre imagine (nu se dau germeni). Imaginea este parcursa pe randuri si fiecare pixel este atribuit unei regiuni. Atunci cand s-a ajuns in pixelul (k,l), toti pixelii de pe randurile anterioare, au fost deja atribuiti. Deci pixelul (k,l) are regiuni inconjuratoare daca nu este primul (k = 0, l = 0).

Mai intai se incearca atribuirea pixelului (k, l) la una dintre regiunile vecine. Daca nu poate fi atribuit unei regiuni existente, este atribuit unei regiuni noi (se creeaza o noua regiune).

Performanta algoritmului este dependenta de regula de unificare, adica de modul de atribuire a pixelului curent la o regiune existenta : P(Ri U (k,l))

Regula de asignare se poate baza pe media aritmetica si deviatia standard. Astfel, asignarea este permisa daca intensitatea pixelului este apropiata de media Mi a unei regiuni vecine:

Pragul Ti poate fi diferit de la regiune la regiune si de la pixel la pixel. El poate fi ales astfel :

unde M'_i  si s'_i sunt media si deviatia standard ale regiunii i unificate cu pixelul (k,l).

Daca pentru nici o regiune nu este satisfacuta conditia de asignare, pixelul (k,l) este atribuit unei regiuni noi.

Daca conditia este satisfacuta pentru mai multe regiuni vecine, pixelul este atribuit regiunii Ri pentru care diferenta

este minima.

Cresterea regiunilor este dependenta de parametrul T. Daca este mic, pragul Ti(k,l) este mic pentru toate regiunile si extinderea regiunilor este dificila. Vor rezulta multe regiuni mici. Daca este mare, pot rezulta regiuni putin omogene si cu deviatii standard mari. Pragul Ti (k,l) depinde de asemenea de raportul . Pentru regiuni omogene, acest raport tinde catre zero si Ti tinde catre T. Deci, T desemneaza diferenta maxima permisa intre intensitatea unui pixel si media unei regiuni foarte omogene. Pentru regiuni mai putin omogene, raportul '_i/M'_i este mai mare, pragul T_i devine mai mic si extinderea unor astfel de regiuni este restrictionata.