Curs Sva Aio

Sisteme de percepie naturale identificarea i localizarea obiectelor

nconjurtoare prelucrarea unei cantiti imense de informaii abiliti nnscute eliminarea informaiilor

redundante

Cap. 1 Introducere

Captarea i procesarea primar a informaiilor vizuale Recunoaterea entitilor prezentate n imagine Determinarea relaiilor spaiale pentru obiectele din

imagine

Elaborarea unui SVA SVA dedicate ghidarea i poziionarea manipulatoarelor inspectarea calitii suprafeelor recunoaterea i localizarea obiectelor: montaj recunoaterea caracterelor analiza imaginilor tomografice: medicina determinarea caracteristicilor 3D ale obiectelor din imagini 2D

1.1 Sarcinile unui SVA

Cap. 1 Introducere

1.1 Sarcinile unui SVA

nx

x

x1

clasificare

achiziie ipreprocesare segmentare descriere recunoatere interpretare

CameraTV

controlerrobot

Brarobot

Cap. 1 Introducere

SVA descrierea simbolica a unei imagini

Etape: achiziia imaginii preprocesarea segmentarea descrierea recunoaterea

formelor interpretarea

Fig. 1. Diagrama recunoaterii unei scene industriale

1.2 Aplicatii si domenii conexe

Cap. 1 Introducere

Procesarea imaginilor imagini noi superioare calitativ

Recunoaterea formelor - clasificarea unui obiect (forma)- evaluarea gradului de similaritate

Analiza scenelor linii, sup. sau poliedreinterpretarea imaginii

Grafica asistat de calculator descriere nepictural

imagine iconic

1.2 Aplicatii si domenii conexe

Aplicatii:

Cap. 1 Introducere

Domeniu Aplicaii Problematica

Comunicaii - Sortarea corespondenei- Procesare doc. bancare

Recunoatereacaracterelor

Medicina - Detecia tumorilor- Analiza cromozomilor

Analiza imaginiimedicale

RoboticaCIM

- Inspecia suprafeelor- Asamblare- Roboi autonomi

Recunoatereaobiectelor, analizascenelor 3D

Cartografie,meteo

- Elaborare hri- Analiza imagini aeriene

Procesareaimaginii

Militar - Detecie inte- Ghidare rachete

Analiza imagine +recunoatere

1.3 Tipuri de imagini i de prelucrri

Cap. 1 Introducere

Relatii intre imaginea initiala si modele anterior construite

Reprezentari intermediarea prin categorii de imagini:

Imagini generalizate: captare imagini picturale Imagini segmentate: gruparea regiunilor asociate

obiectelor Reprezentri geometrice: forme 2D sau 3D

- primitive geom. Modele relaionale: descriere bazata pe el. primitive

- grafuri

1.3 Tipuri de imagini i de prelucrri

Cap. 1 Introducere

Prelucrri efectuate de SVA

Operaii de preprocesare: filtrare, extragere muchii, colturi Operaii de etichetare: zone din imagine cu un anumit grad de

uniformitate Operaii de grupare: pt. pixelii etichetati => structuri Extragerea trasturilor: proprietati geometrice, topologice,

cromatice etc. Determinarea corespondentelor: asocieri intre trasaturi si un

model

Bibliografie1. Sonka M., Hlavac V. and Boyle R.: Image processing,

Analysis and Machine Vision, Published by PWS,1998. (http://www.icaen.uiowa.edu/~dip/LECTURE/lecture.html)

2. Gonzalez R.C. and Woods R.E., Digital ImageProcessing, Second Edition, Prentice Hall, 2002.

3. Gonzalez R.C., Woods R.E. and Eddins S.L., DigitalImage Processing Using Matlab, Prentice Hall, 2004.

4. Shapiro, L.G. and G.C. Stockman: Computer Vision,Upper Saddle River, NJ: Prentice-Hall, 2001.

5. D. Forsythe and J. Ponce: Computer Vision: A modernapproach. Prentice Hall, 2003.

6. Bulea M.: Prelucrarea imaginilor si recunoastereaformelor, Teorie si aplicatii, Ed. Academiei Romane,Bucuresti, 2003

Cap. 1 Introducere

Senzor (camera): intensitatea radiatiei reflectate semnal electric

Radiatii: lumina naturala, raze X, laser, ultrasunete, radiatii infrarosii

Imaginea: un senzor percepe radiatia care a interactionat cu obiecte fizice

Modele matematice- functia imagine: abstractizarea fundamentala

- modelul geometric: proiectia sistemului 3D intr-unul 2D

- modelul radiometric: radiatia masurata de senzor

- modelul frecventelor spatiale: variatii spatiale transformari

- modelul culorii: masurari spectrale corelate cu imagini color

- modelul digitizarii: obtinerea imaginilor digitale

Cap. 2. Formarea imaginii

Imagine: captata cu o camera Modelare printr-o functie continua: f(x,y) sau f(x,y,t) f (x,y) = stralucirea in punctul de coord. (x,y)

= alte marimi fizice: temp., distrib. presiunii,distante

f(i,j) = functie discreta cu i,j numere intregi Imagine monocromatica: f (x,y) => nivelul de gri Imagine color (multispectrala): functie vectoriala

),(),,(),,(),( yxfyxfyxfyx BGRf

2.1. Functia imagine (FI)


Imaginea monoculara Lumea reala (3D): camera imagine (2D) Imaginea 2D = proiectia perspectiva a unei scene 3D Modelul dispozitivelor de captare: proiectia fiecarui punct 3D

prin centrul proiectiei (sau centrul lentilei) pe planul imaginii

2.2. Modelul geometric


(pinhole orificiu infinitezimal)Fig. 2.2.1 Obtinerea imaginii

Ecuatia proiectiei perspective

( , , ) ( ' , ' )x yx y z f fz z

Se ignora a treia coordonata:- OC axa optica; C centrul imaginii


' ' ' '

' ' '' ' ', , ' : ' '' ''

P z fxx x x fx y z zP O P coliniare OP OP y yyx y z y fz zz

Fig. 2.2.2 Proiectia perspectiva

Pinhole-efectul dimensiunii finite => lentileDimensiunea orificiului:- prea mare: mai multe directii

mediate efect de ceata- prea mica: difractie efect de ceata


Fig. 2.2.3 a) Efectul dimensiunii finite; b) necesitatea lentilei

Refractia paraxialaCap. 2. Formarea imaginii

Lentila sferica de raza R: indici de refractie => n1 si n2

1 11

1 1 2 2

2 22

1 2 2 11 1 2 2 1 1 2 2

1 2

1 1

1 1

sin sin

hR d

hR d

n n n nn n n nd d R

Fig. 2.2.4 Refractia paraxiala

Ecuatia refractiei paraxiale

Lentila subtire formarea imaginiiCap. 2. Formarea imaginii

Lentila subtire: - raza refractata de frontiera (dr) => imediat refractata de frontiera (st)- n indicele de refractie al lentilei- lentila inconjurata de aer (indice de refractie unitar)

0 10 1

0 01 0

1 0

1 1( )1 1 1

1 1 '( ) ''

2( 1)

n nr refractie dr rz z Rn n z z fr refractie st rz z R

Runde fn

Fig. 2.2.5 Formarea imaginii

Lentila subtireCap. 2. Formarea imaginii

0

0 0

0

0 0

1

' '' ' 1 1 1 asemenea (Fig.2.2.5) 1' ' '

''

z zy zh z z

z zy zh z z z z f

y yz z

Ecuatialentilei subtiri

f = > distanta focala

F si F => focare

z = f => proiectia perspectiva

Fig. 2.2.6 Lentila subtire formarea imaginii

Modelarea matematica: nivelul de iluminare al unui punct dinimagine

depinde de: - strulucirea (luminanta) scenei- proprietatile intrinseci ale suprafetei obiectelor- orientarea obiectelor- caracteristicile senzorului

Lumina = radiatia electromagnetica vizibila

(lungimea de unda) = {350nm(violet), 780nm(rosu)}


2.3 Modelul radiometric


A: apropiat; B: indepartat; C: foarte indepartat315

vizibil

1nm 100nm 280 350nm

780nm

1 1.4 3m 10m 100m 1mmRaze X MicroundeUltraviolet C B A A B C Infrarosu

Fig. 2.3.1 Pozitia spectrului vizibil

Fotometria: masurarea energiei radiante + efecte produse


Radiatia vizibila: caracterizare energetica

e = fluxul energetic luminos energia radianta emisa/primitade un corp in unit. de timp: distributia neuniforma in raport cu

: densitatea spectrala a fluxului luminos

: fluxul energetic luminos emis/primit (1 2)21

( ) [ / ]

( ) [ ]

( ) . lumina alba: toate lungimile de unda au ac. energie

e

e

dW m

d

d W

ct


Radiatia vizibila: capacitatea de a produce senzatia de lumina

Capacitatea fluxului energetic luminos de a produce senzatia delumina: = fluxul luminos [lm] (lumenul)

Actiunea luminoasa intr-o anumita directie: intensitatea luminoasa

Efectul fluxului luminos incident la o suprafata: iluminarea

