Aplicatii de Prelucrare a Imaginilor cu Camera Terrahertz. Algoritmul K Means

PROIECT DE DIPLOMĂ

MITROI ALEXANDRU

COORDONATOR ȘTIINȚIFIC

Prof.dr.ing DAN SELIȘTEANU

Septembrie 2014

Aplicații de prelucrare a imaginilor cu camera TerraHertz. Algoritmul

K-Means

CUPRINSUL

1 INTRODUCERE

2 PREZENTAREA HARDWARE ȘI SOFTWARE A ECHIPAMENTULUI UTILIZAT

2.1 DESIGNUL CAMEREI DE CIRCUIT

2.1.1 Arhitectura senzorilor camerei.

2.1.2 Detector față-spate și circuitul de reset.

2.1.3 Circuitul de ieșire.

2.1.4 Implementarea matricei și schema circuitului.

2.1.5 Designul camerei.

2.2 PREZENTAREA SOFTWARE-ULUI UTILIZAT.

2.2.1 Limbajul C.

3 SEGMENTAREA IMAGINILOR UTILIZÂND DIFERIȚI ALGORITMI

3.1 INTRODUCERE.

3.2 ALGORITMI DE SEGMENTARE AI IMAGINILOR.

3.2.1 Algoritmul K-Means.

3.2.2 Algoritmul EM.

3.2.3 Algoritmul Normalized Cut.

3.2.3.1 Algoritmul de grupare.

3.3 REZULTATE.

4 BINARIZAREA IMAGINILOR

4.1 INTRODUCERE

4.2 HISTOGRAMA IMAGINILOR

4.2.1 Histograma liniară

4.2.2 Histograma cumulativă

4.2.3 Histograma cumulativă normalizată

4.3 TEHNICI DE ÎMBUNĂTĂȚIRE A IMAGINILOR

4.3.1 Accentuare de contrast

4.3.2 Limitarea și binarizarea imaginilor

4.4 ALGORITMI DE BINARIZARE.

4.5 METODE DE BINARIZARE

4.5.1 AGB – P – tile thresholding

4.5.2 AGB – Optimal thresholding

4.5.3 Optimal thresholding – Metoda Otsu

5 ALGORITMUL K-MEANS

5.1 CLUSTER.

5.2 K-MEANS.

5.3 EXEMPLU.

6 APLICATIE K-MEANS

7 CONCLUZII

8 BIBLIOGRAFIE

8.1 REFERINTE WEB.

Introducere

În ultimele decenii progresul tehnologic precum și cel din domeniul aplicațiilor informatice, au facut ca accentul sa cadă în prezent pe aplicații care necesită o formă mai mult sau mai puțin evoluată de inteligență artificială. Din această mare familie face parte și clasa aplicațiilor de recunoaștere a formelor și obiectelor, aplicație des utilizată în automatizări industriale.

Acest tip de aplicații nu necesită echipamente hardware prea complicate, majoritatea dificultătilor fiind canalizate în realizarea programelor software care sa prelucreze și să interpreteze imaginile astfel obținute. Astfel pentru o abordare nealgoritmică a interpretării imaginilor, sinonimă cu inteligența artificială este necesară simplificarea imaginilor, ca de exemplu binarizarea imaginilor. Cu toate acestea, metoda de binarizare trebuie aleasă astfel încât să se piardă cât mai puțin din informația conținută de imaginea inițială. Deoarece nu există un absolut în domeniul binarizării, de obicei se acceptă o soluție de compromis.

Prezenta lucrare prezintă în prima parte structura sistemului hardware necesar pentru achiziția imaginilor, precum și o parte din funcțiile utilizate în prelucrarea imaginilor. Se evidențiază pe de altă parte simplitatea utilizarii pachetului Matlab pentru prelucrarea imaginilor, comparativ cu programe echivalente în C/C++.

În următoarel capitole vom prezenta o serie de algoritmi utilizați pentru eliminarea zgomotului și respectiv pentru binarizare, punând în evidență avantajele și dezavantajele fiecaruia. Pentru eliminarea zgomotului am utilizat algoritmul K-Means, iar pentru binarizare metoda tip “thresholding”.

PREZENTAREA HARDWARE șI SOFTWARE A ECHIPAMENTULUI UTILIZAT

Introducere

Există  un interes crescut pentru tehnologiile terrahertz în vederea utilizării asupra aplicațiilor în curs de dezvoltare precum scanarea în cadrul securitații aeroporturilor, echipamente de stingere a incendiilor pentru senzori de gaz, imagistică  medicală , aplicații farmaceutice, astronomie, comunicații, analize materiale și biologice.

Metodele electrice de detecție în gama terrahertz sunt de obicei împărțite în 2 mari categorii: metode de detecție coerente ( heterodyne ) și metode incoerente ( direct ).Dacă avem sub fmax, tranzistorii exercită un câstig de putere și circuitele bazate pe siliciu pot opera pană la 160-220 GHz având frecvența radio la o performanță rezonabilă. În cazul în care avem peste fmax, tranzistorii exercită o pierdere de putere, circuitele ar putea funcționa sub-armonic în aceeași masură ca și zona de funcționare a frecvenței radio.

În ciuda faptului că apare o creștere a cifrei zgomotului obținut, aceste circuite se dovedesc a fi utile în aplicațiile terrahertz în curs de dezvoltare.Spre deosebire de detecția heterodyne, cea incoerentă (direct) este mai indicată aplicațiilor multi-pixel.

Designul camerei de circuit.

Senzorii vizuali de imagine CMOS detectează fotonii prin intermediul efectului fotoelectric intern.Din moment ce siliciul cristalin este un semiconductor indirect acest proces presupune mai mult de un singur foton în procesul de absorție al acestora.Numai dacă energia fotonului este sufficient de ridicată, stimulează un electron din zona de desertare a fotodiodei, obținându-se astfel un electron liber ( și o gaură de electroni încărcată pozitiv ).Eficiența senzorilor vizuali ai imaginilor este dată de eficiența cuantică QE (λ) care depinde de lungimea de undă si descrie numărul de electroni generați si colectați per foton.Pentru CMOS, eficiența cuantică este de aproximativ 60% la 700 nm.

Din păcate, la frecvențele terrahertz ( 0.3 – 3 THz sau 0.1 – 1mm ) energia per foton este de aproximativ de 3 ori mai scăzută decât în spectrul vizual ( 400 – 789 THz sau 380 – 750 mm ), de exemplu =4 meV la 1 THz.Prin urmare, efectul fotoelectric intern nu se aplică, si mulți alți fotoni sunt nevoiți să creeze un singur electron, care scade în mod substanțial eficiența cuantică. În analogie cu detectorii vizuali, această eficiență pentru un “square-law detector” este legată de un detector curent responsabil Ri :

care depinde de energia fotonică, produsul dintre constanta lui Planck și frecvența unghiulară dar și de sarcina elementară qe.Un detector terrahertz care acumulează aceeași reactivitate de curent Ri ca și un detector de fotodiode, va obține o eficiență cuantică de 0.06% la 1THz. În aceste condiții procesul rezistiv mixt de distribuție avand un Ri tipic de 2.5mA/W asigură o eficiență cuantică de aproape 0.001%.Aceasta ne demonstrează că din cauza unei porțiuni mici de încărcări acumulate, un circuit de ieșire de zgomot redus al camerei terrahertz este necesar și totodată provocator de proiectat.Următoarea secțiune descrie în detaliu circuitul proiectat al camerei într-un proces tehnologic de 65 nm CMOS.

Arhitectura senzorilor camerei.

Senzorii convenționali de imagine ai CMOS-ului pentru spectrul vizual tipic utilizează un detector fotodiodic și necesită un tranzistor separat de reset.Spre deosebire de aceasta, schema circuitului de citire utilizează tranzistori detectori NMOS pentru a reseta sarcinile acumulate.

