APIM8 - 1

Segmentarea imaginilor

APIM8 - 2

Ce este segmentarea?

• segmentarea = impartirea unei imagini in regiuni cu o

anumita semnificatie

• regiuni cu o anumita semnificatie = obiecte sau zone de

interes

• cel mai simplu – imagine binara - obiectul si fundalul

• segmentarea este primul pas in sistemele de recunoastere

a formelor

• dupa izolarea obiectelor de interes se pot efectua

masuratori pentru caracterizare (pattern recognition) ->

clasificarea obiectelor in clase si grupuri

APIM8 - 3

Generalitati • definirea regiunilor se face pe baza nuantelor de

gri sau a altor proprietati cum ar fi textura sau

culoarea

• uneori se poate utiliza pseudo colorarea

APIM8 - 4

Utilizari

• detectarea organelor (creier, plamani, inima,

ficat, etc.) in imagini tomografice si RMN

• diferentierea tesutului patologic de tesutul

normal

• planificarea tratamentului

• etc.

APIM8 - 5

Clasificarea metodelor

• trasaturile utilizate:

– valorile de gri

– textura

– valoarea gradientului

• tehnicile utilizate:

– necontextuale (tresholding)

– contextuale (bazate pe regiuni, bazate pe

frontiere, bazate pe muchii, contururi active,

watershed)

APIM8 - 6

Tresholding

• segmentarea imaginii utilizand pragul stabilit pe baza

histogramei = probabil cea mai des utilizata metoda

• usor de implementat

• necesita putine resurse UCP

• metodele presupun minimizarea sau maximizarea

unei functii criteriu

• prag global sau local

APIM8 - 7

Tresholding (2)

• dezavantaj: nu se tine cont de contextul spatial

in care apar valorile intensitatii

• utilizate frecvent pentru o segmentare initiala a

imaginii, inaintea aplicarii unor metode mai

sofisticate de segmentare -> reducerea

timpului de convergenta

APIM8 - 8

Tresholding (3)

• Succesul metodei depinde de selectia valorii de prag (treshold)

APIM8 - 9

Tresholding

(4)

APIM8 - 10

Tresholding (5) • Cazul ideal - histograma cuprinde doua distributii

separate (obiectele si fundalul), fara suprapuneri ->

valoarea de prag T se alege oriunde intre cele

doua distributii

• Cazul real – cele doua distributii se suprapun -> T

intre T1 si T2

APIM8 - 11

Conditii de ingreunare a determinarii

valorii de prag

• contrast slab al imaginii -> suprapunerea varfurilor

• fundal de intensitate variabila -> imposibilitatea

utilizarii unei singure valori de prag

• rezolutie spatiala slaba

• iluminare variabila

• obiecte cu niveluri diferite de luminozitate

APIM8 - 12

Tresholding optim • alegerea ca prag a valorii corespunzatoare fundului vaii dintre

cele doua varfuri nu este o valoare optima

• histograma = o suma ponderata a doua sau mai multe densitati probabilistice

• valoarea de prag = nivelul de gri care duce la cel mai mic numar de pixeli clasificati gresit (intersectia celor doua distributii normale)

• introdusa de Otsu

• functie discriminanta de determinare a pragului optim pentru segmentarea imaginii in regiuni aproape uniforme

APIM8 - 13

Tresholding optim (2)

APIM8 - 14

Tresholding optim (3)

APIM8 - 15

Tresholding optim (4) • zgomotul -> clasificare eronata a pixelilor

• imaginile sunt initial netezite cu filtre de mediere sau mediane

APIM8 - 16

Minimul variatiei

• exista mai multe abordari in implementarea treshholding-ului

optim

• scopul = alegerea unei valori de prag astfel incat fiecare pixel

de fiecare parte a pragului sa fie mai apropiat in valoare de

media pixelilor din partea respectiva a pragului decat de media

pixelilor din cealalta parte

• metoda minimului variantiei (Otsu)

• utila pentru imagini cu regiuni cu distributii de intensitate de

variatie egala

APIM8 - 17

Functiile de distributie

• Functie de distributie probabilistica discreta p(i)

, ni – nr. de pixeli de intens. i

M – nr. total de pixeli din im.

N – nr. de niveluri de gri

APIM8 - 18

Probabilitatile claselor • Se calculeaza probabilitatile claselor:

APIM8 - 19

Media si variatia claselor

• Se calculeaza media claselor:

• Se calculeaza varianta claselor

APIM8 - 20

Variatia totala

• varianta totala:

• varianta in clasa:

• varianta intre clase:

unde:

APIM8 - 21

Maximizarea variatiei intre clase