(candela)][cdddI

)luxul(]lx[dAd

E


Luminanta (stralucirea) intr-un punct al suprafetei unei surse

cossau]cd/m[

cos

22

dAddL

dAdIL

dA

proiectia el. desuprafata dA

directia considerataN

I

Fig. 2.3.2 Stralucirea intr-un punct al unei suprafeteintr-o directie data


f0 fp

DLentila

0

Obiect

irdA0

P

Planimagine

dAp

N

Fig. 2.3.3 Geometria sistemului de formare a imaginii

L - stralucirea (luminanta) obiectuluiEp - iluminarea imaginii

Sursa punctiformade lumina

Captarea radiatiei emise de suprafata unui obiect


d

N

A

Definitia unghiului solid =>

20 0cos cosp p

p p p

dA Ld fdE E LddA dA f

Domeniul de integrare: unghiul solid sub care se vede lentila (D) din P

20

32

2

0 cos44

cos

fDdDA

fd

- unghiurile solide egale din O pt. dA0, dAp =>

qi =qr =q iluminarea el. dAp =>

2cosAd

02 2

0

coscos p

p

dAdA

f f


Pentru L = ct. pe domeniu de integrare

Iluminarea observata in imagine Ep = stralucirea unui punct dinimagine (nivelul de gri)

- luminanta (stralucirea) L a scenei

- caract. senzorului : neliniar

- amplasarea obiectului ()

24cos

4p p

DE Lf

fD


2.4. Modelul imaginii bazat pe frecvente spatiale

FI Domeniul frecventelor spatiale (u, v): analizavariatiilor spatiale

Transf.Fourier

inversaTF),(),(

directaTF),(),(

)(2

)(2

dudvevuFyxf

dxdyeyxfvuF

yvxuj

yvxuj

u,v = frecvente spatialeFrecvente spatiale joase variatii lente ale nivelurilor de gri

~ (variatia intensitatii unei suprafetecontinue)

Frecvente spatiale inalte variatii rapide: ex. = muchii

2.5. Imagini color


Culoarea = proprietatea de a reflecta undele electromag. cu diferitImagine color : divizare in benzi spectrale si captare separataCaptarea imaginii: senzori sensibili la o anumita banda ()La iesirea unui senzor:

: distrib. energetica a sursei de lumina: sensibilitatea senzorului

(functie vectoriala)

0 )(),,,(),,(:FI dStyxCtyxf

),,(...,),,,(),,,(),,(:FI)(

),,,(

21 tyxftyxftyxftyx

S

tyxC

nf

Benzile de lungimi de unda aplicatiisatelitul LANDSAT 4 5 benzi spectrale (ultraviolet A infrarosu)televiziunea color 3 benzi: rosu - 700nm (R);

verde - 546.1 nm (G);albastru - 435.8 nm (B)


Detectia culorilor cu ochiul uman

3 categorii de conuri pentrulungimi de unda:

- scurte (S)- medii (M)- lungi (L)

Asocieri posibile:

- S => B (blue)- M => G (green)- L => R (red)

Fig. 2.5.1 Sensitivitatea conurilor

Sistemul RGB (tricromatic)


, , 1R G Br g b r g bR G B R G B R G B

Codarea unei culori arbitrare in spectrul vizibil: culorile primare RGB

Normalizarea culorilor primare:

Fig. 2.5.2 Cubul culorilor Fig. 2.5.3 Triunghiul culorilorSectiune prin:

=> (1,0,0),(0,1,0),(0,0,1) =>b = 1- r - g


Intensitatea: I = R + G + B

Nuanta: ~ valoarea medie a

lungimii de unda

a culorii

Saturatia: : lipsa albului din culoare

HHtunciGBDacaBGBRGR

BRGRH

2:a

21

arccos2/12

IBGR

S),,min(3

1

Sistemul HSI (HSV)

Cromatica: fara informatii despre intensitate si stralucirePerceptia culorilor: sistemul RGB sistemul HSI (HSV)

- intensitate => I (sau V valoare)- cromatica => nuanta H (hue)

saturatie S (saturation)


RGB (cubul culorii) => HSI (hexaconul culorii) proiectia cubului RGB (fig. 2.5.2) perpendiculara pe diagonala (0,0,0), (1,1,1)

- 2D => hexagon;- 3D => hexacon => I axa verticala (diagonala cubului)

=> H unghi cu: R => 0; G => 2/3; B => 4/3=> S a treia coordonata (lipsa albului din culoare)

Fig. 2.5.4 a) Hexagonul culorii; b) hexaconul culorii


2.6. Digitizarea imaginii

Imaginea digitizata structura discreta de date = matriceesantionarea la intervale spatiale regulate

Digitizarea imaginiicuantizarea stralucirii fiecarui esantion

numarul intreg de niveluri de grix, y: intervale de esantionare

xy

x

yFig. 2.6.1 Grila deesantionare ideala ),(periodica:),(

),(),(

),(),(

1 1

digitizare

yxyxS

yjyxixyxS

yjxifyxfM

i

N

j


Imaginea esantionata:

2

2

2

2 0termen0,0

2

2

1 1

1 1

),(1

)},({

),(),(

),(),(),(),(),(

x

x

y

y

ji

i j

yny

xmx

j

mn

m n

yny

xmx

j

mn

M

i

N

j

M

i

N

js

dxdyeyjyxixyx

a

eayxS

yjyxixyxf

yjyxixyxfyxSyxfyxf

FS(x,y) descomp.Fourier


i js

m n

yny

xmx

js

x

x

y

y

yny

xmxj

mn

yjv

xiuF

yxvuF

eyx

yxfyxf

yxdxdyeyx

yxa

,1),(

1),(),(

1),(1

2

2

2

2

2

2


( , ) ( , ) 0 pentru ,f x y F u v u U v V Teorema esantionarii

uU

v V

F(u,v)

u

v 1/x

1/y Fs(u,v)

Fig. 2.6.2. a) Spectrul imaginii originale;b)Spectrul imaginii esantionate

a) b)

Intervalele de esantionare jumatatea celui mai micdetaliu din imagine

1 1,2 2

x yU V


Digitizarea reala:- grila cu impulsuri foarte inguste de aplitudinelimitata hs(x, y)

- senzorii dispozitivelor de captare

yjv

xiuH

yjv

xiuF

yxvuF

yjyxixhyxfyxf

s

M

i

N

js

M

i

N

jss

,,1),(

),(),(),(

1 1

1 1

convolutie distorsiuni intervale de esantionare /10

Fig. 2.6.3. Grila patrata; hexagonala

pixel picture elementk interval de cuantizareb - biti: k = 2b (b = 8)b = 1 imagine binara


Influenta dimensiunii grilei de discretizare


Reprezentarea imaginii digitaleImagine digitala: M linii si N coloane => reprezentare matriceala

f(1,1) f(1,2) f(1,N)

f(2,1) f(2,2) f(2,N)

f(M,1) f(M,2) f(M, N)

1 2 N x

1

2

M

y


Relatii de baza intre pixeli

Distantaa) reflexivitateb) simetriec)

tranzitivitate

- euclidiana- city block- chessboard

d4, d 8 = numarul de pasi efectuati pe grila de la punctul de startla cel final

212122118

212122114

221

2212211

331133222211

11222211

21212211