In Figura 1 avem diagrama bloc a camerei.Fiecare pixel activ constă într-un detector în bandă largă, un circuit de reset, un condensator de integrare și un pixel “blind” pentru compensare, ambele urmate de un amplificator diferențial.Fiecare line a vectorului la un moment dat este avantajată iar coloanele sunt în mod consecutiv selectate de un decoder de linie/coloană care este controlat de un dispozitiv logic programabil (CPLD) aflat în interiorul modulului camerei.Semnalele multiplexate ale vectorului pot fi citite diferențiat înainte ca un buffer amplificat aflat pe un chip să o facă ulterior.Chip-ul camerei este ambalat într-un modul compact cu un convertor analogic-digital extern (ADC) alimentat prin intermediul unui USB.

Figura 1: Diagrama bloc a chip-ului camerei.

Figura 2: Schema singulară terrahertz mixtă cu antenă sonoră și circuit de reset.

Detector față-spate și circuitul de reset.

Detectorul fată-spate este alcătuit dintr-un chip antenă sonoră după cum se poate vedea și în Figura 2, alimentând o pereche de detectori diferențiali NMOS permițand detecția în bandă largă.

Antena asigură o impedanță complex conjugată care să se potrivească atât cu tranzistori de tipul RF NMOS de 1µm lătime bine izolați și putere mică cât și cu tranzistori cu un prag scăzut cu o poartă minimă de 60 nm.Tranzistorul detector poate fi văzut ca o sursă de curent în paralel a lui M1 și a condensatorului integrator Cint ( Figura 2 ).

Prin urmare, timpul constant de integrare/reset poate fi controlat de nivelul de voltaj al semnalului de reset aplicat la poarta M1.Camera a fost proiectată pentru 25 fps.Deși lasă un timp suficient de mare pentru integrare ( 40 ms per frame ), integrarea necesară condensatorului ar fi prea mare pentru a fi integrata pe chip.Zona disponibilă pixelilor trebuie să aibă un condensator de integrare Cint=8 pF și un timp de integrare constant de aproximativ 0.1 µs.

Proiectarea fizică a antenei de pe chip este afișată în Figura 3. Este realizat din cupru în 7 straturi “back-end-of-the-line”(BEOL) și proiectat să asigure operații în bandă largă în timp ce alimentează o lentilă din siliciu emisferică foarte rezistivă prin spatele a 150 µm grosime și 15 Ωcm substrat în mare parte din siliciu.

Figura 3: Geometria metal-nivel a unui singur pixel în vector.Dimensiunile de ieșeire ale metalului arătat ce se află în jurul antenei sonore sunt de 80µm x 80µm și definesc pasul pixelului în vector.

Circuitul de ieșire.

Conform termenilor circuitului de ieșire, principalul scop este acela de a acumula nivele scăzute de putere consumată.Prin urmare senzorii pasivi ai pixelilor sunt de preferat, dar semnalul provenit de la circuitul de detecție este prea mic și tensiunea în modul de citire este necesar să fie determinată de o impedanță mare, facând-o pasibilă de a comuta zgomotul în canalul de ieșire.Prin urmare un circuit activ de pixeli asigură o imunitate mai bună la zgomot și o amplificare “in-pixel”.

În figura 4 găsim schema circuitului unei parți active a circuitului pixel.O linie selectează semnalul care va fi împărțit unei serii de linii de pixeli, în timp ce semnalul Col este împărțit la rândul lui la o serie de coloane de pixeli.Tranzistorul M1 este urmat de o pereche de tranzistori de citire M3/M4 care acționează ca o pereche diferențială având un circuit compensatoriu de offset (“blind reference pixel”).Circuitul “blind reference pixel” nu este conectat la o antenă, deci prin urmare este folosit pentru a produce un potențial de referință compensatoriu offset pentru perechile diferențiale ce opereză în buclă deschisă.Poarta bias a perechii de tranzistori M3/M4 este alimentată de Vant.Această tensiune este aplicată fie prin intermediul pixelului activ, fie prin “blind reference pixel”. În cazul lui M3, tensiunea bias se aplică mai târziu prin nodul comun de la antenă.

Figura 4: Circuitul pixel cu detector, circuit blind detector și un stagiu diferențial “cascode”.

Figura 5: Circuitul pixel-selection al matricei de linii și coloane.

Implementarea matricei și schema circuitului.

Figura 5 prezintă diagrama bloc a unitații de selectare digitală.Selecția liniilor și coloanelor se realizează folosind adrese pe 5 biți.O singură linie este “biased up” la un anumit moment dat iar perechile diferențiale de pe fiecare coloană împart o sarcină activ-comună (M6-M7) furnizănd o simulare de buclă deschisă având un câstig de 50 dB per pixel.Un multiplexor digital selectează un singur pixel pentru a fi “buffered” de un amplificator “unity-gain”.Această schemă de citire permite operațiile paralele ai celor 1024 de pixeli, în timp ce circuitul de citire poate activa o singură linie (32 elemente).

Designul camerei.

Camera terrahertz prezentată în figura 6 este asamblată într-o cutie metalică de 5 x 5 x 3 cm3 . Este conectată la o placă de achiziții de date prin intermediul unui cablu cu 8 fire RJ45.Este alcatuită dintr-o lentilă de silicon atasată în partea din spate a chip-ului, un controller de citire (ROC) implementat pe un dispozitiv complex programabil logic de control (CPLD) condus de un generator de ceas (CLK), un amplificator de câstig variabil pentru zgomote reduse (VGA) și o sursă de putere reglementată precum cea din figura 7.

Figura 6: Camera terrahertz cu și fără carcasă.

Figura 7: Diagrama bloc a modulului camerei care indica controller-ul de citire al camerei (ROC) si circuitul analogic de buf se realizează folosind adrese pe 5 biți.O singură linie este “biased up” la un anumit moment dat iar perechile diferențiale de pe fiecare coloană împart o sarcină activ-comună (M6-M7) furnizănd o simulare de buclă deschisă având un câstig de 50 dB per pixel.Un multiplexor digital selectează un singur pixel pentru a fi “buffered” de un amplificator “unity-gain”.Această schemă de citire permite operațiile paralele ai celor 1024 de pixeli, în timp ce circuitul de citire poate activa o singură linie (32 elemente).

Designul camerei.

Camera terrahertz prezentată în figura 6 este asamblată într-o cutie metalică de 5 x 5 x 3 cm3 . Este conectată la o placă de achiziții de date prin intermediul unui cablu cu 8 fire RJ45.Este alcatuită dintr-o lentilă de silicon atasată în partea din spate a chip-ului, un controller de citire (ROC) implementat pe un dispozitiv complex programabil logic de control (CPLD) condus de un generator de ceas (CLK), un amplificator de câstig variabil pentru zgomote reduse (VGA) și o sursă de putere reglementată precum cea din figura 7.

Figura 6: Camera terrahertz cu și fără carcasă.

Figura 7: Diagrama bloc a modulului camerei care indica controller-ul de citire al camerei (ROC) si circuitul analogic de buffering.

Prezentarea software-ului utilizat.

Limbajul C.

C/C++ este un limbaj de programare de uz general printre altele este un limbaj orientat pe obiecte. Realizează în esență o mapare a instrucțiunilor în limbaj de asamblare într-un set de cuvinte cheie și funcții. Aceste avantaje îl fac unul dintre cele mai utilizate limbaje de programare din toate timpurile.

Directiva #include specifică pre-procesorului să trateze continutul fișierelor specificate ca și cum ar apărea în programul curent acolo unde acestea sunt întalnite. Fișierele utilizate sunt: stdio.h(standard input output library) folosește așa-numitele streamuri care realizează o interfațare cu dispozitive fizice cum ar fi tastatura, imprimanta sau terminale, dar și cu alte fișiere suportate de sistemul de operare. Stdlib.h(Standard General Utilities Library) definește o serie de funcții de uz general pentru generarea numerelor aleatoare, aritmetica numerelor întregi, căutare, sortare și conversii de format, dar cel mai important managementul dinamic al memoriei( malloc(), free(), realloc()). String.h definește o serie de funcții utilizate pentru manipularea șirurilor alfanumerice și a vectorilor. Math.h definește o serie de funcții utilizate pentru operații matematice. Directiva #define creează un macrou care asociază în cazul nostru unui identificator, o parametrizare.

