Imagini Digitale
Cuprins
Cuprins
Introducere
I. Context general 8
1. 1. Analiza imaginilor digitale
1.1.1. Definiții
1.1.2. Imagini digitale
1.1.3. Structura unui sistem de prelucrarea și analiza imaginilor
1.1.4. Stocarea imaginilor
1.1.4.1 Stocarea imaginilor în memorie
1.1.4.2 Stocarea imaginilor în fișiere
1. 2 Recunoașterea formelor
1.2.1. Concepte fundamentale
1.2.1.1. Definiție
1.2.1.2. Spațiul formelor
1.2.1.3. Moduri de abordare a problematicii recunoașterii formelor
1.2.1.4. Caracteristicile unui sistem general de recunoașterea formelor
1.2.1.4.1. Translatorul
1.2.1.4.2. Selectorul de caracteristici
1.2.1.4.3. Clasificatorul
1.2.2. Exemplu de recunoaștere a formelor
1.2.3. Recunoașterea obiectelor
1.2.3.1. Sisteme senzoriale
1.2.3.2. Recunoașterea obiectelor folosind modele
1.2.3.2.1. Recunoașterea tridimensională din informații de profunzime
1.2.3.2.2. Recunoașterea bidimensională din informații de intensitate
1.2.3.3. Structura unui sistem de recunoaștere
1.2.3.4. Tehnici de calcul utilizate de sistemele de recunoaștere
1.2.3.4.1. Clasificarea vectorului trăsăturilor globale
1.2.3.4.2. Clasificarea vectorilor de formă și spațiul formelor
1.2.3.4.3. Clasificarea de distanță minimală
1.2.3.4.4. Clasificarea Bayesiană
1.2.3.5. Potrivirea modelelor cu datele senzoriale
1.2.4. Metode de clasificare bazate pe optimizarea unei funcții criteriu
1.2.4.1. Generalități
1.2.4.2. Disimilaritate. Normalizarea datelor
1.2.4.2.1. Măsuri de disimilaritate
1.2.4.2.2. Împrăștierea datelor
1.2.4.2.3. Normalizarea datelor
1.2.4.3. Măsuri de similaritate
1.2.4.3.1. Măsuri de similaritate pentru vectori binari
1.2.4.4. Funcția criteriu
II. Suport de realizare
2.1. Metode de clasificare
2.1.1. Recunoașterea necontrolată. Tehnici de grupare
2.1.2. Tehnici de învățare
2.1.3. Algoritmi de clasificare nesupervizată (clustering)
2.1.3.1. Algoritmul n-medii (K-means)
2.1.3.2. Exemplu de clusterizare folosind K-Means
2.1.3.3. Algoritmul Isodata
2.1.3.4. K-Means și Isodata
2.1.3.5. Problema grupării punctelor dintr-un spațiu multidimensional
2.2. Segmentarea imaginilor
2.2.1. Generalități
2.2.2. Histograma unei imagini
2.2.3 Histograma ponderată a unei imagini
2.2.4. Segmentarea pe histogramă
2.2.5. Segmentarea pe histograma cumulativă
2.2.6. Creșterea și fuziunea regiunilor
2.2.6.1. Creșterea regiunilor
2.2.6.2. Fuziunea regiunilor
2.2.7. Aplicarea combinată a operațiilor fuzzy în segmentarea imaginilor color
2.2.8. Algoritmul de „Clustering cu Vectori Suport” (SVC)
2.3. Teoria codurilor
2.3.1. Noțiuni introductive
Terminologia folosită în cadrul teoriei codurilor include următoarele noțiuni:
2.3.2. Fundamente. Coduri liniare
2.3.3. Codul Hadamard
2.3.3.1. Construirea codului
2.3.3.2. Decodificarea
2.3.3.3. Istoric
III. Considerații de implementare
3.1. Contextul realizării aplicației
3.1.1. Noțiuni introductive
3.1.1.1. Spectrul electromagnetic
3.1.1.2. Teledetecția
3.1.1.3. Imagini multispectrale
3.1.2. Metrici și distanțe. Similarități
3.1.2.1. Spațiul metric
3.1.2.2. Distanțe
3.1.2.3. Similarități
3.1.3. Softul utilizat
3.1.3.1. ENVI
3.1.3.2. Utilizarea sistemului Matlab pentru aplicații grafice
3.1.3.2.1. Generalități
3.1.3.2.2. Sistemul grafic MATLAB orientat pe obiecte ("Handle Graphics")
3.1.3.2.3. Toolbox-ul Image Processing
3.2. Aplicația propriu-zisă
3.2.1. Aplicații în clasificarea imaginilor
3.2.1.1. K-means pentru puncte bidimensionale (în Matlab)
3.2.1.2. K-means pentru o imagine simplă (în Matlab) 88
3.2.1.3. K-means și Isodata pentru imagini multispectrale (în ENVI și Matlab)
3.2.1.3.1. Influența alegerii metricii
3.2.1.3.2. Date de intrare. Analiza rezultatelor
3.2.2. Aplicații în segmentarea imaginilor
3.2.2.1. K-means pentru segmentarea imaginilor simple în spațiul RGB (în Matlab)
3.2.2.1.1. Clusterizarea intensității pixelilor
3.2.2.1.2. Date de intrare. Analiza rezultatelor
3.2.2.2. SVC pentru segmentarea imaginilor multispectrale (în Matlab)
3.2.3. Aplicații în teoria codurilor
3.2.3.1. Codurile Hadamard. Misiunea spațială Mariner
3.2.4. Aplicații didactice de laborator
3.2.4.1. Argumentul profesorului – Analiza imaginilor de pe Marte
3.2.4.2. Fișa de lucru – Analiza imaginilor de pe Marte
Bibliografie
Anexe
Anexa A: Coduri sursă
Anexa B: Glosar de termeni
Anexa C: Pliante
Introducere
Avansul din ultimele decenii al tehnologiilor electronice și informatice a dus la dezvoltarea de noi domenii științifice, cu numeroase aplicații; printre acestea se numără și prelucrarea și analiza imaginilor. În prezent, pe plan mondial, prelucrarea și analiza imaginilor își face simțită prezența în tot mai multe aplicații industriale, medicale sau de teledetecție. La noi în țară, debutul cercetărilor a fost timpuriu, iar la mijlocul anilor 80 a fost construit primul sistem hardware specializat de analiză a imaginilor.
Prelucrarea și analiza imaginilor cuprinde ansamblul de tehnici și metode de achiziție, stocare, afișare, modificare și exploatare a informației vizuale cuprinsă în imagini. În particular, analiza imaginilor se referă la capacitatea de a descrie, înțelege și recunoaște scene, obiecte din scene și legăturile dintre acestea. Din punct de vedere funcțional, analiza imaginilor transformă o imagine de intrare într-o descriere.
În mod esențial, analiza imaginilor statice înseamnă descompunerea acestora în elementele constitutive (prin segmentare) și apoi caracterizarea elementelor individuale prin parametri de formă. Atât segmentarea cât și descrierea pot fi realizate interpretând obiectele fie ca regiuni compacte, fie numai ca frontiere (contururi).
Clustering-ul reprezintă o tehnică importantă în analiza datelor care poate fi aplicată într-o varietate de discipline inginerești și științifice precum biologie, psihologie, medicină, marketing, robotică, teledetecție și astronomie. Analiza de clustere este un mijloc de explorare a structurii datelor care nu necesită cunoștințe „a priori”; de aici provine denumirea de „învățare nesupervizată” în literatura de specialitate a recunoașterii formelor și a inteligenței artificiale.
Tehnicile de clustering au fost dezvoltate inițial în biologie și zoologie servind la gruparea animalelor și plantelor cu scopul de a construi taxonomii. Nevoia de a organiza cantități vaste de date din diverse domenii științifice în grupuri, clustere, categorii, partiții sau clase cu semnificație a făcut din clustering o tehnică utilă în analiza datelor.
O diversitate de obiecte sau entități au fost clasificate, incluzând boli, eșantioane de roci, suprafețe terestre, amprente digitale, constelații de stele. În unele dintre aceste aplicații nu este foarte important să se identifice numărul exact de clustere sau apartenența corectă a fiecărei forme la un anumit cluster. Deseori este suficient doar gruparea datelor într-o manieră pe care specialiștii să o poată interpreta. O astfel de interpretare este similară cu un proces de învățare și a dus la adoptarea clustering-ului în domeniul inteligenței artificiale sub denumirea de „învățare prin observare”.
În general tehnicile de clustering nu pot fi aplicate în mod automat fără intervenția umană. Alegerea trăsăturilor, a măsurii de similaritate și a tehnicii de grupare necesită familiarizarea cu domeniul din care fac parte datele. Și mai important, este bine ca rezultatele unei clasificări să fie interpretate de un expert din domeniul datelor.
În lucrarea de față vom exemplifica cu rezultate obținute utilizând clasificarea nesupervizată asupra unor imagini multispectrale din astronomie.
Lucrarea este structurată pe trei capitole:
Capitolul I, intitulat Context general, descrie cadrul general al domeniului abordat și conține două mari subcapitole Analiza imaginilor digitale și Recunoașterea formelor.
Analiza imaginilor digitale prezintă noțiunile de bază din domeniul prelucrării și analizei imaginilor digitale. Sunt trecute în revistă principalele tipuri de imagini digitale, structura unui sistem de prelucrare și analiză a imaginilor, precum și modalitățile de stocare a imaginilor în memorie și pe suport extern.
Cel de-al doilea subcapitol Recunoașterea formelor se deschide cu un paragraf ce descrie conceptele fundamentale din acest domeniu. Următoarele paragrafe prezintă noțiunile matematice referitoare la spațiul formelor și la clasificarea acestora.
Capitolul al doilea, intitulat Suport de realizare este structurat pe trei subcapitole. Metode de clasificare abordează principalele tehnici de clasificare nesupervizată, iar Segmentarea imaginilor metodele de segmentare a imaginilor ce vor fi utilizate în realizarea aplicației. Urmează apoi o scurtă introducere în Teoria codurilor.
Capitolul al III-lea Considerații de implementare prezintă o suită de patru tipuri de aplicații posibile în domeniul prezentat.
Clasificarea imaginilor și Segmentarea imaginilor evidențiază cercetările efectuate în domeniul analizei imaginilor multispectrale utilizând algoritmii Isodata și n-medii, precum și metodele de îmbunătățire a acestor tehnici. Pentru evaluarea rezultatelor analizei datelor au fost folosite soft-uri specializate în acest domeniu precum Matlab și Envi. Aplicații în teoria codurilor prezintă apoi rolul codurilor Hadamard în prelucrarea imaginilor obținute de pe solul marțian de către misiunea spațială Mariner 9. În final, este propusă ca Aplicație didactică de laborator o modalitate de analiză a imaginilor de pe Marte ce poate fi realizată de către elevi.
I. Context general
1. 1. Analiza imaginilor digitale
1.1.1. Definiții
Prelucrarea și analiza imaginilor (numită adeseori prescurtat doar prelucrarea imaginilor) s-a născut datorită ideii și necesității de a înlocui observatorul uman printr-o mașină. Este important de precizat că analiza imaginilor a mers mai departe decât simpla înlocuire a observatorului uman, deoarece au apărut soluții inovatoare pentru probleme cu care acesta nu mai fusese confruntat – ca în cazul imaginilor no-vizibile (imagini acustice, ultrasonore, radar). Prelucrarea imaginilor înglobează posibilitatea de a dezvolta mașina totală de viziune, capabilă să realizeze funcțiile vizuale ale oricărei viețuitoare (desigur, după realizarea a importante dezvoltări teoretice și tehnologice).
Trebuie remarcată terminologia anglo-saxonă (originală), în care disciplina este denumită Digital Image Processing, deci prelucrarea digitală a imaginilor. Prin prelucrarea digitală a imaginilor se înțelege prelucrarea pe un calculator digital a unor date bidimensionale (imagini). Termenul cheie este cuvântul digital, înlocuit adesea în mod eronat în multe traduceri românești cu termenul de numeric. După cum o arată dicționarul limbii române moderne, definiția cuvântului numeric este aceea de "care aparține numerelor, privitor la numere, exprimat prin numere". Rezultatul oricărui calcul este numeric. Termenul digital înseamnă însă "ceea ce este referitor la reprezentarea informației discrete în calculatoare".
Deci atâta vreme cât acceptăm ideea că unealta de lucru în prelucrarea imaginilor este calculatorul, și acesta la rândul său este digital, atunci și prelucrarea este la rândul ei digitală, ca un caz particular al oricărei prelucrări numerice. Desigur că există însă și prelucrări de imagini care sunt analogice – așa cum sunt toate prelucrările ce au loc în cadrul lanțului de transmisie și recepție a imaginii standard de televiziune.
1.1.2. Imagini digitale
La început, imaginile sunt semnale, dar nu funcții temporale, ci funcții definite pe un domeniu spațial. Orice imagine este o structură bidimensională (tablou, matrice) de date. Un element al imagini se numește pixel (cuvânt preluat din engleză, unde provine de la „picture element”). Aceste date pot fi numere naturale, reale sau complexe, reprezentate însă pe un număr finit de biți. După tipul datelor din aceastretate de un expert din domeniul datelor.
În lucrarea de față vom exemplifica cu rezultate obținute utilizând clasificarea nesupervizată asupra unor imagini multispectrale din astronomie.
Lucrarea este structurată pe trei capitole:
Capitolul I, intitulat Context general, descrie cadrul general al domeniului abordat și conține două mari subcapitole Analiza imaginilor digitale și Recunoașterea formelor.
Analiza imaginilor digitale prezintă noțiunile de bază din domeniul prelucrării și analizei imaginilor digitale. Sunt trecute în revistă principalele tipuri de imagini digitale, structura unui sistem de prelucrare și analiză a imaginilor, precum și modalitățile de stocare a imaginilor în memorie și pe suport extern.
Cel de-al doilea subcapitol Recunoașterea formelor se deschide cu un paragraf ce descrie conceptele fundamentale din acest domeniu. Următoarele paragrafe prezintă noțiunile matematice referitoare la spațiul formelor și la clasificarea acestora.
Capitolul al doilea, intitulat Suport de realizare este structurat pe trei subcapitole. Metode de clasificare abordează principalele tehnici de clasificare nesupervizată, iar Segmentarea imaginilor metodele de segmentare a imaginilor ce vor fi utilizate în realizarea aplicației. Urmează apoi o scurtă introducere în Teoria codurilor.
Capitolul al III-lea Considerații de implementare prezintă o suită de patru tipuri de aplicații posibile în domeniul prezentat.
Clasificarea imaginilor și Segmentarea imaginilor evidențiază cercetările efectuate în domeniul analizei imaginilor multispectrale utilizând algoritmii Isodata și n-medii, precum și metodele de îmbunătățire a acestor tehnici. Pentru evaluarea rezultatelor analizei datelor au fost folosite soft-uri specializate în acest domeniu precum Matlab și Envi. Aplicații în teoria codurilor prezintă apoi rolul codurilor Hadamard în prelucrarea imaginilor obținute de pe solul marțian de către misiunea spațială Mariner 9. În final, este propusă ca Aplicație didactică de laborator o modalitate de analiză a imaginilor de pe Marte ce poate fi realizată de către elevi.
I. Context general
1. 1. Analiza imaginilor digitale
1.1.1. Definiții
Prelucrarea și analiza imaginilor (numită adeseori prescurtat doar prelucrarea imaginilor) s-a născut datorită ideii și necesității de a înlocui observatorul uman printr-o mașină. Este important de precizat că analiza imaginilor a mers mai departe decât simpla înlocuire a observatorului uman, deoarece au apărut soluții inovatoare pentru probleme cu care acesta nu mai fusese confruntat – ca în cazul imaginilor no-vizibile (imagini acustice, ultrasonore, radar). Prelucrarea imaginilor înglobează posibilitatea de a dezvolta mașina totală de viziune, capabilă să realizeze funcțiile vizuale ale oricărei viețuitoare (desigur, după realizarea a importante dezvoltări teoretice și tehnologice).
Trebuie remarcată terminologia anglo-saxonă (originală), în care disciplina este denumită Digital Image Processing, deci prelucrarea digitală a imaginilor. Prin prelucrarea digitală a imaginilor se înțelege prelucrarea pe un calculator digital a unor date bidimensionale (imagini). Termenul cheie este cuvântul digital, înlocuit adesea în mod eronat în multe traduceri românești cu termenul de numeric. După cum o arată dicționarul limbii române moderne, definiția cuvântului numeric este aceea de "care aparține numerelor, privitor la numere, exprimat prin numere". Rezultatul oricărui calcul este numeric. Termenul digital înseamnă însă "ceea ce este referitor la reprezentarea informației discrete în calculatoare".
Deci atâta vreme cât acceptăm ideea că unealta de lucru în prelucrarea imaginilor este calculatorul, și acesta la rândul său este digital, atunci și prelucrarea este la rândul ei digitală, ca un caz particular al oricărei prelucrări numerice. Desigur că există însă și prelucrări de imagini care sunt analogice – așa cum sunt toate prelucrările ce au loc în cadrul lanțului de transmisie și recepție a imaginii standard de televiziune.
1.1.2. Imagini digitale
La început, imaginile sunt semnale, dar nu funcții temporale, ci funcții definite pe un domeniu spațial. Orice imagine este o structură bidimensională (tablou, matrice) de date. Un element al imagini se numește pixel (cuvânt preluat din engleză, unde provine de la „picture element”). Aceste date pot fi numere naturale, reale sau complexe, reprezentate însă pe un număr finit de biți. După tipul datelor din această structură bidimensională, imaginile prelucrate pot fi împărțite în mai multe categorii:
imagini scalare, în care fiecare componentă este un scalar (un unic număr); ca
exemple de astfel de imagini se pot da imaginile monocrome (în care punctele au
doar două valori posibile, ce corespund unui conținut binar al imaginii, în general
alb-negru) și imaginile cu nivele de gri (de tipul imaginii de luminanță de pe ecranele
televizoarelor alb-negru).
imagini vectoriale, în care fiecare componentă este un vector de numere; cazul
particular cel mai de interes este acela al imaginilor color, în care vectorul are trei
elemente (ce corespund celor trei constituente de bază ale oricărei culori); în general,
pentru imaginile multicomponentă, vectorul asociat fiecărui punct din imagine are
mai multe elemente (caz ce corespunde imaginilor preluate în mai multe benzi
de frecvență, așa cum sunt imaginile de teledetecție ale sateliților, imaginile de
termodetecție în benzile de infraroșu,…). Tot în categoria imaginilor vectoriale
intră însă și imaginile stereo (o pereche de imagini ale aceleiași scene, luate din
unghiuri diferite) și secvențele de imagini.
Conform unor statistici, dintre imaginile prelucrate în aplicații funcționale, 20 % sunt alb-negru, 32 % sunt cu nivele de gri, 20 % sunt color, 10 % sunt imagini stereoscopice și 18 % sunt secvențe de imagini.
În mod clasic, valoarea unui element al unei imagini este o măsură a intensității luminoase în punctul considerat; acesta nu este însă decât un caz particular. După natura lor, imaginile pot fi clasificate ca imagini abstracte, imagini non-vizibile și imagini vizibile. Imaginile abstracte sau modelele sunt de fapt funcții (matematice), continue sau discrete, de două variabile. Imaginile non-vizibile, care, evident, nu pot fi percepute în mod direct de ochiul uman, sunt de fapt achiziții ale unor câmpuri bidimensionale de parametri fizici (presiune, temperatură, presiune, densitate, …). În fine, imaginile ce pot fi percepute în mod direct de către ochiul uman (deci imaginile vizibile) sunt la rândul lor imagini optice, generate ca distribuții de intensitate luminoasă (așa ca hologramele, imaginile de interferență și difracție) sau imagini propriu-zise (de luminanță – în sensul curent al termenului, ce se referă la fotografii, desene, picturi, schițe, scheme și altele din aceeași categorie).
O altă împărțire a imaginilor scalare se poate face după semnificația ce se dă valorii numerice a pixelilor. Vom distinge astfel imagini de intensitate și imagini indexate. O imagine de intensitate este o imagine în care valoarea fiecărui pixel este o măsură directă a intensității luminoase sau a mărimii fizice preluate de senzor, ca de exemplu în imaginile cu nivele de gri. Pixelii unei imagini de intensitate pot avea orice fel de valori: reale sau naturale (depinzând dacă imaginea este sau nu cuantizată).
O imagine indexată este acea imagine în care valoarea fiecărui pixel este un indice prin care se regăsește informația de culoare asociată pixelului respectiv. Deci, pentru afișarea sau reprezentarea unei imagini indexate este necesară o informație suplimentară, de asociere între indici și culori. Această asociere se face prin intermediul tabelei de culoare. Tabela de culoare este o matrice în care fiecare linie conține descrierea unei culori (deci cele trei componente ce definesc culoarea – în mod tipic intensitățile relative de roșu, verde și albastru ce compun culoarea dată printr-un amestec aditiv). Deci tabela de culoare are trei coloane; numărul de linii al tabelei de culoare este egal cu numărul de culori din imaginea reprezentată și este în mod tipic o putere a lui doi (16, 256, …). Indicele (valoarea pixelului) va fi numărul de ordine al liniei din tabela de culoare pe care se găsește descrierea culorii. Este evident că valorile pixelilor unei imagini indexate nu pot fi decât numere naturale (deoarece sunt indici într-o matrice).
Această tehnică este folosită și în grafica pe calculator. Afișarea imaginilor pe ecranul monitorului se face corespunzător unui anumit mod grafic, determinat din placa video a calculatorului. Un mod video definește numărul maxim de culori ce pot fi utilizate simultan și dimensiunile ecranului (în pixeli de afișaj). Culorile utilizate la un moment dat sunt grupate într-o paletă de culori de afișare. Paleta de afișare este o structură logică definită în BGI (Borland Graphics Interface), pentru programare în sesiuni de tip DOS, ca:
struct palettetype { unsigned char size;
int colors[MAXC0L0RS+1]; }
Modificarea unei culori din paletă (o intrare a tabelului) se face cu:
void far setpalette(int index_culoare, int culoare);
Afișarea unui pixel cu o anumită culoare se face cu:
putpixel(int pozx, int pozy, int index_culoare);
Sub Windows, este suportată și specificarea directă a culorii de afișat (sub forma unui triplet RGB), sistemul de operare aproximând culoarea respectivă cu cea mai apropiată culoare disponibilă din paleta de lucru curentă (în acest fel, utilizatorul poate neglija existența acesteia).
Pentru o imagine cu nivele de gri, componentele de roșu, verde și albastru ale fiecărei culori din paleta de culoare sunt identice. Dacă specificarea componentelor de culoare se face prin numere de 8 biți (deci între 0 și 255, adică cazul cel mai des folosit), tabela de culoare va avea 256 de culori (tonuri de gri) diferite. Specificarea acestora se va face cu indecși între 0 și 255, alocați conform convenției 0 – negru, 255 – alb. În acest fel, pentru o imagine indexată cu nivele de gri, nu mai este necesară specificarea tabelei de culoare; culorii reprezentate de indexul i îi corespunde nivelul de gri i, adică tripletul RGB (i,i,i).
Modelul imagini indexate este un caz particular de folosire a tehnicii dicționar (sau tehnicii tabelului de echivalență – Look Up Table – LUT): o tehnică de regăsire a unei cantități de informație folosind asocierea unei chei de căutare mult mai mici.
1.1.3. Structura unui sistem de prelucrarea și analiza imaginilor
Structura tipică a unui sistem de prelucrarea (evident digitală) și analiza imaginilor este alcătuită din punct de vedere funcțional dintr-un număr mic de blocuri (vezi figura 1.1):
sistemul de formare a imaginii (de exemplu sistemul de lentile al camerelor de luat vederi): strânge radiația electromagnetică a obiectului studiat pentru a forma imaginea trăsăturilor de interes
convertorul de radiație: convertește radiația electromagnetică din planul imaginii într-un semnal electric.
Fig. 1.1: Schema generală a unui sistem de analiza și prelucrarea imaginilor
Sistemul de formare a imaginii și convertorul de radiație formează senzorul; acesta realizează o proiecție plană (bidimensională) a scenei reale (care este în general tridimensională). Un studiu realizat în Germania în anul 1996 – inventarierea sistemelor de
preluare a imaginilor folosite în industrie – indică o distribuție a tipurilor de senzori după gama de radiație captată conform tabelului 1.1:
Tabel 1.1: Tipuri de senzori folosiți în prelucrarea imaginilor
sistemul de achiziție (echivalent unui frame-grabber sau video-blaster): convertește semnalul electric al senzorului într-o imagine digitală, pe care o stochezi acesta nu este altceva decât un dispozitiv de eșantionare (discretizare a suportului imaginii) și cuantizare (discretizare a domeniului de valori a imaginii).
sistemul de prelucrare (în mod tipic un calculator, fie el PC sau stație de lucru);În această categorie se încadrează însă și mașinile specializate de calcul, calculatoarele de proces etc.
software-ul specializat: implementează algoritmii de prelucrare și analiză
Unitatea de prelucrarea hardware (deci calculatorul) folosită la aplicațiile de prelucrarea imaginilor funcționale la acea dată este în cea mai mare majoritate a cazurilor un PC obișnuit, cu performanțe standard; datele sunt sintetizate în tabelul 1.2:
Tabel 1.2: Unități de calcul folosite în prelucrarea imaginilor
Sistemul software specializat care este responsabil cu realizarea efectivă a unei sarcini concrete poate fi descompus în mai multe module, nu neapărat bine separate și nu neapărat prezente împreună: îmbunătățirea, restaurarea, compresia, segmentarea și analiza.
Blocul de îmbunătățire a imaginilor are ca scop accentuarea anumitor trăsături (ale obiectelor conținute în imagine) pentru ușurarea unor sarcini ulterioare de analiză automată sau interpretare prin afișare. Asemenea metode pot fi utile la extragerea trăsăturilor caracteristice ale obiectelor, eliminarea zgomotelor suprapuse imaginii, mărirea confortului vizual. Acești algoritmi nu măresc conținutul informațional al imaginii și sunt în general interactivi și puternic dependenți de aplicație.
Restaurarea imaginilor se referă la eliminarea sau minimizarea efectelor unor perturbații și a unor degradări. Perturbațiile reprezintă în general zgomotele (modelate ca procese aleatoare) ce se suprapun în cursul achiziției imaginii (din cauza senzorului și a lanțului de transmisiune și captare); degradările sunt cauzate de imperfecțiunile și limitările deterministe ale senzorului (efecte de apertură, timp de expunere, deficiențe geometrice ale sistemului de lentile, …).
Compresia imaginilor se referă la reducerea volumului de date (numărului de biți) cu care este reprezentată imaginea, printr-o transformare reversibilă – imaginea trebuie să poată să fie recuperată integral (sau cu diferențe foarte mici, controlabile) din versiunea sa comprimată.
Segmentarea este procesul de descompunere a unei imagini (sau scene) în elementele (obiectele) sale constituente. Adeseori, segmentarea este strâns legată de algoritmii de analiză, al căror scop este de a realiza măsurători cantitative sau evaluări calitative asupra unor anumite categorii de obiecte, prezente în imaginea dată.
Sfera de aplicabilitate a tehnicilor de prelucrarea și analiza imaginilor este deosebit de largă; practic, în orice domeniu de activitate se pot găsi numeroase aplicații. Această clasă de aplicații extrem de specifice a fost caracterizată drept „consumul imaginii” (imaginea folosită în vederea analizei, deci a luării unor decizii). Imaginile preluate de către sateliți pot fi folosite la descoperirea resurselor terestre, cartografiere geografică, predicția recoltelor, urmărirea dezvoltării urbane, urmărirea vremii, controlul și prevenirea incendiilor și inundațiilor, precum și alte aplicații ecologice și militare. Aplicațiile transmisiei și compresiei imaginilor se regăsesc în televiziunea digitală, sistemele de teleconferință, transmisiile fax, birotică, comunicația pe rețele distribuite, sisteme de securitate cu circuit închis, aplicații militare. În aplicațiile medicale sunt prelucrate radiografiile cu raze X, angiogramele, ecografiile, tomografiile, imaginile de rezonanță magnetică nucleară. Acestea pot fi utilizate pentru monitorizarea pacienților și pentru descoperirea și identificarea de boli și tumori.
O largă clasă de aplicații sunt cele industriale, în care componentele de prelucrarea și analiza imaginilor sunt folosite în sisteme mai mari de asigurare a calității produselor (metrologie, controlul calității – inclusiv defectoscopie nedistructivă). Soluțiile sunt extrem de specifice, puternic legate de procesul de fabricație urmărit și tind să devină din ce în ce mai utilizate odată cu impunerea normelor de „calitate totală” ale standardului ISO9000.
Din acest punct de vedere este interesantă comparația între câteva caracteristici ale sistemului vizual și de prelucrare uman și un sistem de prelucrarea și analiza imaginilor, folosite pentru aplicații industriale, prezentată în tabelul 1.3.
Tabel 1.3: Comparația între caracteristici esențiale ale sistemului vizual uman și sistemele de prelucrarea și analiza imaginilor
1.1.4. Stocarea imaginilor
Se poate considera că există două moduri de stocare a imaginilor: stocarea în memoria de lucru a unității de prelucrare a imaginii de lucru (care este o stocare de scurtă durată – doar pe durata prelucrării efective) și stocarea de lungă durată imaginilor, în fișiere, pe suporturi externe de memorie (benzi, discuri, etc.). Diferența esențială între cele două tipuri de stocare este aceea că în memorie imaginea va fi reprezentată complet, în formă necomprimată, pentru a permite accesul rapid direct la informația fiecărui pixel.
1.1.4.1 Stocarea imaginilor în memorie
Principalul limbaj de programare utilizat pentru aplicații cu calcule intensive rămâne încă limbajul C (C++). Stocarea imaginilor se va face, evident, prin intermediul unor variabile ce implementează structuri de date bidimensionale. Ceea ce este deosebit este modul de declarare a acestora: declararea statică nu este convenabilă din cauza dimensiunilor în general mari ale imaginilor, și deci este necesară o declarare dinamică. Particularitatea este dată de memorarea separată a fiecărei linii (sau coloane) a matricii într-un vector alocat dinamic, și gruparea adreselor de început a acestora într-un vector de pointeri, la care se va reține adresa de început (deci un alt pointer). Dacă considerăm un tip generic de date pentru componentele matricii (caracter, sau întreg, sau real), atunci o secvență C de declarare a unui imagini poate fi:
tip ** imagine;
unsigned int contor;
imagine=(tip**) malloc(nr_linii*sizeof(tip*));
for (contor=0;contor<nr_linii;contor++)
imagine[contor]=(tip*) malloc(nr_coloane*sizeof(tip));
Se remarcă folosirea constantelor nr_linii și nr_coloane (cu semnificație evidentă) și a tipului generic tip pentru valoarea pixelilor. Linia a 3-a alocă spațiul pentru un masiv de pointeri la date de tip pointer; spațiul de memorie necesar (argumentul funcției malloc) este dat de numărul de pointeri la liniile imaginii ce înmulțește dimensiunea unui astfel de pointer (sizeof(tip*)). Valoarea imagine [contor] este adresa de început a spațiului de memorie la care încep valorile pixelilor de pe linia contor; aceștia sunt stocați într-un vector declarat de malloc(nr_coloane*sizeof(tip)). Trebuie remarcată conversia de tip (cast) obligatorie ce însoțește fiecare alocare de memorie (se știe că funcția malloc întoarce un pointer la void). De asemenea se observă că secvența anterioară nu face nici un fel de verificare a succesului operației de alocare de memorie (verificarea faptului că valoarea returnată de funcția malloc nu este NULL). În mod implicit, la compilare, toți pixelii (toate valorile matricii imagine) sunt inițializați cu 0.
Spre deosebire de C, limbajul Matlab aduce mari simplificări. Există un singur tip de date, reprezentate pe 8 octeți (caracteristică ce se schimbă începând cu versiunea 5.0, ce admite valori reale, întregi sau caracter, declarate explicit). Orice variabilă Matlab este creată în momentul folosirii sale în membrul stâng al unei expresii (deci nu este necesară declararea prealabilă folosirii); orice variabilă este o matrice (scalarul este o matrice de o linie și o coloană). Funcțiile returnează matrici. Secvența C anterioară este echivalentă cu:
imagine=zeros(nr_linii,nr_coloane);
1.1.4.2 Stocarea imaginilor în fișiere
Un fișier este entitatea logică de organizare a informației înscrise pe mediile magnetice de stocare și se compune dintr-un șir de octeți. Pentru stocarea imaginii este necesar ca acești octeți să conțină informația aferentă pixelilor precum și informație despre tipul imaginii: dimensiunile acesteia, dacă este sau nu indexată, dacă are sau nu o tabelă de culoare atașată, dacă este sau nu comprimată și după ce metodă. Anumite structuri de fișiere au fost impuse de-a lungul timpului de firme producătoare de software sau de organisme de standardizare, căpătând denumirea de formate de imagini. Formatele de imagini s-au făcut cunoscute mai ales după extensia standard a fișierelor ce conțin imaginile stocate după formatul respectiv: BMP, TIF, GIF, PCX, JPG … . În cele ce urmează ne vom referi la formatele RAW(cunoscut și ca IMG), unul dintre cele mai rudimentare formate de fișiere imagine, și Windows Bitmap -BMP al firmei Microsoft, care este unul dintre cele mai larg recunoscute formate de fișiere.
Un fișier RAW conține imagini indexate cu nivele de gri, de formă pătrată. Fișierul nu are antet (dimensiunile imaginii fiind deduse din dimensiunea fișierului ce o conține) și nu conține nici tabel de culoare (acesta are toate componentele liniei i egale între ele, reprezentând griuri). Fiecare pixel al imaginii este codat cu numărul corespunzător de biți (4, 8, etc); imaginea este baleiată în ordinea normală (începând cu prima linie a imaginii, de la stânga la dreapta).
Un fișier BMP are trei componente consecutive: un antet de fișier (BITMAPFILEHEADER), o structură de informație a imaginii(BITMAPINFO) și codarea pixelilor. Antetul de fișier (BITMAPFILEHEADER) conține informații asupra tipului, dimensiunii și reprezentării fișierului Bitmap independent de dispozitiv (DIB – Device Independent Bitmap); semnificațiile componentelor sunt date în tabelul 1.4.
typedef struct tagBITMAPFILEHEADER{
WORD bfType;
DWORD bfType;
WORD bfReservedl;
WORD bfReserved2;
DW bfOffBits;
}BITMAPFILEHEADER;
Structura de informație a imaginii (BITMAPINFO) conține informații asupra dimensiunilor și culorilor unui DIB, și este alcătuită din două componente: antetul structurii de informații (BITMAPINFOHEADER), a cărui componente sunt descrise în tabelul 1.5 și tabelul de culoare, format din structuri RGBQUAD.
Tabel 1.4: Descrierea câmpurilor structurii BITMAPFILEHEADER
Tabel 1.5: Descrierea câmpurilor structurii BITMAPINFOHEADER
typedef struct tagBITMAPINFOHEADER{
DWORD biSize;
DWORD biWidth;
DWORD biHeight;
WORD biPlanes;
WORD biBitCount;
DWORD biCompression;
DWORD biSizelmage;
DWORD biXPelsPerMeter;
DWORD biYPelsPerMeter;
DWORD biClrUsed;
DWORD biClrlmportant;
} BITMAPINFOHEADER;
Structura RGBQUAD descrie o culoare prin componentele sale de roșu, verde și albastru, și un câmp rezervat având valoarea 0.
typedef struct tagRGBQUAD{ BYTE rgbBlue; BYTE rgbGreen; BYTE rgbRed; BYTE rgbReserved; }RGBQUAD;
Codarea pixelilor se face după câteva reguli. Fiecare pixel va fi codat pe biBitCount biți; dacă biBitCount este 1, 4 sau 8, imaginea va fi indexată și fișierul conține tabela de culoare asociată imaginii. Codurile pixelilor se grupează pe octeți (deci pentru o codare de 4 biți per pixel, fiecare octet de cod va corespunde la doi pixeli alăturați). Dacă biBitCount este 24, pentru fiecare pixel se asociază direct trei octeți, ce reprezintă componentele de roșu, verde și albastru ale culorii respective; această imagine se numește True Color și nu mai are un tabel de culoare asociat. Denumirea de True Color (culoare adevărată) provine din faptul că numărul total de culori ce se pot astfel reprezenta (224) depășește limita sensibilității umane de discernere a culorilor.
Codarea se face independent pe fiecare linie orizontală a imaginii. Codurile (indexurile) tuturor pixelilor unei linii sunt concatenate; șirul rezultat trebuie să fie multiplu de 32 de biți (sau de 4 octeți, sau să conțină un număr întreg de DWORD's). Dacă această constrângere nu este respectată, linia respectivă se completează cu numărul necesar de biți (care, în mod evident, nu vor fi utilizați la citirea imaginii din fișier). Codarea imaginii începe cu ultima linie, și pentru fiecare linie baleiajul este normal (de la stânga la dreapta).
1. 2 Recunoașterea formelor
1.2.1. Concepte fundamentale
1.2.1.1. Definiție
Recunoașterea formelor este un termen general ce poate desemna una dintre următoarele noțiuni:
Recunoașterea: Fiind dat un tipar (de exemplu imagini ale feței umane, text scris, o priveliște) se generează la ieșire un nume (categoria de percepție);
Clasificare/Categorizare: Tiparele de intrare sunt clasificate/categorizate într-o mulțime de clase/categorii;
Asocierea: Elementul asociator “învață” să stabilească conexiuni între două tipare (concepte). De exemplu: “foc” și “fierbinte”, “banana” și “galben”.
Completarea și perfecționarea.
Prin recunoașterea formelor se înțelege în mod obișnuit acel ansamblu de metode și tehnici cu ajutorul căruia se poate realiza o clasificare în cadrul unei mulțimi de obiecte, procese sau fenomene. Setul de obiecte, procese sau fenomene care urmează a fi clasificate pot fi obiecte (fenomene) fizice sau structuri intelectuale, prin acestea înțelegând ansamblul concretizat de procese legate de o activitate intelectuală coerentă (scris, vorbit, etc)
Scopul recunoașterii formelor constă în determinarea clasei din care face parte o colecție de observabile. Metoda este deosebit de utilă atunci când abordările directe sunt imposibile sau când inferențele teoretice lipsesc.
Stabilirea numărului de clase în care se împart formele este o problemă particulară care depinde exclusiv de aplicațiile concrete ale metodei.
Recunoașterea formelor este un proces ce constă în general din două etape:
învățarea: se folosesc două strategii:
învățarea supervizată (cu profesor): se presupune o cunoaștere “a priori” despre tipare pentru a învăța calculatorul cum să recunoască tiparele
învățarea nesupervizată (fără profesor): calculatorul învață de unul singur.
testarea: calculatorul reușește să recunoască tiparele.
1.2.1.2. Spațiul formelor
Conceptul fundamental al teoriei recunoașterii formelor este următorul:
Un obiect sau un fenomen variabil, Xj, este descris (caracterizat) printr-un set de n caracteristici xij (i=1,…,n). Toate aceste n caracteristici ale unui obiect formează o formă.
Mulțimea x={Xj}j=1,m poartă denumirea de spațiul formelor. Deci un obiect (formă) X poate fi reprezentat printr-un punct X(x1,…,xn) în spațiul formelor.
O problemă este aceea a raportului dintre numărul de forme luate în considerare, m, și numărul de dimensiuni al spațiului formelor, n, adică raportul m/n dintre numărul maxim de obiecte din setul respectiv, m, și numărul de caracteristici, n, aferent fiecăruia dintre obiecte. Dacă numărul de forme, m, este mai mic, egal sau numai puțin mai mare decât numărul de caracteristici atunci discriminarea dintre forme și atribuirea lor la diferitele clase posibile este un proces pur aleator.
În general, se consideră că acest raport m/n, pentru orice aplicație de recunoașterea formelor, trebuie să îndeplinească următoarele condiții:
unde m reprezintă numărul de forme, iar n este numărul de caracteristici independente (număr de dimensiuni).
Condiția (i) reprezintă minimum necesar pentru o clasificare binară, în timp ce condiția (ii) este de dorit în aplicațiile concrete ale tehnicilor de recunoașterea formelor.
1.2.1.3. Moduri de abordare a problematicii recunoașterii formelor
Pentru rezolvarea problemelor de recunoaștere a formelor au fost propuse și utilizate o mare varietate de tehnici matematice din teoria informației, statistica matematică, teoria deciziei, geometrie, etc. , dintre care se disting trei maniere diferite de abordare a problematicii acestui domeniu:
Abordarea statistică (numită și decizional-teoretică);
Abordarea sintactică (sau lingvistică);
Abordarea prin metoda rețelelor neurale.
În cadrul metodelor de recunoașterea formelor decizional-teoretice, din forme sunt extrase un set de măsurători caracteristice, denumite caracteristici. Recunoașterea fiecărei forme (atribuirea formei la o clasă specifică) se face, de obicei, prin partiționarea spațiului formelor, denumit și spațiul caracteristicilor.
Clasificarea formei de intrare se face pe baza unor caracteristici ale formei astfel încât să se poată presupune, cu un coeficient de siguranță cât mai mare, că ele sunt invariante, independente una față de alta și mai puțin sensibile la variații și deformări. În legătură cu acestea se pune problema selectării obiective a celor mai semnificative caracteristici precum și cea a clasificării (adică a luării deciziei pentru a atribuii claselor formelor de intrare respective).
1.2.1.4. Caracteristicile unui sistem general de recunoașterea formelor
Un sistem de recunoaștere a formelor trebuie să asigure, corect și eficient observarea, transformarea, prelucrarea preliminară (selectarea) și clasificarea eșantionului de date.
Elementele esențiale ale unui sistem general de recunoașterea formelor sunt următoarele: translatorul, selectorul de caracteristici (care realizează o prelucrare preliminară) numit și preprocesor, sau extractor de caracteristici și clasificatorul (Fig. 2.1). Deși aceste 3 subunități sunt interdependente, în cele ce urmează le vom prezenta separat.
Fig. 2.1 – Sistem general de recunoaștere a formelor
1.2.1.4.1. Translatorul
Translatorul transformă și transferă informațiile din lumea reală în spațiul formelor într-o formă compatibilă cu modul de reprezentare din calculatoarele electronice. În consecință datele primare, rezultat al observației sunt transformate într-un șir de mărimi scalare care formează vectorul de formă n-dimensional. Fiecare componentă xi a vectorului de formă X reprezintă o cantitate fizică măsurabilă; este foarte important ca ea să surprindă esența datelor primare.
Modul de implementare al translatorului depinde exclusiv de natura datelor primare. Dacă acestea sunt constituite dintr-o succesiune de valori măsurate la intervale de timp, cum sunt traseele EEG, atunci sunt necesare procedee de eșantionare în timp, pe când dacă ele sunt funcție de frecvență, cum sunt de exemplu spectrele în infraroșu ale compușilor chimici, atunci trebuie dezvoltate procedeele de eșantionare a frecvenței (respectiv numerelor de undă). În cazul imaginilor sunt luate în considerare suprafețele mai luminoase sau mai întunecate, muchiile sau formele geometrice. Aceasta este o problemă ceva mai complicată și, de aceea , au fost propuse o serie de metode pentru reducerea complexității imaginilor la un șir de măsurători.
O situație fericită, în care translatorul nu mai este necesar, apare atunci când informațiile din lumea reală sunt exprimate numeric (de exemplu, în cazul spectrelor de masă).
Vectorii de formă dezvoltați de translator constituie mărimile de intrare pentru selectorul de caracteristici.
1.2.1.4.2. Selectorul de caracteristici
Scopul selectorului de caracteristici constă în prelucrarea vectorilor de formă în așa fel încât procedeul de clasificare să fie optimizat.
Selectorul de caracteristici (denumit și extractor de caracteristici sau preprocesor) acceptă ca mărimi de intrare vectorii de formă produși de translator și operează asupra lor transformându-i pentru a elimina sau, cel puțin, pentru a reduce cantitatea de informație irelevantă sau ambiguă menținând în vectori suficientă informație pentru a putea discerne între diferitele clase de forme și descoperi invarianțele dintre formele aceleiași clase.
Pentru realizarea acestor deziderate au fost propuse și utilizate o mare varietate de metode.
Una dintre cele mai simple metode pentru prelucrarea vectorilor de formă constă în normarea acestora. O astfel de normare implică egalarea sumei componentelor fiecărui vector de formă (respectiv suma pătratelor componentelor lor) cu o constată arbitrară convenabil aleasă. Un alt procedeu, mult mai sofisticat, care utilizează matricea de covarianță duce, în final, la o ecuație matricială din care se obțin vectorii proprii și valorile proprii (procedeul numit analiza componentelor principale sau analiza Karhuneu-Loeve).
Pentru prelucrarea vectorilor de formă și selectarea celor mai reprezentative caracteristici au fost utilizate și o serie de transformări mult mai complexe, cum ar fi transformata Fourier.
Pentru identificarea caracteristicilor mai importante au fost utilizate forme model sau prototip, s-au dezvoltat și implementat tehnici interactiv, implicând reprezentări grafice și rutine speciale de comparare, s-au calculat parametrii statistici, cum sunt momentele sau histogramele direct din forme.
Această etapă este esențială, de ea depinde succesul sau insuccesul oricărui studiu de recunoaștere a formelor.
1.2.1.4.3. Clasificatorul
Sarcina oricărui clasificator este, în general, următoarea: având dată o mulțime de vectori de formă prelucrați corespunzător, numită set de formare, se pune problema determinării unei funcții de decizie f(X) astfel încât dacă:
f(X) > 0 atunci X aparține clasei 1
f(X) >= 0 atunci X aparține clasei 2
Această etapă în care este determinată funcția de decizie f(X) este cunoscută sub numele de fază de formare (formarea), de adaptare sau uneori de învățare. Scopul urmărit este minimalizarea probabilității de eroare în procesul de clasificare.
Conceptul de clasificare a formelor poate fi înțeles ca o partiționare a spațiului formelor, x ={X} prin atribuirea fiecărui vector X sau punct X (x1, …,xn) la o clasă de forme corespunzătoare în regiuni reciproc exclusive, fiecare regiune corespunzând unei clase de forme particulară. Din punct de vedere matematic problema clasificării poate fi formulată sub forma funcțiilor de decizie discriminate.
Fie 1, 1,….p cele p clase distincte posibile care urmează a fi recunoscute cu
X = 1 U 2 U ….Up,
1 2 …… p = Fd
și fie X=|xi |i=1,n vectorul de formă, xi reprezentând a i-a caracteristică reprezentativă. Atunci funcția de decizie discriminant f(X)=Dj (X) asociată clasei de forme j, j=1,…,p, astfel încât dacă forma de intrare reprezentată prin vectorul X, respectiv punctul X, este în clasa i, fapt pe care-l vom nota prin Xi , valoarea lui Di(X) trebuie să fie cea mai mare, adică pentru toți Xi vom avea satisfăcută relația:
Di(X) > Dj(X), i, j =1,…,p.
În felul acesta, în spațiul formelor x frontiera partiției, denumită limita de decizie, dintre regiunile corespunzând claselor i și respectiv, j, poate fi definită prin următoarea relație:
Fd= Di(X)-Dj(X) = 0
În figura 2.8. este reprezentat modelul unui clasificator care utilizează funcțiile discriminant. Forma de intrare este analizată conform relației de mai sus, clasificatorul furnizând drept ieșire indicele k aparține {1,2,…,p} corespunzător clasei k din care face parte forma respectivă X.
Fig. 2.2 – Modelul clasificatorului ce utilizează funcția discriminant
Pentru determinarea funcțiilor discriminant neparametrice setul de formare trebuie să fie mare și, de asemenea, reprezentativ pentru a permite estimarea acestora din funcțiile de probabilitate.
1.2.2. Exemplu de recunoaștere a formelor
Prin recunoașterea formelor ne interesează să obținem tehnici care să simuleze capacitatea umană de a recunoaște și clasifica forme. Presupunerea principalã făcută în acest domeniu este că eșantioanele pot fi caracterizate (în mod unic) printr-un set relevant de trăsături.
După măsurarea acestor trăsături particulare, un eșantion poate fi clasificat prin analizarea valorilor trăsăturilor măsurate.
Fig. 2.3: Ilustrarea grafică a problemei recunoașterii merelor și perelor
Să considerăm de exemplu problema deosebirii merelor de pere. Pentru ambele categorii pot fi definite trăsături relevante, de exemplu culoarea și forma. Problema clasificării este ilustrată în mod grafic în figura 2.3.
Putem considera că merele au o formă relativ circulară, pe când perele nu. Pe baza acestei presupuneri ar rezulta că ambele mulțimi sunt ușor de deosebit; și totuși unele mere pot să semene cu o pară. Dacă am folosi „gustul” ca a treia trăsătură am putea să le diferențiem mult mai ușor.
În teoria recunoașterii formelor ne interesează cum putem construi un clasificator dintr-un set de exemple în care sunt separate cele două clase. Cel mai de interes aspect este acuratețea acestui clasificator, întrucât de la un set limitat de exemple se pot construi mai mulți clasificatori.
Teoretic clasificatorul optim ce se poate construi (adică cel care are cea mai mică eroare posibilă) este clasificatorul Bayes. Clasificarea bayesiană se bazează pe presupunerea că se pot atribui probabilități formelor aparținând unor anumite clase. Astfel, un clasificator bayesian calculează probabilitatea ca unei forme măsurate (observate) să i se atribuie o anumită etichetă de clasă.
În situațiile practice este totuși necesară existența unui anumit număr de forme pentru a putea estima densitățile cât mai precis.
Fig. 2.4:Evoluția dimensiunii: pentru un număr fix de forme eroarea unui clasificator poate crește odată cu creșterea numărului de trăsături
1.2.3. Recunoașterea obiectelor
1.2.3.1. Sisteme senzoriale
Ideea unei mașini care sa poată efectua sarcini similare omului s-a conturat de multă vreme. În ultimii ani s-au făcut progrese impresionante în această direcție care s-au materializat prin realizarea unei game largi de roboți. Sarcini pe care omul le găsește simple, sunt complexe și dificile pentru roboți. Găsirea unui obiect, mutarea lui ocolind obstacolele, plasarea lui în poziția destinație sunt sarcini ușoare pentru operatorul uman, dar acestea depășesc posibilitățile majorității roboților.
Îmbunătățirea performanțelor roboților se poate face de exemplu prin dotarea acestora cu sistemele senzoriale complexe. Elementul cel mai important al sistemelor senzoriale îl reprezintă sistemul de vedere artificială. Prin intermediul lui se pot identifica obiectele din spațiul de lucru, se pot determina pozițiile și orientările lor, se poate crea o reprezentare sau un model al lumii înconjurătoare. Un sistem de vedere are două unități funcționale: dispozitivul de captare a imaginii și sistemul de analiză a acesteia. Dispozitivul de captare face legătura între lumea înconjurătoare și sistemul de vedere. În cazul omului dispozitivul de captare este ochiul, iar în cazul sistemului de vedere artificială, camera de luat vederi. Funcția de analiză a imaginilor în cazul omului este realizată de creier, iar în cazul sistemului de vedere artificială de microprocesor.
Lumea înconjurătoare este percepută prin intermediul unor senzori. Aceștia achiziționează informații de tip intensitate luminoasă, culoare sau informații de profunzime. Pentru îmbunătățirea semnalului, în vederea unor prelucrări ulterioare, se aplică asupra lui tehnici specifice prelucrării imaginilor. Tehnicile de segmentare se pot utiliza apoi pentru a realiza o descriere în concordanță cu informația senzorială. Prin folosirea unor sisteme de modelare se pot crea modele ale obiectelor din lumea înconjurătoare. Se obține astfel o reprezentare a modelului lumii, conținând date similare informațiilor ce pot fi detectate în semnalele de intrare.
Unul din obiectivele principale ale unui sistem de vedere este stabilirea unor relații de punere în corespondență între descrierea acordată cu informația senzorială și cunoștințele despre lume cuprinse în modelul lumii.
1.2.3.2. Recunoașterea obiectelor folosind modele
Lumea înconjurătoare este compusă în special din obiecte solide. Când un om privește un obiect pe care nu l-a mai văzut, el este capabil să strângă informații despre acesta din multe puncte de vedere diferite. Procesul de strângere și memorare a informațiilor despre obiect poartă numele de formare a modelului. Odată familiarizat cu obiectele, omul poate să le identifice fără alte investigații.
Problema recunoașterii obiectelor tridimensionale se definește astfel:
1. Fiind dată o colecție de obiecte solide etichetate, se examinează fiecare obiect și se formează modele ale acestora folosind informațiile rezultate din examinări.
2. Fiind dată o imagine digitală corespunzând lumii înconjurătoare, fiind accesibile toate modelele definite anterior procesului curent de formare a modelelor și fiind dată o listă a obiectelor distinctibile, se aplică următoarele acțiuni fiecărui obiect din listă:
a) se verifică dacă obiectul apare în semnalul de tip imagine,
b) pentru fiecare apariție a obiectului se determină poziția în cadrul imaginii cât și poziția față de un sistem de coordonate tridimensional cunoscut.
3. Dacă există regiuni în imagine care nu corespund obiectelor din listă, se caracterizează aceste regiuni și se memorează pentru a putea fi recunoscute în cazul apariției în analizele ulterioare.
1.2.3.2.1. Recunoașterea tridimensională din informații de profunzime
Semnalul este sub forma unei harți de profunzime. Recunoașterea va fi definită ca o aplicație inversă.
Se specifică prin Ntot numărul total de obiecte din modelul lumii. Numărul obiectelor distinctibile se notează prin Nobj. Fiecărui obiect distinctibil i se asociază un indice i, și va fi referit ca obiectul Ai. Numărul de apariții ale unui astfel de obiect se notează cu Ni. Avem relația:
Studiul curent este simplificat prin considerarea Ni=1 și Nobj=Ntot. Pentru descrierea relațiilor spațiale dintre obiecte se definește sistemul de coordonate al lumii și se folosește ca sistem de referință. Obiectele se vor poziționa în spațiu prin intermediul parametrilor de translație t și rotație r. Se definește modelul lumii W ca o mulțime de triplete ordonate (obiect, parametrii de translație, parametrii de rotație) în sistemul de coordonate al lumii:
W={(Ai,ti,ri)| i=0, …, Nobj}
Se notează mulțimea tuturor obiectelor cu L={Ai}. Mulțimea translațiilor se notează Rt, iar cea a rotațiilor cu Rr unde R reprezintă mulțimea numerelor reale.
Un senzor de profunzime captează o proiecție a scenei sub forma unei harți de profunzime. Această proiecție se modelează printr-un operator matematic P care aplică setul Ω=L*Rt*Rr peste un set de funcții scalare notat cu F:
P: Ω→F
Aceste funcții scalare sunt denumite imagini de profunzime:
f(x)=P(A,t,r)
unde x este vectorul planului focal al senzorului.
Pentru fiecare imagine de profunzime, există o aplicație inversă P-1care generează toate obiectele care au creat această hartă de profunzime.
Astfel, recunoașterea obiectelor din imagini de profunzime poate fi exprimată după cum urmează: fiind dat modelul lumii W și o funcție de tip imagine de profunzime f(x) să se calculeze aplicația P-1(f(x)) pentru a obține toate interpretările posibile ale funcției f(x).
Nu există o teorie generală asupra modului de a calcula eficient aceste aplicații inverse. Astfel, se utilizează metode de recunoaștere bazate pe descrierea scenelor în termenii unor trăsături locale tridimensionale de tip muchie sau suprafață, sau a unor trăsături globale și suprapunerea acestor descrieri cu reprezentări similare ale modelelor.
1.2.3.2.2. Recunoașterea bidimensională din informații de intensitate
Aplicând un operator de iluminare reflexie I hărții de profunzime se obține o imagine de intensitate i(x):
i(x)=I(max(P(Ai, ti, ri))
Imaginea i(x) este folosită pentru extragerea unor trăsături locale bidimensionale de tip punct, muchie, unghi sau a unor trăsături globale. Trăsăturile bidimensionale corespund proiecției trăsăturilor tridimensionale pe un plan perpendicular pe direcția de privire. Recunoașterea este o problemă de punere în corespondență a reprezentării scenei cu reprezentările modelelor. Determinarea poziției și orientării este dată de direcția asociată vederii modelului ce se potrivește cu reprezentarea scenei.
1.2.3.3. Structura unui sistem de recunoaștere
Structura unui sistem de recunoaștere este prezentată în figura 3.5. Acesta conține două faze: de învățare și de recunoaștere. Faza de învățare se bazează pe utilizarea mijloacelor CAD pentru proiectarea modelelor. Se conturează următoarele probleme: selectarea sistemului senzorial, selectarea și extragerea trăsăturilor, reprezentarea scenei și a modelelor, potrivirea reprezentărilor modelelor cu reprezentarea scenei.
Fig. 2.5. Structura unui sistem de recunoaștere
Selectarea sistemului senzorial corespunde alegerii tipului de imagine. Astfel, se pot folosi sisteme senzoriale furnizând imagini de intensitate sau imagini de profunzime. Imaginile digitale de intensitate sunt sub forma unor matrici bidimensionale, indicând intensitatea luminoasă a pixelilor imaginii. Imaginile de profunzime indică distanța dintre planul focal al senzorului și suprafețele obiectelor din scenă. Forma tridimensională a acestora aproximează forma suprafețelor obiectelor.
Descrierea obiectelor se face prin intermediul trăsăturilor globale sau locale extrase din imagini. Extragerea trăsăturilor globale este eficientă doar în cazul imaginilor cu obiecte simple, care se pot separa între ele și sunt distinctibile față de fond. Trăsăturile locale își păstrează relevanța și în cazul trunchierilor sau acoperirilor parțiale.
În imaginile de intensitate se pot pune în evidență zone caracterizate de variații rapide ale intensității (contururi) precum și regiuni cu proprietăți omogene. Prin prelucrarea acestora este posibilă extragerea unor trăsături globale (arie, perimetru, centru de greutate), precum și a unor trăsături locale (punctul, segmentul). Imaginile de profunzime permit extragerea facilă a trăsăturilor tridimensionale (globale și locale).
1.2.3.4. Tehnici de calcul utilizate de sistemele de recunoaștere
1.2.3.4.1. Clasificarea vectorului trăsăturilor globale
Metodele de clasificare a vectorului trăsăturilor globale sunt denumite metode decizionale. Condițiile necesare pentru aplicarea acestora sunt inexistența atingerilor și acoperirilor parțiale precum și separabilitatea obiectelor.
Trăsăturile globale grupează următoarele categorii: trăsături geometrice, funcționale și topologice. La rândul lor trăsăturile geometrice sunt de trei tipuri: trăsături caracteristice, trăsăturile de poziționare și coordonatele punctelor de contur. Trăsăturile caracteristice au rol în identificarea obiectelor. Printre acestea sunt următoarele: aria, perimetrul, raza maximă și cea minimă, dimensiunile dreptunghiului minim circumscris, momentele de inerție, media nivelelor de gri. Trăsăturile de poziționare și orientare servesc la determinarea orientării obiectului în scenă. Trăsăturile funcționale realizează o descriere a obiectelor din imagine făcând uz de dezvoltări analitice. În această categorie intră coeficienții Fourier ai funcției intrinseci a curbei de contur, momentele de inerție de diferite ordine calculate pe curba de contur, etc. Funcția intrinsecă a unei curbe se definește astfel:
k(s)=
unde s este abscisa curbilinie. Coeficienții Fourier calculați pe conturul de lungime L sunt:
Dintre trăsăturile topologice amintim: numărul componentelor conexe, numărul cavităților, etc.
1.2.3.4.2. Clasificarea vectorilor de formă și spațiul formelor
Mulțimea trăsăturilor globale selectate, în număr de n, pentru descrierea unei mulțimi de m forme, determină spațiul trăsăturilor. O formă caracterizată prin n trăsături este privită ca un vector X, denumit vector de formă:
Spațiul formelor se notează cu și este definit prin:
Clasificarea formelor atribuie fiecare vector posibil clasei din care face parte. Aceasta poate fi definită sub forma unei funcții discriminant. Fie ω1, ω2, …,ωm cele m clase, cu
unde F reprezintă frontiera dintre clase. Funcția discriminant Di(x) asociată clasei de forme ωi, i=1, 2, …, m are proprietatea că dacă forma reprezentată prin vectorul X face parte din ωi, atunci Di(X)>Dj(X) pentru i, j=1, 2, …, m și i≠j. Limitele de decizie sunt exprimate prin:
F=Di(X)-Dj(X)=0 pentrui, j=1, 2, …, m și i≠j.
Într-un spațiu bidimensional funcțiile discriminant liniare pot fi scrise sub forma:
x1 – mx2 – b = 0 sau W1x1 + W2x2 + W3 = 0 .
Funcția discriminant liniară asociată clasei de forme , într-un spațiu n dimensional, poate fi scrisă sub forma:
Limita de decizie dintre regiunile corespunzătoare claselor și este:
Fig.2.6Limita de decizie
De exemplu, fie două forme A și B descrise de vectorii , respectiv și limita de decizie D(X) = X1 – mX2 – b = 0. Forma A se găsește de o parte a frontierei D iar B de cealaltă parte (D(XA) = x1A – mx2A -b < 0, D(XB) = x1B – mx2B -b > 0).
1.2.3.4.3. Clasificarea de distanță minimală
Clasificarea de distanță minimală se bazează pe evaluarea distanțelor dintre forma de intrare și un set de vectori de referință. Pentru aceasta se consideră m vectori de referință R1, R2, …, Rm, cu Rj asociat clasei j. Clasificatorul va atribui forma X clasei j dacă distanța dintre aceasta și vectorul de referință Ri este minimă.
Se consideră două grupe de puncte distincte și se caută funcția de decizie care va putea separa spațiul formelor în doua regiuni ce vor corespunde celor două clase. Vectorii de referință reprezentând centrele celor două grupuri sunt determinați prin relația: unde m reprezintă numărul de forme din grupare.
În cazul unui spațiu al trăsăturilor n dimensional, distanța Euclidiană dintre o formă X și centrul R al unei grupări este dată de: d2 =(X-R)2 =
sau:
Deoarece primul tremen este independent de centrul de clasă R (S1 constant și pozitiv), d2 este minim când S2 este minim. Fie S2’ = – 0.5 S2 = d’ 2. d2 este minim când S2’ (adică d’ 2) este maxim.
Funcția de decizie va avea forma: Di (X) = XRi – 0.5 RiRi
1.2.3.4.4. Clasificarea Bayesiană
Se utilizează abordarea Bayesiană când distribuția formelor nu este total disjunctă și există suprapuneri semnificative ale valorilor trăsăturilor claselor de formă.
Fig. 2.7.
Să presupunem că probabilitatea formelor clasei i este p(i). Acesta înseamnă că apriori cunoaștem probabilitatea de a apariție a unei forme din clasa i. În absența oricăror alte cunoștințe putem minimiza probabilitatea erorii de decizie presupunând că forma necunoscută aparține clasei cu probabilitatea p(i) maximă. În luarea deciziei de apartenență se ține seama de observații asupra formelor.
Comportarea unei clase de forme este descrisă de probabilitatea condiționată p(X|i) care spune că o trăsătură măsurată a unei forme aparținând clasei i are valoarea X cu probabilitatea p(X|i). Bazat pe aceste cunoștințe se poate calcula probabilitatea a posteriori p(j|X) pentru o formă necunoscută, care spune că dacă o măsurătoare făcută asupra formei necunoscute are valoarea X forma aparține clasei j cu probabilitatea p(j|X). Probabilitatea p(j|X) este dată de formula lui Bayes:
unde m reprezintă numărul de clase. Forma necunoscută va fi atribuită clasei cu p(j|X) maxim.
1.2.3.5. Potrivirea modelelor cu datele senzoriale
Metodele cele mai directe de recunoaștere a obiectelor potrivesc modelele cu datele senzoriale.
O primă soluție pentru a realiza această potrivire constă în potrivirea folosind șabloane rigide de tip imagine. Pentru a identifica și localiza șablonul în imagine se folosește o măsură a similarității care să reflecte gradul de potrivire al șablonului cu datele de tip imagine.
O altă soluție este potrivirea folosind șabloane de tip curbă rigidă. Potrivirea se realizează prin corelarea curbelor șabloanelor cu curbele reprezentând contururile din imagine.
Cea de-a treia soluție este dată de potrivirea folosind șabloane parametrice bazate pe transformata Hough. Aceasta realizează o transformare din spațiul imagine în spațiul parametrilor sub forma unei scheme de votare. Fiecărui punct din spațiul parametrilor i se asociază un acumulator, votarea realizându-se prin baleierea imaginii, calculul parametrilor în fiecare pixel diferit de zero din spațiul imagine și înregistrarea corespunzătoare în spațiul parametrilor. Maximele din spațiul parametrilor vor caracteriza curbe corespondente în spațiul imagine.
1.2.4. Metode de clasificare bazate pe optimizarea unei funcții criteriu
1.2.4.1. Generalități
Metodele deterministe de clasificare sunt în esență proceduri de optimizare a unor funcții criteriu. Pentru construirea unei funcții criteriu se admite că fiecare clasă este reprezentată printr-un prototip geometric. Prototipurile pot fi punctuale, caz în care clasele au aproximativ formă sferică sau liniară, caz în care clasele au formă alungită. Funcția criteriu reprezintă o măsură a apartenenței sau a neapartenenței unei partiții a datelor la prototipurile claselor. Calitatea unei partiții este cu atât mai mare cu cât punctele fiecărei clase sunt mai grupate în jurul prototipului clasei.
O altă posibilitate pentru construirea funcției criteriu este aceea de a utiliza matricile de împrăștiere a datelor. Clasificarea optimă va fi aceea în care împrăștierea în interiorul fiecărei clase este minimă (clasele sunt mai compacte) și împrăștierea între clase este mai mare (clasele sunt cât mai separate una de alta) .
1.2.4.2. Disimilaritate. Normalizarea datelor
1.2.4.2.1. Măsuri de disimilaritate
Fie X o mulțime de obiecte de clasificat. Cea mai generală măsură de disimilaritate pe care o putem defini peste X este o funcție D: X*XR care satisface axiomele:
D(x,y)0 x,yX
D(x,x)=0 xX
D(x,y)=D(y,x) x,yX
Se admite că X este mulțime de instruire (cunoaștem pentru fiecare obiect din X clasa căruia el aparține) iar D este o măsură de disimilaritate adecvată. În aceste condiții este de așteptat ca disimilaritatea dintre obiectele aceleiași clase să fie sensibil mai mică decât disimilaritatea dintre puncte aflate în clase diferite. În cazul când datele sunt obiecte dintr-un spațiu euclidian vom considera metrica spațiului ca o măsură a disimilarității.
Dacă X și Y sunt puncte dintr-un spațiu euclidian d-dimensional
X = (x1, x2,…,xd),
Y =(y1, y2,…,yd),
atunci pentru orice număr real p1 se poate defini metrica:
d(X, Y) (1)
De fapt (1) reprezintă o familie infinită de matrici. Pentru p = 1 din (1) se obține:
d(X, Y) (2)
numită metrica absolută sau distanța City Black.
Dacă p = 2 se obține distanța euclidiană :
d(X, Y) (3)
iar pentru p se obține metrica valorii maxime :
d(X, Y) (4)
Să considerăm că valorile posibile ale caracteristicilor formelor de clasificat sunt în număr finit și fie d acest număr. În acest caz ca măsură de disimilaritate se pot utiliza distanțele Hamming și Lee.
Distanța Hamming dintre vectorii X și Y este dată de numărul componentelor (pozițiilor) în care cei doi vectori diferă. Ponderea Hamming a vectorului X, notată cu WH(X), se definește ca fiind numărul de componente nenule ale lui X. Rezultă că distanța Hamming dintre X și Y este egală cu ponderea Hamming a diferenței lor :
dH (X, Y)= WH(X, Y) (5)
Distanța Lee
Fie q un număr întreg, pozitiv, q2 și X = (x1, x2,…,xd), cu xi0,1, . . . ,q-1.
Ponderea Lee a vectorului X, notată cu WL(X), se definește ca fiind:
WL(X)
unde:
Distanța Lee a vectorilor X și Y se definește ca fiind ponderea Lee a diferenței lor:
dL (X, Y)= WL(X- Y) (6)
Pentru q = 2 și q = 3 distanțele Hamming și Lee coincid. Pentru q3 avem:
dL (X, Y) dH (X, Y), X, Y
De asemenea pentru q = 2 avem
dH (X, Y)
1.2.4.2.2. Împrăștierea datelor
În cele ce urmează vom considera că fiecare obiect de clasificat Xi se reprezintă ca un vector d-dimensional:
xi=( x1i, x2i, . . . ,xdi)
unde xji, specifică componenta j a vectorului xi .
Considerăm o mulțime de obiecte X=x1, x2, . . . , xp, xiRd.
Vom nota cu m vectorul medie a datelor:
m= (7)
Componenta mk a vectorului m este :
mk=
și reprezintă valoarea medie a caracteristicii k. Dacă ne raportăm din nou la mulțimea de obiecte X atunci caracteristica i a lui X este
Xi= xi1, xi2, . . . , xip
și deci vom putea scrie că :
mi= MX i
unde cu M am notat operatorul valoare medie.
Cu aceasta putem să definim dispersia valorilor în jurul valorii medii atât pentru:
caracteristica i
i2 = ii= M(Xi – mi)2 (8)
caracteristicile i și k
ik= M(Xi – mi)(Xk – mk) (9)
Relația (8) se mai poate scrie din care rezultă imediat prin dezvoltarea termenului din sumă
M(Xi2)-mi2 (10)
și deci
(11)
Cu aceste observații se poate defini matricea C(d,d) de componente ik ca reprezentând matricea de dispersie pentru mulțimea X de obiecte. În cadrul acestei matrici elementul ii va reprezenta împrăștierea (dispersia) norului de obiecte în direcția axei i a sistemului de coordonate .
Să considerăm acum un nor de obiecte
X=x1, x2, . . . , xp
al cărui vector medie coincide cu originea spațiului, adică M(X) = 0. Ne propunem să determinăm dispersia (împrăștierea) norului în direcția vectorului u. Considerând că obiectele prezintă 3 caracteristici de exemplu, devine posibilă reprezentarea norului de obiecte într-un spațiu tridimensional
Fig. 2.8. Nor de obiecte
Revenind într-un spațiu cu d dimensional Rd proiecția vectorului (a caracteristicilor obiectului i) xi pe direcția u este matrice [yi] de forma:
[yi]=[u]T[xi]
unde:
[u]T este transpusa matricii componentelor lui u
[xi] este matricea componentelor lui x
Identificând norul de obiecte X cu o matrice [X] de dimensiune d x p ale cărei linii corespund caracteristicilor iar coloane obiectelor:
Putem calcula o matrice [Y] a proiecțiilor norului de obiecte X pe direcția u. Putem scrie că:
[Y] = [u]T[X] (12)
Împrăștierea norului X în direcția u este dată de dispersia proiecțiilor punctelor sale pe u adică de dispersia lui [Y]. Putem deci scrie:
2([Y]) = 2([u]T[X])=M([u]T[X])2 – (M([u]T[X]))2
dar cum M(X) = 0 , dispersia u2X a norului în direcția u se scrie:
2uX=2([Y])= M([u]T[X])2 (13)
care dă împrăștierea grupării de obiecte în direcția u.
1.2.4.2.3. Normalizarea datelor
Caracteristicile unui obiect pot corespunde la mărimi fizice diferite și în consecință se exprimă prin unități de măsură diferite. Pentru calculul distanței ar trebui să adunăm, de exemplu, centimetri și kilograme. Din acest motiv înainte de aplicarea algoritmului de stabilire a apartenenței unui obiect la o clasă este necesar să efectuăm o uniformizare a diferitelor caracteristici. Această uniformizare se poate realiza într-o normalizare a datelor, astfel încât toate caracteristicile să aibă aceeași valoare medie și aceeași dispersie.
Transformarea
i=1,…,d (14)
este o transformare de normalizare, ce constă dintr-o translație și o transformare de scală. Prin această transformare a axelor de coordonate, toate caracteristicile au media zero și dispersia unu. În adevăr, media și dispersia noii caracteristici i se pot scrie:
M(Xi')= (15a)
și
i'2= 2(Xi') = M(Xi'-M Xi')2
ținând cont că M(Xi')=0 rezultă că :
i'2= M((Xi')2)
și deci
i'2= (15b)
Normalizarea (14) este utilă și în cazul când caracteristicile au aceeași unitate de măsură. În acest caz normalizarea realizează o uniformizare a rolului diferitelor caracteristici, împiedicând anumite caracteristici să devină dominante în calculul distanței numai datorită faptului că au valori numerice mari.
Dacă valorile unei caracteristici sunt mici, atunci aceste proiecții ale obiectelor pe axa corespunzătoare se reprezintă ca o singură clasă omogenă. Dispersia caracteristicii respective fiind mică , prin normalizare valorile numerice ale proiecțiilor se măresc. Ca urmare norul proiecțiilor nu mai apare omogen ci structurat în clase.
1.2.4.3. Măsuri de similaritate
O alternativă la folosirea unei măsuri de disimilaritate este considerarea unei măsuri a gradului în care obiectele de clasificat sunt asemănătoare.
O măsură (coeficient) de similaritate peste X este o funcție S:X*XR , care satisface axiomele:
S(x, y)0, S(x, y)= S(y, x), x , y X
S(x, x)= S(y, y) S(x, y) , x , y X
Dacă X este o submulțime a spațiului Rd, atunci ca o măsură a similarității vectorilor (formelor) x și y din X putem considera cosinusul unghiului dintre cei doi vectori. Avem deci măsura de similaritate:
S1(x,y)= (1)
unde :
(x .y) – este produsul scalar a doi vectori, pentru cazul dat avem x1y1+x2y2+…+xdyd
[x]T – transpusa matricii componentelor formei x
x – normala lui x :
Această măsură de similaritate este utilă atunci când mulțimea X a datelor este formată din clusteri liniari. O distanță poate induce o măsură de similaritate. Dacă d este o distanță peste X, atunci putem defini distanța normalizată d/dmax, unde:
Măsura de similaritate indusă de distanța d se definește prin
1.2.4.3.1. Măsuri de similaritate pentru vectori binari
Admitem că toate caracteristicile sunt binare. Fiecare obiect (formă) este reprezentat printr-un vector cu d componente care nu pot fi decât 0 sau 1. Vom pune xi=1 dacă obiectul x posedă atributul i și xi=0 în caz contrar. Dacă atributul i este prezent simultan la obiectele x și y, atunci avem xi yi =1.
Măsura de similaritate (1) poate fi reinterpretată pentru cazul caracteristicilor binare. În acest scop se observă că numărul de atribute prezente simultan la x și y este
S=
Rezultă că dă numărul de atribute pe care le posedă x. Atunci este media geometrică a numărului de atribute din și din și deci S dată de
este o măsură relativă a numărului de atribute comune. Modificând relația (1) se pot obține diverse măsuri de similaritate. Se pot obține astfel:
înlocuind numitorul cu numărul de atribute a unui obiect avem:
(2)
coeficientul lui Tanimoto
(3)
Această măsură este mult utilizată în probleme ridicate de regăsirea informației, biologie etc.
Se observă că dacă atributul i lipsește simultan din și atunci (1-xi)(1-yI)=1 și deci
T= (4)
este numărul atributelor ce lipsesc simultan din și .
Analog
u= (5)
v= (6)
reprezintă numărul atributelor prezente în dar care lipsesc din și respectiv numărul atributelor care sunt prezente în dar lipsesc din .
Cu aceste notații este ușor de văzut că sunt adevărate următoarele egalități
s+u+v+t = d (7a)
s+u = (7b)
s+v = (7c)
Ținând cont de considerentele anterioare, semnificația măsurilor de similaritate date mai jos este ușor de intuit:
S5(,)=, (Kendal-Sokal) (8)
S6(,)=, (Dice) (9)
S7(,)= , (Sokal-Sneath) (10)
S8(,)= (Yule) (11)
S9(,)= (Pearson) (12)
1.2.4.4. Funcția criteriu
Fie mulțimea obiectelor de clasificat. Ne propunem să găsim o tehnică de explorare a datelor, care să ne permită să descoperim structura naturală de clasificare, sau structura de clusteri a mulțimii datelor. Vom admite că structura de clasificare a mulțimii X este dată de o partiție a lui X.
Fiecare element a partiției va corespunde unei clase (nor, cluster) de obiecte, astfel încât punctele unei clase să fie mai asemănătoare decât punctele din clase diferite. Asemănarea obiectelor este dată de o măsura de similaritate sau de o măsură de disimilaritate. Pe baza unei astfel de măsuri putem construi o funcție criteriu. Problema de clasificare se reduce astfel la problema determinării partiției ce realizează optimul funcției criteriu (obiectiv). Pentru a construi o funcție obiectiv al cărei extrem să fie partiția căutată, avem nevoie să fixăm o anumită reprezentare a partiției. Aceste reprezentări depind de scopul clasificării ca și de structura datelor. Structura se poate postula, bazându-se pe anumite informații a priori, sau poate fi determinată prin aplicarea unor metode de analiză preliminară a datelor (analiza componentelor principale, analiza factorială etc.)
Să admitem faptul că fiecare clasă se poate reprezenta printr-un prototip dintr-un spațiu de reprezentare L.
=,,… constituie reprezentarea partiției.
Fie D o măsură de disimilaritate peste X. Admitem că pornim de la D se poate construi o disimilaritate între un obiect din X și un prototip. Acest lucru este întotdeauna posibil când D este o distanță sau pătratul unei distanțe. Vom nota cu Di această măsură de disimilaritate indusă de către D.
Di este așadar o funcție Di: XR
și Di(x, Li)
măsoară gradul în care obiectul x diferă de prototipul Li
Notăm cu
I : P(X) qR
o funcție care măsoară gradul de inadecvare al reprezentării unei clase printr-un prototip. Admitem că măsura I(Ai, Li) a inadecvării clasei Ai prin prototipul Li este dată de
I(Ai, Li) = Di(x,Li) (1)
după care vom considera că inadecvarea reprezentării partiției P prin L este de forma:
J(P, L) = I(Ai, Li) (2)
sau ținând cont de (1):
J(P, L) = (3)
unde J reprezintă funcția criterie.
Problema de clasificare se reduce la determinarea partiției P și a reprezentării L care minimizează această funcție criteriu. Deoarece mulțimea partițiilor cu n clase ale lui X este finită, problema poate fi, teoretic, rezolvată prin considerarea tuturor partițiilor. În realitate acest lucru nu este realizabil decât în situații foarte particulare. Într-adevăr numărul partițiilor cu n clase ce pot fi construite cu p obiecte este
(4)
Acest număr este foarte mare pentru cele mai multe cazuri practice. De exemplu, pentru 5 clase și 100 obiecte avem circa partiții distincte.
Cele mai utilizate metode pentru rezolvarea problemei de minimizare a funcției criteriu sunt metodele iterative. Ideea de bază este de a porni de la o partiție inițială, care poate fi aleasă arbitrar sau determinată printr-un alt algoritm. Obiectele de clasificat sunt transferate dintr-o clasă în alta, dacă o astfel de mutare ameliorează valoarea funcției criteriu. Procedura se oprește când nici o schimbare nu mai îmbunătățește valoarea funcției criteriu. Procedurile iterative de acest tip asigură atingerea unui optim local. Alegeri diferite ale partiției inițiale vor conduce în final după un interval mai mare sau mai mic de timp în general la soluții identice ale problemei de clasificare.
II. Suport de realizare
2.1. Metode de clasificare
Sunt cunoscute două moduri de abordare a procesului de recunoaștere a formelor. Primul mod cunoscut sub numele de recunoaștere controlată (supervizată) presupune existența unui set de forme a căror apartenență la clasă este cunoscută. Acest set este împărțit în două părți: setul de formare utilizat pentru a dezvolta un clasificator (ce utilizează, de exemplu, matricea distanțelor dintre forme) care să recunoască cât mai bine apartenența formelor din set la clasele corespunzătoare și setul de predicție pe care clasificatorul format este evaluat (testat). Clasificatorul astfel dezvoltat este utilizat în continuare pentru stabilirea apartenenței unei forme necunoscute la o clasă.
Cel de-al doilea mod cunoscut sub numele de recunoaștere necontrolată (nesupervizată) nu face apel la o cunoaștere prealabilă a apartenenței formelor la o clasă. Metoda dezvoltă algoritmi care permit în cursul execuției acestora construirea claselor pe măsură ce formele analizate sunt luate în considerare.
Un caz particular al metodelor teoretice decizionale îl constituie tehnicile de învățare. Acestea utilizează un set de forme a căror apartenență la clase este cunoscută. Setul este utilizat în mod iterativ de un algoritm care construiește coeficienții clasificatorului, corespunzător tipului de problemă (fără a utiliza matricea distanțelor dintre forme).
2.1.1. Recunoașterea necontrolată. Tehnici de grupare
Tehnicile de grupare constă dintr-un set de algoritmi care asigură împărțirea spațiului formelor în clase, grupe de forme, fără a face apel la existența prealabilă a unui set de predicție cunoscut. Conceptul de grupare poate fi înțeles cel mai bine prin prezentarea celui mai simplu algoritm de grupare (denumit algoritm de tip prag).
Algoritmul presupune existența în spațiul formelor a unui set de forme și stabilirea inițială a unei distanțe minime (numită distanța de prag) dintre două forme. Dacă distanța dintre două forme este mai mică decât distanța de prag, cele două forme fac parte din aceeași clasă. Notăm cu T distanța prag. Inițial se stabilește aleatoriu un prim centru de grup pe care-l notăm cu Z1(Z1 corespunde cu una din cele N forme). Se calculează distanța dintre acest centru și toate celelalte forme.
Dacă distanțele calculate sunt mai mici decât T, formele respective sunt atribuite clasei 1 , a cărei centru este Z1. Prima formă situată la o distanță mai mare decât T conduce la crearea unei noi grupări (clase) i cu centrul definit de forma respectivă. Se reia calculul distanțelor pentru formele rămase, luând în considerare noua grupare creată.
Procesul de obținere de noi grupări și de atribuire a formelor la aceste grupări continuă până în momentul în care sunt clasificate toate formele. Algoritmul este prezentat în figura 3.1
Fig. 3.1. Algoritm de tip prag
Studiind acest algoritm pot fi determinate o serie de caracteristici ale tehnicilor de grupare.
Alegerea centrelor claselor (grupărilor).
Modul de alegere afectează viteza de clasificare ca și numărul de grupe (clase) care rezultă în urma executării procedurii de clasificare. Din acest motiv se recurge, de obicei, la calculul continuu a unui centru al clasei pe măsură ce la acesta se atribuie noi forme. În acest caz, centrul grupării poate să nu corespundă cu o forma existentă.
Alegerea criteriului de clasificare.
În cazul exemplului dat, criteriul de clasificare este o distanță. Se observă că valoarea lui T afectează rezoluția procesului de clasificare. Dacă T este prea mare, două sau mai multe clase distincte pot fi grupate în una singură. În cazul în care T este prea mic, o grupare poate fi împărțită în mod artificial în câteva grupe. Pentru determinarea valori lui T se ține cont de efectul pe care-l va avea această valoare asupra numărului de grupări. În cazul general se utilizează criteriile de similaritate și nesimilaritate prin care se asigură apartenența unei forme la o clasă. Acestea pot fi distanțe sau alți parametri.
În figura 3.2 se prezintă un algoritm general de grupare care ia în considerare criteriile de grupare specificate anterior.
Fig. 3.2. Algoritm de grupare
2.1.2. Tehnici de învățare
Aceste tehnici dezvoltă algoritmi prin care sunt construiți coeficienții funcției de decizie utilizând o metodă tip ‘feed-back’. Algoritmii operează asupra unui set de forme a căror apartenență la clasă este cunoscută. Determină coeficienții funcției de decizie conform unuia din cele trei criterii de clasificare (specificate anterior), iterativ, până la satisfacerea condițiilor impuse.
Pentru a ilustra cele menționate presupunem un set de N forme împărțit în două clase 1 și 2. Ne propunem să determinăm coeficienții vectorului pondere W. Funcția de decizie dată de relația (1.9), pentru un spațiu n-dimensional, are forma
D(X)=[W1, …,Wn,Wn+1]X, unde X=[x1I,x2I] pentru i=1,…,n.
Pentru formele x1i aparține 1, funcția de decizie este pozitivă și negativă dacă x2I aparține 2 (vezi paragraful 1.2.2.a). Prin urmare criteriul care se urmărește a fi atins este D(X)>0. Algoritmul alege o formă și calculează funcția sa de decizie. Dacă D(X)>0, vectorul pondere este satisfăcător și nu se modifică. Se trece la următoarea formă. Dacă D(X)<0, vectorul de ponderi trebuie să fie modificat astfel încât funcția de decizie să devină pozitivă. Dacă această condiție a fost îndeplinită pentru toate formele din clasa 1 se repetă operația pentru formele din clasa 2 (care au fost înmulțite în prealabil cu –1 pentru ca funcția de decizie să fie pozitivă). Operația presupune:
stabilirea unei valori inițiale pentru vectorul de ponderi;
stabilirea unei modalități de modificare a lui W.
2.1.3. Algoritmi de clasificare nesupervizată (clustering)
Conceptul de clasificare al formelor poate fi înțeles ca o partiționare a spațiului caracteristicilor acestuia. Clasificarea formelor, adică atribuirea fiecărui vector posibil sau punct din spațiul caracteristicilor clasei din care face parte, poate fi interpretată ca o partiționare a acestuia în regiuni (domenii) reciproc exclusive, fiecare domeniu aparținând unei clase de forme particulare. Din punct de vedere matematic acest gen de problemă de clasificare poate fi definită sub forma unei funcții discriminant.
Clasificarea nesupervizată pentru care nu există cunoștințe „a priori” se numește clustering. Este o tehnică care duce la gruparea datelor în clustere astfel încât gradul de asociere și similaritate între membrii aceluiași grup este ridicat și scăzut între membrii grupurilor diferite. Tehnicile de clustering includ: K-means, Isodata, aglomerările ierarhice și altele.
2.1.3.1. Algoritmul n-medii (K-means)
Fie X ={x1, x2…, xp} mulțimea obiectelor de clasificat. Admitem că aceste obiecte reprezintă vectori din spațiul euclidian d-dimensional. Vom considera ca măsură de disimilaritate pătratul distanței induse de norma, adică: D(x ,y)=
Presupunem că mulțimea X este alcătuită din nori (clusteri) de puncte relativ compacți și bine separați, de formă aproximativ sferică. În aceste condiții un nor se poate reprezenta printr-un punct, care constituie prototipul clasei respective. Așadar prototipul Li al clasei Ai este un punct din Rd.
Disimilaritatea dintre un punct x din X și prototipul Li se poate interpreta ca fiind eroarea comisă atunci când punctul x se aproximează prin prototipul clasei Ai. Această disimilaritate se poate scrie: D(x ,Li)=
Funcția criteriu considerată va fi:
J(P, L) =
de unde J(P, L) =
Pentru a determina minimul funcției criteriu, aceasta se va exprima într-o formă ușor modificată. Fie IAi funcția caracteristică a mulțimii Ai. Folosind notația:
Aij = IAi(xj) =
Să presupunem de exemplu că avem un număr de 6 obiecte și că partiționarea acestora inițială este 3. Atunci Aij se va putea construi astfel:
Fig. 3.3 – Obiecte de partiționat
Partiția
În aceste condiții funcția criteriu este:
Ținând cont de faptul că într-un spațiu euclidian produsul scalar a doi vectori este
funcția criteriu apare sub forma
Pentru ca să fie un minim pentru funcția este necesar să avem:
de unde rezultă că:
respectiv:
de unde obținem:
Se observă că numitorul reprezintă numărul de elemente din clasa . Notând cu
numărul de elemente din clasa Ai
expresia prototipului Li se va mai scrie
Observăm că prototipul L i este media sau centrul de greutate al clasei A i.
Reprezentarea L i= L 1, L 2, . . . , L n induce o nouă partiție. Această partiție se obține folosind regula celui mai apropiat vecin. Un obiect (punct) xj este atașat clasei de centrul căreia este cel mai apropiat. Avem deci următoarea regulă de decizie
Din punctul de vedere al programării algoritmului, este mai util ca regula de mai sus să se exprime sub forma
Algoritmul n-medii constă în aplicarea iterativă a formulelor anterioare, plecând de la o partiție inițială a lui X. Această partiție inițială se poate alege arbitrar, se poate stabili folosind anumite informații asupra datelor sau poate constitui rezultatul aplicării unui alt algoritm de clasificare.
Algoritmul n-medii constă efectiv în executarea următorilor pași:
P1. Se alege o partiție inițială p0=A1, A2, . . . , An a lui X.
P2. Se calculează prototipurile acestei partiții cu formula :
P3. Se calculează noua partiție după regula
x A i dacă
P4. Dacă noua partiție coincide cu precedenta, atunci STOP. În caz contrar se merge la P2.
Observații:
În loc de a alege o partiție inițială putem porni de la o alegere arbitrară a n centrii, care pot fi n puncte din mulțimea X a datelor.
Rezultatele algoritmului n-medii depind de numărul de clase considerate, de alegerea inițială a partiției sau a centrilor și de proprietățile geometrice ale datelor. Când datele conțin grupări caracteristice, relativ îndepărtate unele de altele, deci sunt constituite din clusteri compacți și bine separați, rezultatele algoritmului sunt bune. Determinarea numărului optim de clusteri prezenți în mulțimea datelor constituie așa numita problemă a validității clusterilor. Această problemă nu poate fi rezolvată în cadrul acestui algoritm. Dacă avem unele informații despre date, putem ca prin experimentări succesive să determinăm valoarea care dă cea mai bună concordanță cu datele inițiale.
O altă problemă dificilă apare când datele conțin clase ce prezintă diferențe mari ale numărului de puncte. Să considerăm cazul când datele constau din doi clusteri inegali ca populație și extindere. Este posibil ca unele puncte aflate la periferia clusterului mare să fie mai apropiate de centrul clusterului mic. Funcția criteriu considerată va favoriza o partiție ce despică clusterul mare, față de una ce menține integritatea acestuia. Dacă se consideră n=2, atunci clusterul mai mic va capta unele din punctele periferice ale clusterului mare. Acest efect "pseudo-gravitațional" reprezintă o perturbație pentru procesul de clasificare. Este o dificultate majoră care se poate rezolva făcând ca distanța de la un obiect la prototipul unei clase să depindă de dimensiunea clasei respective. Considerarea unei astfel de distanțe adaptive presupune în general ca algoritmul să fie aplicat de două ori.
Alte dificultăți sunt legate de existența punctelor izolate (considerate zgomote) și a podurilor între clustere. De altfel aceste dificultăți apar și în alte tehnici de clasificare.
Algoritmul Isodata previne această problemă prin eliminarea clusterelor redundante. Oridecâteori un cluster nu are suficienți membri acesta poate fi eliminat. Astfel se încearcă obținerea unui număr optim de clustere. Problema alegerii numărului de clustere inițiale rămâne, dar considerarea unui k suficient de mare rezolvă în general problema.
2.1.3.2. Exemplu de clusterizare folosind K-Means
Fig. 3.4
2.1.3.3. Algoritmul Isodata
Algoritmul ISODATA (Iterativ Self-Organizing Data Analyst Techniques) este în esență similar cu algoritmul n-medii. Această asemănare a făcut ca algoritmul n-medii să fie deseori prezentat sub numele de ISODATA. Asemănarea constă în modul iterativ de calcul a centrilor. Deosebirea este dată de natura euristică a algoritmului ISODATA care permite ca numărul de clustere să fie ajustat în mod automat în cadrul iterațiilor prin unirea claselor similare și împărțirea claselor cu deviație standard mare. Algoritmul reprezintă un bun exemplu relativ la avantajele și inconvenientele unor astfel de metode care necesită definirea unor parametrii ce trebuie ajustați prin încercări succesive.
Mai întâi este necesar să se specifice k centri de clase. Acești centri, al căror număr nu este neapărat egal cu numărul claselor dorite, pot fi aleși dintre punctele de clasificat. Fie m1,…,mk alegerea inițială arbitrară a acestor centri.
Algoritmul ISODATA constă în parcurgerea următorilor pași:
P1. Se specifică valorile următorilor parametri:
n = numărul de clase dorite;
p = numărul minim de elemente dintr-o clasă;
s = parametrul de dispersie standard;
c = distanța maximă pentru fuzionare;
L = numărul maxim de perechi de centre ce pot fuziona la un moment dat;
I = numărul maxim de iterații permise.
P2. Se distribuie cele p perechi din X în clasele determinate de centri, după regula:
P3. Se suprimă clasele având mai puțin de elemente și se repartizează obiectele în celelalte clase. Se micșorează k.
P4. Se recalculează centrii claselor după formula
P5. Se calculează diametrul mediu al fiecărei clase
P6. Se calculează distanța medie la care se află obiectele față de centrii claselor
P7. 1) Dacă aceasta este ultima iterație atunci se pune și se merge la P11
2) Dacă se merge la P8
3) Dacă numărul iterației este par sau dacă se merge la P11
P8. Se calculează dispersia clasei
Componenta a lui reprezintă dispersia datelor în direcția j.
P9. Pentru fiecare clasă se determină componenta maximă a dispersiei
P10. Se consideră succesiv toate clasele. Dacă există o clasă astfel încât
și
sau
atunci se despică clasa Ai în două clase și se calculează centrii acestora
și
se șterge și se pune . Centrul se obține adăugând la componenta (care corespunde componentei maxime ale lui ) o cantitate (unde ). Centrul se obține scăzând această cantitate din . Parametrul trebuie astfel ales încât diferența distanțelor de la orice punct arbitrar la noii centri să fie sesizabilă ( mai mare decât un convenabil ales), dar să nu schimbe în mod apreciabil întreaga configurație a claselor.
Dacă s-a produs despicarea vreunei clase la acest pas se merge la P2. În caz contrar se va continua.
P11. Se calculează toate distanțele între centrii claselor
P12. Se compară distanțele dij cu parametrul . Se aranjează primele L distanțe mai mici decât în ordine crescătoare.
P13. Pornind de la perechea de clase având distanța centrilor cea mai mică se modifică centrii după următoarea regulă: Dacă atât pentru cât și pentru centrul nu a fost modificat, se înlocuiesc centrii prin centrul
.
Se șterg și se pune . Dacă fie fie au centrul modificat atunci perechea (i, j) nu e luată în considerare și se trece la următoarea pereche.
P14. Dacă aceasta este ultima iterație sau dacă poziția și numărul centrilor coincid cu cele de la iterația precedentă STOP. In caz contrar se merge la P2 ( sau P1 dacă se modifică datele inițiale).
2.1.3.4. K-Means și Isodata
K-means și Isodata sunt cei mai folosiți algoritmi în procesul de clasificare nesupervizată. Ambii algoritmi sunt proceduri iterative și în general în ambii algoritmi se aleg clusterele inițiale în mod arbitrar. Al doilea pas clasifică fiecare pixel la cel mai apropiat cluster. În al treilea pas se calculează noul centroid efectuând media între pixelii din acel cluster.
Al doilea și al treilea pas sunt repetați până când „diferența” dintre iterații este mică. Această „diferență” poate fi definită în mai multe moduri: de exemplu prin măsurarea procentajului de pixeli care s-au schimbat între iterații sau prin măsurarea distanțelor cu care s-au modificat centroizii de la o iterație la alta.
Algoritmul Isodata este ceva mai rafinat deoarece permite împărțirea și reunirea de clustere. Clusterele sunt unificate dacă numărul de membri (pixeli) dintr-un cluster e mai mic decât un anumit prag sau dacă centrii a două clase sunt mai apropiați decât un anumit prag. Clusterele sunt împărțite în două clustere diferite dacă deviația standard depășește o valoare predefinită și numărul de pixeli este de două ori valoarea pragului pentru numărul minim de membri.
Algoritmul Isodata este similar cu K-means cu deosebirea că Isodata permite un număr variabil de clustere în timp ce K-means presupune ca numărul de clustere să fie cunoscut a priori.
Obiectivul algoritmului K-means este de a minimiza o funcție și anume suma pătratelor distanțelor (Squared Sum) dintre fiecare pixel și centrul clusterului căruia îi aparține (de fapt acestea sunt erorile):
unde C(x) este media clusterului căruia îi aparține pixelul x.
Minimizarea SSdistances echivalează cu minimizarea Erorii Medii Pătrate (Mean Squared Error -MSE):
unde N este numărul de pixeli, c indică numărul de clustere, și b este numărul de benzi spectrale.
De remarcat că MSE nu este funcția obiectiv a algoritmului Isodata; totuși Isodata tinde să minimizeze această funcție.
K-means (la fel ca Isodata) este sensibil la valorile inițiale alese. Pentru două clasificări cu valori inițiale diferite și clasificări rezultate diferite se poate opta pentru cea cu cel mai mic MSE. Totuși, în cazul a două valori inițiale diferite MSE diferă în general foarte puțin pe când clasificările obținute sunt foarte diferite. Deseori nu este vizibil faptul că cea mai bună clasificare este cea pentru care MSE este mai mic.
Un dezavantaj general al celor două metode îl reprezintă faptul că acestea lucrează mai bine pentru imagini ale căror grupări sunt sferice și au aceeași varianță. Dar acest lucru nu este de obicei valabil pentru imaginile din teledetecție. De exemplu, o grupare gen „pădure” este în general mai ovală față de o grupare de tip „deșert”. În timp ce un cluster „deșert” este bine detectat de algoritmul K-means ca un cluster distinct, clusterul „pădure” este de obicei împărțit în câteva clustere mai mici. Modul în care se fac împărțirile variază destul de mult în funcție de valorile inițiale și de aceea poate fi considerat arbitrar.
2.1.3.5. Problema grupării punctelor dintr-un spațiu multidimensional
Clasificarea nesupervizată reprezintă o tehnică esențială în procesarea imaginilor pentru geoștiință și aplicații de teledetecție. De exemplu, clasificarea nesupervizată este des folosită pentru a obține hărți de vegetație ale unor regiuni de interes. Această abordare este utilă când nu se cunosc inițial prea multe informații despre date sau când tehnica implicată ar fi scumpă.
Problema clasificării punctelor dintr-un spațiu multidimensional poate fi privită ca o problemă de optimizare precum:
problema minimizarea sumei distanțelor la cel mai apropriat centru (problema k-mediană)
minimizarea distanței maxime (problema k-centri)
minimizarea sumei pătratelor distanțelor (problema k-medii).
Soluții eficiente se cunosc doar în câteva cazuri particulare. Pentru un k general nu se cunosc soluții eficiente pentru nici una dintre problemele de mai sus, unele formulări conducând la probleme NP-complete. Pentru unele cazuri au fost dezvoltați algoritmi aproximativi eficienți
2.2. Segmentarea imaginilor
2.2.1. Generalități
Segmentarea imaginilor se referă la descompunerea unei scene (imagini) în componentele sale. În urma procesului de segmentare vor fi extrase din imagine obiecte distincte, regiuni ce satisfac anumite criterii de uniformitate, sau alte elemente.
Segmentarea unei imagini f se definește matematic ca partiționarea [completă] a lui f (1) într-un ansamblu de mulțimi disjuncte nevide și conexe (2), ce satisfac fiecare un anumit criteriu C (3), criteriu ce nu mai este respectat pentru reuniunea oricăror două elemente ale partiției:
conexe (1)
șieste conexă, (2)
și (3)
Fig. 3.6 –
Procesul de segmentare
Alegerea unei tehnici specifice de segmentare (partiționare a imaginii) este legată de mai multe aspecte caracteristice imaginii de analizat și cerințelor utilizatorului. După natura și conținutul imaginii, tehnicile de segmentare trebuie să țină cont de prezența în imagine a diverse categorii de artefacte:
reflexii, iluminare neomogenă;
zgomot suprapus informației utile;
zone texturate.
După primitivele de extras, tehnicile de segmentare se împart în două categorii fundamentale:
tehnicile de segmentare orientate pe regiuni și
tehnicile de segmentare orientate pe contur.
Primitivele extrase din imagine sunt regiuni (forme) și zone texturate pentru tehnicile orientate pe regiuni, sau entități de tip discontinuitate (frontiere, segmente de dreaptă, unghiuri) pentru tehnicile orientate pe contur.
În cadrul segmentării orientate pe regiuni se disting câteva categorii principale de tehnici:
etichetarea imaginilor binare
segmentarea pe histogramă
creșterea și fuziunea regiunilor
segmentarea texturilor
segmentarea prin metode de clustering.
Tehnicile principale de segmentare orientată pe contururi sunt:
extragerea contururilor prin metode de gradient și derivative
extragerea contururilor prin metode neliniare
extragerea contururilor prin metode liniare optimale
extragerea contururilor prin modelare matematică.
Cele mai semnificative dintre aceste tehnici vor fi prezentate în continuare.
Fig. 3.7 – b
Exemplu de segmentare orientată pe contururi
2.2.2. Histograma unei imagini
În general, operația de segmentare orientată pe regiuni urmărește extragerea din imagine a zonelor (regiunilor) ocupate de diferitele obiecte prezente în scenă. Un obiect se definește ca o entitate caracterizată de un set de parametri ale căror valori nu se modifică în diferitele puncte ce aparțin entității considerate. Mai simplu, putem spune că obiectul are proprietatea de uniformitate a parametrilor de definiție.
Unul dintre cei mai simpli parametri de definiție este nivelul de gri al punctului. Nivelul de gri corespunde în scenă unei proprietăți fizice (reflectantă, transmitivitate, valoare tristimulus, etc.) ce este preluat de senzorul de imagine și asociat luminanței imaginii. În acest caz, histograma imaginii (funcția de densitate de probabilitate a variabilei aleatoare discrete ale cărei realizări sunt nivelele de gri din imagine) reflectă distribuția în scenă a proprietății fizice înregistrate.
Pentru o imagine f de pixeli și L nivele de gri, histograma este definită (4) ca probabilitatea de apariție în imagine a diferitelor nivele de gri posibile.
(4)
Dacă nivelul de gri (respectiv proprietatea fizică pe care acesta o reprezintă) caracterizează în mod suficient obiectele din scenă, histograma imaginii va prezenta o structură de moduri dominante – intervale de nivele de gri ce apar cu probabilitate mai mare. Fiecare asemenea mod (maxim al histogramei) va reprezenta o anumită categorie de obiecte.
Ca exemplu imediat se poate cita cazul imaginilor obținute prin scanarea documentelor scrise și a tipăriturilor sau imaginile în infraroșu (temperatura punctelor este asociată nivelelor de gri astfel încât mai fierbinte însemnă mai alb). Pentru toate aceste tipuri de imagini histograma este de tipul celei prezentate în figura 3.5.
Fie. 3.8: Histogramă bimodală
Fiind o funcție de densitate de probabilitate, histograma oricărei imagini verifică condiția de normare:
Histograma cumulativă este funcția de repartiție a variabilei aleatoare ce reprezintă nivelul de gri al imaginii, și deci este probabilitatea ca un pixel din imagine să aibă nivelul de gri mai mic sau egal ca un prag fixat:
(5)
Orice imagine este o structură bidimensională de date, deci o matrice. Imaginile sunt stocate în fișiere; adeseori fișierele ce conțin imagini au o organizare (structură) specială, descrisă de așa numitele formate grafice. Fișierele grafice (ce conțin imagini) sunt identificate prin extensiile speciale pe care le au numele acestora.
În Matlab citirea unei imagini stocate în asemenea fișiere se face cu ajutorul funcțiilor imread. Modul de folosire a acestei funcții este:
>>x=imread(’nume_ fișier_ imagine’);
Rezultatul execuției comenzii este acela că se creează (în memoria calculatorului sau în așa numitul spațiu de lucru Matlab) matricea x, ce corespunde imaginii stocate în fișierul cu numele ’nume_fișier_imagine’ (apostrofurile precizează faptul că acesta este un șir de caractere).
Imaginile cu care se lucrează în mod curent sunt imagini cu nivele de gri, reprezentate pe 256 de nivele de cuantizare (deci L = 256). Valoarea fiecărui pixel al imaginii (nivelul de gri al fiecărui pixel) este măsura luminanței punctului respectiv; O corespunde negrului și 255 corespunde albului. Din acest punct de vedere, imaginile sunt imagini de intensitate (valoarea fiecărui punct este proporțională cu intensitatea luminoasă din punctul considerat). În același timp însă, valorile întregi ale punctelor se folosesc la afișarea imaginii pentru a recupera culoarea corespunzătoare dintr-un tabel de culoare (tabel de culoare ce conține cele 256 de nivele de gri folosite), și deci există și o a doua interpretare a imaginilor ca imagini indexate. Afișarea unei imagini cu L nivele de gri, reprezentată de matricea x în fereastra curentă, se face cu comanda Matlab:
>>image(x),colormap(gray(L))
Observație: Evident, în comanda de mai sus, L trebuie înlocuit cu valoarea lui numerică particulară, ca de exemplu 256. De asemenea, trebuie avut în vedere că Matlab nu poate reprezenta imagini cu mai mult de 256 de culori (nivele de gri) diferite.
Pentru calcularea histogramei (4) și a histogramei cumulative (5) a unei imagini x cu nivele de gri se folosește funcția hist:
Dacă nu este necesară și histograma cumulativă, funcția se poate apela doar prin:
>>
Codul Matlab al acestei funcții se regăsește în fișierul hist.m; calculul efectiv este realizat de:
Vizualizarea histogramei în figura curentă se face prin trasarea graficului definit de vectorul h:
>>plot(h)
Dacă nivelul de gri (respectiv proprietatea fizică pe care acesta o reprezintă) caracterizează în mod suficient obiectele din scenă, histograma imaginii va prezenta o structură de moduri dominante – intervale de nivele de gri ce apar cu probabilitate mai mare. Fiecare asemenea mod (maxim al histogramei) va reprezenta o anumită categorie de obiecte.
2.2.3 Histograma ponderată a unei imagini
Construirea histogramei ponderate are ca scop accentuarea minimelor locale, pentru o alegere mai ușoară a pragurilor de segmentare (separație inter-mod). Histograma ponderată este construită prin definirea unei funcții de ponderare w, care transformă o anumită proprietate locală p(m, n), conform relației (6):
(6)
În această histogramă ponderată contribuția pixelilor nu mai este unitară, ci dependentă de proprietățile vecinătății acestora, măsurate prin p(m,n). Proprietatea locală cea mai des utilizată este aceea de neuniformitate (de variație a nivelelor de gri în vecinătatea fiecărui pixel), măsurată prin laplacianul local l(m,n). Pixelii care se află în zonele de tranziție (frontierele obiectelor din imagine) au o vecinătate neuniformă, și deci un laplacian mare în valoare absolută, iar pixelii care se află în interiorul unor regiuni uniforme (interiorul obiectelor) au o vecinătate mai uniformă și deci un laplacian mai apropiat de valoarea nulă. Pentru a accentua pe histogramă zonele de separație inter-mod este necesar ca pixelii ce se află în interiorul unor regiuni uniforme (obiecte) să aibă o contribuție mai importantă decât contribuția pixelilor aflați în zonele de frontieră. În aceste condiții, funcția de ponderare trebuie să fie invers proporțională cu laplacianul local; forma generală a funcției de ponderare este dată de relația (7):
(7)
Exponentul k reprezintă un factor suplimentar de reglaj, permițând obținerea de diferite grade de reliefare a minimelor histogramei (cu cât k este mai mare, cu atât minimele sunt mai bine puse în evidență).
Există un mod de segmentare alternativă, folosind maximele unei histograme ponderate. In acest caz este necesar ca funcția de ponderare w() să transforme minimele histogramei normale în maxime ale histogramei ponderate. Dacă se folosește în continuare laplacianul ca proprietate locală și o funcție de ponderare proporțională cu acesta, de exemplu (8), histograma ponderată va lua în calcul doar pixelii din imagine a căror vecinătate prezintă variații puternice ale nivelelor de gri, în timp ce pixelii aflați în interiorul unor regiuni omogene nu vor avea nici o contribuție. Histograma ponderată astfel construită va prezenta maxime pe nivelele de gri ce corespund zonelor de tranziție între modurile histogramei normale.
w(p(m,n)) =|l(m, n)| (8)
Codul corespunzător prelucrării de bază este:
2.2.4. Segmentarea pe histogramă
Dacă histograma are doar două moduri dominante separarea acestora (deci identificarea obiectelor din imagine) se face prin alegerea unui nivel de gri T3 numit prag de segmentare. Acest prag de segmentare se alege pe minimul global al histogramei Din imaginea inițială f de nivele de gri se construiește o imagine de etichete (imagine etichetată) g, conform transformăm descrise de (9) (vezi Figura 3.6 a)).
(9)
Imaginea etichetată va fi descrisă de două etichete: pentru punctele al căror nivel de gri este mai mic decât pragul T și pentru punctele al căror nivel de gri este mai mare decât pragul T Etichetele și pot fi valori numerice (0 și l, sau 0 și 255) sau pot fi șiruri de simboluri sau alți identificatori
Fig. 3.9 Transformări punctuale de binarizare
Transformarea (9) este o transformare punctuală (noua valoare din punctul (m,n) depinde doar de valoarea anterioară din punctul (m,n)) și poartă numele de binarizare. Această denumire provine din faptul că rezultatul transformării (imaginea etichetată) este o imagine binară – deci o imagine caracterizată doar de două valori.
Există însă și o variantă de binarizare cu două praguri (transformare punctuală numită decupare – „slicing”), definită de ecuația următoare (10) (vezi Figura 3.6 b)):
(10)
În cazul general al existenței a mai multe praguri de segmentare , transformarea de segmentare pe histogramă este descrisă de (11)
dacă (11)
Pragurile Tk se aleg prin inspecția histogramei, în minimele locale ale acesteia. Acest tip de segmentare multinivel este mai puțin eficient decât binarizarea, din cauza dificultății de stabilire a pragurilor care să izoleze eficient intervalele de interes din histogramă, mai ales atunci când numărul modurilor este mare. Trebuie de asemenea remarcat faptul că este necesară cunoașterea numărului de tipuri de obiecte din imagine, pentru alegerea corespunzătoare a numărului de praguri de segmentare.
Pentru segmentarea unei imagini este disponibilă funcția wthresh (de la termenul "thresholding"); folosirea cea mai simplă este:
>>y=wthresh(x, prag);
Comanda anterioară segmentează prin thresholding imaginea x după pragurile indicate de vectorul prag; imaginea de etichete este y. Pragurile sunt, evident, valorile nivelelor de gri ce corespund minimelor histogramei.
Observație: Etichetele alocate sunt numerice, încep cu valoarea 1 și sunt incrementate unitar. Vizualizarea unei imagini de etichete se poate face cu:
>>image(y), colormap(hsv(max (y (:))))
Nucleul funcției de segmentare este realizat de:
2.2.5. Segmentarea pe histograma cumulativă
Histograma cumulativă este funcția de repartiție a variabilei aleatoare ce reprezintă nivelul de gri al imaginii, și deci este probabilitatea ca un pixel din imagine să aibă nivelul de gri mai mic ca un prag fixat.
Exemplul clasic de folosire a tehnicii de segmentare cu folosirea histogramei cumulative este acela de binarizare a unei imagini ce conține obiecte de interes și fundal. In general se consideră că obiectele de interes sunt caracterizate de un nivel de gri mai mic ca al fundalului, și că obiectele ocupă un procent P din suprafața (numărul de pixeli) imaginii. In aceste condiții, pragul de segmentare T se va alege astfel încât: .
Fig. 3.10 – a
Exemplu de segmentare pe histogramă
Fig. 3.10 – b
Exemplu de segmentare pe histogramă
2.2.6. Creșterea și fuziunea regiunilor
2.2.6.1. Creșterea regiunilor
Pentru aplicarea cu succes a tehnicilor de segmentare pe histogramă prezentate anterior trebuiesc îndeplinite neapărat câteva condiții (deja enunțate). Aplicarea tehnicilor de segmentare pe histogramă este condiționată în primul rând de reprezentarea diferitelor clase de obiecte din imagine pe intervale de nivele de gri diferite care nu se suprapun (sau se suprapun parțial pe porțiuni foarte mici); apoi este necesară cunoașterea numărului de tipuri de obiecte diferite. În fine, se presupune că valorile prag corespunzătoare se pot determina cu o precizie corespunzătoare.
Chiar în cazurile în care toate aceste condiții enunțate sunt îndeplinite, nu se poate garanta condiția de conexitate a regiunilor obținute în urma segmentării. Acest lucru este evident, atât timp cât două obiecte de același tip, neconexe, primesc prin segmentarea pe histogramă o aceeași etichetă, și formează în imaginea de etichete o regiune neconexă. Creșterea regiunilor respectă toate condițiile impuse de definiția matematică a segmentării.
Principiul pe care se bazează creșterea regiunilor este simplu: se aleg în imagine puncte reprezentative pentru fiecare obiect individual și categorie de obiecte, pe baza cărora are loc un proces de aglomerare a pixelilor vecini acestora, ce au aceleași proprietăți (în particular același nivel de gri). In urma acestui proces de aglomerare (adăugare de puncte) se obțin zone (regiuni) de pixeli cu aceleași caracteristici, deci obiecte individuale. Procesul se oprește în momentul în care fiecare punct al imaginii a fost alocat unei regiuni. Evident, metoda astfel descrisă pe scurt, are două etape esențiale: alegerea punctelor de start (puncte inițiale), numite germeni sau semințe, și creșterea propriu-zisă a regiunilor.
Numărul final de regiuni rezultate este egal cu numărul de germeni aleși inițial pentru creștere. In principiu, este de dorit ca fiecare obiect individual aflat în imagine să fie marcat de câte un germene. Dacă în interiorul aceluiași obiect se găsesc mai mulți germeni, pentru fiecare dintre ei va fi crescută o regiune; aceasta face ca obiectul inițial să fie împărțit artificial prin segmentare în mai multe regiuni. Parțial, acest neajuns se poate corecta printr-o etapă ce urmează creșterii regiunilor, și anume fuziunea regiunilor adiacente ce au proprietăți asemănătoare. Dacă în interiorul unui obiect nu este ales nici un germene, obiectul respectiv va fi înglobat de regiunile ce cresc pornind de la germeni din vecinătatea sa spațială; astfel, respectivul obiect nu apare ca o regiune distinctă și este pierdut, rezultând o eroare gravă de segmentare.
Pentru a preveni efectul unor neuniformități de iluminare pe suprafața imaginii, aceasta este împărțită în ferestre nesuprapuse; în fiecare astfel de fereastră se alege un număr de germeni, al căror plasament spațial este aleator (germenii se distribuie uniform pe suprafața imaginii). Germenii se aleg astfel încât nivelul lor de gri să fie reprezentativ pentru obiectele prezente local (deci nivelul de gri al germenilor trebuie să corespundă unor maxime ale histogramei locale). În plus, trebuie verificat ca plasamentul spațial al germenilor să se facă în interiorul regiunilor și nu pe frontiera acestora. Verificarea se poate face simplu pe baza calculului unui operator derivativ local, ca de exemplu laplacianul; dacă valoarea acestuia nu depășește un anumit procent prestabilit (10% – 20%) din diferența maximă de nivele de gri a ferestrei, punctul ales este considerat ca plasat corect.
O verificare suplimentară încearcă să prevină o eventuală suprasegmentare2 (împărțirea artificială a unui același obiect în mai multe regiuni), eliminând germenii plasați în interiorul aceluiași obiect. Verificarea se face pe baza calculului variației nivelelor de gri de-a lungul drumurilor3 arbitrare ce unesc perechi de germeni. Dacă există o cale ce unește doi germeni de-a lungul căreia nivelul de gri nu variază cu mai mult de 20% – 30% din diferența maximă a nivelelor de gri din fereastră, cei doi germeni sunt plasați în interiorul unei zone de nivele de gri uniforme, deci în interiorul unui același obiect. În aceste condiții unul dintre cei doi germeni ai perechii este eliminat, deoarece este redundant.
Dacă de-a lungul tuturor căilor ce unesc perechea de germeni nivelul de gri variază mai mult decât pragul ales, atunci se consideră că cei doi germeni sunt plasați în interiorul unor obiecte diferite (deoarece căile ce unesc germenii traversează regiuni de frontieră). În practică, examinarea tuturor drumurilor (căilor) ce unesc perechi de germeni este extrem de costisitoare din punctul de vedere al timpului de calcul. De aceea se verifică doar căile formate din segmente verticale și orizontale, și eventual, dreapta ce unește cele două puncte (dacă această dreaptă poate fi reprezentată de o secvență de puncte conexe) (vezi figura 3.7).
Valorile procentuale ale pragurilor de comparație, precum și numărul de germeni distincți ce rămân după procesul de reducere, nu trebuie considerate ca fixe; nu există valori standardizate și alegerea acestora se face pe baza condițiilor particulare (legate de conținutul imaginii) și a experienței utilizatorului.
Pornind de la germenii aleși, regiunile sunt obținute printr-un proces de creștere aproape simultană, început de la aceștia, până când toți pixelii imaginii sunt repartizați unei regiuni. Cvasi-simultaneitatea creșterii poate fi realizată cu un algoritm serial, prin alocarea pixelilor ce sunt adiacenți (vecini) zonelor deja segmentate. Această alocare trebuie să țină seama de criteriul ca regiunile crescute să fie uniforme: nivelul de gri al pixelului ce se adaugă nu trebuie să difere cu mai mult de un prag prestabilit față de nivelul de gri al germenului regiunii la care se alocă. În același timp, la o singură trecere, numărul de puncte ce se adaugă unei regiuni nu poate depăși un număr prestabilit (condiția încearcă să asigure creșterea relativ uniformă și izotropă a tuturor regiunilor).
Fig. 3.11: Reducerea numărului de germeni: germenii l și 2 sunt uniți de o cale cu segmente paralele cu orizontala și verticala de intensitate constantă, deci sunt redundanți; germenii 3 și 4 sunt uniți de o cale dreaptă de aceeași intensitate, deci sunt redundanți; orice cale ce unește germenii l și 3 are o diferență mare de intensitate.
Dacă adăugarea de noi pixeli se blochează (criteriul de uniformitate nu mai este respectat), diferența maxim admisă pentru nivelul de gri poate fi crescută în etape, până la epuizarea pixelilor imaginii.
Avantajele pe care le are o asemenea tehnică de creștere a regiunilor sunt acelea că nu mai este necesară nici o informație privind conținutul imaginii, regiunile crescute sunt conexe și nu există puncte neetichetate (nealocate vreunei regiuni) și poziția frontierelor dintre diferitele regiuni corespunde poziției frontierelor percepute subiectiv în imagine.
2.2.6.2. Fuziunea regiunilor
O extindere a principiului utilizat în creșterea regiunilor, și anume adăugarea la o regiune a unor entități (pixeli în acest caz) a căror proprietăți sunt similare cu cele ale obiectului de bază (regiunea), se află la baza tehnicilor de fuziune a regiunilor. Fuziunea regiunilor constă în reunirea iterativă a regiunilor adiacente (începând de la nivelul unor entități atomice ale imaginii – deci pixelii) până când regiunile adiacente devin suficient de diferite. Procesul de fuziune a regiunilor poate fi aplicat și în urma unei creșteri a regiunilor, pentru a înlătura efectele unei eventuale suprasegmentări. Există mai multe criterii de fuziune a regiunilor adiacente, a căror acțiune de verificare a deosebirii între regiuni se face fie prin inspecția frontierei comune, fie prin caracterizarea interiorului regiunii.
Pentru două regiuni adiacente și , al căror perimetru este Perim() și Perim(), putem determina Pm = min (Perim(), Perim()) și P lungimea frontierei comune4.
Pe această frontieră comună se disting puncte slabe (în număr de ) și puncte tari (în număr de ). Un punct slab este acel punct pentru care diferența nivelelor de gri între vecinii din regiunile adiacente este foarte mică (mai mică decât un anumit prag fixat). Un punct tare este acel punct pentru care diferența de nivele de gri între vecinii din regiunile adiacente este foarte mare (mai mare ca un anumit prag fixat). Cu aceste notații, criteriile de fuziune a regiunilor și sunt:
dacă numărul de puncte slabe raportat la perimetrul minim este important,
dacă numărul de puncte slabe de pe frontiera comună este mare,
dacă numărul de puncte tari de pe frontiera comună este mic, .
Parametrul controlează dimensiunea regiunilor ce se unesc și se alege în general cu valoarea 0.5 (de exemplu o valoare apropiată de l implică unirea a două regiuni numai dacă una dintre ele este aproape înconjurată de cealaltă). Valori tipice pentru parametrii și sunt 0.75 și 0.2.
Abordarea fuziunii pe baza caracterizării interiorului regiunilor necesită definirea a două componente: o modalitate de caracterizare a proprietăților regiunilor și o modalitate de a defini "apropierea" sau similaritatea dintre trăsături în termeni numerici.
Vectorul de trăsături ce caracterizează o regiune se compune din momente statistice ale variabilei aleatoare ale cărei realizări particulare sunt nivelele de gri din regiunea respectivă; nu pot lipsi din acest vector nivelul de gri mediu al regiunii și varianta acestuia.
Se pot propune patru funcții de măsură a asemănării între perechi de vectori; pentru doi vectori și , având aceeași dimensiune, acestea se definesc ca:
(produsul scalar dintre vectori)
(similaritatea dintre vectori)
(corelația normalizată dintre vectori)
(distanța generalizată dintre vectori, unde A este o matrice pozitiv definită)
Pentru primele trei funcții, o valoare mai mare corespunde unei asemănări mai mari între vectori (valorile maxime pentru și sunt 1). Pentru funcția de similaritate bazată pe distanța generalizată, o valoare mai mică corespunde unei asemănări mai puternice între vectori. Prin particularizarea matricii A se pot obține diferite distanțe, ca distanța Euclidiană obișnuită ( fiind matricea unitate, ), distanțe Euclidiene ponderate (dacă A este o matrice diagonală), sau distanța Mahalanobis (dacă este o matrice de covariație a componentelor).
Exemplu în Matlab
Creșterea regiunilor dintr-o imagine poate fi realizat cu ajutorul funcției grow_reg din Matlab. Rezultatele procesului de creștere a regiunilor folosind diferiți parametri de reglaj (toleranța la modificarea nivelelor de gri, dimensiune maximă a regiunii) și diferiți germeni pot fi vizualizate prin următorul exemplu:
>>x=imgread('lena128', 128);
>>[poziții, valori]=grow_reg(x, 100, 100, 20, 100);
>>rez=find(h==0);
>>map=gray(256); map(rez(l), 1)=1; map(rez(l), 2)=0; map(rez(l), 3)=0;
>>y=x; [t,tt]=size(poziții); y(pozitii)=rez(l)*ones(t);
>>figure, image(y), colormap(map), colorbar
2.2.7. Aplicarea combinată a operațiilor fuzzy în segmentarea imaginilor color
Operațiile cu mulțimi fuzzy pot fi aplicate pentru segmentarea unei imagini color după culoare (nuanță), punând în evidență de exemplu doar obiectele de culoare roșie (nuanță roșie) prin nivele de luminozitate mare (apropiată de alb) față de obiectele de altă nuanță, care vor apărea reprezentate ca "non-obiecte" (negru).
Pentru aceasta, avem nevoie de reprezentarea unei imagini color într-un spațiu de culoare care să conțină atributul de nuanță.
Reprezentarea primară a imaginilor color se realizează în spațiul (R,G,B) (spațiu numit al componentelor primare de culoare: roșu, verde și albastru, prin a căror combinare aditivă ponderată putem obține orice culoare din spectru). Spațiile culorilor mai apropiate însă de modul de percepere uman al culorii sunt spațiile HSV și HSL, în care culoarea se reprezintă prin atributele perceptuale de nuanță (hue, H), saturație (S) și luminozitate (L sau V-value).
Reprezentarea culorilor în ambele spații poate fi "văzută" simplu folosind de ex. programul Paint, unde opțiunea Edit Colors din meniul Colors, urmată de click pe Define Custom Colors și selecția unei culori din paleta care apare, ne prezintă pentru orice culoare selectată atât valorile componentelor sale R,G și B, cât și valorile H, S și L (cele din urmă fiind scalate în domeniul [0;240], deși pot fi reprezentate, la fel ca și atributele R, G, B și nivelele de gri, pe 8 biți, în domeniul [0;255].
În Matlab, la deschiderea unei imagini color, reprezentarea sa implicită este în spațiul (R,G,B). Există însă o funcție foarte simplă de conversie a reprezentării în spațiul HSV: rgb2hsv. Valorile h, s și v rezultate sunt reprezentate în domeniul [0;1]. Pentru prelucrarea propusă în lucrarea de laborator, vom utiliza numai atributul de nuanță a culorii, deci componenta h. Mai mult, vom considera (pentru o reprezentare unitară și conformă cu literatura de specialitate) reprezentarea nuanței în domeniul [0;255], ceea ce presupune scalarea componentei h prin simpla înmulțire cu constanta 255: H=255*h.
Diferitele valori ale nuanței H definesc culorile importante din spectrul vizibil: roșu, orange, galben, verde, cyan, albastru, indigo (purpuriu), violet (magenta), roz și (la capătul domeniului) din nou roșu (în conformitate cu reprezentarea unghiulară, deci circulară, a nuanței – tipică în teoria prelucrărilor de imagini). Pentru fiecare culoare avem un interval al nuanțelor; de fapt, granițele între diferitele culori nu sunt tranșante (avem tranziții "line" între nuanțele corespunzătoare unor culori alăturate), motiv pentru care este mai potrivită reprezentarea nuanțelor corespunzând culorilor enumerate prin mulțimi fuzzy.
În această reprezentare, universul discuției este domeniul valorilor posibile pentru nuanță, X=[0;255], iar variabila din universul discuției este nuanța H. Pentru fiecare culoare vom avea definită câte o mulțime fuzzy peste X. Ca urmare avem un total de 9 mulțimi fuzzy, cu funcțiile de apartenență notate prin: Red, Orange, Yellow, Green, Cyan, Blue, Purple, Magenta, Pink, definite toate peste X, cu valori în [0;1]. Pentru simplitatea reprezentării, alegem o abordare simplă din literatura de specialitate în care cele 9 mulțimi sunt reprezentate prin funcții de apartenență liniare pe porțiuni (triunghiulare și trapezoidale). Cele 9 mulțimi și parametrii lor sunt prezentate în figura de mai jos.
Să considerăm acum următoarea aplicație: avem de analizat o imagine color care conține obiecte (zone) de culoare dominant roșie și dominant verde. Dorim să separăm doar zonele (obiectele) de culoare dominant roșie, adică, să le reprezentăm (indiferent de micile lor variații de culoare) prin nivele de gri cât mai apropiate de alb (cu atât mai apropiate de alb cu cât sunt mai "roșii"), spre deosebire de orice alte culori din imagine, pe care vrem să le reprezentăm prin negru (fond).
Fig 3.12
Folosind mulțimile fuzzy de mai sus și operațiile cu mulțimi fuzzy, putem spune că de fapt dorim să definim o nouă mulțime fuzzy, care să reprezinte conceptul "Culoare dominant roșie" sau, "Culoare foarte apropiată de roșu". Observăm că, în percepția vizuală a ochiului uman, vom "cataloga" ca obiecte roșii nu doar pe cele corespunzătoare strict nuanței roșu (Red), ci și pe cele portocalii (dacă este un portocaliu spre roșu) și, cu siguranță, pe cele roz (Pink). Ca urmare, mulțimea fuzzy „Culoare foarte apropiată de roșu” (definită peste universul discuției X al nuanței H} poate fi reprezentată lingvistic prin conceptul: culoare foarte apropiată de roșu = culoare roșu SAU (culoare portocaliu DAR NU culoare galben) SAU culoare roz. într-o formulare echivalentă, înlocuim DAR prin ȘI => culoare foarte apropiată de roșu = culoare roșu SAU (culoare portocaliu ȘI NU culoare galben) SAU culoare roz.
Cum conectivul lingvistic SAU reprezintă reuniunea unor mulțimi fuzzy, operatorul NU reprezintă complementarea, conectivul ȘI reprezintă intersecția unor mulțimi fuzzy, reprezentăm, peste universul discuției X al nuanței H, mulțimea fuzzy CuloareAproapeDeRoșu, uti Uzând operațiile cu mulțimi fuzzy, prin funcția de apartenență CuloareAproapeDeRoșu:[0,1] dată de expresia:
CuloareAproapeDeRoșu(H)=Roșu(H)Roz(H) (Portocaliu(H) NotGalben<H)),
sau:
CloseToRed(H)=Red(H) (Orange(H) )Pink(H).
Folosind ca operator de reuniune – operatorul max, iar ca operator de intersecție – operatorul min, obținem:
CloseToRed(H)=max{Red(H)), min {Orange(H), }, Pink(H).
Cu cât obiectul sau zona din imagine (pixelul din imagine) este mai roșu, cu atât gradul său de apartenență la mulțimea CloseToRed este mai mare. Reprezentarea vizuală a rezultatului obținut se poate realiza ușor dacă realizăm o scalare a gradului de apartenență rezultat în domeniul [0;255], pentru fiecare pixel, și afișăm rezultatul ca imagine de luminanță (zonele albe sau apropiate de alb vor corespunde obiectelor de interes de culoare dominant roșie identificate în imagine.)
Exemplificare: implementarea în Matlab.
– pentru operațiile de deschidere a unei imagini și conversie în spațiul HSV se vor folosi funcțiile imread, respectiv rgb2hsv
– pentru extragerea componentei H din matricea tridimensională rezultată în urma conversiei imaginii color în spațiul HSV, considerând această matrice notată prin ImHSV, vom folosi sintaxa:
hIm(:,:)=ImHSV(:,:,1), dat fiind că în matricea 3-D, a treia dimensiune corespunde coordonatelor H, S și V ale spațiului, iar prima coordonată este H.
– pentru definirea funcțiilor de apartenență ale celor 9 mulțimi fuzzy și calculul gradelor de apartenență ale nuanțelor tuturor pixelilor din imagine la mulțimile fuzzy vom folosi funcțiile Matlab dedicate:
1. trimf pentru o mulțime fuzzy triunghiulară; mulțimea se specifică prin parametrii săi (colț stânga – vârf – colț dreapta); de ex. mulțimea Orange se descrie prin vectorul [O 21 43]. Calculul gradului de apartenență al unei valori h oarecare la mulțime se face apelând funcția astfel:
GrdAp*=trimf(h*,[0 21 43]).
2. trapmf pentru o mulțime fuzzy trapezoidală; mulțimea se specifică prin parametrii săi (colț stânga bază mare – colț stânga bază mică -colț dreapta bază mică – colț dreapta bază mare); de ex. mulțimea Green se descrie prin vectorul [43 80 90 128]. Calculul gradului de apartenență al unei valori h oarecare la mulțime se face apelând funcția astfel:
GrdAp*=tmpmf(h*,[43 80 90 128]).
– pentru prelucrarea întregii imagini (tuturor pixelilor) vom folosi bucle for; domeniile de valori ale coordonatelor pixelilor sunt date de dimensiunile imaginii, aflate cu ajutorul funcției size:
lățimea imaginii, WSz=size(hIm,2)
înălțimea imaginii, HSz=size(hIm,l)
Codul Matlab pentru exemplificare:
U=imread('Peppers.bmp'); ImHSV=rgb2hsv(U);
H=255*hlm;
HSz = size(H, l);
WSz= size(H, 2);
for i=1:HSz, for j=l:WSz, if H(i, j)>255, H(i,j)=255;, end, end,end;
for i=1:HSz, for j=1:WSz, if H(i, j)<0, H(i,j)=0;, end, end, end;
for i=1:HSz, for j=1:WSz, Red(i,j)=max(trimf(H(i,j),[0 O 2l]),trimf(H(i, j),[234 255 255]));, end,
end;
for i=1:HSz, for j=1:WSz, Omnge(i,j)=trimf(H(i, j),[0 21 43]);, end, end;
for i=1Sz, for j=1:WSz, Yellow(i,j)=trimf(H(i, j),[21 43 80]);, end, end;
for i=1:HSz, for j=l:WSz, Green(i,j)=trapmf(H(i, j),[43 80 90 128]);, end, end;
for i=1:HSz, for j=1:WSz, Cyan(i,j)=trimf(H(i, j),[90 128 165]);, end, end;
for i=1:HSz, for j=l:WSz, Blue(i,j)=trapmf(H(i, j),[128 165 175 191]);, end, end;
for i=1:HSz, for j=l:WSz, Purple(i,j)=trimf(H(i ,j),[175 191 213]);, end, end;
for i=1Sz, for j=l:WSz, Magenta(i,j)=trimf(H(i, j),[191 213234]);, end, end;
for i=1:Sz, for j=l:WSz, Pink(i,j)=trimf(H(i,j),[213 234 255]);, end, end;
OrangeToRed=min(Orange, l – Yellow);
CloseToRed=max(Red,OrangeToRed);
CloseToRed=max(CloseToRed, Pink);
imshow(uint8(255 *CloseToRed))
figure(2)
imshow(U)
2.2.8. Algoritmul de „Clustering cu Vectori Suport” (SVC)
Prin acest algoritm de clasificare nesupervizat, punctele sunt mapate din spațiul de date într-un spațiu al trăsăturilor de dimensiune mare, folosind kernelul Gaussian. În acest spațiu se caută un hiperplan care să separe mulțimea de date de origine. Când acest hiperplan va fi mapat înapoi în spațiul de date va forma un set de contururi ce vor delimita punctele. Aceste contururi sunt interpretate ca margini ale cluster-elor. Punctele delimitate de fiecare contur în parte vor fi asociate aceluiași cluster. Pe măsură ce parametrul de lățime din kernelul Gaussian scade, numărul de contururi nelegate va crește, conducând la un număr ridicat de clustere.
Pentru a separa datele de origine se rezolvă următoarea cuadratură:
(12)
unde: (13)
Ne așteptăm că dacă w și rezolvă această problemă, atunci funcția de decizie
(14)
va fi pozitivă pentru majoritatea xi conținuți în mulțimea de date, în timp ce va fi în continuare mic.
Folosind introducem următorul lagrangian:
(15)
și derivatele vor respecta:
(16)
, (17)
Toți acei xi pentru care αi > 0se numesc vectori suport.. Deci funcția f se transformă într-o expansiune a kernel-ului.
(18)
Înlocuind ecuațiile (16) și (17) în (15) obținem problema duală:
(19)
unde:
, (20)
Putem obține valoarea folosind faptul că pentru orice αi > 0 forma corespunzătoare xi verifică:
(21)
2.3. Teoria codurilor
2.3.1. Noțiuni introductive
Se poate spune că originea teoriei codurilor stă în apariția calculatoarelor. Computerele inițiale erau niște monștri mecanici a căror fiabilitate era foarte scăzută comparativ cu calculatoarele din zilele noastre. Dacă un releu se defecta întregul calcul era eronat.
În timp ce lucra pentru laboratoarele Bell, R. W. Hamming s-a gândit la faptul că dacă aparatul era capabil să constate că este într-o stare eronată poate există o metodă pentru ca aparatul să și corecteze acea eroare; lucrând la această problemă, a descoperit o cale de a codifica informația astfel încât eroarea detectată să poată fi și corectată. Bazându-se parțial pe aceste operațiuni, Claude Shannon a pus bazele studiului științific al teoriei codurilor.
Ceea ce numim astăzi Teoria Codurilor se referă mai exact la Teoria Codurilor Corectoare de Erori, întrucât mai există un domeniu mai vechi al Teoriei Codurilor care se ocupă de crearea și descifrarea mesajelor secrete – domeniu numit Criptografie.
Problema pe care o considerăm se referă la dificultățile ce pot apărea la transmiterea de mesaje cauzate de zgomote, semnal slab, căderi de energie sau alte cauze naturale. Trebuie să ne asigurăm ca mesajul inițial să poată fi dedus la recepție.
O primă abordare la această problemă o reprezintă codul repetat. De exemplu dacă dorim să transmitem mesajul BAD NEWS am putea repeta fiecare literă de 5 ori astfel:
BBBBBAAAAADDDDD NNNNNEEEEEWWWWWSSSSS
Chiar dacă la recepție primim și alte litere în mesaj:
BBBEBFAAAADGDDD MNNNTEEEEEWWWSWRRSSS
se poate reconstitui mesajul inițial pe baza procesului numit decizie majoritară.
Această rezolvare este neeconomică și deci ineficientă, întrucât lungimea codului crește foarte mult deci implicit și timpul necesar transmisiei.
Terminologia folosită în cadrul teoriei codurilor include următoarele noțiuni:
Cuvânt de cod – un bloc de simboluri repetate, o bucată de informație transmisă.
Cod – mulțimea tuturor cuvintelor de cod.
Cod de blocuri – cod în care toate cuvintele au aceeași lungime
Exemplu: Codurile repetate sunt un tip de coduri de blocuri. Pentru cazul considerat când cuvintele au lungimea 5, codul repetat poate detecta între 1 și 4 erori apărute în transmisia unui cuvânt, întrucât orice cuvânt de 5 litere în care apar litere distincte nu este un cuvânt de cod.
Totuși e posibil să nu se detecteze 5 erori (când apare de exemplu BBBBB în loc de AAAAA). De aceea spunem că acest cod detectează 4 erori, adică este 4-detector. O altă caracteristică este aceea de a corecta erori – acest cod poate corecta întotdeauna 1 sau 2 erori, dar poate decodifica un cuvânt ce are 3 sau mai multe erori în mod incorect – de aceea spunem că este un cod 2-corector.
2.3.2. Fundamente. Coduri liniare
Să presupunem că ni se transmite un cuvânt din limba engleză și la recepție primim cuvântul SHIP. Dacă bănuim că au apărut unele erori la transmisie, nu putem stabili ce cuvânt ni s-a transmis cu adevărat – ar putea fi oricare din următoarele: SKIP, SHOP, STOP, THIS, de fapt orice cuvânt de 4 litere.
Problema este că cuvintele englezești sunt prea aproape unele de altele. Ce determină puterea unui cod de a corecta erorile este faptul că aceste cuvinte sunt cât mai distanțate unele de altele.
Mai întâi facem câteva precizări: vom considera doar codurile bloc (cuvinte de lungime egală), iar alfabetul folosit ân crearea cuvintelor va fi doar 0 și 1.
Deci vom obține cuvinte reprezentând n-tupluri de 0 și 1, unde n este lungimea cuvântului. Acestea poată fi văzută mai abstractizat ca elemente ale unui spațiu vectorial n-dimensional peste GF(2).
Distanța Hamming dintre 2 cuvinte de cod reprezintă numărul de simboluri corespondente care diferă. De exemplu, cuvintele (0,0,1,1,1,0) și (1,0,1,1,0,0) au distanța Hamming egală cu 2.
Această distanță Hamming este o metrică în spațiul vectorial, adică verifică:
d(x,x) = 0
d(x,y) = d(y,x)
d(x,y) + d(y,z) >= d(x,z) .
Fig 3.13 Reprezentarea distanței Hamming sub formă de cub
Distanța minimă a codului C este cea mai mică distanță între oricare pereche de cuvinte distincte din C.
Dacă distanța minimă a unui cod C este 2e + 1, atunci codul C este e-corector, ântrucît dacă apar e sau mai puține erori într-un cuvânt atunci cuvântul rezultat este mai aproapre de cuvântul original decât de oricare alt cuvânt de cod, deci poate fi decodificat în mod corect.
Ponderea unui cuvânt reprezintă numărul de componente nenule din vector. De asemenea, ponderea este distanța cuvântului față de vectorul nul.
d(x,0)=w(x); d(x,y)=w(x-y)
O clasă importantă de coduri sunt codurile liniare, singurele coduri în care cuvintele formează un subspațiu vectorial.
În general, găsirea distanței minime a unui cod implică compararea fiecărei perechi de elemente distincte. Pentru codurile liniare acest lucru nu este necesar, întrucât avem următoarea propoziție:
Propoziție – Într-un cod liniar distanța minimă este egală cu ponderea minimă a cuvintelor de cod nenule.
Dem: Fie x și z cuvinte din codul C => x-y este în C, deoarece C este liniar.
Avem așadar d(x,y) = d(x-y,0) = w(x-y).
2.3.3. Codul Hadamard
Fig. 3.14 Matricea codului Hadamard (32, 6, 16) pentru codul Reed-Muller (1, 5) al sondei spațiale Mariner 9 lansate de NASA în 1971
2.3.3.1. Construirea codului
Codul Hadamard , denumit astfel după Jacques Hadamard, este un sistem utilizat pentru detectarea și corectarea erorilor de semnal. Codul aparține familiei de coduri [2 n , n + 1, 2 n − 1 ]. Are o rată mică de detecție mai ales pentru un n mare, dar este capabil să corecteze multe erori.
Acest cod se bazează pe matricile Hadamard. Dacă H este o matrice Hadamard de ordin 2n, cuvintele de cod sunt construite prin considerarea rândurilor matricilor H și -H ca și cuvinte de cod, unde fiecare -1 se înlocuiește cu 0. În acest mod sunt construite 2 n + 1 cuvinte de cod, fiecare având o lungime de 2 n. Deoarece rândurile dintr-o matrice Hadamard sunt ortogonale distanța minimă va fi de 2 n – 1. În acest fel este construit un cod [2n, n + 1, 2 n – 1].
Acest cod poate fi, de asemenea, obținut prin crearea matricii de verificare a parității care este alcătuitădin toți cei 2n – 1 vectori care conțin un număr impar de 1, sau prin utilizarea unui proces de codificare recursivă.
Obs: S-a dovedit că, pentru valori ale lui n <= 6, codurile Hadamard sunt optime.
2.3.3.2. Decodificarea
Codul are distanța minimă 2n – 1 și, prin urmare, poate corecta cel mult t = 2 n – 2 – 1 erori. Algoritmul de mai jos realizează acest lucru.
Când se primește un cuvânt de cod acesta este transformat în primul rând într-un vector v 1/-1 schimbând toate 0-urile în -1. Se calculează apoi (v H T). Intrarea maximă în valoare absolută corespunde rândului luat ca un cuvânt de cod. Dacă acesta este pozitiv, atunci cuvântul de cod a fost primit de la H, în cazul în care este negativ cuvântul de cod a venit de la – H.
Demonstrație: Dacă nu au existat erori, produsul (v H T) ar consta doar din zero și un singur de +/−2 n. Dacă există erori în v, apoi, în valoare absolută, unele dintre zerouri devin mai mari, iar maximul devine mai mic. Fiecare eroare care apare poate modifica un zero în 2. Deci zero-urile pot deveni cel mult 0 + 2 t = 2 n – 1 – 2. Maximul poate scade la 2 n – 2 t = 2 n – 2 n – 1 + 2 = 2 n – 1 + 2. Deci maximul care indică rândul corect va fi întotdeauna mai mare în valoare absolută, decât celelalte valori din rând.
2.3.3.3. Istoric
Un cod Hadamard a fost folosit în timpul misiunii Mariner 9 din 1971 pentru a corecta eroarea de transmitere a imaginii. Cuvintele folosite în timpul acestei misiuni au avut lungimea de 6 biți, care au reprezentat 64 de valori ale tonurilor de gri. Din cauza limitărilor existente în calitatea alinierii emițătorului, lungimea maximă a datelor utile a fost de aproximativ 30 de biți. În loc de a folosi un cod de repetare, a fost fososit un cod Hadamard [32, 6, 16] care ar putea corecta erori de până la 7 biți per cuvânt. În comparație cu un 5-cod de repetare, codul Hadamard are proprietăți de corectare a erorilor mult mai bune, deși rata este comparabilă. Algoritmul eficient de decodificare a fost un factor important în decizia de a folosi acest cod. “Mașinăria” construită în acest scop s-a numit "Mașina Verde (Green Machine)" și a folosit transformata Fourier rapidă, care poate crește viteza de decriptare de 3 ori.
III. Considerații de implementare
3.1. Contextul realizării aplicației
3.1.1. Noțiuni introductive
3.1.1.1. Spectrul electromagnetic
Undele electromagnetice sau radiația electromagnetică sunt fenomene fizice care constă dintr-un câmp electric și unul magnetic care se generează unul pe altul pe măsură ce se propagă.
Spectrul electromagnetic se referă la întreaga gamă de frecvente si lungimi de undă ale undelor electromagnetice. Lumina tradițională se referă la gama frecvențelor care pot fi recepționate și de către om.
În funcție de frecvența sau lungimea de undă cu care radiația se repetă în timp, respectiv în spațiu, undele electromagnetice se pot manifesta în diverse forme. Spectrul radiațiilor electromagnetice este împărțit după criteriul lungimii de undă în câteva domenii (vezi fig. 1.1):
radiații hertziene,
radiații infraroșii,
radiații luminoase,
radiații ultraviolete,
radiații X (sau Röntgen ),
radiații γ (gamma).
Pornind de la frecvențele joase avem undele radio, care se folosesc și pentru transmiterea semnalelor de televiziune, pentru comunicații prin satelit și telefonie mobilă. Microundele sunt folosite atât în comunicații cât și în cuptorul cu microunde, care se bazează pe absorbția relativ puternică a radiațiilor de această frecvență în apă și materii biologice. Undele milimetrice se folosesc de exemplu în astronomie. Undele terahertziene au început abia de curând să fie cercetate și folosite în aplicații practice. Radiația infraroșie este foarte utilă în analize fizico-chimice prin spectroscopie. Lumina vizibilă este cel mai la îndemână exemplu de unde electromagnetice. Radiația ultravioletă este responsabilă pentru bronzarea pielii. Razele X sînt folosite de multă vreme în medicină pentru vizualizarea organelor interne. Razele gamma se produc adesea în reacții nucleare.
Aproape toate obiectele din univers emit, reflectă sau transmit lumină (probabil cu excepția materiei negre). Distribuția acestei lumini în cadrul spectrului electromagnetic (numit spectrul său) este determinat de compoziția obiectului.
Fig. 4.1 – Spectrul electromagnetic
3.1.1.2. Teledetecția
Capacitatea oamenilor de a vedea Pământul din spațiu a crescut odată cu perfecționarea tehnologiei. În ziua de azi sateliții ce orbitează deasupra Pământului sunt dotați cu un număr mare de camere si senzori. Acestea transmit datele la posturile de recepție de la suprafață unde sunt procesate pentru a obține imagini vizibile. Tehnicile și procedurile de analiză folosite în explorarea planetei noastre din spațiu formează teledetecția.
Agențiile guvernamentale se ocupă de construirea instrumentelor de înaltă tehnologie și plasează sateliții pe orbită. Oamenii de știință și studenții pot accesa imaginile luate din sateliți pentru a avea o mai bună perspectivă asupra planetei.
Sateliții orbitează în jurul Pământului urmând câteva tipare caracteristice. Orbitele cele mai obișnuite sunt cea geostaționară și cele polare. Sateliții geostaționari rămân tot timpul deasupra unui singur punct de pe suprafața Pământului. Ei înconjoară planeta odată la 24 de ore vizualizând aceeași porțiune. Sateliții de pe orbitele polare înconjoară planeta situându-se într-un plan constant în timp ce Pământul se rotește dedesubt. Aceștia obțin doar imagini de tip fâșie care trebuie apoi lipite ca într-un mozaic.
Sateliții poartă instrumente ce adună o cantitate variată de date. Instrumentele ce achiziționează și stochează energia emisă natural sau reflectată de suprafața Pământului folosesc o abordare pasivă; acestea înregistrează efectiv cantitatea de energie ce o recepționează. Un exemplu de astfel de instrument este camera digitală. Când obiectivul camerei se deschide senzorii din interior înregistrează intensitatea luminii, iar apoi datele sunt procesate într-o imagine.
Lumina vizibilă nu este singura lungime de undă electromagnetică pe care un satelit o poate recepta. Senzori specializați pot înregistra energia de diferite lungimi de undă pentru a genera imagini ale obiectelor care nu pot fi detectate în mod obișnuit.
Instrumentele sensibile la undele infraroșii pot înregistra scene chiar și în timpul nopții; acesta e un prim exemplu de utilizare a unei lungime de undă diferită de lumina vizibilă pentru a obține informații.
Majoritatea sateliților de astăzi măsoară energia la diferite lungimi de undă. Imaginile capturate la diferite lungimi de undă pot fi combinate pentru a realiza imagini compozite. Aceste imagini compozite rezultate pot fi folosite pentru a identifica trăsături ale suprafețelor.
Fig. 4.2 – Imagini multispectrale
(prin bunăvoința MITI, ERSDAC, JAROS and the U.S./Japan ASTER Science Team)
3.1.1.3. Imagini multispectrale
Tehnologia de obținere și prelucrare a imaginilor multispectrale a fost inițial dezvoltată pentru imaginile luate din spațiu. Senzorii multispectrali pot capta undele electromagnetice dincolo de banda luminii vizibile și astfel se pot obține informații suplimentare pe care omul nu le poate percepe cu ochiul liber ce posedă receptori doar pentru roșu, verde și albastru.
Imaginile multispectrale sunt principalul tip de imagini achiziționate de radiometrele de teledetecție. De regulă, sateliții au între 3 și 7 radiometre (SPOT are 3, LandSat are 7). Fiecare dintre acestea achiziționează o imagine digitală (numită scenă) într-o bandă îngustă începând cu spectrul vizibil(denumită zona RGB), până la infraroșu (clasificat ca NIR-Infrarosu apropiat, MIR-InfraRoșu mediu și FIR-Infraroșu îndepărtat sau Termic).
În cazul satelitului Landsat se obțin 7 scene ce constituie o imagine multispectrală cu 7 benzi.
Această tehnologie a ajutat de asemenea și la interpretarea unor papirusuri antice ca cele găsite la Herculaneum prin folosirea benzii de infraroșu. În general un astfel de text văzut cu ochiul liber apare ca scris negru pe hârtie neagră; la 1000 nm însă diferențele de reflectare a luminii fac textul să fie lizibil.
Fig. 4.3 – Satelitul Landsat-7
3.1.2. Metrici și distanțe. Similarități
3.1.2.1. Spațiul metric
În matematică un spațiu metric este o mulțime pe care s-a definit o distanță între elementele sale. Spațiul metric pe care îl putem percepe cel mai intuitiv este spațiul euclidian tridimensional pe care se definește distanța dintre două puncte ca lungimea liniei ce le unește.
Un spațiu metric este un tuplu (M,d) unde M este o mulțime (a formelor) și d o metrică pe M, adică o funcție: d: E X E ->|R astfel încât:
d(x, y) ≥ 0 [d(x,y) = 0 x=y, x,yE (identitatea) ]
d(x, y) = d(y, x), () x,yE (simetria)
d(x, y) ≤ d(x, z) + d(z, y), () x,y,zE (inegalitatea triunghiului).
Aplicația d se numește distanță.
În procesul de clasificare a formelor se pot folosi diverse distanțe.
3.1.2.2. Distanțe
a) Distanța Euclidiană generalizată
b) Distanța Mahalanobis (Minkowski) de ordin n
c) Distanța Cebîșev
d) Distanța City-Block (Manhattan)
unde p este dimensiunea vectorilor x si y (în cazul recunoașterii formelor este numărul de caracteristici).
Se observă că distanța Minkowski devine:
distanța euclidiană, pentru n=2;
distanța Manhattan, pentru n=1;
distanța Cebîșev, pentru n= ∞.
Să considerăm următorul exemplu; fie M, matricea formelor:
atunci vom avea următoarele distanțe:
3.1.2.3. Similarități
Coeficientul de similaritate este o relație simetrică și este folosit pentru a măsura gradul de asemănare dintre două forme. Prin funcție de similaritate vom întelege o relație care asociază unui număr de două obiecte X si Y un număr pozitiv S(X,Y) capabil să măsoare asemănarea dintre formele caracteristice acestora (atunci când formele sunt reprezentate sub forma unor vectori cu caracteristici binare).
Vom prezenta exemple de indici de similaritate pentru formele ce au caracteristici binare. Pentru început vom defini următoarele mărimi având semnificațiile:
a – numărul de atribute deținute în comun de cele două forme
b – numărul de atribute deținute doar de cea de-a două forma
c – numărul de atribute deținute doar de prima forma
d – numărul de atribute ce nu sunt deținute de nici una din forme
a) Russel & Rao
b) Jaccard
c) Kendall
Fie x și y două forme având următoarele caracteristici binare:
x = (1,1,0,0,1), y = (1,0,0,1,1);
atunci:
a = 2 (1,x,0,x,1)
b = 1 (x,x,x,1,x)
c = 1 (x,1,x,x,x)
d = 1 (x,x,0,x,x)
și: S1 = 3/5 = 0.6, S2 = 3/(5-1) = 3/4 = 0.75, S5 = (3+1)/5 = 4/5 = 0.8.
3.1.3. Softul utilizat
3.1.3.1. ENVI
ENVI este soft-ul ideal pentru vizualizarea, analiza și reprezentarea a tuturor tipurilor de imagini digitale. Pachetul complet de analiză și procesare a imaginilor include unelete avansate și totuși ușor de utilizat precum: instrumente spectrale, corecții geometrice, analiză de teren, analiză radar, capabilități raster, suport larg pentru o varietate de imagini.
ENVI poate oferi asistență în multiple domenii precum:
agricultură și domeniul forestier;
planificarea și analiza orașelor;
geologie;
ingineria mediului;
industrie;
astronomie.
Una dintre cele mai importante aspecte ale acestui program este faptul că furnizează funcții pentru clasificare. Se poate folosi clasificarea nesupervizată pentru a clusteriza pixelii dintr-o mulțime de date, fără intervenția utilizatorului.
Tehnicile de clasificare nesupervizate disponibile cuprind K-means și Isodata.
3.1.3.2. Utilizarea sistemului Matlab pentru aplicații grafice
3.1.3.2.1. Generalități
MATLAB este un mediu de programare și un limbaj de înaltă performanță utilizat în tehnică care integrează calcul numeric, grafică avansată, vizualizare și programare. Acesta oferă cercetătorilor, inginerilor și oricărui om de știință un sistem interactiv, puternic și ușor de utilizat, în care problemele și soluțiile sunt exprimate într-un mod natural. Utilizările sale tipice includ:
calcul matematic (numeric și simbolic);
algoritmi de dezvoltare;
modelare și simulare;
analiză de date, explorarea și vizualizarea acestora;
grafică științifică și inginerească; aplicații de dezvoltare, incluzând realizarea de interfețe grafice utilizator.
MATLAB are o familie de aplicații specifice numite "toolboxes", care aplică o tehnologie specializată și care sunt o colecție de funcții MATLAB ("M-files") ce extind mediul MATLAB să rezolve clase particulare de probleme. Aria în care sunt disponibile toolbox – urile include: procesare de semnal, procesare de imagine, comanda sistemelor, simulare, rețele neurale, fuzzy logic și multe altele.
Toată familia de produse MATLAB aparține firmei The MathWorks Inc. Ultima versiune este MATLAB 7. Numele de MATLAB provine de la "matrix laboratory".
MATLAB este un sistem interactiv, al cărui element de bază este o matrice care nu trebuie declarată înainte de folosire și care nu are o dimensiune ce trebuie specificată. In sens larg, un vector este o matrice cu o linie sau o coloană, iar un scalar este un vector cu dimensiunea 1. Acest mod de lucru permite exprimarea simplă și naturală a operațiilor matematice (așa cum s-ar scrie pe hârtie) și rezolvarea multor probleme de calcul tehnic cu formulări matriceale și vectoriale.
MATLAB – lucrează fie în modul linie de comandă, situație în care fiecare linie este prelucrată imediat, rezultatele putând fi afișate, fie cu programe (mai multe instrucțiuni MATLAB, cu posibilitatea apelării altor fișiere de același tip și a apelării recursive) conținute in fișiere numite fișiere – M ("M-files") deoarece au extensia .m.
Sistemul MATLAB cuprinde 5 părți principale:
Limbajul MATLAB este un limbaj de nivel înalt de tip matrice / vector cu instrucțiuni de control, funcții, structuri de date, intrări / ieșiri și trăsături de programare orientată pe obiecte.
Mediul de lucru MATLAB este un set de instrumente și facilități cu care intră în contact utilizatorul sau programatorul MATLAB. Include facilități pentru gestiunea variabilelor (acces, vizualizare, informații) în spațiul de lucru și importarea / exportarea datelor.In plus, permite dezvoltarea, depanarea și lucrul cu fișiere de tip M ("M-files").
"Handle Graphics" este sistemul grafic MATLAB care include comenzi de nivel înalt pentru vizualizări 2-D și 3-D, procesare de imagine, animație și prezentări grafice. Include și comenzi de nivel redus pentru personalizarea modului de prezentare a graficelor și construirea interfețelor grafice utilizator (GUI) pentru aplicații.
Librăria de funcții matematice MATLAB este o colecție vastă de algoritmi de calcul și analiză. Există peste 500 de funcții matematice, pentru statistică și inginerie optimizate pentru calcul matriceal. Acestea includ:
algebră liniară și calcul matriceal;
funcții Fourier și de analiză statistică;
rezolvare de ecuații diferențiale;
operații trigonometrice și alte operații matematice fundamentale.
5) Interfața Program Aplicație ("Application Program Interface") – API – este o librărie specializată care permite interacțiunea cu programe externe mediului MATLAB. Este permisă astfel apelarea programelor scrise în C sau Fortran, importarea / exportarea datelor și stabilirea de relații de tip client / server între MATLAB și alte programe.
MATLAB furnizează:
– o serie de funcții (rutine) grafice de nivel înalt care implementează cele mai utilizate tehnici pentru afișarea datelor precum reprezentările grafice în coordonate rectangulare sau polare, reprezentările grafice speciale (cu bare, histograme ș.a.), reprezentările grafice ale liniilor de contur sau suprafețelor și animația. In plus, prin funcții specializate, pot fi controlate unele aspecte privind modul de prezentare al graficelor (culoare, umbrire, etichete pe axe ș.a.) fără a fi necesară accesarea explicită a unor proprietăți ale obiectelor.
– sistemul grafic orientat pe obiecte ("Handle Graphics"), care permite inclusiv realizarea de interfețe grafice programabile. "Handle Graphics" definește un set de obiecte grafice (linii, suprafețe, text ș.a.) și oferă mecanismul de manipulare a acestor obiecte pentru a obține rezultatele dorite. Se poate avea astfel un control mult mai precis asupra modului de afișare al datelor și se pot dezvolta aplicații grafice proprii. Utilizând "Handle Graphics", utilizatorul poate crea meniuri și elemente de control interactiv pentru reprezentările grafice (butoane prin apăsare, potențiometre, casete de control, liste de opțiuni)
Fișierele – M utilizator, create pentru a executa operații grafice, pot utiliza atât funcții grafice de nivel înalt cat și sistemul "Handle Graphics" în mod direct.
3.1.3.2.2. Sistemul grafic MATLAB orientat pe obiecte ("Handle Graphics")
MATLAB folosește programarea orientată pe obiecte pentru controlul interactiv al reprezentărilor grafice. Conform acesteia, ferestrele figură sunt obiecte figură ("figure") și sunt copii ai obiectului grafic rădăcină "root" (fereastra ecran). De asemenea, sunt părinți ai oricăror alte obiecte grafice: ai axelor ("axes"), elementelor de control ale interfețelor grafice ("uicontrol") și meniurilor ("uimenu").
Există 11 tipuri de obiecte grafice:
"root" , care este în topul ierarhiei și corespunde ecranului computer-ului; în mod automat, la inceputul unei sesiuni MATLAB, este creat obiectul "root"; Fig. 4.4.: Obiecte grafice în Matlab
"figure" – corespunde ferestrei figură;
"uicontrol" – sunt obiecte asociate controalelor unei interfețe grafice butoane prin apăsare,
butoane radio, slidere), care execută o funcție când sunt activate de utilizator;
"axes" – obiect care definește o zonă din fereastra figură asociată unui sistem de axe;
"uimenu" – obiecte asociate meniurilor unei interfețe grafice utilizator, dispuse în partea de sus a ferestrei figură;
"image" – obiecte de tip imagine;
"line" – obiecte grafice primitive de bază pentru cele mai multe grafice 2D;
"patch"- obiecte care constau în poligoane pline și laturile acestora;
"surface" – obiecte 3D care corespund reprezentărilor grafice 3D a matricelor de date;
"text" – obiecte de tipul șir de caractere;
"light" – obiecte care definesc surse de lumină care afectează toate obiectele în interiorul
unui sistem de axe.
Fiecare tip de obiect grafic are o serie de proprietăți ce pot fi modificate (setate). Sistemul MATLAB asociază fiecărui obiect grafic creat un identificator ("handle"). Pentru a putea accesa proprietățile obiectului, este util ca, la crearea acestuia, să se rețină identificatorul într-o variabilă.
Modificarea proprietăților obiectelor grafice se realizează apelând comanda set, care are următoarea sintaxă:
set (identificator, 'numele_proprietății', valoarea_ proprietății)
Pentru a obține valoarea curentă a unei proprietăți se apelează funcția get cu următoarea sintaxă:
get (identificator, ' numele_ proprietății')
Identificatorul obiectului rădăcină este totdeauna 0. Pentru obiectul figură, în mod implicit acesta este un număr întreg afișat în bara de titlu a ferestrei grafice.
Există și următorii identificatori predefiniți:
gcf – pentru fereastra figură curentă ("Get Current Figure")
gca – pentru sistemul de axe curent ("Get Current Axes")
Exemple de utilizare a funcțiilor set și get
set(gcf, 'color', V) – stabilește culoarea alb pentru figura curentă
set(gca, 'color', 'y') – stabilește culoarea galben pentru sistemul de axe curent
get(gcf, 'color') – returnează culoarea figurii curente
get(gca, 'color') – returnează culoarea sistemului de axe curent
3.1.3.2.3. Toolbox-ul Image Processing
Toolbox-ul Image Processing este o colecție de funcții care extind posibilitățile MATLAB din domeniul prelucrării imaginilor. Toolbox-ul dispune de o mare varietate de operațiuni de prelucrare a imaginilor, cum ar fi:
• Operații geometrice
• Operații de tip vecinătate
• Filtrare liniară și proiectarea filtrelor
• Transformate
• Analiza și îmbunătățirea imaginilor
• Operații binare
• Operații asupra regiunii de interes
Multe dintre funcțiile toolbox-ului sunt fișiere M-files care constau în instrucțiuni MATLAB care implementează algoritmi specializați de prelucrare a imaginilor. Aceste instrucțiuni pot fi vizualizate cu comanda cunoscută:
type function_name
Posibilitățile toolbox-ului pot fi extinse prin crearea de fișiere proprii prin utilizarea funcțiilor disponibile în combinație cu alte toolbox-uri cum ar fi Signal Processing Toolbox și Wavelet Toolbox.
3.2. Aplicația propriu-zisă
3.2.1. Aplicații în clasificarea imaginilor
3.2.1.1. K-means pentru puncte bidimensionale (în Matlab)
Pentru cazul punctelor din spațiul bidimensional s-a implementat un algoritm K-means în Matlab și s-a vizualizat evoluția acestui algoritm asupra unui grup de puncte (v. Anexa A):
Exemplu:
Fig 4.5 3 clustere 4 clustere
3.2.1.2. K-means pentru o imagine simplă (în Matlab)
Întrucât în Matlab orice imagine este văzută ca o matrice de pixeli s-a generalizat programul anterior pentru o imagine simplă (vezi Anexa A):
Exemplu – fig 4.6:
3.2.1.3. K-means și Isodata pentru imagini multispectrale (în ENVI și Matlab)
3.2.1.3.1. Influența alegerii metricii
În cazul seturilor de imagini multispectrale au fost efectuate următoarele proceduri:
s-au rulat algoritmii Isodata și K-means implementați în ENVI folosind distanța clasică euclidiană
s-a implementat și rulat K-means în Matlab folosind atât distanța euclidiană cât și distanța fracționară (cu valori diferite pentru „n”) cu scopul de a reduce zgomotul din imaginile obținute (vezi Anexa A)
s-au comparat rezultatele obținute și s-au întocmit histograme
Fig 4.7: Vizualizarea imaginilor multispectrale ca benzi
Ex.
Fie vectorul v=(2, 1024, 3, 10,…)
Se observă că v2 este o valoare mare comparativ cu celelalte => zgomot
Se încearcă atenuarea zgomotului prin folosirea distanței fracționare
Distanța Minkowsky:
Distanța fracționară utilizată:
0<n<1 (nu este o distanța obișnuită întrucât nu verifică inegalitatea triunghiului)
pt. => Sqrt(v)=(1.44, 12, 1.73, …)
=> introduce o atenuare a zgomotului
Fig 4.8: Graficul funcțiilor rădăcină pătrată și exponențială
Notă: Imaginile multispectrale folosite ca date de intrare aparțin Observatorului Astronomic din Cote dºIvoire sau au fost luate de pe site-ul NASA.
3.2.1.3.2. Date de intrare. Analiza rezultatelor
Exemplul 1 – fig. 4.9:
3C120: 547_LP.tif 555_LP.tif 657_LP.tif 814_LP.tif
ENVI: Isodata (5 clustere, distanța euclidiană) K-Means
Distanța euclidiană
Matlab: K-Means, 5 clustere
Distanța fracționară, n=2
Exemplul 2 – fig. 4.10:
n2683_lJ.tif n2683_lR.tif
ENVI: (distanța euclidiană)
K-means 5 clustere K-means 10 clustere IsoData min5max10
Distanța euclidiană
Matlab: K-means, 5 clustere
Distanța fracționară, n=2
Exemplul 3 – fig 4.11:
Nebuloasa Vulturul („Stâlpii Creației) – imagine fals-color
ENVI: (distanța euclidiană): K-means Isodata
Matlab: K-means (5 clustere) – Distanța euclidiană Distanța fracționară, n=2
3.2.2. Aplicații în segmentarea imaginilor
3.2.2.1. K-means pentru segmentarea imaginilor simple în spațiul RGB (în Matlab)
3.2.2.1.1. Clusterizarea intensității pixelilor
Segmentarea imaginilor multispectrale constă în găsirea zonelor din specimen cu compoziție aproximativ omogenă; aceasta se poate realiza prin clusterizarea pixelilor.
Putem folosi K-means pentru a clusteriza intensitățile pixelilor într-o imagine cu k clustere, acest algoritm furnizându-ne o cale simplă de a „segmenta” o imagine în k regiuni compacte de intensități similare. Această metodă este mai automată decât prăguirea manuală a unei imagini.
Procedura constă în următoarele (vezi Anexa A):
dimensiunea imaginii = dimensiunea matricii de pixeli = m x n
se convertește la un vector cu (m x n) linii și 1 coloană
acesta este un vector de trăsături unidimensional al intensităților pixelilor
se rulează algoritmul K-means având cadate de intrare vectorul de intensități
atribuie fiecărui pixel nivelurile de gri ale clusterului la care este asignat
Notă: la imaginile color se poate folosi un vector de trăsături tridimensional, pentru fiecare pixel având de exemplu valorile RGB.
3.2.2.1.2. Date de intrare. Analiza rezultatelor
Exemplul 1 – fig. 4.12:
Imaginea inițială Imaginea rezultată prin clustering
în spațiul RGB, k=11 segmente
Exemplul 2 – fig. 4.13a:
Exemplul 3 – fig. 4.13b: Viking Albedo Segment
3.2.2.2. SVC pentru segmentarea imaginilor multispectrale (în Matlab)
Următoarele proceduri au fost testate în segmentarea imaginilor multispectrale. Imaginea multispectrală din cazul de față reprezintă un bob de grâu obținut prin fluorescență.
S-a realizat apoi o secțiune transversală prin bobul de grâu. Scopul este acela de a identifica componentele fluorescente ale straturilor.
Cerealele au fost furnizate de INRA și imaginile au fost salvate de INRA .
Fig. 4.14 Descrierea aplicației
Reducerea dimensionalității a fost realizată folosind procedura de Analiză a componentelor principale. Distribuția de energie a componenetelor principale este prezentată mai sus
Algoritmii Parzen-watershed și SVC
au fost aplicați asupra unor imagini bidimensionale cu rezoluție de 80*10 two, imagini ce reprezintă cele două zone încadrate din cele două componenet principale.
Numărul de clase ce pot fi propuse este 6, 4 sau 3 conform algoritmului
Parzen-watershed.
Rezultatele segmentării sunt prezentate în figură.
Folosind algoritmul
SVC
numărul de clase semnificative crește. Rezultatele segmentării cu 6, respectiv 8 clase sunt prezentate în figură.
Rezultatele au fost apoi comparate cu o schemă teoretică a structurii bobului de grâu. Această comparare a arătat că straturile din grâu pot fi corect identificate în urma clasificării efectuate. O clasă nu corespunde neapărat unui anumit strat sau unei componente anume din bobul de grâu, dar straturile sunt totuși ușor identificabile ân cadrul imaginii obținute.
Fig. 4.18 Identificarea straturilor din secțiunea transversală de grâu
3.2.3. Aplicații în teoria codurilor
3.2.3.1. Codurile Hadamard. Misiunea spațială Mariner 9
Fie H o matrice Hadamard de ordinul 4. Se iau toate rândurile matricei H și rândurile matricei –H și se transformă toate aparițiile lui –1 în 0. Astfel obținem vectori de dimensiune 8m de lungime 4m peste GF(2). Acum folosind proprietățile matricii Hadamard obținem că distanța dintre 2 vectori distincți este sau 2m sau 4m. Deci, considerând că toate rândurile formează un cod, distanța minimă este 2m și codul va corecta (m-1) erori. Codurile formate în acest mod se numesc coduri Hadamard sau, dacă matricea Hadamard este formată prin luarea directă a produselor matricii Hadamard de ordinul 2, atunci se numesc coduri Reed-Muller de primul tip.
Pentru a examina procesul folosirii codurilor ne vom referi la o aplicație reală.
Fig 4.19 Sonda spațială Mariner 9
Mariner 9 a fost o sondă spațială a cărei misiune a fost zborul pe Marte și transmiterea de imagini către Pământ. Camera alb-negru de la bordul navetei Mariner 9 a captat imaginile și o grilă fină a fost plasată peste imagini, fiecare pătrățel al grilei de culoare neagră fiind măsurată pe o scală de la 0 la 63. Aceste numere, exprimate în cod binar sunt informațiile transmise către Pământ (mai precis către Laboratorul Jet Propulsion al Institutului Californian de Tehnologie din Pasadena). La primire semnalul original este foarte slab și de aceea trebuie amplificat. Zgomotul adăugat semnalului din spațiu și zgomotul termic de la amplificator determină ca ocazional când un semnal este transmis ca 1 el să fie interpretat de către receptor ca 0 și reciproc.
Dacă probabilitatea că aceasta să se întâmple este de 0.05, atunci prin calculul efectuat în introducere, dacă nu s-a făcut codificarea, aproximativ 26% din imaginea primită ar fi incorectă. Astfel, există deci nevoia codificării informației cu un cod de corectare a erorilor. Acum întrebarea care se pune este, ce cod ar trebui să folosim? Orice cod ar mări dimensiunea informației care este trimisă și acest lucru creează o problemă. Naveta Mariner 9 fiind un vehicul mic nu putea purta un transmițător imens, deci semnalul transmis trebuia să fie direcțional, dar peste distanțe mari un semnal direcțional are probleme de aliniere. Deci, există o mărime maximă a informației care poate fi transmisă deodată (în timp ce transmițătorul era aliniat). Astfel informația devine de 5 ori mai mare decât informația originală și deoarece informația constă din 6 biți (0, 1 – vectori de lungime 6), informația codată este de 30 de biți.
Codul de repetiție–5 era o posibilitate, având avantajul că este foarte ușor de implementat, dar corectează doar 2 erori. Un cod Hadamard bazat pe o matrice Hadamard de ordin 32 ar corecta 7 erori și merita să fie implementat chiar dacă era mai dificil. Folosind acest cod, probabilitatea erorii în imagine se reduce la numai 0.01% ( codul de repetiție-5 ar avea o probabilitate a erorii de aproximativ 1%).
Fig. 4.20 „Orașul Inca” situat lîngă polul sud marțian
Ne îndreptăm acum atenția asupra problemelor de codificare și decodificare a unui cod Hadamard. La o primă privire, codificarea nu pare să fie o problemă, existând 64 tipuri de date și 64 cuvinte de cod, deci orice corespondență arbitrară între date și cuvintele de cod este viabilă. Problema constă însă în faptul că naveta Mariner 9 este mică și această metodă necesită stocarea tuturor cuvintelor de cod de lungime de 32 de biți. Este mai economic, în termeni de spațiu și greutate, proiectarea componentelor hardware care vor calcula cuvintele cod, decât să fie citite dintr-un vector de stocare. Alegând corect matricea Hadamard, codul Hadamard va rezulta a fi un cod liniar și acest calcul va multiplica informația prin matricea generatoare a codului. Matricea Hadamard corectă este cea obținută prin luarea repetată a produsului direct a matricii Hadamard de ordin 2.
Considerăm problema de decodare. O schemă simplă de decodare este următoarea: un semnal receptat, de exemplu o secvență de 32 de zerouri și de unu-uri, este schimbat în ±1 (prin modificarea fiecărui 0 în -1). Dacă rezultatul este vectorul x și dacă nu sunt erori, atunci xHt, unde H este matricea Hadamard originală, va fi un vector de 31 de componente egale cu 0 și o componentă egală ori cu +32 ori cu –32. În prezența erorilor aceste numere sunt modificate, dar dacă numărul erorilor este mai mic decât 7 atunci valorile 0 pot crește până cel mult la 14 și valoarea 32 poate scădea până cel mult la 18. Astfel valoarea maximă din xHt ne va spune care rând din H sau –H (dacă este negativă) a fost transmis. Deși acesta este algoritmul folosit în decodarea semnalelor navetei Mariner 9, acesta este un pic lent din punct de vedere computațional (necesitând 322 de produse și sumele necesare pentru fiecare cuvânt de cod), deci se va folosi un truc de calcul pentru a reduce volumul de calcul la mai puțin de 1/3 (prin utilizarea Transformatei Fourier rapide).
3.2.4. Aplicații didactice de laborator
3.2.4.1. Argumentul profesorului – Analiza imaginilor de pe Marte
Cum înțeleg și interpretează oamenii de știință trăsăturile de suprafață ale planetei Marte luate de pe orbită și cum determină dacă un loc propus pentru amartizare va întruni scopurile misiunii de știință?
Distanța până la Marte variază între 80 și 240 milioane de kilometri. Acesta este motivul pentru care planeta este studiată folosind tehnici senzoriale aplicabile de la distanță.
Imaginile luate cu prilejul misiunilor Mars Global Surveyor și Mars Odyssey au oferit informații valoroase în ce privește înțelegerea suprafeței lui Marte. Aceleași imagini luate de sondele de pe orbită au ajutat la o mai bună înțelegere a trecutului geologic al planetei. Fenomenele geologice de pe Marte sunt similare cu cele de pe Pământ. Astfel un studiu interesant asupra planetei Marte va motiva elevii spre o mai bună înțelegere a fenomenelor de pe planeta noastră.
Misiunile de acest tip trebuie să țină în echilibru două domenii: ingineria și știința. Pentru o misiune de succes, inginerii trebuie să asigure succesul navetei spațiale, în special trebuie să aleagă o zonă în care amartizarea să se poată face cât mai în siguranță. Pe de altă parte, oamenii de știință trebuie să aleagă o zonă în care interesul științific poate fi cât mai bine satisfăcut. Aceste două grupuri de oameni trebuie să ajungă la un consens sau cel puțin la un compromis pentru ca misiunea să meargă mai departe.
Activitatea propusă va plasa elevii în rolul oamenilor de știință care trebuie să analizeze fenomenele geologice ce ar fi putut avea loc pe o imagine vizibilă luată de pe suprafața lui Marte cu ajutorul Sistemului de Imagini prin Emisie Termală (THEMIS).
Elevii vor putea apoi să facă o recomandare în privința faptului că zona prezentată prezintă interes din punct de vedere științific pentru a putea fi luată în considerare ca posibilă zonă de amartizare.
În acest scop, elevii pot urmări cele 4 scopuri majore ale explorărilor realizate de către NASA:
Determinarea faptului că există sau nu viață pe Marte
Caracterizarea climei de pe Marte
Caracterizarea geologică a planetei
Pregătirea pentru o explorare cu echipaj uman a planetei.
Așa cum s-a procedat și cu prilejul misiunii Mars Exploration Rover, aceste potențiale zone de amartizare vor fi apoi evaluate de către ingineri care însă vor folosi cu totul alte criterii.
Pe măsură ce elevii vor analiza imaginile de pe Marte, profesorul va trebui să-și îndrepte atenția mai degrabă asupra procesului prin care elevii decid, decât asupra faptului că au ales mai mult sau mai puțin răspunsul „corect”. Elevii vor trebui să poată motiva alegerea făcută, explicând procesul prin care au analizat și au înțeles imaginea.
Obiective:
Elevii vor căpăta o mai bună înțelegere a procesului de cercetare științifică și a istoriei geologice a unei planete (de exemplu Pământ și Marte) prin analizarea imaginilor THEMIS vizibile de pe planeta Marte.
Nivel de pregătire: clasele a V-a – a XII-a
Timp de desfășurare: 1-2 ore / săptămână
Materiale necesare pentru un grup de elevi (4 elevi / grup):
imagine mare laminată THEMIS (11” x 17” sau mai mare)
imagine de context (8.5” x 11”) a imaginii vizibile THEMIS, reprezentând zona înconjurătoare în care a fost realizată imaginea (Exemple de imagini sunt disponibile la adresa http://msip.asu.edu/sample.html sau se pot solicita imagini de împrumut prin contact la adresa [anonimizat])
Tabelul de identificare a trăsăturilor suprafețelor
Un tabel cu Jurnalul suprafețelor (4 pagini)
Marker cu scris solubil
2 rigle
2 calculatoare de buzunar
un glob sau o hartă a planetei Marte (pentru harta planetei Marte vizitați adresa http://msip.asu.edu și accesați harta MOLA în format JPG.)
Obiective educaționale standard:
Conținut standard 1: Ca rezultat al activităților lor, toți elevii ar trebui să-și dezvolte abilități necesare cercetării științifice:
Să identifice întrebări ce pot fi soluționate prin investigare științifică;
Să folosească mijloace potrivite pentru analizarea și interpretarea datelor;
Să dezvolte descrieri și explicații folosind dovezile existente;
Să gândească critic și logic pentru a crea relații între dovezile existente și explicații;
Să comunice procedurile științifice și explicațiile aferente.
Conținut standard 2: Ca rezultat al activităților lor, toți elevii ar trebui să-și dezvolte o înțelegere a:
Structurii planetei Pământ.
Naturii științei.
Principii și standarde (ale Consiliului Național al Profesorilor de Matematică -USA)
Numere și operații:
Să lucreze ușor și flexibil cu numere zecimale pentru a rezolva probleme.
Să înțeleagă și să folosească rapoarte și proporții pentru a reprezenta relații cantitative.
Măsurători:
Să înțeleagă atât sistemul metric, cât și alte sisteme uzuale de măsurare.
Să selecteze și să aplice tehnici și mijloace pentru a găsi exact dimensiunile la nivele de precizie potrivite.
Să rezolve probleme care implică utilizarea scărilor de măsură, folosind rapoarte și proporții.
Imaginea THEMIS
Imaginea THEMIS include numele regiunii în care imaginea a fost făcută și de asemenea imaginea include numărul de identificare a imaginii în colțul din dreapta jos. Imaginea vizibilă THEMIS are o rezoluție de 18 metrii pe pixel. Porțiunea superioară a imaginii este partea cea mai nordică a imaginii. Fiecare imaginea vizibilă completă THEMIS constă din 19 cadre (aproape ca niște dreptunghiuri individuale împreunate). Imaginile vizibile THEMIS au în lățime aproximativ 18 km și 57 km în lungime.
Extensii posibile:
• Activitatea poate fi extinsă la crearea proiectului pentru un rover sau pentru un oraș (biodom) pe Marte.
• Elevii pot să calculeze adâncimi și înălțimi ale componentelor împărțind lungimea umbrei la tangenta unghiului de incidență a soarelui cu suprafața
• Elevii pot să analizeze și să eticheteze imaginile folosind un software precum Adobe Photoshop.
3.2.4.2. Fișa de lucru – Analiza imaginilor de pe Marte
Nume_________________________
Clasa / Grupa_________________________
Data_________________________
Partea I: Contextul general
Prima parte din această activitate vă cere să va îndreptați atenția pe imaginea oferită, atât asupra imaginii cu contextul general, cât și asupra imaginii THEMIS. Imaginea de context arată cadrul mai larg din care face parte zona ce corespunde imaginii THEMIS.
Apoi încercați să răspundeți la următoarele întrebări:
1. Care este latitudinea și longitudinea imaginii?
2. Denumiți zona din care face parte imaginea ținând cont de imaginea de context
3. Descrieți zona din care face parte imaginea; puteți preciza dacă aceasta cuprinde multe cratere, se află lângă un vulcan sau prezintă urme posibile de apă.
Partea a II-a: Identificarea trăsăturilor de suprafață
Pentru această parte a activității veți eticheta diferite componente direct pe imaginea THEMIS. Pentru a vă ajuta veți folosi “Tabelul de identificare a trăsăturilor suprafețelor” și descrierile precizate. Dacă se găsesc mai multe exemple ale aceleiași componente, numerotați-le de exemplu astfel: Crater 1, Crater 2, Crater 3.
De realizat:
“Întocmește un tabel în care să treceți trăsăturile pe care le-ați regăsit în imagini. Emite o ipoteză prin care să precizezi cum crezi că s-au format acestea.”
Tabelul poate avea următoarea formă:
Jurnalul Suprafețelor
Imaginea THEMIS nr: ____________________________
Regiunea de pe Marte _____________________________
Tabelul de identificare a trăsăturilor suprafețelor
Imaginea de contextImaginea THEMISConcluzii
Îmbunătățirea tehnicilor senzoriale din teledecție ne permite azi să înregistrăm diferite “hărți” ale obiectelor observate. Analiza acestor hărți prin metode de clasificare ne permite să interpretăm conținutul obiectelor studiate cel puțin din punct de vedere calitativ. O interpretare mai exhaustivă o pot da specialiștii din domeniul studiat.
Prelucrarea și analiza imaginilor poate deveni mai interesantă prin perspectiva deschisă de multi-threading – existența și gestionarea de către o aplicație oarecare a mai multor fire de execuție ce rulează concomitent din punct de vedere logic (sau aproape concomitent din punctul de vedere fizic al calculatorului cu unic procesor). În general puține sisteme fizice multiprocesor au fost realizate pentru prelucrarea de imagini: sistemele de prelucrarea și analiza imaginilor au utilizat în general mașini cu paralelism masiv sau grupuri de calculatoare.
Exploatarea paralelismului este un merit pe care prelucrarea imaginilor și l-a arogat încă de la începuturi; operațiile tipice de prelucrarea imaginilor sunt operații relativ simple, cu un număr mare de instanțe (pentru fiecare pixel al imaginii se face ceva), folosind date puțin redundante (suprapunerea între pozițiile alăturate ale ferestrelor de filtrare este în general mică) și, uneori, informație globală (cazul histogramei sau a filtrărilor în domeniul de frecvență). Se pot distinge astfel două nivele de paralelism: un paralelism masiv, intrinsec structurii imaginii, legat de nivelul pixel, și un paralelism ascuns, specific operațiilor de prelucrare.
Misiunile spațiale curente și viitoare folosesc din plin tehnicile de prelucrare și analiză a imaginilor pe baza cărora oamenii de știință pot să tragă concluzii și să emită ipoteze cât mai apropiate de realitate. De asemenea, noțiunile de teoria codurilor au fost prezente încă de la primele misiuni, ele fiind necesare și în continuare pentru a putea răspunde în timp real situațiilor ce apar.
În concluzie, putem afirma că prelucrarea și analiza imaginilor a reușit să câștige teren ca urmare a realizărilor spectaculoase ale tehnologiei electronice și informaticii. Creșterea continuă a puterii de calcul disponibile în unitățile de prelucrare ale calculatoarelor va transforma probabil în viitorul apropiat prelucrarea și analiza imaginilor dintr-o anexă nebuloasă și exotică a aplicațiilor speciale într-o soluție fiabilă de larg consum industrial.
Bibliografie
[1] Castleman, K. R.: Digital Image Processing, Prentice Hall, Englewood Cliffs, New Jersey, 1996
[2] Curilă, S.; Curilă, M.: Tehnici de prelucrare a imaginilor utilizate la recunoașterea formelor, Editura Universtății din Oradea, 2004
[3] Gyorody, R.; Gyorody, Cornelia: Recunoașterea formelor și descoperirea cunoștințelor, Editura Mediamira, Cluj-Napoca, 2005
[4] Jain, A. K.; Dubes, R. C.: Algorithms for Clustering Data, Prentice Hall, Englewood Cliffs, New Jersey, 1998
[5] Jain, A. K.; Murty, M. N.; Flynn, P.J.: Data Clustering: A Review, ACM Computing Surveys, Vol. 31, No. 3, septembrie 1999
[6] Lazar, C.: Unsupervised data classification and its application in the segmentation of the multi-spectral images, University of Reims Champagne-Ardenne, CreSTIC Laboratory, 2005
[7] Marchand, P.: Graphics and GUIs with MATLAB, CRC Press, SUA, 1999.
[8] Memarsadeghi, Nargess; Mount, D.M.; Netanyahu, N.S; Le Moigne, Jacqueline: A Fast Implementation of the ISODATA Clustering Algorithm, International Journal of Computational Geometry and Applications (IJCGA), Vol. 17, No. 1, 2007
[9] Nuzillard, Danielle; Lazar, C.: Comparison of Two Unsupervised Methods of Classification for Segmenting Multi-spectral Images, International Conference on Acoustics, Speech, and Signal Processing 2006 (ICASSP’06). Toulouse, France, mai 2006.
[10] Nuzillard, Danielle; Lazar, C.: Méthodes de classification non supervisées pour l’analyse d’images multi-composantes, Paris, France, aprilie 2006
[11] Peterson, W.W.; Weldon, E.J.:, Error-Correcting Codes, MIT Press, Cambridge, 1972
[12] Pless, V.: Introduction to the Theory of Error-Correcting Codes, Wiley, New York, 1982
[13] Vertan, C.: Prelucrarea și analiza imaginilor, Editura Printech, București, 1999
[14] Vertan, C.; Ciuc, M.; Zamfir Marta: Analiza imaginilor – îndrumător de laborator, Editura Printech, București, 2001
Webgrafie
[15] http://fourier.eng.hmc.edu/e161/lectures/classification/classification.html
[16] http://en.wikipedia.org/wiki/Multispectral_image
[17] http://mars.jpl.nasa.gov/
[18] http://www.classzone.com/books/earth_science/terc/navigation/home.cfm
[19] http://www.ittvis.com/envi
[20] http://www-math.cudenver.edu/~wcherowi/courses/m6409/mariner9talk.pdf
[21] http://www.mathworks.com/products/image/
[22] http://www.yale.edu/ceo/Projects/swap/landcover/Unsupervised_classification.htm
Anexe
Anexa A: Coduri sursă
Anexa B: Glosar de termeni
Anexa C: Pliante
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Imagini Digitale (ID: 107010)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.