,max),(),,(

),(),,(

)()(),(),,(

),(),,(),(),,(),(),,(),(),,(),(),,(

,0),(),,(

yyxxyxyxd

yyxxyxyxd

yyxxyxyxd

yxyxdyxyxdyxyxdyxyxdyxyxd

yyxxyxyxd

E


Vecinatatea unui pixel

d 4 = 1 V4

d8 = 1 V8

V4 vecinatate tetraconectata

V8 vecinatate octoconectata

p(i,j) => V4(p): (i+1,j), (i-1,j), (i,j+1), (i,j-1)

p(i,j) => V8(p): (i+1,j), (i-1,j), (i,j+1), (i,j-1),(i+1,j+1),(i+1,j-1),(i-1,j+1),(i-1,j-1)

- P Q A1, A2,, An cu A1= P, An= Q si Ai+1 adiacent cu Ai- traiectorie (cale) simpla fara pixeli care se repeta, un pixel are

cel mult doi vecini- traiectorie (cale) inchisa traiectorie simpla: primul pixel vecin

al ultimului pixel (A1= An)- S => submultime de pixeli dintr-o imagine


Conectare, adiacenta

traiectoriecale

2 pixeli p si q sunt conectati => - sunt vecini- nivelurile de gri sunt similare (apartin multimii G)

adiacenta pixeli tetraconectati => pixeli octoconectati =>

4

8

, , ( ), , ( )

p q G q V pp q G q V p

, , , daca o cale intre ei cu pixeli dinp q S p q conectati S

Regiune = multime de pixeli conectati (R) exista o traiectorie intre oricepereche de pixeli

Frontiera (conturul) unei regiuni R = multimea pixelilor care apartin lui R si au celputin un vecin in afara lui R

Ri: regiuni disjuncte dintr-o imagine + nu ating limitele imaginii

Rc: multimea complementara a regiunii R in raport cu imaginea

Rc conectata cu limitele imag. = fundalrestul neconectat = gauri

Regiunei

iR R


Regiune, frontiera

Regiuni: cu gauri => simplu conectatafara gauri => multiplu conectata

Regiuni obiecte din scenaGasirea regiunilor din imagini care sunt obiecte = segmentare

Nivelul de gri gasirea obiectelor prag > prag: obiect +conectivitate

< prag + puncte ale obiectului = gaura< prag + puncte ale obiectului + celelalte puncte = fundal


Muchia = prop. unui pixel => vector (magnitudine, directie)grad f(x, y) intr-o vecinatate > prag

magnitudinea => modulul gradientuluidirectia => pe directia grad. orientata dupa

cresterea functiei imagine

Muchii crack


Muchia

Grila patrata paradoxuri

Fig. 2.6.5. Paradoxul curbei inchise


Remediu: pixelii obiectului tetraconectati sipixelii fundalului octoconectati

Fig. 2.7.1 Reflectarea radiatiei primita de la o singura sursade iluminare


2.7 Dispozitive de captare


Fig. 2.7.2 Camera CCD: Charge-Coupled Device

Celule discrete ce convertesc energia luminoasa in sarcini electrice


Fig. 2.7.3 Rolul frame buffer-ului in procesarea imaginii

Frame grabber: memorie de imagineComunicatie digitala directa: standard IEEE 1394

Cap. 3. Preprocesarea imaginilor

Preprocesare: - imbunatatirea imaginii

- evidentierea trasaturilor: muchii si colturi

transformri ale nivelului de gri

Metode de preprocesare transformri geometrice

preprocesri locale

refacerea imaginii

3.1. Transformri ale nivelului de gri

corectarea nivelului de gri (depinde de poziie)Metode

modificarea scalei nivelurilor de gri


3.1.1. Corectarea nivelului de gri

Ideal: sensibilitatea dispozitivelor de achizitie nu depinde de pozitia obiectului in imagine

Distorsiuni: lentile, fotodetectorul senzorului, iluminarea corecia nivelului de gri

e(x, y): coeficientul multiplicativ al erorii

g(x, y): imaginea original nedistorsionata

f(x, y): imaginea cu distorsiuni

Determinarea coeficientului multiplicativ al erorii: imagine de referinta cunoscuta

g(x, y): imagine de referinta cu acelai nivel de gri (c)

fc(x, y): imagine cu distorsiuni

),(),(),( yxgyxeyxf

cyxfyxe c ),(),(


3.1.2. Transformarea scalei nivelului de gri

Transformari ale nivelului de gri

(a) : negativ

(b) : contrast

(p1, p2)

(c) : alb/negru

Fig. 3.1.1. Transformri ale scaleinivelului de gri


)(,, 00 pTqqqqppp kT

k

)( 00

00 pppp

qqqq

k

k

kpppppqpppppqpppp

q

222

2111

10

)()(

pk

p

pppq

pppqq

0

00

(c)q

(b)

(a)

q kq 2

q 1

q 0pp2pp p1p0 pk

Fig. 3.1.2. Histograma unei imagini

H(p)

p

Modificarea histogrameiHistograma = frecvena de apariie a unui anumit nivel de gri p (H(p))

pjifjiCardpHNj

Mi

),(|),()(

,1,1

Histograma un maxim n domeniul frecvenelor joase

detaliile caracterizate prin niveluri de gri joase

nu sunt perceptibile

Modificarea histogramei (cresterea contrastului)- forma prestabilita: constanta exponeniala hiperbola etc


Fig. 3.1.3. Egalizarea histogramei

Egalizarea histogrameiImaginea iniial: NM ; k niveluri de gri: kppp ,,, 21 Pe fiecare nivel: ni pixeli MNn

k

ii

1

Imaginea final: l niveluri de gri cu mi pixeli/nivel )(;1

klMNml

ii

11

11

1

1

1121 ,,,

k

ii

k

iik nmnqppp

indexul k2

22

121

1

1

k

ii

k

ii nmmn

nivelul q2 - o parte din pixeli cu nivelul 1kp

- pixeli cu nivelul: 11 21 ,, kk pp - o parte din pixeli cu nivel 2kp

Procedura continu pentru toate nivelurile de gri.

H(p)

p

qq1 ql

pkHe(q)


Modificarea histogramei transformarea punctual:kiljij pTq

,,1,,1)(

(*)

Aplicaii Imaginea iniial + histograma doritTHistograma imagii iniiale + T histograma mbuntit

Histograma = funcie de densitate de probabilitate discret (variabila aleatoare = nivelul de gri)

(*)

k

ii

l

jje pHqH

11)()( funcii de distribuii discrete

He: funcia de densitate probabilistic uniform1qq

MNfl

He ideal: cazul continuu al funciei de densitate probabilistic uniform

pp

eppe

qq e

qdssHMN

qqpTqdssH

qqqq

MNdsqq

MN111 1

1

1

1

1)()()(

1: histogram cumulativ

Aproximare discret:

p

pi

e iHMN

qqqpTq

1

)()( 11

Netezirea histogramei iniialeH(p)

k

kiipH

kpH )(

121

)(' ; k - vecintate


Imagini ale aceleiasi scene cu diferite nivele de iluminare: a,b,c

Imagine prelucrata: contrast marit: d

a) c)

b) d)

Cap. 3. Procesarea imaginilor

3.2. Transformri geometrice

Eliminarea distorsiunilor geometrice ce apar la achizitie

Compararea imaginilor diferite pentru acelai obiect

Transformarea geometric funcia vectorial T:(x, y) (x,y))','('),,(' yxTyyxTx yx

Tx, Ty: rotaii,translaii, scalri, etc.

Transformare geometrica doi pai: transf. coordonatelor pixelilor din imaginea original nr. reale gsirea punctului de pe gril i calculul nivelului de gri prin interpolare

T-1

T

Fig. 3.2.1. Transformarea geometric a unui plan


3.2.1. Transformarea coordonatelor unui pixel

relaii polinomiale

m

r

rm

k

krrk

m

r

rm

k

krrk yxbyyxax

0 00 0','

Transformare liniar n raport cu ark, brk perechi de puncte corespondente (x, y), (x', y')

m = 2 sau 3, 6 10 perechi de puncte

Transformarea

biliniar xybybxbbyxyayaxaax

3210

3210''

: 4 perechi de puncte

Transformarea

afin ybxbbyyaxaax

210

210''

: 3 perechi de puncte

: rotaia, translaia, scalarea i nclinarea


Transformare aplicata imaginii schimbarea sistemului de coordonate Jacobianul J

yy

yx

xy

xx

yxyx

J

''

''

),()','(

:

10

JJ

aria imaginilor invariant la transformri

Transformare biliniar: ybabaxbabababaJ )()( 322313311221

T r a n sf o r m a r ea a f i n : 1221 babaJ

Transformri:

- nclinarea cu unghiul pe direcia y

yyJyxx

'1;tg'

- scalarea cu a pe x i b pe y:

byyabJaxx

';'

nu inversa transformatei


rotaia cu unghiul:

cossinsincos)sin('

sinsincoscos)cos('

yx

yx

y

x

cossin'1;sincos'

yxyJyxx

y

x

y

x

(x, y)(x, y)

Fig. 3.2.2. Rotaia cu unghiul

- translaia cu a pe x i b pe y:

byyJaxx

'1;'


(a) (b) (c)

(d) (e)Fig. 3.2.3. Tipuri de distorsiuni (captarea imag. de la distanta

(a) distorsiunea panoramic (scanare liniare cu vitez const. de rotire a oglinzii)

(b) distorsiunea neliniar (distane neegale ale obiectului fa de oglinda scanerului)

(c) distorsiunea de nclinare (scanare mecanic la prelucrarea imaginilor din satelit)

(d) distorsiunea de scalare (schimbarea distanei obiectului fa de senzor)

(e) distorsiunea de perspectiv (proiecie de perspectiv)


Imaginea initiala: a Imaginea inclinata dupa axa Oy: c

Imagine rotita cu 45 grade: b Transformare geometrica de tip proiectie: d

a)c)

b) d)


3.2.2. Interpolarea nivelurilor de gri

),(),( yxTyyxTx yx nu rezult numere ntregi poziia nou nu se suprapune peste

grila imaginii noi interpolarea nivelului de gri vecinul cel mai apropiat (a)

liniar (b)

bicubic (c)

Problema interpolrii se exprim n mod dual

Se determin nivelul de gri al pixelului din imaginea original ce corespunde pixelului

din a doua imagine

),(),( 1 yxTyx nu rezult coordonate ntregi: (x, y) nr. reale; (x, y) nr. ntregi

Imaginea iniial f(x, y) valori cunoscute: ),( ykxlfs

l knsn ykyxlxhykxlfyxf ),(),(),(:eaInterpolar

321)(,)(,)(: cban ; hn: nucleul interpolrii (vecintate redus)


hs

x1-1

1D

h3

x1-1

1D

2-2

plrie mexican

Interpolarea (a)

(x, y): nivelul de gri al celui mai apropiat vecin

5.0regint)int(

)int(),int(),(1

xx

yxfyxf s

Interpolarea (b)

(x, y): nivelul de gri = combinaie liniar (4 pixeli vecini)

kybyklxaxlklabfklfab

klfbaklfbayxf

ss

ss

),int(;),int()1,1()1,()1(),1()1(),()1)(1(),(2

Interpolarea (c)

(x, y): nivelul de gri = aprox. local cu o suprafa bicubic

(8 pixeli vecini)

Nucleul 1D;

restin0

21584

102132

32

3 xxxx

xxx

h

grila II mapat de T-1 n imaginea originalgrila discret a imaginii originale

h1

x0 0.5-0.5

1D


3.3. Preprocesarea local

Preprocesare local = filtrarea pe o vecintate V a unui pixel

- netezire: eliminarea zgomotelor

- operatori gradient: depistarea poriunilor cu variaii mari

ale funciei imagine intr-o directie => muchii

- detectoare de colturi: depistarea poriunilor cu variaii

mari ale funciei imagine in ambele directii (x si y)

,( , ) ( , ) ( , )

m n Vg i j h m n f m i n j

: convoluie discret cu nucleul h

h: masc de convoluie

Convoluie discret calculul sumelor ntre produsele dintre funcia imagine i elementele

corespunztoare ale mtii


3.3.1. Netezirea imaginii

Eliminarea zgomotului din imagine medierea nivelului de gri n V cu pastrarea muchiilor

MediereaPixel = zgomot = variabil aleatoare de medie zero i varian

- Se achiziioneaz n imagini statice ale aceleiai scene

Rezultatul medierii:nn

ff nn ...... 11 variabil aleatoare cu medie zero i varian n

n imagini:

n

kk jifn

jig1

),(1),( fr umbrire

- 1 imagine mediere ntr-o vecintate local V = 3 3

121242121

161,

111121111

101centralpixeluluiaaccentuare,

111111111

91 hhh (si V4)

sau 5 5, 7 7 umbrirea (estomparea blur) muchiilor


Mediere cu validitatea datelor limitat = nivelul de gri ntr-un interval predefinit [min, max]

restin0

max][min,),(pentru1),(

jnimfjih

Se evit efectul de umbrire

Medierea cu mti de rotaieEvit umbrirea: se calculeaz nivelul mediu numai pentru partea omogen din vecintatea pixelului curent

n pixeli n R

Rji Rjijif

njif

n ),(

2

),(

2 ,(1

),(1

sau mai usor computational

.),(

),(1

),(),(

2),(1

),(),(),(2),(

1

2

),(

),(

2

2

),(

2

),(

),(

2

),(

2

),(),(22

n

jif

jifnn

jifn

n

jif

jifn

n

jif

n

jifjifjif

n

Rji

Rji

RjiRji

Rji

Rji

RjiRji


Mti de rotaie

8 mti 3 3 ntr-o vecintate 5 5.

1 2 7 8

Algoritmi de netezire cu o masc de rotaie

1o (i, j) pixel al imaginii x

2o se calculeaz 2 pentru mtile 18 din jurul pixelului (i, j)3 o se alege masca cu 2 minim

4 o pixelul (i, j) nivelul de gri f (i, j) obinut cu 3o.


V Netezirea median

Pixelul curent valoarea median dintr-o vecintate V

A[i]i=0..n-1 => multime ordonata de n numere reale

A[(n-1)/2] => valoarea mediana a multimii

Dezavantaje: deteriorarea liniilor subiri i a colurilor ascuite

Forme speciale pentru V:


Filtararea gaussiana- se reduce ponderarea pixelilor odata cu cresterea distantei fata de pixelul central

- pixelul (x,y) va fi ponderat cu:

2 2

222

1( , )2

x y

G x y e


Distributie gaussiana cu media (0,0) si = 1 Aproximarea discreta a gaussianului cu = 1.4

Filtrarea median neliniar

Generalizare: f (i,j): pixelul din imaginea iniial

g(m,n): rezultatul filtrrii

a(i, j) = coeficient de ponderare ct. : filtru izomorfFiltre izomorfe: - media aritmetic u(f) = f

- media armonic u(f) = 1/f- media geometric u(f) = log f


Vji

Vji

jia

jifujiaunmg

),(

),(1),(

),(),(),(

a)

b)

d)