Struct este o declarare a unui tip complex de date, care permite definirea de către programator care definește fizic o listă grupată de variabile să fie plasată în memorie sub un singur nume, aceste variabile putând fi accesate ulterior printr-un singur pointer.

Limbajul C permite utilizarea pointerilor, un tip de referință care înregistrează adresa sau locația unui obiect sau a unei funcții în memorie. Pointerii pot fi manipulați utilizând operații aritmetice de adunare, scădere sau înmulțire. Alocarea dinamică a memoriei este realizată cu ajutorul acestor pointeri. Vectorii de obicei au dimensiune fixă, specificată încă de la declararea variabileor, cu toate acestea pot prin alocarea dinamică a memoriei se poate evita această restricție, prin utilizarea de exemplu a funcției malloc(). Trebuie însă avută grijă sa nu se depășească dimensiunile acestor vectori, deoarece nu există nici un mecanism de restricție, iar această operație ilegală poate avea repercursiuni grave. Utilizarea pointerilor poate fi utilizată alternativ cu cea a vectorilor astfel x[i] unde x este pointer, este o formă sintactică pentru *(x+i).

Una dintre cele mai importante funcții ale unui limbaj de programare este acela de a furniza unelte pentru managementul memorie. În limbajul C memoria poate fi alocată în principal în 3 moduri:

Alocare statică a memoriei – locațiile de memorie sunt alocate în fișierul .bin în momentul compilării programului. Obiectele astfel create au durata de viață atâta timp cât fișierul .bin este încărcat în memorie.

Alocarea automată a memoriei – obiecte temporare sunt încărcate într-o stivă, spațiul fiind automat eliberat atunci când se iese din blocul de comenzi, memoria putând fi reutilizată

Alocarea dinamică a memoriei – blocuri de memorie de dimensiuni arbitrare sunt alocate în timpul rulării programului dintr-o zonă de memorie numită heap, până la reutilizare sau eliberare.

SEGMENTAREA IMAGINILOR UTILIZÂND DIFERIțI ALGORITMI

Introducere.

Se pune problema segmentării unei imagini în diferite regiuni.Analizăm rezultatele obținute cu algoritmii K-means și EM iar apoi comparăm cu un algoritm bazat pe grafice numit Normalized Cut Algorithm. K-means și EM sunt algoritmi ai mulțimilor care împart un set de date în clase diferite pe baza unor criterii de măsurare a distanței.

Imaginile sunt considerate un mediu foarte important de transfer a informațiilor.Înțelegerea și extragerea informațiilor din ele este o sarcină importantă în înțelegerea funcționării masinilor.Un exemplu în acest caz ar fi utilizarea imaginilor în deplasarea roboților.Alte aplicații pot fi din domeniul medicinii cum ar fi de exemplu segmentarea scanărilor medicale a țesuturilor bolnave.Unul din primii pasi pentru a ințelege informațiile din imagini este acela de a le segmenta și de a găsii diverse obiecte în ele.Pentru a realiza acest lucru se poate folosii reprezentarea grafică a histogramei și transformata în frecvența în domeniu.

Există 3 tipuri de algoritmi în procesul de segmentare și o comparație pentru a determina algoritmul ideal: Clusterul K-means, Expectation Maximization (EM) și Normalized Cuts.Comparația are la bază varietatea de erori metrice și complexitatea timpului fiecărui algoritm.Se presupune că numărul de segmente al unei imaginii se cunoaște și prin urmare poate fi trecut prin algoritm.

Algoritmi de segmentare ai imaginilor.

Imaginile pot fi segmentate în regiuni prin următorii algoritmi:

Algoritmul K-Means.

Este un algoritm care clasifică punctele datelor de intrare în clase multiple bazate pe distanța intrinsacă dintre ele.Algoritmul presupune că trăsăturile datelor de intrare alcătuiesc un vector și încearcă să le ordoneze în mulțimi ăîtr-un mod natural.Punctele se grupeaza în mulțimi în jurul centroidelor care sunt obținute prin minimizarea obiectivului

unde sunt k clase Si i=1,2,…,k și µi este centroida tuturor punctelor xj ϵ Si

O versiune iterativă a algoritmului a fost implementată, aceasta având nevoie de o imagine 2D ca dată de intrare.Pasii algoritmului sunt următorii:

1.Calculul histogramei imaginii.

2.Inițializarea centroidelor cu un număr aleatoriu k de puncte.

3.Se repetă următorii pași până cand etichetele claselor imaginii nu se mai modifică.

4.Se grupează punctele în clase pe baza distanței dintre centroida inițială și punctele respective.

5.Se calculează noile centroide pentru fiecare clasă în parte.

Algoritmul EM.

Expectation Maximization(EM) este unul dintre cei mai comuni algoritmi utilizați pentru estimarea punctelor.Algoritmul se bazează pe găsirea probabilității maxime în estimarea parametrilor atunci când modelul de date depinde de un anumit set de variabile latente.În cadrul acestui algoritm, pașii alternativi E (Expectation) și M (Maximization) au loc într-o manieră iterativă până când rezultatul converge.Pașii E calculează perspectiva probabilității pe baza includerii variabilelor latente așa cum ar trebui să fie observate și un pas de maximizare M, care calculează probabilitatea maximă de estimare a parametrilor prin maximizarea probabilității obținute de la ultimul pas E.Parametrii obținuți în urma pașilor M sunt utilizați apoi pentru a începe un nou pas E, și procesul continuă până la convergență.

Din punct de vedere matematic, pentru un anumit set de date și un model unde z este o variabilă latenta.Vom avea:

Din ecuția de mai sus, probabilitatea logaritmică este descrisă în funcție de x,z,Ѳ.Dar cum variabila latentă z este necunoscută vom folosii aproximarea în schimb.Aceste aproximări iau forma pașilor E si M menționați mai sus și vom obține:

Pașii E, pentru fiecare i:

Pașii M, pentru toți z:

unde Qi este distribuția posterioară a lui z(i) cunoscând x(i).

În mod conceptual algortimul EM poate fi considerat o variantă a algoritmului K Means unde membrii oricărui punct apropiat clasei nu este complet și poate fi fracțional.

Algoritmul Normalized Cut.

Segmentarea imaginilor poate fi vazută de asemenea și ca o partiționare optimă a unui graf.Imaginea este prezentată sub forma unui graf neorientat ponderat G=(V,E).Graful imaginii poate fi împarțit în 2 subgrafuri A si B modelând fiecare partiție prin minimizarea “tăieturii” după cum urmează:

unde w(i, j) este o funcție de similaritate între nodurile i și j.Oricum criteriul minim de tăiere favorizează seturi mici de tăiere ale nodurilor izolate.Putem folosii de asemenea o funcție modificată “Normalized Cut” precum cea definită mai jos:

Variabila assoc(A, V) reprezintă toate conexiunile nodului A cu celelalte noduri ale grafului.

Valoarea Ncut nu va fi mică pentru regiunea care cuprinde punctele izolate deoarece valoarea regiunii va reprezenta un procentaj mare din totalul conexiunilor unui set către celelalte.

Fiind dată o partiție a unui graf V care are 2 seturi disjuncte și complementare A și B, fie x un vector dimensional de indicație N = |V|; xi = 1 dacă nodul i se afla în A, -1 în caz contrar.Fie di = Σj W(i, j) număr total de conexiuni de la nodul I către toate celelalte noduri.Găsirea optimului global se va reduce pana la:

cu condiția si să fie egale cu 0.

Algoritmul de grupare.

