material on-line - Laboratorul de Analiza si Prelucrarea
Transcrição
material on-line - Laboratorul de Analiza si Prelucrarea
Capitolul 1 FILTRAREA NELINIARĂ BAZATĂ PE ORDONARE Ordonarea crescătoare a unui set de valori stă la baza operaţiilor de filtrare de ordine [33]. Valorile ordonate ale eşantioanelor din fereastra de filtrare, numite statistici de ordine, pot fi utilizate ca atare, sau pot fi combinate. Filtrul median [33], [48] este cel mai folosit filtru cu ordonare după rang; ieşirea acestuia este statistica de ordin central a setului de valori, permiţând astfel eliminarea valorilor extreme aberante (outliar ) ı̂n acelaşi timp cu păstrarea detaliilor utile ale imaginii. Cea mai uzuală combinaţie a statisticilor de ordine este combinarea liniară; filtrul astfel obţinut se numeşte L-filtru [33], [48]. L-filtrele sunt extrem de flexibile, ı̂nglobând posibilitatea obţinerii atât a filtrelor simple de ordonare după rang (inclusiv filtrul median) cât şi a filtrelor liniare1 . Dacă ı̂n cazul imaginilor scalare ordonarea valorilor nu prezintă nici o problemă, extinderea claselor de filtre bazate pe ordonare ı̂n cazul imaginilor color (sau, ı̂n general, vectoriale) nu este o chestiune simplă. După cum se remarcă ı̂n [3], proprietăţile de ordonare există doar ı̂ntr-o singură dimensiune şi nu există nici o concepţie naturală de rang. Notaţia general acceptată este de a considera {x1 , x2 , ..., xn } o populaţie de vectori p-dimensionali, realizări particulare ale variabilei aleatoare multivariate X. Componenta i a variabilei aleatoare multivariate este Xi şi va fi reprezentată de mulţimea de realizări particulare {x1i , x2i , ..., xni }. Pentru cazul imaginilor color prelucrate prin filtre de vecinătate, n este dimensiunea ferestrei de filtrare, numărul de componente a vectorilor este p = 3, iar vectorii xi sunt triplete de componente de culoare ce descriu fiecare pixel. 1.1 Filtrări de ordine prin ordonare lexicografică O relaţie introdusă ı̂ntre elementele unui spaţiu vectorial se numeşte relaţie de ordine dacă verifică proprietăţile de reflexivitate (1.1), tranzitivitate (1.2) şi antisimetrie (1.3): x x, ∀x (1.1) x y si y z =⇒ x z, ∀x, y, z (1.2) 1 Filtrul liniar de mediere se obţine evident ı̂n condiţiile ı̂n care ponderile statisticilor de ordine sunt egale cu 1/n; pentru aplicarea unei filtrări liniare de mediere ponderată, trebuie introdusă noţiunea de L-filtru adaptiv, cu coeficienţi de ponderare diferiţi pentru fiecare pixel, ce sunt permutări ale coeficienţilor filtrului liniar (permutări generate ı̂n aceeaşi fel ca ordonarea valorilor din imagine). 1 x y si y x =⇒ x = y, ∀x, y (1.3) Conform acestei definiţii, pentru date multivariate (vectoriale) se poate introduce o singură relaţie de ordine bine definită: ordinea lexicografică (numită şi ordine de dicţionar). Pentru vectorii pdimensionali x şi y relaţia de ordine lexicografică este definită 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 că ı̂n cadrul ordonării complete, lexicografice (1.4), vectorii sunt ordonaţi după prima componentă, apoi după a doua componentă, şi aşa mai departe. Aceasta ı̂nseamnă că prima componentă trebuie să fie cea mai importantă sau semnificativă (sau, mai mult, componentele vectorului trebuie să fie ordonate ı̂n ordinea importanţei acestora). Această ordonare nu poate fi cunoscută apriori şi este puternic dependentă de problemă; mai mult, ı̂n cazul imaginilor, ordinea importanţei componentelor de culoare nu este invariantă spaţial. În plus (şi acesta este dezavantajul cel mai important), ordinea lexicografică nu păstrează topologia spaţiului. Aplicarea practică a ordonării lexicografice se bazează deci pe stabilirea unei ordini a importanţei componentelor de culoare (deci stabilirea unor ranguri pentru acestea). În această situaţie se disting două cazuri fundamentale: dacă reprezentarea culorilor este reprezentarea RGB primară este de presupus că, apriori, toate componentele au o aceeaşi importanţă şi distincţia dintre ele trebuie făcută adaptiv, pentru fiecare pixel al imaginii, după măsuri statistice locale; dacă culorile sunt reprezentate ı̂ntr-un spaţiu de culoare derivat, ı̂n care cele trei componente să aibă semnificaţii fizice sau perceptuale diferite, este de aşteptat să se poată stabili apriori o ordine a importanţei acestora. 1.1.1 Ordonarea lexicografică ı̂n spaţiul primar Pentru a realiza ordonarea unor vectori ale căror componente sunt valorile RGB ale culorilor trebuie, deci, deduse măsuri ale activităţii componentelor de culoare; asemenea măsuri sunt calculate pentru fiecare plan de culoare, ı̂n vecinătatea fiecărui pixel al imaginii. Asemenea măsuri de activitate a componentelor de culoare ı̂ncearcă să stabilească ı̂n care componentă de culoare sunt sesizabile cele mai mari variaţii. Variaţiile puternice ale unei componente se presupune că sunt datorate prezenţei impulsurilor de zgomot ı̂n vecinătatea curentă. Ca măsuri de activitate (sau de disimilaritate) pot fi folosite varianţa, domeniul de variaţie (diferenţa ı̂ntre maximul şi minimul local), raportul de contrast [18] sau domeniul de variaţie normat la media componentei; cu cât disimilaritatea este mai mare, cu atât componenta este mai importantă, şi deci, local, pentru ordonare, componentele vectorilor de culoare sunt permutate. 1.1.2 Ordonarea lexicografică ı̂n spaţiul perceptual Dificultatea stabilirii unei ordini clare de importanţă a componentelor de culoare RGB a unei imagini sugerează folosirea unui spaţiu de reprezantare a culorilor ı̂n care, din modul de definire, importanţa componentelor să fie deja stabilită. Un astfel de spaţiu este spaţiul perceptual de reprezentare HSV . Reprezentarea se compune din componenta de nuanţă, ce indică tipul de culoare, componenta de saturaţie, ce exprimă puritatea culorii şi componenta de “valoare”, de tipul luminanţei sau intensităţii luminoase a culorii. Perceptual, cel mai uşor de sesizat sunt modificările nuanţei (deoarece schimbă natura culorilor) [8], urmate de modificările saturaţiei (care pot da un caracter nenatural imaginii). În acelaşi timp, prezenţa impulsurilor de zgomot este sesizabilă ı̂n toate componentele HSV . Aceasta sugerează că cel mai indicat este folosirea componentei V ca cea mai importantă componentă, ı̂n care să se detecteze prezenţa impulsurilor de zgomot. Atunci, ı̂nainte de ordonare, vectorii reprezentării HSV a culorilor vor avea permutate componentele H şi V . 2 1.2 Filtrări de ordine prin principii de pre-ordonare Acceptând inutilitatea căutării oricărei ordonări totale, simple, ne-ambigue şi universale a n eşantioane multivariate, interesul practic a fost limitat la modurile ı̂n care se pot construi relaţii restrânse de ordonare vectorială, fezabile şi avantajoase. Rezultatul oricărui principiu de ordonare parţială (sau sub-ordonare, sau pre-ordonare, ce nu respectă principiul de antisimetrie (1.3)) este o ordonare (sau plasare după rang) a uneia sau mai multor caracteristici ale observaţiei, considerată individual sau ı̂n combinaţie cu alte observaţii. Proprietăţile dorite pentru ordonarea după rang a datelor vectoriale se pot extrapola din proprietăţile ordonării scalare: eşantioanele monoton ne-descrescătoare pe toate componentele sunt vectori proprii, invarianţi la ordonare; relaţia ı̂nglobează posibilitatea determinării unui estimator robust al locaţiei (medianul [33], [2]), ce poate fi determinat prin selecţia statisticii cu un anume rang; este omogenă faţă de scalarea cu factori pozitivi a componentelor individuale; se reduce la ordonarea scalară dacă componentele sunt identice; produce statistici de ordine ce sunt observaţii ale mulţimii ordonate; sortează valorile extreme aberante ı̂n regiuni consistente ale spaţiului rangurilor. În [3] se propun patru pricipii de bază de ordonare parţială (pre-ordonare) a datelor vectoriale: • ordonarea marginală (descrisă ı̂n secţiunea 1.2.1) • ordonarea condiţională (descrisă ı̂n secţiunea 1.2.2) • ordonarea parţială (descrisă ı̂n secţiunea 1.2.3) • ordonarea redusă (descrisă ı̂n secţiunea 1.2.4) 1.2.1 Ordonarea marginală Ordinea marginală [3], [33] este, după cum sugerează şi numele, o ordonare care se face după unul sau mai multe din eşantioanele marginale ale vectorilor consideraţi. Din punctul de vedere al prelucrării semnalelor, ordonarea marginală revine la a ordona ı̂n mod independent valorile eşantioanelor din fiecare canal al semnalului; modelul asociat semnalului vectorial (sau multicanal) este ı̂n acest caz o stivă de semnale scalare, ce pot fi ordonate şi prelucrate ı̂n mod separat. Prin această prelucrare independentă a componentelor semnalelor nu se ia ı̂n considerare intercorelaţia existentă ı̂ntre canale, aceasta fiind principala sursă de erori a metodei (ı̂n [2] se arată de exemplu cum o prelucrare de tip median marginal a unui semnal de culoare produce culori false ı̂n anumite zone cu culori puternic saturate). Spre deosebire de cazul scalar, statisticile vectoriale marginale de ordine nu mai sunt observaţii ale semnalului, ci valori noi. În cazul imaginilor color, ı̂n mod paradoxal, filtrarea marginală produce rezultate excelente, atât vizual (deci caracterizate conform unor măsuri subiective) cât şi ca măsuri de calitate. Filtrul median marginal MMF (Median Marginal Filter ) elimină ı̂n mod eficient zgomotul impulsiv din imagini, chiar prezent ı̂n proporţii foarte mari (până la 25%-30% din pixeli degradaţi). Filtrul median marginal este utilizat şi la derivarea unor structuri de filtrare adaptive (de exemplu prin comutarea ı̂ntre un filtru median şi un filtru trece tot, condiţionat de varianţa locală a componentelor). Din punct de vedere teoretic, există două metode de luare ı̂n considerare a corelaţiei ce există ı̂ntre componentele imaginii vectoriale: ı̂n primul rând, corelaţia poate fi eliminată prin decorelarea componentelor imaginii, sau corelaţia dintre canale (componente) poate fi ı̂nglobată ı̂n proiectarea structurii filtrului. 3 Filtre mediane marginale cu decorelare Abordarea cu decorelare propune realizarea filtrării mediane a fiecărei componente de culoare după decorelarea acestora. Decorelarea se face prin utilizarea transformării Karhunen-Loève (KL); recorelarea componentelor se face după filtrarea fiecărui plan de culoare. Această abordare prezintă avantajul unei performanţe independente de sistemul de reprezentare folosit pentru culorile imaginii (fie ı̂n spaţiul primar RGB, fie un spaţiu perceptual). După cum se poate uşor constata, presupunerea statistică esenţială pe care se bazează folosirea transformării KL la decorelare este aceea că valorile (vectoriale) ale pixelilor imaginii sunt realizări particulare ale unui câmp aleator, identic distribuite. Dacă această distribuţie a valorilor pixelilor (presupusă deci invariantă pentru ı̂ntreaga imagine) ar fi normală (gaussiană), ı̂n urma decorelării, componentele vectorilor observaţie ar deveni şi independente, nu numai decorelate [31], [43]. Aşa numita abordare cu independentizare a filtrării marginale a imaginilor color: ı̂naintea etapei de decorelare, distribuţia valorilor pixelilor este transformată ı̂ntr-o distribuţie aproape normală folosind teorema limită centrală [31], [43] – suma unui număr de câteva variabile aleatoare identic distribuite, din care nici una nu este dominantă, tinde la o distribuţie normală. Pentru a realiza această distribuţie aproape normală, s-a propus realizarea de sume locale a vecinilor fiecărui pixel. După sumare se poate face decorelarea, filtrarea marginală, recorelarea şi apoi transformarea inversă independentizării (rezultând o operaţie de filtrare numită IDMMF (Independent Decorrelated Marginal Median Filter ) sau se poate renunţa la etape de decorelare (rezultând o operaţie de filtrare numită IMMF (Independent Marginal Median Filter ). L-filtre vectoriale bazate pe ordonare marginală Corelaţia dintre componentele observaţiilor vectoriale poate fi luată ı̂n considerare prin modificarea structurii filtrelor de ordine ce se folosesc; acestea nu mai sunt identice cu analoagele lor din cazul scalar. Cazul L-filtrelor este tipic pentru această abordare. Un L-filtru scalar aplicat unui set de valori X = {x1 , x2 , ..., xn } produce ca ieşire o combinaţie liniară a statisticilor de ordine ale acestora [33], [48]: y= n X wi x(i) = n X Wi1 x(i1 ) (1.5) i1 =1 i=1 unde scalarii wi , respectiv Wi1 sunt cei n coeficienţi ai filtrului. Pentru cazul valorilor vectoriale, fiecare observaţie este un vector cu p componente, xi = (x1i , x2i , ..., xni ), iar statisticile de ordine marginale sunt vectori formaţi din statisticile de ordine marginale (calculate pentru fiecare componentă a observaţiilor vectoriale, x(i) = (x1(i) , x2(i) , ..., xn(i) ). Utilizarea acestor statistici vectoriale conduce la redefinirea L-filtrului vectorial ca: y= n X n X n X ... i1 =1 i2 =1 Wi1 i2 ...ip x(i) (1.6) ip =1 unde Wi1 i2 ...ip sunt cele N p matrici p × p de coeficienţi ai filtrului. Forma din (1.6) poate fi rearanjată ı̂n funcţie de vectorii statisticilor de ordine marginale din fiecare canal (componentă) a vectorilor observaţie: y= p X j=1 e (j) Wj x (1.7) Determinarea matricilor de coeficienţi Wj se poate face prin optimizarea ı̂n sensul erorii pătratice medii minime a unui L-filtru a cărui ieşire să fie un estimator nedeplasat al poziţiei centrale (şi deci să elimine zgomotul impulsiv, singular sau ı̂n mixtură cu zgomotul gaussian). Determinarea coeficienţilor necesită cunoaşterea funcţiilor de densitate de probabilitate a statisticilor de ordine marginale ale semnalului de intrare, precum şi a valorilor acestuia. Cum rareori semnalul de intrare nedegradat este 4 cunoscut, acesta trebuie estimat din valorile corecte deja calculate, prin ipoteze asupra staţionarităţii şi proprietăţilor sale de corelaţie. 1.2.2 Ordonarea condiţională Ordonarea condiţională este un mod de a stabili ranguri, sau o ordine, sau o modalitate de selecţie [3], [33] pentru vectorii unui set de date, condiţionată de ordonarea unei componente marginale a acestora. Deci ordinea unei singure componente marginale decide ordinea vectorilor; din acest punct de vedere, ordonarea condiţională poate fi interpretată ca o ordonare lexicografică trunchiată la o singură componentă2 . Acestă trunchiere ı̂nseamnă că orice prelucrare se va face relativ la o singură componentă, păstrândule pe celelalte nemodificate. Componenta ce se prelucrează trebuie, desigur, să fie cea mai coruptă (degradată de zgomot), sau componenta ı̂n care influenţa zgomotului se resimte cel mai puternic. Ca şi ı̂n cazul definirii ordinii lexicografice (secţiunea 1.1) este necesară determinarea componentei ce se va prelucra. Se pot distinge şi aici două cazuri: dacă există o componentă intrinsec dominantă (aşa cum este componenta de valoare de la reprezentarea perceptuală HSV a imaginilor color), atunci aceasta este cea care se va prelucra. Dacă toate componentele au, apriori, o aceeaşi importanţă (ca ı̂n cazul reprezentării imaginilor color ı̂n spaţiul primar RGB), este evident că prelucrarea unui aceluiaşi ı̂ntreg plan de culoare (sau a unei aceleiaşi componente) nu poate produce rezultate. Ca şi ı̂n cazul ordonării lexicografice, soluţia se află ı̂n alegerea adaptivă a componentei de prelucrat (componenta după care se face ordonarea condiţională) pentru fiecare poziţie a ferestrei de filtrare (deci pentru fiecare pixel al imaginii). Componenta cea mai activă este definită printr-o valoare mare a unei măsuri de neuniformitate: interval de variaţie, interval de variaţie normat la medie, varianţă, raport de contrast, chiar valori proprii. 1.2.3 Ordonarea parţială Ceea ce Barnett [3] numeşte ordonare parţială a unui set de date multivariate (a unui set de vectori) se bazează pe distincţia ı̂ntre grupuri de observaţii (vectori) şi nu pe distincţia ı̂ntre fiecare vector ı̂n parte. Deci, pentru această variantă de sub-ordonare, accentul se mută de la considerarea eşantioanelor marginale sau a observaţiilor multivariate individuale la luarea ı̂n considerare a proprietăţilor globale, relaţionale, din ı̂ntregul set al eşantioanelor. Pentru a face o distincţie ı̂ntre diferitele grupuri de observaţii (având ı̂n vedere ordinea, extremele, rangul) se urmăreşte modul ı̂n care observaţiile se situază ı̂n diferite regiuni ale spaţiului eşantioanelor. Metoda de partiţionare folosită (bazată pe unul dintre mai multe principii posibile) poate implica proprietăţi marginale ale datelor; scopul principal este de a oferi o distincţie limitată ı̂ntre diferitele eşantioane (vectori) ai populaţiei. Ordonarea parţială produce o bază de ı̂mpărţire a eşantioanelor ı̂n grupuri distincte de diferite ordine, fără a face distincţii ı̂n interiorul unui aceluiaşi grup. Ordonarea parţială implică construirea anvelopei convexe a setului de observaţii (setul convex minim ce conţine toate observaţiile iniţiale). Punctele (vectorii) ce se află pe ı̂nfăşurătoarea anvelopei convexe sunt numite grupul 1, şi apoi eliminate; se formează apoi anvelopa convexă a reziduului, punctele de pe noua ı̂nfăşurătoare formează grupul 2 (a se vedea figura 1.2.3). Procedeul este repetat, formând astfel o metodă bazată pe divizarea datelor ı̂n grupuri de ordine (sau de rang). Cu cât numărul (ordinul) 2 Anticipând definirea ordonării reduse, putem spune că ordonarea condiţională poate fi obţinută şi din aceasta dacă scalarul asociat fiecărui vector (a se vedea descrierea completă a metodei ı̂n secţiunea 1.2.4) este o singură componentă a acestuia. 5 Fig. 1.1: Partiţionarea unui set de vectori bidimensionali după anvelopa convexă. grupului este mai mic, cu atât observaţia (eşantionul, vectorul) este mai extremal. Este evident că, ı̂n aceste condiţii, vectorii setului de ordin maxim sunt situaţi ı̂n centrul clusterului de puncte, şi deci sunt candidaţi pentru medianul acestora. O asemenea metodă de ordonare este analoagă cu ceea ce a fost numit ı̂n statistică cojirea unei populaţii multivariate [27] (potato peeling sau orange peeling). O asemenea operaţie are ı̂nsă un analog pentru cazul scalar: aşa numitul filtru tobogan3 de ı̂mbunătăţire a uniformităţii unei regiuni [55]. Esenţa metodei se bazează deci pe implementarea unor algoritmi de calcul al anvelopei convexe pentru date p dimensionale, cu p > 1, deci pe algoritmi de geometrie computaţională [30]. Teorema McMullenShepard [30] arată că anvelopa convexă a oricărei mulţimi de puncte din spaţiul Euclidian p dimensional este un politop4 convex (reciproc, orice politop convex fiind anvelopa convexă a cel puţin unui set de puncte). Pentru cazul plan (p = 2) există alte seturi de teoreme ce dau descrieri ale anvelopei convexe a unui set de puncte, ce sunt direct implementabile; algoritmi deja clasici sunt algoritmii Jarvis (Jarvis march) [42] şi algoritmul Graham (Graham scan) [42]. Pe măsură ce dimensiunea spaţiului creşte problema de determinare a anvelopei convexe devine din ce ı̂n ce mai complicată; ı̂n cazul general, rezolvarea acesteia se poate face printr-o abordare de tip package-wrapping (sau gift-wrapping) [30]. Fiecare pas al acestei metode găseşte o nouă faţă a politopului anvelopă convexă ı̂ndoind (pliind) 3 Filtrul tobogan ı̂nlocuieşte extremele valorilor selectate de o fereastră de filtrare cu statisticile imediat următoare (superioară sau inferioară, depinzând dacă extremul este un minim sau un maxim), cu condiţia ca acestea să aibă valori diferite de valoarea extremului. 4 Un politop este o mulţime poliedrală, rezultată ca intersecţia unui număr finit de semispaţii ı̂nchise; un semispaţiu este regiunea spaţiului p dimensional aflată de aceeaşi parte a unui hiperplan. 6 un hiperplan ı̂n jurul unei muchii a anvelopei convexe deja determinate, până ı̂n momentul ı̂n care acesta ı̂ntâlneşte primul punct al mulţimii de puncte iniţiale. Analiza complexităţii algoritmice a unei asemenea abordări a condus la deducerea unei comportări O(n2 ), unde n este numărul de puncte al setului pentru care se calculează anvelopa convexă. Abordările cele mai rapide pornesc de la principiul divide et impera şi de la o teoremă ce demonstrează echivalenţa dintre problemele sortării unui şir de numere şi de calculare a anvelopei convexe [30]; aceste abordări rapide conduc la o complexitate O(n log n). O problemă suplimentară apare ı̂n momentul considerării spaţiilor discrete, ı̂n care trebuie definit conceptul de convexitate discretă [9]. O componentă conexă discretă C este convexă dacă pentru orice pereche de puncte P, Q ∈ C şi orice scalar α ∈ [0; 1] există un punct R ∈ C pentru care discul de centru R şi rază h/2, construit conform distanţei chessboard, include punctul de pe segmentul P Q, dat de αP + (1 − α)Q. O consecinţă a acestei definiţii a convexităţii este aceea că mulţimea de puncte ce formează anvelopa convexă discretă nu coincide, ci include mulţimea de puncte de coordonate discrete din anvelopa convexă “continuă” construită pe baza aceleiaşi mulţimi de puncte discrete iniţiale. Pentru cazul planului discret, ı̂n [9] se identifică două tipuri esenţiale de configuraţii de neconvexitate, ce trebuiesc identificate ı̂n mulţimea dată de puncte şi eliminate (eliminarea presupune inserarea unui punct suplimentar): configuraţiile U şi L. Dar acestă operaţie nu este altceva decât o operaţie morfologică de tip totul sau nimic (Hit or Miss) [48], realizată cu măşti corespunzătoare configuraţiilor U, L şi a rotitelor acestora. Cu toată bogăţia de metode şi algoritmi existenţi pentru calculul anvelopelor convexe, literatura de specialitate nu consemnează nici o realizare de filtre de ordine de tip median bazate pe ordonarea parţială a datelor extrase de fereastra de filtrare din imagine. Putem găsi mai multe argumente pentru justificarea lipsei totale de interes pentru utilizarea acestei tehnici: ı̂n primul rând ordonarea se referă la un set mic de valori (vectorii dintr-o vecinătate a pixelului curent), ceea ce poate duce la imposibilitatea găsirii a mai multe “rânduri” de anvelope convexe; apoi vectorii au dimensiune mai mare ca 2 (cel puţin 3, pentru imaginile color), ceea ce face ca algoritmii eficienţi de calcul al anvelopei convexe să fie din ce ı̂n ce mai greu de descris; ı̂n fine, este posibil ca mulţimea de rang maxim (cea mai “centrală” să conţină mai mult de un singur vector, ceea ce face ca să fie necesară o nouă procedură de selecţie). 1.2.4 Ordonarea redusă Ordonarea redusă [3] se bazează pe reducerea fiecărei observaţii vectoriale (multivariate) la o unică valoare (scalar) printr-o combinaţie a valorilor componentelor observaţiilor. Scalarii obţinuţi sunt apoi ordonaţi (conform ordinii comune din mulţimea numerelor reale); ordinea scalarilor determină ordinea vectorilor. Ordonare bazată pe distanţe De cele mai multe ori, scalarii si asociaţi vectorilor xi sunt deduşi pe baza unei distanţe generalizate la un punct fix specificat xf ix , rezultând astfel o formă pătratică: si = (xi − xf ix )T A−1 (xi − xf ix ) (1.8) Matricea pătrată p × p A poate fi orice matrice pozitiv semidefinită; ı̂n general este preferată alegerea matricii unitare, ce generează metrica Euclidiană, dar este posibilă şi alegerea matricii de covarianţă a observaţiilor (rezultând distanţa Mahalanobis) sau a unei matrici diagonale, ce va genera distanţe Euclidiene ponderate. Punctele fixe de interes sunt ı̂n general vectori obţinuţi prin prelucrări marginale: 7 fie medie (xf ix = xi = xmedie ), fie median (xf ix = medianxi = xmed ). O asemenea ordonare este interesantă atâta vreme cât vectorul al cărui scalar asociat are valoarea minimă este cel mai bun candidat, dintre vectorii observaţiilor, pentru punctul fix (central) faţă de care s-a făcut ordonarea. S-a propus de asemenea folosirea unor distanţe ponderate de la fiecare vector de culoare din fereastra de filtrare la medianul marginal local m; ponderarea se face prin utilizarea unor matrici diagonale: 1/wR 0 0 1/wG 0 (xi − m) si = (xi − m)T 0 0 0 1/wB adică si = (xi1 − m1 )2 (xi2 − m2 )2 (xi3 − m3 )2 + + wR wG wB Ponderile wR , wG , wB sunt astfel alese ı̂ncât să reflecte importanţa fiecărei componente a vectorilor; la fel ca şi pentru ordonarea lexicografică, aceste ponderi sunt măsuri de activitate locale, ca: intervalul de variaţie, varianţa, intervalul de variaţie normat la medie sau raportul de contrast (varianţa normată la medie). O altă variantă de scalar construit pe baza unor distanţe este scalarul obţinut ca sumă a distanţelor de la vectorul dat la toţi ceilalţi vectori ai setului de ordonat (distanţă agregată [3]): si = n X (xj − xi )T A−1 (xj − xi ) (1.9) j=1 După cum se arată ı̂n [2], [33] medianul setului de date este caracterizat de o distanţă agregată minimă, indiferent dacă ne aflăm ı̂n cazul scalar sau vectorial: xV M F = arg min {si } (1.10) i=1,n Filtrul care funcţionează după acest principiu a fost denumit median vectorial VMF (Vector Median Filter ) [2]; introducerea acestui filtru a constituit ı̂nceputul erei de adevărată prelucrare multicanal a semnalelor vectoriale, fiind primul filtru construit special pentru date multivariate ce utilizează ı̂n mod intrinsec corelaţia dintre canalele semnalului. De fapt, vector medianul [2] nu este decât o redescoperire inginerească a ceea ce statistica multivariată numea “punct de distanţă agregată minimă”, punct care ı̂i intersase pe economişti şi planificatori (pentru care determinarea acestuia este cunoscută ca problema generalizată a lui Weber [3], de plasare optimală a unui depozit de materiale ce deserveşte mai multe uzine). Principalul dezavantaj al VMF este volumul mare de calcule: pentru a calcula medianul vectorial al unui set de N valori, este necesară calcularea distanţelor dintre toate observaţiile mulţimii, deci N (N − 1)/2 distanţe. Acesta duce la o complexitate O(pN 2 ) a numărului de ı̂nmulţiri. O diminuarea a complexităţii calculului VMF se poate realiza prin construirea unei aproximări rapide a distanţei Euclidiene. Această aproximare se bazează pe o combinaţie liniară a statisticilor de ordine a componentelor vectorului pentru care se calculează norma, după formula: kxk2 = a p √ X ( i− √ i − 1) |x|(i) i=1 cu a= 1+ s 2 p √ √ P ( i − i − 1)2 i=1 8 Pentru cazul vectorilor de culoare, p = 3, a = 0.9398 şi norma vectorului de culoare x este dată cu o eroare de 1 − a (6.019 %) de aproximarea: kxk2 = 0.9398 |x|(1) + 0.3893 |x|(2) + 0.2987 |x|(3) . După cum se demonstrează ı̂n [2], distanţa Euclidiană (normă L2 ) este folosită ca bază a VMF datorită optimalităţii sale pentru un zgomot modelat de o distribuţie normală; dacă distribuţia devine biexponenţială, distanţa trebuie calculată ca o normă L1 [2]. Ideea de modificare a metricii folosite ı̂n calculul distanţei a fost folosită şi ı̂n alte implementări (de exemplu metrici din familia de norme Lβ ). Ideea a fost extinşă prin propunerea de a folosi o combinare după două norme: fiecare distanţă ı̂ntre observaţii este calculată pe baza unei norme Lβ , iar agregarea distanţelor se face după o normă Lα , producând un scalar de forma: si = n X j=1 p X (xjk k=1 !1/β α 1/α − xik )β (1.11) Evident, pentru α = β = 1 se obţine medianul vectorial clasic [2]; pentru α, β > 1 se obţine un efect echivalent de netezire şi de reducere a zgomotului, iar pentru α < 1, β > 1 filtrul se comportă ca un filtru de ordonare după rang, favorizând diferite statistici de ordine. Slaba performanţă a filtrului VMF (indiferent de norma care generează distanţa folosită la calculul scalarului si ) ı̂n prezenţa zgomotului gaussian a dus la ideea combinării acestuia cu un filtru de mediere; ieşirea unui asemenea filtru compozit, denumit EVMF (Extended Vector Median Filter ) [2] este identică fie cu medianul vectorial VMF, fie cu media marginală, după cum aceste puncte sunt cele mai centrate (ı̂n sensul distanţei agregate minime la observaţiile din fereastra de filtrare). Este de asemnea posibilă utilizarea a mai multe ferestre de filtrare, parţial suprapuse, pentru fiecare pixel al imaginii; ı̂n fiecare asemenea fereastră se calculează un median vectorial, iar valoarea filtrată este obţinută printr-o serie de comparaţii ca una dintre valorile mediane astfel calculate, obţinând efecte de eliminare a zgomotului impulsiv sau de accentuare a contururilor ı̂n imagini nedegradate de zgomot. Ordonare bazată pe orientare unghiulară Criteriile de ordonare a observaţiilor vectoriale folosite până ı̂n acest moment au ilustrat doar componenta modul a vectorilor; componenta de tip orientare (unghi) a rămas neexplorată până ı̂n momentul introducerii noţiunii de filtru [median, ı̂n principiu] direcţional. Acest tip de filtre, introduse ı̂n [45] se bazează pe folosirea ca scalar si pentru ordonarea redusă, a distanţei agregate unghiulare a observaţiilor vectoriale, deci suma unghiurilor de la fiecare vector la toţi ceilalţi. Ca şi pentru filtrul median vectorial VMF [2], filtrul direcţional de bază BVDF (Basic Vector Directional Filter ) produce ca ieşire vectorul a cărui distanţă unghiulară agregată este minimă. Pentru un asemenea filtru, scalarul de ordonare este deci ! n n X X hxi , xj i si = xd arccos (1.12) i xj = kxi k kxj k j=1 j=1 şi medianul direcţional se defineşte ca: xV DF = arg min {si } (1.13) i=1,n Una dintre motivaţiile principale ale considerării prelucrărilor direcţionale este legată de natura particulară a unor clase de imagini (sau semnale) multidimensionale, mai precis imaginile color. Pentru culori reprezentate ı̂n spaţiul RGB primar, intersecţia vectorului de culoare cu planul (triunghiul) Maxwell prezintă o importanţă deosebită. Pe de o parte, una dintre măsurile de bază de calitate a 9 prelucrărilor imaginilor color este definită ca o eroare pătratică medie normalizată a valorilor ı̂n planul Maxwell (aceasta este MCRE, Mean Chromaticity Error ); pe de altă parte, după cum se arată şi ı̂n [8], cromaticitatea unei culori (nuanţa şi saturaţia culorii) este determinată de distanţele de la intersecţia vectorului de culoare cu planul Maxwell la culorile primare maxim saturate (roşu, verde şi albastru pur). Este evident că acest punct de intersecţie depinde numai de orientarea vectorului de culoare şi nu de modulul acestuia. Filtrarea direcţională generalizată GVDF (Generalized Vector Directional Filter ) [45], este o extindere a BVDF ce selecţionează mai multe observaţii ca ieşire posibilă a filtrului, observaţii ce au cele mai mici distanţe unghiulare agregate[47]; ı̂n esenţă, această selecţie multiplă permite ca să se realizeze o a doua selecţie a unui singure observaţii de ieşire, prin operaţii de distanţă (modul). Abordarea direcţională a fost folosită şi pentru detectarea contururilor ı̂n imagini color şi pentru realizarea segmentării pe regiuni a imaginilor color prin ı̂ncorporarea informaţiei de orientare (unghi faţă de vecini) la descrierea pixelilor. Ordonare bazată pe distanţe şi orientare unghiulară Comportările relativ complementare ale celor două tipuri esenţiale de filtre vectoriale (cu ordonare după distanţe şi cu ordonare după direcţie) ı̂n ceea ce priveşte eficienţa ı̂n zgomotele principale (impulsiv şi gaussian) a condus la ideea combinării celor două tipuri de prelucrări, ı̂ntr-o abordare mixtă modul-direcţie. O primă etapă a combinării celor două principii a fost introdusă prin aplicarea secvenţială a unei preselectări după direcţie a vectorilor (GVDF) urmată de o prelucrare după modul a acestora (fie scalară, după componenta de luminanţă, fie ca VMF). Un alt mod de a lua ı̂n calcul distantele ”ı̂n valoare” şi unghiulare constă sin construirea unui scalar si care să integreze atât informaţia direcţională cât şi informaţia de modul a vectorilor ce se prelucrează. Modelul cel mai general folosit este o combinaţie exponenţial convexă a distanţelor agregate unghiulare şi Euclidiene ı̂ntre vectorii setului: si = n X j=1 p xd i xj n X j=1 1−p kxi − xj k (1.14) Filtrul realizat prin ordonarea vectorilor după scalarul (1.14) a fost numit DDF(Distance Directional Filter ) şi este generalizarea unui filtru simplu definit anterior cu p = 0.5. Valoarea parametrului p care asigură rezultate optimale pentru o gamă largă de distribuţii de zgomot este p = 0.75, deci atribuind o pondere mai mare caracterului direcţional. O altă modalitate de a integra prelucrările direcţionale şi de distanţă este de a comuta ı̂ntre ieşirea filtrului VDF şi VMF. O posibilitate este de a construi ieşirea filtrului pe direcţia vectorului VDF şi cu modulul vectorului VMF: kxV M F k xout = xV DF kxV DF k În plus, se poate introduce un grad suplimentar de “fineţe” a comparaţiei, luând ı̂n calcul şi media marginală a observaţiilor, vectorul de ieşire fiind pe direcţia VDF şi cu modulul vectorului VMF sau mediei marginale, după cum unul dintre aceşti vectori este cel mai central situat, ı̂n sensul distanţei agregate minime la observaţiile setului de prelucrat. 10 Ordonare bazată pe proiecţii Metodele de ordonare redusă prezentate până ı̂n prezent s-au bazat esenţial pe considerarea poziţiilor relative a vectorilor de ordonat ı̂n spaţiul original de reprezentare a acestora (spaţiul eşantioanelor), fie prin măsurarea distanţelor, fie prin măsurarea unghiurilor, fie prin considerarea ambelor. O variantă nouă de determinare a unor scalari si de ordonare a vectorilor pleacă de la ideea modificării spaţiului de reprezentare a acestora; o reprezentare echivalentă ı̂ntr-un spaţiu de dimensiune mai mică va duce la reducerea dimensiunii vectorului, iar, prin repetare, se poate ajunge la un scalar. O asemenea metodă a fost numită metodă proiectivă. Observaţia iniţială se raportează la utilizarea triunghiului (planului) Maxwell ı̂n spaţiul RGB primar. Dar acest punct de intersecţie este definit de numai două coordonate independente, şi nu de trei, precum culoarea din care provine, şi poate fi considerat ca proiecţia vectorului de culoare pe planul Maxwell. Repetarea acestei proiecţii ı̂n plan, pe “dreapta Maxwell” (definită de ecuaţia x1 + x2 = 1) va reduce ı̂ncă o dată dimensiunea vectorului, până la un scalar. În cazul general, pentru un vector p dimensional, x = (x1 , x2 , ..., xp ), vom defini xk , vectorul după a k-a proiecţie (compusă dintr-o rotaţie şi o translaţie, deci o transformare afină); proiecţia se defineşte astfel ı̂ncât primele k componente ale vectorului xk să fie nule, deci x1 = (0, x11 , ..., x1p−1 ), xk = (0, 0, ..., xk1 , ..., xkp−k ). Ultima proiecţie va produce vectorul xp−1 = (0, ..., 0, xp1 ) ce are o unică componentă nenulă. Această unică componentă nenulă este scalarul după care se face ordonarea; vectorul al cărui 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)), proiecţiile vor produce scalarii (1 + sR = (1 + (1 + sG = (1 + (1 + sB = (1 + √1 )(G 3 √1 )(G 3 + B − 1) + √1 )(R 3 √1 )(R 3 + B − 1) + √1 )(R 3 √1 )(R 3 + G − 1) + + B − 1) − + B − 1) − + G − 1) − √2 R 3 √2 R 3 √2 G 3 √2 G 3 √2 B 3 √2 B 3 după cum prima rotaţie este după axa R, G, sau B. Alegerea unui anume scalar se face adaptiv, conform criteriilor locale de activitate a fiecărei componente. Filtrul median prin proiecţii iterative pe planul Maxwell se comportă mai bine decât filtrul VMF clasic ı̂n condiţii de zgomot mic (impulsiv şi mixtură); ı̂n plus, şi volumul de calcule necesare pentru a calcula scalarul este extrem de mic – filtrul cu proiecţii iterative necesită 27 ı̂nmulţiri pentru fiecare pixel (considerând o fereastră pătrată de 3 x 3 pixeli) iar filtrul VMF necesită 144 ı̂nmulţiri (şi un număr mult mai mare de adunări). Ordonare bazată pe curbe de umplere a spaţiului În prelucrarea imaginilor, problema reducerii unor obiecte vectoriale la scalari nu este nouă, şi a apărut odată cu considerarea primelor metode de codare a imaginilor, ca aplicaţii directe ale metodelor existente pentru semnalele unidimensionale. Aplicarea unei asemenea metode necesita transformarea semnalului bidimensional imagine ı̂ntr-un semnal unidimensional prin parcurgerea corespunzătoare a tuturor pixelilor. Parcurgerea (sau baleierea imaginii) ı̂nseamnă de fapt stabilirea unei ordini de 11 Fig. 1.2: Curbe de umplere a spaţiului - cazul bidimensional. vizitare a fiecărui punct a grilei rectangulare de reprezentare a imaginii, deci ordonarea unor vectori bidimensionali (ale căror componente sunt coordonatele pixelilor). O asemenea parcurgere a fost formalizată matematic ca o curbă de umplere a spaţiului [9]. O curbă de umplere a spaţiului T este o aplicaţie bijectivă ce asociază fiecărui punct din Z 2 (punctul din plan) un număr natural (numărul de ordine): T : K ⊂ Z 2 −→ N, T (xk ) = nk Curba de umplere a spaţiului va trece prin fiecare punct al mulţimii baleiate o singură dată (nu se va autointersecta). O clasă particulară a acestor curbe are proprietăţile suplimentare de autosimilaritate (sunt fractali) şi de păstrare a corelaţiei spaţiale (puncte care sunt vecine pe curbă, sunt vecine ı̂n plan). Exemplul cel mai cunoscut de astfel de curbă este curba Hilbert, cunoscută ı̂n două variante: curba Peano (sau curba Hilbert ı̂n U) şi curba Morton (sau curba Hilbert ı̂n Z) [9], [48]. Denumirea celor două curbe provine de la forma celulei de bază (reprezentate ı̂n figura 1.2.4). Proprietăţile de bijectivitate a curbelor Hilbert (şi ı̂n general a curbelor de umplere a spaţiului) au fost propuse pentru ordonarea redusă a vectorilor [40]: fiecărui vector i se asociază indicele punctului de pe curba de umplere a spaţiului corespunzător. Scalarii (indicii de pe curbă) sunt ordonaţi, iar vectorul al cărui indice este medianul valorilor indicelor extrase este ales ca median a setului de vectori. Problema esenţială legată de utilizarea unor curbe de tip Hilbert pentru calcularea scalarilor de ordonare redusă este aceea a modificării structurii de vecinătate a spaţiului indicilor faţă de spaţiul iniţial: puncte vecine din spaţiul iniţial nu mai sunt vecine ı̂n spaţiul indicilor, şi reciproc [40]. Aceasta duce la apariţia de artefacte pe imaginile prelucrate, chiar la nivele mici de zgomot. Pentru a evita asemenea efecte trebuiesc folosite curbe care să păstreze cât mai bine structura de vecinătate a spaţiului vectorial iniţial, şi deci corelaţia dintre vectori. Este evident că curba Hilbert ı̂n U (Peano) este mult mai potrivită din acest punct de vedere decât curba Hilbert ı̂n Z (Morton). Aceeaşi observaţie conduce la definirea a unor curbe cu aspect “spiralat” [40]. 12 Esenţial, problema care va decide eficienţa practică a unei curbe (pentru probleme de filtrare a imaginilor color, de exemplu) este ı̂nsă problema calculului indicelui pe curbă al unui anume vector. Trebuie să remarcăm că soluţia de implementare cu un LUT nu este realizabilă: pentru vectori p dimensionali exprimaţi cu b biţi pe fiecare componentă, tabelul de echivalenţă ar trebui să conţină 2pb numere de pb biţi (pentru imagini color obişnuite acesta ı̂nseamnă 224 numere de 3 octeţi, deci 12 MB). Atât pentru curba Peano, cât şi pentru curba definită de [40], trecerea de la cazul plan de definire la vectori de dimensiune superioară implică o procedură recursivă, cu decizii multiple. Spre deosebire de acesta, pentru curba Morton, indicii se calculează extrem de simplu: forma binară a indicelui pe curbă a unui vector se obţine prin ı̂ntreţeserea formelor binare a componentelor vectorului; dacă componenta xi a vectorului p dimensional este exprimată ı̂n formă binară ca xi,b−1 xi,b−2 ...xi,1 xi,0 , atunci forma binară a indicelui este [9]: x1,b−1 x2,b−1 ...xp,b−1 x1,b−2 x2,b−2 ...xp,b−2 ...x1,0 x2,0 ...xp,0 Diversitatea de metode de ordonare prezentate ı̂n acest capitol oferă o perspectivă asupra posibilităţilor de implementare a filtrelor de ordonare (şi ı̂n particular filtrul median) pentru imaginile vectoriale (color). Eficienţa acestor filtre este asemănătoare analoagelor lor scalare şi ı̂şi arată limitele ı̂n cazul filtrării unor zgomote de tip mixtură. Ceea ce se impune este deci modificarea structurii de filtrare prin considerarea tuturor vectorilor din fereastra de filtrare. 13 Capitolul 2 FILTRAREA NELINIARĂ FĂRĂ PRINCIPII DE ORDONARE După cum am mai amintit, filtrarea neliniară poate apare ca o consecinţă a mai multor procedee de prelucrare: fie prelucrări intrinsec neliniare (aşa cum este ordonarea valorilor extrase de fereastra de filtrare, ca ı̂n cazul filtrelor cu ordonare după rang sau a L-filtrelor), fie adaptarea unei structuri de prelucrare care, intrinsec, nu este neliniară. Adaptarea se referă la modificarea parametrilor de definiţie a unui filtru ı̂n funcţie de caracteristicile locale ale semnalului (imaginii) de prelucrat. În mod uzual, un filtru, interpretat ca o operaţie locală (de vecinătate), este definit de o fereastră de filtrare (mulţime de puncte ce defineşte vecinătatea punctului curent de prelucrat) şi de o mulţime de coeficienţi (sau ponderi), ataşaţi poziţiilor ferestrei de filtrare. Adaptarea se poate referi fie la modificarea coeficienţilor de definiţie a filtrului, fie la modificarea formei ferestrei de filtrare. În cele ce urmează vom considera filtrele neliniare obţinute ca urmare a adaptării unei filtrări liniare; dacă {xj } este mulţimea celor n vectori (valori ale pixelilor) din fereastra de filtrare curentă, atunci ieşirea filtrului pentru poziţia dată este combinaţia liniară ponderată a acestor valori: Card(W ) y= X wj xj , xj ∈ W (2.1) j=1 Pentru o filtrare de netezire (deci de reducere a zgomotului), coeficienţii wj trebuie să satisfacă [8], [18] condiţia de normare (care asigură invarianţa pentru zone uniforme): Card(W ) X wj = 1 (2.2) j=1 Adaptarea semnifică că mulţimea coeficienţilor filtrului este diferită, de la un punct la altul al imaginii şi ı̂n funcţie de conţinutul acesteia, şi deci wj = wj (m, n, x(m, n)), sau că vecinătatea se modifică, dependent de punctul curent de prelucrare, W = W (m, n). Ceea ce trebuie ı̂nsă remarcat este faptul că cele două aspecte ale adaptării nu sunt independente: un coeficient de ponderare extrem de mic (la limită nul) semnifică neluarea ı̂n calculul ieşirii y a filtrului a valorii respective, deci, echivalent, eliminarea poziţiei corespunzătoare din fereastra de filtrare. Problema determinării adaptive a ponderilor asociate unei ferestre de filtrare de formă impusă poate fi abordată din mai multe puncte de vedere: coeficienţii pot fi dependenţi (ı̂n mod explicit) de distanţele dintre vectorii selectaţi de fereastra de filtrare, prin ceea ce a fost denumit DDMF - Distance Dependent Multichannel Filter ; deducerea coeficienţilor se poate face prin abordări de clustering sau de estimare statistică; coeficienţii pot fi deduşi printr-o abordare bazată pe integrarea logicii vagi (fuzzy) 14 ı̂n abordările clasice. De asemenea, se pot avea ı̂n vedere şi metode bazate pe calculul unei ferestre de filtrare adaptive. 2.1 Filtre dependente de distanţă Prelucrările cunoscute sub numele de filtrări cu coeficienţi dependenţi de distanţă, şi denumite DDMF - Distance Dependent Multichannel Filter [16] sau MDF - Multichannel Distance Filter [14] reprezintă o clasă de filtre adaptive, bazate pe (2.1), ı̂n care coeficienţii de ponderare a vectorilor sunt deduşi ı̂n funcţie de distanţele relative dintre aceştia (deci conform distribuţiei lor ı̂n spaţiul de reprezentare). Spaţiul de reprezentare a vectorilor (pentru cazul imaginilor color) este spaţiul RGB primar, chiar dacă distanţele euclidiene dintre vectori nu sunt ı̂n concordanţă cu diferenţele perceptuale de percepere a culorilor reprezentate de aceştia. În general, ceea ce se deduce direct pentru fiecare vector este o pondere a contribuţiei sale la ieşirea filtrului, aj , ponderi care, pentru setul de n vectori ai ferestrei de filtrare, nu respectă condiţia de normare a coeficienţilor, impusă de (2.2). Îndeplinirea condiţiei de normare este asigurată prin construirea ponderilor de filtrare ca raportul dintre coeficienţii de ponderare şi suma acestora: aj (2.3) wj = P n aj i=1 2.1.1 Folosirea distanţei euclidiene dintre vectori Modul de construcţie a coeficienţilor de ponderare a vectorilor este ı̂n principiu inspirat din modalităţile de ordonare redusă a respectivilor vectori, deja discutate ı̂n capitolul anterior. În general, coeficientul de ponderare este o funcţie dependentă de un scalar dj , de tip scalar de ordonare (sj ). Funcţiile de tip polinomial au fost folosite cu succes de majoritatea cercetătorilor. Cea mai simplă funcţie propusă este puterea r a scalarului: 1 aj = r (2.4) dj Această abordare a fost introdusă ı̂n [14] (ANL1 - Adaptive Non-Linear ), [7] (MDF1) şi [16] (DDMF2). Scalarul de tip distanţă dj trebuie să exprime situarea vectorului curent xj , căruia ı̂i este ataşat, faţă de ieşirea dorită a filtrului, şi deci trebuie să fie cu atât mai mare cu cât vectorul curent este mai depărtat de valoarea corectă (deci mai afectat de zgomot). Pentru a satisface această cerinţă, ı̂n [14] şi [7] se foloseşte distanţa euclidiană agregată (suma distanţelor de la vectorul curent la toţi ceilalţi vectori ai ferestrei de filtrare); ı̂n [15] este folosit acelaşi model pentru prelucrarea semnalelor unidimensionale multicanal (semnale seismice): dj = n X kxi − xj k (2.5) i=1 În [16] se propune folosirea distanţei de la vectorul curent la un punct fix, ce este ı̂n general un estimator marginal al ieşirii dorite (ı̂n general, medianul marginal multicanal, dar şi vectorul ce corespunde poziţiei ı̂n care se face filtrarea, deci vectorul din originea ferestrei de filtrare): dj = kxf ix − xj k (2.6) Pentru a evita cazurile de nedeterminare ı̂n evaluarea lui aj (ce pot apare când dj = 0), ı̂n [7] şi [16] s-a propus modificarea distanţei prin adunarea unei constante ε, care este fie unitară (ε = 1) [7] pentru MDF2, fie este foarte mică (ε −→ 0) [16] pentru DDMF2: dj = kxf ix − xj k + ε 15 (2.7) Testele efectuate asupra comportării acestui tip de filtre ı̂n prezenţa a diferite distribuţii de zgomot au condus la concluziile folosirii unor valori specifice ale puterii r: r = 1 pentru zgomot uniform, r = 0 pentru zgomot gaussian (ceea ce ı̂nseamnă de fapt că ponderile tuturor vectorilor sunt egale, şi filtrul obţinut este de fapt filtrul de mediere marginală), r = −2 pentru zgomot de tip laplacian sau cu alte distribuţii de tip “long tail ” (cu coadă lungă). Adaptarea propriu-zisă a puterii r ı̂n funcţie de caracteristicile locale ale imaginii (semnalului) - deci ı̂n interiorul ferestrei de filtrare - se poate face conform caracteristicilor statistice locale de ordinul doi ale semnalului [6]. Filtrul propus, AMDF Adaptive Multichannel Distance Filter, se bazează pe o extindere multicanal a unui algoritm clasic de estimare a varianţei locale a semnalului util şi a zgomotului [28], [55]. Pe fiecare canal (deci pe fiecare plan de culoare a imaginii color) se face o estimare a varianţei locale de pe canalul j, ı̂n poziţia curentă 2 , prin: de filtrare, σxj 2 σxj = n P i=1 x2ij − 1 n n P xij 2 i=1 n−1 Pentru fiecare canal, se stabileşte un coeficient de importanţă a efectului zgomotului faţă de variaţiile proprii ale semnalului: 2 σxj cj = 1 − 2 σnj iar pe baza acestui coeficient se alege puterea r corespunzătoare: r= ( 0, dacă min{cj } ≥ 0 min{cj }, ı̂n rest. (2.8) Plecând de la ideea folosirii de distanţe la puncte fixe (2.6), ı̂n [16] s-a reluat ideea din [44], de a suma distanţele la mai multe puncte fixe reprezentative, ca medianul marginal, media marginală şi punctul central (din originea ferestrei de filtrare), rezultând un filtru numit DDMF3, cu o distanţă: dj = kxmedie − xj k + kxmedian − xj k + kxcentru − xj k (2.9) Scalarul de distanţă dj asociat fiecărui vector exprimă calitatea sa (deci măsura ı̂n care valoarea sa este neafectată de zgomot); exprimarea unei asemenea măsuri trebui ı̂nsă să ţină seama şi de ceilalţi vectori din fereastra de filtrare; ı̂n acest context scalarul propus ı̂n [14] pentru filtrul MDF2 este construit ca suma distanţelor dintre toţi vectorii ferestrei de filtrare, mai puţin vectorul curent: aj = n 1X di − dj 2 i=1 unde dj este distanţa euclidiană agregată din (2.5). O altă funcţie propusă pentru transformarea distanţelor dintre vectorii ferestrei de filtrare ı̂n ponderi relative individuale este o funcţie de tip exponenţial [16], determinată de parametrii α > 1 şi 0 < β < 1: dj aj = exp − ln α βdmax Constanta dmax este determinată ca fiind distanţa maxim posibilă dintre vectori pentru semnalul studiat (ı̂n cazul√imaginilor color reprezentate cu 8 biţi pentru fiecare plan de culoare, aceasta este dmax = 8 · 255 · 3). Acestă relaţie exprimă principiul general conform căruia vectorii ce au asociate distanţe mici trebuie să aibă asociate ponderi mai mari (mai ales ı̂n cazul ı̂n care se doreşte eliminarea impulsurilor de zgomot şi păstrarea clarităţii tranziţiilor din imagine). Testele experimentale au arătat că o combinaţie eficientă de parametri este α = 2 şi β = 0.05 [16]. 16 2.1.2 Folosirea distanţei unghiulare dintre vectori După cum am arătat şi ı̂n secţiunea privind filtrarea bazată pe ordonare directă a vectorilor, ı̂n cazul imaginilor color, informaţia de culoare (crominanţă, saturaţie) este mai importantă decât informaţia de intensitate luminoasă, şi deci pare naturală folosirea unor criterii de comparaţie (ordonare, ponderare) a vectorilor care să ia ı̂n considerare această informaţie direcţională. Aceasta este abordarea numită Vector Directional [46], ı̂n care distanţa dintre vectori este ı̂nlocuită cu unghiul dintre respectivii vectori. O asemenea abordare a fost adoptată ı̂n [38]; pe baza distanţei agregate unghiulare dj (1.12) sau (2.10) dintre vectori se derivă coeficienţi aj ce exprimă ponderea cu care vectorul xj participă la ieşirea filtrului. ! n n X X hxi , xj i (2.10) dj = xd arccos i xj = kxi k kxj k i=1 i=1 În [38] se propune FVDF - Fuzzy Vector Directional Filter, pentru care fiecare coeficient de ponderare a vectorilor este dat de o formulă ce grupează abordările polinomială şi exponenţială : aj = 1 1 + exp(drj ) Pentru rezultate optime, parametrul de control r are valorile 1 sau 2. Această construcţie impune două comentarii: ı̂n primul rând, filtrul vector direcţional de bază (BVDF) se poate obţine selectând doar vectorul a cărui coeficient aj este maxim; ı̂n al doilea rând, termenul de fuzzy ce apare ı̂n denumirea filtrului nu exprimă neapărat existenţa unor inferenţe logice a unui set de reguli, ci se justifică prin normarea (2.3) care produce numere subunitare pozitive, ce pot fi interpretate ca grade de apartenenţă ale fiecărui vector din fereastra de filtrare la clasa “valoare corectă”. O altă abordare bazată de distanţa agregată unghiulară dj este prezentată ı̂n [34] şi se bazează pe construcţia unor coeficienţi de ponderare daţi de: aj = max{di } − dj max{di } − min{di } Acest filtru a fost denumit ANNMF - Adaptive Nearest Neighbor Multichannel Filter. O modificare a sa se poate obţine dacă ı̂n locul distanţei unghiulare agregate se foloseşte doar unghiul dintre vectorul curent şi un vector de referinţă (2.11) (deci acelaşi principiu ca şi ı̂n cazul folosirii distanţei euclidiene). Vectorul de referinţă (dacă nu este chiar centrul ferestrei de filtrare) se calculează ı̂n general ı̂ntr-o altă fereastră de filtrare (de dimensiune mai mică decât fereastra de filtrare curentă); de aceea filtrul astfel construit se numeşte DWANNMF - Double Window Adaptive Nearest Neighbor Multichannel Filter [34]: dj = xfd (2.11) ix xj În fine, ca şi ı̂n cazul ordonării vectorilor, se pot considera abordări mixte, distanţă - unghi, deci integrarea ı̂ntr-un singur scalar (printr-un produs) a distanţelor agregate unghiulare şi euclidiene [19], [20]. O asemenea variantă este propusă ı̂n [16] ca DDMF4: dj = n X i=1 sau ca dj = n X i=1 xd i xj ! xd i xj ! · n X ! kxi − xj k i=1 · (kxmedie − xj k + kxmedian − xj k + kxcentru − xj k) 17 2.2 Filtrarea prin estimare statistică Filtrarea poate fi interpretată şi ca o estimare [statistică] a valorii corecte a pixelului curent, ı̂n condiţiile ı̂n care se dispune de observaţii perturbate de zgomot (pixelul curent şi vecinii săi din imaginea degradată). Una dintre metodele simple de determinare a unor estimaţi ai unor mărimi statistice pe baza unui set unic de observaţii sunt cunoscute ı̂n statistică ca metode de reeşantionare a datelor [27]. Asemenea metode (relativ similare) sunt metodele jack-knife şi bootstrap, folosite mai ales pentru construirea de intervale de ı̂ncredere ale estimatelor. Cea mai rapidă dintre cele două metode este metoda jack-knife, pe care am folosit-o ı̂n construirea unor filtre mediane vectoriale. Principiul tehnicii jack-knife este următorul: să presupunem că se doreşte determinarea unui estimat θb al unui parametru oarecare θ al unei populaţii formate din n observaţii p dimensionale P = {x1 , x2 , ..., xp }. Din populaţia iniţială se construiesc n noi populaţii, fiecare dintre acestea conţinând toate observaţiile iniţiale, mai puţin observaţia xi : Pi = P \ {xi }, i = 1, 2, ..., n Pentru fiecare nouă populaţie de n − 1 observaţii se construieşte un estimat θbi , iar pe baza tuturor celor n estimate astfel calculate, se construieşte estimatul jack-knife θbjk printr-o operaţie de mediere aritmetică. n 1X θbjk = θbi n i=1 Aplicaţia propusă a acestei tehnici este realizarea unui filtru median vectorial; aceasta ı̂nseamnă că estimatele θbi sunt mediane ale vectorilor ce formează populaţiile Pi . Aceste estimate pot fi obţinute prin orice fel de tehnică de tip median vectorial (deci median marginal, sau VMF, sau VDF, ...). Complexitatea algoritmică a noului filtru este de acelaşi ordin de mărime cu a filtrelor de bază prin care se calculează estimatele θbi . Noul filtru este mult mai robust ı̂n prezenţa zgomotului gaussian, datorită medierii estimatelor parţiale. În [22], [24], [21] se propune utilizarea unui filtru MTM - Modified Trimmed Mean vectorial (multivariat), ca extensie directă a filtrului scalar analog; filtrul scalar mediază un număr dat de statistici de ordine situate simetric faţă de median. Extensia vectorială a MTM este bazată pe ordonarea redusă a vectorilor din fereastra de filtrare prin distanţe faţă de un punct fix (medianul marginal), calculate ca distanţe Mahalanobis (C fiind matricea de covariaţie locală): si = (xi − xmed )T C−1 (xi − xmed ) Esenţa problemei este faptul că matricea C este necunoscută. Estimarea ei prin medie şi varianţe locale este ineficientă, deoarece acestea nu sunt estimate robuste, şi valorile acestora sunt puternic influenţate de prezenţa chiar a unui singur vector aberant (“outliar ”). În [22], [24], [21] se analizează diferite metode, directe şi iterative, de estimare a matricii de covariaţie şi se studiază robusteţea estimatelor obţinute şi a filtrelor realizate pe baza lor la diferite tipuri de zgomote. O altă abordare a creşterii robusteţii structurilor de filtrare este aceea de a ı̂ncerca determinarea unui estimat liniar (optim ı̂n sensul minimizării unei funcţii de cost pătratic a erorii de estimare); ı̂n acest caz estimatul este [43]: b= x Z∞ xf (x|y)dx = −∞ R∞ xf (x, y)dx −∞ f (y) (2.12) În cazul general, distribuţia zgomotului ce a afectat imaginea nu este cunoscută, şi densităţile de probabilitate implicate ı̂n (2.12) nu pot fi determinate prin tehnici parametrice; atunci soluţia constă 18 ı̂n determinarea lor prin tehnici neparametrice, pe baza mulţimii observaţiilor. Metoda de estimare folosită ı̂n [35] şi [36] este o estimare cu nuclee (“kernel estimator ”). Astfel, funcţia de densitate de probabilitate necunoascută f (z) este estimată neparametric din setul de n observaţii multivariate (de dimensiune p) independente (realizări particulare ale procesului aleator) prin: fb(z) = n 1X (hi )−p K n i=1 z − zi hi (2.13) Funcţia K : Rp −→ R este nucleul de estimare (funcţie pozitivă, centrată pe 0, de arie unitară a subgraficului); ı̂n [36] sunt folosite nuclee de estimare exponenţiale: K(z) = e−|z| 1 T z K(z) = e− 2 z Scalarii hi sunt parametrii de netezire, definiţi ı̂n funcţie de distanţa euclidiană agregată dintre vectorul curent zi şi ceilalţi vectori ai mulţimii de observaţii; aceştia au forma: hi = n − kp Ai = n − kp n X j=1 kzj − zi k (2.14) Folosind expresiile (2.13) şi (2.14) ı̂n (2.12), şi folosind observaţiile din imaginea cu zgomot xi obţinem: b= x n hi −p K X P n −p hj i=1 K j=1 x−xi hi xi x−xi hj Acest estimat liniar corespunde unei combinaţii liniare a vectorilor ferestrei de filtrare cu coeficienţii de ponderare x − xi wi = hi −p K (2.15) hi În [36] sunt propuse două extensii ale acestui filtru, rezultate direct din aplicarea teoriei estimării: ı̂n primul rând s-a introdus un factor suplimentar de reglaj prin varierea coeficienţilor de netezire a nucleelor de estimare după o putere r, caz ı̂n care ponderile filtrului liniar din (2.15) devin: wi = hi −p K x − xi hri ! Un estimator cu o calitate superioară se poate obţine printr-o tehnică de filtrare cu fereastră dublă (DW - Double Window ), prin care fiecare observaţie zgomotoasă din fereastra de filtrare este ı̂nlocuită de un median vectorial (marginal sau VMF) al valorilor dintr-o fereastră mai mică centrată ı̂n punctul respectiv. Deşi această abordare este foarte robustă şi permite realizarea de filtre cu performanţe bune de rezistenţă la diferite tipuri de zgomote (impulsive şi mixturi), complexitatea unui asemenea filtru o depăşeşte pe cea a abordărilor ce nu folosesc estimarea. 2.3 Filtrarea cu vecinătăţi adaptive După cum am arătat ı̂n introducerea acestui capitol, adaptarea se poate referi fie la modificarea coeficienţilor de definiţie a filtrului, fie la modificarea formei ferestrei de filtrare. Modificarea formei ferestrei de filtrare este ı̂n fapt o modalitate de a selecta (sau a ignora) anumiţi vectori din vecinătatea 19 pixelului curent prelucrat. Realizarea acestei trieri se poate realiza prin două metode: dintr-o fereastră de filtrare de formă fixă se rejectează vectorii cu valori aberante contextului local sau fereastra de filtrare este determinată pentru fiecare punct al imaginii de prelucrat. Prima abordare ce conduce la o fereastră de filtrare de formă adaptivă este de a selecta doar acei vectori suficient de apropiaţi de punctul curent (pentru care se face prelucrarea). Această metodă a fost denumită metoda celor mai apropiaţi vecini, NN - Nearest Neighbour [12], [23]. După cum se sugerează prin această denumire, alegerea vectorilor corecţi se face după un criteriu de distanţă minimă: sunt păstraţi doar acei vectori care sunt cei k cei mai apropiaţi de punctul central [12] sau a căror distanţă la punctul central este mai mică decât un prag fixat [23]. Cu vectorii astfel selectaţi se efectuează o prelucrare simplă (ı̂n general o operaţie de mediere sau de median marginal), robusteţea fiind asigurată de rejectarea iniţială a valorilor aberante. Determinarea ferestrei de filtrare după specificul local al punctului de prelucrat (şi deci, implicit, determinarea a câte unei ferestre de filtrare pentru fiecare punct al imaginii de prelucrat) a fost denumită filtrare cu vecinătăţi adaptive [32], [39], [10]. Esenţa acestei metode este de a determina, pentru fiecare pixel al imaginii de prelucrat (color sau cu nivele de gri) o zonă relativ uniformă, conexă, printr-o tehnică de creştere a regiunilor [11], [18], [52] (folosită ı̂n mod uzual la segmentarea orientată pe regiuni a imaginilor). Avantajul determinării unei asemenea zone este dublu: pe de o parte sunt rejectate valorile aberante (de tipul punctelor afectate de zgomot impulsiv), iar pe de altă parte filtrul de netezire realizat cu aceste vecinătăţi va păstra extrem de bine contrastul contururilor din imagine (atâta vreme cât regiunile uniforme nu conţin pixeli aflaţi de o parte şi de alta a respectivelor contururi). Operaţia propriu-zisă de filtrare este o operaţie de mediere simplă [32], [10] sau mediere ponderată cu coeficienţi adaptivi [39]. Principalele probleme ridicate de acestă metodă de filtrare sunt cele de complexitate a calculului: pentru fiecare pixel al imaginii se creşte o regiune ce are ca germene punctul respectiv (aşadar complexitatea este mult mai mare decât la o operaţie de segmentare prin creşterea regiunilor, ı̂n care numărul de germeni este mult mai mic decât numărul de puncte al imaginii). Pentru a asigura o relativă eficienţă a algoritmului, s-a propus introducerea unei limite superioare a dimensiunii regiunii (Nmax pixeli), ı̂mpiedicând astfel extinderea ferestrelor de filtrare ı̂n platourile uniforme foarte ı̂ntinse; ı̂n acelaşi timp o dimensiune minimă (Nmin ) este impusă pentru a avea suficiente valori pe baza cărora să se realizeze estimarea valorii corecte. 2.4 Filtrarea prin tehnici de clustering O abordare hibridă de determinare atât a unor ponderi cât şi a unei ferestre de filtrare specifice fiecărui punct a fost propusă sub numele de filtrare prin clustering. Ideea esenţială este ı̂n continuare aceea de a separa o măcar o parte din valorile aberante ce apar ı̂ntr-o fereastră de filtrare fixă (deci ı̂n vecinătatea pixelului curent prelucrat) şi de a aplica o netezire valorilor rămase. O asemenea tehnică stă la baza filtrării cu vecinătăţi adaptive sau a filtrelor de tip NN (Nearest Neighbour ), prezentate anterior. Abordarea propune realizarea unei partiţionări ı̂n trei clase a vectorilor din fereastra de filtrare; cele trei clase corespund poziţionării vectorilor pe care, ı̂n limbaj natural, am putea să ı̂i numim centrali, extremali superior şi extremali inferor. Din punctul de vedere al statisticilor de ordine, putem considera că vectorii din clasa centrală sunt estimate ale mediei sau medianului vectorial, iar vectorii din cele două clase extreme sunt estimate ale minimului şi maximului local. Pentru realizarea partiţionării ı̂n trei clase a vectorilor selectaţi de fereastră se va folosi un algoritm de clustering, iterativ sau ierarhic. Fiecare clasă a partiţiei (mulţime de vectori selecţionaţi) este caracterizată de ceea ce se numeşte vector prototip (sau centroid), obţinut ca medie aritmetică a vectorilor ce aparţin clasei respective. Ieşirea filtrului de clustering este prototipul clasei centrale, sau 20 vectorul cel mai apropiat de prototipul clasei centrale. Efectele de netezire ale acestui filtru sunt uşor de demonstrat: impulsurile de zgomot sunt eliminate prin separarea vectorilor ı̂n clase şi alegerea ca ieşire a unui reprezentant al clasei centrale (deci cea mai ı̂ndepărtată de extreme) şi calcularea prototipului clasei centrale se face printr-o mediere ce reduce efectul zgomotului gaussian aditiv. Global, filtrarea poate fi caracterizată ca un median ponderat, păstrând contrastul frontierelor imaginii. Comportarea acestui filtru ı̂n prezenţa mixturilor de zgomot (gaussian şi impulsiv) este superioară filtrelor median vectorial clasice (vector median VMF, median marginal). 2.5 Integrarea logicii vagi ı̂n adaptarea filtrelor Logica vagă (fuzzy logic) a fost introdusă la sfârşitul anilor 1960 [54] ca o ı̂ncercare de a manipula incertitudinea şi nedeterminarea din descrierile semantice ale lumii reale; sunt clasice exemplele privind interpretarea conceptelor de ı̂nălţime sau greutate a unei persoane, mai ales prin prisma dificultăţii adaptării logicii clasice binare la o realitate graduală [54], [41]. O mulţime vagă nu este altceva decât o funcţie ce asociază fiecărui element al universului un număr pozitiv subunitar. La aceasta definiţie a mulţimilor vagi merită adăugat comentariul din [5]. Conform definiţiei, orice funcţie reală cu valori în intervalul [0, 1] este o mulţime vagă (fuzzy). În timp ce aceasta este adevărat dintr-un punct de vedere matematic formal, multe funcţii ce satisfac această condiţie nu pot fi interpretate corespunzător ca realizări ale unei mulţimi vagi conceptuale. Cu alte cuvinte, funcţiile ce transformă un univers în intervalul unitar pot fi mulţimi vagi, dar devin mulţimi vagi atunci şi numai atunci când se potrivesc cu o descriere semantică intuitivă plauzibilă a proprietăţilor imprecise ale obiectelor din univers. Una dintre principalele întrebari ridicate de acest mod de reprezentare priveşte relaţia vagului cu probabilitatea, şi mai precis, dacă mulţimile vagi sunt doar o deghizare ingenioasă pentru modelele statistice. Răspunsul negativ la această problemă rezultă evident dintr-un exemplu [5]. Fie universul de obiecte format din mulţimea tuturor lichidelor şi fie mulţimea vagă L={toate lichidele potabile (ce pot fi băute)}. După o săptamână petrecută în deşert fără apă, călătorul însetat descoperă două sticle perfect opace A şi B, marcate cu “A: apartenenţă (A ı̂n L) = 0.91” şi “B: probabilitate (B ı̂n L) = 0.91”, din care trebuie neaparat trebuie să aleagă una pe care să o bea. Problema este deci alegerea corespunzătoare a sticlei. A poate conţine de exemplu apă de baltă sau mlaştină, excluzând desigur posibilitatea existenţei unui modelator fuzzy Machiavelic, şi nu acid clorhidric. Deci apartenenţa de 0.91 înseamnă că conţinutul lui A este destul de similar cu lichidele perfect potabile (în speţă apa pură). De cealaltă parte, probabilitatea de 0.91 ca B să fie potabilă înseamnă că, dintr-un şir lung de experimente, conţinutul lui B va fi potabil în 91% din cazuri; în restul cazurilor, adică la o încercare din zece, conţinutul sticlei putând fi chiar mortal. O altă faţetă a acestui experiment implică ideea de observaţie. Dacă examinăm conţinutul lui A şi B şi descoperim de exemplu că A conţine bere şi B acid clorhidric, după observaţie, gradul de apartenenţă a lui A nu se modifică, în timp ce probabilitatea lui B devine 0. În fine, care ar fi efectul schimbării valorilor numerice la 0.5 ? Majoritatea persoanelor ar bea din B, cu o şansă din două ca lichidul să fie potabil, deoarece un grad de apartenenţă atât de mic indică în principiu un lichid nepotabil (dar aceasta depinde în întregime de funcţia de apartenenţă a mulţimii vagi, ceea ce conduce din nou la observaţia privind posibilitatea de a interpreta orice funcţie cu valori în intervalul unitar ca o mulţime vagă). Deci, cele două modele (vag şi probabilist) propun două tipuri de informaţie total diferită: apartenenţa vagă reprezintă similaritatea unor obiecte cu proprietăţi imprecise, iar probabilitatea dă frecvenţe relative; mai mult, interpretările şi deciziile luate în funcţie de aceste valori depind de numerele specifice asociate unor obiecte şi evenimente particulare. 21 Este deci evident că modelarea vagă şi folosirea logicii vagi nu se reduc la folosirea unor ponderi pozitive subunitare pentru fiecare obiect al universului. Totuşi există cazuri ı̂n care filtre adaptive de mediere ponderată au fost denumite “fuzzy” doar pentru acestă caracteristică a coeficienţilor (de exemplu FVDF - Fuzzy Vector Directional Filter [38]). O metodologie cu adevărat bazată pe logica vagă este dezvoltată ı̂n [37]: determinarea unui nou filtru pe baza combinării a mai multe filtre (concept ce provine, desigur, din combinarea prelucrărilor direcţionale şi orientate pe amplitudine pentru imagini color). O asemenea abordare se bazează pe folosirea a mai multe criterii de evaluare a ponderilor vectorilor din fereastra de filtrare ı̂n vectorul de ieşire a filtrului, fără ca nici unul dintre acestea să fie optimal, criterii ce sunt apoi combinate printr-un operator neliniar, derivat ı̂n mod esenţial din calculul ı̂n logică vagă (un agregator fuzzy). O clasă particulară de asemenea operatori sunt operatorii compensativi [56], definiţi ca medii ponderate ale unor operatori OR (∪) şi AND (∩) logic pentru mulţimile ce se combină: A γ B = (A ∩ B)1−γ (A ∪ B)γ (2.16) Folosind diferite forme pentru operaţiile logice vagi de bază (OR este o t-conormă, AND este o tnormă) şi considerând o forma clasică pentru operatorul de complementare (negaţia Lukasiewicz), se pot obţine diferite forme particulare ale operatorului de agregare. În [37] se propune folosirea ı̂n (2.16) a t-normei Zadeh (min) şi a t-normei probabiliste (de tip produs), ceea ce duce la obţinerea relaţiilor: wj = wj = min wji i=1,k k Y i=1 1−γ wji 1−γ 1− k Y max wji i=1,k γ , j = 1, ..., n !γ (1 − wji ) , j = 1, ..., n (2.17) (2.18) i=1 În (2.17) şi (2.18) k este numărul de filtre individuale ce se combină, iar wji este ponderea de ordinul j corespunzătoare filtrului i. Aplicaţiile prezentate ı̂n [37] folosesc combinarea cu ponderi egale (γ = 0.5) a două filtre (k = 2): un vector median VMF şi un vector median direcţional BVDF. În [51] a propus extinderea filtrului median scalar fuzzy introdus de [53] şi denumit AFMMF - Adaptive Fuzzy Multilevel Median Filter. Pentru acest filtru, procesul de prelucrare este descris de reguli de asociere vagă de tipul regulii lingvistice “dacă X este Ai , atunci Y este Bi ” (unde A şi B sunt mulţimi vagi definite peste universurile de obiecte X şi Y ). Filtrul din [53] provine din MMF - Multilevel Median Filter, definit pentru ferestre de filtrare de dimensiune impară, ı̂n care se formează grupuri de valori Wi conform principalelor direcţii (verticală, orizontală, diagonale). Pentru fiecare set de valori Wi , se calculează medianul zi = median(Wi ), iar toate aceste rezultate sunt combinate la ieşirea filtrului ca: y = median(min(zi ), max(zi ), f ) (2.19) Folosirea regulilor fuzzy aduce o ı̂mbunătăţire a performanţelor filtrului, eliminând sensibilitatea acestuia la zgomotul de “zgârieturi”, prin includerea ı̂n (2.19) a doi noi termeni, ce sunt definiţi de o credibilitate maximă. Credibilitatea unei valori este calculată după următorul set de reguli: • dacă diferenţa absolută dintre medianul zi şi celelalte puncte din Wi este foarte mare, atunci credibilitatea lui zi este mică • dacă diferenţa absolută dintre medianul zi şi celelalte puncte din Wi este foarte mică, atunci credibilitatea lui zi este mică 22 • dacă diferenţa absolută dintre medianul zi şi celelalte puncte din Wi este medie, atunci credibilitatea lui zi este mare În final, dacă medianele de credibilitate maximă sunt zc1 şi zc2 , expresia ieşirii filtrului AFMMF devine: y = median(min(zi ), max(zi ), f, zc1 , zc2 ) Extensia multicanal (vectorială) a acestui filtru se poate obţine foarte uşor, prin simpla ı̂nlocuire a sintagmei diferenţă absolută cu cuvântul distanţă. În [51], pentru filtrarea imaginilor color, am folosit distanţa euclidiană ı̂n spaţiul RGB. Funcţiile de credibilitate sunt funcţii des folosite ca funcţii de apartenenţă fuzzy: trapezoidală, parabolică, dreptunghiulară. După cum demonstrează exemplul precedent, extinderea structurilor de filtrare scalare la cazul multicanal este suficient de simplă dacă regulile după care se face prelucrarea sunt exprimate ı̂n mod independent de dimensiunea spaţiului din care fac parte obiectele la care se referă. Acesta este şi cazul filtrării de clustering [50] şi [49], care se poate consideră că provine din filtrele scalare de tip “trimmed median” [33]. Extinderea fuzzy a acestora se realizează prin simpla ı̂nlocuire a algoritmului de partiţionare net cu unul fuzzy. Folosirea tehnicilor de clustering fuzzy pentru filtrarea imaginilor color [50] produce rezultate sensibil mai bune decât cele obţinute prin folosirea algoritmilor “crisp”. Elementul esenţial ı̂n folosirea unei tehnici de partiţionare vagă este acela că prototipurile claselor sunt influenţate de toate valorile selectate de fereastra de filtrare. În acest fel, valorile ce se află ı̂n apropierea frontierelor claselor şi ar fi fost repartizate (ı̂n cazul algoritmului crisp) ı̂n mod arbitrar unei unice clase, vor contribui ı̂ntr-un mod semnificativ la prototipurile tutoror claselor. Dacă partiţionarea este realizată cu un grad mare de fuzzificare, separaţia dintre clase devine mai puţin clară şi prototipul clasei centrale este o aproximare mai bună a valorii originale. Unul dintre algoritmii cei mai folosiţi de clustering fuzzy este Fuzzy Isodata [4] (cunoscut şi ca algoritmul Dunn-Bezdek). Pentru setul de n vectori xi ce se doresc partiţionaţi ı̂n C clase (fiecare clasă caracterizată de centroidul µj ), se asociază setul de coeficienţi de apartenenţă uij , care exprimă gradul de apartenenţă al vectorului xi la clasa j. Aceşti coeficienţi de apartenenţă sunt numere pozitive subunitare ce respectă condiţia de normare C X uij = 1, i = 1, ..., n (2.20) j=1 Determinarea partiţiei ı̂nseamnă determinarea coeficienţilor de apartenenţă a vectorilor la clase, prin rezolvarea iterativă a sistemului de ecuaţii (m este gradul de fuzzificare a partiţiei): µj = n P um ij xi i=1 n P i=1 uij = , j = 1, ..., C 1 C X kxi − µj k m−1 k=1 kxi − µk k (2.21) um ij −1 , i = 1, ..., n, j = 1, ..., C (2.22) Dezavantajul esenţial al acestei tehnici de clustering fuzzy este creşterea dramatică a complexităţii de calcul: sunt necesare mult mai multe ı̂nmulţiri decât la variantele crisp, şi ı̂n plus apare şi necesitatea ridicărilor la putere. Mai mult, pentru un acelaşi set de vectori, un algoritm de partiţionare iterativă fuzzy necesită mai multe iteraţii decât algoritmul net din care provine. O posibilă cale de a micşora necesarul de calcule este de a utiliza algoritmi ierarhici şi nu iterativi. Algoritmii de clustering clasici (fie că provin dintr-o abordare de tip cuantizare vectorială [17], fie dintr-o abordare de tip recunoaşterea formelor [29]) sunt definiţi ca optimizând un criteriu de calitate 23 a partiţie de tip eroare pătratică medie minimă. Se pot deci folosi simultană mai multe criterii de optimalitate a unei partiţii (eroare pătratică medie minimă, compactitudine a claselor definită prin distanţe agregate inter-vectori, volum minim a claselor); complicarea evidentă a formei criteriului de optimizat (imposibil de rezolvat simbolic) a dus la considerarea de soluţii de optimizare prin tehnici “inteligente” (simulated annealing [1] sau algoritmi genetici). O altă abordare a filtrării de tip median prin metode de clustering fuzzy a fost propusă ca extindere a filtrului fuzzy median scalar [13]. În [13] se propunea construirea medianului unui set de scalari nu prin procedeul obişnuit de ordonare, ci printr-o combinaţie liniară a tuturor valorilor din fereastra de filtrare, ponderate cu coeficienţii lor de apartenenţă la clasa numită “median” (adică ieşirea filtrului este prototipul clasei ı̂n care au fost grupate valorile). Acest clustering cu o singură clasă se face printr-un procedeu iterativ analog celui folosit la metoda Fuzzy Isodata; ceea ce se schimbă este ecuaţia (2.22) de determinare a gradelor de apartenenţă, care devine (C = 1): µ= n P um i xi i=1 n P i=1 um i kxi − µk2 ui = exp − K ! Acest tip de filtrare de clustering poate fi asimilat (sau asemănat) mai multor modele de filtre: pe de o parte filtrele cu coeficienţi dependenţi de distanţă, de tipul DDMF [16], sau se poate considera că modelul de clustering urmează paradigma posibilistă, introdusă ı̂n [26], [25]. Modelul fuzzy posibilist se bazează pe modificarea interpretării gradului de apartenenţă. Pentru modelul probabilist (clasic), gradul de apartenenţă al fiecărui vector exprima gradul ı̂n care acesta este comun la mai multe clase şi se exprimă prin constrângerea (2.20) ca gradele de apartenenţă ale unui singur vector faţă de toate clasele să se comporte ca probabilităţile asociate unui câmp complet de evenimente. Dezavantajul acestei abordări este că, adeseori, vectori ce au acelaşi grad de apartenenţă faţă de două clase nu sunt reprezentativi ı̂n aceeaşi măsură pentru clasele respective. Ceea ce ne interesează ı̂n general este ı̂nsă tocmai reprezentativitatea vectorilor faţă de o clasă, deci cât de tipic este un vector pentru o clasă dată. Această interpretare este modelarea posibilistă [26] şi se bazează pe renunţarea la constrângerea (2.20) şi la adoptarea unei relaţii de calcul a gradelor de apartenenţă ı̂n funcţie de centroizii unei singure clase (şi nu de centroizii tuturor claselor). În [26], [25] s-a propus folosirea relaţiei de tip exponenţial, ponderată cu un scalar ηj variabil cu iteraţiile: uij = 1 + n P ηj = K i=1 kxi − µj k2 ηj ! 1 m−1 −1 2 um ij kxi − µj k n P i=1 , j = 1, ..., C um ij 24 Anexa A Probabilitatea de degradare a unui pixel Zgomotul impulsiv este unul dintre tipurile de zgomot cele mai utilizate pentru exemplificarea limitărilor filtrării liniare de netezire şi evaluarea performanţelor filtrelor neliniare (mai ales de tip median). Pentru o imagine scalară (cu nivele de gri) zgomotul impulsiv (sau de tip “sare şi piper”) se manifestă prin ı̂nlocuirea valorilor unor puncte din imagine (uniform distribuite) cu două valori extreme. Acesta ı̂nsemană că din imaginea originală f se obţine o imagine degradată fzg prin: fzg (m, n) = ( valmin , cuprobabilitatea pmin valmax , cuprobabilitatea pmax În mod uzual, pentru imaginile color, se consideră că zgomotul impulsiv afectează ı̂n mod independent fiecare componentă de culoare a imaginii; probabilităţile ca ı̂n fiecare plan de culoare un pixel să fie degradat sunt respectiv pR , pG şi pB (iar ı̂n cazul uzual aceste probabilităţi sunt egale pR = pG = pB = p). La nivelul imaginii color (deci pentru toate cele trei componente de culoare considerate simultan), probabilitatea ca un pixel să fie afectat de zgomot este ı̂nsă determinată de formula: P = p R + pG + p B − p R p G − p B p R − p G pB + pR pG p B . Pentru cazul ı̂n care pe toate planele de culoare există acelaşi zgomot, această formulă se simplifică la: P = 3p − 3p2 + p3 . Pentru probabilităţile de zgomot impulsiv folosite ı̂n testele prezentate ı̂n lucrare, probabilitatea echivalentă de degradare a unui pixel la nivelul ı̂ntregii imagini este prezentată ı̂n tabelul A. Procent de zgomot p% 1 5 10 15 25 Probabilitate de degradare a pixelilor P % 2.9701 14.2625 27.1 38.5875 57.8125 Tabel A.1: Probabilitatile de degradare a unui pixel al imaginii color, in functie de zgomotul impulsiv adaugat in mod independent fiecarui plan de culoare. 25 Bibliografie [1] E. Aarts şi J. Korst. Simulated Annealing and Boltzmann Machines (a stochastic approach to combinatorial optimization and neural compuring). J. Wiley and Sons, New York NY, 1989. [2] J. Astola, P. Haavisto, şi 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 Image Processing ICIP ‘95, vol. 1, pp. 175–178, Washington D.C., USA, 23-26 Oct. 1995. [7] A. Buchowicz şi I. Pitas. “Multichannel Distance Filters”. In Proc. of IEEE Conference on Image Processing 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 şi A. Montanvert. Geometrie discrete en Analyse d’images. Hermes, Paris, 1991. [10] M. Ciuc, R. M. Rangayyan, T. Zaharia, şi V. Buzuloiu. “Adaptive neighbourhood filters for color image filtering”. In Proc. of the SPIE Nonlinear Image Processing IX Conference, vol. 3304, pp. 277–286, 10-13 Jan. 1998. [11] J. P. Cocquerez şi 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 IEEE Conference on Image Processing ICIP ‘96, vol. 1, pp. 1005–1008, Lausanne, Switzerland, 16-19 Sept. 1996. [13] M. Doroochi şi A. M. Reza. “Fuzzy Cluster Filter”. In Proc. IEEE Conference on Image Processing ICIP ‘96, vol. 2, pp. 939–942, Lausanne, Switzerland, 16-19 Sept. 1996. [14] G. Economou şi S. Fotopoulos. “A Family of Adaptive Nonlinear Low Complexity Filters”. In Proc. ECCTD ‘93 - Circuit Theory and Design, pp. 521–524, Davos, Switzerland, Sept. 1993. [15] G. Economu, A. Ifantis, şi 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 şi G. Economou. “Multichannel Filters Using Composite Distance Metrics”. In Proc. of the IEEE Workshop on Nonlinear Signal and Image Processing, vol. 2, pp. 503–506, Neos Marmaras, Greece, Jun. 1995. [17] A. Gersho şi 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 şi 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 şi P. E. Trahanias. “Generalized Multichannel Image-Filtering Structures”. IEEE Trans. on Image Processing, 6(7):1038–1045, Jul. 1997. [21] V. Koivunen. “Nonlinear Filtering of Multivariate Images Under Robust Error Criterion”. IEEE Trans. on Image Processing, 5(6), Jun. 1996. [22] V. Koivunen, N. Himayat, şi S. A. Kassam. “Multivariate MTM Filters Analysis and Design Options”. 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 şi S. A. Kassam. “Nearest Neighbor Filters for Multivariate Data”. In Proc. of the IEEE Workshop on Nonlinear Signal and Image Processing, vol. 2, pp. 734–737, Neos Marmaras, Greece, Jun. 1995. [24] V. Koivunen şi 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, şi Nasraoui O. “Fuzzy and Possibilistic Shell Clustering Algorithm and Their Application to Boundary Detection and Surface Approximation - Part I”. IEEE Trans. on Fuzzy Systems, 3(1):29–43, Feb. 1995. [26] R. Krishnapuram şi J. M. Keller. “A Possibilistic Approach to Clustering”. IEEE Trans. on Fuzzy 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”. IEEE Trans. on PAMI, 2(2), Mar. 1980. [29] V. E. Neagoe şi O. Stănăşilă. Teoria Recunoaşterii formelor. Ed. Academiei Române, Bucureşti, 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, şi R. M. Rangayyan. “Image Restauration by adaptiveneighbourhood noise subtraction”. Applied Optics, 33(14):2861–2869, May 1994. [33] I. Pitas şi A. N. Venetsanopoulos. Nonlinear Digital Filters - Principles and Applications. Kluwer Academic Publ., Norwell MA, 1990. 27 [34] K. N. Plataniotis, D. Androutsos, şi A. N. Venetsanopoulos. “Multichannel Filtering for Color Image 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, şi A. N. Venetsanopoulos. “Nearest Neighbour Multichannel Filters 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, şi A. N. Venetsanopoulos. “Color Image Processing Using Adaptive Multichannel Filters”. IEEE Trans. on Image Processing, 6(7):933–949, Jul. 1997. [37] K. N. Plataniotis, D. Androutsos, şi A. N. Venetsanopoulos. “Multichannel Filters for Image Processing”. Signal Processing: Image Communications, 9(2):143–158, Jan. 1997. [38] K. N. Plataniotis, N. Androutsos, şi A. N. Venetsanopoulos. “Color Image Processing Using Fuzzy Vector Directional Filters”. In Proc. of the IEEE Workshop on Nonlinear Signal and Image Processing, vol. 2, pp. 535–538, Neos Marmaras, Greece, Jun. 1995. [39] R. M. Rangayyan, M. Ciuc, şi F. Faghih. “Adaptive-neighborhood filtering of images corrupted by signal dependent noise”. Applied Optics, 37(20):4477–4487, 1998. [40] C. S. Regazzoni şi A. Teschioni. “A New Approach to Vector Median Filtering Based on Space Filling Curves”. IEEE Trans. on Image Processing, 6(7):1025–1037, Jul. 1997. [41] B. Reusch. “Mathematics of Fuzzy Logic”. In H. J. Zimmermann, D. Dascălu, şi M. G. Negoiţă, editors, Real World Applications of Intelligent Technologies, pp. 15–52, Bucureşti, Romania, 1996. Romanian Academy Publ. House. [42] R. Sedgewick. Algorithms in C++. Addison Wesley, Reading, MA, 1992. [43] A. Spătaru. Teoria Transmisiunii Informaţiei. Ed. Didactică şi Pedagogică, Bucureşti, 1983. [44] K. Tang, J. Astola, şi Y. Neuvo. “Nonlinear Multivariate Image Filtering Techniques”. IEEE Trans. on Image Processing, 4(6):788–798, Jun. 1995. [45] P. E. Trahanias şi A. N. Venetsanopoulos. “Color Edge Detection Using Vector Statistics”. IEEE Trans. on Image Processing, 2(2):259–264, Apr. 1993. [46] P. E. Trahanias şi A. N. Venetsanopoulos. “Vector Directional Filters - A New Class of Multichannel Image Processing Filters”. IEEE Trans. on Image Processing, 2(4):528–534, Oct. 1993. [47] P. E. Trahanias şi A. N. Venetsanopoulos. “Vector Order Statistics Operators as Color Edge Detectors”. IEEE Trans. on Systems, Man and Cybernetics, B, 26(1):135–143, Feb. 1996. [48] C. Vertan. Prelucrarea şi Analiza Imaginilor. Ed. Printech, Bucureşti, 1999. [49] C. Vertan, V. Buzuloiu, M. Malciu, şi T. Zaharia. “Color Image Enhancement by Cluster Filtering”. In Buletinul Ştiinţific al Universităţii Politehnica Timişoara, vol. 41, pp. 210–213, Timişoara, Romania, 26-27 Sept. 1996. [50] C. Vertan şi C. Geangălă. “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, şi V. Buzuloiu. “Fuzzy Developments of Multichannel Filters”. In L. 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 şi P. S. Toh. “Adaptive Fuzzy Multilevel Median Filter”. IEEE Trans. on Image Processing, 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
Documentos relacionados
probleme manageriale ale reconstrucţiei întreprinderilor
cu o ruptură. Principiul rupturii tratat în raport cu reingineria poate, deci, părea, dacă nu simplist, puţin original. Cert. Dar aplicarea sa concretă nu este aşa de simplă, căci ea impune, pentru...
Leia maispictorii renaşterii - trateaza
GIOCONDA. Ce i-a dat putere pictorului care şi lăsat neterminate atâtea opere şi să lucreze continuu la acest tablou într-una din perioadele cele mai grele ale vieţii, într-o vreme când era copleşi...
Leia mais