PRELUCRAREA SI ANALIZA IMAGINILORConstantin VERTAN{1999}Cuprins1 INTRODUCERE 61.1 Imagini digitale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2 Structura unui sistem de prelucrarea si analiza imaginilor . . . . . . . . . 91.3 Stocarea imaginilor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.3.1 Stocarea imaginilor n memorie . . . . . . . . . . . . . . . . . . . 131.3.2 Stocarea imaginilor n siere . . . . . . . . . . . . . . . . . . . . . 142 TEHNICI DE MBUNATA TIRE A IMAGINILOR 172.1 Operatii punctuale de modicare a contrastului . . . . . . . . . . . . . . 182.1.1 Modicarea liniar a a contrastului . . . . . . . . . . . . . . . . . . 192.1.2 Modicarea neliniar a a contrastului . . . . . . . . . . . . . . . . . 232.2 Pseudocolorarea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.3 Operatii de contrastare bazate pe histograma imaginii . . . . . . . . . . . 263 FILTRAREA LINIARA A IMAGINILOR 313.1 Filtrarea liniar a de netezire . . . . . . . . . . . . . . . . . . . . . . . . . 343.2 Filtrarea liniar a de contrastare . . . . . . . . . . . . . . . . . . . . . . . . 363.3 Filtrarea liniar a adaptiv a . . . . . . . . . . . . . . . . . . . . . . . . . . . 384 TRANSFORMARI INTEGRALE UNITARE DISCRETE 4224.1 Generalit ati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.2 Propriet atile transformatelor unitare unidimensionale . . . . . . . . . . . 444.3 Transformata Fourier discret a . . . . . . . . . . . . . . . . . . . . . . . . 454.3.1 Propriet atile fundamentale ale transformatei Fourier . . . . . . . . 464.3.2 Transformata Fourier rapid a . . . . . . . . . . . . . . . . . . . . . 494.4 Alte transform ari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534.4.1 Transformata cosinus . . . . . . . . . . . . . . . . . . . . . . . . . 534.4.2 Transformata sinus . . . . . . . . . . . . . . . . . . . . . . . . . . 545 FILTRAREA NELINIARA A IMAGINILOR 565.1 Filtrarea de ordine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575.1.1 Filtrul median . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595.1.2 Filtrele de ordine ponderate si structurile multietaj . . . . . . . . 625.2 Filtre de ordine de domeniu . . . . . . . . . . . . . . . . . . . . . . . . . 655.3 L-ltre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 655.4 Aspecte de implementare . . . . . . . . . . . . . . . . . . . . . . . . . . . 666 ELEMENTE DE MORFOLOGIE MATEMATICA 716.1 Transform ari morfologice de baz a . . . . . . . . . . . . . . . . . . . . . . 726.1.1 Transformarea Hit or Miss . . . . . . . . . . . . . . . . . . . . . . 726.1.2 Erodarea morfologic a . . . . . . . . . . . . . . . . . . . . . . . . . 746.1.3 Dilatarea morfologic a . . . . . . . . . . . . . . . . . . . . . . . . . 756.1.4 Propriet atile erod arii si dilat arii . . . . . . . . . . . . . . . . . . . 776.1.5 Aspecte de implementare . . . . . . . . . . . . . . . . . . . . . . . 846.2 Transform ari morfologice derivate . . . . . . . . . . . . . . . . . . . . . . 856.2.1 Deschiderea si nchiderea . . . . . . . . . . . . . . . . . . . . . . . 8536.2.2 Filtrele alternate secvential . . . . . . . . . . . . . . . . . . . . . 886.2.3 Operatori morfologici de contur . . . . . . . . . . . . . . . . . . . 886.3 Extinderea morfologiei matematice la nivele de gri . . . . . . . . . . . . . 897 METODE DE COMPRESIE A IMAGINILOR 927.1 Compresia imaginilor binare. . . . . . . . . . . . . . . . . . . . . . . . . 937.1.1 Codarea entropic a (Human) . . . . . . . . . . . . . . . . . . . . 937.1.2 Codarea pe ux de biti . . . . . . . . . . . . . . . . . . . . . . . . 957.2 Compresia imaginilor cu nivele de gri . . . . . . . . . . . . . . . . . . . . 997.2.1 Codarea predictiv a. . . . . . . . . . . . . . . . . . . . . . . . . . 1007.2.2 Compresia imaginilor cu transformate . . . . . . . . . . . . . . . . 1017.2.3 Codarea cu arbori cuaternari . . . . . . . . . . . . . . . . . . . . 1027.2.4 Cuantizarea vectorial a . . . . . . . . . . . . . . . . . . . . . . . . 1058 SEGMENTAREA IMAGINILOR 1108.1 Segmentarea orientat a pe regiuni . . . . . . . . . . . . . . . . . . . . . . 1118.1.1 Segmentarea bazat a pe histogram a . . . . . . . . . . . . . . . . . 1118.1.2 Cresterea si fuziunea regiunilor . . . . . . . . . . . . . . . . . . . 1198.2 Segmentarea orientat a pe contururi . . . . . . . . . . . . . . . . . . . . . 1238.2.1 Metode derivative . . . . . . . . . . . . . . . . . . . . . . . . . . . 1238.2.2 Alte metode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1289 PARAMETRI DE FORMA 1309.1 Parametri geometrici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1309.2 Momente statistice si invarianti . . . . . . . . . . . . . . . . . . . . . . . 1319.3 Semn atura formei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13349.4 Skeletoane morfologice si generalizate . . . . . . . . . . . . . . . . . . . . 1359.4.1 Skeletonul morfologic . . . . . . . . . . . . . . . . . . . . . . . . . 1359.4.2 Skeletonul generalizat . . . . . . . . . . . . . . . . . . . . . . . . . 13710 PRINCIPII DE IMPLEMENTARE SOFTWARE SI HARDWARE 1395Capitolul 1INTRODUCEREPrelucrarea si analiza imaginilor (numit a adeseori prescurtat doar prelucrarea imaginilor)s-a n ascut datorit a ideii si necesit atii de a nlocui observatorul uman printr-o masin a. Esteimportant de precizat c a analiza imaginilor a mers mai departe dect simpla nlocuirea observatorului uman, deoarece au ap arut solutii novatoare pentru probleme cu careacesta nu mai fusese confruntat - ca n cazul imaginilor non-vizibile (imagini acustice,ultrasonore, radar). Dup a cum se remarc a n [9], prelucrarea imaginilor nglobeaz a posi-bilitatea de a dezvolta masina total a de viziune, capabil a s a realizeze functiile vizuale aleoric arei vietuitoare (desigur, dup a realizarea a importante dezvolt ari teoretice si tehno-logice).Image processing holds the possibility of developing the ultimate machinethat could perform the visual functions of all living beings.Trebuie remarcat a terminologia anglo-saxon a (original a), n care disciplina este denumit aDigital Image Processing, deci prelucrarea digital a a imaginilor. Prin prelucrarea digital aa imaginilor se ntelege prelucrarea pe un calculator digital a unor date bidimensionale(imagini).Termenul cheie este cuvntul digital, nlocuit adesea n mod eronat n multetraduceri romnesti cu termenul de numeric. Dup a cum o arat a dictionarul limbii romnemoderne, denitia cuvntului numeric este aceea decare apartine numerelor, privitor la numere, exprimat prin numere.Rezultatul oric arui calcul este numeric. Termenul digital nseamn a ns aceea ce este referitor la reprezentarea informatiei discrete n calculatoare6Deci atta vreme ct accept am ideea c a unealta de lucru n prelucrarea imaginilor estecalculatorul, si acesta la rndul s au este digital, atunci si prelucrarea este la rndul eidigital a, ca un caz particular al oric arei prelucr ari numerice. Desigur c a exist a ns a siprelucr ari de imagini care sunt analogice - asa cum sunt toate prelucr arile ce au loc ncadrul lantului de transmisie si receptie a imaginii standard de televiziune.1.1 Imagini digitaleLa nceput, imaginile sunt semnale, dar nu functii temporale, ci functii denite pe undomeniu spatial. Orice imagine este o structur a bidimensional a (tablou, matrice) de date.Un element al imagini se numeste pixel (cuvnt preluat din englez a, unde provine de lapicture element). Aceste date pot numere naturale, reale sau complexe, reprezentatens a pe un num ar nit de biti.Dup a tipul datelor din acest a structur a bidimensional a,imaginile prelucrate pot mp artite n mai multe categorii: imagini scalare, n care ecare component a este un scalar (un unic num ar);caexemple de astfel de imagini se pot da imaginile monocrome (n care punctele audoar dou a valori posibile, ce corespund unui continut binar al imaginii, n generalalb-negru) si imaginile cu nivele de gri (de tipul imaginii de luminant a de pe ecraneletelevizoarelor alb-negru). imagini vectoriale, n care ecare component a este un vector de numere;cazulparticular cel mai de interes este acela al imaginilor color, n care vectorul are treielemente (ce corespund celor trei constituente de baz a ale oric arei culori); n general,pentru imaginile multicomponent a, vectorul asociat ec arui punct din imagine aremai multe elemente (caz ce corespunde imaginilor preluate n mai multe benzide frecvent a, asa cum sunt imaginile de teledetectie ale satelitilor, imaginile determodetectie n benzile de infrarosu,...). Tot n categoria imaginilor vectorialeintr a ns a si imaginile stereo (o pereche de imagini ale aceleiasi scene, luate dinunghiuri diferite) si secventele de imagini.Conform datelor prezentate n [11], dintre imaginile prelucrate n aplicatii functionale,20 % sunt alb-negru, 32 % sunt cu nivele de gri, 20 % sunt color, 10 % sunt imaginistereoscopice si 18 % sunt secvente de imagini.n mod clasic, valoarea unui element al unei imagini este o m asur a a intensit atii luminoasen punctul considerat; acesta nu este ns a dect un caz particular. Dup a natura lor,imaginile pot clasicate ca imagini abstracte, imagini non-vizibile si imagini vizibile [2].Imaginile abstracte sau modelele sunt de fapt functii [matematice], continue sau discrete,de dou a variabile. Imaginile non-vizibile, care, evident, nu pot percepute n mod directde ochiul uman, sunt de fapt achizitii ale unor cmpuri bidimensionale de parametri zici7(presiune, temperatur a, presiune, densitate, ...). n ne, imaginile ce pot perceputen mod direct de c atre ochiul uman (deci imaginile vizibile) sunt la rndul lor imaginioptice, generate ca distributii de intensitate luminoas a (asa ca hologramele, imaginilede interferent a si difractie) sau imagini propriu-zise (de luminant a - n sensul curent altermenului, ce se refer a la fotograi, desene, picturi, schite, scheme si altele din aceeasicategorie).O alt a mp artire a imaginilor scalare se poate face dup a semnicatia ce se d a valoriinumerice a pixelilor. Vom distinge astfel imagini de intensitate si imagini indexate. Oimagine de intensitate este o imagine n care valoarea ec arui pixel este o m asur a direct aa intensit atii luminoase sau a m arimii zice preluate de senzor, ca de exemplu n imaginilecu nivele de gri. Pixelii unei imagini de intensitate pot avea orice fel de valori: reale saunaturale (depinznd dac a imaginea este sau nu cuantizat a).O imagine indexat a este acea imagine n care valoarea ec arui pixel este un indice prin carese reg aseste informatia de culoare asociat a pixelului respectiv. Deci, pentru asarea saureprezentarea unei imagini indexate este necesar a o informatie suplimentar a, de asocierentre indici si culori. Aceast a asociere se face prin intermediul tabelei de culoare. Tabelade culoare este o matrice n care ecare linie contine descrierea unei culori (deci celetrei componente ce denesc culoarea - n mod tipic intensit atile relative de rosu, verdesi albastru ce compun culoarea dat a printr-un amestec aditiv). Deci tabela de culoareare trei coloane; num arul de linii al tabelei de culoare este egal cu num arul de culoridin imaginea reprezentat a si este n mod tipic o putere a lui doi (16, 256, ...).Indicele(valoarea pixelului) va num arul de ordine al liniei din tabela de culoare pe care seg aseste descrierea culorii. Este evident c a valorile pixelilor unei imagini indexate nu pot dect numere naturale (deoarece sunt indici ntr-o matrice).Aceast a tehnic a este folosit a si n graca pe calculator. Asarea imaginilor pe ecranulmonitorului se face corespunz ator unui anumit mod grac, determinat din placa videoa calculatorului. Un mod video deneste num arul maxim de culori ce pot utilizatesimultan si dimensiunile ecranului (n pixeli de asaj).Culorile utilizate la un momentdat sunt grupate ntr-o palet a de culori de asare. Paleta de asare este o structur a logic adenit a n BGI1(Borland Graphics Interface), pentru programare n sesiuni de tip DOS,ca:struct palettetype {unsigned char size;int colors[MAXCOLORS+1]; }Modicarea unei culori din palet a (o intrare a tabelului) se face cu:void far setpalette(int index_culoare, int culoare);1Exemplele de cod C prezentate n lucrare corespund mediilor integrate Borland (Borland C++ 3.1,Turbo C 2.0)8Asarea unui pixel cu o anumit a culoare se face cu:putpixel(int pozx, int pozy, int index_culoare);Sub Windows, este suportat a si specicarea direct a a culorii de asat (sub forma unuitriplet RGB2), sistemul de operare aproximnd culoarea respectiv a cu cea mai apropiat aculoare disponibil a din paleta de lucru curent a (n acest fel, utilizatorul poate neglijaexistenta acesteia).Pentru o imagine cu nivele de gri, componentele de rosu, verde si albastru ale ec areiculori din paleta de culoare sunt identice. Dac a specicarea componentelor de culoare seface prin numere de 8 biti (deci ntre 0 si 255, adic a cazul cel mai des folosit), tabela deculoare va avea 256 de culori (tonuri de gri) diferite. Specicarea acestora se va face cuindecsi ntre 0 si 255, alocati conform conventiei 0 - negru, 255 - alb. n acest fel, pentruo imagine indexat a cu nivele de gri, nu mai este necesar a specicarea tabelei de culoare;culorii reprezentate de indexul i i corespunde nivelul de gri i, adic a tripletul RGB (i, i, i).Modelul imagini indexate este un caz particular de folosire a tehnicii dictionar (sautehnicii tabelului de echivalent a - Look Up Table - LUT): o tehnic a de reg asire a uneicantit ati de informatie folosind asocierea unei chei de c autare mult mai mici.1.2 Structura unui sistem de prelucrarea si analizaimaginilorStructura tipic a a unui sistem de prelucrarea (evident digital a) si analiza imaginilor estealc atuit a din punct de vedere functional dintr-un num ar mic de blocuri (vezi gura 1.1): sistemul de formare a imaginii (de exemplu sistemul de lentile al camerelor deluat vederi): strnge radiatia electromagnetic a a obiectului studiat pentru a formaimaginea tr as aturilor de interes convertorul de raditie: converteste radiatia electromagnetic a din planul imaginiintr-un semnal electric.Sistemul de formare a imaginii si convertorul de radiatie formeaz a senzorul; acesta reali-zeaz a o proiectie plan a (bidimensional a) a scenei reale (care este n general tridimensio-nal a). Un studiu realizat n Germania n anul 1996 [11] prin inventarierea sistemelor de2Red Green Blue - Rosu, Verde, Albastru: sistemul primar de reprezentare a culorilor.9Fig. 1.1: Schema general a a unui sistem de analiza si prelucrarea imaginilorpreluare a imaginilor folosite n industrie indic a o distributie a tipurilor de senzori dup agama de radiatie captat a conform tabelului 1.1:Domeniu Infrarosu Infrarosu Vizibil Ultraviolet Radar Radiatieelectromagnetic dep artat apropiat (microunde) XProcent 5 % 25 % 40 % 10 % 10 % 10 %Tabel 1.1: Tipuri de senzori folositi n prelucrarea imaginilor sistemul de achizitie (echivalent unui frame-grabber sau video-blaster): convertestesemnalul electric al senzorului ntr-o imagine digital a, pe care o stochez a; acesta nueste altceva dect un dispozitiv de esantionare (discretizare a suportului imaginii)si cuantizare (discretizare a domeniului de valori a imaginii). sistemul de prelucrare (n mod tipic un calculator, e el PC sau statie de lucru); naceast a categorie se ncadreaz a ns a si masinile specializate de calcul, calculatoarelede proces, ... software-ul specializat: implementeaz a algoritmii de prelucrare si analiz an [11] se arat a c a unitatea de prelucrarea hardware (deci calculatorul) folosit a la apli-catiile de prelucrarea imaginilor functionale la acea dat a este n cea mai mare majoritatea cazurilor un PC obisnuit, cu performante standard; datele sunt sintetizate n tabelul1.2:10Platform a hardware Procent din piat aPC standard, bus ISA, Windows 3.1, 95, NT 40 %Calculatoare industriale (procesoare Intel), bus VME 15 %PC standard cu acceleratoare specializate, bus VLB, PCI 15 %Statii de lucru (workstations) 10 %Masini specializate 10 %Calculatoare Macintosh, calculatoare paralele (transputere), altele 10 %Tabel 1.2: Unit ati de calcul folosite n prelucrarea imaginilorSistemul software specializat care este responsabil cu realizarea efectiv a a unei sarcini con-crete poate descompus n mai multe module, nu neap arat bine separate si nu neap aratprezente mpreun a: mbun at atirea, restaurarea, compresia, segmentarea si analiza [9].Blocul de mbun at atire a imaginilor are ca scop accentuarea anumitor tr as aturi [aleobiectelor continute n imagine] pentru usurarea unor sarcini ulterioare de analiz a au-tomat a sau interpretare prin asare.Asemenea metode pot utile la extragerea tr as a-turilor caracteristice ale obiectelor, eliminarea zgomotelor suprapuse imaginii, m arireaconfortului vizual. Acesti algoritmi nu m aresc continutul informational al imaginii sisunt n general interactivi si puternic dependenti de aplicatie.Restaurarea imaginilor se refer a la eliminarea sau minimizarea efectelor unor perturbatiisi a unor degrad ari.Perturbatiile reprezint a n general zgomotele (modelate ca procesealeatoare) ce se suprapun n cursul achizitiei imaginii (din cauza senzorului si a lantuluide transmisiune si captare); degrad arile sunt cauzate de imperfectiunile si limit arile de-terministe ale senzorului (efecte de apertur a, timp de expunere, deciente geometrice alesistemului de lentile, ...).Compresia imaginilor se refer a la reducerea volumului de date (num arului de biti) cucare este reprezentat a imaginea, printr-o transformare reversibil a - imaginea trebuie s apoat a s a e recuperat a integral (sau cu diferente foarte mici, controlabile) din versiuneasa comprimat a.Segmentarea este procesul de descompunere a unei imagini (sau scene) n elementele(obiectele) sale constituente. Adeseori, segmentarea este strns legat a de algoritmii deanaliz a, al c aror scop este de a realiza m asur atori cantitative sau evalu ari calitative asupraunor anumite categorii de obiecte, prezente n imaginea dat a.Sfera de aplicabilitate a tehnicilor de prelucrarea si analiza imaginilor este deosebit delarg a; practic, n orice domeniu de activitate se pot g asi numeroase aplicatii. Aceast a clas ade aplicatii extrem de specice a fost caracterizat a drept consumul imaginii [1] (ima-ginea folosit a n vederea analizei, deci a lu arii unor decizii). Imaginile preluate de c atresateliti pot folosite la descoperirea resurselor terestre, cartograere geograc a, predictiarecoltelor, urm arirea dezvolt arii urbane, urm arirea vremii, controlul si prevenirea incendi-11ilor si inundatiilor, precum si alte aplicatii ecologice si militare. Aplicatiile transmisieisi compresiei imaginilor se reg asesc n televiziunea digital a, sistemele de teleconferint a,transmisiile fax, birotic a, comunicatia pe retele distribuite, sisteme de securitate cu cir-cuit nchis, aplicatii militare. n aplicatiile medicale sunt prelucrate radiograile cu razeX, angiogramele, echograile, tomograile, imaginile de rezonant a magnetic a nuclear a.Acestea pot utilizate pentru monitorizarea pacientilor si pentru descoperirea si identi-carea de boli si tumori.O larg a clas a de aplicatii sunt cele industriale, n care componentele de prelucrarea sianaliza imaginilor sunt folosite n sisteme mai mari de asigurare a calit atii produselor(metrologie, controlul calit atii - inclusiv defectoscopie nedistructiv a).Solutiile sunt ex-trem de specice, puternic legate de procesul de fabricatie urm arit si tind s a devin a dince n ce mai utilizate odat a cu impunerea normelor de calitate total a ale standarduluiISO9000 (se poate urm ari [10] pentru aplicatii specice ale diferitelor rme germane).Din acest punct de vedere este interesant a comparatia ntre cteva caracteristici ale sis-temului vizual si de prelucrare uman si un sistem de prelucrarea si analiza imaginilor [8],folosite pentru aplicatii industriale, prezentat a n tabelul 1.3.Criterii Om Sistem de prelucrarea imaginilorObiectivitate NU DAControl 100% NU DARat a de eroare MARE MICARat a de lucru MICA MARERezistent a la oboseal a MICA MAREIluzie optic a DA NUPrelucrare statistic a Greu realizabil DAReproductibilitate Greu realizabil DAM asurare geometric a Cu instrumente auxiliare DARecunoastere de forme DA DATabel 1.3: Comparatia ntre caracteristici esentiale ale sistemului vizual uman si sistemelede prelucrarea si analiza imaginilor1.3 Stocarea imaginilorSe poate considera c a exist a dou a moduri de stocare a imaginilor: stocarea n memoriade lucru a unit atii de prelucrare a imaginii de lucru (care este o stocare de scurt a durat a- doar pe durata prelucr arii efective) si stocarea de lung a durat a imaginilor, n siere, pesuporturi externe de memorie (benzi, discuri, etc.). Diferenta esential a ntre cele dou atipuri de stocare este aceea c a n memorie imaginea va reprezentat a complet, n form anecomprimat a, pentru a permite accesul rapid direct la informatia ec arui pixel.121.3.1 Stocarea imaginilor n memoriePrincipalul limbaj de programare utilizat pentru aplicatii cu calcule intensive r amne nc alimbajul C (C++). Stocarea imaginilor se va face, evident, prin intermediul unor variabilece implementeaz a structuri de date bidimensionale. Ceea ce este deosebit este modul dedeclarare a acestora:declararea static a nu este convenabil a din cauza dimensiunilor ngeneral mari ale imaginilor, si deci este necesar a o declarare dinamic a. Particularitateaeste dat a de memorarea separat a a ec arei linii (sau coloane) a matricii ntr-un vectoralocat dinamic, si gruparea adreselor de nceput a acestora ntr-un vector de pointeri, lacare se va retine adresa de nceput (deci un alt pointer). Dac a consider am un tip genericde date pentru componentele matricii (caracter, sau ntreg, sau real), atunci o secvent aC de declarare a unui imagini poate :tip ** imagine;unsigned int contor;imagine=(tip**) malloc(nr_linii*sizeof(tip*));for (contor=0;contor