c)

e)

a) imaginea initiala; b) zgomot sare si piperc) filtru mediere 3x3; d) filtru mediere 7x7; e) filtru mediere 15x15

d) si e) => efectul de estompare (blur)


a) imaginea initiala; b) zgomot sare si piperc) filtru gaussian 3x3; d) filtru gaussian 7x7;

a)

c) d)

b)



3.3.2. Detecia muchiilor

Localizeaz variaii abrupte ale nivelului de gri ntr-o imagine

Muchie = proprietatea unui pixel

= variaia funciei imagine ntr-o vecintate

Variabil tip vector = magnitudine i direcie

Variatia funciei imagine gradientul funciei

Magnitudinea = modul gradientului

Direcia = direcia grad. - 90o (: direcia n care funcia imagine are variatia maxim)

Profiluri tipice pentru muchii 1D

f

x

Treapt

f

x

Acoperi

f

x

Linie

f

x

Zgomot

255 alb


Gradientul funciei imagine continue

Detecia muchiei = msura gradientului funciei f de-a lungul lui r n direcia

sincos yx ffry

yf

rx

xf

rf

0max

rf

rf

yf

xf

yf

xfyxfgradM ,arg;),(

22

(arg(x, y): unghiul n rad. dintre axa x i (x, y))

sau:

yf

xfM

yf

xfM ,max:sau,

Operatori de detecie a muchiilor: gradient

compas

0cossin22

max

yx

x

yg

yx

ffrf

ff

arctgff


Magnitudinea muchiei (fr direcie) (Laplacian)

Calculul derivatelor diferene finite

Operatori detectie: - aproximarea derivatelor FI cu diferene finite (gradient, compas) (i)

muchii - trecerile prin zero ale derivatei de ordinul doi (ii)

- punerea n coresponden cu modelele parametrice ale muchiilor (iii)

mti de convoluie

2

2

2

22 ),(),(),(

y

yxf

x

yxfyx

),(),(),(),(),(),(

sau),(),(),(),(),(),(

njifnjifjifjnifjnifjif

njifjifjifjnifjifjif

j

i

j

i


(i) Operatorul compas: calculul gradientului in direciile k = /2+k /4 ),(max),( jiMjiM k

(i-1, j-1) (i, j-1) (i+1, j-1)

(i-1, j) (i, j) (i+1, j)

(i-1, j+1) (i, j+1) (i+1, j+1)

7..0,),(),(),( kjnimfnmhjiMm n

kk

Operatorul Prewitt

011101110

,101101101

,110101

011,

111000111

3210 hhhh

011101110

,101101101

,110101011

,111000111

7654 hhhh

101202101

;210101

012;

121000121

210 hhh

533503533

;553503

333,

555503333

111121111

;111121

111,

111121111

210

210

hhh

hhh


Operatorul Sobel

Operatorul Robinson

Operatorul Kirsch


(i) Operatorul gradient Operatorul Roberts

(i, j) (i+1, j)

21,

21 ji

22 (i, j+1) (i+1, j+1))1,(),1()1,1(),(:Magnitud.

0110

,10

0121

jifjifjifjifM

hh

R

- masc 22: sensibilitate la zgomot

Operatorul Prewitt:

101101101

,111

000111

xy hh

Operatorul Sobel

101202101

,121

000121

xy hh

Magnitudinea i direia:

),(),(

;),(),(),(

);,(),(),();,(),(),(

jiMjiM

arctgjiMjiMjiM

jnimfnmhjiMjnimfnmhjiM

x

yyx

m nyy

m nxx


Operatorul Laplacian

- Se aproximeaz derivata de ordinul 2

pixeli tetraconectai: pixeli octococectai:

- Dezavantaj: rspunde dublu pentru anumite muchii

),(4)1,()1,(),1(),1()(

),()1,(),(),1()(

),(2

),(2

jifjifjifjifjiff

jifjifjifjiff

ji

jjiiji

.111181111

;010141010

hh


Operatorul Prewitt Operatorul SobelOperatorul Roberts


Operatorul Roberts Operatorul Prewitt Operatorul Sobel


(ii) Operatori bazati pe trecerile prin zero ale derivatei de ordinul doi

Operatorul Marr-HildrethTrecerile prin zero ale derivatelor de ordinul II

x

f (x) f (x)

x

f (x)

x ;

Muchie 1D (a)

x

f (x) f (x)

x

f (x)

x

Muchie 1D (b)

Derivata de ordinul II: sensibil la zgomote netezirea imaginii

Filtrul Gaussian 2D

2

22

2

22

22

22

1),(

yxyx

eeyxG

= parametru vecintatea = arc cu R = 3


Operatorul LoG (Laplacian of Gaussian)

),(),,(),(),,( 22 yxfyxGyxfyxG

G2 : independent de imagine se poate calcula analitic dinainte

Substituia

2

2

2

2

2

2

22

2

22

2

2222

11)(;1)(

;)(

rr

r

errGrerG

erGyxr

Revenind la (x, y) i la coeficientul multiplicativ de normalizare c:

Masca de convoluie: 222

22

221),(

yx

eyx

cyxh

.

Locaia n care G2 aplicat imaginii trece prin zero = muchie

Netezire pot s dispar colurile


Masti care aproximeaza operatorul LoGa) 3x3; b) 11x11

a)

b)


Operatorul Canny

Optimal pentru muchii treapt afectate de zgomot alb

Optimalitate trei criterii

(i) criteriul detecie: muchiile importante nu trebuie sa lipseasc i fr rspunsuri false

(ii)criteriul localizrii: distana dintre muchia actual si cea localizat s fie minim

(iii) criteriul un singur rspuns: minimizeaz rspunsurile multiple la o singur muchie

Ideile care stau la baza operatorului Canny

1. Detectorul de muchii semnal 1D i criteriile de optimalitate (i), (ii):

soluia: calcul variaional

2. Dac se adaug criteriul (iii) optimizare numeric

filtrul rezultat ~ derivata filtrului de netezire Gaussian

similar cu detectorul Marr-Hidreth


3. Generalizarea detectorului la 2D:

- se obine o muchie tip treapt cu poziia, orientarea i magnitudinea cunoscute;

operator directional => convolutia imaginii cu gaussianul G si diferentiere indirectia gradientului

- Fie gaussianul 2D:

2

22

2

22

22

22

1),(

yxyx

eeyxG

- Se definete operatorul Gn => prima derivat a lui G n direcia n => GGGn

nn

- Direcia n (perpendiculara pe directia muchiei) nu este cunoscut n avans: pentru o

imagine f netezit gaussian => se estimeaz cu normala la direcia muchiei:

)*()*(

fGfG

n

- Poziia muchiei: maximul local (n direcia n) al operatorului Gn aplicat imaginii f

0*0* 22

fGfGn nn (eliminare non-maximala)


- Convoluia i derivarea sunt asociative

- se calculeaz nti convoluia imaginii f cu Gaussian-ul G

- se calculeaz derivata de ordinul doi folosind o estimare a direciei n

- se calculeaz magnitudinea gradientului: )*(* fgfGn

4. Rspunsuri false: prag pt. detectia muchiei rspunsul operatorului oscileaz apar intreruperi

in contur (streaking) => se introduce prag cu histerezis

- toate rspunsurile obinate cu magnitudinea mai mare dect pragul superior = muchii

- rspunsurile sup pragul superior zgomote; dac sunt conectate cu muchii

se examineaz un prag inferior mai mare dect pragul inferior = muchie

5. Scalarea operatorului: depinde de obiectele din imagine

- diferite scale: valori diferite pentru => cea mai mica scala = cea mai buna pozitionare

- metoda sintezei trsturii (Canny)

a) sunt determinate toate muchiile cu cea mai mic scalare