• Pragul optim (t*) – max. variantei intre clase:

• Pentru imagini multimodale (k clase):

• Sau minimizarea variantei in clasa

APIM8 - 22

Exemplu

APIM8 - 23

Functii criteriu echivalente

• propus de Kurita

• functia maximizeaza probabilitatea distributiei

conditionale a unui model de populatii mixte care

consta in doua distributii normale cu medii diferite si

cu variatie comuna

unde: pj – probabilitatea clasei j

APIM8 - 24

Exemplu

APIM8 - 25

Imagine trimodala

APIM8 - 26

Metoda isodata (alg. de clasificare

media –K) 1. Se aplica pragul calculat ca media varfurilor sau ca

media pixelilor

2. Se calculeaza valoarea medie a pixelilor cu valori

sub valoarea de prag, m1, si a celor deasupra valorii

de prag, m2

3. Se calculeaza noua valoare de prag T1=(m1+m2)/2

4. Se repeta pasii 2-3 pana cand valoarea de prag

ramane neschimbata sau diferenta dintre valorile de

prag este mai mica decat o valoare impusa

APIM8 - 27

Metoda isodata (alg. de clasificare

media –K) • in general, in primul pas al algoritmului se considera

ca valoare medie a primei clase valoarea medie a

pixelilor din colturile imaginii (ca facand parte din

fundal) si ca valoare medie a celei de a doua clase

media celorlalti pixeli

• Pentru media celorlalti pixeli se folosesc doar 5% din

pixelii ramasi, acestia fiind alesi aleatoriu

APIM8 - 28

Exemplu

• Prima iteratie

m1=(2+2+2+1)/4=1.75

m2=5.46

T=3.61

• Prima clasa {0,1,2,3} si a doua clasa {4,...,12}

• A doua iteratie

m1=2.44

m2=6.44

T=4.44

APIM8 - 29

Exemplu

• Prima clasa {0,1,2,3,4} si a doua clasa {5,...,12}

• A treia iteratie

m1=2.86

m2=6.96

T=4.91 -> clasele raman neschimbate

APIM8 - 30

Exemplu

Modelare mixta

APIM8 - 31

Exemplu

Seg. Otsu Seg.izodata Entropie max.

APIM8 - 32

Tresholding adaptiv • uneori utilizarea unei singure valori de prag nu

este posibila

• de ex. in imagini cu fundal variabil

APIM8 - 33

Tresholding adaptiv • o solutie – scaderea unei imagini care contine doar

fundalul si apoi aplicarea tresholdului optim

• alta solutie – utilizarea tresholdingului adaptiv:

– se considera ca un pixel are o vecinatate de nxn pixeli

si se calculeaza o valoare de prag, TL pentru aceasta

– valoarea pixelului este setata la alb sau negru in

functie de aceasta valoare de prag

– mai eficient daca:

TL = {val. medie sau mediana) – C

– este necesara determinarea lui n si C

APIM8 - 34

Exemplu

Tresholding adaptiv

n=45 si C=3

Tresholding Otsu

APIM8 - 35

Metode bazate pe regiuni • determina regiunile conectate pe baza unor

similaritati ale pixelilor continute in ele

• obiectivul – obtinerea unor regiuni cat mai mari

posibile

• daca cerinta este ca pixelii dintr-o regiune sa fie

prea similari -> suprasegmentarea

• daca se admite o flexibilitate mai mare ->

unirea unor obiecte care ar trebui sa fie separate

APIM8 - 36

Extinderea regiunilor • este o procedura de jos in sus (bottom-up)

• se incepe cu niste pixeli “seminte” si se extinde

regiunea prin adaugarea pixelilor din vecinatate

care au proprietati similare cu samanta

• conectivitatea (4 sau 8 in 2D) -> definirea

pixelilor vecini

• proprietate: variatia intensitatii

APIM8 - 37

Exemplu

Original Variatie 100 Variatie 50

APIM8 - 38

Exemplu

Original Variatie 200 Variatie 150

APIM8 - 39

Extinderea regiunilor (2) • inceperea cu o singura samanta si extinderea

completa a regiunii inainte de a extinde si alte

seminte -> favorizeaza regiunea extinsa prima

• dezavantaje:

– prima regiune extinsa domina procesul de

extindere -> ambiguitatile legate de laturile

regiunile adiacente nu pot fi tratate corect

– diferite seminte -> diferite segmentari

– apar probleme daca samanata se afla pe latura

APIM8 - 40

Extinderea regiunilor (3) • solutie = alegerea aleatoare a unor puncte din

imagine ca seminte si extinderea simultana a

regiunilor

• unirea regiunilor cu proprietati similare, dar

