Capitolul 1

FILTRAREA NELINIARA BAZATAPE ORDONARE

Ordonarea crescatoare a unui set de valori sta la baza operatiilor de filtrare de ordine [33]. Valorileordonate ale esantioanelor din fereastra de filtrare, numite statistici de ordine, pot fi utilizate caatare, sau pot fi combinate. Filtrul median [33], [48] este cel mai folosit filtru cu ordonare dupa rang;iesirea acestuia este statistica de ordin central a setului de valori, permitand astfel eliminarea valorilorextreme aberante (outliar) ın acelasi timp cu pastrarea detaliilor utile ale imaginii. Cea mai uzualacombinatie a statisticilor de ordine este combinarea liniara; filtrul astfel obtinut se numeste L-filtru[33], [48]. L-filtrele sunt extrem de flexibile, ıngloband posibilitatea obtinerii atat a filtrelor simple deordonare dupa rang (inclusiv filtrul median) cat si a filtrelor liniare1.

Daca ın cazul imaginilor scalare ordonarea valorilor nu prezinta nici o problema, extinderea claselorde filtre bazate pe ordonare ın cazul imaginilor color (sau, ın general, vectoriale) nu este o chestiunesimpla. Dupa cum se remarca ın [3], proprietatile de ordonare exista doar ıntr-o singura dimensiunesi nu exista nici o conceptie naturala de rang.

Notatia general acceptata este de a considera {x1,x2, ...,xn} o populatie de vectori p-dimensionali,realizari particulare ale variabilei aleatoare multivariate X. Componenta i a variabilei aleatoare multi-variate este Xi si va fi reprezentata de multimea de realizari particulare {x1i, x2i, ..., xni}. Pentru cazulimaginilor color prelucrate prin filtre de vecinatate, n este dimensiunea ferestrei de filtrare, numarulde componente a vectorilor este p = 3, iar vectorii xi sunt triplete de componente de culoare ce descriufiecare pixel.

1.1 Filtrari de ordine prin ordonare lexicografica

O relatie introdusa ıntre elementele unui spatiu vectorial se numeste relatie de ordine daca verificaproprietatile de reflexivitate (1.1), tranzitivitate (1.2) si antisimetrie (1.3):

x � x, ∀x (1.1)

x � y si y � z =⇒ x � z, ∀x,y, z (1.2)1Filtrul liniar de mediere se obtine evident ın conditiile ın care ponderile statisticilor de ordine sunt egale cu 1/n;

pentru aplicarea unei filtrari liniare de mediere ponderata, trebuie introdusa notiunea de L-filtru adaptiv, cu coeficientide ponderare diferiti pentru fiecare pixel, ce sunt permutari ale coeficientilor filtrului liniar (permutari generate ın aceeasifel ca ordonarea valorilor din imagine).

1

x � y si y � x =⇒ x = y, ∀x,y (1.3)

Conform acestei definitii, pentru date multivariate (vectoriale) se poate introduce o singura relatiede ordine bine definita: ordinea lexicografica (numita si ordine de dictionar). Pentru vectorii p-dimensionali x si y relatia de ordine lexicografica este definita prin:

x � y⇐⇒{xi = yi, pentru i = 1, 2, ..., k, cu k ∈ [0; p− 1]xi ≤ yi, pentru i = k + 1.

(1.4)

Este evident ca ın cadrul ordonarii complete, lexicografice (1.4), vectorii sunt ordonati dupa primacomponenta, apoi dupa a doua componenta, si asa mai departe. Aceasta ınseamna ca prima com-ponenta trebuie sa fie cea mai importanta sau semnificativa (sau, mai mult, componentele vectoruluitrebuie sa fie ordonate ın ordinea importantei acestora). Aceasta ordonare nu poate fi cunoscutaapriori si este puternic dependenta de problema; mai mult, ın cazul imaginilor, ordinea importanteicomponentelor de culoare nu este invarianta spatial. In plus (si acesta este dezavantajul cel maiimportant), ordinea lexicografica nu pastreaza topologia spatiului.

Aplicarea practica a ordonarii lexicografice se bazeaza deci pe stabilirea unei ordini a importanteicomponentelor de culoare (deci stabilirea unor ranguri pentru acestea). In aceasta situatie se distingdoua cazuri fundamentale: daca reprezentarea culorilor este reprezentarea RGB primara este de pre-supus ca, apriori, toate componentele au o aceeasi importanta si distinctia dintre ele trebuie facutaadaptiv, pentru fiecare pixel al imaginii, dupa masuri statistice locale; daca culorile sunt reprezentateıntr-un spatiu de culoare derivat, ın care cele trei componente sa aiba semnificatii fizice sau perceptualediferite, este de asteptat sa se poata stabili apriori o ordine a importantei acestora.

1.1.1 Ordonarea lexicografica ın spatiul primar

Pentru a realiza ordonarea unor vectori ale caror componente sunt valorile RGB ale culorilor trebuie,deci, deduse masuri ale activitatii componentelor de culoare; asemenea masuri sunt calculate pentrufiecare plan de culoare, ın vecinatatea fiecarui pixel al imaginii. Asemenea masuri de activitate acomponentelor de culoare ıncearca sa stabileasca ın care componenta de culoare sunt sesizabile celemai mari variatii. Variatiile puternice ale unei componente se presupune ca sunt datorate prezenteiimpulsurilor de zgomot ın vecinatatea curenta. Ca masuri de activitate (sau de disimilaritate) pot fifolosite varianta, domeniul de variatie (diferenta ıntre maximul si minimul local), raportul de contrast[18] sau domeniul de variatie normat la media componentei; cu cat disimilaritatea este mai mare,cu atat componenta este mai importanta, si deci, local, pentru ordonare, componentele vectorilor deculoare sunt permutate.

1.1.2 Ordonarea lexicografica ın spatiul perceptual

Dificultatea stabilirii unei ordini clare de importanta a componentelor de culoare RGB a unei imaginisugereaza folosirea unui spatiu de reprezantare a culorilor ın care, din modul de definire, importantacomponentelor sa fie deja stabilita. Un astfel de spatiu este spatiul perceptual de reprezentare HSV .Reprezentarea se compune din componenta de nuanta, ce indica tipul de culoare, componenta desaturatie, ce exprima puritatea culorii si componenta de “valoare”, de tipul luminantei sau intensitatiiluminoase a culorii. Perceptual, cel mai usor de sesizat sunt modificarile nuantei (deoarece schimbanatura culorilor) [8], urmate de modificarile saturatiei (care pot da un caracter nenatural imaginii).In acelasi timp, prezenta impulsurilor de zgomot este sesizabila ın toate componentele HSV . Aceastasugereaza ca cel mai indicat este folosirea componentei V ca cea mai importanta componenta, ın caresa se detecteze prezenta impulsurilor de zgomot. Atunci, ınainte de ordonare, vectorii reprezentariiHSV a culorilor vor avea permutate componentele H si V .

2

1.2 Filtrari de ordine prin principii de pre-ordonare

Acceptand inutilitatea cautarii oricarei ordonari totale, simple, ne-ambigue si universale a n esantioanemultivariate, interesul practic a fost limitat la modurile ın care se pot construi relatii restranse deordonare vectoriala, fezabile si avantajoase. Rezultatul oricarui principiu de ordonare partiala (sausub-ordonare, sau pre-ordonare, ce nu respecta principiul de antisimetrie (1.3)) este o ordonare (sauplasare dupa rang) a uneia sau mai multor caracteristici ale observatiei, considerata individual sauın combinatie cu alte observatii. Proprietatile dorite pentru ordonarea dupa rang a datelor vectorialese pot extrapola din proprietatile ordonarii scalare: esantioanele monoton ne-descrescatoare pe toatecomponentele sunt vectori proprii, invarianti la ordonare; relatia ınglobeaza posibilitatea determinariiunui estimator robust al locatiei (medianul [33], [2]), ce poate fi determinat prin selectia statisticiicu un anume rang; este omogena fata de scalarea cu factori pozitivi a componentelor individuale;se reduce la ordonarea scalara daca componentele sunt identice; produce statistici de ordine ce suntobservatii ale multimii ordonate; sorteaza valorile extreme aberante ın regiuni consistente ale spatiuluirangurilor.

In [3] se propun patru pricipii de baza de ordonare partiala (pre-ordonare) a datelor vectoriale:

• ordonarea marginala (descrisa ın sectiunea 1.2.1)

• ordonarea conditionala (descrisa ın sectiunea 1.2.2)

• ordonarea partiala (descrisa ın sectiunea 1.2.3)

• ordonarea redusa (descrisa ın sectiunea 1.2.4)

1.2.1 Ordonarea marginala

Ordinea marginala [3], [33] este, dupa cum sugereaza si numele, o ordonare care se face dupa unul saumai multe din esantioanele marginale ale vectorilor considerati. Din punctul de vedere al prelucrariisemnalelor, ordonarea marginala revine la a ordona ın mod independent valorile esantioanelor dinfiecare canal al semnalului; modelul asociat semnalului vectorial (sau multicanal) este ın acest cazo stiva de semnale scalare, ce pot fi ordonate si prelucrate ın mod separat. Prin aceasta prelucrareindependenta a componentelor semnalelor nu se ia ın considerare intercorelatia existenta ıntre canale,aceasta fiind principala sursa de erori a metodei (ın [2] se arata de exemplu cum o prelucrare de tipmedian marginal a unui semnal de culoare produce culori false ın anumite zone cu culori puternicsaturate). Spre deosebire de cazul scalar, statisticile vectoriale marginale de ordine nu mai suntobservatii ale semnalului, ci valori noi.

In cazul imaginilor color, ın mod paradoxal, filtrarea marginala produce rezultate excelente, atatvizual (deci caracterizate conform unor masuri subiective) cat si ca masuri de calitate. Filtrul medianmarginal MMF (Median Marginal Filter) elimina ın mod eficient zgomotul impulsiv din imagini, chiarprezent ın proportii foarte mari (pana la 25%-30% din pixeli degradati). Filtrul median marginal esteutilizat si la derivarea unor structuri de filtrare adaptive (de exemplu prin comutarea ıntre un filtrumedian si un filtru trece tot, conditionat de varianta locala a componentelor).

Din punct de vedere teoretic, exista doua metode de luare ın considerare a corelatiei ce exista ıntrecomponentele imaginii vectoriale: ın primul rand, corelatia poate fi eliminata prin decorelarea compo-nentelor imaginii, sau corelatia dintre canale (componente) poate fi ınglobata ın proiectarea structuriifiltrului.

3

Filtre mediane marginale cu decorelare

Abordarea cu decorelare propune realizarea filtrarii mediane a fiecarei componente de culoare dupadecorelarea acestora. Decorelarea se face prin utilizarea transformarii Karhunen-Loeve (KL); recore-larea componentelor se face dupa filtrarea fiecarui plan de culoare. Aceasta abordare prezinta avan-tajul unei performante independente de sistemul de reprezentare folosit pentru culorile imaginii (fieın spatiul primar RGB, fie un spatiu perceptual). Dupa cum se poate usor constata, presupunereastatistica esentiala pe care se bazeaza folosirea transformarii KL la decorelare este aceea ca valorile(vectoriale) ale pixelilor imaginii sunt realizari particulare ale unui camp aleator, identic distribuite.Daca aceasta distributie a valorilor pixelilor (presupusa deci invarianta pentru ıntreaga imagine) arfi normala (gaussiana), ın urma decorelarii, componentele vectorilor observatie ar deveni si indepen-dente, nu numai decorelate [31], [43]. Asa numita abordare cu independentizare a filtrarii marginale aimaginilor color: ınaintea etapei de decorelare, distributia valorilor pixelilor este transformata ıntr-odistributie aproape normala folosind teorema limita centrala [31], [43] – suma unui numar de catevavariabile aleatoare identic distribuite, din care nici una nu este dominanta, tinde la o distributie nor-mala. Pentru a realiza aceasta distributie aproape normala, s-a propus realizarea de sume locale avecinilor fiecarui pixel. Dupa sumare se poate face decorelarea, filtrarea marginala, recorelarea si apoitransformarea inversa independentizarii (rezultand o operatie de filtrare numita IDMMF (IndependentDecorrelated Marginal Median Filter) sau se poate renunta la etape de decorelare (rezultand o operatiede filtrare numita IMMF (Independent Marginal Median Filter).

L-filtre vectoriale bazate pe ordonare marginala

Corelatia dintre componentele observatiilor vectoriale poate fi luata ın considerare prin modificareastructurii filtrelor de ordine ce se folosesc; acestea nu mai sunt identice cu analoagele lor din cazulscalar. Cazul L-filtrelor este tipic pentru aceasta abordare. Un L-filtru scalar aplicat unui set de valoriX = {x1, x2, ..., xn} produce ca iesire o combinatie liniara a statisticilor de ordine ale acestora [33],[48]:

y =n∑i=1

wix(i) =n∑

i1=1

Wi1x(i1) (1.5)

unde scalarii wi, respectiv Wi1 sunt cei n coeficienti ai filtrului. Pentru cazul valorilor vectoriale,fiecare observatie este un vector cu p componente, xi = (x1i, x2i, ..., xni), iar statisticile de ordinemarginale sunt vectori formati din statisticile de ordine marginale (calculate pentru fiecare componentaa observatiilor vectoriale, x(i) = (x1(i), x2(i), ..., xn(i)). Utilizarea acestor statistici vectoriale conducela redefinirea L-filtrului vectorial ca:

y =n∑

i1=1

n∑i2=1

...n∑

ip=1

Wi1i2...ipx(i) (1.6)

unde Wi1i2...ip sunt cele Np matrici p× p de coeficienti ai filtrului. Forma din (1.6) poate fi rearanjataın functie de vectorii statisticilor de ordine marginale din fiecare canal (componenta) a vectorilorobservatie:

y =p∑j=1

Wjx(j) (1.7)

Determinarea matricilor de coeficienti Wj se poate face prin optimizarea ın sensul erorii patraticemedii minime a unui L-filtru a carui iesire sa fie un estimator nedeplasat al pozitiei centrale (si deci saelimine zgomotul impulsiv, singular sau ın mixtura cu zgomotul gaussian). Determinarea coeficientilornecesita cunoasterea functiilor de densitate de probabilitate a statisticilor de ordine marginale alesemnalului de intrare, precum si a valorilor acestuia. Cum rareori semnalul de intrare nedegradat este

4

cunoscut, acesta trebuie estimat din valorile corecte deja calculate, prin ipoteze asupra stationaritatiisi proprietatilor sale de corelatie.

1.2.2 Ordonarea conditionala

Ordonarea conditionala este un mod de a stabili ranguri, sau o ordine, sau o modalitate de selectie[3], [33] pentru vectorii unui set de date, conditionata de ordonarea unei componente marginale aacestora. Deci ordinea unei singure componente marginale decide ordinea vectorilor; din acest punctde vedere, ordonarea conditionala poate fi interpretata ca o ordonare lexicografica trunchiata la osingura componenta2.

Acesta trunchiere ınseamna ca orice prelucrare se va face relativ la o singura componenta, pastrandu-le pe celelalte nemodificate. Componenta ce se prelucreaza trebuie, desigur, sa fie cea mai corupta(degradata de zgomot), sau componenta ın care influenta zgomotului se resimte cel mai puternic. Casi ın cazul definirii ordinii lexicografice (sectiunea 1.1) este necesara determinarea componentei ce seva prelucra. Se pot distinge si aici doua cazuri: daca exista o componenta intrinsec dominanta (asacum este componenta de valoare de la reprezentarea perceptuala HSV a imaginilor color), atunciaceasta este cea care se va prelucra. Daca toate componentele au, apriori, o aceeasi importanta (ca ıncazul reprezentarii imaginilor color ın spatiul primar RGB), este evident ca prelucrarea unui aceluiasiıntreg plan de culoare (sau a unei aceleiasi componente) nu poate produce rezultate.

Ca si ın cazul ordonarii lexicografice, solutia se afla ın alegerea adaptiva a componentei de prelucrat(componenta dupa care se face ordonarea conditionala) pentru fiecare pozitie a ferestrei de filtrare(deci pentru fiecare pixel al imaginii). Componenta cea mai activa este definita printr-o valoare marea unei masuri de neuniformitate: interval de variatie, interval de variatie normat la medie, varianta,raport de contrast, chiar valori proprii.

1.2.3 Ordonarea partiala

Ceea ce Barnett [3] numeste ordonare partiala a unui set de date multivariate (a unui set de vectori)se bazeaza pe distinctia ıntre grupuri de observatii (vectori) si nu pe distinctia ıntre fiecare vector ınparte. Deci, pentru aceasta varianta de sub-ordonare, accentul se muta de la considerarea esantioanelormarginale sau a observatiilor multivariate individuale la luarea ın considerare a proprietatilor globale,relationale, din ıntregul set al esantioanelor. Pentru a face o distinctie ıntre diferitele grupuri deobservatii (avand ın vedere ordinea, extremele, rangul) se urmareste modul ın care observatiile sesituaza ın diferite regiuni ale spatiului esantioanelor. Metoda de partitionare folosita (bazata pe unuldintre mai multe principii posibile) poate implica proprietati marginale ale datelor; scopul principaleste de a oferi o distinctie limitata ıntre diferitele esantioane (vectori) ai populatiei.

Ordonarea partiala produce o baza de ımpartire a esantioanelor ın grupuri distincte de diferite ordine,fara a face distinctii ın interiorul unui aceluiasi grup.

Ordonarea partiala implica construirea anvelopei convexe a setului de observatii (setul convex minimce contine toate observatiile initiale). Punctele (vectorii) ce se afla pe ınfasuratoarea anvelopei convexesunt numite grupul 1, si apoi eliminate; se formeaza apoi anvelopa convexa a reziduului, punctele de penoua ınfasuratoare formeaza grupul 2 (a se vedea figura 1.2.3). Procedeul este repetat, formand astfelo metoda bazata pe divizarea datelor ın grupuri de ordine (sau de rang). Cu cat numarul (ordinul)

2Anticipand definirea ordonarii reduse, putem spune ca ordonarea conditionala poate fi obtinuta si din aceasta dacascalarul asociat fiecarui vector (a se vedea descrierea completa a metodei ın sectiunea 1.2.4) este o singura componentaa acestuia.

5

Fig. 1.1: Partitionarea unui set de vectori bidimensionali dupa anvelopa convexa.

grupului este mai mic, cu atat observatia (esantionul, vectorul) este mai extremal. Este evident ca,ın aceste conditii, vectorii setului de ordin maxim sunt situati ın centrul clusterului de puncte, si decisunt candidati pentru medianul acestora. O asemenea metoda de ordonare este analoaga cu ceea ce afost numit ın statistica cojirea unei populatii multivariate [27] (potato peeling sau orange peeling). Oasemenea operatie are ınsa un analog pentru cazul scalar: asa numitul filtru tobogan3 de ımbunatatirea uniformitatii unei regiuni [55].

Esenta metodei se bazeaza deci pe implementarea unor algoritmi de calcul al anvelopei convexe pentrudate p dimensionale, cu p > 1, deci pe algoritmi de geometrie computationala [30]. Teorema McMullen-Shepard [30] arata ca anvelopa convexa a oricarei multimi de puncte din spatiul Euclidian p dimensionaleste un politop4 convex (reciproc, orice politop convex fiind anvelopa convexa a cel putin unui set depuncte). Pentru cazul plan (p = 2) exista alte seturi de teoreme ce dau descrieri ale anvelopei convexe aunui set de puncte, ce sunt direct implementabile; algoritmi deja clasici sunt algoritmii Jarvis (Jarvismarch) [42] si algoritmul Graham (Graham scan) [42]. Pe masura ce dimensiunea spatiului cresteproblema de determinare a anvelopei convexe devine din ce ın ce mai complicata; ın cazul general,rezolvarea acesteia se poate face printr-o abordare de tip package-wrapping (sau gift-wrapping) [30].Fiecare pas al acestei metode gaseste o noua fata a politopului anvelopa convexa ındoind (pliind)

3Filtrul tobogan ınlocuieste extremele valorilor selectate de o fereastra de filtrare cu statisticile imediat urmatoare(superioara sau inferioara, depinzand daca extremul este un minim sau un maxim), cu conditia ca acestea sa aiba valoridiferite de valoarea extremului.

4Un politop este o multime poliedrala, rezultata ca intersectia unui numar finit de semispatii ınchise; un semispatiueste regiunea spatiului p dimensional aflata de aceeasi parte a unui hiperplan.

6

un hiperplan ın jurul unei muchii a anvelopei convexe deja determinate, pana ın momentul ın careacesta ıntalneste primul punct al multimii de puncte initiale. Analiza complexitatii algoritmice a uneiasemenea abordari a condus la deducerea unei comportari O(n2), unde n este numarul de puncte alsetului pentru care se calculeaza anvelopa convexa. Abordarile cele mai rapide pornesc de la principiuldivide et impera si de la o teorema ce demonstreaza echivalenta dintre problemele sortarii unui sirde numere si de calculare a anvelopei convexe [30]; aceste abordari rapide conduc la o complexitateO(n log n).

O problema suplimentara apare ın momentul considerarii spatiilor discrete, ın care trebuie definitconceptul de convexitate discreta [9]. O componenta conexa discreta C este convexa daca pentru oricepereche de puncte P,Q ∈ C si orice scalar α ∈ [0; 1] exista un punct R ∈ C pentru care discul decentru R si raza h/2, construit conform distantei chessboard, include punctul de pe segmentul PQ,dat de αP + (1−α)Q. O consecinta a acestei definitii a convexitatii este aceea ca multimea de punctece formeaza anvelopa convexa discreta nu coincide, ci include multimea de puncte de coordonatediscrete din anvelopa convexa “continua” construita pe baza aceleiasi multimi de puncte discreteinitiale. Pentru cazul planului discret, ın [9] se identifica doua tipuri esentiale de configuratii deneconvexitate, ce trebuiesc identificate ın multimea data de puncte si eliminate (eliminarea presupuneinserarea unui punct suplimentar): configuratiile U si L. Dar acesta operatie nu este altceva decato operatie morfologica de tip totul sau nimic (Hit or Miss) [48], realizata cu masti corespunzatoareconfiguratiilor U, L si a rotitelor acestora.

Cu toata bogatia de metode si algoritmi existenti pentru calculul anvelopelor convexe, literatura despecialitate nu consemneaza nici o realizare de filtre de ordine de tip median bazate pe ordonareapartiala a datelor extrase de fereastra de filtrare din imagine. Putem gasi mai multe argumentepentru justificarea lipsei totale de interes pentru utilizarea acestei tehnici: ın primul rand ordonarease refera la un set mic de valori (vectorii dintr-o vecinatate a pixelului curent), ceea ce poate duce laimposibilitatea gasirii a mai multe “randuri” de anvelope convexe; apoi vectorii au dimensiune maimare ca 2 (cel putin 3, pentru imaginile color), ceea ce face ca algoritmii eficienti de calcul al anvelopeiconvexe sa fie din ce ın ce mai greu de descris; ın fine, este posibil ca multimea de rang maxim (cea mai“centrala” sa contina mai mult de un singur vector, ceea ce face ca sa fie necesara o noua procedurade selectie).

1.2.4 Ordonarea redusa

Ordonarea redusa [3] se bazeaza pe reducerea fiecarei observatii vectoriale (multivariate) la o unicavaloare (scalar) printr-o combinatie a valorilor componentelor observatiilor. Scalarii obtinuti sunt apoiordonati (conform ordinii comune din multimea numerelor reale); ordinea scalarilor determina ordineavectorilor.

Ordonare bazata pe distante

De cele mai multe ori, scalarii si asociati vectorilor xi sunt dedusi pe baza unei distante generalizatela un punct fix specificat xfix, rezultand astfel o forma patratica:

si = (xi − xfix)TA−1(xi − xfix) (1.8)

Matricea patrata p× p A poate fi orice matrice pozitiv semidefinita; ın general este preferata alegereamatricii unitare, ce genereaza metrica Euclidiana, dar este posibila si alegerea matricii de covarianta aobservatiilor (rezultand distanta Mahalanobis) sau a unei matrici diagonale, ce va genera distante Eu-clidiene ponderate. Punctele fixe de interes sunt ın general vectori obtinuti prin prelucrari marginale:

7

fie medie (xfix = xi = xmedie), fie median (xfix = medianxi = xmed). O asemenea ordonare esteinteresanta atata vreme cat vectorul al carui scalar asociat are valoarea minima este cel mai buncandidat, dintre vectorii observatiilor, pentru punctul fix (central) fata de care s-a facut ordonarea.

S-a propus de asemenea folosirea unor distante ponderate de la fiecare vector de culoare din fereastrade filtrare la medianul marginal local m; ponderarea se face prin utilizarea unor matrici diagonale:

si = (xi −m)T

1/wR 0 00 1/wG 00 0 1/wB

(xi −m)

adica

si =(xi1 −m1)2

wR+

(xi2 −m2)2

wG+

(xi3 −m3)2

wB

Ponderile wR, wG, wB sunt astfel alese ıncat sa reflecte importanta fiecarei componente a vectorilor; lafel ca si pentru ordonarea lexicografica, aceste ponderi sunt masuri de activitate locale, ca: intervalulde variatie, varianta, intervalul de variatie normat la medie sau raportul de contrast (varianta normatala medie).

O alta varianta de scalar construit pe baza unor distante este scalarul obtinut ca suma a distantelorde la vectorul dat la toti ceilalti vectori ai setului de ordonat (distanta agregata [3]):

si =n∑j=1

(xj − xi)TA−1(xj − xi) (1.9)

Dupa cum se arata ın [2], [33] medianul setului de date este caracterizat de o distanta agregata minima,indiferent daca ne aflam ın cazul scalar sau vectorial:

xVMF = arg mini=1,n{si} (1.10)

Filtrul care functioneaza dupa acest principiu a fost denumit median vectorial VMF (Vector MedianFilter) [2]; introducerea acestui filtru a constituit ınceputul erei de adevarata prelucrare multicanal asemnalelor vectoriale, fiind primul filtru construit special pentru date multivariate ce utilizeaza ın modintrinsec corelatia dintre canalele semnalului. De fapt, vector medianul [2] nu este decat o redescoperireinginereasca a ceea ce statistica multivariata numea “punct de distanta agregata minima”, punct care ıiintersase pe economisti si planificatori (pentru care determinarea acestuia este cunoscuta ca problemageneralizata a lui Weber [3], de plasare optimala a unui depozit de materiale ce deserveste mai multeuzine).

Principalul dezavantaj al VMF este volumul mare de calcule: pentru a calcula medianul vectorialal unui set de N valori, este necesara calcularea distantelor dintre toate observatiile multimii, deciN(N − 1)/2 distante. Acesta duce la o complexitate O(pN2) a numarului de ınmultiri. O diminuareaa complexitatii calculului VMF se poate realiza prin construirea unei aproximari rapide a distanteiEuclidiene. Aceasta aproximare se bazeaza pe o combinatie liniara a statisticilor de ordine a compo-nentelor vectorului pentru care se calculeaza norma, dupa formula:

‖x‖2 = ap∑i=1

(√i−√i− 1) |x|(i)

cua =

2

1 +

√p∑i=1

(√i−√i− 1)2

8

Pentru cazul vectorilor de culoare, p = 3, a = 0.9398 si norma vectorului de culoare x este data cu oeroare de 1− a (6.019 %) de aproximarea:

‖x‖2 = 0.9398 |x|(1) + 0.3893 |x|(2) + 0.2987 |x|(3) .

Dupa cum se demonstreaza ın [2], distanta Euclidiana (norma L2) este folosita ca baza a VMF da-torita optimalitatii sale pentru un zgomot modelat de o distributie normala; daca distributia devinebiexponentiala, distanta trebuie calculata ca o norma L1[2]. Ideea de modificare a metricii folosite ıncalculul distantei a fost folosita si ın alte implementari (de exemplu metrici din familia de norme Lβ).Ideea a fost extinsa prin propunerea de a folosi o combinare dupa doua norme: fiecare distanta ıntreobservatii este calculata pe baza unei norme Lβ, iar agregarea distantelor se face dupa o norma Lα,producand un scalar de forma:

si =

n∑j=1

( p∑k=1

(xjk − xik)β)1/β

α1/α

(1.11)

Evident, pentru α = β = 1 se obtine medianul vectorial clasic [2]; pentru α, β > 1 se obtine un efectechivalent de netezire si de reducere a zgomotului, iar pentru α < 1, β > 1 filtrul se comporta ca unfiltru de ordonare dupa rang, favorizand diferite statistici de ordine.

Slaba performanta a filtrului VMF (indiferent de norma care genereaza distanta folosita la calcululscalarului si) ın prezenta zgomotului gaussian a dus la ideea combinarii acestuia cu un filtru demediere; iesirea unui asemenea filtru compozit, denumit EVMF (Extended Vector Median Filter) [2]este identica fie cu medianul vectorial VMF, fie cu media marginala, dupa cum aceste puncte suntcele mai centrate (ın sensul distantei agregate minime la observatiile din fereastra de filtrare). Estede asemnea posibila utilizarea a mai multe ferestre de filtrare, partial suprapuse, pentru fiecare pixelal imaginii; ın fiecare asemenea fereastra se calculeaza un median vectorial, iar valoarea filtrata esteobtinuta printr-o serie de comparatii ca una dintre valorile mediane astfel calculate, obtinand efecte deeliminare a zgomotului impulsiv sau de accentuare a contururilor ın imagini nedegradate de zgomot.

Ordonare bazata pe orientare unghiulara

Criteriile de ordonare a observatiilor vectoriale folosite pana ın acest moment au ilustrat doar compo-nenta modul a vectorilor; componenta de tip orientare (unghi) a ramas neexplorata pana ın momentulintroducerii notiunii de filtru [median, ın principiu] directional. Acest tip de filtre, introduse ın [45] sebazeaza pe folosirea ca scalar si pentru ordonarea redusa, a distantei agregate unghiulare a observatiilorvectoriale, deci suma unghiurilor de la fiecare vector la toti ceilalti. Ca si pentru filtrul median vec-torial VMF [2], filtrul directional de baza BVDF (Basic Vector Directional Filter) produce ca iesirevectorul a carui distanta unghiulara agregata este minima. Pentru un asemenea filtru, scalarul deordonare este deci

si =n∑j=1

xixj =n∑j=1

arccos

(〈xi,xj〉‖xi‖ ‖xj‖

)(1.12)

si medianul directional se defineste ca:

xV DF = arg mini=1,n{si} (1.13)

Una dintre motivatiile principale ale considerarii prelucrarilor directionale este legata de natura par-ticulara a unor clase de imagini (sau semnale) multidimensionale, mai precis imaginile color. Pentruculori reprezentate ın spatiul RGB primar, intersectia vectorului de culoare cu planul (triunghiul)Maxwell prezinta o importanta deosebita. Pe de o parte, una dintre masurile de baza de calitate a

9

prelucrarilor imaginilor color este definita ca o eroare patratica medie normalizata a valorilor ın planulMaxwell (aceasta este MCRE, Mean Chromaticity Error); pe de alta parte, dupa cum se arata si ın [8],cromaticitatea unei culori (nuanta si saturatia culorii) este determinata de distantele de la intersectiavectorului de culoare cu planul Maxwell la culorile primare maxim saturate (rosu, verde si albastrupur). Este evident ca acest punct de intersectie depinde numai de orientarea vectorului de culoare sinu de modulul acestuia.

Filtrarea directionala generalizata GVDF (Generalized Vector Directional Filter) [45], este o extinderea BVDF ce selectioneaza mai multe observatii ca iesire posibila a filtrului, observatii ce au cele mai micidistante unghiulare agregate[47]; ın esenta, aceasta selectie multipla permite ca sa se realizeze o a douaselectie a unui singure observatii de iesire, prin operatii de distanta (modul). Abordarea directionalaa fost folosita si pentru detectarea contururilor ın imagini color si pentru realizarea segmentarii peregiuni a imaginilor color prin ıncorporarea informatiei de orientare (unghi fata de vecini) la descriereapixelilor.

Ordonare bazata pe distante si orientare unghiulara

Comportarile relativ complementare ale celor doua tipuri esentiale de filtre vectoriale (cu ordonaredupa distante si cu ordonare dupa directie) ın ceea ce priveste eficienta ın zgomotele principale(impulsiv si gaussian) a condus la ideea combinarii celor doua tipuri de prelucrari, ıntr-o abordaremixta modul-directie. O prima etapa a combinarii celor doua principii a fost introdusa prin aplicareasecventiala a unei preselectari dupa directie a vectorilor (GVDF) urmata de o prelucrare dupa modula acestora (fie scalara, dupa componenta de luminanta, fie ca VMF).

Un alt mod de a lua ın calcul distantele ”ın valoare” si unghiulare consta sin construirea unui scalar sicare sa integreze atat informatia directionala cat si informatia de modul a vectorilor ce se prelucreaza.Modelul cel mai general folosit este o combinatie exponential convexa a distantelor agregate unghiularesi Euclidiene ıntre vectorii setului:

si =

n∑j=1

xixj

p n∑j=1

‖xi − xj‖

1−p

(1.14)

Filtrul realizat prin ordonarea vectorilor dupa scalarul (1.14) a fost numit DDF(Distance DirectionalFilter) si este generalizarea unui filtru simplu definit anterior cu p = 0.5. Valoarea parametrului p careasigura rezultate optimale pentru o gama larga de distributii de zgomot este p = 0.75, deci atribuindo pondere mai mare caracterului directional.

O alta modalitate de a integra prelucrarile directionale si de distanta este de a comuta ıntre iesireafiltrului VDF si VMF. O posibilitate este de a construi iesirea filtrului pe directia vectorului VDF sicu modulul vectorului VMF:

xout = xV DF‖xVMF ‖‖xV DF ‖

In plus, se poate introduce un grad suplimentar de “finete” a comparatiei, luand ın calcul si mediamarginala a observatiilor, vectorul de iesire fiind pe directia VDF si cu modulul vectorului VMF saumediei marginale, dupa cum unul dintre acesti vectori este cel mai central situat, ın sensul distanteiagregate minime la observatiile setului de prelucrat.

10

Ordonare bazata pe proiectii

Metodele de ordonare redusa prezentate pana ın prezent s-au bazat esential pe considerarea pozitiilorrelative a vectorilor de ordonat ın spatiul original de reprezentare a acestora (spatiul esantioanelor), fieprin masurarea distantelor, fie prin masurarea unghiurilor, fie prin considerarea ambelor. O variantanoua de determinare a unor scalari si de ordonare a vectorilor pleaca de la ideea modificarii spatiuluide reprezentare a acestora; o reprezentare echivalenta ıntr-un spatiu de dimensiune mai mica va ducela reducerea dimensiunii vectorului, iar, prin repetare, se poate ajunge la un scalar. O asemeneametoda a fost numita metoda proiectiva.

Observatia initiala se raporteaza la utilizarea triunghiului (planului) Maxwell ın spatiul RGB primar.Dar acest punct de intersectie este definit de numai doua coordonate independente, si nu de trei,precum culoarea din care provine, si poate fi considerat ca proiectia vectorului de culoare pe planulMaxwell. Repetarea acestei proiectii ın plan, pe “dreapta Maxwell” (definita de ecuatia x1 + x2 = 1)va reduce ınca o data dimensiunea vectorului, pana la un scalar.

In cazul general, pentru un vector p dimensional, x = (x1, x2, ..., xp), vom defini xk, vectorul dupa ak-a proiectie (compusa dintr-o rotatie si o translatie, deci o transformare afina); proiectia se definesteastfel ıncat primele k componente ale vectorului xk sa fie nule, deci x1 = (0, x11, ..., x1p−1), xk =(0, 0, ..., xk1, ..., xkp−k). Ultima proiectie va produce vectorul xp−1 = (0, ..., 0, xp1) ce are o unicacomponenta nenula. Aceasta unica componenta nenula este scalarul dupa care se face ordonarea;vectorul al carui scalar este medianul tuturor scalarilor este definit ca medianul vectorial.

Revenind ın cazul particular al vectorilor de culoare (cu trei componente, pe care le vom considera(R,G,B)), proiectiile vor produce scalarii

sR =(1 + 1√

3)(G+B − 1) + 2√

3R

(1 + 1√3)(G+B − 1)− 2√

3R

sG =(1 + 1√

3)(R+B − 1) + 2√

3G

(1 + 1√3)(R+B − 1)− 2√

3G

sB =(1 + 1√

3)(R+G− 1) + 2√

3B

(1 + 1√3)(R+G− 1)− 2√

3B

dupa cum prima rotatie este dupa axa R, G, sau B. Alegerea unui anume scalar se face adaptiv,conform criteriilor locale de activitate a fiecarei componente.

Filtrul median prin proiectii iterative pe planul Maxwell se comporta mai bine decat filtrul VMFclasic ın conditii de zgomot mic (impulsiv si mixtura); ın plus, si volumul de calcule necesare pentrua calcula scalarul este extrem de mic – filtrul cu proiectii iterative necesita 27 ınmultiri pentru fiecarepixel (considerand o fereastra patrata de 3 x 3 pixeli) iar filtrul VMF necesita 144 ınmultiri (si unnumar mult mai mare de adunari).

Ordonare bazata pe curbe de umplere a spatiului

In prelucrarea imaginilor, problema reducerii unor obiecte vectoriale la scalari nu este noua, si aaparut odata cu considerarea primelor metode de codare a imaginilor, ca aplicatii directe ale metodelorexistente pentru semnalele unidimensionale. Aplicarea unei asemenea metode necesita transformareasemnalului bidimensional imagine ıntr-un semnal unidimensional prin parcurgerea corespunzatoarea tuturor pixelilor. Parcurgerea (sau baleierea imaginii) ınseamna de fapt stabilirea unei ordini de

11

Fig. 1.2: Curbe de umplere a spatiului - cazul bidimensional.

vizitare a fiecarui punct a grilei rectangulare de reprezentare a imaginii, deci ordonarea unor vectoribidimensionali (ale caror componente sunt coordonatele pixelilor). O asemenea parcurgere a fostformalizata matematic ca o curba de umplere a spatiului [9]. O curba de umplere a spatiului T esteo aplicatie bijectiva ce asociaza fiecarui punct din Z2 (punctul din plan) un numar natural (numarulde ordine):

T : K ⊂ Z2 −→ N, T (xk) = nk

Curba de umplere a spatiului va trece prin fiecare punct al multimii baleiate o singura data (nu se vaautointersecta). O clasa particulara a acestor curbe are proprietatile suplimentare de autosimilaritate(sunt fractali) si de pastrare a corelatiei spatiale (puncte care sunt vecine pe curba, sunt vecine ınplan). Exemplul cel mai cunoscut de astfel de curba este curba Hilbert, cunoscuta ın doua variante:curba Peano (sau curba Hilbert ın U) si curba Morton (sau curba Hilbert ın Z) [9], [48]. Denumireacelor doua curbe provine de la forma celulei de baza (reprezentate ın figura 1.2.4).

Proprietatile de bijectivitate a curbelor Hilbert (si ın general a curbelor de umplere a spatiului) au fostpropuse pentru ordonarea redusa a vectorilor [40]: fiecarui vector i se asociaza indicele punctului de pecurba de umplere a spatiului corespunzator. Scalarii (indicii de pe curba) sunt ordonati, iar vectorulal carui indice este medianul valorilor indicelor extrase este ales ca median a setului de vectori.

Problema esentiala legata de utilizarea unor curbe de tip Hilbert pentru calcularea scalarilor de or-donare redusa este aceea a modificarii structurii de vecinatate a spatiului indicilor fata de spatiul initial:puncte vecine din spatiul initial nu mai sunt vecine ın spatiul indicilor, si reciproc [40]. Aceasta duce laaparitia de artefacte pe imaginile prelucrate, chiar la nivele mici de zgomot. Pentru a evita asemeneaefecte trebuiesc folosite curbe care sa pastreze cat mai bine structura de vecinatate a spatiului vecto-rial initial, si deci corelatia dintre vectori. Este evident ca curba Hilbert ın U (Peano) este mult maipotrivita din acest punct de vedere decat curba Hilbert ın Z (Morton). Aceeasi observatie conduce ladefinirea a unor curbe cu aspect “spiralat” [40].

12

Esential, problema care va decide eficienta practica a unei curbe (pentru probleme de filtrare a imag-inilor color, de exemplu) este ınsa problema calculului indicelui pe curba al unui anume vector. Trebuiesa remarcam ca solutia de implementare cu un LUT nu este realizabila: pentru vectori p dimensionaliexprimati cu b biti pe fiecare componenta, tabelul de echivalenta ar trebui sa contina 2pb numere de pbbiti (pentru imagini color obisnuite acesta ınseamna 224 numere de 3 octeti, deci 12 MB). Atat pentrucurba Peano, cat si pentru curba definita de [40], trecerea de la cazul plan de definire la vectori dedimensiune superioara implica o procedura recursiva, cu decizii multiple. Spre deosebire de acesta,pentru curba Morton, indicii se calculeaza extrem de simplu: forma binara a indicelui pe curba a unuivector se obtine prin ıntreteserea formelor binare a componentelor vectorului; daca componenta xi avectorului p dimensional este exprimata ın forma binara ca xi,b−1xi,b−2...xi,1xi,0, atunci forma binaraa indicelui este [9]:

x1,b−1x2,b−1...xp,b−1x1,b−2x2,b−2...xp,b−2...x1,0x2,0...xp,0

Diversitatea de metode de ordonare prezentate ın acest capitol ofera o perspectiva asupra posibilitatilorde implementare a filtrelor de ordonare (si ın particular filtrul median) pentru imaginile vectoriale(color). Eficienta acestor filtre este asemanatoare analoagelor lor scalare si ısi arata limitele ın cazulfiltrarii unor zgomote de tip mixtura. Ceea ce se impune este deci modificarea structurii de filtrareprin considerarea tuturor vectorilor din fereastra de filtrare.

13

Capitolul 2

FILTRAREA NELINIARA FARAPRINCIPII DE ORDONARE

Dupa cum am mai amintit, filtrarea neliniara poate apare ca o consecinta a mai multor procedeede prelucrare: fie prelucrari intrinsec neliniare (asa cum este ordonarea valorilor extrase de fereastrade filtrare, ca ın cazul filtrelor cu ordonare dupa rang sau a L-filtrelor), fie adaptarea unei structuride prelucrare care, intrinsec, nu este neliniara. Adaptarea se refera la modificarea parametrilor dedefinitie a unui filtru ın functie de caracteristicile locale ale semnalului (imaginii) de prelucrat. Inmod uzual, un filtru, interpretat ca o operatie locala (de vecinatate), este definit de o fereastra defiltrare (multime de puncte ce defineste vecinatatea punctului curent de prelucrat) si de o multimede coeficienti (sau ponderi), atasati pozitiilor ferestrei de filtrare. Adaptarea se poate referi fie lamodificarea coeficientilor de definitie a filtrului, fie la modificarea formei ferestrei de filtrare.

In cele ce urmeaza vom considera filtrele neliniare obtinute ca urmare a adaptarii unei filtrari liniare;daca {xj} este multimea celor n vectori (valori ale pixelilor) din fereastra de filtrare curenta, atunciiesirea filtrului pentru pozitia data este combinatia liniara ponderata a acestor valori:

y =Card(W )∑j=1

wjxj , xj ∈W (2.1)

Pentru o filtrare de netezire (deci de reducere a zgomotului), coeficientii wj trebuie sa satisfaca [8],[18] conditia de normare (care asigura invarianta pentru zone uniforme):

Card(W )∑j=1

wj = 1 (2.2)

Adaptarea semnifica ca multimea coeficientilor filtrului este diferita, de la un punct la altul al imaginiisi ın functie de continutul acesteia, si deci wj = wj(m,n,x(m,n)), sau ca vecinatatea se modifica,dependent de punctul curent de prelucrare, W = W (m,n). Ceea ce trebuie ınsa remarcat este faptulca cele doua aspecte ale adaptarii nu sunt independente: un coeficient de ponderare extrem de mic(la limita nul) semnifica neluarea ın calculul iesirii y a filtrului a valorii respective, deci, echivalent,eliminarea pozitiei corespunzatoare din fereastra de filtrare.

Problema determinarii adaptive a ponderilor asociate unei ferestre de filtrare de forma impusa poate fiabordata din mai multe puncte de vedere: coeficientii pot fi dependenti (ın mod explicit) de distanteledintre vectorii selectati de fereastra de filtrare, prin ceea ce a fost denumit DDMF - Distance De-pendent Multichannel Filter ; deducerea coeficientilor se poate face prin abordari de clustering sau deestimare statistica; coeficientii pot fi dedusi printr-o abordare bazata pe integrarea logicii vagi (fuzzy)

14

ın abordarile clasice. De asemenea, se pot avea ın vedere si metode bazate pe calculul unei ferestre defiltrare adaptive.

2.1 Filtre dependente de distanta

Prelucrarile cunoscute sub numele de filtrari cu coeficienti dependenti de distanta, si denumite DDMF- Distance Dependent Multichannel Filter [16] sau MDF - Multichannel Distance Filter [14] reprezintao clasa de filtre adaptive, bazate pe (2.1), ın care coeficientii de ponderare a vectorilor sunt dedusi ınfunctie de distantele relative dintre acestia (deci conform distributiei lor ın spatiul de reprezentare).Spatiul de reprezentare a vectorilor (pentru cazul imaginilor color) este spatiul RGB primar, chiardaca distantele euclidiene dintre vectori nu sunt ın concordanta cu diferentele perceptuale de perceperea culorilor reprezentate de acestia. In general, ceea ce se deduce direct pentru fiecare vector este opondere a contributiei sale la iesirea filtrului, aj , ponderi care, pentru setul de n vectori ai ferestreide filtrare, nu respecta conditia de normare a coeficientilor, impusa de (2.2). Indeplinirea conditieide normare este asigurata prin construirea ponderilor de filtrare ca raportul dintre coeficientii deponderare si suma acestora:

wj =ajn∑i=1

aj

(2.3)

2.1.1 Folosirea distantei euclidiene dintre vectori

Modul de constructie a coeficientilor de ponderare a vectorilor este ın principiu inspirat din modalitatilede ordonare redusa a respectivilor vectori, deja discutate ın capitolul anterior. In general, coeficientulde ponderare este o functie dependenta de un scalar dj , de tip scalar de ordonare (sj). Functiile detip polinomial au fost folosite cu succes de majoritatea cercetatorilor. Cea mai simpla functie propusaeste puterea r a scalarului:

aj =1drj

(2.4)

Aceasta abordare a fost introdusa ın [14] (ANL1 - Adaptive Non-Linear), [7] (MDF1) si [16] (DDMF2).Scalarul de tip distanta dj trebuie sa exprime situarea vectorului curent xj , caruia ıi este atasat, fata deiesirea dorita a filtrului, si deci trebuie sa fie cu atat mai mare cu cat vectorul curent este mai departatde valoarea corecta (deci mai afectat de zgomot). Pentru a satisface aceasta cerinta, ın [14] si [7] sefoloseste distanta euclidiana agregata (suma distantelor de la vectorul curent la toti ceilalti vectori aiferestrei de filtrare); ın [15] este folosit acelasi model pentru prelucrarea semnalelor unidimensionalemulticanal (semnale seismice):

dj =n∑i=1

‖xi − xj‖ (2.5)

In [16] se propune folosirea distantei de la vectorul curent la un punct fix, ce este ın general un estimatormarginal al iesirii dorite (ın general, medianul marginal multicanal, dar si vectorul ce corespundepozitiei ın care se face filtrarea, deci vectorul din originea ferestrei de filtrare):

dj = ‖xfix − xj‖ (2.6)

Pentru a evita cazurile de nedeterminare ın evaluarea lui aj (ce pot apare cand dj = 0), ın [7] si [16]s-a propus modificarea distantei prin adunarea unei constante ε, care este fie unitara (ε = 1) [7] pentruMDF2, fie este foarte mica (ε −→ 0) [16] pentru DDMF2:

dj = ‖xfix − xj‖+ ε (2.7)

15

Testele efectuate asupra comportarii acestui tip de filtre ın prezenta a diferite distributii de zgomotau condus la concluziile folosirii unor valori specifice ale puterii r: r = 1 pentru zgomot uniform,r = 0 pentru zgomot gaussian (ceea ce ınseamna de fapt ca ponderile tuturor vectorilor sunt egale, sifiltrul obtinut este de fapt filtrul de mediere marginala), r = −2 pentru zgomot de tip laplacian saucu alte distributii de tip “long tail” (cu coada lunga). Adaptarea propriu-zisa a puterii r ın functie decaracteristicile locale ale imaginii (semnalului) - deci ın interiorul ferestrei de filtrare - se poate faceconform caracteristicilor statistice locale de ordinul doi ale semnalului [6]. Filtrul propus, AMDF -Adaptive Multichannel Distance Filter, se bazeaza pe o extindere multicanal a unui algoritm clasic deestimare a variantei locale a semnalului util si a zgomotului [28], [55]. Pe fiecare canal (deci pe fiecareplan de culoare a imaginii color) se face o estimare a variantei locale de pe canalul j, ın pozitia curentade filtrare, σ2

xj , prin:

σ2xj =

n∑i=1

x2ij − 1

n

(n∑i=1

xij

)2

n− 1Pentru fiecare canal, se stabileste un coeficient de importanta a efectului zgomotului fata de variatiileproprii ale semnalului:

cj = 1−σ2xj

σ2nj

iar pe baza acestui coeficient se alege puterea r corespunzatoare:

r =

{0, daca min{cj} ≥ 0min{cj}, ın rest.

(2.8)

Plecand de la ideea folosirii de distante la puncte fixe (2.6), ın [16] s-a reluat ideea din [44], de a sumadistantele la mai multe puncte fixe reprezentative, ca medianul marginal, media marginala si punctulcentral (din originea ferestrei de filtrare), rezultand un filtru numit DDMF3, cu o distanta:

dj = ‖xmedie − xj‖+ ‖xmedian − xj‖+ ‖xcentru − xj‖ (2.9)

Scalarul de distanta dj asociat fiecarui vector exprima calitatea sa (deci masura ın care valoarea sa esteneafectata de zgomot); exprimarea unei asemenea masuri trebui ınsa sa tina seama si de ceilalti vectoridin fereastra de filtrare; ın acest context scalarul propus ın [14] pentru filtrul MDF2 este construit casuma distantelor dintre toti vectorii ferestrei de filtrare, mai putin vectorul curent:

aj =12

n∑i=1

di − dj

unde dj este distanta euclidiana agregata din (2.5).

O alta functie propusa pentru transformarea distantelor dintre vectorii ferestrei de filtrare ın ponderirelative individuale este o functie de tip exponential [16], determinata de parametrii α > 1 si 0 < β < 1:

aj = exp(− djβdmax

lnα)

Constanta dmax este determinata ca fiind distanta maxim posibila dintre vectori pentru semnalulstudiat (ın cazul imaginilor color reprezentate cu 8 biti pentru fiecare plan de culoare, aceasta estedmax = 8 · 255 ·

√3). Acesta relatie exprima principiul general conform caruia vectorii ce au asociate

distante mici trebuie sa aiba asociate ponderi mai mari (mai ales ın cazul ın care se doreste eliminareaimpulsurilor de zgomot si pastrarea claritatii tranzitiilor din imagine). Testele experimentale au aratatca o combinatie eficienta de parametri este α = 2 si β = 0.05 [16].

16

2.1.2 Folosirea distantei unghiulare dintre vectori

Dupa cum am aratat si ın sectiunea privind filtrarea bazata pe ordonare directa a vectorilor, ın cazulimaginilor color, informatia de culoare (crominanta, saturatie) este mai importanta decat informatia deintensitate luminoasa, si deci pare naturala folosirea unor criterii de comparatie (ordonare, ponderare)a vectorilor care sa ia ın considerare aceasta informatie directionala. Aceasta este abordarea numitaVector Directional [46], ın care distanta dintre vectori este ınlocuita cu unghiul dintre respectiviivectori. O asemenea abordare a fost adoptata ın [38]; pe baza distantei agregate unghiulare dj (1.12)sau (2.10) dintre vectori se deriva coeficienti aj ce exprima ponderea cu care vectorul xj participa laiesirea filtrului.

dj =n∑i=1

xixj =n∑i=1

arccos

(〈xi,xj〉‖xi‖ ‖xj‖

)(2.10)

In [38] se propune FVDF - Fuzzy Vector Directional Filter, pentru care fiecare coeficient de ponderarea vectorilor este dat de o formula ce grupeaza abordarile polinomiala si exponentiala :

aj =1

1 + exp(drj)

Pentru rezultate optime, parametrul de control r are valorile 1 sau 2. Aceasta constructie impune douacomentarii: ın primul rand, filtrul vector directional de baza (BVDF) se poate obtine selectand doarvectorul a carui coeficient aj este maxim; ın al doilea rand, termenul de fuzzy ce apare ın denumireafiltrului nu exprima neaparat existenta unor inferente logice a unui set de reguli, ci se justifica prinnormarea (2.3) care produce numere subunitare pozitive, ce pot fi interpretate ca grade de apartenentaale fiecarui vector din fereastra de filtrare la clasa “valoare corecta”.

O alta abordare bazata de distanta agregata unghiulara dj este prezentata ın [34] si se bazeaza peconstructia unor coeficienti de ponderare dati de:

aj =max{di} − dj

max{di} −min{di}

Acest filtru a fost denumit ANNMF - Adaptive Nearest Neighbor Multichannel Filter. O modificare asa se poate obtine daca ın locul distantei unghiulare agregate se foloseste doar unghiul dintre vectorulcurent si un vector de referinta (2.11) (deci acelasi principiu ca si ın cazul folosirii distantei euclidiene).Vectorul de referinta (daca nu este chiar centrul ferestrei de filtrare) se calculeaza ın general ıntr-oalta fereastra de filtrare (de dimensiune mai mica decat fereastra de filtrare curenta); de aceea filtrulastfel construit se numeste DWANNMF - Double Window Adaptive Nearest Neighbor MultichannelFilter [34]:

dj = xfixxj (2.11)

In fine, ca si ın cazul ordonarii vectorilor, se pot considera abordari mixte, distanta - unghi, deciintegrarea ıntr-un singur scalar (printr-un produs) a distantelor agregate unghiulare si euclidiene [19],[20]. O asemenea varianta este propusa ın [16] ca DDMF4:

dj =

(n∑i=1

xixj

)·(

n∑i=1

‖xi − xj‖)

sau ca

dj =

(n∑i=1

xixj

)· (‖xmedie − xj‖+ ‖xmedian − xj‖+ ‖xcentru − xj‖)

17

2.2 Filtrarea prin estimare statistica

Filtrarea poate fi interpretata si ca o estimare [statistica] a valorii corecte a pixelului curent, ınconditiile ın care se dispune de observatii perturbate de zgomot (pixelul curent si vecinii sai dinimaginea degradata). Una dintre metodele simple de determinare a unor estimati ai unor marimistatistice pe baza unui set unic de observatii sunt cunoscute ın statistica ca metode de reesantionarea datelor [27]. Asemenea metode (relativ similare) sunt metodele jack-knife si bootstrap, folosite maiales pentru construirea de intervale de ıncredere ale estimatelor. Cea mai rapida dintre cele douametode este metoda jack-knife, pe care am folosit-o ın construirea unor filtre mediane vectoriale.

Principiul tehnicii jack-knife este urmatorul: sa presupunem ca se doreste determinarea unui es-timat θ al unui parametru oarecare θ al unei populatii formate din n observatii p dimensionaleP = {x1,x2, ...,xp}. Din populatia initiala se construiesc n noi populatii, fiecare dintre acesteacontinand toate observatiile initiale, mai putin observatia xi:

Pi = P \ {xi}, i = 1, 2, ..., n

Pentru fiecare noua populatie de n − 1 observatii se construieste un estimat θi, iar pe baza tuturorcelor n estimate astfel calculate, se construieste estimatul jack-knife θjk printr-o operatie de medierearitmetica.

θjk =1n

n∑i=1

θi

Aplicatia propusa a acestei tehnici este realizarea unui filtru median vectorial; aceasta ınseamna caestimatele θi sunt mediane ale vectorilor ce formeaza populatiile Pi. Aceste estimate pot fi obtinuteprin orice fel de tehnica de tip median vectorial (deci median marginal, sau VMF, sau VDF, ...).Complexitatea algoritmica a noului filtru este de acelasi ordin de marime cu a filtrelor de baza princare se calculeaza estimatele θi. Noul filtru este mult mai robust ın prezenta zgomotului gaussian,datorita medierii estimatelor partiale.

In [22], [24], [21] se propune utilizarea unui filtru MTM - Modified Trimmed Mean vectorial (multi-variat), ca extensie directa a filtrului scalar analog; filtrul scalar mediaza un numar dat de statistici deordine situate simetric fata de median. Extensia vectoriala a MTM este bazata pe ordonarea redusaa vectorilor din fereastra de filtrare prin distante fata de un punct fix (medianul marginal), calculateca distante Mahalanobis (C fiind matricea de covariatie locala):

si = (xi − xmed)TC−1(xi − xmed)

Esenta problemei este faptul ca matricea C este necunoscuta. Estimarea ei prin medie si variantelocale este ineficienta, deoarece acestea nu sunt estimate robuste, si valorile acestora sunt puternicinfluentate de prezenta chiar a unui singur vector aberant (“outliar”). In [22], [24], [21] se analizeazadiferite metode, directe si iterative, de estimare a matricii de covariatie si se studiaza robusteteaestimatelor obtinute si a filtrelor realizate pe baza lor la diferite tipuri de zgomote.

O alta abordare a cresterii robustetii structurilor de filtrare este aceea de a ıncerca determinarea unuiestimat liniar (optim ın sensul minimizarii unei functii de cost patratic a erorii de estimare); ın acestcaz estimatul este [43]:

x =∞∫−∞

xf(x|y)dx =

∞∫−∞

xf(x,y)dx

f(y)(2.12)

In cazul general, distributia zgomotului ce a afectat imaginea nu este cunoscuta, si densitatile deprobabilitate implicate ın (2.12) nu pot fi determinate prin tehnici parametrice; atunci solutia consta

18

ın determinarea lor prin tehnici neparametrice, pe baza multimii observatiilor. Metoda de estimarefolosita ın [35] si [36] este o estimare cu nuclee (“kernel estimator”). Astfel, functia de densitate deprobabilitate necunoascuta f(z) este estimata neparametric din setul de n observatii multivariate (dedimensiune p) independente (realizari particulare ale procesului aleator) prin:

f(z) =1n

n∑i=1

(hi)−pK(

z− zihi

)(2.13)

Functia K : Rp −→ R este nucleul de estimare (functie pozitiva, centrata pe 0, de arie unitara asubgraficului); ın [36] sunt folosite nuclee de estimare exponentiale:

K(z) = e−|z|

K(z) = e−12zT z

Scalarii hi sunt parametrii de netezire, definiti ın functie de distanta euclidiana agregata dintre vectorulcurent zi si ceilalti vectori ai multimii de observatii; acestia au forma:

hi = n− kpAi = n

− kp

n∑j=1

‖zj − zi‖

(2.14)

Folosind expresiile (2.13) si (2.14) ın (2.12), si folosind observatiile din imaginea cu zgomot xi obtinem:

x =n∑i=1

hi−pK

(x−xihi

)n∑j=1

hj−pK(

x−xihj

)xi

Acest estimat liniar corespunde unei combinatii liniare a vectorilor ferestrei de filtrare cu coeficientiide ponderare

wi = hi−pK

(x− xihi

)(2.15)

In [36] sunt propuse doua extensii ale acestui filtru, rezultate direct din aplicarea teoriei estimarii:ın primul rand s-a introdus un factor suplimentar de reglaj prin varierea coeficientilor de netezire anucleelor de estimare dupa o putere r, caz ın care ponderile filtrului liniar din (2.15) devin:

wi = hi−pK

(x− xihri

)

Un estimator cu o calitate superioara se poate obtine printr-o tehnica de filtrare cu fereastra dubla(DW - Double Window), prin care fiecare observatie zgomotoasa din fereastra de filtrare este ınlocuitade un median vectorial (marginal sau VMF) al valorilor dintr-o fereastra mai mica centrata ın punctulrespectiv. Desi aceasta abordare este foarte robusta si permite realizarea de filtre cu performante bunede rezistenta la diferite tipuri de zgomote (impulsive si mixturi), complexitatea unui asemenea filtruo depaseste pe cea a abordarilor ce nu folosesc estimarea.

2.3 Filtrarea cu vecinatati adaptive

Dupa cum am aratat ın introducerea acestui capitol, adaptarea se poate referi fie la modificareacoeficientilor de definitie a filtrului, fie la modificarea formei ferestrei de filtrare. Modificarea formeiferestrei de filtrare este ın fapt o modalitate de a selecta (sau a ignora) anumiti vectori din vecinatatea

19

pixelului curent prelucrat. Realizarea acestei trieri se poate realiza prin doua metode: dintr-o fereastrade filtrare de forma fixa se rejecteaza vectorii cu valori aberante contextului local sau fereastra defiltrare este determinata pentru fiecare punct al imaginii de prelucrat.

Prima abordare ce conduce la o fereastra de filtrare de forma adaptiva este de a selecta doar aceivectori suficient de apropiati de punctul curent (pentru care se face prelucrarea). Aceasta metodaa fost denumita metoda celor mai apropiati vecini, NN - Nearest Neighbour [12], [23]. Dupa cumse sugereaza prin aceasta denumire, alegerea vectorilor corecti se face dupa un criteriu de distantaminima: sunt pastrati doar acei vectori care sunt cei k cei mai apropiati de punctul central [12] sau acaror distanta la punctul central este mai mica decat un prag fixat [23]. Cu vectorii astfel selectati seefectueaza o prelucrare simpla (ın general o operatie de mediere sau de median marginal), robusteteafiind asigurata de rejectarea initiala a valorilor aberante.

Determinarea ferestrei de filtrare dupa specificul local al punctului de prelucrat (si deci, implicit,determinarea a cate unei ferestre de filtrare pentru fiecare punct al imaginii de prelucrat) a fostdenumita filtrare cu vecinatati adaptive [32], [39], [10]. Esenta acestei metode este de a determina,pentru fiecare pixel al imaginii de prelucrat (color sau cu nivele de gri) o zona relativ uniforma, conexa,printr-o tehnica de crestere a regiunilor [11], [18], [52] (folosita ın mod uzual la segmentarea orientatape regiuni a imaginilor). Avantajul determinarii unei asemenea zone este dublu: pe de o parte suntrejectate valorile aberante (de tipul punctelor afectate de zgomot impulsiv), iar pe de alta partefiltrul de netezire realizat cu aceste vecinatati va pastra extrem de bine contrastul contururilor dinimagine (atata vreme cat regiunile uniforme nu contin pixeli aflati de o parte si de alta a respectivelorcontururi). Operatia propriu-zisa de filtrare este o operatie de mediere simpla [32], [10] sau mediereponderata cu coeficienti adaptivi [39].

Principalele probleme ridicate de acesta metoda de filtrare sunt cele de complexitate a calculului:pentru fiecare pixel al imaginii se creste o regiune ce are ca germene punctul respectiv (asadar com-plexitatea este mult mai mare decat la o operatie de segmentare prin cresterea regiunilor, ın carenumarul de germeni este mult mai mic decat numarul de puncte al imaginii). Pentru a asigura orelativa eficienta a algoritmului, s-a propus introducerea unei limite superioare a dimensiunii regiunii(Nmax pixeli), ımpiedicand astfel extinderea ferestrelor de filtrare ın platourile uniforme foarte ıntinse;ın acelasi timp o dimensiune minima (Nmin) este impusa pentru a avea suficiente valori pe baza carorasa se realizeze estimarea valorii corecte.

2.4 Filtrarea prin tehnici de clustering

O abordare hibrida de determinare atat a unor ponderi cat si a unei ferestre de filtrare specifice fiecaruipunct a fost propusa sub numele de filtrare prin clustering. Ideea esentiala este ın continuare aceea de asepara o macar o parte din valorile aberante ce apar ıntr-o fereastra de filtrare fixa (deci ın vecinatateapixelului curent prelucrat) si de a aplica o netezire valorilor ramase. O asemenea tehnica sta la bazafiltrarii cu vecinatati adaptive sau a filtrelor de tip NN (Nearest Neighbour), prezentate anterior.Abordarea propune realizarea unei partitionari ın trei clase a vectorilor din fereastra de filtrare; celetrei clase corespund pozitionarii vectorilor pe care, ın limbaj natural, am putea sa ıi numim centrali,extremali superior si extremali inferor. Din punctul de vedere al statisticilor de ordine, putem consideraca vectorii din clasa centrala sunt estimate ale mediei sau medianului vectorial, iar vectorii din celedoua clase extreme sunt estimate ale minimului si maximului local.

Pentru realizarea partitionarii ın trei clase a vectorilor selectati de fereastra se va folosi un algoritmde clustering, iterativ sau ierarhic. Fiecare clasa a partitiei (multime de vectori selectionati) estecaracterizata de ceea ce se numeste vector prototip (sau centroid), obtinut ca medie aritmetica avectorilor ce apartin clasei respective. Iesirea filtrului de clustering este prototipul clasei centrale, sau

20

vectorul cel mai apropiat de prototipul clasei centrale. Efectele de netezire ale acestui filtru sunt usor dedemonstrat: impulsurile de zgomot sunt eliminate prin separarea vectorilor ın clase si alegerea ca iesirea unui reprezentant al clasei centrale (deci cea mai ındepartata de extreme) si calcularea prototipuluiclasei centrale se face printr-o mediere ce reduce efectul zgomotului gaussian aditiv. Global, filtrareapoate fi caracterizata ca un median ponderat, pastrand contrastul frontierelor imaginii. Comportareaacestui filtru ın prezenta mixturilor de zgomot (gaussian si impulsiv) este superioara filtrelor medianvectorial clasice (vector median VMF, median marginal).

2.5 Integrarea logicii vagi ın adaptarea filtrelor

Logica vaga (fuzzy logic) a fost introdusa la sfarsitul anilor 1960 [54] ca o ıncercare de a manipulaincertitudinea si nedeterminarea din descrierile semantice ale lumii reale; sunt clasice exemplele privindinterpretarea conceptelor de ınaltime sau greutate a unei persoane, mai ales prin prisma dificultatiiadaptarii logicii clasice binare la o realitate graduala [54], [41]. O multime vaga nu este altceva decato functie ce asociaza fiecarui element al universului un numar pozitiv subunitar.

La aceasta definitie a multimilor vagi merita adaugat comentariul din [5]. Conform definitiei, oricefunctie reala cu valori in intervalul [0, 1] este o multime vaga (fuzzy). In timp ce aceasta este adevaratdintr-un punct de vedere matematic formal, multe functii ce satisfac aceasta conditie nu pot fi in-terpretate corespunzator ca realizari ale unei multimi vagi conceptuale. Cu alte cuvinte, functiile cetransforma un univers in intervalul unitar pot fi multimi vagi, dar devin multimi vagi atunci si numaiatunci cand se potrivesc cu o descriere semantica intuitiva plauzibila a proprietatilor imprecise aleobiectelor din univers.

Una dintre principalele intrebari ridicate de acest mod de reprezentare priveste relatia vagului cuprobabilitatea, si mai precis, daca multimile vagi sunt doar o deghizare ingenioasa pentru modelelestatistice. Raspunsul negativ la aceasta problema rezulta evident dintr-un exemplu [5]. Fie universulde obiecte format din multimea tuturor lichidelor si fie multimea vaga L={toate lichidele potabile (cepot fi baute)}. Dupa o saptamana petrecuta in desert fara apa, calatorul insetat descopera doua sticleperfect opace A si B, marcate cu “A: apartenenta (A ın L) = 0.91” si “B: probabilitate (B ın L) =0.91”, din care trebuie neaparat trebuie sa aleaga una pe care sa o bea. Problema este deci alegereacorespunzatoare a sticlei. A poate contine de exemplu apa de balta sau mlastina, excluzand desigurposibilitatea existentei unui modelator fuzzy Machiavelic, si nu acid clorhidric. Deci apartenenta de0.91 inseamna ca continutul lui A este destul de similar cu lichidele perfect potabile (in speta apapura). De cealalta parte, probabilitatea de 0.91 ca B sa fie potabila inseamna ca, dintr-un sir lung deexperimente, continutul lui B va fi potabil in 91% din cazuri; in restul cazurilor, adica la o incercaredin zece, continutul sticlei putand fi chiar mortal.

O alta fateta a acestui experiment implica ideea de observatie. Daca examinam continutul lui A si B sidescoperim de exemplu ca A contine bere si B acid clorhidric, dupa observatie, gradul de apartenentaa lui A nu se modifica, in timp ce probabilitatea lui B devine 0. In fine, care ar fi efectul schimbariivalorilor numerice la 0.5 ? Majoritatea persoanelor ar bea din B, cu o sansa din doua ca lichidul safie potabil, deoarece un grad de apartenenta atat de mic indica in principiu un lichid nepotabil (daraceasta depinde in intregime de functia de apartenenta a multimii vagi, ceea ce conduce din nou laobservatia privind posibilitatea de a interpreta orice functie cu valori in intervalul unitar ca o multimevaga).

Deci, cele doua modele (vag si probabilist) propun doua tipuri de informatie total diferita: apartenentavaga reprezinta similaritatea unor obiecte cu proprietati imprecise, iar probabilitatea da frecventerelative; mai mult, interpretarile si deciziile luate in functie de aceste valori depind de numerelespecifice asociate unor obiecte si evenimente particulare.

21

Este deci evident ca modelarea vaga si folosirea logicii vagi nu se reduc la folosirea unor ponderipozitive subunitare pentru fiecare obiect al universului. Totusi exista cazuri ın care filtre adaptivede mediere ponderata au fost denumite “fuzzy” doar pentru acesta caracteristica a coeficientilor (deexemplu FVDF - Fuzzy Vector Directional Filter [38]).

O metodologie cu adevarat bazata pe logica vaga este dezvoltata ın [37]: determinarea unui noufiltru pe baza combinarii a mai multe filtre (concept ce provine, desigur, din combinarea prelucrarilordirectionale si orientate pe amplitudine pentru imagini color). O asemenea abordare se bazeaza pefolosirea a mai multe criterii de evaluare a ponderilor vectorilor din fereastra de filtrare ın vectorul deiesire a filtrului, fara ca nici unul dintre acestea sa fie optimal, criterii ce sunt apoi combinate printr-unoperator neliniar, derivat ın mod esential din calculul ın logica vaga (un agregator fuzzy). O clasaparticulara de asemenea operatori sunt operatorii compensativi [56], definiti ca medii ponderate aleunor operatori OR (∪) si AND (∩) logic pentru multimile ce se combina:

A�γ B = (A ∩B)1−γ(A ∪B)γ (2.16)

Folosind diferite forme pentru operatiile logice vagi de baza (OR este o t-conorma, AND este o t-norma) si considerand o forma clasica pentru operatorul de complementare (negatia Lukasiewicz), sepot obtine diferite forme particulare ale operatorului de agregare. In [37] se propune folosirea ın (2.16)a t-normei Zadeh (min) si a t-normei probabiliste (de tip produs), ceea ce duce la obtinerea relatiilor:

wj =(

mini=1,k

wji

)1−γ (maxi=1,k

wji

)γ, j = 1, ..., n (2.17)

wj =k∏i=1

w1−γji

(1−

k∏i=1

(1− wji))γ

, j = 1, ..., n (2.18)

In (2.17) si (2.18) k este numarul de filtre individuale ce se combina, iar wji este ponderea de ordinul jcorespunzatoare filtrului i. Aplicatiile prezentate ın [37] folosesc combinarea cu ponderi egale (γ = 0.5)a doua filtre (k = 2): un vector median VMF si un vector median directional BVDF.

In [51] a propus extinderea filtrului median scalar fuzzy introdus de [53] si denumit AFMMF - AdaptiveFuzzy Multilevel Median Filter. Pentru acest filtru, procesul de prelucrare este descris de reguli deasociere vaga de tipul regulii lingvistice “daca X este Ai, atunci Y este Bi” (unde A si B sunt multimivagi definite peste universurile de obiecte X si Y ). Filtrul din [53] provine din MMF - MultilevelMedian Filter, definit pentru ferestre de filtrare de dimensiune impara, ın care se formeaza grupuri devalori Wi conform principalelor directii (verticala, orizontala, diagonale). Pentru fiecare set de valoriWi, se calculeaza medianul zi = median(Wi), iar toate aceste rezultate sunt combinate la iesireafiltrului ca:

y = median(min(zi),max(zi), f) (2.19)

Folosirea regulilor fuzzy aduce o ımbunatatire a performantelor filtrului, eliminand sensibilitatea aces-tuia la zgomotul de “zgarieturi”, prin includerea ın (2.19) a doi noi termeni, ce sunt definiti de ocredibilitate maxima. Credibilitatea unei valori este calculata dupa urmatorul set de reguli:

• daca diferenta absoluta dintre medianul zi si celelalte puncte din Wi este foarte mare, atuncicredibilitatea lui zi este mica

• daca diferenta absoluta dintre medianul zi si celelalte puncte din Wi este foarte mica, atuncicredibilitatea lui zi este mica

22

• daca diferenta absoluta dintre medianul zi si celelalte puncte din Wi este medie, atunci credibil-itatea lui zi este mare

In final, daca medianele de credibilitate maxima sunt zc1 si zc2, expresia iesirii filtrului AFMMF devine:

y = median(min(zi),max(zi), f, zc1, zc2)

Extensia multicanal (vectoriala) a acestui filtru se poate obtine foarte usor, prin simpla ınlocuire asintagmei diferenta absoluta cu cuvantul distanta. In [51], pentru filtrarea imaginilor color, am folositdistanta euclidiana ın spatiul RGB. Functiile de credibilitate sunt functii des folosite ca functii deapartenenta fuzzy: trapezoidala, parabolica, dreptunghiulara.

Dupa cum demonstreaza exemplul precedent, extinderea structurilor de filtrare scalare la cazul mul-ticanal este suficient de simpla daca regulile dupa care se face prelucrarea sunt exprimate ın modindependent de dimensiunea spatiului din care fac parte obiectele la care se refera. Acesta este sicazul filtrarii de clustering [50] si [49], care se poate considera ca provine din filtrele scalare de tip“trimmed median” [33]. Extinderea fuzzy a acestora se realizeaza prin simpla ınlocuire a algoritmuluide partitionare net cu unul fuzzy. Folosirea tehnicilor de clustering fuzzy pentru filtrarea imaginilorcolor [50] produce rezultate sensibil mai bune decat cele obtinute prin folosirea algoritmilor “crisp”.Elementul esential ın folosirea unei tehnici de partitionare vaga este acela ca prototipurile claselorsunt influentate de toate valorile selectate de fereastra de filtrare. In acest fel, valorile ce se afla ınapropierea frontierelor claselor si ar fi fost repartizate (ın cazul algoritmului crisp) ın mod arbitrar uneiunice clase, vor contribui ıntr-un mod semnificativ la prototipurile tutoror claselor. Daca partitionareaeste realizata cu un grad mare de fuzzificare, separatia dintre clase devine mai putin clara si prototipulclasei centrale este o aproximare mai buna a valorii originale.

Unul dintre algoritmii cei mai folositi de clustering fuzzy este Fuzzy Isodata [4] (cunoscut si ca al-goritmul Dunn-Bezdek). Pentru setul de n vectori xi ce se doresc partitionati ın C clase (fiecareclasa caracterizata de centroidul µj), se asociaza setul de coeficienti de apartenenta uij , care exprimagradul de apartenenta al vectorului xi la clasa j. Acesti coeficienti de apartenenta sunt numere pozitivesubunitare ce respecta conditia de normare

C∑j=1

uij = 1, i = 1, ..., n (2.20)

Determinarea partitiei ınseamna determinarea coeficientilor de apartenenta a vectorilor la clase, prinrezolvarea iterativa a sistemului de ecuatii (m este gradul de fuzzificare a partitiei):

µj =

n∑i=1

umijxin∑i=1

umij

, j = 1, ..., C (2.21)

uij =

C∑k=1

(‖xi − µj‖‖xi − µk‖

) 1m−1

−1

, i = 1, ..., n, j = 1, ..., C (2.22)

Dezavantajul esential al acestei tehnici de clustering fuzzy este cresterea dramatica a complexitatii decalcul: sunt necesare mult mai multe ınmultiri decat la variantele crisp, si ın plus apare si necesitatearidicarilor la putere. Mai mult, pentru un acelasi set de vectori, un algoritm de partitionare iterativafuzzy necesita mai multe iteratii decat algoritmul net din care provine. O posibila cale de a micsoranecesarul de calcule este de a utiliza algoritmi ierarhici si nu iterativi.

Algoritmii de clustering clasici (fie ca provin dintr-o abordare de tip cuantizare vectoriala [17], fiedintr-o abordare de tip recunoasterea formelor [29]) sunt definiti ca optimizand un criteriu de calitate

23

a partitie de tip eroare patratica medie minima. Se pot deci folosi simultana mai multe criterii deoptimalitate a unei partitii (eroare patratica medie minima, compactitudine a claselor definita prindistante agregate inter-vectori, volum minim a claselor); complicarea evidenta a formei criteriului deoptimizat (imposibil de rezolvat simbolic) a dus la considerarea de solutii de optimizare prin tehnici“inteligente” (simulated annealing [1] sau algoritmi genetici).

O alta abordare a filtrarii de tip median prin metode de clustering fuzzy a fost propusa ca extinderea filtrului fuzzy median scalar [13]. In [13] se propunea construirea medianului unui set de scalari nuprin procedeul obisnuit de ordonare, ci printr-o combinatie liniara a tuturor valorilor din fereastra defiltrare, ponderate cu coeficientii lor de apartenenta la clasa numita “median” (adica iesirea filtruluieste prototipul clasei ın care au fost grupate valorile). Acest clustering cu o singura clasa se faceprintr-un procedeu iterativ analog celui folosit la metoda Fuzzy Isodata; ceea ce se schimba esteecuatia (2.22) de determinare a gradelor de apartenenta, care devine (C = 1):

µ =

n∑i=1

umi xin∑i=1

umi

ui = exp

(−‖xi − µ‖

2

K

)Acest tip de filtrare de clustering poate fi asimilat (sau asemanat) mai multor modele de filtre: pe deo parte filtrele cu coeficienti dependenti de distanta, de tipul DDMF [16], sau se poate considera camodelul de clustering urmeaza paradigma posibilista, introdusa ın [26], [25].

Modelul fuzzy posibilist se bazeaza pe modificarea interpretarii gradului de apartenenta. Pentrumodelul probabilist (clasic), gradul de apartenenta al fiecarui vector exprima gradul ın care acestaeste comun la mai multe clase si se exprima prin constrangerea (2.20) ca gradele de apartenenta aleunui singur vector fata de toate clasele sa se comporte ca probabilitatile asociate unui camp complet deevenimente. Dezavantajul acestei abordari este ca, adeseori, vectori ce au acelasi grad de apartenentafata de doua clase nu sunt reprezentativi ın aceeasi masura pentru clasele respective. Ceea ce neintereseaza ın general este ınsa tocmai reprezentativitatea vectorilor fata de o clasa, deci cat de tipiceste un vector pentru o clasa data. Aceasta interpretare este modelarea posibilista [26] si se bazeazape renuntarea la constrangerea (2.20) si la adoptarea unei relatii de calcul a gradelor de apartenentaın functie de centroizii unei singure clase (si nu de centroizii tuturor claselor). In [26], [25] s-a propusfolosirea relatiei de tip exponential, ponderata cu un scalar ηj variabil cu iteratiile:

uij =

1 +

(‖xi − µj‖2

ηj

) 1m−1

−1

ηj = K

n∑i=1

umij ‖xi − µj‖2

n∑i=1

umij

, j = 1, ..., C

24

Anexa A

Probabilitatea de degradare a unuipixel

Zgomotul impulsiv este unul dintre tipurile de zgomot cele mai utilizate pentru exemplificarealimitarilor filtrarii liniare de netezire si evaluarea performantelor filtrelor neliniare (mai ales de tipmedian). Pentru o imagine scalara (cu nivele de gri) zgomotul impulsiv (sau de tip “sare si piper”)se manifesta prin ınlocuirea valorilor unor puncte din imagine (uniform distribuite) cu doua valoriextreme. Acesta ınsemana ca din imaginea originala f se obtine o imagine degradata fzg prin:

fzg(m,n) =

{valmin, cuprobabilitatea pmin

valmax, cuprobabilitatea pmax

In mod uzual, pentru imaginile color, se considera ca zgomotul impulsiv afecteaza ın mod independentfiecare componenta de culoare a imaginii; probabilitatile ca ın fiecare plan de culoare un pixel sa fiedegradat sunt respectiv pR, pG si pB (iar ın cazul uzual aceste probabilitati sunt egale pR = pG =pB = p). La nivelul imaginii color (deci pentru toate cele trei componente de culoare consideratesimultan), probabilitatea ca un pixel sa fie afectat de zgomot este ınsa determinata de formula:

P = pR + pG + pB − pRpG − pBpR − pGpB + pRpGpB.

Pentru cazul ın care pe toate planele de culoare exista acelasi zgomot, aceasta formula se simplificala:

P = 3p− 3p2 + p3.

Pentru probabilitatile de zgomot impulsiv folosite ın testele prezentate ın lucrare, probabilitatea echiva-lenta de degradare a unui pixel la nivelul ıntregii imagini este prezentata ın tabelul A.

Procent de zgomot Probabilitate de degradare a pixelilorp % P %

1 2.97015 14.262510 27.115 38.587525 57.8125

Tabel A.1: Probabilitatile de degradare a unui pixel al imaginii color, in functie de zgomotul impulsivadaugat in mod independent fiecarui plan de culoare.

25

Bibliografie

[1] E. Aarts si J. Korst. Simulated Annealing and Boltzmann Machines (a stochastic approach tocombinatorial optimization and neural compuring). J. Wiley and Sons, New York NY, 1989.

[2] J. Astola, P. Haavisto, si Y. Neuvo. “Vector Median Filters”. Proc. IEEE, 78(4):678–689, Apr.1990.

[3] V. Barnett. “The Ordering of Multivariate Data”. J. of. Royal Stat. Soc. A, 139(3):318–354,1976.

[4] J. C. Bezdek. Pattern Recognition with Fuzzy Objective Functions. Plenum, New York NY, 1981.

[5] J. C. Bezdek. “Fuzzy Models - What are They and Why ?”. IEEE Trans. on Fuzzy Systems,1(1):1–5, Feb. 1993.

[6] A. Buchowicz. “Adaptive Multichannel Distance Filters”. In Proc. of IEEE Conference on ImageProcessing ICIP ‘95, vol. 1, pp. 175–178, Washington D.C., USA, 23-26 Oct. 1995.

[7] A. Buchowicz si I. Pitas. “Multichannel Distance Filters”. In Proc. of IEEE Conference on ImageProcessing ICIP ‘94, vol. 2, pp. 575–579, 1994.

[8] K. R. Castleman. Digital Image Processing. Prentice Hall, Englewood Cliffs NJ, 1996.

[9] J. M. Chassery si A. Montanvert. Geometrie discrete en Analyse d’images. Hermes, Paris, 1991.

[10] M. Ciuc, R. M. Rangayyan, T. Zaharia, si V. Buzuloiu. “Adaptive neighbourhood filters for colorimage filtering”. In Proc. of the SPIE Nonlinear Image Processing IX Conference, vol. 3304, pp.277–286, 10-13 Jan. 1998.

[11] J. P. Cocquerez si S. Philipp, editors. Analyse d‘images: filtrage et segmentation. Masson, Paris,1995.

[12] H. A. Cohen. “Image Restauration via N-Nearest Neighbour Classification”. In Proc. of IEEEConference on Image Processing ICIP ‘96, vol. 1, pp. 1005–1008, Lausanne, Switzerland, 16-19Sept. 1996.

[13] M. Doroochi si A. M. Reza. “Fuzzy Cluster Filter”. In Proc. IEEE Conference on Image Pro-cessing ICIP ‘96, vol. 2, pp. 939–942, Lausanne, Switzerland, 16-19 Sept. 1996.

[14] G. Economou si S. Fotopoulos. “A Family of Adaptive Nonlinear Low Complexity Filters”. InProc. ECCTD ‘93 - Circuit Theory and Design, pp. 521–524, Davos, Switzerland, Sept. 1993.

[15] G. Economu, A. Ifantis, si D. Sindoukas. “Multichannel Distance Filtering of Seismic Signals”.In VIII European Signal Processing Conference EUSIPCO ‘96, vol. 1, pp. 89–92, Trieste, Italy,10-13 Sept. 1996.

26

[16] S. Fotopoulos si G. Economou. “Multichannel Filters Using Composite Distance Metrics”. InProc. of the IEEE Workshop on Nonlinear Signal and Image Processing, vol. 2, pp. 503–506, NeosMarmaras, Greece, Jun. 1995.

[17] A. Gersho si R. M. Gray. Vector Quantization and Signal Compression. Kluwer Academic Publ.,Boston, 1992.

[18] A.K. Jain. Fundamentals of Digital Image Processing. Prentice Hall Intl., Englewood Cliffs NJ,1989.

[19] D. G. Karakos si P. E. Trahanias. “Combining Vector Median and Vector Directional Filters:The Directional - Distance Filter”. In Proc. of IEEE Conference on Image Processing ICIP ‘95,vol. 1, pp. 171–174, Washington D.C., USA, 23-26 Oct. 1995.

[20] D. G. Karakos si P. E. Trahanias. “Generalized Multichannel Image-Filtering Structures”. IEEETrans. on Image Processing, 6(7):1038–1045, Jul. 1997.

[21] V. Koivunen. “Nonlinear Filtering of Multivariate Images Under Robust Error Criterion”. IEEETrans. on Image Processing, 5(6), Jun. 1996.

[22] V. Koivunen, N. Himayat, si S. A. Kassam. “Multivariate MTM Filters Analysis and DesignOptions”. In Proc. of IEEE Conference on Image Processing ICIP ‘95, vol. 1, pp. 354–357,Washington D.C., USA, 23-26 Oct. 1995.

[23] V. Koivunen si S. A. Kassam. “Nearest Neighbor Filters for Multivariate Data”. In Proc. of theIEEE Workshop on Nonlinear Signal and Image Processing, vol. 2, pp. 734–737, Neos Marmaras,Greece, Jun. 1995.

[24] V. Koivunen si S. A. Kassam. “Covariance Estimation in Multivariate OS-Filtering”. In Proc.of IEEE Conference on Image Processing ICIP ‘96, vol. 1, pp. 981–984, Lausanne, Switzerland,16-19 Sept. 1996.

[25] R. Krishnapuram, H. Frigui, si Nasraoui O. “Fuzzy and Possibilistic Shell Clustering Algorithmand Their Application to Boundary Detection and Surface Approximation - Part I”. IEEE Trans.on Fuzzy Systems, 3(1):29–43, Feb. 1995.

[26] R. Krishnapuram si J. M. Keller. “A Possibilistic Approach to Clustering”. IEEE Trans. onFuzzy Systems, 1(2):98–110, May 1993.

[27] W. J. Krzanowski. Principles of Multivariate Analysis: A User‘s Perspective. Clarendon Press,Oxford, 1993.

[28] J. S. Lee. “Digital Image Enhancement and Noise Filtering by Use of Local Statistics”. IEEETrans. on PAMI, 2(2), Mar. 1980.

[29] V. E. Neagoe si O. Stanasila. Teoria Recunoasterii formelor. Ed. Academiei Romane, Bucuresti,1992.

[30] J. O’Rourke. Computational Geometry in C. Cambridge University Press, Cambridge, 1995.

[31] A. R. Papoulis. Probability, random variables and stochastic processes. McGraw Hill Book Comp.,New York NY, 1994.

[32] R. B. Paranjape, T. F. Rabie, si R. M. Rangayyan. “Image Restauration by adaptive-neighbourhood noise subtraction”. Applied Optics, 33(14):2861–2869, May 1994.

[33] I. Pitas si A. N. Venetsanopoulos. Nonlinear Digital Filters - Principles and Applications. KluwerAcademic Publ., Norwell MA, 1990.

27

[34] K. N. Plataniotis, D. Androutsos, si A. N. Venetsanopoulos. “Multichannel Filtering for ColorImage Processing”. In Proc. of IEEE Conference on Image Processing ICIP ‘96, vol. 1, pp.993–996, Lausanne, Switzerland, 16-19 Sept. 1996.

[35] K. N. Plataniotis, D. Androutsos, si A. N. Venetsanopoulos. “Nearest Neighbour MultichannelFilters for Image Processing”. In VIII European Signal Processing Conference EUSIPCO ‘96,vol. 1, pp. 157–160, Trieste, Italy, 10-13 Sept. 1996.

[36] K. N. Plataniotis, D. Androutsos, si A. N. Venetsanopoulos. “Color Image Processing UsingAdaptive Multichannel Filters”. IEEE Trans. on Image Processing, 6(7):933–949, Jul. 1997.

[37] K. N. Plataniotis, D. Androutsos, si A. N. Venetsanopoulos. “Multichannel Filters for ImageProcessing”. Signal Processing: Image Communications, 9(2):143–158, Jan. 1997.

[38] K. N. Plataniotis, N. Androutsos, si A. N. Venetsanopoulos. “Color Image Processing UsingFuzzy Vector Directional Filters”. In Proc. of the IEEE Workshop on Nonlinear Signal andImage Processing, vol. 2, pp. 535–538, Neos Marmaras, Greece, Jun. 1995.

[39] R. M. Rangayyan, M. Ciuc, si F. Faghih. “Adaptive-neighborhood filtering of images corruptedby signal dependent noise”. Applied Optics, 37(20):4477–4487, 1998.

[40] C. S. Regazzoni si A. Teschioni. “A New Approach to Vector Median Filtering Based on SpaceFilling Curves”. IEEE Trans. on Image Processing, 6(7):1025–1037, Jul. 1997.

[41] B. Reusch. “Mathematics of Fuzzy Logic”. In H. J. Zimmermann, D. Dascalu, si M. G. Negoita,editors, Real World Applications of Intelligent Technologies, pp. 15–52, Bucuresti, Romania, 1996.Romanian Academy Publ. House.

[42] R. Sedgewick. Algorithms in C++. Addison Wesley, Reading, MA, 1992.

[43] A. Spataru. Teoria Transmisiunii Informatiei. Ed. Didactica si Pedagogica, Bucuresti, 1983.

[44] K. Tang, J. Astola, si Y. Neuvo. “Nonlinear Multivariate Image Filtering Techniques”. IEEETrans. on Image Processing, 4(6):788–798, Jun. 1995.

[45] P. E. Trahanias si A. N. Venetsanopoulos. “Color Edge Detection Using Vector Statistics”. IEEETrans. on Image Processing, 2(2):259–264, Apr. 1993.

[46] P. E. Trahanias si A. N. Venetsanopoulos. “Vector Directional Filters - A New Class of Multi-channel Image Processing Filters”. IEEE Trans. on Image Processing, 2(4):528–534, Oct. 1993.

[47] P. E. Trahanias si A. N. Venetsanopoulos. “Vector Order Statistics Operators as Color EdgeDetectors”. IEEE Trans. on Systems, Man and Cybernetics, B, 26(1):135–143, Feb. 1996.

[48] C. Vertan. Prelucrarea si Analiza Imaginilor. Ed. Printech, Bucuresti, 1999.

[49] C. Vertan, V. Buzuloiu, M. Malciu, si T. Zaharia. “Color Image Enhancement by Cluster Filter-ing”. In Buletinul Stiintific al Universitatii Politehnica Timisoara, vol. 41, pp. 210–213, Timisoara,Romania, 26-27 Sept. 1996.

[50] C. Vertan si C. Geangala. “Fuzzy Unsupervised Clustering for Color Image Filtering”. In Proc.of EUFIT 1996, vol. 3, pp. 1750–1753, Aachen, Germany, 2-5 Sept. 1996.

[51] C. Vertan, C. I. Vertan, si V. Buzuloiu. “Fuzzy Developments of Multichannel Filters”. InL. C. Jain, editor, Conventional and Knowledge-Based Intelligent Electronic Systems, vol. 2, pp.488–492. IEEE Press, New York, 1997.

[52] F. M. Wahl. Digital Image Signal Processing. Artech House, Boston, 1987.

28

[53] X. Yang si P. S. Toh. “Adaptive Fuzzy Multilevel Median Filter”. IEEE Trans. on ImageProcessing, 4(5):680–682, May 1995.

[54] L. Zadeh. “Fuzzy Sets”. Information and Control, 8:338–353, 1965.

[55] P. Zamperoni. “Image Enhancement”. Advances in Imaging and Electron Physics, 92:1–77, 1995.

[56] H. J. Zimmermann. Fuzzy Sets, Decision Making and Expert Systems. Kluwer Academic Publ.,Boston MA, 1987.

29