inteligenta artificiala

Click here to load reader

Post on 11-Sep-2015

50 views

Category:

Documents

15 download

Embed Size (px)

DESCRIPTION

tehnici de clustering si altele

TRANSCRIPT

  • 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 necesa

View more