Determinarea contururilor unei regiuni

Determinarea contururilor unei regiuni

O regiune este un set de pixeli conectat in care toti pixelii au aceeasi intensitate/culoare.

Definitii

1a: Doi pixeli sunt vecini directi (vecini-d) daca celulele lor au o latura comuna .

1b: Doi pixeli sunt vecini indirecti (vecini-i) daca celulele lor se ating numai intr-un colt .

1c: Termenul vecin-N, 0≤N≤7, desemneaza un pixel aflat in pozitia N fata de un pixel P, ca in figura de mai jos:

vecini-d sunt vecini-N, cu N=par

vecini-i sunt vecini-N, cu N=impar

2a: O cale este o secventa de pixeli A₁, A₂, . , A_n, astfel incat:

pentru k>1, A_k-1 este un vecin al lui A_k

pentru k<n, A_k+1 este un vecin al lui A_k

2b: O cale-d este o cale in care toti pixelii sunt vecini-d.

2c: O cale simpla este o cale in care toti pixelii sunt disjuncti si nici un pixel nu are mai mult de 2 vecini-d in cale.

2d: O cale inchisa este o cale in care primul pixel coincide cu ultimul.

Un set de pixeli, S, este conectat (sau conectat-i), daca pentru fiecare pereche de pixeli A si B din S, exista o cale in care A si B sunt primul si ultimul element, iar toti ceilalti pixeli ai caii apartin lui S.

Termenul set de pixeli conectat-d are intelesul care rezulta, adica intre fiecare pereche de pixeli exista o cale-d.

Reprezentarea contururilor

Prin adresele absolute ale pixelilor care-l compun, sau adresa primului urmata de adrese relative

Prin cod Freeman = cod de inlantuire

Prin cod de inlantuire diferential

Pentru un contur neted, in codul diferential predomina 0, +1, -1.

De aceea pentru reprezentarea unui contur prin cod diferential se poate folosi un numar diferit de biti pentru fiecare directie, rezultand o medie de 2biti/pixel:

Extragerea contururilor regiunilor

Conturul unei regiuni este traversat pe o cale inchisa, fiind posibil intotdeauna sa se aleaga o astfel de cale.

Un pixel de contur este un pixel care are cel putin un vecin-d in afara regiunii.

Pixelul de start se poate alege de exemplu scanand imaginea de sus in jos si de la stanga la dreapta: el este un pixel care apartine regiunii considerate (are intensitatea pixelilor regiunii) si este pixel de contur.

Traversarea consta intr-o deplasare pixel cu pixel, in fiecare pas fiind ales ca pixel urmator pixelul din regiune care este cel mai in dreapta fata de pixelul curent. In acest fel interiorul regiunii se afla intotdeauna in stanga pixelului selectat (conturului).

Cu aceasta regula de traversare, contururile exterioare sunt parcurse in sens trigonometric, iar cele interioare in sensul acelor de ceas.

Algoritm de extragere a unui contur

Punctul de start se alege astfel incat vecinul sau 4 sa nu apartina regiunii.

Alegerea se bazeaza pe cunoasterea intensitatii pixelilor din regiune. Punctul de start ales poate fi un pixel izolat.

Notatii:

S - pixelul de start

C - pixelul curent

D - directia de cautare a urmatorului pixel de contur, unde 0≤D≤7, iar directiile sunt codificate astfel:

urm - pixelul din vecinatatea celui curent, care ar putea fi urmatorul pixel de frontiera (contur)

contur = vector in care se memoreaza directia de deplasare in fiecare pas; in final se va obtine reprezentarea prin cod de inlantuire (Freeman) a conturului traversat.

urm in R = true, daca urm apartine regiunii R (are intensitatea pixelilor regiunii).

Operatiile si Θ sunt operatii "modulo". Astfel:

daca D=0 atunci D

daca D=6 atunci D

Initial D=6.

In fiecare iteratie se cauta urmatorul punct de contur printre vecinii D Θ 1, D, D 1 ai pixelului curent.

Algoritmul se termina cand pixelul curent este cel de start.

Este posibil ca pixelul de start sa fie un punct izolat. De aceea, daca dupa trei iteratii nu s-a gasit un alt punct de contur, inseamna ca punctul de start este punct izolat.

