Inteligenta Artificiala

115
54 CAPITOLUL 2 EXTRACŢIA ŞI SELECŢIA CARACTERISTICILOR DINTR-O IMAGINE DIGITALĂ 2.1 Introducere Extracţia şi selecţia caracteristicilor (feature extraction and selection) unei forme vizuale reprezintă două etape definitorii, de o importanţă deosebită asupra succesului şi performanţelor procesului ulterior de recunoaştere/ identificare a formei (pattern recognition) respective (fig. 2.1). Fig. 2.1 Extracţia şi selecţia caracteristicilor unei forme vizuale Pentru a fi utile procesului de recunoaştere a formelor, regiunile obţinute în urma procesului de segmentare a imaginii de intrare trebuie reprezentate într-o formă adecvată. Reprezentarea respectivă implică conciziune, eliminarea informaţiilor redundante şi, în special, reţinerea informaţiilor necesare

description

tehnici de clustering si altele

Transcript of Inteligenta Artificiala

  • 54

    CAPITOLUL 2

    EXTRACIA I SELECIA CARACTERISTICILOR DINTR-O IMAGINE

    DIGITAL

    2.1 Introducere

    Extracia i selecia caracteristicilor (feature extraction and selection) unei forme vizuale reprezint dou etape definitorii, de o importan deosebit asupra succesului i performanelor procesului ulterior de recunoatere/ identificare a formei (pattern recognition) respective (fig. 2.1).

    Fig. 2.1 Extracia i selecia caracteristicilor unei forme vizuale

    Pentru a fi utile procesului de recunoatere a formelor, regiunile obinute n urma procesului de segmentare a imaginii de intrare trebuie reprezentate ntr-o form adecvat. Reprezentarea respectiv implic conciziune, eliminarea informaiilor redundante i, n special, reinerea informaiilor necesare

  • 55

    recunoaterii formelor/obiectelor de interes. Procesul de obinere a unei asemenea reprezentri a regiunilor de interes este cunoscut n literatura de specialitate ca descriere/extragere de caracteristici. Descrierea este n direct legtur cu structura de date aleas pentru reprezentare, existnd o puternic dependen de aplicaia concret dezvoltat. Posibilitile de descriere a unei regiuni sunt extrem de variate. Se disting, totui, o serie de metode mai importante pentru extragerea de caracteristici:

    caracterizarea formei conturului regiunii (descriptori de contur); caracterizarea regiunii pe baza interiorului (descriptori regionali); descrierea topologic a regiunii de interes (texturi); descrierea morfologic a regiunii de interes (descriptori morfologici). Descriptorii formelor (vizuale) pot fi locali utilizai n situaii mai

    dificile (ocluzii, suprapunere de obiecte etc.), respectiv globali mai simpli i mai sintetici. Alegerea unei modaliti adecvate de descriere este esenial pentru reuita procesului ulterior de recunoatere a formei. De asemenea, un principiu fundamental care supervizeaz construcia descriptorilor formei este principiul invarianei acestora la diferite tipuri de transformri liniare sau neliniare aplicate formei de interes (se dorete, n special, obinerea invarianei setului de descriptori utilizat la punctul de start, scalare, translaie, reflexie i rotaie). Experiena practic demonstreaz c aspectul cel mai important n reuita unei aplicaii de recunoatere a formelor l reprezint selecia caracteristicilor/ proprietilor, respectiv a descriptorilor utilizai. Selecia caracteristicilor este, practic, un proces de compresie de date i poate fi asimilat cu o transformare liniar sau neliniar, de la spaiul iniial al observaiilor, presupus n-dimensional, la un spaiu cu mai puine dimensiuni, m (m

  • 56

    primare extrase i caracteristicile selectate ale acelor forme. Literatura de specialitate prezint mai multe metode consacrate pentru selecia caracteristicilor unei forme (nu neaprat vizuale), din care se disting prin performanele oferite:

    analiza componentelor principale (PCA); analiza componentelor independente (ICA); transformata KL, cu varianta sa 2D, Fukunaga-Koontz; selecia caracteristicilor prin maximizarea criteriilor de separare a

    claselor (analiza discriminatorie); transformrile neliniare; criteriul divergenei; proieciile n spaii 2D (algoritmul lui Sammon, algoritmul Lee-Slayle-

    Blum). Not. n paragrafele urmtoare vor fi dezvoltate i prezentate ntr-o form

    concis toate consideraiile enunate n cadrul acestui paragraf introductiv. De asemenea, n final, este util a fi precizat i faptul c unii specialiti n

    domeniu (Torma, 1996) consider selecia caracteristicilor unei forme (vizuale) ca fiind format din dou direcii distincte:

    selecia caracteristicilor n spaiul caracteristicilor; selecia caracteristicilor n spaiul transformat. Selecia caracteristicilor n spaiul transformat mai este cunoscut i sub

    denumirea de extracia caracteristicilor. Evident, fa de punctul de vedere acceptat n aceast lucrare referitor la

    definirea noiunilor de extracie i selecie a caracteristicilor unei forme (vizuale), clasificarea prezentat anterior constituie doar o nou interpretare terminologic a acestor noiuni, suportul conceptual fiind ns identic. 2.2 Metode de extracie a caracteristicilor

    Extracia caracteristicilor/descrierea unei forme vizuale este o etap esenial n prelucrarea digital a imaginilor (Digital Image Processing), aceasta deoarece rezultatele recunoaterii ulterioare depind n foarte mare msur de acurateea descrierii formei respective. Descrierea unei forme (nu neaprat vizuale) implic un nalt grad de concentrare a informaiei i, respectiv, de eliminare a celei neeseniale n procesul de identificare a acesteia. De asemenea, este util de amintit i faptul c extracia caracteristicilor unei forme este strns legat de structura de date aleas pentru reprezentarea acesteia. Cele mai importante cerine legate de structurarea setului de descriptori ai formei sunt urmtoarele :

    necesitatea utilizrii unor descriptori ai formei robuti, care sunt invariani la diferite tipuri de transformri liniare sau neliniare, n funcie de tipul concret de aplicaie vizat;

  • 57

    utilizarea unor descriptori ai formei regenerativi, n sensul caracterizrii n mod biunivoc a formei respective;

    utilizarea unor descriptori cu performane superioare, avnd n vedere importana etapei ulterioare de recunoatere a formei.

    Not. Condiia de invarian la anumite transformri impus structurrii unui set de descriptori ai formei, nu constituie ns o condiie absolut necesar, deoarece exist n prezent dezvoltate n literatur metode concrete de obinere a unui set invariant de caracteristici ale formei pornind de la un set variant de caracteristici ale acesteia (o soluie ar fi, spre exemplu, utilizarea unei reele neuronale pentru realizarea acestei transformri variantinvariant). Literatura de specialitate prezint, n esen, urmtoarele posibiliti de descriere a unei forme vizuale:

    caracterizarea conturului formei de interes (descriptori de contur); caracterizarea formei pe baza interiorului (descriptori regionali); descrierea topologic ( de textur) a regiunii de interes; descrierea morfologic a regiunii de interes. n consecin, mai jos sunt sintetizate principalele modaliti teoretice de

    extragere/descrierea a caracteristicilor unei forme vizuale: descriptori de contur: 1) codul Freeman; 2) numrul de form (codul lan generalizat); 3) aproximri poligonale; 4) reprezentri B-spline; 5) semnturi; 6) descriptori Fourier; 7) modelul AR etc. descriptori regionali: 1) elementari (aria, perimetrul, direcia, energia de ndoire, numrul lui

    Euler, nveliul convex, rectangularitatea, deficiena convex etc.); 2) momente (geometrice); 3) momente (pseudo-)Zernike; 4) momente Fourier-Mellon; 5) momente Hermit; 6) momente Bamieh etc. descriptori de textur: 1) statistici; 2) spectrali; 3) structurali; 4) morfologici. descriptori morfologici: 1) skeletonul morfologic; 2) skeletonul generalizat etc.

  • 58

    Not. n continuare vor fi dezvoltai teoretic cei mai interesani descriptori ai formei din punct de vedere al satisfacerii cerinelor impuse anterior i al performanelor de clasificare care pot fi obinute ulterior pe baza acestora. 2.2.1 Descriptori de contur Clasificarea obiectelor 2D constituie una din problemele cele mai importante ale recunoaterii formelor coninute n imagini. Evident, odat selectat obiectul de interes din imaginea complex, scopul imediat este de a-l clasifica. Dac informaia esenial procesului de clasificare este concentrat n conturul obiectului, atunci se vor utiliza descriptori de contur pentru caracterizarea acestuia.

    Not. n continuare se va accentua asupra descriptorilor formelor vizuale plane i nchise (mai uzuali i din punct de vedere al prii aplicative).

    2.2.1.1 Codul lan i numrul de form Se cunoate c un caz particular al reprezentrii unui contur prin secvena direciilor tangentelor la contur n= (ln) este codul lan (Freeman code/ chain code).

    Fig. 2.2 Reprezentarea unui contur folosind codul lan

  • 59

    Exist dou variante ale acestui cod, i anume cu cutare pe patru direcii, respectiv pe opt direcii. La codul cu patru direcii variabila este cuantizat pe patru niveluri, iar lungimile elementelor de contur (ln+1ln) sunt de un pixel (fig. 2.2). La codul cu opt direcii segmentele diagonale au lungimea mrit cu factorul 2 fa de segmentele de contur orizontale sau verticale.

    Not. Codul Freeman/codul lan mai este cunoscut n literatura de specialitate i sub denumirea de algoritmul de urmrire cu mna pe perete. n continuare se prezint structura algoritmului de urmrire a conturului cu opt direcii (mai des utilizat). n acest sens, algoritmul definete n prealabil o variabil dir pentru codificarea direciei. Etapele acestui algoritm sunt urmtoarele:

    pasul I: prin explorarea imaginii n ordine lexicografic se determin primul pixel al formei (regiunii) de interes R, practic pixelul din extremitatea stng-sus a regiunii de interes. Se marcheaz acest pixel cu un cod de start (A). Se verific dac pixelul de start mai are cel puin un pixel vecin din regiunea R:

    1) dac nu, algoritmul este terminat, STOP (conturul const din pixelul de start);

    2) dac pixelul de start mai are vecini n regiunea R, stabilete direcia iniial 0dir = ;

    pasul II: se repet pasul III pn cnd succesorul gsit este pixelul de start;

    pasul III: se actualizeaz direcia de cutare cu modulo8( 4)dir + . Pn la gsirea pixelului succesor de pe contur se repet secvena urmtoare:

    1) se incrementeaz direcia modulo8( 1)dir + dir; 2) dac pixelul vecin situat pe noua direcie este din regiunea de interes

    R, acesta este succesorul punctului de contur i dir este direcia curent. Se marcheaz succesorul cu un cod pixel de contur;

    pasul IV: codul de contur obinut este translatat n forma sa binar (8=23, deci sunt necesari trei bii pentru reprezentare). Algoritmul descris mai sus urmrete conturul n sens trigonometric, regiunea de interes R fiind n permanen la stnga direciei de deplasare. Direciile de deplasare gsite succesiv de algoritm (mpreun cu informaia despre poziia pixelului de start) permit o indentificare unic a conturului analizat, constituind reprezentarea acestuia prin intermediul codului lan. Acest cod are o serie de proprieti interesante care vor fi prezentate n continuare.

    Acest descriptor nu ndeplinete ns cerinele rezultate din respectarea principiului invarianei (spre exemplu, nu este invariant la rotaie i la punctul de start, dar este invariant la translaie). Un alt dezavantaj al utilizrii codului Freeman ca descriptor de contur este determinat de sensibilitatea sa sporit la zgomot (o soluie posibil la aceast ultim problem ar fi netezirea/filtrarea conturului sau reeantionarea imaginii de interes pe o nou gril cu rezoluie redus).

  • 60

    Este totui posibil obinerea unei reprezentri aproximative a conturului, bazat pe o variant a codului Freeman numrul de form (shape number), a crui calcul presupune, n esen, parcurgerea urmtoarelor etape de baz (Gonzales, 1993):

    1) construirea dreptunghiului de baz; 2) reeantionarea conturului; 3) determinarea codului Freeman diferenial normalizat (numrul de

    form) pentru conturul reeantionat. construirea dreptunghiului de baz

    Prin definiie, dreptunghiul de baz al unei regiuni este dreptunghiul de arie minim care include complet regiunea respectiv. O modalitate concret de determinare a acestuia este urmtoarea: mai nti, se traseaz axa major a regiunii care este cea mai lung coard a regiunii (axa major unete punctele de pe contur situate la distana cea mai mare). Ulterior, se traseaz axa minor, perpendicular pe axa major. Axele astfel construite definesc dreptunghiul de baz al regiunii de interes.

    Fig. 2.3 Construirea dreptunghiului de baz

    reeantionarea conturului

    Grila de eantionare a conturului se construiete n funcie de ordinul ales, ordin definit prin numrul segmentelor de contur. Ordinul influeneaz n mod direct numrul maxim de forme care pot fi reprezentate, respectiv precizia reprezentrii. Not. Ordinul trebuie s fie par deoarece orice form nchis are un numr par de pixeli pe contur. Construcia grilei de eantionare pentru un ordin ales implic un anumit grad de aproximare, aceasta deoarece dreptunghiul de baz real are

    excentricitatea (raportul laturilor maxmin

    ll

    ) oarecare, n timp ce dreptunghiurile care

    pot fi realizate pentru un anumit ordin au un numr finit de rapoarte posibile.

  • 61

    Spre exemplu, pentru ordinul 20 sunt posibile dreptunghiuri cu formatul 19, 28, 37 i 46 (care au perimetrul egal cu 20). Pentru trasarea grilei de eantionare se alege dreptunghiul cu ordinul care aproximeaz cel mai bine excentricitatea dreptunghiului de baz real i se centreaz peste acesta.

    Fig. 2.4 Reeantionarea conturului

    Reeantionarea conturului presupune trasarea acestuia folosind noua gril construit, astfel nct eroarea de aproximare s fie minim. Practic, ptratele care conin un numr de pixeli ai regiunii de interes superior fundalului sunt atribuite regiunii respective, i ulterior, conturul este trasat relativ uor folosind algoritmul de urmrire a conturului descris mai sus.

    determinarea codului Freeman diferenial normalizat (numrul de form) pentru conturul reeantionat Pentru a obine numrul de form mai sunt necesare parcurgerea urmtoarelor dou subetape:

    1) calculul codului Freeman diferenial pentru obinerea invarianei la rotaie;

    Acest cod se obine considernd codul Freeman iniial ca o secven ciclic i calculnd diferenele de direcie asociate fiecrui punct. Diferenele sunt calculate modulo 4 pentru codul cu patru direcii, respectiv modulo8 pentru cel cu opt direcii.

    Fig. 2.5 Un exemplu de calcul al codului Freeman diferenial normalizat

  • 62

    2) normalizarea codului Freeman diferenial pentru obinerea independenei reprezentrii n raport cu punctul de start;

    Acest lucru se realizeaz printr-o deplasare circular a codului lan diferenial pn cnd rezultatul obinut este minim (sau maxim).

    Not. Noul descriptor de contur construit este invariant la rotaie pentru o clas larg de tipuri de forme i, de asemenea, este independent n raport cu punctul de start. Numrul de form poate fi utilizat cu rezultate excelente, n special la descrierea contururilor plane i nchise, dar cu unele complicaii poate fi adaptat i pentru caracterizarea regiunilor ce prezint guri/discontinuiti.

    2.2.1.2 Aproximri poligonale

    Intuitiv, orice contur aparinnd unei imagini poate fi aproximat cu o precizie cunoscut cu ajutorul unui poligon. n situaia extrem, poligonul respectiv este format din toate punctele de pe contur i eroarea de aproximare n acest caz este nul. Practic, se dorete obinerea unei reprezentri optime din punct de vedere al preciziei de aproximare i care s capteze caracteristicile eseniale ale formei de interes, totul cu ajutorul unui numr ct mai mic de puncte. Problema respectiv se dovedete ns a fi prohibitiv prin prisma resurselor de timp i calcul necesare, de aceea, uzual, se utilizeaz diverse metode suboptimale, de complexitate moderat, metode care conduc la rezolvarea cu succes a aplicaiilor concrete de prelucrare digital a imaginilor. n acest sens, reprezentative sunt urmtoarele metode:

    fuziunea punctelor de pe contur Ideea principal a acestei metode este inspirat din faptul c, aproximarea

    poligonal a unui contur poate fi interpretat ca o problem de segmentare a acestuia (resegmentare). Prin urmare, acest algoritm cuprinde urmtorii pai:

    1) pasul I: se pornete de la un punct arbitrar i se parcurge conturul, fuzionnd succesiv punctele de pe contur pn cnd eroarea medie ptratic de aproximare asociat poriunii de contur parcurse de linia dreapt ce minimizeaz aceast eroare depete un prag prestabilit; se trece la pasul II;

    2) pasul II: se memoreaz parametrii liniei drepte; 3) pasul III: eroarea de aproximare 0; 4) pasul IV: se continu cu pasul I pn la parcurgerea ntregului contur; 5) pasul V: dup parcurgerea ntregului contur se determin punctele de

    intersecie ale liniilor drepte ce aproximeaz segmentele de contur adiacente, rezultnd vrfurile poligonului ce aproximeaz conturul de interes (condiia de STOP).

    Not. Un dezavantaj major al algoritmului prezentat este acela c n general vrfurile poligonului de aproximare nu coincid cu punctele de extrem ale curburii formei, puncte care au ns o importan deosebit pentru calitatea

  • 63

    percepiei vizuale, respectiv pentru procesul ulterior de recunoatere a formei analizate.

    divizarea segmentelor de contur Este o metod de aproximare suboptimal opus tehnicii de segmentare prezentat anterior i care permite eliminarea dezavantajelor metodei de fuziune. Algoritmul de divizare a segmentelor de contur presupune n esen parcurgerea urmtorilor pai:

    1) pasul I: se segmenteaz conturul n dou pri folosind n mod uzual perechea de puncte cu distana maxim (ele determin axa major a regiunii de interes). Pentru fiecare din segmentele de contur obinute, se determin o msur de eroare, n spe, distana maxim la dreapta care unete capetele segmentului respectiv, conform fig. 2.6:

    Fig. 2.6 Aproximarea poligonal corespunztoare primei diviziuni

    2) pasul II: dac criteriul de eroare impus este satisfcut, STOP; n caz

    contrar, se trece la pasul III; 3) pasul III: segmentul de contur este divizat din nou, folosindu-se ca

    separator al noii perechi de segmente punctul de distan maxim, totul conform fig. 2.7;

    4) pasul IV: se trece la pasul II. Not. n referina bibliografic [5] se prezint o metod eficient de calcul

    a distanei de la un punct (aparinnd conturului) la o dreapt. Se poate concluziona c aproximrile poligonale sunt un caz particular de aproximare a contururilor prin linii drepte. Evident, este natural tendina de generalizare a metodelor de aproximare poligonale prezentate anterior prin utilizarea curbelor de grad mai mare dect unu, reprezentative n acest sens (ca performane) fiind aproximrile prin funcii spline, cu aplicaii directe, n special, n grafica computerizat.

  • 64

    Fig. 2.7 Aproximarea poligonal corespunztoare unei noi diviziuni

    2.2.1.3 Reprezentri B-spline B-spline sunt funcii polinomiale (definite pe poriuni) care pot furniza

    aproximri locale neliniare ale contururilor regiunilor utiliznd un numr redus de parametri. Utilizarea funciilor B-spline este pe deplin justificat de faptul c percepia uman se consider a fi mai sensibil la vizualizarea curburilor unui contur sau la suprafaa unui obiect. Funciile B-spline sunt utilizate cu succes n analiza i sinteza formelor, grafic computerizat sau recunoaterea formelor.

    Fie t un punct aparinnd unui contur arbitrar, iar x(t), respectiv y(t) coordonatele spaiale asociate acestuia. O reprezentare B-spline este de forma:

    [ ] [ ], 1 20

    ( ) ( ), cu ( ) ( ), ( )i ,n

    TTi i k i i i

    it p B t t x t y t p p p

    =

    = = =x x , (2.1)

    unde {pi}i reprezint punctele de control, iar {Bi,k(t)}i,k, 1, , 1,2,...i n k= = sunt funciile normalizate B-spline de ordin k. n grafica computerizat aceste funcii mai sunt numite i funcii spline primare sau funcii mixte i pot fi generate n mod recursiv cu ajutorul relaiilor:

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

    1 1

    1,1

    ( ) , 2,3,...

    1, dac( ) ,

    0, altfel

    i i k i k i ki k

    i k i i k i

    i ii

    t t B t t t B tB t k

    t t t tt t t

    B t

    + +

    + + +

    +

    = + =

    =

    (2.2)

  • 65

    unde se adopt convenia 0 00= . Parametrii {ti}i, i=0,1,... se numesc puncte de

    legtur (knots) i semnific locaiile n care funciile spline se intersecteaz reciproc. Asociate cu punctele de legtur sunt nodurile (nodes) {si}i care se definesc ca fiind locaiile medii ale k1 puncte de legtur, de forma:

    ( )1 2 11 ... , 0,

    1i i i i ks t t t i n

    k + + + = + + + =

    . (2.3)

    Not. Variabila t se mai numete i parametru de nod i ale crui valori

    speciale sunt ti i, respectiv, si. n fig. 2.8 sunt prezentate cteva exemple de funcii B-spline. Aceste funcii sunt cu valori pozitive i au un suport finit. Mai precis, pentru cazul funciilor B-spline normalizate avem c 0 Bi,k(t)1, iar suportul acestora este intervalul [ti, ti+k ). Funciile Bi,k(t) formeaz o baz n spaiul funciilor polinomiale definite pe poriuni i mai sunt numite i funcii B-spline deschise sau nchise (sau periodice), dup cum conturul pe care l aproximeaz este unul deschis sau nchis. Parametrul k controleaz ordinul de continuitate al curburii. Spre exemplu, pentru 3k = funciile spline sunt polinoame cuadrice (definite pe poriuni), iar pentru 4k = sunt polinoame cubice. n grafica computerizat, un ordin k egal cu 3 sau 4 se consider a fi suficient.

    Fig. 2.8 Funciile B-spline normalizate de ordin 1,2,3,4k =

    Cnd punctele de legtur sunt repartizate uniform n spaiu, ceea ce nseamn c:

    1 ,i it t t i+ = , (2.4)

  • 66

    atunci funciile Bi,k(t) se numesc funcii spline uniforme i acestea devin translaii ale funciei B0,k (t), de forma:

    ( ) ( ), 0, , 1, ,..., 1i k kB t B t i i k k n k= = + . (2.5)

    O aproximare a contururilor Bi,k(t) se obine cu ajutorul relaiei (2.2). Pentru cazul funciilor B-spline uniforme i deschise cu 1t = , valorile punctelor de legtur pot fi alese de forma:

    0 ,1 ,2,

    i

    i kt i k k i n

    n k i n

    , (2.6)

    iar pentru cazul funciilor B-spline uniforme i periodice (sau nchise) punctele de legtur pot fi alese ca:

    ( )( ) ( ), 0,

    mod 1i

    ( ) mod 1i

    i k k

    t i n

    B t B t i n

    = +

    = + (2.7)

    Pentru valorile k=1,2,3,4 i punctele de legtur date de relaia (2.7), forma analitic a funciei B0,k (t) este prezentat n relaiile urmtoare:

    0,1

    0,2

    2

    2

    0,3 2

    1, 0 1( ) ;

    0, altfel

    , 0 1( ) 2 , 1 2;

    0 , altfel

    , 0 12

    3 1,5, 1 2( ) ;(3 ) , 2 3

    20 , altfel

    tB t

    t tB t t t

    t t

    t t tB tt t

  • 67

    3

    3 2

    3 2

    0,4

    3

    , 0 163 12 12 4 , 1 2

    63 24 60 44( ) , 2 3.

    6(4 ) , 3 4

    60 , altfel

    t t

    t t t t

    t t tB t t

    t t

  • 68

    Fig. 2.9 Semnificaia fizic a punctelor de control

    Uneori, se cunosc punctele discrete de contur 0 1, ,...., nt s s s= i se pune problema determinrii punctelor de control {pi}i . Relaia:

    ,0

    ( ) ( ), 0,n

    j i i k ji

    s p B s j n=

    = =x (2.10) poate fi rescris sub forma:

    k =B P x , (2.11)

    unde Bk , P i x sunt matrice de dimensiune (n+1)(n+1), (n+1)2, respectiv (n+1)2 cu elementele Bi,k (sj), pi i respectiv, x(sj). Cnd sj sunt locaiile nodurilor, atunci matricea Bk este o matrice nesingular, iar matricea punctelor de control se obine ca:

    1k=P B x . (2.12)

    Pentru funcii spline nchise i uniform eantionate, Bk devine o matrice circular, pentru care prima linie b0 este dat de:

    ( )0 0 1 1

    0,

    1 1

    ... ,0...0, ... ,

    -1unde , 0,i int eger ,2

    ct, .

    q q

    j k j

    j j j j

    b b b b b

    kb B s j q q

    s s t t j+ +

    =

    = = = = =

    b

    (2.13)

  • 69

    n cazul funciilor B-spline deschise, matricea Bk este apropiat de forma unei matrici Toeplitz cnd ,j js t j= .

    Not. n continuare se prezint un exemplu de calcul al funciilor B-spline pentru 3k = .

    cazul funciilor periodice Din relaiile (2.3) i (2.7) nodurile (locaiile de eantionare) sunt:

    [ ] ( )0 12 13 5 7, ,..., , , ,...,

    5 2 2 6nn n

    s s s

    =

    . (2.14)

    Pe baza relaiei (2.13), funciile de mixare B0,3(t) conduc la o matrice circular de forma:

    3

    6 1 11 1 ... 18

    1 1 6

    =

    B . (2.15)

    cazul funciilor neperiodice

    Din relaiile (2.3) i (2.6) punctele de legtur i nodurile rezult de forma:

    [ ] [ ]

    [ ] ( )( )0 1 3

    0 1

    , ,..., 0,0,0,1,2,3,..., 2, 1, 1, 1 ;

    2 3 11 3 5 7, ,..., 0, , , , ,..., .2 2 2 2 2

    n

    n

    t t t n n n n

    n ns s s

    + =

    =

    (2.16)

    Funciile de mixare neperiodice pentru 3k = se obin de forma:

    ( )

    ( )

    2

    0,3

    2

    21,3

    1 , 0 1( ) ,0 , 1 1

    3 2 2 , 0 12 3 3

    1( ) 2 , 1 2 ,20 , 2

    t ttt n

    t t

    t t t

    t n

  • 70

    ( )

    ( )

    ( )

    2

    2

    ,3

    2

    21,3

    2

    ,3

    0 , 0 21 2 , 2 12

    1 3( ) , 1 ,2 4

    1 1 , 120 , 1 1, 2,( 2)

    0 , 0 31( ) 3 , 3 2 ,23 5 2 , 2 12 3 3

    0 ,( )

    j

    n

    n

    t j

    t j j t j

    t t j j t j

    t j j t j

    j t n j n

    t n

    t t n n t n

    t n n t n

    t

    < + < = + +

  • 71

    Fig. 2.10 Aproximarea unui contur cu ajutorul funciilor B-spline quadrice:

    a) punctele de control impuse; b) funcii B-spline quadrice periodice; c) funcii B-spline quadrice neperiodice

    n practic, se dispune de un numr suficient de mare de puncte de eantionare ale conturului i pe baza exemplului prezentat n fig. 2.6 este evident c numrul punctelor de control pentru o reprezentare riguroas a conturului este mult mai mic. De aceea se cunote x(t) pentru t=0, 1, 3,..., m, unde m>>n. n continuare urmeaz s se determine soluia de interes pe baza unui sistem de ecuaii (m+1)(n+1):

    ,0

    ( ) ( ) , 0,n

    j i k j ii

    B p j m=

    = =x (2.19)

    Pentru estimarea punctelor de control {pi}i se poate aplica metoda celor mai mici ptrate. Prin intermediul unei indexri corespunztoare a punctelor de eantionare {i}i i prin alegerea raportului (m+1)/(n+1) sub forma unui numr ntreg, soluia oferit de metoda amintit mai sus necesit calculul inversei unei matrice circulare, invers pentru care exist prezentate n literatura de specialitate numeroase metode de calcul rapid.

    2.2.1.4 Semnturi

    Semnturile sunt reprezentri 1D ale (conturului) formei definite de distana de la un punct de referin fixat, de regul centroidul conturului:

    1 1

    0 0

    1 1, ,N N

    c n c ni i

    x x y yN N

    = =

    = = (2.20)

  • 72

    unde (xn, yn), 1,n N= reprezint un punct al conturului de interes, iar N este numrul punctelor/pixelilor conturului la fiecare punct de pe conturul respectiv. Aceast distan poate fi redat/ exprimat fie n funcie de unghiul la centru

    dintre punctul curent de pe contur i axa orizontal de referin not= dc(), fie n

    raport de abscisa curbilinie (reprezint lungimea conturului cuprins ntre punctul curent i punctul n care axa de referin intersecteaz conturul) not= dc(). Semnturile formei sunt reprezentri biunivoce (cunoscnd semntura,

    se poate reconstrui conturul formei).

    Fig. 2.11 Semntura contururilor unor forme simple, convexe

    Not. Cea mai des utilizat semntur a conturului formei este cea n

    funcie de unghiul la centru dc(), de aceea, n continuare, consideraiile urmtoare sunt specifice, n special, acestei reprezentri.

    Semnturile sunt caracteristici invariante la translaie. Invariana la rotaie se obine efectund o permutare ciclic a semnturii, n sensul aducerii punctului de raz maxim la 0 = . Invariana la factorul de scar se obine normaliznd dc prin raportarea la valoarea sa maxim, dcmax. Influena zgomotului asupra valorii maxime dcmax poate fi diminuat prin utilizarea n locul acesteia fie a valorii medii, fie a dispersiei razei dc.

    Este posibil ca, pentru anumite forme concave semntura n funcie de unghiul la centru s nu poat fi calculat, deoarece, pentru anumite unghiuri , intersecia dreptei corespunztoare acestei direcii cu conturul formei este format din mai multe puncte.

    Not. Problema respectiv nu apare ns n cazul utilizrii semnturii formei n funcie de abscisa curbilinie. Restricia general care se impune n acest caz, al semnturii bazate pe unghiul la centru, este ca punctul de referin ales s aparin nucleului formei.

  • 73

    Nucleul unei forme P este definit prin:

    { }( ) , [ ]Ker P x y P xy P= , (2.21)

    unde [xy] reprezint segmentul de dreapt definit de punctele x i y. Rezult c, n cazul formelor concave, nucleul formei este o mulime vid. Cteva aplicaii posibile ale semnturii contururilor formei sunt i urmtoarele:

    aproximarea unei forme prin dezvoltarea n serie Fourier a semnturii acesteia, urmat de trunchierea reprezentrii respective, cu aplicaie imediat n recunoaterea conturului unor forme vizuale (a se vedea referina bibliografic [5] n acest sens);

    plecnd de la observaia imediat c pentru o form poligonal n semntura acesteia poziia vrfurilor este marcat prin puncte unghiulare, se poate obine o nou metod de aproximare poligonal a unei forme oarecare;

    pe baza utilizrii semnturii conturului unei forme/pattern P se pot defini urmtorii parametri de tip geometric:

    1) raportul de simetrie

    [0, ]

    ( )( ) sup inf( )c

    x P c

    dS Pd

    =

    + ; (2.22)

    2) raportul de circularitate

    sup ( ( ) ( ))( )inf ( ( ) ( ))

    c c

    c c

    d dC Pd d

    + + =

    + + . (2.23)

    Aceti parametri geometrici pot fi utilizai cu succes ca i parametri

    regionali elementari n procesul ulterior de recunoatere a formelor (vizuale) de interes.

    dac dc() reprezint semntura conturului unei forme n funcie de unghiul la centru , atunci se definete momentul de ordin p, de forma:

    [ ]1

    0

    1 ( )N

    pp c

    id

    N

    =

    = , (2.24)

    respectiv momentul centrat de ordin p:

    [ ]1

    10

    1 ( )pN

    p ci

    m dN

    =

    = , (2.25)

  • 74

    unde N reprezint numrul de pixeli de pe contur. De asemenea, se definesc i momentele normalizate de ordin p, de forma:

    22

    22

    ,

    ( )

    .

    ( )

    pp p

    pp

    m

    mm

    m

    =

    =

    (2.26)

    Se demonstreaz c orice set complet de momente al unei forme permite individualizarea i reconstrucia formei respective, asemeni unei transformri unitare. Pentru aplicaii practice de recunoatere a formelor se pot reine doar anumite valorile ale unor momente de diferite ordine.

    Not. Detalii teoretice suplimentare pot fi obinute prin consultarea referinei bibliografice [4]. 2.2.1.5 Descriptorii Fourier Pornind de la reprezentarea conturului formei sub forma unei secvene complexe i periodice, z(n)=x(n)+iy(n), 0, 1n N= (unde N reprezint numrul pixelilor de pe conturul indexat), se poate calcula DFT 1D a acestei secvene, de forma:

    1

    0

    1 i2( )exp , 0, 1 ,N

    un

    t z n un u NN N

    =

    = = (2.27)

    unde {tu}u este setul descriptorilor Fourier. Transformrile geometrice elementare aplicate unui contur sau forme se manifest n cazul descriptorilor Fourier asociai noului contur prin operaii simple asupra acestora. Prin urmare:

    dac un contur este translatat cu

    0 0 0iz x y= + , (2.28)

    atunci noii descriptori Fourier rmn identici, mai puin cel corespunztor 1u = ;

  • 75

    efectul de scalare a conturului iniial se manifest printr-o scalare corespunztoare a setului de coeficieni {tu}u;

    modificarea punctului de start al unui contur are ca efect modularea coeficienilor iniiali {tu}u;

    rotaia conturului cu un unghi 0 conduce la apariia unui defazaj suplimentar constant al noilor descriptori Fourier etc. O sintez a celor mai importante proprieti ale descriptorilor Fourier este prezentat n tabelul 2.1:

    Tabelul 2.1 Proprietile descriptorilor Fourier Transformare Conturul transformat Descriptorii Fourier Identitate z(n) tu Translaie zr(n)= z(n)+z0 tru=tu+z0u Scalare zr(n)= z(n) tru=tu Punct de start

    zr(n)= z(n-n0) 02 i

    en u

    r Nu ut t

    = Rotaie 0i( ) ( )erz n z n = 0ieru ut t

    = Reflexie 0i2*( ) ( ) 2rz n z n e = + 0i2*( ) 2 ( )rut t u e u

    = +

    Pe baza proprietilor prezentate n tabelul 2.1, se pot deduce paii necesari pentru a obine invariana setului de descriptori Fourier asociai unui contur sau forme la transformrile geomentrice elementare. Astfel:

    pasul I: invariana la punctul de referin, translaie, reflexie (fa de o dreapt) i rotaie se obine prin considerarea setului urmtor de descriptori Fourier:

    { } , 1, 1u ut u N= ; (2.29)

    pasul II: invariana la scalare se obine prin considerarea urmtorului set de coeficieni Fourier:

    , 1, 1i este primul descriptor Fourier nenulu kk u

    t u N tt

    =

    . (2.30)

    Not. Posibilitatea de a obine prin operaii simple invariana

    descriptorilor Fourier la transformrile geometrice elementare poate fi utilizat cu succes n procesul ulterior descrierii formelor de interes, i anume recunoaterea acestora. n general, avnd la baz o serie de consideraii

  • 76

    experimentale, se demonstreaz c 3 la 5 descriptori Fourier sunt suficieni pentru a obine scoruri de bun recunoatere a formelor de interes foarte bune. De asemenea, descriptorii Fourier sunt caracteristici de form regenerative. Numrul de descriptori necesari pentru reconstrucia formei originale depinde n foarte mare msur de alura conturului formei respective i de acurateea dorit. O alt aplicaie a descriptorilor Fourier este i utilizarea acestora la potrivirea unor forme similare (boundary matching), chiar dac aceste forme au mrimi i orientri diferite. Dac se consider seturile de descriptori Fourier

    { } { }(1) (2)iu uu ut t asociate la dou contururi diferite, z(1)(n), respectiv z(2)(n),

    forma acestor contururi va fi similar dac:

    0

    0 0 0

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

    ( , , , ) min ( ) ( ) 0N

    z n nd z n z n z n n e z

    =

    = + . (2.31)

    Parametrii z0, , n0 i 0 rezult din impunerea condiiei de minimizare a

    efectelor translaiei, scalrii, punctului de start i, respectiv, rotaiei. Pentru cazul cnd contururile anterioare sunt normate, adic

    1 1

    (1) (2)

    0 0

    ( ) ( ) 0N N

    n nz n z n

    = =

    = = , (2.32)

    atunci pentru o translaie n0 impus, distana din relaia (2.31) este minim dac:

    0(3)

    0

    2(2)

    0,

    cos( ),

    u uu

    uu

    z

    t u

    t

    =

    + +

    =

    (2.33)

    i:

    *

    (3)

    0 (3)

    i(1) (2) (3) (3)0

    sin( )tg ,

    cos( )

    2unde: e ,i . u

    u uu

    u uu

    u u u u

    t u

    t u

    nt t t tN

    +

    = +

    = =

    (2.34)

  • 77

    Pe baza valorilor i 0 rezultate din relaiile (2.33) i (2.34) se poate calcula distana minim:

    02i( )(1) (2)min[ ( )] min e uu u

    ud d t t +

    = = (2.35)

    Distana d() poate fi evaluat pentru fiecare ( )0n = , 0 0, 1n N= i intereseaz distana cu valoare minim care este o msur a similaritii celor dou contururi. Rezultatele experimentale au dovedit n mod convigtor c descriptorii Fourier sunt foarte utili la descrierea curbelor plane nchise, deoarece ei permit o recunoatere uoar pentru forme rotite i scalate, afectate de zgomot. n acelai timp, aceti descriptori nu necesit informaii suplimentare, dependente de tipul aplicaiei, ci constituie o metod standard de descriere a formelor (vizuale). 2.2.2 Descriptori regionali Descriptorii regionali desemneaz proprieti ale regiunilor de interes, caracteristici care se evaluez pe baza tuturor pixelilor acestora. Complexitatea descriptorilor propui n literatura de specialitate este o funcie de caracteristicile aplicaiilor de interes.

    n continuare sunt prezentai cei mai interesani descriptori regionali din punct de vedere al succesului etapei ulterioare de recunoatere a formelor.

    2.2.2.1 Descriptori regionali elementari

    Cei mai importani descriptori elementari regionali sunt: aria este una din caracteristicile cele mai simple ale regiunilor i poate

    fi definit ca fiind numrul total de pixeli ai unei regiuni sau poate avea i o anumit dimensiune fizic real (dac se cunosc condiiile concrete de achiziie a imaginilor). Aria poate fi calculat cu uurin i cu ajutorul codului Freeman asociat conturului regiunii de interes. Conform referinei bibliografice [17], acest algoritm de calcul al ariei este fundamentat pe urmtoarele observaii simple: se definete o linie de baz situat la o anumit coordonat vertical arbitrar, B. Pentru simplitate poate fi considerat prima linie din imagine i n acest caz, B=0. Prin urmare, aria poate fi considerat ca fiind dat de coloanele verticale de diferite lungimi care rezult. Aria unei coloane verticale este egal cu lungimea acesteia, l. Din figura de mai jos se observ c lungimea l este tocmai diferena distanelor de la cele

  • 78

    dou extremiti ale coloanei la linia de baz. n consecin, presupunnd cunoscut codul lan obinut prin urmrirea conturului regiunii n sens trigonometric, atunci aria coloanei se obine ca diferen ntre coordonatele verticale curente obinute n urma parcurgerii poriunii de jos, respectiv de sus ale coloanei n discuie. Se observ c pentru orice coloan poriunea inferioar este parcurs de la stnga spre dreapta corespunztor direciei codificate cu 0, n timp ce poriunea superioar este parcurs de la stnga spre dreapta corespunztor direciei codificate cu 2. De asemenea, se observ c deplasarea n jos cu direcia de cod 3 incrementeaz poziia vertical curent, spre deosebire de deplasarea n sus, cu direcia de cod 1 care decrementeaz poziia vertical curent. n continuare, se prezint forma final a algoritmului respectiv (pentru cazul utilizrii codului lan cu patru direcii):

    1) pasul I: se definesc i se iniializeaz variabilele 0aria = , _ 0poziie vertical = (sau orice alt valoare);

    Fig. 2.12 Calculul ariei unei regiuni cu ajutorul codului Freeman

    2) pasul II: pentru fiecare simbol din codul lan, se efectueaz urmtoarea

    succesiune de operaii: a) dac simbolul este 0, atunci aria=aria+poziie_vertical; b) dac simbolul este 1, atunci poziie_vertical =poziie_vertical-1; c) dac simbolul este 2, atunci aria=aria-poziie_vertical; d) dac simbolul este 3, atunci poziie_vertical =poziie_vertical+1. Rezultatul final este coninut n variabila aria. Not. Un algoritm similar poate fi obinut i n cazul utilizrii codului lan

    cu opt direcii. n final se impune a fi fcut urmtoarea observaie util: dac pentru calculul ariei unei regiuni se utilizeaz algoritmul de urmrire a conturului prezentat n deschiderea paragrafului 2.2.1.1, atunci aria obinut este mai mic dect valoarea sa real. Pentru corecia acestei deficiene o soluie ar fi utilizarea codului lan al muchiilor, care urmrete muchiile dintre pixelii regiunii de interes i fundal,

  • 79

    situaie n care aria determinat cu ajutorul acestui algoritm este cea real. Modalitatea de obinere a codului lan al muchiilor este asemntoare cu cea din cazul codului lan standard.

    Not. n referina bibliografic [17] se prezint n detaliu structura algoritmului de obinere a codului lan al muchiilor. n fig. 2.13 se prezint un exemplu practic de calcul al ariei unei regiuni cu ajutorul codului lan standard i, respectiv, cu ajutorul codului lan al muchiilor (se pot remarca diferenele care apar ntre cele dou metode de calcul). O alt modalitate rapid de calcul a ariei unei regiuni este cea cu ajutorul reprezentrilor poligonale (a se revedea n acest sens paragraful 2.2.1.2).

    Fig. 2.13 Calculul ariei:

    a) cu ajutorul codului lan standard; b) cu ajutorul codului lan al muchiilor

    Dac (xi, yi) sunt coordonatele vrfurilor unui poligon cu N laturi care aproximeaz conturul unei regiuni de interes i (x1, y1)=(xN,, yN), atunci aria acestei regiuni este dat de relaia:

    1 11

    0,5N

    i i i ii

    aria x y x y+ +=

    = ; (2.36)

    perimetrul este, de asemenea, o caracteristic elementar regional uor de calculat i, pentru cazul unei imagini digitale, este definit ca numrul pixelilor de pe contur. n cazul contururilor 8-conexe, pixelii situai pe direcii diagonale ale conturului vor fi ponderai cu 2 . Perimetrul este o caracteristic mai sensibil la zgomot dect aria. De asemenea, rezoluia unei imagini influeneaz ntr-o mare msur rezultatele determinrii perimetrului (efectul zgomotului este mai puternic n cazul imaginilor cu rezoluie mare). O modalitate de eliminare a efectului zgomotului

  • 80

    ar consta n filtrarea conturului regiunii de interes, valoarea perimetrului fiind una mai sczut;

    complexitatea formei este o caracteristic global larg utilizat, definit prin:

    21 (perimetrul)4 aria

    K =

    (2.37)

    Not. Factorul 1/4, omis n unele definiii, conduce la valoarea minim

    K=1 care se obine numai pentru o regiune sub form de disc. n unele lucrri de specialitate, complexitatea formei mai este denumit i rotunjime sau compactizare;

    direcia formei poate fi estimat pe baza orientrii axei majore, dar exist i definiii ale acesteia mai complexe;

    energia de ndoire (bending energy) a unei forme poate fi interpretat ca energia necesar pentru a ndoi o bar metalic astfel nct aceasta s se muleze pe forma respectiv. n cazul unei imagini discrete, expresia acestei energii pentru un contur ce conine N pixeli este de forma:

    [ ]1

    2

    0

    1 ( ) ,N

    kBE k

    N

    =

    = (2.38) unde (k) este curbura local a conturului. Calculul dat de formula (2.38) este eficient dac se utilizeaz codul lan, cod ce conine ntreaga informaie despre contur;

    numrul lui Euler este un descriptor de tip topologic, avnd avantajul de a fi invariant la distorsiunilor geometrice neliniare ale imaginii. El este dat de formula:

    (numrul de componente) (numrul de guri)E = . (2.39)

    Not. n fig. 2.14 este prezentat un exemplu practic de calcul al numrului lui Euler pentru diferite forme simple;

    Fig. 2.14 Numrul lui Euler pentru diferite forme simple

  • 81

    nveliul convex al unei regiuni se definete ca fiind poligonul convex de arie minim care include regiunea respectiv. Strns legat de aceast noiune este i termenul de deficiena convex;

    deficiena convex care reprezint diferena dintre nveliul convex i regiunea/ forma de interes, n conformitate cu fig. 2.15.

    n finalul paragrafului de fa se impune a fi fcut i urmtoarea observaie foarte util: aceti descriptori regionali elementari sunt importani doar n msura n care utilizarea lor conduce la eliminarea eventualelor

    Fig. 2.15 nveliul i deficiena convex pentru o form oarecare

    ambiguiti (de clasificare, ca finalitate) determinate de descriptorii consacrai din literatura de specialitate (numrul de form, semntura formei, descriptorii Fourier, skeletonul morfologic etc).

    2.2.2.2 Momente O imagine f(x,y) poate fi interpretat ca fiind densitatea de probabilitate corespunztoare unei variabile aleatoare 2D, pentru care este uzual caracterizarea sa statistic cu ajutorul momentelor. Momentul (geometric) de ordin ( )p q+ se definete ca:

    ( ), , d d , , 0,1,2,...p qp qm x y f x y x y p q

    = = (2.40) sau n cazul imaginilor discrete:

    ( ), , .p qp qx y

    m x y f x y

    = =

    = (2.41)

  • 82

    Not. Evident, limitele de nsumare din relaia (2.41) se vor restrnge la coordonatele pixelilor regiunii de interes (ale crei momente se evalueaz). Funcia caracteristic a imaginii f(x,y) se definete ca transformata sa Fourier conjugat:

    ( ) ( ) 1 22 i( )1 2, , e d dx yF f x y x y

    +

    = . (2.42)

    Funcia de generare a momentelor imaginii f(x,y) se definete ca:

    ( ) ( ) 1 2( )1 2, , e d dx yM f x y x y

    +

    = . (2.43) Pe baza relaiilor (2.40) i (2.43), momentul de ordin ( )p q+ se rescriu de forma:

    ( )1 2, 1 2

    1 2

    ,pentru 0

    p q

    p q p qM

    m+

    = = =

    . (2.44)

    Fundamentarea teoretic a utilizrii descriptorilor de tip moment se

    bazeaz pe teorema reprezentrii momentului (a se consulta n acest sens i referina bibliografic [27] ).

    Teorema reprezentrii momentului: setul infinit de momente {mp,q}p,q=0,1,2... determin n mod unic funcia f(x,y) i reciproc.

    Not. Demonstrarea acestei teoreme presupune parcurgerea urmtoarelor etape: dezvoltarea n serie de puteri a termenului exponenial din relaia (2.42), schimbarea ordinii de sumare i integrare, utilizarea relaiei (2.40) i aplicarea transformatei Fourier ambilor membri ai egalitii respective. n consecin, se obine urmtoarea formul de reconstrucie:

    ( ) 1 22 i( ) , 1 21 20

    (2 i), e d d! !

    p qp qx y

    p qp

    f x y mp q

    + +

    =

    = (2.45)

    Aceast formul nu este practic, deoarece nu se poate schimba ordinea de integrare i sumare ntruct transformata Fourier a termenului (2i1)p nu este mrginit. De aceea, seria definit de relaia (2.45) nu poate fi trunchiat pentru a gsi o aproximare a funciei f(x,y), ceea ce constituie un dezavantaj major.

  • 83

    Totui, dac se cunosc momentele funciei f(x,y) pn la ordinul N, este posibil s se determine o funcie continu g(x,y) ale crui momente de ordin pn la p q N+ = se potrivesc cu cele ale funciei iniiale, deci:

    , , ,0

    ( , )i i ji j i j p qi j N

    g x y g x y g m +

    = (2.46)

    Not. Dezavantajul metodei prezentate mai sus este acela c odat coeficienii {gi,j}i,j determinai, acetia se schimb prin modificarea numrului de momente considerate, adic setul de ecuaii ce trebuie rezolvat pentru determinarea acestora crete cu creterea lui N. Avnd n vedere relaia (2.40), se definete momentul (geometric) centrat de ordin ( )p q+ de forma:

    ( ) ( ) ( ), , ,p q

    p q c cx y

    x x y y f x y

    = =

    = (2.47)

    unde:

    1,0 0,1

    0,0 0,0,c c

    m mx y

    m m= = (2.48)

    Not. Pentru imagini binare avem c f(x,y)=1 i 0,0 este tocmai aria

    formei de interes. Din relaiile (2.40) i, respectiv, (2.47) se observ c setul de momente {p,q} este practic proiecia funciei f(x,y) pe baza de polinoame {xpyq}, baz care ns nu este ortogonal. O alternativ ar fi utilizarea polinoamelor ortogonale Legendre. Proiecia pe noua baz va conduce la obinerea unui set de momente ortogonale. n practic, se opereaz cu un set finit de momente, de forma p q M+ = , care ns conduc la o expresie aproximant pentru forma de interes f(x,y). Este necesar a fi fcut i remarca foarte important c, folosirea acestor momente de natur statistic pentru caracterizarea unei forme nu asigur ndeplinirea principiului invarianei. De aceea au fost introduse momentele statistice invariante. Momentele statistice invariante la translaie sunt momentele statistice centrate definite de relaia anterioar (2.47).

    Momentele statistice invariante la translaie i scalare sunt definite de:

    ,,

    0,0

    , 1 , 2,3,...2

    p qp q

    p q p q

    + = = + + =

    (2.49)

  • 84

    Invarianii la translaie, scalare i rotaie ai unei forme, obinui n condiiile folosirii unor momente statistice de ordin cel mult trei ( 3M = ), sunt n numr de apte i sunt dai de relaiile urmtoare:

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

    ( )( ) ( ) ( )

    ( )

    1 2,0 0,22 2

    2 2,0 0,2 1,1

    2 23 3,0 1,2 0,3 2,1

    2 24 3,0 1,2 0,3 2,1

    2 25 3,0 1,2 3,0 1,2 3,0 1,2 0,3 2,1

    2 20,3 2,1 0,3 2,1 0,3 2,1 3,0 1,2

    6 2,0 0,2 3

    ;

    4 ;

    3 3 ;

    ;

    3 3

    3 3 ;

    H

    H

    H

    H

    H

    H

    = +

    = +

    = +

    = + + +

    = + + + + + + + +

    = ( ) ( )( ) ( )

    ( )( ) ( ) ( )

    ( ) ( ) ( )

    2 2,0 1,2 0,3 2,1

    1,1 3,0 1,2 0,3 2,1

    2 27 0,3 2,1 0,3 2,1 0,3 2,1 3,0 1,2

    2 20,3 2,1 3,0 1,2 0,3 2,1

    4 ;

    3 3

    3 3 .

    H

    + + +

    + + + +

    = + + + + +

    (2.50)

    Not. Momentele {Hi} 1,7i = sunt cunoscute n literatura de specialitate i

    sub denumirea de momente invariante Hu (Hu, 1962). Eficiena acestor invariani const n modul rapid de calcul i posibilitatea

    de ai utiliza cu succes pentru recunoaterea formelor geometrice convexe. De asemenea, se demonstreaz c pentru momente de ordin M (M3), sunt M+1 momente care rmn neschimbate n valoare absolut la reflexie i rotaie. Relaiile ntre momentele invariante i mp,q devin mult mai complicate pentru ordine superioare. Fiind invariante la transformri de coordonate liniare, momentele invariante sunt foarte utile n cadrul problemelor de recunoatere a formelor. Utiliznd, spre exemplu, M astfel de momente, o imagine poate fi reprezentat ca un punct n spaiul M-dimensional. Aceasta conduce la conversia problemei de recunoatere a formei ntr-o problem standard din teoria deciziilor, pentru care sunt disponibili diferii algoritmi de abordare a acesteia. Momentele invariante sunt utile i n analiza de imagini, cu observaia util c n practic calculul optic al acestora este cel mai eficient (timp i resurse de calcul minime). O form de exprimare mai adecvat pentru momentele unei imagini este sub forma momentelor (pseudo-)Zernike.

  • 85

    2.2.2.3 Momente (pseudo-) Zernike

    momente Zernike Polinoamele Zernike sunt un set infinit de polinoame ortogonale peste cercul unitate, referite prin indicele n numit ordin, respectiv prin indicele l numit perioad de repetiie. Pentru un ordin ( n) sunt (n+1)(n+2)/2 polinoame liniar independente. Forma standard de reprezentare a polinoamelor Zernike este cea n coordonate polare:

    i( , ) ( )e lnl nlV x y R r= , (2.51)

    unde n + , iar l astfel nct expresia (nl) este par i l n.

    Not. Transformarea ( ) ( ), ,x y r este cea uzual:

    cossin

    x ry r=

    = . (2.52)

    Rnl(r) este un polinom radial de grad n, dat de urmtoarea formul:

    ( ) ( )2 20

    1 !( )

    ! ! !2 2

    n li

    n inl

    i

    n iR r r

    n l n li i i

    =

    =

    +

    . (2.53)

    O funcie f(x,y) definit peste cercul unitate ( )2 2 1x y+ poate fi aproximat cu ajutorul unui set finit de M ( )M < polinoame Zernike, de forma:

    Re Re0 0

    0

    Re Re Im Im

    0

    ( , ) ( , ) ( , )

    2[ ( , ) ( , )],

    M n

    M nl nl n nn l n n

    n l par

    nl nl nl nln l

    f x y A V x y A V x y

    A V x y A V x y

    = = =

    >

    = = +

    +

    (2.54)

    unde prin AnlRe, VnlRe i AnlIm, VnlIm s-a notat partea real, respectiv partea imaginar pentru Anl i, similar, pentru Vnl.

  • 86

    Coeficienii Anl din relaia (2.54), denumii i momente Zernike, sunt dai de urmtoarea expresie:

    ( ) ( )2 2

    *

    1

    1 , , d dnl nlx y

    nA f x y V x y x y+

    +=

    (2.55)

    sau n cazul imaginilor digitale/discrete:

    ( ) ( )2 2

    *

    1

    1 , ,nl nlx y

    x y

    nA f x y V x y

    +

    +=

    . (2.56)

    Not. n referinele bibliografice [20] i [22] sunt prezentate consideraiile

    teoretice care stau la baza obinerii invarianilor Zernike (la rotaie, translaie i scalare). Aceti invariani pot fi exprimai cu ajutorul momentelor centrate date de relaia (2.49), sub urmtoarea form compact:

    ( )

    ( )

    ( ) ( )

    ( ) ( )

    ( )( ) ( ) ( ){( )

    1 2,0 0,2

    2 22 2,0 0,2 1,12

    2 23 0,3 2,1 3,0 1,22

    2 24 0,3 2,1 3,0 1,22

    2 25 0,3 2,1 0,3 2,1 0,3 2,1 3,0 1,24

    3,0 1,2 3,0

    3 2 1 ;

    9 4 ;

    16 3 3 ;

    144 ;

    13824 3 3

    3

    Z

    Z

    Z

    Z

    Z

    = +

    = +

    = +

    = + + +

    = + + +

    +

    ( ) ( ) ( ) }( ) ( ) ( ){( )( )}

    2 21,2 3,0 1,2 0,3 2,1

    2 26 0,2 2,0 3,0 1,2 0,3 2,13

    1,1 0,3 2,1 3,0 1,2

    3 ;

    864

    4 .

    Z

    + +

    = + + +

    + + +

    (2.57)

    De asemenea, se demonstreaz c pentru un ordin n al momentelor

    Zernike impus, exist un numr de n+1 invariani independeni, numr identic cu cel al momentelor geometrice invariante de acelai ordin.

  • 87

    momente pseudo-Zernike Un alt set de polinoame ortogonale peste cercul unitate ( )2 2 1x y+ este i setul polinoamelor pseudo-Zernike, definit prin relaia generic:

    i( , , ) ( )e lnl nlW x y r S r= , (2.58)

    unde n + , iar l , cu aceeai semnificaie ca i n cazul polinoamelor Zernike. Snl este un polinom radial n r de grad n, de forma:

    ( ) ( )( ) ( ) ( ),

    1 1 !( ) , unde :

    ! ! 1 !

    n ini

    n l nli nlii l

    n iS r D r D

    n i i l l i

    =

    + += =

    + + (2.59)

    Legtura cu polinoamele Zernike definite anterior este asigurat de urmtoarea relaie:

    , 2 1, (2 1)( ) ( )n l n lrS r R r + += , (2.60)

    unde R(r) este polinomul radial Zernike. Not. Pentru un ordin ( n), exist ( )21n + polinoame pseudo-Zernike.

    O funcie f(x,y) definit peste cercul unitate poate fi aproximat cu ajutorul unui set finit de Mp (Mp

  • 88

    momentele Zernike date de relaia (2.55), respectiv momentele pseudo-Zernike introduse de relaia (2.61). 2.2.2.4 Momente Fourier -Mellon Funcia de baz Fourier-Mellon ortogonal de ordin p i perioad de repetiie q se definete ca:

    i( , ) ( )e pqpq pU Q = , (2.63)

    unde p + , q , iar (, ) sunt coordonatele polare, n conformitate cu relaia (2.52). Qp este un polinom radial dat de:

    ( ) ( )( ) ( )0

    1 2 1 !( )

    ! ! 1 !

    spp s

    ps

    p sQ

    s p s p s

    =

    + =

    + . (2.64) Fie f o funcie complex peste discul unitate. Momentul ortogonal Fourier-Mellon al funciei f de ordin p i perioad de repetiie q se definete ca:

    ( ) 1 ,fpq pqp f U+

    = , (2.65)

    unde . reprezint produsul scalar Euclidian de forma:

    ( ) ( ) { }2

    2 2 2 2, , , d d , unde: ( , ) 1 .D

    f g f x y g x y x y D x y R x y= = + (2.66) n continuare se poate demonstra c relativ la momentele ortogonale Fourier-Mellon sunt adevrate urmtoarele proprieti:

    1) ( ) ( )( )f fp q pq

    = ;

    2) (0) ( 1) ( 1)ppQ p= + ;

    3) 1,2 2p p

    Q Qp

    =+

    ;

    4) 1

    0

    1( ) ( ) d2 2p q pq

    Q Qp

    = + ;

    5) ,1pq uv pu qv

    U Up

    = +

    ;

  • 89

    6) 1

    ( ) ( 1) (2,2, )pp pp

    Q Gp+

    =

    , unde Gn(p,q,) sunt polinoamele

    Courant-Hilbert Jacobi definite n conformitate cu referina bibliografic [20];

    7)

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

    0 20

    ( )

    2

    1 2 1 ! 12 2 (1 )! ! 2 ! 2

    0 pentru 0

    unde funcia este de forma:

    :0, dac 0 0,5

    ( , )1, altfel

    spap p s

    sapq

    p sp

    s p s p s

    q

    a

    a D

    a

    +=

    + = +

    + =

  • 90

    ( ) ( )( )2 2 22 0,3 3,0 2,1 1,2 0,3 1,2 2,1 2,1 3,0 1,22

    3 0,4 4,0 1,3 3,1 2,22 2 3

    4 4,0 2,2 0,4 3,1 2,2 1,3 4,0 1,3 0,4 3,1 2,2

    4 ;

    4 3 ;

    2 .

    B

    B

    B

    =

    = +

    =

    (2.68)

    Not. Pentru detalii teoretice suplimentare se poate consulta referina

    bibliografic [32]. momentele Legendre

    O funcie bidimensional f(x,y) poate fi descris n mod unic prin intermediul coeficienilor Legendre:

    ( ) ( ) ( )1 1

    2 2, ,

    1 1

    d d1 1 , d dd d

    p pp qp q p q p pl K x y f x y x yx y

    = , (2.69)

    cu , 1,p q = i unde:

    ,1 10,5 0,5

    2 ! 2 !p q p qK p q

    p q= + + . (2.70)

    Coeficienii definii de ecuaia (2.69) se demonstreaz c pot fi scrii ca o sum dubl de forma:

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

    2 1 2 1, ,

    4

    p q

    p q i ji j

    p ql C p i C q j m

    = =

    + += , (2.71)

    unde ( , )i ( , )C p i C q j sunt constante independente de variabilele x i y, iar

    , ,{ }i j i jm sunt momentele geometrice introduse de relaia (2.40). n continuare, spre exemplu, prin substituirea n relaia anterioar a

    , ,cui j i jm (a se vedea i relaia (2.49) n acest sens), se obine setul momentelor Legendre, momente care sunt invariante la transformrile geometrice elementare. De asemenea, n conformitate cu referina bibliografic [5] se poate demonstra c setul momentelor Legendre astfel obinut, prin transformri adecvate, poate fi fcut invariant la transformrile afine generale (aici mi,j este substituit cu momentele (geometrice) afine invariante affine,i jm ).

    momente invariante Taubin Taubin i Cooper (1992) au definit momentele afine invariante pe baza introducerii conceptului de matrice de covarian. Plecnd de la momentele

  • 91

    centrate de ordinul doi ale unei forme arbitrare S, acetia au calculat urmtoarea matrice bidimensional:

    ' '2,0 1,1 ,'

    11 ,' '0,01,1 0,2

    , unde:( )

    p qp q m S

    = =

    M . (2.72)

    Not. Se cunoate faptul c transformrile geometrice elementare ale unei

    forme oarecare sunt cazuri particulare ale transformrilor afine aplicate aceleiai forme. n continuare pe baza matricei M11 i a utilizrii descompunerii Cholesky se determin o matrice inferior triunghiular L de forma:

    1,111

    2,1 2,2

    0, cu proprietatea c: T

    l

    l l

    = =

    L LM L I . (2.73)

    n consecin cu ajutorul matricii L se determin noile momente

    ', , cu 2p q p q + > , care satisfac ecuaia:

    ( ) ( ) ( )' , 1,1 2,1 2,20,0 ( , )

    1( )

    p qp q c c c

    x y Sl x x l x x l y y

    m S = + , (2.74)

    unde ( , )c cx y este centroidul formei S, dat de relaia (2.48). Pentru momentele de ordin trei i patru, se gsesc urmtoarele dou matrici:

    ' ' '1 3,0 2,1 1 1,2'

    12 ' ' '1 2,1 1,2 1 0,3

    ' ' '2 4,0 2 3,1 2 2,2

    ' ' ' '22 1 3,1 2,2 1 1,3 1 2

    ' ' '2 2,2 1 1,3 2 0,4

    ,

    1respectiv , unde:i 0,5.2

    c c

    c c

    c c c

    c c c c

    c c c

    = = = =

    M

    M

    (2.75)

    n final setul de opt momente afine invariante Taubin {Ti} 1,8i = pentru forma S este alctuit din:

    a) cele dou valori proprii ale matricei simetrice bidimensionale ' '12 12

    TM M ;

  • 92

    b) cele trei valori proprii ale matricei simetrice '22M ; c) cele dou valori proprii ale matricei simetrice bidimensionale

    ' ' '12 22 12

    TM M M ;

    d) scalarul ' '4,0 0,41 ( ).4 +

    Not. Pentru detalii teoretice suplimentare privind invarianii Taubin se poate consulta referina bibliografic [32].

    momente invariante Flusser Flusser i Suk (1993) au definit urmtorul set de ase momente afine invariante, set care este invariant pentru transformrile afine generalizate bidimensionale:

    ( )

    (

    )( ) (

    ) ( )

    21 2,0 0,2 1,14

    0,0

    2 2 32 3,0 0,3 3,0 2,1 1,2 0,3 3,0 1,210

    0,0

    3 2 20,3 2,1 2,1 1,2

    23 2,0 2,1 0,3 1,2 1,1 0,3 3,07

    0,0

    22,1 1,2 0,2 3,0 1,2 2,1

    3 3 24 2,0 0,3 2,011

    0,0

    1 ;

    1 6 4

    4 3 ;

    1

    ;

    1 6

    F

    F

    F

    F

    =

    = + +

    +

    =

    +

    =

    ( 21,1 1,2 0,3 2,0 0,2 2,1 0,32 2 22,0 0,2 1,2 2,0 1,1 2,1 0,3 1,1 2,0 0,2 3,0 0,3

    3 22,0 1,1 0,2 2,1 1,2 1,1 3,0 0,3 2,0 0,2 3,0 1,2

    2 2 2 22,0 0,2 2,1 1,1 0,2 3,0 1,2 1,1 0,2 3,0

    6

    9 12 6

    18 8 6

    9 12 6

    +

    + + +

    +

    + + )( )

    ( )

    3 22,1 0,2 3,0

    35 4,0 0,4 3,1 1,2 2,26

    0,0

    2 2 36 4,2 0,4 2,2 3,1 2,2 1,2 4,0 1,2 0,4 3,1 2,29

    0,0

    ;

    1 4 3 ;

    1 2 .

    F

    F

    +

    = +

    = +

    (2.76)

    Not. n referina bibliografic [32] se poate regsi modalitatea concret

    de construcie a setului de invariani Flusser. De asemenea, este interesant de amintit aici i rezultatele teoretice

    raportate n referina bibliografic [11], unde se propune o metod de

  • 93

    normalizare pentru obinerea invarianilor asociai diferitelor seturi de momente la transformrile afine de baz (n acest sens, un exemplu concret este reprezentat de determinarea efectiv a momentelor afine invariante Fourier i Zernike).

    2.2.3 Descriptori de textur Texturile sunt structuri repetitive cu regularitate i complexitate variabil,

    prezente n imagini. Varietatea texturilor naturale i artificiale fac dificil ns o definiie formal riguroas a noiunii de textur.

    Texturile pot fi utilizate att pentru segmentarea, ct i pentru descrierea regiunilor. n aceast direcie, este necesar definirea i cuantificarea proprietilor texturilor printr-un numr relativ redus de caracteristici. Caracteristicile texturilor se pot defini prin mai multe metode, cele mai importante fiind cele statistice, spectrale i, respectiv, structurale. n consecin:

    caracteristici statistice Texturile care se ntlnesc n natur au, n general, un caracter aleator, de

    aceea abordarea lor statistic este cea mai potrivit metod de caracterizare a acestora. n aceast ordine de idei, momentele histogramelor locale sau regionale constituie cele mai simple caracteristici statistice ale texturilor, iar dintre acestea dispersia (momentul centrat de ordinul doi ) f2 are o semnificaie aparte. Se poate introduce o msur a netezimii texturii pe baza dispersiei, de forma:

    211

    1 fR =

    + . (2.77)

    n regiuni cu nivel de gri constant, 0R = . Pe msur ce regiunea prezint

    un contrast local mai mare, R1. Momentele impare sunt nule la histogramele simetrice. Momentele de

    ordin superior permit diferenierea ntre regiunile cu medii de gri i dispersii egale, dar cu legi de distribuie a nivelurilor de gri diferite. Caracteristicile de textur deduse pe baza de histogramei sunt invariante la translaie i rotaie, ceea ce poate constitui un avantaj important. Un dezavantaj major al caracteristicilor bazate pe histograme este pierderea complet a informaiilor referitoare la dispunerea spaial a nivelurilor de gri. O metod posibil de ncorporare n analiza statistic a informaiei spaiale este de a construi histogramele de ordin superior.

  • 94

    n acest sens, literatura de specialitate prezint o serie de descriptori statistici de textur mult mai puternici i care sunt definii cu ajutorul histogramei de ordin doi. Acetia sunt:

    1) probabilitatea maxim:

    { }1 , ,max j k j kM c= ; (2.78)

    2) contrastul:

    22 ,( ) j k

    j kM j k c= ; (2.79)

    3) energia:

    2

    3 ,j kj k

    M c= ; (2.80)

    4) entropia:

    4 , ,logj k j kj k

    M c c= , (2.81) unde C reprezint versiunea normalizat a histogramei de ordinul doi, iar cj,k este elementul su general.

    Not. n referina bibliografic [17] se prezint un exemplu practic de algoritm pentru calculul histogramei de ordinul doi a unei imagini.

    Dincolo de posibilitile de interpretare intuitiv pentru fiecare astfel de descriptor n parte, acetia trebuie vzui ca un ansamblu, denumit i vector al caracteristicilor statistice de textur.

    caracteristici spectrale Prezena unor structuri repetitive n imagini poate fi detectat mai eficient

    n domeniul transformatei Fourier, unde acestea se manifest prin concentrri ale valorilor spectrale, dect n domeniul spaial, prin operatori locali. Dup detecia i eliminarea componentelor periodice rmn doar structurile neperiodice ale imaginii, care pot fi analizate n continuare prin metodele statistice descrise anterior.

    Un instrument de analiz mai performant l ofer tehnicile multirezoluie, un exemplu n acest sens fiind realizarea descompunerii imaginii, corespunztor diferitelor benzi de frecven prin tehnica piramidei laplaciene.

  • 95

    Not. Pentru detalii teoretice suplimentare referitoare la tehnicile multirezoluie de analiz a unei imagini se poate consulta referina bibliografic [17].

    caracteristici structurale

    n acest caz, se ncearc descrierea texturilor prin sintez, folosind ca descriptori forme elementare (texeli sau primitive) deterministe, care se ansambleaz pe baza unui set finit de reguli. Un texel se poate izola ntr-o imagine prin identificarea unui grup de pixeli care au anumite proprieti invariante i care se repet n imagine. Texelul poate fi individualizat prin intermediul nivelului propriu de gri, prin form, prin omogenitate sau prin intermediul unor proprieti locale, de tipul mrimii, orientrii sau histogramei de ordinul doi. Relaiile spaiale dintre texeli pot fi caracterizate pe baza anumitor reguli deterministe de poziionare, reguli care pot fi exprimate n termeni de adiacen, distan minim, periodicitate etc., prin urmare se vorbete despre o textur puternic. Pentru cazul texelilor plasai aleatoar, regulile de poziionare pot fi exprimate n funcie de mrimi ca: densitatea contururilor, conectivitate etc., acum vorbindu-se despre o textur slab. 2.2.4 Descriptori morfologici Spre deosebire de abordarea clasic a prelucrrii imaginilor bazat pe fundamentele teoretice ale prelucrrii semnalelor multidimensionale, morfologia matematic realizeaz o abordare a prelucrrii imaginilor axat pe noiunea de form. Specific oricrei prelucrri morfologice este faptul de a considera imaginea de interes ca fiind un ansamblu (o mulime de pri componente) asupra cruia se aplic transformri a cror esen rezid n comparaia cu mulimi mai simple, numite elemente structurante. Prin intermediul acestor transformri se urmrete, n principal, extragerea unor forme mai relevante (simple) din formele iniiale (complexe) ale imaginii. Pentru o nelegere adecvat a fundamentelor teoretice care stau la baza obinerii descriptorilor morfologici se prezint, pe scurt, cele mai importante transformri morfologice. 2.2.4.1 Transformri morfologice fundamentale

    transformarea HOM Transformarea HOM (Hit Or Miss/totul sau nimic) se definete pe baza unei partiii (B1, B2) a elementului structurant B: B=B1B2 i B1B2= ca fiind:

  • 96

    { } { }1 2( ) ( ) cx xA B x B A x B A = , (2.82)

    unde: A este mulimea cruia i se aplic transformarea, Ac este complementara sa, B este elementul structurant, iar (Bi)x este mulimea Bi translatat cu x.

    Not. Oricrui element structurant este necesar s-i fie ataat o origine.

    Fig. 2.16 Exemplu de calcul a transformatei HOM

    erodarea morfologic

    Erodarea morfologic a mulimii A este transformata sa HOM cu un singur element structurant B=B1, B2=:

    { } { } { }1 2( ) ( ) ( )cx x xA B x B A x B A x B A = = . (2.83)

    Fig. 2.17 Exemple de erodare morfologic

  • 97

    dilatarea morfologic Dilatarea morfologic a mulimii A cu elementul structurant B este dat de urmtoarea relaie:

    { }( )xA B x B A = . (2.84)

    Fig. 2.18 Exemple de dilatare morfologic

    Se demonstreaz relativ uor c erodarea i dilatarea morfologic sunt operaii duale i nu sunt inverse. De asemenea, se poate arta i faptul c operaiile morfologice respective sunt invariante la translaie i scalare (omotetie). 2.2.4.2 Transformri morfologice derivate

    deschiderea i nchiderea morfologic Deschiderea morfologic a mulimii A prin elementul structurant B se definete ca:

    ( ) sA B A B B= , (2.85)

    unde Bs este elementul structurant simetrizat. nchiderea morfologic a mulimii A prin elementul structurant B este dat de relaia:

    ( ) sA B A B B = . (2.86)

  • 98

    Proprietatea de baz a deschiderii i nchiderii morfologice este aceea c sunt transformri duale una alteia. De asemenea, ele sunt invariante la translaie i scalare.

    Fig. 2.19 Exemple de deschidere i nchidere morfologic

    Not. Operaiile de deschidere i nchidere pot fi asimilate cu o filtrare de

    netezire a formelor de interes i, respectiv, cu o eliminare a zgomotului (a obiectelor i gurilor de mici dimensiuni din forma studiat).

    conturarea morfologic Conturarea are ca rezultat obinerea mulimii pixelilor de pe conturul formei fr o ordonare a acestora. Aceast operaie este dat de relaia:

    /A A A B = , (2.87)

    unde A este mulimea supus transformrii, iar B este elementul structurant.

    Fig. 2.20 Exemplu de conturare morfologic

  • 99

    scheletizarea morfologic Scheletizarea morfologic a unei mulimi A prin elementul structurant B este definit astfel:

    max

    0

    ( ) [( ) /( ) ]n

    Bi

    S A A iB A iB=

    =

    , (2.88)

    unde nmax este numrul maxim de erodri (prin B) dup care A devine o mulime vid, iar AnB=(((AB) B)... B).

    Fig. 2.21 Exemplu de scheletizare morfologic

    Not. n literatura de specialitate sunt menionate i alte tipuri de

    transformri morfologice derivate ca: subierea, ngroarea, curarea etc. De asemenea, n general se poate arta c aceste transformri pot fi extinse de la imagini binare la imagini cu niveluri de gri.

    Pentru detalii teoretice suplimentare referitoare la operaiile morfologice se pot consulta referinele bibliografice [19] i [57]. 2.2.4.3 Scheletonul morfologic Skeletonul morfologic al unei forme (continue) este mulimea centrelor discurilor maximale ale formei. Pentru o form oarecare A se definete discul maximal n A, de centru x i raz r, notat cu Bx(r), de forma:

    '

    ''

    '

    ( )i

    ( ) ( )

    x

    x x

    B r A

    r rB r B r A

    x x

    = =

    . (2.89)

  • 100

    Fig. 2.22 Exemple de skeletoane pentru forme continue

    Calculul skeletonului unei forme reprezentate n spaiul discret se poate

    face prin formula lui Lantuejoul (n acest sens, se poate consulta referina bibliografic [57]). Skeletonul formei A, SK(A), este format din reuniunea unui numr finit de seturi skeleton:

    max

    0( ) ( )i

    ( ) ( ) ( ) ,

    nn

    n

    NSK A U S A

    S A A nB A nB B=

    =

    = (2.90)

    unde ordinul Nmax corespunde momentului n care toate seturile skeleton succesive devin nule, adic ANmaxB=. Elementul structurant nB este iterarea de n ori a elementului structurant B, nB=B...B i, n general, este o expresie discret a discului unitar (elementul structurant V4 sau V8).

    Fig. 2.23 Exemplu de calcul al skeletonului unei forme discrete

    Reconstrucia formei din skeleton se face cu formula:

    max

    0( ) .

    N

    nnA U S A nB

    == (2.91)

  • 101

    Not. Se poate opta i pentru reconstrucii pariale prin neglijarea seturilor skeleton ce reprezint detaliile (seturi skeleton de ordin mic). Skeletonul este invariant la translaie, nu este conex i nu este comutativ cu operaia de reuniune a formelor. De asemenea, transformarea skeleton este idempotent i antiextensiv. Seturile skeleton sunt disjuncte dou cte dou. Folosirea skeletonului morfologic n recunoaterea formelor este limitat de sensibilitatea sa sporit la zgomote i de variaia la rotaia i scalarea obiectelor. n acelai timp, folosirea elementului structurant de tip disc unitar introduce o puternic dependen de metrica folosit n definirea sa i conduce la elemente structurante ptrate (V4 sau V8), ce pot fi cu greu interpretate ca discuri. Aceste dezavantaje au condus la folosirea unor clase de elemente structurante care s nu fie legate de metrica utilizat (elemente structurante generalizate) i la noiunea de skeleton generalizat. 2.2.4.4 Scheletonul morfologic generalizat Fie {Gi}i un set de mulimi numit set generator. Elementele structurante generalizate se definesc recurent prin intermediul relaiei:

    1

    0

    , 1,2,...0 .

    i i i

    n

    B B G iB

    = =

    = (2.92)

    Not. n general, se folosesc seturi generatoare avnd o anumit

    periodicitate T ( )T , ,i k iG G i k+ = .

    Fig. 2.24 Construcia unui set de elemente structurante generalizate

    Fiecrui punct al formei A i se va asocia ordinul (indicele) elementului structurant generalizat maximal centrat cu originea n punctul respectiv, construind astfel o hart de distane, de forma:

    ( ) ( )10,dac

    ( ),dac i .n nx x

    x AD x

    n B A B A

    = (2.93)

  • 102

    Skeletonul generalizat al unei forme este mulimea originilor elementelor structurante generalizate maximale n forma:

    { }( ) 1 ( ) 1( ) |( ) ( ) , .D x y D y yGSK A x A B B x y = (2.94)

    Fig. 2.25 Harta de distane i skeletonul generalizat asociat

    Not. Mai multe detalii teoretice privind construcia i proprietile

    skeletonului morfologic, respectiv skeletonului morfologic generalizat pot fi regsite n referinele bibliografice [57] i [60].

    2.3 Metode de selecie a caracteristicilor Dimensiunea spaiului caracteristicilor influeneaz ntr-o msur destul de important eficiena/performanele algoritmilor de clasificare. Astfel, o serie de algoritmi de clasificare eficieni n spaii cu puine dimensiuni devin nepractici n spaii cu mai multe dimensiuni. De aceea, se caut transformri care s ierarhizeze importana caracteristicilor n spaiul transformat i s permit astfel micorarea dimensiunii acestuia prin eliminarea celor mai puin semnificative, pstrnd n acelai timp informaia esenial n vederea clasificrii. Pentru aceasta, vor fi selectate acele caracteristici care conin cea mai mare cantitate de informaie despre forma respectiv. Prin urmare, aplicarea unei astfel de transformri datelor obinute n urma fazei de extracie a caracteristicilor i reinerea numai a celor semnificative poart numele de selecia caracteristicilor (feature selection).

    Not. O tratare excelent i riguroas a transformrilor pentru selecia caracteristicilor este realizat n referinele bibliografice [37] i [38].

    Sunt prezentate n continuare ntr-o form concis metodele PCA, transformrile liniare, transformrile care folosesc criteriile de separabilitate ale claselor (analiza discriminatorie), transformrile neliniare i proieciile n spaii de forma 2D.

  • 103

    2.3.1 Analiza componentelor principale (PCA) Analiza componentelor principale este o metod clasic de analiz a datelor, larg rspndit, care permite detectarea celor mai marcante tendine ale unei mulimi de date. Fie X un nor de puncte n spaiul n:

    ( )1, ..., , , 1,P j nX x x x j P= = . (2.95)

    Componentele principale ale mulimii X sunt direciile din n de-a lungul crora alungirea norului este cea mai semnificativ. Cunoaterea acestor direcii poate servi att n scopuri de clasificare, ct i pentru determinarea celor mai importante caracteristici ale norului de puncte. Proiectnd norul pe direciile date de componentele sale principale, se realizeaz o compresie a informaiei cuprins n mulimea de instruire respectiv, cu efect imediat asupra reducerii dimensiunilor formelor de intrare i implicit, a numrului de neuroni din stratul de intrare al unei reele neuronale. Determinarea componentelor principale ale norului de date X revine la cutarea acelor direcii u1, u2, ... care corespund dispersiei maxime a acestuia i n consecin se poate afirma c norul X este format din puncte care ader strns la dreptele care trec prin centrul su de greutate i au direciile u1, u2, .... Prin urmare, problema determinrii direciilor principale ale mulimii X poate fi privit ca o problem de minim. Notm cu J1(u,v) funcia definit de suma ptratelor distanelor punctelor norului la dreapta L de direcie u i care trece prin punctul v n:

    ( )21 11

    ( , ) , , :P

    j n n

    jJ u v d x L J

    =

    = . (2.96)

    Prin urmare, componentele principale ale norului sunt direciile care minimizeaz funcia J1. Se poate demonstra c orice dreapt L care reprezint o soluie a problemei de optim:

    1( , ) min

    , nJ u v

    u v

    =

    , (2.97)

    trece prin centrul de greutate c al norului de puncte, unde:

    1

    1 P jj

    c xP =

    = . (2.98)

  • 104

    Cum aceast dreapt optimal L trece ntotdeauna prin centrul de greutate al norului X, se poate efectua o normalizare (o translaie) a acestuia, astfel nct c s fie considerat noua origine a sistemului de coordonate, adic vectorul c s fie zero. Aceast translaie este echivalent cu o transformare a datelor norului de forma:

    , 1,j jx x c j P = . (2.99)

    De asemenea, putem considera tot n sens simplificator c 1u = , unde u=(u1, u2, ...). Funcia criteriu (2.81) poate fi rescris acum sub forma:

    ( ) ( )221 1 1

    ( ) , , , :P P P

    j j j n

    j j jJ u d x L x x u J

    = = =

    = = , (2.100),

    unde cu ( ),jx u s-a notat produsul scalar. Definind n prealabil o nou funcie:

    1

    ( ) ( , ), :P

    j n

    jF u x u F

    =

    = , (2.101)

    problema de optim (2.97) se poate rescrie sub forma problemei de maxim:

    ( ) max,i

    1.

    F u

    u

    = =

    (2.102)

    Cum orice produs scalar n spaiul n se poate scrie sub forma:

    ( , ) ( )( )T Tq s s q q s= C C , (2.103),

    unde C este o matrice simetric i pozitiv definit, relaia (2.101) devine:

    ( )( )1

    ( )P

    T j jT

    jF u u x x u

    =

    = C C . (2.104)

  • 105

    Notm cu S matricea de mprtiere a norului X, se poate arta c pentru date normalizate aceasta are urmtoarea forma:

    1

    Pj jT

    jx x

    =

    = S C C . (2.105)

    Prin urmare, funcia F se rescrie sub forma:

    ( ) TF u u u= S . (2.106)

    Rezult c determinarea componentelor principale ale norului de date X se reduce la determinarea punctelor de maxim ale formei ptratice F pe sfera unitate. Aceste maxime sunt tocmai vectorii proprii u1, ..., un ai matricei de mprtiere S:

    , 1,i iiu u i n= =S , (2.107), unde i este valoarea proprie asociat vectorului propriu ui. Ordonnd n mod descresctor aceste valori proprii (eventual, dublat de o nou indexare):

    1 2 ... n , (2.108),

    atunci importana direciei principale 1 va fi mai mare dect cea a direciei 2 etc., aceasta deoarece i msoar dispersia norului X n direcia ui. De asemenea, oricare dou direcii principale sunt ortogonale.

    Not. Dac centrul de greutate c nu este n origine (c0), atunci relaia (2.105) se rescrie sub forma urmtoare (date de intrare nenormalizate):

    ( )( )1

    P Tn j j

    jx c x c

    =

    = S C C (2.109)

    Prin urmare componentele principale ale norului X vor fi vectorii proprii ai matricei de mprtiere Sn.

    Algoritmul PCA poate fi definit ntr-o manier analoag i pentru cazul mulimilor de instruire nuanate (fuzzy). Caracterul liniar al metodei standard PCA (metoda standard PCA reprezint o proiecie liniar a datelor analizate pe componentele/direciile principale) determin o serie de neajunsuri majore n prelucrarea datelor de intrare reale. De aceea, n ultima perioad au fost dezvoltate teoretic o serie de

  • 106

    generalizri neliniare ale variantei clasice, un exemplu concret n acest sens fiind i algoritmul kernel-PCA (o funcie kernel realizeaz chiar prin structura sa intern o transformare neliniar n spaiul caracteristicilor). Informaii suplimentare privind tehnicile de analiz neliniare PCA pot fi regsite n referinele bibliografice [38] i [49]. 2.3.2 Analiza componentelor independente (ICA) 2.3.2.1 Problematica ICA Analiza componentelor independente (Independent Component Analysis) (Comon, 1994) este o tehnic de procesare a semnalelor a crui scop este exprimarea unui set de variabile aleatoare sub forma unor combinaii liniare de variabile componente independente statistic. Aplicaiile de baz ale ICA se refer la separarea oarb a surselor de semnal, selecia de caracteristici i ntr-o form uor modificat, la deconvoluia oarb. n forma cea mai simpl a ICA se observ m variabile aleatoare scalare v1, v2, ..., vm care sunt combinaii liniare ale celor n componente independente necunoscute s1, s2,..., sn, variabile care sunt considerate mutual independente statistic i cu media nul. Suplimentar, se poate considera c nm. n continuare, variabilele observate {vi}i sunt aranjate sub forma unui vector v=(v1, v2,..., vm)T i, respectiv, variabilele componente {si}i sub forma unui vector s, relaia liniar de legtur ntre acetia fiind una de forma:

    1

    n

    i ii

    a s=

    = =v As , (2.110) unde A este o matrice necunoscut de rang maxim ( )m n numit matrice de mixare i ale crui coloane sunt vectorii ( ) 1,i i na = . Problema principal a ICA const n estimarea componentelor originale {si}i pe baza mixturilor {vj}j sau, echivalent, estimarea matricei de mixare A. Coloanele ai ale acestei matrici sunt denumite vectori de baz. Restricia fundamental a acestui model este aceea c se poate estima numai componentele independente non-gaussiene (exceptnd cazul cnd doar una din componentele independente este gaussian). Suplimentar, nici energia sau semnul componentelor independente nu poate fi estimat, aceasta deoarece orce constant care multiplic o component independent din ecuaia (2.110) ar putea fi anulat prin divizarea coloanei corespunztoare din matricea de mixare A cu aceeai constant. Pentru o exprimare matematic adecvat, se poate presupune c, componentele independente {si}i au o covarian unitar. Aceasta

  • 107

    conduce la obinerea unor componente independente (nongaussiene) unice, n conformitate cu semnalele asignate acestora.

    Not. Nu exist definit nici o relaie de ordine ntre componentele independente determinate (considerate dou cte dou). n cazul separrii oarbe a surselor de semnal (Jutter i Herault, 1991), valorile observate ale vectorului v corespund unei realizri a semnalului discret m-dimensional v(t), t=1,2,... Componentele si(t) se numesc semnale surs i care n mod normal sunt semnale originale, neafectate de zgomot sau surse de zgomot. Pentru cazul deconvoluiei oarbe (Shalvi i Weinstein, 1990), se presupune cunoscut o versiune convoluionat v(t) a semnalului necunoscut s(t). Problema de interes const n determinarea unui filtru de separare f, astfel nct s(t)=f(t)v(t). Filtrul corector f(t) este implementat sub forma unei linii cu ntrziere neuniform i cu o lungime adecvat, ceea ce determin ca efectul de trunchiere s fie nesemnificativ. Matricea ptratic A se determin cu ajutorul unui filtru de convoluie. O alt aplicaie posibil a ICA este selecia caracteristicilor (Bell i Sejnowski, 1977). n acest caz, coloanele matricei A reprezint caracteristicile, iar semnalele {si}i reprezint prezena, respectiv amplitudinea caracteristicii i n cadrul datelor observate v. 2.3.2.2 Algoritmul lui Comon n accepiunea lui Comon, metoda ICA const n determinarea unei transformri care maximizeaz independena statistic a unui set de date i care presupune parcurgerea a dou etape distincte:

    determinarea unei transformri liniare care asigur independena statistic pn la statistica de ordinul doi (practic, se realizeaz decorelarea setului de date), practic etapa de albire sau descompunerea dup valori singulare;

    realizarea independenei statistice de ordin nalt, utiliznd cumulanii (momentelor statistice) de ordin superior.

    Not. Independena statistic se obine atunci cnd toate momentele mutuale sau toi cumulanii mutuali de orice ordin sunt nuli. Deoarece estimarea tuturor momentelor statistice sau cumulanilor de ordin superior este practic imposibil, Comon a propus utilizarea unor funcii de contrast care s minimizeze informaia mutual dintre componentele setului de date, funcie care poate fi aproximat prin intermediul unui numr limitat de cumulani mutuali. Se presupune urmtorul model statistic liniar:

    = +v As , (2.111)

  • 108

    unde s, v i sunt vectori aleatori cu valori reale sau complexe, cu valori medii nule i covariane finite, A este matricea de mixare, iar componentele vectorului s sunt independente statistic. Natural, problema ICA se poate formula: fiind cunoscute m valori ale vectorului v, se cere determinarea matricei de mixare A i valorile corespunztoare ale lui s. Deoarece se presupune c zgomotul are o distribuie necunoscut, atunci este posibil refacerea exact a valorilor vectorului s i totodat este posibil s se determine o matrice F, cu proprietatea c:

    =v Fz , (2.112)

    unde z este un vector aleator ale crui componente maximizeaz o funcie de contrast. n consecin, se definete ICA pentru un vector aleator v de dimensiune m i covariana finit Cv , o pereche de matrice {F, }, astfel nct:

    covariana sa se poate pune sub forma

    2 Tv =C F F , (2.113)

    unde este o matrice diagonal real pozitiv, iar F este o matrice de rang p;

    semnalele observate respect relaia (2.112), unde z este un vector aleator de dimensiune ( )1p , cu covariana 2 i ale crui componente sunt ct mai independente posibil, n sensul maximizrii unei funcii de contrast.

    Not. Deoarece prin nmulirea variabilelor aleatoare cu scalari diferii de zero sau prin schimbarea ordinii nu se afecteaz independena lor statistic, ICA definete practic nu o singur descompunere, ci o clas de descompuneri echivalente. Pentru nelegerea n condiii optime a algoritmului lui Comon, se definesc n prealabil urmtoarele noiuni:

    statistici de ordin nalt (higher order statistics) Se consider un proces aleator n timp discret x(n) obinut prin eantionarea unui proces staionar (ntr-un sens oarecare) x(t). Procesul x(t) poate fi caracterizat n mai multe moduri, dar cel mai rspndit mod de caracterizare a sa este cu ajutorul funciei densitate de probabilitate. Un set foarte cunoscut de mrimi care descriu alura densitii de probabilitate este cel reprezentat de momentele statistice (spre exemplu, momentul de ordinul unu al procesului x(t) reprezint valoarea sa medie, cel de ordinul doi dispersia, cel de ordinul trei msoar asimetria funciei densitate de probabilitate etc.). Matematic, se poate utiliza o funcie numit funcie de generare a momentelor MGF (Moments Generation Function) pentru a exprima toate momentele unui proces aleator. Prin urmare, primul coeficient al dezvoltrii n serie Taylor a MGF este valoarea medie, al doilea coeficient este dispersia etc.

  • 109

    Un alt set de parametri care caracterizeaz un proces aleator i care este caracterizat prin proprieti matematice deosebite este cel reprezentat de cumulani. Cumulanii se definesc cu ajutorul dezvoltrii n serie Taylor a funciei de generare a cumulanilor CGF (Cumulants Generation Function) care este tocmai logaritmul natural al MGF. n general, statisticile de ordin superior sunt mai potrivite dect corelaia pentru procesarea semnalelor afectate de zgomot, chiar dac zgomotul este unul colorat.

    Not. Cele mai importante proprieti ale cumulanilor i legtura acestora cu momentele statistice de acelai ordin sunt prezentate pe larg n cadrul referinei bibliografice [40].

    informaia mutual Dac s este o variabil aleatoare cu valori reale (din n) i care are funcia densitate de probabilitate ps(u), atunci variabila s are componentele mutual independente dac i numai dac:

    1

    ( ) ( )i

    n

    s s ii

    p u p u=

    = (2.114) Rezult c o modalitate natural pentru verificarea independenei

    componentelor variabilei s este msurarea distanei 1

    ( , )i

    n

    s si

    p p=

    dintre membrii relaiei (2.114) cu ajutorul divergenei Kullback:

    1

    ( )( ) ( ) log d ,( )

    i

    nss s n

    si

    p uI p p u u up u

    =

    =

    , (2.115)

    unde I(ps) este informaia mutual (medie) a variabilei s.

    Not. Aceast funcie poate fi utilizat ca funcie de contrast pentru separarea surselor.

    negentropia Se definete entropia diferenial a variabilei aleatoare s de forma:

    ( ) ( ) log ( )ds s sS p p u p u u= . (2.116)

    Not. Se noteaz cu En spaiul variabilelor aleatoare cu valori n n, cu Ern subspaiul Euclidian al lui En format de variabilele cu momente finite pn la ordinul r (r2) i cu 2

    nE subsetul variabilelor din E2n care au matricea de covarian inversabil.

  • 110

    Pentru densiti de probabilitate din 2nE se definete negentropia de

    forma:

    ( ) ( ) ( )s s sJ p S S p= , (2.117) unde s este o distribuie gaussian cu aceeai valoare medie i dispersie ca i densitatea de prob