dezvoltate din seminte diferite

• utilizarea metodei:

– in imagini cu zgomot unde laturile sunt dificil

de detectat

– in imagini multimodale

APIM8 - 41

Exemplu

Segmentare utilizand 7 seminte

APIM8 - 42

Metode bazate pe frontiere • se bazeaza pe gasirea diferentelor dintre pixeli

• obiectivul – determinarea unui contur inchis

astfel incat atat interiorul (obiectul) cat si

exteriorul (fundalul) sa poata fi definit

• metode:

– detectarea si conectarea laturilor

– trasarea frontierei

APIM8 - 43

Detectarea si conectarea laturilor • detectarea laturilor se face utilizand un operator

gradient (de ex. operatorul Sobel)

• se face un tresholding pe baza modulului

gradientului

• laturile evidente sunt distincte, dar cele mai

putin evidente apar cu discontinuitati

• imaginile cu zgomot -> laturi parazite -> se

face o netezire inainte (dezav.: laturile se

ingroasa, cele mai putin evidente dispar)

APIM8 - 44

Exemplu

original dupa tresholding dupa aplicarea op.

Sobel

APIM8 - 45

Exemplu

Original (cu

zgomot) dupa tresholding dupa aplicarea op.

Sobel

APIM8 - 46

Exemplu

dupa aplicarea

filtrului Butterworth dupa tresholding dupa aplicarea op.

Sobel

APIM8 - 47

Detectarea si conectarea laturilor (2) • se impune conectarea laturilor pentru a avea o

frontiera continua

• laturile alaturate trebuie unite daca au proprietati similare (de ex. acelasi modul al gradientului si aceeasi orientare):

• necesitatea unor constrangeri asupra pixelilor de legatura

• dupa rezolvarea legaturilor se face o postprocesare pentru a afla seturile de pixeli conectati separati de mici goluri care trebuie umplute

APIM8 - 48

Trasarea frontierei • aplicabila imaginii gradient sau unei imagini

care contine numai informatii despre frontiera

• dupa identificarea unui punct de pe frontiera

(cel de val max. din imagine) se studiaza pixelii

vecini pentru a determina noul pixel al

frontierei

• Trasarea continua cu cautarea pixelului cu cea

mai mare valoare de gri in aceeasi directie ca si

in pasul anterior cu o deviatie maxima de un

pixel

APIM8 - 49

Trasarea frontierei (2)

• necesita verificarea intersectiei cu alte frontiere ->

metoda neadecvata pentru obiecte care se ramnifica

sau se intersecteza cu altele

APIM8 - 50

Modele deformabile parametrice

• contururi active explicite (suprafete active,

snakes)

• in 2D - o curba definita intr-o imagine care isi

schimba locatia si forma pana cand satisface cel

mai bine conditiile predefinite

• in 3D – o suprafata definita intr-o imagine 3D

care isi schimba locatia si forma pana cand

satisface cel mai bine conditiile predefinite

APIM8 - 51

Contururi active (1)

• in 2D - o curba parametrizata C(s)=(x(s),y(s))

unde s [ 0, 1]

• C(0) este punctul de start al frontierei si C(1)

este punctul final

• conturul actioneaza ca o banda elastica care isi

schimba forma sub presiunea

– diferitelor trasaturi locale ale imaginii

– constrangerilor bazate pe forma

– constrangerilor impuse de utilizator

APIM8 - 52

Contururi active (2)

• deformarea conturului (miscarea) -> proces de

minimizare a energiei (analogie cu sistemele

fizice)

E = Eint + Eext

• energia interna – constrangerile bazate pe

forma (de ex.: lungimea conturului, curbura lui)

• energia externa - trasaturile locale ale imaginii

si constrangerile definite de utilizator

APIM8 - 53

Contururi active (3) • Energia:

E = Eint + Eext + Ec

• Ec = energia datorata constrangerilor suplimentare

impuse:

- penalitati pentru formarea buclelor in contur

- penalitati pentru indepartarea fata de pozitia initiala

- penalitati pentru mutarea intr-o zona nepermisa a

imaginii

APIM8 - 54

Energia interna (1)

• constantele determina influenta fiecarui termen:

– elasticitatea conturului activ <- c1 ( daca este zero

-> conturul poate fi intins la infinit, termenul nu

conteaza in cadrul energiei; daca e prea mare ->

elasticitate mica)

– indoirea conturului <- c2 (rigiditatea conturului)

APIM8 - 55

Energia interna (2)

• extinderea analogiei fizice -> modificarea conturului

sub actiunea unor forte care tind sa-i minimizeze

energia

• fortele corespunzatoare sunt:

• aceste forte imping punctul inspre cei doi vecini ai

sai

N

i

iidKE1

2

1,int )(

APIM8 - 56

Energia interna (3) • deplasarea conturului in noua pozitie:

unde C este o constanta definita de utilizator

(deplasarea pentru o forta data)

• 20 de iteratii ale conturului

APIM8 - 57

Energia externa (1)

• c3 -> influenta fortei de atractie a laturilor

• de ex.: migrarea spre zone deschise la culoare

atunci fortele sunt:

N

i

iext PkE1

APIM8 - 58

Energia externa (2) • forta actioneaza in directia gradientului nivelului

de gri

• Ex.: intr-o imagine rampa->contur -> dupa 20 de

iteratii

• Pentru evitarea efectului structurii locale ->

utilizarea unui gradient mai complex

APIM8 - 59

Contururi active

• conturul uzual implementat prin functii spline

• optimizarea -> rezolvarea numerica a formei

Euler-Lagrange a energiei functionale E:

APIM8 - 60

Exemplu

APIM8 - 61

Exemplu • este important conturul initial -> cat mai

aproape de cel final -> numar mic de iteratii

• metoda semi-automata

APIM8 - 62

Imbunatatirea algoritmului

• o forta de extensie (contur initial prea departe de

cel final)

• posibilitatea de a se diviza in contururi separate

• abilitatea de a creste (de a insera puncte de

control)

• criterii suplimentare regionale (de ex. impunerea

unei variante minime a nivelului de gri – zona

omogena)

APIM8 - 63

Modele deformabile geometrice (1)

• colectie de izofote -> descrierea imaginii

• un contur implicit poate fi o izofota

APIM8 - 64

Modele deformabile geometrice (2)

• conturul implicit poate fi o izofota -> evolutia

conturului implicit implica evolutia imaginii

• de ex.: conturul dat de izofota 100 -> dupa

procesarea imaginii ne intereseaza izofota 100

• se pot utiliza si alte curbe definite in termenii

geometriei imaginii

APIM8 - 65

Modele deformabile geometrice (3)

• conturul implicit C cu parametrul s atunci

derivata in raport cu timpul ne da evolutia

curbei

• descompunerea deplasarii in lungul curbei sau

normal pe curba

APIM8 - 66

Modele deformabile geometrice (4)

• evolutia conturului transpusa in evolutia imaginii

• argumentele lui β’ trebuie translatate in argumentele

in forma imaginii

• un arg. des intalnit este k curbura izofotei care se

transpune in evolutia imaginii in

APIM8 - 67

Modele deformabile geometrice (5) • alte argumente utilizate:

• des utilizata este si

care se transpune

conturul este atras spre laturi si segmentarea se poate

face aplicand o valoare de prag

APIM8 - 68

Modele deformabile geometrice (6)

• mai putine restrictii topologice (permite

inclusiv separarea in mai multe conturi)

• permite evolutia mai multor contururi simultan

• aplicarea directa in 3D

APIM8 - 69

Exemplu

APIM8 - 70

Exemplu

APIM8 - 71

Segmentarea Watershed • separarea automata a obiectelor care se ating

dintr-o imagine segmentata

• imaginea distantelor este binarizata folosind o

valoare de prag suficient de mare ca obiectele

sa fie separate

• metoda functioneaza bine pe imagini cu obiecte

convexe netede care nu se suprapun prea mult

APIM8 - 72

Exemplu

imaginea binara

tresholding

harta distantelor

APIM8 - 73

Segmentarea Watershed (2)

APIM8 - 74

Exemplu

original dupa inversiune dupa tresholding

Otsu

APIM8 - 75

Exemplu

liniile watershed

suprapusa peste

imaginea binarizata

dupa transformata

distanta

APIM8 - 76

Exemplu

liniile watershed

suprapusa peste imaginea

originala ->SKIZ

dupa transformarea

distantei

APIM8 - 77

Exemplu

gradientul

morfologic

imaginea binara

APIM8 - 78

Exemplu

liniile watershed

suprapusa peste

imaginea originala

liniile watershed

suprapuse peste

imaginea gradient

APIM8 - 79

Segmentarea Watershed (3) • Apare suprasegmentarea datorita zgomotului si

a iregularitatilor locale

• Se aplica initial o operatie de netezire

• Un pas de postprocesare ce consta in unirea

regiunilor pe baza similaritatilor

• Se utilizeaza inundarea pe baza unui set de

markeri predefinit

APIM8 - 80

Exemplu

transformarea

watershed asupra

gradientului

imaginea binara

APIM8 - 81

Exemplu

transformarea

watershed

controlata prin

markeri

imaginea cu markeri