Download - OPERATII ASUPRA IMAGINILOR ( 3 /4)
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)