Indicatii referitoare la proiectarea sistemelor de recunoastere a formelor.

Scopul lucrarii

Lucrarea are ca scop prezentarea notiunilor de baza privind implementarea unor programe de recunostere a formelor.

Notiuni teoretice

Generalitati

Metodele de recunoastere a formelor constituie proceduri algoritmice, implementabile pe calculator, utilizate in scopul clasificarii unor obiecte, fenomene, in clase (grupuri discrete), pe baza caracteristicilor acestora, grupate in matrice multidimensionale de date. Scrierea, punerea la punct si executarea unor astfel de programe se poate face relativ usor facand apel doar la cunostinte fundamentale de programare. Pentru implementarea propriului sistem de recunoastere a formelor este necesara selectia caracteristicilor formarea si evaluarea clasificatorilor implementati.

Una dintre cele mai importante probleme ale implementarii este analiza formelor efectuata cu scopul extragerii celor mai reprezentative caracteristici ce urmeaza sa fie utilizate ulterior in procesul de recunoastere. Aceasta etapa este efectuata cu ajutorul selectorului de caracteristici care reprezinta o selectie de tehnici matematice cu rol de eliminare a acelor caracteristici care nu sunt esentiale.(de exemplu proceduri de transformare rotationale diagonale, transformari liniare si neliniare, etc).

Alegerea optima a caracteristicilor duce in final la gruparea cea mai buna a formelor in spatiul n-dimensional, si la construirea unor algoritmi de clasificare mai simpli. Daca selectorul de caracteristici este impropriu si inefectiv, algoritmi de clasificare (clasificatori) vor fi mai putini eficienti, iar probabiliatea de eroare a clasificari va creste. Daca am utiliza un om pentru a inlocui selectorul de caracteristici dintr-o masina de recunoastere a formelor, el ar efectua o extragere de caracteristici pe baza experientei anterioare(invatare) si a personalitatii sale. Se observa faptul ca selectia caracteristicilor este limitata la doua sau trei dimensiuni, fiind cu toti convinsi ca vizualizarea unui spatiu cu o dimensionalitate mai mare este extrem de dificila daca nu imposibila. Cu toate acestea exista o multitudine de tehnici matematice care pot fi aplicate in acest domeniu.

Extragerea si selectia caracteristicilor are urmatoarele scopuri:

Gasirea caracteristicilor esentiale care permit generarea sau reconstructia formelor originale.

Selectarea caracteristicilor care identifica cel mai bine formele.

Marea majoritate a metodelor matematice care sunt utilizate pentru extragerea si selectia caracteristicilor se bazeaza pe:

Transformari liniare si neliniare pentru reducerea multidimensionalitatii spatiului formelor si/sau pentru marirea separabilitatii claselor.

Criterii de evaluare a caracteristicilor.

Proceduri de cautare pentru selectarea optima a unui set dintr-un set de caracteristici.

Problema selectiei caracteristicilor poate fi privita ca problema de optimizare combinatoriala care necesita o functie criteriu si o procedura de cautare. Singurul mod de a fi siguri ca a fost ales subsetul cel mai bun de k caracteristici din totalul de N caracteristici este de a analiza toate combinatiile posibile C_k^N. Alegerea functiei criteriu utilizata in alegerea subsetului cel mai bun ca si procedura de cautare sunt determinate de problema concreta de recunoastere a formelor.

Etapele necesare pentru a fi parcurse in afara de analiza a formelor si selectare a caracteristicilor sunt rezumate in figura Fig.1.1.

Fig.1.1 Fazele procesului de selectare a caracteristicilor

Strategii computationale folosite in recunoasterea bazata pe model

Clasificarea vectorului trasaturilor globale

Metodele bazate pe clasificarea vectorului trasaturilor globale sunt cunoscute in literatura si sub denumirea de metode teoretico-decizionale, sau metode statistice.

Conditiile necesare pentru aplicarea acestora metode sunt inexistenta atingerilor, acoperirilor partiale si a trunchierilor si separabilitatea obiectelor intre ele si fata de fond.

Obiectele sunt modelate prin vectori de trasaturi, avand drept componente trasaturi globale. In general se utilizeaza trasaturi geometrice, functionale si topologice.

In categoria trasaturilor geometrice intra trasaturile caracteristice sau de identificare, trasaturile de pozitionare si coordonatele punctelor de contur.

Trasaturile caracteristice au rol in identificarea obiectelor. Se aleg astfel incat sa fie, pe cat este posibil invariante la transformarile rigide. Printre trasaturile caracteristice cele mai utilizate se numara:

A    aria;

P    perimetrul;

R_max    raza maxima;

R_min    raza minima;

m_R raza medie;

si altele.

Trasaturile functionale realizeaza o descriere suficient de exacta a obiectelor din imagine facand uz de dezvoltari analitice usor de utilizat. In aceasta categorie intra coeficientii Fourier ai functiei intrinseci a curbei de contur, momentele de inertie de diferite ordine calculate pe curba de contur precum si invarianti calculati pe baza momentelor de inertie. (acestea nu prezinta obiect de studiu pentru acest laborator).

Trasaturile topologice exprima proprietati ale obiectelor invariante la deformarile care nu afecteaza suprafata. Ele sunt independente de distanta.

PROBLEME PROPUSE

Sa se scrie un program, in unul din limbajele de programare cunoscute, care sa stabileasca apartenenta la una din clasele C₁, C₂, C₃ definite de utilizator(unde C₁ reprezinta dimensiune mica, C₂ reprezinta dimensiune medie, C₃ reprezinta dimensiune mare), pe baza trasaturilor geometrice.

Se vor considera vectorul de intrare latura (L) si functia criteriu data de valoarea ariei patratului.

Sa se scrie un program, in unul din limbajele de programare cunoscute, care sa stabileasca apartenenta la una din clasele C₁, C₂, C₃, C₄ definite de utilizator(unde C₁ identifica paralelogramele, C₂ identifica cercuri, C₃ identifica trapeze, C₄ figura neidentificata), pe baza trasaturilor geometrice.

Se vor considera vectorii de intrare:

lungime (L);

latime (l);

inaltime (h)

raza (r)

baza mare (B)

baza mica (b)

Functia criteriu va fi data de formula de calcul a ariei figurilor.

Se vor lua in considerare urmatoarele formule:( S_pgr=L*h, S_cerc=,S_trapez =(B+b)*h/2).

Folosind vectorii de intrare definiti in problema 2 si clasele definite la problemele 1. si 2. , sa se implementeze un program care stabileste apartenenta la clasele definite (specificarea tipului figurii si a dimensiunii).

*Sa se scrie un program care sa identifice figurile geometrice cercuri, patrate, triunghiuri determinate de 8 puncte generate aleator care ar putea fi distribuite pe circumferinta acestor figuri.

Considerand n puncte aleatoare in spatiul 2D.Sa se scrie un program care sa identifice punctele a caror distributie genereaza configuratia necesara unei figuri geometrice prin a carei rotire sa se obtina un con.