b) folosind muchiile de la a) sunt sintetizate muchiile unui operator ipotetic cu mai mare

c) se compar muchiile de la b) cu rspunsul unui operator cu mai mare

d) se marcheaza muchiile cu un raspuns mai puternic decat al celor obtinute prin sinteza

e) se repeta procedura pt. o secventa de scalari si se adauga muchiile obtinute la d)


ALGORITM DE IMPLEMENTARE A OPERATORULUI CANNY

1. Se repet paii 2 6 cu valori cresctoare ale lui

2. Se calculeaz convoluia imaginii f cu gaussian-ul G de scal

3. Se estimeaz direciile normale la muchii pentru fiecare pixel

4. Se determin poziia muchiei

5. Se calculeaz magnitudinea muchiei

6. Se elimin rspunsurile false prin utilizarea unui prag cu histerezis

7. Se utilizeaz metoda sinteza trsturii pentru a obine muchiile finale


Detectorul de treceri prin zero Operatorul LoG Operatorul Canny


3.3.3 Detectia colturilor

Muchie => trasatura unidimensionala (variatia functiei imagine intr-o directie)=> reconstitue miscarea numai pe directia perpendiculara pe muchie

Colt => trasatura bidimensionala (variatia functie imagine in ambele directii x si y)=> intersectia a doua sau mai multe muchii=> analiza miscarii in planul imaginii

Detectoare de colturi => calculul unei marimi locale = cornerness

operatorul pentru detectia punctelor de interes (OPI) operatorul Harris operatorul Smith


Operatorul pentru detectia punctelor de interes (OPI)- Punct de interes (Moravec) => punct in care functia imagine

are variatii importante in toate directiile

i=4

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

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

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

x

y

i=3

i=2

i=1

- Se calculeaza varianta vi, i = 1..4

1

2

3

4

( , ) max( ( 1, ) ( , ) , ( 1, ) ( , ) )( , ) max( ( , 1) ( , ) , ( , 1) ( , ) )( , ) max( ( 1, 1) ( , ) , ( 1, 1) ( , ) )( , ) max( ( 1, 1) ( , ) , ( 1, 1) ( , ) )

v x y f x y f x y f x y f x yv x y f x y f x y f x y f x yv x y f x y f x y f x y f x yv x y f x y f x y f x y f x y

, ; min ,f ii

I x y v x y

- Puncte de interes:

Regiune neteda (flat):fara schimbari intoate directiile

Muchie (edge):fara schimbari de-a

lungul muchiei

Colt (corner):importante schimbariin toate directiile


Operatorul Harris


- Colt maximul unei functii de autocorelatie- functia de autocorelatie => variatii locale ale lui f(x,y)

- Variatii locale (x,y) si punctul (x,y) => functia de autocorelatie:

- (i,j) puncte in fereastra w centrata pe (x,y)

- Detectie colturi => integrare dupa toate directiile variatiilor

2( , ) ( , ) ( , ),

g x y f i x j y f i ji j w

sau- fereastra w(x,y) =

gaussiana1 in fereastra, 0 afara


( , ) ( , ) ; ,

( , ) ( , ) ( , )

: (

( , ) ( , )

2( , )

,

x f ff i j f i j f fx y x yx yy

x xf i j f i j x y A x yx y y y

unde A x

f i x j y f i j

g x yi j w

2( , ) ( , ) ( , ), ,

, )2

( , ) ( , ) ( , ), ,

f i j f i j f i jx x yi j w i j w

yf i j f i j f i jx y y

i j w i j w

- Integrare dupa directiile discrete matricea de autocorelatie- matricea de autocorelatie dezvoltare in serii Taylor si aproximare

2( , ) ( , ) ( , )

2( , ) ( , ) ( , )

2

2,

, , ( , ) ,

: ( , ) ( , )f i j f i j f i jx x y

f i j f i j f i jx y y

x x y

i j w x y y

TE x y x y A x y x y

f f f B Dunde A x y w i j

D Cf f f


Matricea A => structura ferestrei w

Fereastra gaussiana:

Evaluarea variatiilor functiei f:

Derivatele fx, fy => aproximarea gradientului (de ex. cu Prewitt)

Nota: w: (3x3) => vecinatatea de cautare: (5x5)w: (5x5) => vecinatatea de cautare: (7x7) etc.

2 2

2( )

( , )x y

w x y e


si = valorile proprii ale matricei A- si => descriptori pentru A

si mici: => regiune neteda (flat) o valoare proprie mica si cealalta mare => muchie (edge) si mari: => colt (corner)

Functia raspuns:

R > 0 => regiunea corner R < 0 => regiunea edge |R| cu val. mici => regiunea flat

22

( ) ( )

: ( ) , ( ) 0.04 0.06

R Det A k Tr A

unde Det A B D Tr A BD Ck

R > 0

R < 0

R < 0|R| mic


Detectia colturilor => calculul marimii cv (cornerness value)

22

2 22

( )( )

x y

x y x y

f fTr AcvDet A f f f f

- cv nu necesita calculul valorilor proprii

- colt cv < vp (valoare de prag)


Operatorul Smith

Masca circulara => centru = nucleuPixelii cu acelasi nivel de gri cu al nucleului => colorati in negruZona colorata in negru => USAN (Univalue Segment Assimilating Nucleus)

Masca Smith 37 pixeli


Aria USAN:- muchii

- un minim pt. muchii- colturi

- un minim local accentuat pt. colturi


Operatorul SmithColt => cea mai mica arie USAN SUSANDetectorul SUSAN (Smallest Univalue Segment Assimilating Nucleus)

Calculul ariei- se compara nivelul de gri al nucleului cu nivelurile pixelilor din masca:

60( ) ( )

0( , ) 100f r f r

tc r r e

r

rrcn )0,(

r0 => pozitia nucleului (x0,y0)r => pozitia pixelilor din masca (x,y)t => prag pt. diferenta f(r)-f(r0)

- se calculeaza aria USAN:

Colt n < gg=1/2 din cea mai mare arie posibila USAN (g = 1850)


OPI

Harris Smith

OPI => = 26Harris => vp = 1000Smith => t = 29


3.4. Reconstituirea imaginilorDegradarea imaginilor (funcii h) - micarea relativ a unui obiect (V = ct.) n raport cu camera (a)

- focalizarea greit a imaginii (b)

- turbulene atmosferice (c)

Imaginea degradat: ),(),)((),( jijihfjig zgomot

),(),(),(),(),(

),(),(),(),(11 vuHvuNvuHvuGvuF

vuNvuHvuFvuG

(a) V = viteza constant pe directia axei x, T = intervalul de timp

Transformata Fourier a degradri: VuVTuvuH

)sin(),(

(b) 2221 ;),(),( vurar

raJvuH

J1 = funcia Bessel de ordinul I

(c)6/522 )(),( vucevuH : c = coeficient dependent de tipul turbulenei


3.5 Procesarea imaginilor color

(i) procesarea fiecrei componente a imaginilor color

(ii) procesarea bazat pe reprezentarea vectorial

Imagine monocrom

(x,y)

TBGR yxyxyxyx ),(),(),(),( ffff

Imagine color RBG

(x,y)


3.6 Detecia muchiilor

(i) se determin muchiile pentru fiecare component- se aplic tehnicile de la imaginile monocrome

(ii)Gradientul vectorului f n fiecare punct (x,y)

- magnitudinea i direciar, g, b: vectori unitate de-a lungul axelor R, G, B

TBGR yxyxyxyx ),(),(),(),( ffff

bgrn

bgrm

yB

yG

yR

xB

xG

xR


yB

xB

yG

xG

yR

xRg

yB

yG

yRg

xB

xG

xRg

Txy

Tyy

Txx

nmnm

nnnn

mmnm

222

222

yyxx

xygg

garctg

221

Di Zenzo direcia variaiei maxime

magnitudinea: variaia n direcia

2sin2221)( xyyyxxyyxx gcodggggM

Cap4. Segmentarea imaginii

Segmentare = divizarea imaginii n pri (regiuni) corelate cu obiectele i

suprafetele din imagini

Segmentare: 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)

jiRRRR jis

ii

,

1

prag;)(pentru0)(pentru1

),(

T

Ti,jfTi,jf

jig

),()ii(;)()i( cffTTfTT


Band-thresholding

Praguri multiple

Semi-prag

Metoda pragului niveluri de gri din imagine, gradientul imaginii etc.

restin0)(pentru1

),(Di,jf

jig

restin0),(pentru

),(pentru2),(pentru1

),( .............................................2

1

nDjifn

DjifDjif

jig

Di = submulimi de niveluri de gri

Ti,jfTi,jfjif

jig)(pentru0)(pentru),(

),(


Rosu [26 56]; Albastru [110 128];

Verde [56 84]; Violet [147 166];

4.1.1. Detecia pragului

Metoda p-tile

Text tiprit: aria ocupat de caractere =

= 1/p din aria total histograma : (1/p)NG

Metoda optimal de gsire a pragului

probabilitatea ca un pixel dintr-o imagine MN s aib nivelul de gri g

Histograma Distributie probabilistic variana = gradul de omogenitatePri omogene variane mici

Pragul T

H-bimodala

(i) i (ii): variana ponderat

pragul T : se calculeaza efort de calcul

1,0,),(|),(Card)( GgMNgjifjigP

1

12

01

)()()ii(

)()()i(

G

Tg

T

g

gPTq

gPTq : probabilitatea de apariie a pixelilor cu NG T

: probabilitatea de apariie a pixelilor cu NG > T

)()()()(;)()(media)ii(

)()()()(;)()(media)i(

21

1

22

22

1

122

10

21

21

011

TqgPTgTTqggP

TqgPTgTTqggP

G

Tg

G

Tg

T

g

T

g

variana

variana


)(min 2 TwT

)()()()()( 222211

2 TTqTTqTw 1-0,1,..,),(2 GgTw


Soluie iterativ (rapida): media i variana total

TgPgggP Gg

G

gpraguldedepindnu:)(;)(

1

0

221

0

1,1pentruSimilar0)()()()()(

)()()()()()()(

:

)()()()(2)(

)()()()(2)(

)()()()()()(

11111

01

01

011

1

1

2222

22

0

2111

21

1

122

0

211

2

GTgTqTTqTT

gPTggPTgPTTg

Nota

gPTTTgTg

gPTTTgTg

gPTTggPTTg

T

g

T

g

T

g

G

Tg

T

g

G

Tg

T

g


2

22

222

211

222

211

2

1

12

22

22

01

21

21

2

1

1

22

22

0

21

21

2

max

maxmin

)()()()()()()()(

)()()()()()()()(

)()()()()()()()(

22

B

Bw

G

Tg

T

g

G

Tg

T

g

Bw

TTqTTqTTqTTq

TqTgPTgTqTgPTg

gPTgPTggPTgPTg

( nu depinde de T )2se calculeaz recursiv :,,, 2121 qq

)()()()()(2,0)(1)(

)1()1()1()()()1(

0)0(;

)1()()1()0()0(

2221112

1

111

1

1

1

1

TTTqTTqGTTqTq

TqTPTTTqTTPTqTq

Pq

Algoritm de segmentare:

1o ntreaga imagine = o singur regiune

2o band spectral histogram netezithistogram max. semnificativ + 2 min. segmentarea n 2 subregiuni proiectarea ntr-o singur imagine

multispectral

3o Repet pasul 2o pentru fiecare regiune un singur maxim


4.1.2. Metoda pragului pentru imagini multispectrale

(1) (2)

Segmentarea unei imaginibispectrale

Segmentare prin metoda pragului pe fiecare banda


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 pragPrewitt LoG

4.2.1. Relaxarea muchiilor

Frontiere 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) extremeVst, Vdr