Vectorul propriu corespunzător celui de-al doilea cel mai mic vector propriu este valoarea reală care sub-partiționează întregul graf, a treia cea mai mică valoare este soluția optimă de partiționare a primei părti în alte două și așa mai departe.Algoritmul de grupare are următorii pașiȘ

Fiind dată o imagine se construiește graful corespunzător G(V,E) prin considerarea fiecărui pixel a câtui un nod și legarea acestuia de o margine.Importanța fiecărei margini ar trebui sa reflecte probabilitatea ca doi pixeli să aparțină aceluiași obiect.Folosind doar valoarea luminozității pixelului si locația in spațiu putem definii marginile grafului prin conectarea a două noduri i si j precum:

în caz contrar w(i,j) este zero.

Se rezolvă (D-W)y = λDy pentru vectorii proprii cu cele mai mici valori proprii.

Se folosește vectorul propriu cu cea mai mică valoare proprie pentru a bipartiționa graful prin găsirea punctelor de diviziune la fel ca și în cazul minimizării N cut.

Se repatiționează în mod recursiv părțile segmentate (primul pas).

Se termina algoritmul dacă pentru fiecare segment N cut este mai mare decât o valoare prestabilită.

Rezultate.

Am aplicat algoritmii de partitionare imaginilor în nuanțe de gri.Rezultatele segmentării făcute pe imagini diferite cu fiecare algoritm în parte pentru diferite valori ale lui k sunt prezentate înfigurile 1, 2, 3 și 4.

Figura 1 Imaginile Originale

Figura 2 Expectation Maximization

Figura 3 K-Means

Figura 4 Normalized Cut

BINARIZAREA IMAGINILOR

Introducere

O imagine digitală este o colecție discretă de puncte (numite pixeli) aranjate pe un număr întreg bine definit de linii și coloane. Fiecare pixel este descris fie prin culoarea sa (în cazul imaginilor color), fie prin luminanța sa (în cazul imaginilor pe nivele de gri). În cel de-al doilea caz, fiecare pixel din imagine se poate descrie printr-un număr întreg pozitiv finit, proporțional cu luminozitatea scenei în poziția spațială corespunzătoare pixelului din imagine.

Din această definiție rezultă că orice imagine digitală poate fi reprezentată matematic sub formă matricială.Numărul de linii din matrice va fi numărul de linii al imaginii digitale (cunoscut și sub termenul de înălțimea imaginii), iar numărul de coloane ale matricii este numărul de coloane din imaginea digitală (cunoscut și sub termenul de lățimea imaginii). Dacă, pentru simplitatea abordării, ne referim aici doar la cazul imaginilor pe nivele de gri, atunci elementele matricii care reprezintă imaginea digitală vor fi valori întregi pozitive, și anume – luminanțele pixelilor din imaginea digitală.

Prelucrările punctuale (numite și prelucrări la nivel de pixel) ale imaginilor pe nivele de gri reprezintă, din punct de vedere matematic, cea mai simplă categorie de algoritmi care pot fi folosiți pentru prelucrarea (modificarea) unei imagini digitale. Aceste prelucrări sunt folosite în domeniu de mult timp si stau la baza celor mai complexe tipuri de prelucrări de imagini.

Prelucrările punctuale (prelucrările la nivel de pixel) cuprind o clasă de algoritmi de prelucrare a imaginilor în care culoarea sau luminanța (nivelul de gri al ) fiecărui pixel din imaginea rezultată prin prelucrare depinde doar de culoarea sau luminanța pixelului plasat în aceeasi poziție spațială în imaginea inițială. Algoritmii de prelucrare punctuală sunt bazați în general pe un aparat matematic simplu. De obicei, prelucrarea punctuală este realizată printr-o transformare

liniară sau neliniară a domeniului de variație a culorii sau a luminanței pixelilor din imaginea inițială, care determină noul

domeniu de variație a culorii sau luminanței pixelilor în imaginea rezultată prin prelucrare (acelasi sau altul decât în imaginea inițială). Această transformare liniară sau neliniară este specificată uzual fie grafic, fie analitic.

Histograma imaginilor

Vom începe discuția despre histogramele imaginilor cu cazul cel mai simplu, și anume cel al imaginilor digitale pe nivele de gri. Generalizarea conceptului de histogramă la imagini color este directă: pentru o imagine color, definim histogramele color, care – ținând cont de faptul că pentru reprezentarea culorii avem în general nevoie de trei componente – reprezintă un caz mai complex decât histograma imaginii pe nivele de gri, unde "culoarea" fiecărui pixel este pur și simplu luminanța sa, deci este reprezentată printr-o singură valoare.

Histograma unei imagini digitale pe nivele de gri indică distribuția cantitativă a pixelilor din imaginea digitală pe nivelele de gri din imagine. Un alt mod de interpretare a histogramei imaginii pe nivele de gri este ca o reprezentare a numărului de apariții al fiecărui nivel de gri în imaginea digitală respectivă. Histograma furnizează o descriere globală a imaginii și ajută la identificarea diferitelor componente cum ar fi fundalul, diferitele obiecte sau zgomote din imagine. Histograma nivelelor de gri a unei imagini digitale reprezintă una dintre cele mai simple modalități de descriere a conținutului informațional al imaginii.

Există 3 tipuri de histogramă pe care le vom definii mai jos.

Histograma liniară

Definim histograma liniară (sau, pe scurt, histograma) imaginii digitale pe nivele de gri U cu domeniul de variație al nivelelor de gri L cu valori între 0 și 255, ca fiind funcția cu valori întregi pozitive Hliniar,

Hliniar : L ->{0,1,…,M × N}, dată de expresia:

Hliniar (k) = nk , "k = 0,1,…,255

unde nk este numărul de pixeli din imaginea digitală U care au nivelul de gri egal cu k:

nk = Card{u(i, j)u(i, j) = k, "i =1,2,…,M, "j = 1,2,…,N}, "k = 0,1,…,255.

În ecuația de mai sus, semnificația operatorului Card este următoarea: dacă S este o mulțime oarecare finită, atunci Card(S) este cardinalul mulŃimii S, adică, numărul de elemente din mulțimea S.

Histograma cumulativă

Histograma cumulativă a unei imaginii U este definită prin funcția cu valori pozitive întregi Hcumulativ ,

Hcumulativ : L -> {0,1,…,M × N},dată de expresia:

unde nl este numărul de pixeli din imaginea digitală U al căror nivel de gri este l. Astfel, valoarea histogramei cumulative în nivelul de gri k, Hcumulativ(k), reprezintă numărul de pixeli din imaginea digitală U care au nivelul de gri mai mic sau egal cu k, pentru orice k ϵ L.

Histograma cumulativă normalizată

Aceasta se definește în manieră similară histogramei liniare normalizate. Ea se obține raportând valorile funcției histogramă cumulativă Hcumulativ(k), k ϵ L , la numărul total de pixeli din imaginea digitală U, n=M×N. Descriem histograma cumulativă normalizată prin funcția densitate de probabilitate Pcumulativ, Pcumulativ : L -> [0,1], dată de expresia:

Tehnici de îmbunătățire a imaginilor

Accentuare de contrast

Această tehnică de îmbunătățire este necesară în cazul imaginilor cu un contrast scăzut, datorat unei iluminări slabe sau prea puternice. Funcția matematică utilizată în acest caz este:

Parametrii a si b se obțin prin examinarea histogramei imaginii. Parametrii α, β si y determină gradul de accentuare a contrastului.

Figura 1: Funcția accentuare de contrast

Limitarea și binarizarea imaginilor

Limitarea imaginilor este un caz particular de accentuare de contrast cu a = g = 0 :

Metoda este folositoare în cazul atenuării zgomotului când acesta este în domeniul [a,b].

Binarizarea este un caz particular de limitare când a=b=t, obținându-se o imagine care va avea după prelucrare numai două nivele de gri.

Figura 2: Exemple de limitare și binarizare