Functia PunctContur prezentata in continuare primeste ca parametru punctul de contur curent si intoarce urmatorul punct de contur, sau punctul curent daca in vecinatatile D Θ 1, D, D 1 nu se gaseste un punct de contur. Directia in care s-a gasit urmatorul punct de contur este memorata in vectorul contur.

unsigned char * contur;

int n=0, D;

Punct PunctContur (Punct C)

urm = vecin(C, D);

if (urm in R)

urm = vecin(C, D

if (urm in R)

D = D

return C;

}

Functia ExtrageContur primeste ca parametru punctul de start contur.

int ExtrageContur (Punct S)

if( k==3) return 0; // S este punct izolat

// traverseaza conturul

while( C != S)

C = PunctContur(C);

return 1;

Extragerea tuturor contururilor unei regiuni

Pentru simplificare, vom considera ca

o  pixelii regiunii au intensitatea =1;

o  pixelii din afara au intensitatea =0

Acestea nu sunt restrictii, algoritmul prezentat in continuare putand fi generalizat.

O regiune poate avea mai multe contururi interioare care marginesc "gauri" ale regiunii.

Se incepe cu extragerea conturului exterior, executand algoritmul "ExtrageContur" modificat astfel incat:

o  punctul de start sa fie memorat intr-un vector PStart

o  codurile de inlantuire sa fie memorate in vectorul contur, in care delimitarea contururilor se face prin valoarea 8 (adica 8=sfarsit contur)

o  la traversarea unui contur, valoarea pixelilor conturului se incrementeaza, devenind 2 sau > 2 in cazul in care un pixel este parcurs de mai multe ori la traversarea conturului. In acest fel se pot recunoaste contururile deja traversate.

Functia ExtrageContur modificata pentru traversarea tuturor contururilor este:

Punct * PStart; int ncont=0;

unsigned char ** Img;

int ExtrageContur (Punct S)

if( k==3) return 0; // S este punct izolat

PStart[ncont++] = S;

Img[S.y][S.x]++;

// traverseaza conturul

while( C != S)

contur[n++] = 8;

return 1;

Dupa ce toate contururile au fost traversate, vectorul P va contine punctele de start pentru toate

contururile, iar vectorul contur va contine lista codurilor de inlantuire pentru toate contururile, separate

prin valoarea 8

Pasii algoritmului:

Se extrage conturul exterior.

Se cauta un punct pe contur din care va incepe parcurgerea regiunii pentru gasirea contururilor interioare.

Parcurgerea regiunii are loc intotdeauna spre dreapta, de aceea punctul de start pentru parcurgere se

alege de pe un arc coborator.

Conditia ca un punct sa fie punct de start parcurgere este:

o  codul punctului de contur anterior sa fie cuprins intre 4-7

o  codul punctului de contur curent sa fie cuprins intre 5-7

Se parcurge regiunea din punctul de start determinat, spre dreapta, cautand fie un punct de start pentru un contur interior, fie marginea regiunii (iesirea din regiune).

Parcurgerea regiunii pe linia curenta se termina la intalnirea secventei 120 sau 01.

Secventa 120 marcheaza intalnirea unui contur deja traversat.

Secventa 01 marcheaza intalnirea unui contur interior netraversat. In acest moment se termina parcurgerea liniei curente si se extrage conturul interior. Dupa extragere, pixelii conturului vor avea valoarea 2, deci, pe liniile imagine urmatoare el va fi identificat ca un contur deja parcurs prin intalnirea secventei 120.

Atunci cand un contur interior are pixeli comuni cu un alt contur (cel exterior sau unul interior), dupa traversarea sa pixelii comuni vor avea o valoare >2.

Exemple: curs

Implementarea in C a algoritmului:

Punct * PStart; int ncont=0;

unsigned char ** Img;

unsigned char * contur;

int n=0, D;

int ExtrageToateContururile(Punct S)

else

P = PunctUrm(P,c); // calculeaza adresa urmatorului punct de contur

if( 4 <= c0 <= 7 && 5 <= c <= 7) // P este punct de start parcurgere spre dreapta

else

if( A==0 && B>2 && C==0 // contur interior deja parcurs

|| A==1 && B==2 && C==0) // contur exterior regiune

x++;

}// while (! gata)

c0 = c;

}//while (l<n-1) - sfarsit lista contururi