Vidurinių reikšmių iškoštuvas

Medianos filtras (angl. Median Filter) – algoritmas, plačiai naudojamas , norint sumažinti triukšmą vaizduose ar duomenų signaluose.

Pavyzdys: trijų skirtingo lango dydžio medianos filtrų taikymas triukšmingai nuotraukai.

Svarbus algoritmo privalumas yra maža įtaka pačiam skaitmeniniam signalui, t. y. signalu perneštų duomenų baigtinei reikšmių aibei nedaroma įtaka – kas padeda išsaugoti kraštines taip perduotame vaizde. Atsikratoma tik kraštutinių, neįprastų, normaliam signalui nebūdingų reikšmių. Toks triukšmo sumažinimas yra įprastas, siekiant po to kaip galint geriau atlikti darbą, pvz., atvaizde surasti kraštines (angl. edge detection).

Veikimo principas

Algoritmo vykdymo metu peržiūrimas visas duomenų signalas, perrenkant iš eilės visus duomenis ir kiekvieną iš jų laikinai pakeičiant vidurine „kaimyninių duomenų“ reikšme. Kaip šie „kaimynai“ bus atrinkti, nusakoma taip vadinamu „langu“, kuris iš eilės pastumiamas nuo vieno duomens prie kito, kol peržiūrimas visas apdorojamas signalas. Vienmačiams signalams akivaizdžiu konkretaus duomens langu būtų keli prieš ir po jo einantys duomenys, tuo tarpu dvimačiams (ir esant daugiau matų) signalams, tokiems kaip vaizdai, gali būti žymiai sudėtingesni „dėžučių“ ar „kryžiukų“ pavidalo langai. Reiktų pastebėti, kad jeigu langui imamas kaimynų kartu su pačiu duomeniu nelyginis skaičius, tai visai nesunku surasti medianą, tereikia duomenis išrūšiuoti jų reikšmių didėjimo tvarka ir paimti vidurinio duomens reikšmę. Lyginio skaičiaus atveju gali būti daugiau nei viena vidurinė reikšmė.

Vienmačio atvejo išnagrinėjimas

Vidurinių reikšmių filtravimui paimkime langą su dviem kaimynais, kurių vienas eina iškart prieš, o kitas iš karto po konkretaus duomens. Pirminiu vienmačių duomenų signalu lai būna x = [2, 80, 6, 3].

Filtruodami x signalą gautume tokį y duomenų signalą, kurio

y[1] = vidurinReik[2, 2, 80] = 2; y[2] = vidurinReik[2, 80, 6] = vidurinReik[2, 6, 80] = 6; y[3] = vidurinReik[80, 6, 3] = vidurinReik[3, 6, 80] = 6; y[4] = vidurinReik[6, 3, 3] = vidurinReik[3, 3, 6] = 3; 

t. y. y = [2, 6, 6, 3].

Ribų klausimas

Ribiniais atvejais norint langui pateikti pakankamai duomenų, tiek pirmojo, tiek paskutiniojo duomens reikšmės imamos pakartotinai. Tai vienas iš būdų kaip, pasiekus ribą duomenų signale, pasiekti kad langui vis dar užtektų duomenų. Tačiau galima elgtis ir kitaip, kas susiklosčius tam tikroms aplinkybėms gali būti net pageidautina:

• Ribinių vietų iš viso neperžiūrėti su vėlesniu signalo ar atvaizdo ribų pašalinimu ar be pašalinimo.
• Pakišant reikšmes iš kitų duomenų signalo vietų, pavyzdžiui, atvaizdams imant duomenis iš tolimo gulsčio ar stačio krašto.
• Sumažinant patį langą šalia ribų taip, kad jam užtektų duomenų.

Dvimačio atvejo apdorojimo programa

