OPERATII ASUPRA IMAGINILOR

(3/4)

Algoritmi morfologici de baza

Pentru imaginile binare principala aplicatie a morfologiei extragerea componentelor de imagine utile in reprezentarea si descrierea formelor:

-extragerea granitelor;-componente conectate;-invelitoarea conexa;-schelet.

Algoritmi:-umplerea de regiuni;-subtiere;-ingrosare;-retezare.

Extragerea granitelor

Granita unui set A, notata β(A): erodarea lui A cu un element de structurare potrivit B, apoi diferenta dintre A si rezultatul erodarii:

β(A) = A – (A Ө B)

Aplicatie. Se determina granita setului A cu elementul de structurare B (B8).

Analog, se determina granita corespunzatoare unui personaj, tot cu B8.

Element de structurare mai mare (5x5) => granita obiectelor de grosime mai mare (2 sau 3 pixeli).

,....3,2,1)( 1 kCkk ABXX

AX k

Umplerea regiunilor

-granita cu puncte 8-conectate (obtinut cu elementul de structurare B8)

a unei regiuni;-un punct interior granitei X0, setat la 1.

Se executa succesiv:

(B = elementul de structurare simetric B4). Algoritmul se incheie cand Xk = Xk-1.

Rezultatul:

(regiunea umpluta impreuna cu granita).

Extragerea componentelor conectate

Notiuni de conectivitate si componente conectate:

Un pixel p de coordonate (x,y) are patru vecini pe orizontala si verticala:(x+1,y), (x-1,y), (x,y+1), (x,y-1)

si reprezinta vecinii de ordin 4 ai lui p, notati N4(p).

Cei patru vecini diagonali:

(x+1,y+1), (x+1,y-1), (x-1,y+1), (x-1,y-1)

notati cu ND(p).

N4(p) + ND(p) = vecinii de ordin 8 ai lui p, notati N8(p).

Doi pixeli sunt conectati daca sunt vecini si satisfac anumite criterii de similaritate (egalitate a nivelurilor de gri).

V = setul de niveluri de gri utilizate pentru a defini adiacenta (imagini binare V = {1}).

Se considera trei tipuri de adiacente:-adiacenta de ordin 4: doi pixeli p si q cu valori in V sunt adiacenti de

ordin 4 daca q este in setul N4(p);

-adiacenta de ordin 8: doi pixeli p si q cu valori in V sunt adiacenti de ordin 8 daca q este in setul N8(p);

-adiacenta-m (adiacenta mixata): doi pixeli p si q cu valori in V sunt m-adiacenti daca

(i) q este in setul N4(p), sau

(ii) q este in setul ND(p) si setul N4(p) ∩ N4(q) nu are pixeli cu valori in V.

Adiacenta-m ~ modificare a adiacentei de ordin 8 pentru a elimina ambiguitatile.

Exemplu: (a) set de pixeli cu V = {1}; (b) cei trei pixeli din partea de sus prezinta adiacente de ordin 8 multiple (ambigue) (c) ambiguitatea este inlaturata prin utilizarea adiacentei-m.

a) b) c)

O cale (curba) de la pixelul p de coordonate (x,y) la pixelul q de coordonate (s,t) este o secventa de pixeli distincti de coordonate:

(x0, y0), (x1, y1), (x2, y2),...., (xn, yn)

unde (x0, y0) = (x, y), (xn, yn) = (s, t) iar (xi, yi), (xi-1, yi-1) sunt adiacenti pentru

1≤i≤n.Lungimea caii = n.Daca (x0, y0) = (xn, yn), => cale inchisa.

Se pot defini cai de ordin 4, 8 sau m (tip de adiacenta).

Exemplu: in exemplul precedent intre pixelii NE si SE exista (b) cai de ordin 8 (c) cale m. De remarcat lipsa ambiguitatii din cazul (c).

Fie S un subset de pixeli din imagine. Doi pixeli p si q sunt conetctati in S daca exista o cale intre acestia constituita in intregime din pixeli din S.

Pentru orice pixel p in S setul de pixeli din S conectati la acesta se numeste componenta conectata a lui S. Daca acesta are numai o componenta conectata atunci setul S se numeste set conectat.

Fie R un subset de pixeli din imagine. R se numeste regiune a imaginii daca R este un set conectat.

Granita („boundary”) sau contur a regiunii R este setul de pixeli din regiune avand unul sau mai multi vecini care nu sunt in R. Distinctie intre conceptele:

-granita („boundary”) = cale inchisa;-muchie („edge”) = discontinuitati de intensitate, valori derivative ce

depasesc un anumit prag.

Extragerea de componente conectate dintr-o imagine binara: esentiala in multe aplicatii de analiza a imaginilor.

Fie Y o componenta conectata continuta intr-un set A si p un punct din Y. Relatia iterativa care furnizeaza toate elementele din Y este:

,...3,2,1)( 1 kkk ABXX

X0 = p

B = un element de structurare potrivit.

In momentul in care Xk = Xk-1 => algoritmul s-a incheiat => Y = Xk.

Aplicatie. Se prezinta punctul initial p, elementul de structurare B, rezultatul dupa prima iteratie, rezultatul dupa a doua iteratie si rezultatul final.

Aplicatie. Identificarea componentelor conectate se utilizeaza in inspectia automata.

(a) O imagine cu raze X a unui piept de pui fragmente osoase. (b) tehnica de prag => evidentiaza oasele fata de fond. (c) erodarea cu element de structurare 5x5 => raman numai obiectele de dimensiuni semnificative extragerea componentelor conectate => rezultatul in tabela (15 componente conectate, dar 4 au dimensiuni semnificative => exista corpuri straine!).

Invelitoare convexa

O multime (un set) A este convexa daca o linie care uneste oricare doua puncte din A este continuta in intregime in A.

Invelitoarea convexa H a unui set oarecare S este cel mai mic set convex continand pe S.

Deficienta convexa a lui S = setul diferenta H – S.

=> utilitate: descrierea obiectelor.

4

1

)(

i

iC DA

Algoritm pentru obtinerea invelitorii convexe C(A) a unui set A.

Fie Bi , i = 1, 2, 3, 4 patru elemente de structurare. Se implementeaza ecuatia:

cu Xi0 = A. Fie Di = Xi

conv, („conv” indica convergenta Xik = Xi

k-1).

Invelitoarea convexa a lui A este:

(implementarea simplificata a transformarii „hit-or-miss” in care nu este necesara potrivire de background).

Aplicatie. Invelitoarea convexa a unui set A. In cadrul elementelor de structurare utilizate ‚x’ ~ valoarea nu conteaza (pentru o masca particulara are loc o potrivire de forma cand centrul ferestrei 3x3 este 0 si cei trei pixeli corespunzand zonei umbrite din masca sunt 1; celelalte valori din fereastra 3x3 nu conteaza).

Remarca: fiecare Bi este Bi-1 rotit in sens orar 90˚.

In ultima figura s-a evidentiat contributia fiecarui element de structurare.

Un dezavantaj al algoritmului: permite marirea setului reprezentand rezultatul in scopul de a garanta convexitatea.

Restrictie: sa nu se depaseasca pixelii extremi ai setului initial (pe verticala si orizontala) => micsorare a rezultatului. Exemplu:

Subtiere („thinning”)

Subtierea unui set A prin elementul de structurare B se poate defini prin transformarea „hit-or-miss”:

(nu este necesara operatie de background).

Mai utila: subtierea simetrica a lui A cu o secventa de elemente de structurare:

{B} = {B1, B2, B3, ... , Bn}

(unde fiecare Bi este Bi-2 rotit in sens orar 90˚):

Intregul proces este repetat pana cand nu se mai produc schimbari.

Rezultatul final. Setul subtiat convertit la conectivitate-m pentru eliminarea cailor multiple

Ingrosare („thickening”)

=> operatia inversa subtierii!

Definita:

ca operatie secventiala:

Se pot utiliza aceleasi elemente de structurare ca la subtiere, dar cu interschimbarea tuturor unitatilor si zerourilor.

Varianta: se subtiaza background-ul si apoi se complementeaza rezultatul.

a) b)

c) d)

(a) setul A; (b) complementul lui A; (c) rezultatul subtierii complementului lui A; d) ingrosarea obtinuta prin complementarea rezultatului (prin aceasta metoda pot rezulta puncte deconectate);

e)

(e) post-procesare pentru eliminarea punctelor neconectate.

KkkEkEk ,...,1,0]),([),()( BBABAAS

K

kk

0

)()(

ASAS

Schelet

Schelet = reprezentarea printr-o linie a unui obiect avand grosimea unui pixel, trece prin mijlocul obiectului si conserva topologia acestuia. Obtinerea scheletului nu este intotdeauna posibila! (ex: obiectul are grosimea de doi pixeli, sau nu se poate conserva topologia obiectului).

Definitia subsetului schelet data de Lantuéjoul Sk(A) este:

unde E(A,kB) este erodarea succesiva a lui A de k ori utilizand elementul de structurare B, ’◦’ este operatorul de deschidere, K este valoarea cea mai mare a lui k inainte ca setul Sk(A) sa devina vid. Elementul de structurare B este ales

in Z2 astfel incat sa aproximeze un disc circular, deci este convex, marginit si simetric.

Scheletul:

K

kk k

0

))((

BASA

BAS kk )(

BBBASBAS ...))))((...(())(( kk k

Obiectul original poate fi reconstruit din subseturile schelet Sk(A), elementul

structural B si K:

unde

reprezinta k dilatari succesive ale lui Sk(A):

Aplicatie. Pe prima coloana este setul initial si apoi doua erodari succesive cu elementul de structurare B (inca o erodare ar fi furnizat setul vid, deci K = 2). Se observa etape succesive pentru obtinerea scheletului si apoi refacerea setului A.

Schelet mai gros!

Observatie: nu este conectat (definitia scheletului prin operatii morfologice nu garanteaza conectivitatea).

Retezare („pruning”)

Algoritmii de subtiere si scheletizare pot lasa componente parazite (indepartate printr-o post-procesare) => metode de retezare.

Recunoasterea automata a caracterelor scrise de mana: analizarea formei scheletului fiecarui caracter. Deseori scheletele sunt afectate de „pinteni” (componente parazite), aparute prin erodare => tehnici morfologice (presupunere: lungimea componentelor parazite < un numar specificat de pixeli).

Aplicatie. 'a‘ de mana cu o componenta parazita in partea stanga (a). Se va elimina orice ramificatie cu max trei pixeli.

Solutia: subtierea setului de intrare A cu o secventa de elemente de structurare proiectate sa detecteze numai puncte terminale.

{B} = secventa de elemente de structurare B1 - B8 (b,c). ‘x‘ ~ "nu conteaza“.

314 XXX

Pasii algoritmului:

1)Subtierea lui A (ecuatia precedenta) de trei ori => X1 (d).

2) Refacerea caracterului fara ramuri parazite: X2 = setul punctelor finale ale lui

X1 (e):

3) Dilatarea punctelor finale de trei ori utilizand setul A ca delimitator (f):

(H = element de structurare 3x3 cu biti 1)

4) Reuniunea X3 cu X1 => rezultatul (g):

a) b), c)

d) e)

f) g)