Cap4. Segmentarea imaginiiSegmentare = divizarea imaginii n pri (regiuni) corelate cu obiectele i suprafetele din imaginiSegmentare: complet regiuni disjuncte = obiecte: proc. de nivel rid. parial regiuni ce nu conduc direct la obiecte: proc. de nivel scaz.Segmentare partiala regiuni omogene (luminozitate, culoare, textura etc.)

Metode de segmentare bazate pe cunotine globale despre imagine (uzual se foloseste histograma) bazate pe muchii (lanturi de muchii frontiera) bazate pe regiuni (dezvoltarea regiunilor)

Cap. 4. Segmentarea imaginii 4.1. Segmentarea prin metode de prag

Nivel de gri constant = prag extragerea obiectelor din fundalSegmentarea complet a unei imagini R regiunile R1, R2, RS

Metoda pragului:

1= obiecte,0 = fundal (sau invers) : imagine binara

Metode de prag globale: un singur prag T pentru R (i) locale:pragul T variaz pe R (ii)

Cap. 4. Segmentarea imaginii Band-thresholding

Praguri multiple

Semi-prag Metoda pragului niveluri de gri din imagine, gradientul imaginii etc.Di = submulimi de niveluri de gri

Cap. 4. Segmentarea imaginii

Cap. 4. Segmentarea imaginii Rosu [26 56]; Albastru [110 128];Verde [56 84];Violet [147 166];

4.1.1. Detecia pragului Metoda p-tileText tiprit: aria ocupat de caractere = = 1/p din aria total histograma : (1/p)NG

Cap. 4. Segmentarea imaginii

Metoda optimal de gsire a pragului

probabilitatea ca un pixel dintr-o imagine MN s aib nivelul de gri gHistograma Distributie probabilistic variana = gradul de omogenitatePri omogene variane miciPragul TH-bimodala

(i) i (ii): variana ponderat pragul T : se calculeaza efort de calcul

: probabilitatea de apariie a pixelilor cu NG T

: probabilitatea de apariie a pixelilor cu NG > T varianavarianaCap. 4. Segmentarea imaginii

Cap. 4. Segmentarea imaginii Soluie iterativ (rapida): media i variana total

Cap. 4. Segmentarea imaginii ( nu depinde de T )se calculeaz recursiv

Algoritm de segmentare:1o ntreaga imagine = o singur regiune2o band spectral histogram netezithistogram max. semnificativ + 2 min. segmentarea n 2 subregiuni proiectarea ntr-o singur imagine multispectral3o Repet pasul 2o pentru fiecare regiune un singur maximCap. 4. Segmentarea imaginii 4.1.2. Metoda pragului pentru imagini multispectraleSegmentare prin metoda pragului pe fiecare banda

(1)

(2)

Segmentarea unei imagini bispectrale

Cap. 4. Segmentarea imaginii 4.2. Segmentarea bazat pe muchii

Istoric: primul grup de tehnici de segmentare Segmentare: gasirea muchiilor lanturi de muchii frontiera (contur) Metode de segmentare bazate pe muchii - strategii de construire a conturului final - informatii apriorice disponibile in procesul de segmentare Zgomot muchii false prag Prewitt LoG

4.2.1. Relaxarea muchiilorFrontiere prin metode de prag zgomoteProprietile muchiei n contextul mutual al vecinilor creste calitatae segmentariiIntensitatea muchiei ntr-o vecintate local gradul de certitudine al muchiei Metoda de relaxare bazata pe muchiile dintre pixeli (crack edges)Contextul muchiei cele dou capete (varfuri) extreme Vst, Vdr Se pot aduga i muchiile i i h paralele cu e Relaxarea muchiilor frontier continue muchie central: cte un vrf la fiecare capt 3 posibile continuri ale frontierei din fiecare vrf Vrf nr. de muchii emanat (fr e) = tipul vrfuluiTipul muchiei = i - j = forma muchiei i, j = tipurile vrfurilor muchiei

Cap. 4. Segmentarea imaginii

a

b

c

d

f

g

i

h

e

Muchii crack

Cap. 4. Segmentarea imaginii

