Concepte fundamentale ale teoriei recunoasterii formelor

Ce este recunoasterea formelor?

Prin recunoasterea formelor se intelege in mod obisnuit acel ansamblu de metode si tehnici cu ajutorul caruia se poate realiza o clasificare in cadrul unei multimi de obiecte, procese sau fenomene. Setul de obiecte, procese sau fenomene care urmeaza a fi clasificate pot fi obiecte (fenomene) fizice sau structuri intelectuale, prin acestea intelegand ansamblul concretizat de procese legate de o activitate intelectuala coerenta (scris, vorbit, etc)

Scopul recunoasterii formelor consta in determinarea clasei din care face parte o colectie de observabile. Metoda este deosebit de utila atunci cand abordarile directe sunt imposibile sau cand inferentele teoretice lipsesc.

Stabilirea numarului de clase in care se impart formele este o problema particulara care depinde exclusiv de aplicatiile concrete ale metodei.

Spatiul formelor

Conceptul fundamental al teoriei recunoasterii formelor este urmatorul:

Un obiect sau un fenomen variabil, X_j, este descris (caracterizat) printr-un set de n caracteristici x_ij (i=1,.,n). Toate aceste n caracteristici ale unui obiect formeaza o forma.

Multimea W_x=_j=1,m poarta denumirea de spatiul formelor. Deci un obiect (forma) X poate fi reprezentat printr-un punct X(x₁,.,x_n) in spatiul formelor.

O problema este aceea a raportului dintre numarul de forme luate in considerare, m, si numarul de dimensiuni al spatiului formelor, n, adica raportul m/n dintre numarul maxim de obiecte din setul respectiv, m, si numarul de caracteristici, n, aferent fiecaruia dintre obiecte. Daca numarul de forme, m, este mai mic, egal sau numai putin mai mare decat numarul de caracteristici atunci discriminarea dintre forme si atribuirea lor la diferitele clase posibile este un proces pur aleator.

In general, se considera ca acest raport m/n, pentru orice aplicatie de recunoasterea formelor, trebuie sa indeplineasca urmatoarele conditii:

(i)         

(ii)        (1.1)

unde m reprezinta numarul de forme, iar n este numarul de caracteristici independente (numar de dimensiuni).

Conditia (i) reprezinta minimum necesar pentru o clasificare binara, in timp ce conditia (ii) este de dorit in aplicatiile concrete ale tehnicilor de recunoasterea formelor.

Moduri de abordare a problematicii recunoasterii formelor

Pentru rezolvarea problemelor de recunoastere a formelor au fost propuse si utilizate o mare varietate de tehnici matematice din teoria informatiei, statistica matematica, teoria deciziei, geometrie, etc. , de fapt doua maniere diferite de abordare a problematicii acestui domeniu:

Abordarea statistica (numita si decizional- teoretica) si

Abordarea sintactica (sau lingvistica).

In cadrul metodelor de recunoasterea formelor decizional-teoretice, din forme sunt extrase un set de masuratori caracteristice, denumite caracteristici. Recunoasterea fiecarei forme (atribuirea formei la o clasa specifica) se face, de obicei, prin partitionarea spatiului formelor, denumit si spatiu caracteristicilor.

Clasificarea formei de intrare se face pe baza unor caracteristici ale formei astfel incat sa se poata presupune, cu un coeficient de siguranta cat mai mare, ca ele sunt invariante, independente una fata de alta si mai putin sensibile la variatii si deformari. In legatura cu acestea se pune problema selectarii obiective a celor mai semnificative caracteristici precum si cea a clasificarii (adica a luarii deciziei pentru a atribuii claselor formelor de intrare respective).

Caracteristicile unui sistem general de recunoasterea formelor

Un sistem de recunoastere a formelor trebuie sa asigure, corect si eficient observarea, transformarea, prelucrarea preliminara (selectarea) si clasificarea esantionului de date.

Elementele esentiale ale unui sistem general de recunoasterea formelor sunt urmatoarele: translatorul, selectorul de caracteristici (care realizeaza o prelucrare preliminara) numit si preprocesor, sau extractor de caracteristici si clasificatorul (Fig. 1.4-1). Desi aceste 3 subunitati sunt interdependente, in cele ce urmeaza le vom prezenta separat.

Fig. 1.4‑ Sistem general de recunoastere a formelor

Translatorul

Translatorul transforma si transfera informatiile din lumea reala in spatiul formelor intr-o forma compatibila cu modul de reprezentare din calculatoarele electronice. In consecinta datele primare, rezultat al observatiei sunt transformate intr-un sir de marimi scalare care formeaza vectorul de forma n-dimensional. Fiecare componenta x_i a vectorului de forma X reprezinta o cantitate fizica masurabila; este foarte important ca ea sa surprinda esenta datelor primare.