Algoritmi de binarizare.

Se pot aplica pe orice tip de document.

Acestia clasifica pixelii în 2 categorii.

Prima formată din pixelii cu o proprietate măsurabilă ce are valoarea sub un anumit prag.

A doua formată din pixelii care au această proprietate are o valoare egală sau mai mare decât acest prag.Aceștia creează o imagine binară.

Alegerea pragului este o operație critică.

Metode de binarizare

AGB – P – tile thresholding

Folosim histograma cumulativă:

Pragul T verifică ecuția:

Pentru obiecte cu luminozitate scazută (dark foreground)

Pentru obiecte cu luminozitate ridicată (bright foreground)

AGB – Optimal thresholding

Histograma unei imagini este suma a două distribuții care se suprapun.

Pragul optim: punctele din aceste distribuții care se suprapun (corespund probabilității minime dintre maximele celor două distribuții).

Problema: distribuțiile sunt necunoscute.

Optimal thresholding – Metoda Otsu

Otsu este un algoritm global de binarizare ce folosește clusterizarea

Metoda de evaluare a calității clusterelor

Entropia

Puritatea

Separea intra-clustere

Se caută o valoare de prag T, astfel încât varianta în cadrul claselor să fie minimă.

σ2w(t) = σ2w(t) + σ2b(t) unde σω(t) probabilitatea ca un pixel să fie alb.

σb(t) probabilitatea ca un pixel sa fie negru.

Ponderile:

ωb(t) = , ωw(t) =

• Media claselor:

µw(t) = µb(t) =

Varianta totală

σ2(t) = σ2w(t) + σ2b(t)

σ2(t) = σ2

(varianta totală nu depinde de t)

a minimiza σ2w(t) = a maximiza σ2b(t)

σ2b(t) = ωw(t) ωb(t) [μw(t) – μb(t)]2

Algoritmul:

calculează histograma

ωa(0) = 0, ωn(0) = 0

for t = 1 .. n

a. recalculează ωa(t), ωn(t)

b. recalculează µa(t), µn(t)

c. calculează σ2b(t)

t căutat este cel care corespunde valorii maxime σ2b(t)

Avantaje

Destul de rapid.

Ușor de implementat.

Rezultate foarte bune dacă cele două clase au dimensiuni comparabile.

Dezavantaje

Sensibil la dimensiunea obiectului.

dimensiunea obiectului din foreground este mult mai mare sau mai mică decât background-ul.

Sensibil dacă părți ale obiectului au nuantă apropiată de culoarea background-ului

pixeli clasificați incorect

Algoritmul k-mEANS

Cluster.

Clustering-ul este o tehnică de învățare nesupervizată, care determină o structură intrisecă într-o mulțime de date.Această metodă este un proces de organizarea obiectelor,care sunt asemănatoare (similare) dintr-un punct de vedere.

Cluster-ul este o mulțime de obiecte asemănătoare între ele și diferite de obiectele aparținând altui cluster.Putem vorbi despre clustering,bazat pe o anumită distanța în sensul că avem următorul criteriu de similaritate:

“Două sau mai multe obiecte aparțin aceluiași cluster dacă sunt foarte apropiate,relative la distanța considerată”

În clusterul conceptual,obiectele sunt grupate în același cluster dacă au aceeași proprietate, un cluster fiind definit de acea proprietate (concept).

5.1.1.Probleme rezolvabile utilizând clustering-ul

Reducerea datelor (“data reduction”), gâsind reprezentanții unui grup omogen;

Determinarea unor clase convenabile (“useful data classes”);

Determinarea unor clustere natural și descrierea proprietaților lor necunoscute (“natural data types”);

Găsirea unor obiecte mai rar întâlnite (“outlier detection”)

5.1.2.Aplicații

Marketing, pentru găsirea grupurilor de client cu profil asemănător, pe baza unei baze de date a acestor clienți, cu atributele lor și cumpărăturile lor anterioare;

Biologie, pentru clasificarea plantelor și animalelor;

Asigurări, pentru identificarea clienților ce prezintă riscuri mari și pentru identificarea fraudelor;

Biblioteci, pentru ordonarea cartilor după anumite criterii;

Internet, pentru împărțirea documentelor în funcție de tematică.

5.1.3.Măsura de similaritate

Poate fi considerată ca fiind o metrică definită pe o anumită mulțime M.Este aleasă în concordanță cu tipul de date cu care se lucrează și cu scopul propus.

O bază de date formată din m vectori linie, n-dimensionali x1,…,xm poate fi reprezentată ca fiind o matrice cu m linii și n coloane.Vom definii mai multe metrici (distanțe):

Distanța euclidiană

Distanța euclidiană standardizată

unde D este matricea diagonală ce are ca elemente dispersia vectorului , notată , adică :

Distanța city block

Distanța Minkowski

Se observă că:

daca p = 1 obținem distanța Manhattan

daca p = 2 obținem distanța euclidiană

K-Means.

Algoritmul K-means (Mac Queen, 1967) clasifică o mulțime de n obiecte într-un număr k dat apriori de clustere.

– alegem aleator k puncte în spațiul definit de obiectele din baza de date, ce urmează a fi clausterizate.Acestea sunt centroizii inițiali.De obicei încercăm să îi plasăma cât se poate de departe unul de altul.

– asociem fiecare obiect din mulțimea de date celui mai apropiat centroid ( în sensul distanței considerate), obținând astfel un prim grupaj.

– calculăm centrele de greutate ale clusterelor obținute, definind astfel noii centroizi.

– reluăm procedeul și astfel cei k centroizi își vor schimba locul pas cu pas, până ajung în poziția dorită.

În final, algoritmul urmărește minimizarea funcției obiectiv .

unde este distanța aleasă între punctul din baza de date și centroidul al clusterului .

Funcția obiectiv, care este în acest caz funcția erorii pătratice, este un indicator al distanței dintre cele n puncte din baza de date și centrele clusterelor corespunzătoare.

Probleme care pot apărea în cadrul aplicării algoritmului:

Algoritmul nu gasește întotdeauna configurația optimă, corespunzătoare minimului global al funcției obiectiv.

Algoritmul este minuțios în alegerea inițială a centroizilor.

Pentru reducerea acestor efecte se rulează de mai multe ori algoritmul.

Exemplu.

Presupunând că avem 4 obiecte ca date de puncte de formare și fiecare obiect are 2 atribute.Fiecare atribut reprezintă coordonatele unui obiect.

Astfel, știm că aceste obiecte aparțin 2 grupuri de tratament (clasa 1 și clasa 2).Acum problema este să determinăm care tratament aparține clasei 1 și care tratament aparține celeilalte clase.Fiecare tratament este un punct cu 2 componente drept coordonate.

Exemplu numeric:

Pasul de bază al claselor k-means este simplu.La început, trebuie să determinăm numărul de clase K și să asociem fiecărei clase o centroidă (centru).Putem alege aleatoriu oricare obiect ca centroidă inițială sau primele K clase pot fi folosite ca centre inițiale.

Apoi algoritmul K-mean va face următorii 3 pași de mai jos până la convergență:

1.Determină coordonatele centroidelor.

2.Determină distanța de la fiecare obiect până la centroidă.

3.Grupează obiectele în funcție de distanța minimă.

Exemplul numeric de mai jos este pentru a ințelege această simplă iterație.

Sa presupunem că avem câteva obiecte ( 4 tipuri de tratament ) și fiecare obiect are 2 atribute sau trăsături cum sunt prezentate în tabelul de mai jos.Scopul nostru este să grupăm aceste obiecte în K=2 grupe de tratament bazat pe cele 2 caracteristici (pH și greutate).

Fiecare tratament reprezintă un punct cu 2 caracteristici ( X, Y ) pe care le putem prezenta ca și coordonate într-o caracteristică spațială cum e prezentată în figura de mai jos.