Pentru simetrie: i j situaii contextuale: 0 - 0muchie izolat : influen negativ asupra certitudinii 0 - 2capt mort: influen negativ asupra certitudinii 0 - 3 0 - 1muchie nesigur: influen slab pozitiv sau fr influen 1 - 1muchie de prelungire (continuare): influen puternic pozitiv 1 - 2 muchie de continuare spre intersecia 1 - 3 frontierei: influen medie pozitiv 2 2 3 - 3 punte ntre frontiere : fr importan pentru segmentare 2 - 3 fr influen

Tipuri de muchii

3 - 3

e

2 - 0

e

1 - 1

e

e

0 - 0

Cap. 4. Segmentarea imaginii Relaxarea muchiei metod iterativ certitudinea muchiei converge la: 0 = muchie terminal1 = muchie ce formeaz frontieraCertitudinea c(1)(e) pentru primul pas = magnitudinea normalizat a muchiei crack eNormalizareamax. global al muchiilor crack din ntreaga imaginemax. local ntr-o vecintate a muchiei Algoritm de relaxare1o Calculeaz c(1)(e) pentru toate muchiile crack din imagine2o Gsete tipul muchiei utiliznd certitudinea ntr-o vecintate3o Actualizeaz c(k+1)(e) : tipul muchiei + c(k)(e) 4o Stop dac toate certitudinile converg ctre 0 sau 1; dac nu se repet 2o i 3oAlgoritmul evalueaz: tipul vrfurilor tipul muchiilor modificarea certitudinii muchiilor

Cap. 4. Segmentarea imaginii Un vrf este de tipul i dac:

a, b, c: valorile normalizate ale muchiilor crack incidente cu m = max(a, b, c, q); q constant egal de obicei cu 0.1 Ex. vrf de tipul 1 (q = 0.1) vrf de tipul 3 (q = 0.1) Tipul muchiei o nlnuire a tipurilor vrfurilor Modificarea certitudinilor muchiei: - certitudinea crete - certitudinea descrete

Cap. 4. Segmentarea imaginii 4.2.2. Trasarea frontierelorReginile def. in imagine (binare-etichetate) frontiere:interioara, exterioara, extinsa Algoritmi pentru trasarea frontierei interioare1o P0 : pixelul din stnga sus al unei regiuni dir = direcia de la pixelul precedent curent (i) dir = 3 (V4);(ii) dir = 7 (V8)2o V(33) pentru pixelul curent: caut (trig.) (i) (dir + 3) mod 4 (c); (ii) (dir + 7) mod 8 (d) pentru dir par (dir + 6) mod 8 (e) pentru dir impar Primul pixel = valoarea pixelului curent un nou element Pn al frontierei actualizeaz direcia3o Elementul curent al frontierei Pn = P1 : al doilea element i dac Pn-1 = P0 STOP Dac nu pasul 2o 4o Pixelii P0 . Pn-2 = frontiera interioar

(e)

(d)

(c)

3

5

1

7

(b)

V8

6

4

2

0

(a)

V4

3

2

1

0

Exemplu: Trasarea frontierei interioare 1 2 3 4 5 6Pasul 1o: P0 dir = 7 Pasul 2o: P0 dir = (7+6)mod 8 = 5 (5,2)=P1 dir = 5 P1 dir = (5+6)mod 8 = 3 (4,1), (4,2)=P2 dir = 4 P2 dir = (4+7)mod 8 = 3 (3,1), (3,2), (3,3)=P3 dir = 5 P3 dir = (5+6)mod 8 = 3 (2,2), (2,3)=P4 dir = 4 P4 dir = (4+7)mod 8 = 3 (1,2), (1,3), (1,4), (2,4)=P5 dir = 6

Not: Algoritmul nu poate detecta frontiera interioar a unei guriCap. 4. Segmentarea imaginii - pixelii testai pe parcursul trasrii frontierei - pixelii frontierei

1

2

3

4

Trasarea frontierei pentru V8

P5

P4

P3

P2

P1

P0

Exemplu: Trasarea frontierei exterioare Pasul 1o: P0 dir = 3Pasul 2o: P0 dir = (3+3)mod 4 = 2 (1, 2), (2, 3), (3.2)=P1 dir = 0 P1 dir = (0+3)mod 4 = 3 (3,3)=P2 dir = 3 P2 dir = (3+3)mod 4 = 2 (2, 3), (3,4)=P3 dir = 3 P3 dir = (3+3)mod 4 = 2 (2, 4), (3, 5), (4,4)=P4 dir = 4Cap. 4. Segmentarea imaginii Algoritm pentru trasarea frontierei exterioare1o Traseaz frontiera interioar utiliznd V42o Pixelii testai R frontiera exterioar Frontiera exterioar perimetrul, compatitatea