Se pot aduga i muchiile i i h paralele cu e

Relaxarea muchiilor frontier continue muchie central: cte un vrf la fiecare capt 3posibile 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

a

b

c

d

f

g

i

h

e

Muchii crack



Pentru simetrie: i j situaii contextuale: 0 - 0 muchie izolat : influen negativ asupra certitudinii 0 - 2 capt mort : influen negativ asupra certitudinii

0 - 3 0 - 1 muchie nesigur : influen slab pozitiv sau fr influen 1 - 1 muchie 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

e

0 - 0

e

1 - 1

e

2 - 0

e

3 - 3

Tipuri de muchii


Relaxarea muchiei metod iterativ certitudinea muchiei converge la:0 = muchie terminal

1 = muchie ce formeaz frontiera

Certitudinea c(1)(e) pentru primul pas = magnitudinea normalizat a

muchiei crack e

Normalizarea max. global al muchiilor crack din ntreaga imagine

max. local ntr-o vecintate a muchiei

Algoritm de relaxare

1o Calculeaz c(1)(e) pentru toate muchiile crack din imagine

2o Gsete tipul muchiei utiliznd certitudinea ntr-o vecintate

3o 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 3o

Algoritmul evalueaz: tipul vrfurilor tipul muchiilor modificarea certitudinii muchiilor


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.1Ex. 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

abccmab

cmbmacmbmam

kkik

)3(tip)()2(tip

;))(()1(tip

))()(()0(tip

3,2,1,0,)(tipmax)(tip

)( cba

)2.0,2.0,3.0(),,(

)05.0,05.0,5.0(),,(

cba

cba

)(,0max)(

)(,1min)(

)()1(

)()1(

ecec

ecec

kk

kk

3.0,1.0


4.2.2. Trasarea frontierelor

Reginile 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 direcia

3o Elementul curent al frontierei Pn = P1 : al doilea element i dac Pn-1 = P0 STOPDac nu pasul 2o

4o Pixelii P0 . Pn-2 = frontiera interioar

3

5 7

10

1

2

3

V4(a)

0

2

4

6

V8(b)

(c) (d) (e)

Exemplu: Trasarea frontierei interioare 1 2 3 4 5 6

Pasul 1o: P0 dir = 7Pasul 2o:

P0 dir = (7+6)mod 8 = 5 (5,2)=P1dir = 5

P1 dir = (5+6)mod 8 = 3 (4,1), (4,2)=P2dir = 4

P2 dir = (4+7)mod 8 = 3 (3,1), (3,2), (3,3)=P3dir = 5

P3 dir = (5+6)mod 8 = 3 (2,2), (2,3)=P4dir = 4

P4 dir = (4+7)mod 8 = 3 (1,2), (1,3), (1,4), (2,4)=P5dir = 6

Not: Algoritmul nu poate detecta frontiera interioar a unei guri


- pixelii testai pe parcursul trasriifrontierei

- pixelii frontierei

P0P1P2

P3P4P5

Trasarea frontierei pentru V8

1

2

3

4


Algoritm pentru trasarea frontierei exterioare1o Traseaz frontiera interioar utiliznd V42o Pixelii testai R frontiera exterioar

Frontiera exterioar perimetrul, compatitatea 12345

P0 P1P2P3 P4

Trasarea frontierei exterioare ()

1 2 3 4 5 6 7 8

Exemplu: Trasarea frontierei exterioare

Pasul 1o: P0 dir = 3Pasul 2o:

P0 dir = (3+3)mod 4 = 2 (1, 2), (2, 3), (3.2)=P1dir = 0

P1 dir = (0+3)mod 4 = 3 (3,3)=P2dir = 3

P2 dir = (3+3)mod 4 = 2 (2, 3), (3,4)=P3dir = 3

P3 dir = (3+3)mod 4 = 2 (2, 4), (3, 5), (4,4)=P4dir = 4


Frontiera extinsFrontiera interioar RFrontiera exterioar R

Frontiera extinsa regiuni adiacente

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

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

123

5 607

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 extinse


Frontiera extins

R

SUS (R)

JOS (R)

DREAPTA (R)STNGA (R)


Construirea FE folosind frontiera exterioar

(a) frontiera exterioar

(b) construirea FE

(c) FE = aceeai form cu frontiera

obiectului

Frontiera exterioar: DREAPTA, STNGA, SUS, JOS

Se 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)


Algoritm de trasare a FE metoda look-up table

Tabelul 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)

(g) (h) (i) (j) (k) (l)

fundal

regiune

fundalsauregiune

4.2.3. Conectarea muchiilor cu ajutorul grafurilor orientate

Cunotine 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 frontierei

Reguli 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)


4

)(;4

)(

iid xx

2)]()([

2mod

ji xx


START STOP

1

2 34

5 1

5

3

7 86

Exemplu

Muchii cu directii simagnitudini

Construirea unui graf orientatA

D

C

G

E

I

H

F

B

J

15

21

5

23

3

36

67 7

8

T = 15


Construirea frontierei

Construirea frontierei gsirea unei ci de cost minim n graf de la un nod deSTART 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 xBg(xi): componente gs(xi): estimarea costului cii xA xi

ge(xi): estimarea costului cii xi xBgs(xi): suma costurilor arcelor sau nodurilor xA xi ; sau lungimea xA xigs(xi): lungimea frontierei xi xBFuncia de cost esenial poate fi dependent de:

a) - modulul gradientului:

b) - curbura frontierei detectate:

c) - distana pn la punctul final:

( ) ( ); max ( )i i ii R

g M s M s

x x x( ) ( ) ( )i i jg x x x

( ) ~ ( , )e i i Bg dx x x


Exemplu

A

D

CG

E

I

H

F

B

J

15

21

5

23

3

3 6

67 7

8

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

( ) ( ); max ( )i i ii R

g M s M s

x x x

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 douapuncte care apartin caii

Dac:

Eliminm x2:

1

1 2 1 1 2 2 2 3 1 *

1 2 1 2 1 1 2 2 1

( , , ..., ) ( , ) ( , ) ... ( , ) ( )( ) max ( , ); , ..., fara

n n n n

nx

h x x x h x x h x x h x xx x f x h x x h h x

numai n h1

)(max)....,,,(max

),()(max)(

),()(max)(

121

11121

3222132

1

2

nnx

nx

nnnnnx

nn

x

xfxxxh

xxhxfxf

xxhxfxf

ni

n

2 valori discrete ( 1)ix p n p p


)...,,,(max 21 nx

xxxhi

calcule n loc de pn

n pasi cu optimizareaunor functii de 2 variabile


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

1 2 11 2

1 8 1

1 1

( , , ..., ) ( ) ( , ) 0

( , ) 2curbura ( , ) ( ) ( )

n nn k k k

k k

k k k k

k k k k

h s q

Vq q

x x x x x xx x x x

x x x x

)(),()(max)(

)(),()(max)(0)(

111

1021121

10

1

kkkkkkk fqsf

fqsff

kxxxxx

xxxxxx

x

x


Exemplu

A

D

C

G

E

I

H

F

B

J

05

10

4

4

23

3

26

56 7

7

A

D

C

G

E

I

H

F

B

J

(5) (8)

max(11,12)

1 2 3 4 5 k

f(xk)

max(9,10)(8)max(10,13)

max(19,28)

(23)max(9,16)

Ponderarea arcelor:

1( ) ( ) ( ) ; 4 /k k ks x x x

Conectarea muchiilor folosind programarea dinamica

START STOP

1

2 34

5 1

5

3

7 86


4.2.5. Transformata Hough

Obiecte = forme imrimi cunoscute


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 trecprin pixelul respectiv valorile a, b: A(a, b)

baxy

2222

11

1111

),()','(

),(

yaxbyxBbayaxb

baxyyxAbaxy

),( 22 yxB

baxy y

x

),( 11 yxA

22 yaxb b

a

11 yaxb b'

a'


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 parametrilor

2o Formeaza o arie de acumulatori A(a); seteaza pe 0 toate elementele

3o (x1, y1) muchie si

4o Maxim local in aria A realizarea curbei f (x, a).AAAf )()(0),( aaax

sincos yx0),( axf

y

x

'

'

'

'


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.

222 )()( rbyax

)(,)()())(sin())(cos(

1

1

xxxxx

RybRxa

a

bR

(x1, y1)

sincos

1

1RbyRax


4.2.6. Construirea regiunilor cu ajutorul frontierelor

Segmentarea bazata pe muchii detectia frontierelor segmentare totala

partiala 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


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) = 1

B(x) = 0.2 pentru b(x) = 2

B(x) = 0.5 pentru b(x) = 3

B(x) = 1.0 pentru b(x) > 3

Certitudinea ca un pixel

Condiia ca x si y sa fie opusi:fundalului1

1)(

8

R

xRxVi

iB

2

3)()(

2 2mod

yx


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) jiRRRR ji