1.Valorile inițiale ale centroidelor: Să presupunem că folosim tratamentul A și tratamentul B ca centroide inițiale.Fie c1 și c2 coordonatele centroidelor.Astfel c1=(1,1) și c2=(2,1)

2.Distanța obiect-centroidă: calculăm distanța de la centrul clasei până la fiecare obiect.Vom folosi distanța euclidiană; astfel vom avea matricea distanțelor la pasul 0 următoarea:

Fiecare coloană din matricea distanțelor reprezintă un obiect.Prima linie din matricea distanțelor corespunde distanței de la fiecare obiect la prima centroidă și cea de-a 2-a linie este distanța de la fiecare obiect la a 2-a centroidă.De exemplu, distanța de la tratamentul C=(4,3) la prima centroidă c1=(1,1) este , și distanța până la cea de-a 2-a centroidă c2=(2,1) este .

3.Clasarea obiectelor: Alocăm fiecare obiect în funcție de distanța minimă.Astfel, tratamentul A este atribuit clasei 1, tratamentul B este atribuit clasei 2, tratamentul C clasei 2 și tratamentul D tot clasei 2.Elementele clasei matricelor de mai jos este 1 dacă și numai dacă acest obiect este atribuit acelei clase.

4.Iterația 1: Determinarea centroidelor: Cunoscând membrii fiecărei clase putem evalua noile centroide ale fiecărei clase bazate pe acești noi membri.Clasa 1 are un singur membru astfel centroida rămâne c1=(1,1).Clasa 2 are 3 membri astfel centroida este media coordonatelor celor 3 membri:

5.Iterația 1, distanța obiect-centroidă: Următorul pas este să calculăm distanța tutoror obiectelor până la noile centroide.Similar pasului 2 avem matricea distanțelor de la pasul 1 următoarea:

6.Iterația 1, clasarea obiectelor: Similar pasului 3, atribuim fiecare obiect pe baza distanței minime.Bazându-ne pe noua matrice a distanțelor :

7.Iterația 2, determinarea centroidelor: Acum repetăm pasul 4 pentru calculul coordonatelor noilor centroide bazându-ne pe iterația anterioară.Atât clasa 1 cât și clasa 2 au 2 membri, astfel noile centroide sunt

și .

8.Iterația 2, distanța obiect-centroidă: Se repetă pasul 2, avem o nouă matrice a distanțelor:

9.Iterația 2, clasarea obiectelor: Din nou, atribuim fiecare obiect bazat pe distanța minimă.

Obținem faptul că .Comparând gruparea ultimei iterații observăm că obiectele nu se mai grupează.Astfel, calcularea claselor k-mean și-a atins stabilitatea și nu mai este nevoie de o nouă iterație.Vom avea în final următoarea grupare:

.Cum funcționează algoritmul K-mean?

Dacă numărul de date este mai mic decât numărul de clase pe care le atribuim, fiecare dată este aleasă ca centroidă a clasei.Fiecare centroidă va avea numărul clasei.Dacă numărul de date este mai mare decât numărul de clase, pentru fiecare dată, calculăm distanța la toate centroidele și obținem minimul distanței.Această dată aparține clasei care are distanța minimă față de data respectivă.

Dacă nu suntem siguri despre locația centroidei, vom ajusta locația acesteia bazându-ne pe actualizarea datelor curente.Apoi vom atribui toate datele acestei noi centroide.Procedeul este repetat până când nici o dată nu se mai deplasează la o altă clasă.Din punct de vedere matematic această buclă s-a dovedit a fi convergentă.

Aplicatie k-means

Vom aplica Algoritmul K-Means asupra frame-urilor unui video realizat cu camera TerraHertz.

Mai jos sunt atașate un set de 12 imagini componente ale video-ului.

Codul programului aplicat frame-urilor:

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>

#define Nr_culori 256

//variabile globale lungimea si latimea imaginii

int height, width;

//structura in care se citeste header-ul imaginii bmp(24biti)

typedef struct

{

char type[2]; // tipul fisierului

unsigned int size;//numarul de octeti ai fisierului

unsigned short int res1,res2;//octeti rezervati pentru software

unsigned int offset; //offset-ul

}HEADER;

//structura pentru o culoare RGB[3]=[RED, BLUE, GREEN]

typedef struct

{

unsigned char RGB[3];

}RGB;

//structura informatii despre imagine

typedef struct

{

unsigned int size;//dimensiune octeti

int width,height;//dimensiune in pixeli

unsigned short int planes;

unsigned short int bpp;//bytes per pixel

unsigned int compression;//compresie

unsigned int imagesize;//dimensiunea imaginii

int xresolution,yresolution;//rezolutii

unsigned int colours;//culori

unsigned int impcolours;//culori importante

}IMAGE;

//calculeaza distributia initiala a centroidelor

void calcul(int k,int *group)

{

int i;

printf("Initial centers\n");

for(i=0;i<k;i++)

{

printf("Red: ");

scanf("%d",&group[3*i]);

printf("Green: ");

scanf("%d",&group[3*i+1]);

printf("Blue: ");

scanf("%d",&group[3*i+2]);

/*aux=i*pas;

group[3*i]=(i*pas)%256%256;

group[3*i+1]=((i*pas)%256)/256;

group[3*i+2]=(i*pas)%(256*256);*/

//printf("Center %d: %d %d %d",i+1,group[3*i],group[3*i+1],group[3*i+2]);

}

}

void dist(RGB **Matrix,int *group,int k, int *cluster)

{

int *distanta;

float min;

float x,y,z;

RGB tmp;

int i,j,t,ind,indice=0,n;

distanta=(int*) malloc(k*sizeof(int));

for(i=0;i<height;i++){

for(j=0;j<width;j++){

for(t=0;t<k;t++)

{

tmp=Matrix[i][j];

x=tmp.RGB[0]-group[3*t];

y=tmp.RGB[1]-group[3*t+1];

z=tmp.RGB[2]-group[3*t+2];

distanta[t]=sqrt(x*x+y*y+z*z);

}

min=distanta[0];

ind=0;

for(t=1;t<k;t++)

if(distanta[t]<min)

{

min=distanta[t];

ind=t;

}

cluster[indice]=ind;

indice++;

}

}

free(distanta);

int *r,*r1,*g,*g1,*b,*b1;

r=(int*) malloc(k*sizeof(int));

r1=(int*) malloc(k*sizeof(int));

g=(int*) malloc(k*sizeof(int));

g1=(int*) malloc(k*sizeof(int));

b=(int*) malloc(k*sizeof(int));

b1=(int*) malloc(k*sizeof(int));

for(i=0;i<k;i++)

{

r[i]=0;

r1[i]=0;

g[i]=0;

g1[i]=0;

b[i]=0;

b1[i]=0;

}

indice=0;

for(i=0;i<height;i++){

for(j=0;j<width;j++){

n=cluster[indice];

indice++;

tmp=Matrix[i][j];

r[n]=r[n]+tmp.RGB[0];

r1[n]++;

g[n]=g[n]+tmp.RGB[1];

g1[n]++;

b[n]=b[n]+tmp.RGB[2];

b1[n]++;

}

}

for(i=0;i<k;i++){

if(r1[i]!=0)

group[3*i]=r[i]/r1[i];

else

group[3*i]=0;

if(g1[i]!=0)

group[3*i+1]=g[i]/g1[i];

else

group[3*i+1]=0;

if(b1[i]!=0)

group[3*i+2]=b[i]/b1[i];

else

group[3*i+2]=0;

}

free(r);

free(r1);

free(g);

free(g1);

free(b);

free(b1);

}

//prototipurile functiilor utilizate

FILE* exist(char *name);

void isBMP(FILE* arq,HEADER head,IMAGE image);

IMAGE readInfo(FILE* arq);

RGB** createMatrix();

void loadImage(FILE* arq, RGB** Matrix);

void writeBMP(RGB **OutMatrix, HEADER head, FILE* arq, int *cluster, int *group);