Trasarea frontierei exterioare (()

P4

P3

P2

P1

P0

1 2 3 4 5 6 7 8

1

2

3

4

5

Cap. 4. Segmentarea imaginii Frontiera extins Frontiera interioar R Frontiera exterioar RFrontiera extinsa regiuni adiacente

Definirea frontierei extinse V8 R: regiune ; Q: exteriorul regiunii R

Pixelii frontierei interioare regiunii R: pixel STNGA: P R i P4(P) Q pixel DREAPTA: P R i P0(P) Q pixel SUS: P R i P2(P) Q pixel JOS: P R i P6(P) Q

1

2

3

5

6

0

7

4

P

P1(P)

P0(P)

Codare

Definirea frontierei extinse Fie submulimile corespunzatoare lui R: STNGA (R), DREAPTA (R), SUS (R), JOS (R) FE submultimea punctelor P, P0, P6, P7 ce satisfac: FE = {P: P STNGA (R)}{P: P SUS (R)} {P6(P): P JOS (R)} {P6(P): PSTNGA (R)}{P0(P): PDREAPTA (R)}{P7(P): PDREAPTA (R)}Exemplu: Trasarea frontierei extinseCap. 4. Segmentarea imaginii Frontiera extins

R

SUS (R)

JOS (R)

DREAPTA (R)

STNGA (R)

Cap. 4. Segmentarea imaginii Construirea FE folosind frontiera exterioar (a) frontiera exterioar(b) construirea FE (c) FE = aceeai form cu frontiera obiectului

Frontiera exterioar: DREAPTA, STNGA, SUS, JOSSe deplaseaz: - DREAPTA un pixel n jos- STNGA un pixel spre dreapta- SUS un pixel n jos i la dreapta- JOS nu se modific

(a)

(b)

(c)

Cap. 4. Segmentarea imaginii Algoritm de trasare a FE metoda look-up tableTabelul ce definete 12 situaii posibile ale configuraiei locale a unei ferestre 2 2, dependente de direciile precedente i de statutul pixelilor ferestrei.

1o Definete pixelul de start: standard (stg. dr., sus jos )2o Prima micare dup 1o: dir = 6 (jos) (i) din tabel3o Traseaz FE cu tabelul de mai sus FE nchis STOPObservaie: Algoritmul nu permite trasarea frontierelor gurilor gaura regiune separat pentru care se aplic algoritmul

(a)

(b)

(c)

(d)

(e)

(f)

(l)

(k)

(j)

(i)

(h)

(g)

fundal

regiune

fundal sau regiune

4.2.3. Conectarea muchiilor cu ajutorul grafurilor orientateCunotine apriorice: - punctele de START i STOP ale unei frontiere - muchiile x R2 din imagine cu magnitudinea s(x) i direcia (x) Graf: - noduri ni muchiile x - arce ntre nodurile orientate si ponderate: ponderea = cost ni (xi) nj(xj): (xi), (xj) = dir. local a frontiereiReguli pentru construirea grafurilor - muchie = nod dac s(x) T ; T = prag - ni (xi) nj(xj) => intre noduri va exista un arc daca: xj este unul din cei trei vecini (V8) ai pixelului xi n direcia: diferena direciilor : - arcele se pondereaz cu s(xj) Cap. 4. Segmentarea imaginii

Cap. 4. Segmentarea imaginii ExempluMuchii cu directii simagnitudiniConstruirea unui graf orientat

START

STOP

1

2

3

4

5

1

5

3

7

8

6

5

T=1

8

7

7

6

6

3

3

3

2

5

1

2

5

1

J

B

F

H

I

E

G

C

D

A

Cap. 4. Segmentarea imaginii Construirea frontierei

Construirea frontierei gsirea unei ci de cost minim n graf de la un nod de START xA la un nod de STOP xB g(xi): funcia de cost a cii optime ntre nodurile nA i nB ce trece prin ni : xA xi xB g(xi): componente gs(xi): estimarea costului cii xA xi ge(xi): estimarea costului cii xi xB gs(xi): suma costurilor arcelor sau nodurilor xA xi ; sau lungimea xA xi gs(xi): lungimea frontierei xi xB

Funcia de cost esenial poate fi dependent de:a) - modulul gradientului: b) - curbura frontierei detectate:c) - distana pn la punctul final:

Cap. 4. Segmentarea imaginii Exemplu Functia de cost:

g(D) = 1; g(C) = 7; g(G) = 5 => D selectat (se renunta la C si G) => din D: E, F si B determina calea

A

(

D

C

(

G

(

H

I

E

J

B

F

2

5

1

1

5

2

3

3

3

6

6

7

7

8

4.2.4. Conectarea muchiilor folosind tehnici de programare dinamica

Optimizare: => gasirea unui optim global in mai multi pasi Bellman optimul unei cai intre doua puncte => optimul intre oricare doua puncte care apartin caii Dac:

Eliminm x2:

numai n h1Cap. 4. Segmentarea imaginii calcule n loc de pnn pasi cu optimizarea unor functii de 2 variabile

Cap. 4. Segmentarea imaginii Trasarea frontierei funcie de evaluare care s conduc la cea mai bun frontierCriteriul pentru estimarea unei bune frontiere din n pixeli:

Criteriul are forma (*) optimul funciei de evaluare

Cap. 4. Segmentarea imaginii ExempluPonderarea arcelor:Conectarea muchiilor folosind programarea dinamica

(23)

max(19,28)

max(10,13)

(8)

max(9,10)

f(xk)

k

5

4

3

2

1

max(11,12)

max(9,16)

(8)

(5)

J

B

F

H

I

E

G

C

D

A

7

7

6

5

6

2

3

3

2

4

4

0

1

5

0

J

B

F

H

I

E

G

C

D

A

START

STOP

1

2

3

4

5

1

5

3

7

8

6

Cap. 4. Segmentarea imaginii 4.2.5. Transformata Hough

Obiecte = forme i mrimi cunoscute

Cap. 4. Segmentarea imaginii

Detectare unei linii drepte expresia analitic

Linie punct n planul parametrilorDetecia liniilor: - se extrag muchiile (posibile puncte ale liniilor) daca s(x)T- pentru fiecare punct: un numr limit de direcii (a discretizat)- b discretizat structura rectangulara de celule in planul parametrilor- pentru fiecare celula un acumulator A(a, b) se incrementeaz la detectarea liniei - pentru fiecare muchie se determina a, b: linii cu directii permise ce trec prin pixelul respectiv valorile a, b: A(a, b)

EMBED Equation.3

y

x

EMBED Equation.3

EMBED Equation.3

b

a

b

EMBED Equation.3

EMBED Equation.3

a

_1098689529.unknown

_1098689806.unknown

_1098689874.unknown

_1098689595.unknown

_1098689402.unknown

Cap. 4. Segmentarea imaginii

Cap. 4. Segmentarea imaginii Detectia liniei detectia unui maxim local in spatiul acumulatorilorMetoda nu este sensibil la:- poriuni lips din linie- zgomote- alte structuri linii linii verticale a : Transformata Hough pentru curbe complexe: a : vector al parametrilor curbei x Algoritm pentru detecia curbelor1o Cuantizeaz spatiul parametrilor2o Formeaza o arie de acumulatori A(a); seteaza pe 0 toate elementele 3o (x1, y1) muchie si4o Maxim local in aria A realizarea curbei f (x, a).

y

x

'

'

'

'

_1098689529.unknown

_1098689806.unknown

_1098689874.unknown

_1098689595.unknown

_1098689402.unknown

Cap. 4. Segmentarea imaginii Exemplu: Cercul Acumulator tridimensional A(a,b, r): se va incrementa daca (a, b) este la distanta r fata de x Acumulatorul creste exponential cu numarul parametrilor Volum de calcule scazut: informatii apriorice despre directia muchiilor Exemplu: Detectia unei frontiere circulare cu raza R - muchii cu 8 directii se incementeaza un numar mai mic de celule

: relatia satisfacuta incrementare- : directia muchiilor pentru pixelul x- : eroare maxima de directie anticipata - A mai mare pentru muchii cu magnitudini mari Parametrii pot reprezenta diferite curbe analitice:- linii, cercuri, elipse, parabole, etc.

Cap. 4. Segmentarea imaginii

Cap. 4. Segmentarea imaginii 4.2.6. Construirea regiunilor cu ajutorul frontierelorSegmentarea bazata pe muchii detectia frontierelor segmentaretotalapartiala frontiere partialeFrontiere partiale construirea regiunilor Metoda superslice - pentru regiuni cu prop. dominante dependente de nivelurile de gri - se cunoaste amplasarea in imagine a unor fragmente de frontiera - regiunea R: in interiorul frontierelor partiale - pixelii de frontiera: pozitia x directia (x) - se cauta pixelul opus = pixel muchie semnificativa pe o directie perpendiculara (x) - pixel al regiunii R = pixel de pe liniile ce unesc pixelii opusi

Cap. 4. Segmentarea imaginii Algoritm de formare a regiunilor din frontiere partiale 1o Pentru fiecare pixel x al frontierei se cauta pixelii opusi pe o distanta M; se conecteaza prin linii pixelii opusi 2o Calculeaza de cte ori un pixel s-a aflat pe o linie = numarul de marcari b(x) 3o Determina numarul ponderat de marcari B(x):B(x) = 0.0 pentru b(x) = 0 B(x) = 0.1 pentru b(x) = 1B(x) = 0.2 pentru b(x) = 2B(x) = 0.5 pentru b(x) = 3B(x) = 1.0 pentru b(x) > 3Certitudinea ca un pixelCondiia ca x si y sa fie opusi:

Cap. 4. Segmentarea imaginii

Cap. 4. Segmentarea imaginii 4.3. Segmentarea imaginilor prin formarea regiunilor

Omogenitatea regiunilor divizarea imaginii in zone cu omogenitate maxima- segmentare (S)Functie binara de evaluare a omogenitatii regiunilor Ri H(Ri)- omogenitate (O)Ri adiacent cu Rj - maximalitate (M)Segmentarea regiuni cu proprietatile O si MFormarea regiunilor - unirea regiunilor - divizarea regiunilor - unirea/divizarea regiunilor

Cap. 4. Segmentarea imaginii 4.3.1. Unirea regiunilor Algoritm de unire a regiunilor1o Defineste o metoda de startare a segmentarii regiuni mici care satisfac (O) 2o Defineste un criteriu de unire a doua regiuni adiacente3o Uneste toate regiunile ce satisfac criteriu de la pasul 2o. Daca nu exista nici un grup de doua regiuni ce satisfac criteriu STOP

Metode simple Regiuni: 22, 44, 88 proprietati statistice (histograma) Regiunile adiacente cu aceleasi descrieri se unesc; se marcheaza regiunile ce nu pot fi puse in corespondenta O regiune nu poate fi unita cu nici un vecin adiacent STOP

Cap. 4. Segmentarea imaginii 4.3.2. Divizarea regiunilorSTART: Imaginea = o regiune nu satisface (O)Se divide imaginea in regiuni cu: (S, (O) si (M)4.3.3. Divizare si unireReprezentare piramidala a imaginii regiunea = patrat- Regiune neomogena divizare in patru regiuni- 4 regiuni a unui nivel cu aceeasi omogenitate o regiune

DivizareUnire

Segmentarea = construirea unui arbore cvadripartit- fiecare nod f. = regiune omogena(f. = frunza)- nr. noduri f. = nr. regiuni segmentateCap. 4. Segmentarea imaginii Divizare si unire eliminarea sau adaugarea unor parti din arborele cvadripartitArbore cvadripartit de segmentare

Cap. 4. Segmentarea imaginii Algoritmul divide si uneste1o Segmentarea initiala in regiuni omogenitatereprezentare piramidala2o H(R) = (fals) divide R in 4 regiuni copil; daca 4 regiuni cu acelasi parinte pot fi unite uneste-le. Daca nu se pot uni sau divide regiunile 3o3o Ri, Rj adiacente daca se pot uni intr-o regiune omogena uneste-le chiar daca nu fac parte din acelasi nivel al piramidei sau daca nu au acelasi parinte4o Uneste regiunile mici cu cele mai similare regiuni adiacente daca este necesar sa fie eliminate regiunile cu dimensiuni mici.