Modul de implementare al translatorului depinde exclusiv de natura datelor primare. Daca acestea sunt constituite dintr-o succesiune de valori masurate la intervale de timp, cum sunt traseele EEG, atunci sunt necesare procedee de esantionare in timp, pe cand daca ele sunt functie de frecventa, cum sunt de exemplu spectrele in infrarosu ale compusilor chimici, atunci trebuie dezvoltate procedeele de esantionare a frecventei (respectiv numerelor de unda). In cazul imaginilor sunt luate in considerare suprafetele mai luminoase sau mai intunecate, muchiile sau formele geometrice. Aceasta este o problema ceva mai complicata si, de aceea , au fost propuse o serie de metode pentru reducerea complexitatii imaginilor la un sir de masuratori.

O situatie fericita, in care translatorul nu mai este necesar, apare atunci cand informatiile din lumea reala sunt exprimate numeric (de exemplu, in cazul spectrelor de masa).

Vectorii de forma dezvoltati de translator constituie marimile de intrare pentru selectorul de caracteristici.

Selectorul de caracteristici

Scopul selectorului de caracteristici consta in prelucrarea vectorilor de forma in asa fel incat procedeul de clasificare sa fie optimizat.

Selectorul de caracteristici (denumit si extractor de caracteristici sau preprocesor) accepta ca marimi de intrare vectorii de forma produsi de translator si opereaza asupra lor transformandu-i pentru a elimina sau, cel putin, pentru a reduce cantitatea de informatie irelevanta sau ambigua mentinand in vectori suficienta informatie pentru a putea discerne intre diferitele clase de forme si descoperi invariantele dintre formele aceleiasi clase.

Pentru realizarea acestor deziderate au fost propuse si utilizate o mare varietate de metode.

Una dintre cele mai simple metode pentru prelucrarea vectorilor de forma consta in normarea acestora. O astfel de normare implica egalarea sumei componentelor fiecarui vector de forma (respectiv suma patratelor componentelor lor) cu o constata arbitrara convenabil aleasa. Un alt procedeu, mult mai sofisticat, care utilizeaza matricea de covarianta duce, in final, la o ecuatie matriciala din care se obtin vectorii proprii si valorile proprii ( procedeul numit analiza componentelor principale sau analiza Karhuneu-Loeve).

Pentru prelucrarea vectorilor de forma si selectarea celor mai reprezentative caracteristici au fost utilizate si o serie de transformari mult mai complexe, cum ar fi transformata Fourier.

Pentru identificarea caracteristicilor mai importante au fost utilizate forme model sau prototip, s-au dezvoltat si implementat tehnici interactiv, implicand repreyentari grafice si rutine speciale de comparare, s-au calculat parametrii statistici, cum sunt momentele sau histogramele direct din forme.

Aceasta etapa este esentiala, de ea depinde succesul sau insuccesul oricarui studiu de recunoastere a formelor.

Clasificatorul

Sarcina oricarui clasificator este, in general, urmatoarea: avand data o multime de vectori de forma prelucrati corespunzator, numita set de formare, se pune problema determinarii unei functii de decizie f(X) astfel incat daca:

f(X) > 0 atunci X apartine clasei 1

f(X) >= 0 atunci X apartine clasei 2    (1.2)

Aceasta etapa in care este determinata functia de decizie f(X) este cunoscuta sub numele de faza de formare (formarea), de adaptare sau uneori de invatare. Scopul urmarit este minimalizarea probabilitatii de eroare in procesul de clasificare.

Conceptul de clasificare a formelor poate fi inteles ca o partitionare a spatiului formelor, W_x prin atribuirea fiecarui vector X sau punct X (x₁, .,x_n) la o clasa de forme corespunzatoare in regiuni reciproc exclusive, fiecare regiune corespunzand unei clase de forme particulara. Din punct de vedere matematic problema clasificarii poate fi formulata sub forma functiilor de decizie discriminate.

Fie w w w_p cele p clase distincte posibile care urmeaza a fi recunoscute cu

W _X = w U w U ..Uw_p

w w w_p = F_d (1.3.)

si fie X=|x_i |_i=1,n vectorul de forma, x_i reprezentand a i-a caracteristica reprezentativa. Atunci functia de decizie discriminant f(X)=D_j (X) asociata clasei de forme w_j, j=1,.,p, astfel incat daca forma de intrare reprezentata prin vectorul X, respectiv punctul X, este in clasa w_i, fapt pe care-l vom nota prin X w_i , valoarea lui D_i(X) trebuie sa fie cea mai mare, adica pentru toti X w_i vom avea satisfacuta relatia:

D_i(X) > D_j(X), i, j =1,.,p. (1.4)

In felul acesta, in spatiul formelor w_x frontiera partitiei, denumita limita de decizie, dintre regiunile corespunzand claselor w_i si respectiv, w_j, poate fi definita prin urmatoarea relatie:

F_d= D_i(X)-D_j(X) = 0 (1.5)

In figura 2.8. este reprezentat modelul unui clasificator care utilizeaza functiile discriminant. Forma de intrare este analizata conform relatiei (1.4), clasificatorul furnizand drept iesire indicele k apartine corespunzator clasei w_k din care face parte forma respectiva X.

Fig. 1.4‑ Modelul clasificatorului ce utilizeaza functia discriminant

Pentru determinarea functiilor discriminant neparametrice setul de formare trebuie sa fie mare si, de asemenea, reprezentativ pentru a permite estimarea acestora din functiile de probabilitate.