void freeMatrix(RGB **Matrix,IMAGE image);

//functia main

int main(int argc, char** argv){

int i,j;

int k,ok=0,number=0;

int *cluster;

//group=(int*) calloc(3*k,sizeof(int));

//groupaux=(int*) calloc(3*k,sizeof(int));

printf("Number of colours:");

scanf("%d",&k);

int group[3*k],groupaux[3*k];

calcul(k,group);

for(i=0;i<k;i++)

{

groupaux[3*i]=group[3*i];

groupaux[3*i+1]=group[3*i+1];

groupaux[3*i+2]=group[3*i+2];

}

FILE *arq;

RGB **Matrix, tmp;

IMAGE image;

HEADER head;

char name[15];

printf("Type the image's name : ");

scanf("%s",name);

arq = exist(name);

isBMP(arq,head,image);

image = readInfo(arq);

height = image.height;

width = image.width;

cluster=(int*) malloc(height*width*sizeof(int));

Matrix = createMatrix();

loadImage(arq,Matrix);

while(ok==0){

dist(Matrix,group,k,cluster);

ok=1;

for(i=0;i<k;i++)

{

if(groupaux[3*i]!=group[3*i]||groupaux[3*i+1]!=group[3*i+1]||groupaux[3*i+2]!=group[3*i+2])

ok=0;

}

for(i=0;i<k;i++)

{

printf("%d %d %d\n",group[3*i],group[3*i+1],group[3*i+2]);

printf("%d %d %d\n",groupaux[3*i],groupaux[3*i+1],groupaux[3*i+2]);

}

if(ok==0)

for(i=0;i<k;i++)

{

groupaux[3*i]=group[3*i];

groupaux[3*i+1]=group[3*i+1];

groupaux[3*i+2]=group[3*i+2];

}

number++;

printf("Generatia: %d \n",number);

if(number>=100)

ok=1;

}

printf("Final centers:");

for(i=0;i<k;i++)

printf("%d %d %d\n",group[3*i],group[3*i+1],group[3*i+2]);

writeBMP(Matrix,head,arq,cluster,group);

free(group);

free(cluster);

free(groupaux);

return(0);

}

// verifica daca poate fi deschisa imaginea

FILE* exist(char *name)

{

FILE *tmp;

tmp = fopen(name,"r+b");

if (!tmp)

{

printf("\nERROR: Incorrect file or not exist!\n");

exit(0);

}

fseek(tmp,0,0);

return(tmp);

}

// verifica daca imaginea este format bmp 24 biti

void isBMP(FILE* arq, HEADER head, IMAGE image){

char type[3];

unsigned short int bpp;

fseek(arq,0,0);

fread(type,1,2,arq);

type[2] = '\0';

fseek(arq,28,0);

fread(&bpp,1,2,arq);

if (strcmp(type,"BM") || (bpp != 24)){

printf("\nThe file is not BMP format or is not 24 bits\n");

exit(0);

}

}

//citeste imaginea propriu-zisa din fisier

IMAGE readInfo(FILE* arq){

IMAGE image;

//Lungimea in pixeli

fseek(arq,18,0);

fread(&image.width,1,4,arq);

//Latimea in pixeli

fseek(arq,22,0);

fread(&image.height,1,4,arq);

// Color depth, BPP (bits per pixel)

fseek(arq,28,0);

fread(&image.bpp,1,2,arq);

//tipul de compresie

fseek(arq,30,0);

fread(&image.compression,1,4,arq);

//nr de bytes al imaginii

fseek(arq,34,0);

fread(&image.imagesize,1,4,arq);

//culori

fseek(arq,46,0);

fread(&image.colours,1,4,arq);

//numar de culori importante

fseek(arq,50,0);

fread(&image.impcolours,1,4,arq);

//returneaza informatiile despre imagine- structura image

return(image);

}

void loadImage(FILE* arq, RGB** Matrix){

int i,j;

RGB tmp;

long pos = 51;

fseek(arq,0,0);

for (i=0; i<height; i++){

for (j=0; j<width; j++){

pos+= 3;

fseek(arq,pos,0);

fread(&tmp,(sizeof(RGB)),1,arq);

Matrix[i][j] = tmp;

}

}

}

// crearea matricei pe baza imaginii

RGB** createMatrix(){

RGB** Matrix;

int i;

Matrix = (RGB **) malloc (sizeof (RGB*) * height);

if (Matrix == NULL){

perror("***** No memory available *****");

exit(0);

}

for (i=0;i<height;i++){

Matrix[i] = (RGB *) malloc (sizeof(RGB) * width);

if (Matrix[i] == NULL){

perror("***** No memory available *****");

exit(0);

}

}

return(Matrix);

}

// creare imaginii modificate

void writeBMP(RGB **Matrix, HEADER head, FILE* arq, int *cluster, int *group){

FILE* out;

int i,j;

int index;

RGB tmp;

long pos = 51;

char header[54];

fseek(arq,0,0);

fread(header,54,1,arq);

out = fopen("out.bmp","w");

fseek(out,0,0);

fwrite(header,54,1,out);

for(i=0;i<height;i++){

for(j=0;j<width;j++){

pos+= 3;

fseek(out,pos,0);

index=cluster[i*width+j];

tmp.RGB[0]=group[3*index];

tmp.RGB[1]=group[3*index+1];

tmp.RGB[2]=group[3*index+2];

//tmp = Matrix[i][j];

fwrite(&tmp,(sizeof(RGB)),1,out);

}

}

fflush(out);

fclose(out);

}

// eliberarea memoriei alocata matricei

void freeMatrix(RGB** Matrix, IMAGE image)

{

int i;

int lines = image.height;

for (i=0;i<lines;i++){

free(Matrix[i]);

}

free(Matrix);}

În urma rulării programului aceleași frame-uri vor devenii:

concluzii

În această lucrare am evidențiat utilitatea metodei de cuantizare vectorială k-means în prelucrarea numerică a semnalelor, în cazul nostru prelucrarea frame-urilor obținute în urma partiționării filmului realizat cu camera TerraHertz, precum și avantajele acestei metode în comparație cu alți algoritmi existenți: normalized cut și algoritmul EM. Algoritmul k-means are o precizie ridicată în comparație cu ceilalți doi algoritmi amintiți mai sus, precizie realizată cu costul vitezei de execuție și al memoriei utilizate.

Am implementat algoritmii EM și K-means.Pentru valori mici ale lui k, algoritmii dau rezultate bune.Pentru valori mai mari, segmentarea devine mai greoaie, multe clustere apar în imagini în locuri discrete.Acest lucru se întâmplă din cauza faptului că distanța euclidiană nu reprezintă cea mai bună metrică în procesul de segmentare.

Pentru valori mai mari ale lui k se recomandă algoritmii bazați pe graf-uri precum NCut.O diferență de bază între algoritmii N Cut și cei pe bază de clustering este aceea că cel din urmă consideră pixelii cu valori de intesitate relativ apropiate aparținând unui singur segment.N cut consideră asemenea regiuni ca fiind segmente separate.Metoda valoriilor proprii durează mai mult în cazul imaginii la scală originală; astfel trebuie să fie redimensionate pentru a obține rezultate mai rapizi.

Bibliografie

P. Siegel, “Terahertz technology,” IEEE Trans. Microwave Theory

Tech., vol. 50 Mar. 2002.

K. Ajito, H.-J. Song, A. Hirata, A. Wakatsuki, Y. Muramoto, N.

Shigekawa, T. Kumashiro, D. Asa, T. Nagatsuma, N. Kukutsu, and

Y. Kado – “Continuous-wave terahertz spectroscopic imaging at over 1

THz for pharmaceutical applications,” in 2010 35th Int. Conf. Infrared

Millimeter and Terahertz Waves (IRMMW-THz), Sep. 2010.

K. Ajito and Y. Ueno – “THz chemical imaging for biological applications,”