s

ii

,,1

,fals"" ,1"adevarat")( jiRRH siRH jii

- omogenitate (O)

Ri adiacent cu Rj - maximalitate (M)

Segmentarea regiuni cu proprietatile O si MFormarea regiunilor - unirea regiunilor

- divizarea regiunilor

- unirea/divizarea regiunilor


4.3.1. Unirea regiunilor

Algoritm de unire a regiunilor

1o Defineste o metoda de startare a segmentarii regiuni mici care satisfac (O)2o Defineste un criteriu de unire a doua regiuni adiacente

3o 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

descriere


4.3.2. Divizarea regiunilor

START: Imaginea = o regiune nu satisface (O)Se divide imaginea in regiuni cu: (S, (O) si (M)

4.3.3. Divizare si unire

Reprezentare piramidala a imaginii regiunea = patrat- Regiune neomogena divizare in patru regiuni- 4 regiuni a unui nivel cu aceeasi omogenitate

o regiune

Divizare

Unire

Segmentarea = construirea unui arbore cvadripartit- fiecare nod f. = regiune omogena (f. = frunza)- nr. noduri f. = nr. regiuni segmentate


00 01

02 031

232

30

33

310 311

312 313

Divizare si unire eliminarea sau adaugarea unor parti din arborele cvadripartit

Arbore cvadripartitde segmentare

1 2

30 32 33

310 312 313 314

01 02 03 04


Algoritmul divide si uneste1o Segmentarea initiala in regiuni omogenitate

reprezentare piramidala

2o H(R) = (fals) divide R in 4 regiuni copil; daca 4 regiuni cu acelasi parintepot fi unite uneste-le. Daca nu se pot uni sau divide regiunile 3o

3o Ri, Rj adiacente daca se pot uni intr-o regiune omogena uneste-le chiar dacanu fac parte din acelasi nivel al piramidei sau daca nu au acelasi parinte

4o Uneste regiunile mici cu cele mai similare regiuni adiacente daca este necesar sa

fie eliminate regiunile cu dimensiuni mici.

Segmentarea construirea regiunilor omogene determinarea frontierelor regiunilor

Descrierea regiunilor vector (numeric) al trasaturilor descrierea sintactica

Caracterizeaza proprietatile regiunilor: forma

Forma nu exista tehnici generale de descriereClase de forme:

forme generice ale obiectelor ce apartin acelorasi clase

Cap5. Descrierea si reprezentarea formelor

Forma (shape) proprietatea unui obiect- reprezentarea formelor frontiere - extern

regiuni - intern- abilitatea refacerii obiectelor- posibilitatea de a recunoaste formele incomplete- tehnici de reprezentare matematice: TF

euristice : elongatia- descrierea sintactica sau statistica- robustetea descrierii la translatii, rotatii, scalari etc.

Descrierea formelor descriptori globalisau de frontiera: descriere externa locali

de regiune: descriere interna

Cap. 5. Descrierea si reprezentarea formelor


5.1. Identificarea regiunilorIdentificarea regiunilor: necesara pentru descrierea regiunilor

Identificarea = etichetarea (colorarea) unei regiuni (frontiere) cu un numar intreg

- eticheta cu numarul cel mai mare numarul regiunilor

Imaginea R Ri regiuni disjuncte:

Ri = obiecte (i b); Rb = fundal

Etichetare:

segmentare

jiji

m

ii RRRR

1,

m

i

cb

bii RR

1

ibi

ib vRR ,0


f (i-1, j)f (i, j )f (i, j -1)

f (i-1, j)f (i, j)f (i, j -1)

f (i-1, j -1) f (i-1, j +1)0 0 0 0 0 00 1 0 0 2 00 1 0 0 2 00 1 0 0 2 00 1 1 1 ? 00 0 0 0 0 0V4 V8

1. Cerceteaza linie cu linie Rpixelul R(i, j) 0 R(i, j) = v, v 0 : v in functie de pixelii vecini aflati in V4 sau V81.1 vecinii Rb v = valoare noua (numar nou nefolosit)1.2 un vecin 0 v = valoare gasita 01.3 mai multi vecini 0 se atribuie eticheta oricarui pixel 0

coliziunea etichetelor perechi echivalente in tabele de echivalente2. Pixeli cu etichete incerte tabelul de echivalente se alege o valoare

(de ex. cea mai mica)

Etichetele se atribuie incremental in diferite etape ale algoritmului

Algoritm de etichetare


0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 1 1 0 0 1 1 0 1 00 1 1 1 1 1 1 0 0 1 0 0 1 00 0 0 0 1 0 1 0 0 0 0 0 1 00 1 1 1 1 1 1 1 1 1 1 1 1 00 0 0 0 1 1 1 1 1 1 1 1 1 00 1 1 0 0 0 1 0 1 0 0 1 1 00 0 0 0 0 0 0 0 0 0 0 0 0 0

a) pasul 1o : v = 1

0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 2 2 0 0 3 3 0 4 00 5 5 5 2 2 2 0 0 3 0 0 4 00 0 0 0 5 0 2 0 0 0 0 0 4 00 6 6 5 5 5 2 2 2 2 2 4 4 00 0 0 0 5 5 5 2 2 2 2 2 4 00 7 7 0 0 0 5 0 2 0 0 2 2 00 0 0 0 0 0 0 0 0 0 0 0 0 0

b) pasii 1.1 - 1.3

2 - 55 - 6

2 - 4

0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 2 2 0 0 1 1 0 2 00 2 2 2 2 2 2 0 0 1 0 0 2 00 0 0 0 2 0 2 0 0 0 0 0 2 00 2 2 2 2 2 2 2 2 2 2 2 2 00 0 0 0 2 2 2 2 2 2 2 2 2 00 3 3 0 0 0 2 0 2 0 0 2 2 00 0 0 0 0 0 0 0 0 0 0 0 0 0

c) pasul 2o

Tabelul de echivalente:

ExempluIdentificarea regiunilor folosind V8

Cap. 5 Descrierea si reprezentarea formelor

Algoritm de identificare pentru o structura de tip arbore cvadripartit

1o Cauta nodurile incepand de la radacina: dir NW, NE, SW, SE nod frunza 0 neetichetat eticheta verifica nodurile frunza din vecinatate:

dir = E si S pt. (V4) + SE pt. (V8) nodurile frunza 0 fara eticheta eticheta nodului de unde a inceput verificarea nod etichetat coliziune

2o Repata 1o pana se verifica tot arborele

3o Reeticheteaza nodurile frunza din tabelul de echivalente


5.2. Descrierea formelor bazata pe contur

Reprezentarea matematica a frontierelor regiunilor

y

xxn

xnyn

y

xr

y

x

n

Sistem decoordonate

rectangular polar tangential

(xn,yn) (r, ) (n, )() un elemental frontierei


5.2.1. Codurile Freeman (lant)

Codul lant = descriere prin:

- coordonate punct start

- secventa de numere = sir segmente de lungime unitate cu directii predefinite

Codul lant diferential mod 4 sau mod 8: secventa de directii relative masurate ca

variatii cu 90o sau 45o

- dir = dir(k+1) dir(k)

Codul lant normalizat independent de pixelul de START- se alege START secventa numar intreg de valoare minima


Exemplu

2

Codul lant: 3 0 0 3 3 0 0 0 0 0 1 1 2 2 1 1 1 2 2 2 3 3 2 2

Codul diferential: 1 0 3 0 1 0 0 0 0 1 0 3 0 1 0 0 3 0 0 1 0 1 0 3

[0o-(-90o)] [0o-0o] [-90o-0o]90o 0o -90o

1

3

0

V4

START: (2, 4)

START


5.2.2. Reprezentari geometrice ale frontierei

Descriptori sensibili la rezolutia imaginii

Lungimea frontiereiCodul lant: 4 dir. directii de lungime unitara;

8 dir. directii de lungime 1 sauFrontiera inchisa lungime = perimetru [pixeli] CurburaCazul continuu: curbura = rata de variatie a pantei

Descriptorul curbura =

Evaluarea curburii detectia punctelor de curbura ridicata = colturi sau puncte dominante ()

nr. total de pixeli ai frontierei (lungimea)nr. de pixeli cu schimbari semnificative de directie

2

Functia de curbura:


:)()(

)(

,)()(

22

dd

dyd

dxts

btatyytxx

C

t

a

0( ) lim

sc s

s

lungimea unuiarc t [a, b]

x

y

C = x + jy

x

y

s

T1 T2

M1

M2a

22 2( ) ; pentru 0xy xyc t cx y

punctde inflexiune

puncte dominante: varfurile poligonului care aproximeaza conturul: reprezentarea parametrica

a curbei C

2

2

2

2

;

;

dx d xx xdt dtdy d yy ydt dt

Notatii:


Cazul discret:

functia c = zgomotoasa

analog)(,)1()1()1()1()1()1(

)(22

txtytytxtx

txtxtx

- Netezirea functiilor x(t) si y(t): operator gaussian 22

2),(

t

etg

2

2

2 2

2 2

( )2

'

"

22 2

2 2 2

( , ) ( ) ( , ) ( )

( , ) ( ) ( , ) ( ) ( , )

( , ) ( ) ( , ) ( ) ( , )

1 1( , ) ; ( , ) 1

( , ) ( , ) ( , ) ( , )( , )

t

t t

x t x t g t x e d

x t x t g t x t g t

x t x t g t x t g t

tg t te g t e

x t y t x t y tc t

3/ 22 2( , ) ( , )x t y t

netezirea functiei x(t)

functia de curbura


Codul lant

21

-1-2

c(k)

k

421

c2(k)

k

Energia de indoireCurbura: c(k) dir(k+1)-dir(k)

1 2

1

0 0

45 1 45 1

90 2 90 2

1 ( )L

kEI c k

L

248

16228

1EI


SemnaturaSemnatura = {distante normale la contor}

Exemple

y

x

r2r

Cerc Semnatura unui cerc

Triunghi echilateral Semnatura unui triunghih

h


Distributia corziiCoarda = linia care uneste doua puncte ale conturului

b(x, y) = 1 pt. multimea punctelor ce alcatuiesc conturul

b(x, y) = 0 celelalte puncte

Descriptori:

Distributia radiala = invarianta la rotatii

Distributia unghiulara: : invarianta la scalare

( , ) ( , ) ( , )

( , ) ( , ) ( , )i j

h x y b x y b x x y y dx dy

h x y b i j b i x j y

ry

yxr

rdyxhrhr

arcsin;

),()(

22

2/

2/

)max(

0),()(

ra dryxhh

Imagini digitale

r

x

y


5.2.3. Descriptori FourierCurba C parcursa cu viteza constanta:

viteza intregul contur parcurs in 2pz (t) = functie periodica

s: distanta parcursa in t sec. :

Descriptorii Tn depind de: - forma curbei

- punctul de start

)()()( tjytxtz

0

1( ) ( )T

jnt jntn n

nz t T e T z t e dt

T

2

0

2 1; ( )L jn s

Lnst t s T z s e ds

L L

y

xs

(x1(s), y1(s))

C

Tn = descriptori Fourier


Descriptori Fourier invarianti

Frontiera inchisa:

Descriptori invarianti la rotatii si translatii:

Descriptori invarianti la scalare:

1

11

2

1

11

2

11

11

11

),(),(L

m

nmL

jmn

L

m

nmL

jmn

LL

eyL

b

exL

ayxyx

1

22 ;rr

wbar nnnnn

1

nn

rw

r

forma4discreta

( ) ( )( ) : ( ) TFD nz s z k V z k T


y

x

4

l4(x1, y1)

1 23 4

5

1

2

0

dist ( , ); : unghiul tangentei pentru

2( ) : functie periodica

1 ( )2

k k k k

k k

k k k

jnun

l

u l La l u

S a u e du

x x x

SF

Reprezentarea frontierelor: lk , k

k capteaza frecventele ridicate Sn descreste mai incet ca Tn

Descrierea formelor cativa coeficienti Fourier de ordin inferior


5.2.4. Reprezentarea poligonala a frontierei

Reprezentarea poligonala regiunea ~ poligon descriere prin varfuri

Frontiera segmentare secventa de segmente de dreptasegmente de curbura constanta

Punctele extreme ale fragmentelor de frontiera varfuri

Segmentare - puncte de curbura ridicata = varfuri pentru fragmentele de frontiera

frontierei - pixeli adiacenti ce pot fi aproximati prin drepte sau curbe


2

2

1

1

1

2

1 1 1 12

( , ) ( ) min

( , ) 0 ( ) 0

( , ) 0 0

; ; ;

n

i ii

n

i i iin

i iin n n n

i i x i y i i xyxi i i i

x x x

f a b y ax b

f a b x y ax ba

f a b y ax bb

x m x m y m x y m

am bm m

2

2 22 2;

y

x y

y x yxy x y x

x xx x

am b m

m m m mm m ma b

m m m m

Notatii:

Determinarea segmentelor liniare de contur (metoda celor mai mici patrate)Segmentarea frontierei varfurile {x(i), y(i)}, i = 1 N ; parametrii segmentelorFragmente (pixeli de la 1 n) drepte: y = ax + b a, b ?

Calculul parametrilor optimi:

Segmentarea frontierelor in domeniul - sSegmentarea frontierei determinarea varfurilor in - s: = dir. tangentei la contur

s = lungimea arcului


x

y ab

c d Punct de start s

a b c d

2pp

(s) = constant portiuni liniareliniar variabil zone de curbura constante


)()(

)()()(cos

kkkk

kpp

pTp

p BABA

kpp

kppp

pkp

pkpp

yyxx

k

yyxx

k

)(

)(

B

A

impusa apriori

k opt. :Valoarea lui k

10

)1(cos)(cos...)1(cos)(cos

Nm

kkmm optpoptppp

N = lungimea fragmentului

(xp-k , yp-k)

(xp , yp)

(xp+k , yp+k)

p(k)

Determinarea valorilor lui (s) intr-un punct (xp, yp)

- pixelii din vecinatatea (xp-k, yp-k) (xp+k, yp+k)Cuantizarea directiei: 0o, 45o, 90o,

Valoarea unghiului :


5.3. Descrierea formelor bazata pe regiuni

Regiuni forme simple: descriptori euristici: aria, elongatia, compactitatea etc

forme complexe descompunere in subregiuni simple descriptori euristiciObiect graful subregiunilor

- subtierea regiunilor scheletul regiunii- subregiune = nod; arcele = relatii de vecinatate ale subregiunilor

Reprezentari grafice ale regiunilor:

- invariante la translatii, rotatii si in raport cu magnitudinea

- robuste la mici schimbari ale formei

- potrivite pentru recunosterea sintactica


5.3.1. Descritori scalari simpliProprietati globale descriptori : vector de trasaturi recunoasterea statistica AriaA = nr. de pixeli aria reala a unui pixelGrila rectangulara: functie caracteristica a regiunii R

- R poligon cu varfurile (ik , jk ) si (i0 , j0 ) = (in , jn )

- R codul lant cu 4 directii1o A = 0, pozitia verticala PV = i (i coordonata punctului de start)2o Pentru directiile codului executa 0: A = A - PV

1: PV = PV + 12: A = A + PV3: PV = PV - 1

3o Elementele frontierei parcurse aria in A

10

1121 n

kkkkk jijiA

i jR jigA

Ryxyxg ),(

restin0),(pixeluldaca1

),(


Perimetrul

Pixelii care apartin frontierei

RjiVRjiCRjiVRjiC

),(),(

),(),(

8

4

),(),(),(),(Card2),(),(),(Card

:),(...,),,(),,(

4118

114

1100

kkkkkkkk

kkkkkk

nn

jiVjiVjiCji

jiVjiCjiPjijijiC

CompactitateaA

P2

d 4

ab ab

baab

ba )(22)(2 22222

lkl

k

k

kl

kl 2

2

2 )1(4)1(2

ordonarea pixelilor vecini fiecare pereche formata din vecini

Cerc: cercul cea mai compacta regiune

Elipsa:

Dreptunghi:

Centrul de greutate

Elongatia

Gradul de excentritate

n = nr. de pixeli frontierei

Elongatia


1,...,1,0),(),,()( nkjijidkd kkcc

1

0

21

0

minmaxmin

max

)(1

;)(1

,

)(min;)(max,

n

kdd

n

kd

d

d

kk

kdn

kdn

kddkdddd

Rji

cRji

c jAji

Ai

),(),(

1;

1

(ic , jc) - centrul de greutate

(ik , jk) - pixelii frontierei


y

x

ds

dj

sst sd

jst jd

sts

stj

s = susj = josd = dreaptast = stanga

Regiunea incadrata intr-un dreptunghicu laturi paralele cu 0x si 0y

Laturile dreptunghiului:

RjiIjij

RjiIjij

RjiIjii

RjiIjii

j

j

i

i

),(),(max

),(),(min

),(),(max

),(),(min

max

min

max

min

Coordonatele punctelor de extrem:

Fiecare pereche de puncte extreme (ex.: sd, dj) axa: lungime, orientare descriptori

Rjijid

RjiIjiis

ij

jd

),(),(max

),(),(max,

maxmax

minminmin

Punctele de extrem


5.3.2. Descriptori bazati pe momente

Functia imagine normalizata = densitate de probabilitate a unei variabile aleatoare 2DProprietatile variabilei aleatoare caracteristici statistice = momenteMomentul de ordinul p + q:

- momente centrate (invariante la translatie):

Centrul de greutate (xc, yc):

Imagine binara:

- momente centrate scalate: scalare

-

i i

qppq

digit

imagqppq jifjimdxdyyxfyxm ),(),(

.

.

i i

qc

pcpq jifyjxi ),()()(

00

01

00

10 ,mm

ymm

x cc

RjiptjifAm ),(.1),(00yyxx ','

)2(00 ',12:cu''

qp

pqpq

pqpq

qp


203212123003211230

20321

21230123003217

03211230112

03212

123002206

20321

2123003210321

20321

21230123012305

20321

212304

20321

212303

211

20220202201

33

33

4

33

33

;33

4;

- momente centrate normalizate nescalate:

:

Date post:	13-Sep-2015
Category:	Documents
Upload:	mihai-ep
View:	284 times
Download:	0 times

Curs Sva Aio

Documents