Paprasto dvimačio medianos filtro programa galėtų atrodyti taip:

 Išskirti atminties dvimačiui masyvui apdirbtasSrautas[atvaizdo plotis][atvaizdo aukštis] Išskirti atminties vienmačiui masyvui langas[lango plotis * lango aukštis] xKrastas := (lango plotis / 2) suapvalinus mažėjimo kryptimi yKrastas := (lango aukštis / 2) suapvalinus mažėjimo kryptimi // Peržiūrėsime visus duomenis, kuriems užteks duomenų langui for x from xKrastas to (atvaizdo plotis – xKrastas) for y from yKrastas to (atvaizdo aukštis – yKrastas) { //konkrečiam duomeniui užpildom langą i := 0 for fx from 0 to lango plotis for fy from 0 to lango aukštis { langas[i] := pirminisSrautas[x + fx – xKrastas][y + fy – yKrastas] i := i + 1 } surūšiuoti vienmatį masyvą langas[] apdirbtasSrautas[x][y] := langas[lango plotis * lango ilgis / 2] }

Pastabos:

• vienu metu filtruojamas tik vienos spalvos kanalas (įprastai būna trys – raudona, mėlyna ir žalia).
• praleidžiamos ribinės vietos, kurioms trūksta duomenų lango užpildymui.

Medianos filtro panaudojimas stipriai apgadinto vaizdo atstatymui.

Dvimatis medianos filtras

Kaip paprastai, daugiausiai pastangų ir laiko užima kiekvieno lango vidurinės reikšmės ieškojimas. Kadangi filtrui reikia peržiūrėti langus daugumai signalo duomenų, dideliems signalams, tokiems kaip atvaizdai, vidurinės reikšmės ieškojimo veiksmingumas labai svarbus rodiklis, nusakantis, kaip ilgai bus atliekamas darbas. Paprastas, anksčiau aprašytas įgyvendinimas kiekvienam langui surūšiuoja visus duomenis, kad būtų galima atrasti jame vidurinę reikšmę. Tačiau kai reikia tik vidurinės reikšmės iš visų likusių, galima pasinaudoti daug veiksmingesniais jos išrinkimo būdais.

Kai kuriuose duomenų signaluose reikšmė visada yra sveikasis skaičis (dažna atvaizdams). Tokiais atvejais histogramų vidurinių reikšmių ieškojimas gali būti žymiai greitesnis, nes labai paprasta atnaujinti pereinant tarp gretimų langų, o vidurinės reikšmės išrinkimui histogramoje daug pastangų nereikia.

Kraštinių išsaugojimas

Medianos filtras yra vienas iš glodinimo būdų, tokių kaip Gausinis suliejimas (angl. Gaussian blur). Visi išlyginimo būdai veiksmingi šalinant triukšmą iš signalo jo tolygiuose ploteliuose ar dalyse, tačiau skirtingai paveikia kraštines. Labai dažnai mažinant triukšmą duomenų signale, tuo pat metu labai svarbu yra išsaugoti kraštines. Pavyzdžiui, kraštinės labai svarbios tam, kaip atvaizdas atrodys žvelgiant žmogaus akimis. Kai (Gausinio) triukšmo lygis yra nedidelis ar nuosaikus, šalinant triukšmą bei išsaugant kraštus su nekintamo dydžio langu, akivaizdžiai tinkamesnis už Gausinį suliejimą yra medianos filtras. Tačiau kai (Gausinio) triukšmo lygis aukštas, medianos filtras ne toks jau geras palyginus su Gausiniu suliejimu. Tuo tarpu medianos filtras ypatingai veiksmingas taškiniam triukšmui (angl. speckle noise) bei druskiniam ir pipiriniam (didelių trumpų pokyčių) triukšmui (angl. salt and pepper noise). Todėl medianos filtras plačiai naudojamas skaitmeninėje vaizdų analizėje.

Šaltiniai

1. T. Huang, G. Yang, and G. Tang, „A fast two-dimensional median filtering algorithm“, IEEE Trans. Acoust., Speech, Signal Processing, vol. 27, no. 1, pp. 13–18, 1979.
2. E. Arias-Castro and D.L. Donoho, "Does median filtering truly preserve edges better than linear filtering? ", Annals of Statistics, vol. 37, no. 3, pp. 1172–2009.
3. G.R. Arce, „Nonlinear Signal Processing: A Statistical Approach“, Wiley:New Jersey, USA, 2005.

Nuorodos

• Fast Matlab 1D median filter implementation
• Mathematica MedianFilter function
• Median filter 2016-03-03 iš Wayback Machine projekto.
• Fast 2D median filter
• Fastest possible 2D implementation (GPL license)
• Implementation written in different programming languages (on Rosetta Code)
• Dr Dobbs article