IEEE Trans. Terahertz Sci. Technol., vol. 1, Sep. 2011.

B. Karasik, A. Sergeev, and D. Prober – “Nanobolometers for THz

photon detection,” IEEE Trans. Terahertz Sci. Technol., vol. 1, Sep. 2011.

U. Pfeiffer – “Sub-millimeter wave active imaging with silicon integrated

circuits,” in 2011 Int. Conf. Infrared, Millimeter, and Terahertz

Waves (IRMMW-THz), Oct. 2011.

E. Öjefors, N. Baktash, Y. Zhao, R. Al Hadi, H. Sherry, and U. Pfeiffer –

“Terahertz imaging detectors in a 65-nm cmos soi technology,” in 2010

Eur. Solid-State Circuits Conf. (ESSCIRC), Seville, Spain, Sep. 2010.

Jianbo Shi & Jitendra Malik – Normalized Cuts and Image Segmentation, Proc. IEEE Conf.

Computer Vision and Pattern Recognition, 1997.

T. Kanungo, D. M. Mount, N. Netanyahu, C. Piatko, R. Silverman, & A. Y.Wu. – An efficient

k-means clustering algorithm: Analysis and implementation Proc. IEEE Conf. Computer Vision and

Pattern Recognition, 2002.

D. Arthur, & S. Vassilvitskii – K-mean++ The advantage of Careful Seeding. Symposium of

Discrete Algorithms, 2007.

Buzuloiu, V.: Prelucrarea imaginilor: note de curs, Universitatea “Politehnica” Bucuresti, 1998.

Castleman, K. R – Digital Image Processing, Prentice Hall, Englewood Cliffs, NJ,

1996

Cocquerez, J. P., Philipp, S. (coord.) – Analyse d‘images: filtrage et segmentation,

Masson, Paris, 1995

Gonzales, R. C., Woods, R. E. – Digital Image Processing, Addison Wesley, Reading

MA, 1992.

Ministerium für Wirtschaft, Mittelstand und Technologie des Landes Nordrhein-

Westfalen – Produkte und Dienstleitungen für die Bildverarbeitung. Stand und Trends,

Düsseldorf, 1996.

R. Al Hadi, H. Sherry, J. Grzyb, N. Baktash, Y. Zhao, E. Öjefors, A.

Kaiser, A. Cathelin, and U. Pfeiffer – “A broadband 0.6 to 1 THz CMOS

imaging detector with an integrated lens,” in IEEE MTT-S Int. Microw.

Symp. Dig., Jun. 2011.

H. Sherry, R. Al Hadi, J. Grzyb, E. Öjefors, A. Cathelin, A. Kaiser, and

U. R. Pfeiffer – “Lens-integrated THz imaging arrays in 65 nm CMOS

technologies,” in IEEE Radio Freq. Integr. Circuits (RFIC) Symp.Dig.,

Jun. 2011.

H. Sherry, J. Grzyb, Y. Zhao, R. A. Hadi, A. Cathelin, A. Kaiser, and

U. Pfeiffer – “A 1 k-pixel CMOS camera chip for 25 fps real-time terahertz

imaging applications,” in 2012 IEEE Int. Solid-State Circuits

Conf. (ISSCC) Dig. Tech. Papers, Feb. 2012.

Referinte Web.

http://people.revoledu.com/kardi/tutorial/kMean/matlab_kMeans.htm

http://www.croce.ggf.br/dados/K%20mean%20Clustering1.pdf

http://math.ucv.ro/~gorunescu/en/courses/curs/clustering.pdf

http://www.ece.uvic.ca/~aalbu/computer%20vision%202009/Lecture%209.%20Segmentation-Thresholding.pdf

Bibliografie

P. Siegel, “Terahertz technology,” IEEE Trans. Microwave Theory

Tech., vol. 50 Mar. 2002.

K. Ajito, H.-J. Song, A. Hirata, A. Wakatsuki, Y. Muramoto, N.

Shigekawa, T. Kumashiro, D. Asa, T. Nagatsuma, N. Kukutsu, and

Y. Kado – “Continuous-wave terahertz spectroscopic imaging at over 1

THz for pharmaceutical applications,” in 2010 35th Int. Conf. Infrared

Millimeter and Terahertz Waves (IRMMW-THz), Sep. 2010.

K. Ajito and Y. Ueno – “THz chemical imaging for biological applications,”

IEEE Trans. Terahertz Sci. Technol., vol. 1, Sep. 2011.

B. Karasik, A. Sergeev, and D. Prober – “Nanobolometers for THz

photon detection,” IEEE Trans. Terahertz Sci. Technol., vol. 1, Sep. 2011.

U. Pfeiffer – “Sub-millimeter wave active imaging with silicon integrated

circuits,” in 2011 Int. Conf. Infrared, Millimeter, and Terahertz

Waves (IRMMW-THz), Oct. 2011.

E. Öjefors, N. Baktash, Y. Zhao, R. Al Hadi, H. Sherry, and U. Pfeiffer –

“Terahertz imaging detectors in a 65-nm cmos soi technology,” in 2010

Eur. Solid-State Circuits Conf. (ESSCIRC), Seville, Spain, Sep. 2010.

Jianbo Shi & Jitendra Malik – Normalized Cuts and Image Segmentation, Proc. IEEE Conf.

Computer Vision and Pattern Recognition, 1997.

T. Kanungo, D. M. Mount, N. Netanyahu, C. Piatko, R. Silverman, & A. Y.Wu. – An efficient

k-means clustering algorithm: Analysis and implementation Proc. IEEE Conf. Computer Vision and

Pattern Recognition, 2002.

D. Arthur, & S. Vassilvitskii – K-mean++ The advantage of Careful Seeding. Symposium of

Discrete Algorithms, 2007.

Buzuloiu, V.: Prelucrarea imaginilor: note de curs, Universitatea “Politehnica” Bucuresti, 1998.

Castleman, K. R – Digital Image Processing, Prentice Hall, Englewood Cliffs, NJ,

1996

Cocquerez, J. P., Philipp, S. (coord.) – Analyse d‘images: filtrage et segmentation,

Masson, Paris, 1995

Gonzales, R. C., Woods, R. E. – Digital Image Processing, Addison Wesley, Reading

MA, 1992.

Ministerium für Wirtschaft, Mittelstand und Technologie des Landes Nordrhein-

Westfalen – Produkte und Dienstleitungen für die Bildverarbeitung. Stand und Trends,

Düsseldorf, 1996.

R. Al Hadi, H. Sherry, J. Grzyb, N. Baktash, Y. Zhao, E. Öjefors, A.

Kaiser, A. Cathelin, and U. Pfeiffer – “A broadband 0.6 to 1 THz CMOS

imaging detector with an integrated lens,” in IEEE MTT-S Int. Microw.

Symp. Dig., Jun. 2011.

H. Sherry, R. Al Hadi, J. Grzyb, E. Öjefors, A. Cathelin, A. Kaiser, and

U. R. Pfeiffer – “Lens-integrated THz imaging arrays in 65 nm CMOS

technologies,” in IEEE Radio Freq. Integr. Circuits (RFIC) Symp.Dig.,

Jun. 2011.

H. Sherry, J. Grzyb, Y. Zhao, R. A. Hadi, A. Cathelin, A. Kaiser, and

U. Pfeiffer – “A 1 k-pixel CMOS camera chip for 25 fps real-time terahertz

imaging applications,” in 2012 IEEE Int. Solid-State Circuits

Conf. (ISSCC) Dig. Tech. Papers, Feb. 2012.

Referinte Web.

http://people.revoledu.com/kardi/tutorial/kMean/matlab_kMeans.htm

http://www.croce.ggf.br/dados/K%20mean%20Clustering1.pdf

http://math.ucv.ro/~gorunescu/en/courses/curs/clustering.pdf

http://www.ece.uvic.ca/~aalbu/computer%20vision%202009/Lecture%209.%20Segmentation-Thresholding.pdf