2015MichalVotı´pka Aplikacewaveletove´transformacevdigita´lnı´mzpracovańıóbrazuTheApplicationoftheWaveletTransforminDigitalImageProcessing VSˇB–TechnickaúniverzitaOstravaFakultaelektrotechnikyainformatikyKatedraaplikovane´matematiky

(1)

Fakulta elektrotechniky a informatiky Katedra aplikovane´ matematiky

Aplikace waveletove´ transformace v digita´lnı´m zpracova´nı´ obrazu

The Application of the Wavelet Transform in Digital Image

Processing

2015 Michal Votı´pka

(2)

(3)

(4)

(5)

(6)

Tato praće se zaby´va´ ru˚zny´mi aplikacemi waveletove´ transformace v oblasti digita´lnı´ho zpracovańı´ obrazu. Waveletovska´ reprezentace signa´lu je novou technikou, ktera´ v mnoha oblastech nahradila Fourierovu transformaci. Postupneˇ je veˇnovańa technika´m odstranˇo- vańı´ obrazove´ho sˇumu, u´praveˇ kontrastu - zejmeńa u medicıńskyćh snı´mku˚, detekci hran, ktera´ je za´kladem pro rozpozna´vańı´ vzoru˚ v obraze a take´ kompresi obrazu. Jednotlive´

aplikace byly implementovańy s ru˚zny´mi wavelety v programu MATLAB. Wavelety jsou mezi sebou navza´jem porovnańy, nebot’vy´beˇr waveletove´ ba´ze velmi ovlivnˇuje vy´sledek zpracovańı´ obrazu.

Klıćˇova´ slova: wavelety, waveletova´ transformace, odsˇumovańı´ obrazu, komprese obrazu, u´prava kontrastu, rozpozna´vańı´ vzoru˚, detekce hran, medicıńske´ snı´mky.

Abstract

This thesis deals with different applications of wavelet transform in digital image processing. Wavelet representation of the signal is a new technique which replaced the Fourier transform in many areas. We focused on techniques of image denoising, image enhancement - especially for medical images. Further we apply wavelet transform to edge detection which is the base for pattern recognition in image and also to image compression. Individual applications were implemented with different wavelets in MATLAB.

Wavelets are compared each other because the selection of wavelet basis greatly affects the result of image processing.

Keywords: wavelets, wavelet transform, image denoising, image compression, image enhancement, pattern recognition, edge detection, medical images.

(7)

Z – mnozˇina cely´ch cˇı´sel

R – mnozˇina rea´lny´ch cˇı´sel

L²(Rⁿ) – L²(Rⁿ) =



f :Rⁿ→R,

Rⁿ|f(x)|²dx <+∞ MRA – multiu´rovnˇova´ analy´za (multirozklad)

WT – waveletova´ transformace

CWT – spojita´ waveletova´ transformace DWT – diskre´tnı´ waveletova´ transformace

IDWT – zpeˇtna´ diskre´tnı´ waveletova´ transformace

LLn – diagona´lnı´ aproximacˇnı´ koeficienty nan-te´ u´rovni HLn – vertika´lnı´ detailnı´ koeficienty nan-te´ u´rovni HHn – diagona´lnı´ detailnı´ koeficienty nan-te´ u´rovni LHn – horizonta´lnı´ detailnı´ koeficienty nan-te´ u´rovni PSNR – sˇpicˇkovy´ odstup signa´l/sˇum

(8)

Obsah

1 U´ vod 4

2 Historie a vznik waveletu˚ 6

3 Waveletova´ transformace 8

3.1 Spojita´ waveletova´ transformace - CWT . . . 8

3.2 Diskre´tnı´ waveletova´ transformace - DWT . . . 11

3.3 Prˇehled waveletu˚ . . . 15

3.4 Vy´beˇr waveletu . . . 20

4 Metrika k urcˇova´nı´ kvality obrazu 22 4.1 Peak Signal to Noise Ratio (PSNR) . . . 22

5 Aplikace waveletove´ transformace 23 5.1 Odstranˇova´nı´ obrazove´ho sˇumu . . . 23

5.2 Komprese obrazu . . . 31

5.3 U´ prava kontrastu . . . 42

5.4 Rozpozna´va´nı´ vzoru˚ . . . 49

6 Za´veˇr 57

7 Literatura 59

(9)

Seznam obra´zku ˚

1 Dekompozice signa´lu pomocı´ banky filtru˚ (prˇevzato z [32]) . . . 12

2 Sche´ma DWT pro 2D obraz s dveˇma stupni dekompozice (prˇevzato z [34]) 14 3 Haaru˚v wavelet . . . 15

4 Wavelet Daubechies 4 . . . 16

7 Wavelet Cohen-Daubechies-Feauveau 9/7 (Biorthogonal 4.4) . . . 18

8 Wavelet Coiflet 2 . . . 18

9 Wavelet Symlet 6 . . . 19

10 Komplexnı´ wavelet SCD-6 . . . 20

11 Blokove´ sche´ma principu odsˇumovańı´ s vyuzˇitı´m waveletovy transformace 23 12 Rozdı´l mezi meˇkky´m (vlevo) a tvrdy´m (vpravo) prahovańı´m po cˇtyrˇech (nahorˇe) a sˇesti (dole) stupnıćh dekompozice . . . 27

13 Porovna´nı´ neˇkolika stupnˇu˚ dekompozice s Haarovou vlnkou . . . 28

14 Porovna´nı´ jednotlivy´ch metod s ru˚zny´mi druhy vlnek . . . 29

15 Porovna´nı´ metody pro odstranˇova´nı´ sˇumu pomocı´ SVD rozkladu matice paketove´ho rozkladu . . . 30

16 Vynulovane´ HH1 a LH1 koeficienty s vyuzˇitı´m Daubechies 16 vlnkou, PSNR =87,4449dB . . . 31

17 Porovnańı´ obrazu˚ po vynulovańı´ jednotlivyćh stupnˇu˚ dekompozice pro ru˚zne´ typy vlnek . . . 32

18 Sekvence kroku˚ prˇi typicke´ kompresi obrazu s vyuzˇitı´m waveletove´ transformace . . . 33

19 Proces JPEG komprese (prˇevzato z [20]) . . . 34

20 Sche´ma prˇi JPEG 2000 kompresi (prˇevzato z [12]) . . . 36

21 Porovna´nı´ zkomprimovane´ho obrazu pomocı´ JPEG 2000 a JPEG standardu 38 22 Stromova´ reprezentace obrazu pro EZW ko´dova´nı´ (prˇevzato z [17]) . . . . 40

23 Pru˚chod obrazem pomocı´ rastrove´ho skenu a Mortonova rozkladu (prˇe- vzato z [17]) . . . 41

24 Uka´zka u´pravy kontrastu pomocı´ nelinea´rnı´ modifikace a ekvalizace histogramu . . . 42

25 U´ prava kontrastu pomocı´ (21) s vlnkou Daubechies 8 . . . 44

28 Vliv stupneˇ dekompozice na zmeˇnu kontrastu, 3. typ modifikace, vlnka Daubechies 16 . . . 46

29 Pu˚vodnı´ plochy´ snı´mek hrudnı´ho kosˇe urcˇeny´ k na´sledne´ u´praveˇ kontrastu 46 30 U´ prava kontrastu pomocı´ trˇech prˇedstavenyćh modifikacı´ v porovnańı´ s vlnkami . . . 47 31 U´ prava kontrastu pomocı´ trˇech prˇedstavenyćh modifikacı´ s obra´zkem Lenny 48

(10)

32 a) pu˚vodnı´ obraz. b) - e) obraz Msf(x, y) pro s = 2^j,1 ≤ j ≤ 4. Cˇerne´

pixely indikujı´ nulove´ hodnoty a bı´le´ pixely korespondujı´ s nejvysˇsˇı´mi hodnotami. f) - i) obrazA_sf(x, y) pros = 2^j,1 ≤ j ≤4 Hodnoty u´hlu˚ v rozmezı´ od 0 (cˇerna´) po2π(bı´la´). j)- m)Vy´sledny´ obraz s detekovany´mi hranami (cˇerneˇ). Obra´zky byly prˇevzaty z [30] . . . 52 33 Detekce hran pomocı´ dvou ru˚zny´ch technik . . . 54 34 Porovna´nı´ detekce hran s Cannyho detektorem. a)Cannyho detektor apli-

kovany´ na cely´ obraz. b)Odsˇumeˇny´ obraz a na´sledny´ Cannyho detektor na cely´ obraz. c)Technika cˇ. 2 s vyuzˇitı´m waveletove´ transformace prˇi detekci 54 35 Porovna´nı´ dvou technik pro detekci hran s ru˚zny´mi vlnkami . . . 56

(11)

1 U ´ vod

Digita´lnı´ zpracova´nı´ obrazu ma´ v dnesˇnı´ dobeˇ velky´ vy´znam. Prakticky kazˇdy´ signa´l (obraz) je nutno zpracovat, aby mohl by´t da´le vyuzˇit. Vstupem pro digita´lnı´ zpracova´nı´

mohou by´t data ru˚zne´ho pu˚vodu, naprˇ. obrazova´ data z digita´lnı´ho fotoapara´tu, rentgenove´ cˇi ultrazvukove´ snı´mky vygenerovane´ le´karˇsky´m zarˇı´zenı´m nebo satelitnı´ snı´mky z druzˇice. Veˇtsˇinou tyto obrazy trpı´ neˇjakou vadou, kterou je nutno eliminovat.

V pra´ci se veˇnujeme modernı´ technice, ktera´ je zna´ma´ jen neˇkolik ma´lo let. Rˇecˇ je o waveletove´ transformaci, ktera´ nacha´zı´ uplatneˇnı´ v sˇiroke´ sˇka´le digita´lnı´ho zpracova´nı´ obrazu.

Zameˇrˇujeme se na nejzna´meˇjsˇı´ aplikace pro obrazova´ data, konkre´tneˇ na odstranˇova´nı´

obrazove´ho sˇumu, u´pravu kontrastu, detekci hran a kompresi obrazu. Mnohdy pra´ce obsahuje i porovna´nı´ waveletovske´ metody s beˇzˇneˇ zna´mou technikou pro danou aplikaci.

Vy´sledek procesu s waveletovou transformacı´ velmi za´visı´ na pouzˇite´ ba´zi (waveletu), ktera´ ovlivnı´ kvalitu vy´sledku dane´ aplikace. Na konci kapitoly, kazˇde´ aplikace, je porovna´nı´ mezi jednotlivy´mi wavelety.

Uved’me strucˇneˇ pru˚let pracı´. V kapitole 2 najdeme informace o historii waveletove´ transformace, kam azˇ sahajı´ jejı´ korˇeny a jak se postupneˇ formovala do podoby, v jake´ je dnes.

Kapitola 3 obsahuje teoreticke´ informace o waveletove´ transformaci vcˇetneˇ prˇehledu waveletu˚ a jejich vlastnostı´. V kapitole 4 je kra´tce prˇedstavena metrika PSNR, pouzˇı´vana´

k porovnańı´ kvality obrazu. Hlavnı´ cˇa´st praće je obsazˇena v kapitole 5. V jednotlivyćh podkapitolaćh nalezneme postupneˇ jizˇ zmıńeˇne´ aplikace. Podkapitola 5.1 se veˇnuje od- stranˇovańı´ obrazove´ho sˇumu. Zameˇrˇili jsme se na prahovacı´ metody VisuShrink, Sure- Shrink, BayesShrink a jednu netypickou metodu s vyuzˇitı´m SVD rozkladu. Na´sledovala podkapitola 5.2, ktera´ se veˇnovala aplikaci WT v kompresi obrazu. Waveletova´ transformace je hlavnı´ na´stroj v kompresnı´m forma´tu JPEG 2000. Jejı´ implementace by vsˇak byla nad ra´mec te´to praće, proto se standardu JPEG 2000 veˇnujeme teoreticky. Porovnali jsme vy´hody i nevy´hody se zna´my´m standardem JPEG. Take´ jsme uka´zali, jak se zmeˇnı´

kvalita rekonstruovane´ho obrazu, pokud neˇktere´ dekompozice zcela vynulujeme a tı´m obraz de facto komprimujeme. Dalsˇı´ zajı´mavou aplikacı´ je u´prava kontrastu (podkapitola 5.3). Le´karˇske´ prˇı´stroje generujı´ obraz poneˇkud nevy´razny´, teˇzˇce se v neˇm orientuje a stanovenı´ diagno´zy pacienta je obtı´zˇne´. Proto je nutne´ takovy´ obraz zpracovat a vyle- psˇit. Zameˇrˇujeme se na techniky nelinea´rnı´ modifikace waveletovsky´ch koefientu˚, ktere´

poskytujı´ velke´ vy´hody v porovna´nı´ s tradicˇnı´ ekvalizacı´ histogramu. Vyzkousˇeli jsme trˇi ru˚zne´ modifikace a vy´sledky otestovali na mamograficke´m a rentgenove´m snı´mku.

Poslednı´ aplikacı´, kterou najdeme v podkapitole 5.4, byla detekce hran, ktera´ hraje velkou roli v oblasti rozpozna´va´nı´ vzoru˚ v obraze. Uka´zali jsme opeˇt tradicˇnı´ metodu Cannyho detektor, ktery´ je silny´m na´strojem pro detekci hran v obraze. Na´sledneˇ jsme zkombino- vali zna´me´ metody pro detekci hran a s vyuzˇitı´m waveletove´ transformace a prahovacı´

metody VisuShrink uka´zali dveˇ hybridnı´ techniky prˇi detekci hran. Detekci hran jsme prova´deˇli stejneˇ jako u ostatnı´ch aplikacı´ na obra´zku Lenny, ale take´ pro obraz s diago-

(12)

na´lnı´mi, vertika´lnı´mi a horizonta´lnı´mi vzory spolecˇneˇ s textem v jednom. To abychom pokryli co nejvı´ce mozˇny´ch vzoru˚.

Du˚lezˇitou soucˇa´stı´ te´to pra´ce byla take´ implementace teˇchto aplikacı´ waveletove´ transformace v programu MATLAB, tedy i samotna´ diskre´tnı´ waveletova´ transformace. Na prˇi- lozˇene´m CD lze najı´t vesˇkere´ zdrojove´ ko´dy pouzˇite´ v pra´ci.

(13)

2 Historie a vznik waveletu ˚

Teorie waveletu˚ (vlnek) se zacˇala rapidneˇ rozvı´jet azˇ v osmdesa´ty´ch letech 20. stoletı´.

Tento silny´ na´stroj k rˇesˇenı´ mnoha nejen matematickyćh proble´mu˚ vycha´zel z neza´vislyćh pracı´ mnoha veˇdcu˚, na kteryćh, anizˇ by to navza´jem tusˇili, te´meˇrˇ cele´ stoletı´ pracovali.

Tato teorie byla vy´znamneˇ sva´zańa s teoriı´ signa´lu˚, v dnesˇnı´ dobeˇ vsˇak rˇadı´me wavelety mezi matematiku, teorii signa´lu˚ a zpracovańı´ obrazu a zvuku. Teorie se neusta´le zobecnˇuje a prohlubuje, proto dnes nacha´zı´ uplatneˇnı´ v cele´ rˇadeˇ veˇdnıćh oboru˚. Podrob- neˇjsˇı´ informace lze najı´t v [2].

Nynı´ neˇco ma´lo k historii teorie waveletu˚. Podı´va´me-li se zpeˇt do historie matematiky, najdeme hned neˇkolik ru˚zny´ch zdroju˚ waveletove´ analy´zy. Nejveˇtsˇı´ cˇa´st te´to teorie vznikala ve trˇica´ty´ch letech 20. stoletı´. V te´ dobeˇ se jesˇteˇ netusˇilo, zˇe by spolu tehdejsˇı´ vy´sledky vy´- zkumu neˇjaky´m zpu˚sobem souvisely. Nezna´me´ bylo i slovo wavelet, i celkova´ koncepce soucˇasne´ teorii waveletu˚. Prvnı´ mysˇlenku vu˚bec, ktera´ se stala nejdu˚lezˇiteˇjsˇı´m podneˇtem pro vznik waveletove´ teorie, prˇinesl jizˇ v roce 1807 Joseph Fourier se svy´mi zna´my´mi Fourierovy´mi rˇadami.

Ale jizˇ v roce 1873 Paul Du Bois-Reymond zkonstruoval spojitou2π-periodickou rea´lnou funkci, jejı´zˇ Fourierova rˇada v dane´m bodeˇ diverguje. Proto se zacˇalo zkoumat, jak by bylo mozˇne´ Fourierovy rˇady vylepsˇit. A pra´veˇ jednou mozˇnostı´ tehdy bylo nale´zt jiny´

ortonorma´lnı´ syste´m funkcı´.

Touto cestou se vydal k objevu Alfred Haar, ktery´ v roce 1909 ve sve´ disertacˇnı´ pra´ci

”K teorii ortogona´lnıćh syste´mu˚ funkcı´,” nalezl jiny´ mozˇny´ ortonorma´lnı´ syste´m. Jeho vy´zkum vedl k vy´voji mnozˇiny obde´lnı´kovyćh ba´zovyćh funkcı´. Pozdeˇji cele´ rodiny waveletu˚. Haaru˚v wavelet byl pojmenovań na za´kladeˇ te´to mnozˇiny funkcı´ a byl take´

nejjednodusˇsˇı´m waveletem sve´ doby. Haarovy ba´zove´ funkce se skla´daly z kra´tke´ho kladne´ho pulsu na´sledova´ny kra´tky´m za´porny´m pulsem [1].

V jeho objevu byla poprve´ prˇedstavena dalsˇı´ za´kladnı´ mysˇlenka waveletove´ teorie: po- pisovat prostory funkcı´ pomocı´ celocˇı´selny´ch translacı´ a dyadicky´ch dilatacı´ jedne´ jedine´

funkce.

Ve trˇica´tyćh letech pokrocˇil vy´zkum o velky´ kus vprˇed. Vy´znamny´ fyzik te´ doby, Paul Le´vy, se snazˇil zkoumat neˇktere´ vlastnosti Brownova pohybu. Zjistil, zˇe pro reprezentaci neˇkteryćh komplikovanyćh detailu˚ je Fourieru˚v trigonometricky´ syste´m nepouzˇitelny´.

Kdyzˇ zkousˇel uplatnit reprezentaci pomocı´ Haarovy ba´ze, uka´zalo se, zˇe vy´pocˇty jsou daleko prˇesneˇjsˇı´, a zˇe takto lze zı´skat korektnı´ vy´sledky. Toto uplatneˇnı´ Haarova syste´mu se da´ povazˇovat za prvnı´ vy´znamne´ vyuzˇitı´ waveletove´ ba´ze v praxi.

Pojem wavelet se poprve´ objevil v pra´ci fyzika A. Grossmanna a inzˇeny´ra J. Morleta z roku 1980. Zajı´mali se prˇedevsˇı´m o kvantovou fyziku, zavedli v tomto kontextu prvnı´

ucelenou waveletovou teorii a uka´zali souvislost waveletu˚ s fyzika´lnı´ praxı´. Vycha´zeli prˇitom z vy´sledku˚ matematika A. Calderońa z sˇedesa´tyćh let. Zdu˚razneˇme, zˇe mezi vsˇemi teˇmito veˇdci tehdy neexistoval te´meˇrˇ zˇa´dny´ kontakt, a proto vsˇechny vy´sledky vy´zkumu, i kdyzˇ velmi podobne´, byly objeveny neza´visle na sobeˇ veˇdci z ru˚znyćh zemı´ a prˇedevsˇı´m ru˚znyćh veˇdnıćh oboru˚.

(14)

V osmdesa´ty´ch letech prˇisˇel S. Mallat s aplikacı´ prˇi digita´lnı´m zpracova´nı´ signa´lu˚.

Nejdu˚lezˇiteˇjsˇı´m krokem, ktery´ vedl k prosperiteˇ waveletu˚, bylo vymysˇlenı´ multiroz- kladove´ analy´zy (multirozkladu) spolecˇneˇ s Y. Meyerem. Multirozklad umozˇnˇoval na´vrh sˇka´lovacı´ch funkcı´, ktere´ dovolovaly ostatnı´m vy´zkumnı´ku˚m konstruovat vlastnı´ ba´zove´

wavelety. Naprˇı´klad Ingrid Daubechies kolem roku 1988 vytvorˇila vlastnı´ rodinu waveletu˚, zvane´ Daubechies wavelety na za´kladeˇ teorie multirozkladu.

Wavelety se zacˇala zaby´vat cela´ rˇada odbornı´ku˚ z matematicke´ho i fyzika´lnı´ho hlediska, a protozˇe komunikace jizˇ byla snadneˇjsˇı´, byla tak postupem cˇasu vytvorˇena jednotna´

teorie waveletu˚, usta´lena definice pojmu wavelet a take´ odvozeny vesˇkere´ jeho za´kladnı´

vlastnosti. Soubeˇzˇneˇ se objevovaly nove´ prˇı´klady waveletu˚ vycha´zejı´cı´ z ru˚zny´ch typu˚

funkcı´.

Jmenoviteˇ mezi nejvy´znamneˇjsˇı´ pru˚kopnı´ky, kterˇı´ se vy´znamny´m zpu˚sobem zaslouzˇili o vznik a rozvoj te´to teorie, patrˇı´: R. Coifman, J. O. Stro¨mberg, S. Mallat, Y. Meyer, I.

Daubechies, G. Beylkin, P. Wojtaszczyk a mnoho dalsˇı´ch.

(15)

3 Waveletova´ transformace

Co je to wavelet? Pokud slysˇı´me slovo wavelet (v cˇesˇtineˇ vlnka), myslı´ se tı´m ba´ze, prˇesneˇji ortonorma´lnı´ ba´ze. Ta je tvorˇena funkcı´, materˇsky´m waveletemψ, z neˇjake´ trˇı´dy funkcı´, naprˇı´kladL²(R). Snahou je vygenerovat neˇjakou ba´zi pomocı´ dilatace a translace materˇske´ho waveletuψ. Wavelety jsou funkce definovane´ jako [33]

ψa,b(t) = 1

|a| ψ

t−b a



, kdea, b∈R, a̸= 0. (1) Chceme-li popsat, jak je waveletova´ transformace definova´na, budeme potrˇebovat slozˇi- teˇjsˇı´ matematicky´ apara´t, jehozˇ za´kladem je tzv. vı´ceu´rovnˇova´ analy´za (angl. multireso- lution analysis - MRA) [3].

MRA, ktera´ byla vyvinuta v poslednı´ch letech, meˇla prˇı´znivy´ dopad na pole zpracova´nı´

obrazu. Jde o techniku ke zkoumańı´ signa´lu˚ ve sˇka´love´ domeńeˇ, podobneˇ jako Fourierova transformace zkouma´ signa´ly ve frekvencˇnı´ domeńeˇ. Vy´znamny´m vy´sledkem studie MRA je spocˇetna´ mnozˇina waveletu˚, ktera´ doka´zˇe vytvorˇit ortonorma´lnı´ ba´zi proL²(R) [33]. Pro na´sledujıćı´ text jsme vyuzˇili [3].

Definice.MultirozklademL²(Rⁿ)(vı´ceu´rovnˇovou analy´zou) budeme nazy´vat neklesajı´cı´

posloupnost uzavrˇeny´ch sˇka´lovacı´ch podprostoru˚ Vm ∈ L²(Rⁿ), m ∈ Z pro neˇzˇ platı´

na´sledujı´cı´ podmı´nky:

1.· · · ⊂V−2⊂V−1 ⊂V0 ⊂V1⊂V2 ⊂ · · ·, tj.Vm ⊂Vm+1, ∀m∈Z.

2.

m∈ZVm={0}. 3.

m∈ZVmje husty´ a prˇedstavujeL²(Rⁿ), tj.

m∈ZVm =L²(Rⁿ).

4.f(t)∈Vm ⇔f(2t)∈Vm+1, t∈Rⁿ.

5. Existuje funkceφ∈V₀takova´, zˇe{φ(t−n)}_n∈

Zje ortonorma´lnı´ ba´zı´V₀. Funkceφ∈V₀ se nazy´va´ sˇka´lovacı´ funkce, resp. otcovsky´ wavelet.

3.1 Spojita´ waveletova´ transformace - CWT

Definice.Necht’f(t), ψ(t)∈L²(R). Spojitou waveletovou transformaci funkcef(t)defi- nujeme

W T(f) =F(a, b) = ˆf(a, b) = 1

|a|

+∞



−∞

f(t)ψ

t−b a



dt, (2)

kdea ∈ R\ {0}je tzv. dilatacˇnı´ sˇka´lovy´ parametr, b ∈ Rje translacˇnı´ parametr,ψ(t) je materˇsky´ wavelet nebo jen obecneˇ wavelet splnˇujı´cı´ podmı´nku

+∞



−∞

ψ(t)dt= 0.

Zpeˇtna´ (inverznı´) spojita´ waveletova´ transformace je da´na prˇedpisem

(16)

W T⁻¹(F) =f(t) =

+∞



−∞





+∞



−∞

F(a, b) 1

|a| ψ

t−b a

 da



db. (3) Obraz F je tedy definova´n jako skala´rnı´ soucˇin analyzovane´ funkce f s translacemi a dilatacemiψ, cˇili [3]

F(a, b) =



f(t), 1

|a| ψ

t−b a



. (4)

Waveletova´ transformace vyuzˇı´va´ neˇjaky´ druh okna k filtraci signa´lu. Pomocı´ parametru ase prova´dı´ zmeˇna meˇrˇı´tka, parametrbprˇedstavuje posouva´nı´ okna v meˇrˇı´tkuapo cˇa- sove´ ose. Zatı´mco Fourierova transformace vyuzˇı´va´ konstantnı´ velikost okna, waveletova´

transformace meˇnı´ velikost okna pro lepsˇı´ zachycenı´ frekvencı´ [32].

3.1.1 Vlastnosti spojite´ waveletove´ transformace

Waveletovske´ koeficienty, cˇili koeficienty zı´skane´ po waveletove´ transformaci obsahujı´ informace o pouzˇite´m waveletu, ale take´ o analyzovane´ funkci. Necht’W T(f(t)) =F(a, b), pak na´sledujı´cı´ vlastnosti nejsou za´visle´ na pouzˇite´m typu waveletu [3]:

1. linearita:W T(αf1+βf2) =αW T(f1) +βW T(f2) =αF1(a, b) +βF2(a, b), 2. invariance vzhledem k posunutı´:W T(f(t−b0)) =F(a, b−b0),

3. invariance vzhledem k dilataci:W T

 f

t a0



= _a¹

0F

a a0,_a^b

0

 , 4. derivova´nı´ origina´lu:W T _∂^m

∂t^mf

= (−1)^m

+∞



−∞

f(t)_∂t^∂^mm

ψ_a,b(t) dt, 5. v prˇı´padeˇ ortogona´lnı´ waveletovske´ ba´ze (analogie Parsevalovy veˇty):

+∞



−∞

f1(t)f₂(t)dt=C_ψ⁻¹

+∞



−∞

+∞



−∞

F1(a, b)F2(a, b)a⁻²da db ⇒

energie signa´lu

+∞



−∞

|f(t)|² dt=C_ψ⁻¹

+∞



−∞

+∞



−∞

|F(a, b)|²a⁻² da db.

(17)

3.1.2 Konstrukce ortonorma´lnı´ch waveletu˚

Vycha´zeli jsme z [3]. Necht’P_m znacˇı´ ortogona´lnı´ projekci f do V_m a D₂^m je dilatacˇnı´

opera´tor, tj.f(.) ∈D2^mVn ⇔f(2^m.)∈Vm+n. S rostoucı´mmpakPmf le´pe aproximujef, tedy

m→∞lim Pmf =f.

ProstorVmje tvorˇen sˇka´lovy´mi funkcemi{φ_mn}_∀n,∀m∈Z.

Nebot’dle definice MRA, je prostorV_mobsazˇen take´ v prostoruV_m+1, definujmeW_mjako m-ty´ waveletovy´ prostor, ktery´ obsahuje waveletove´ funkce {φ_mn}_∀n,∀m ∈ Ztak, aby byl ortogona´lnı´m doplnˇkemVmdoVm+1, tj.

V_m+1=V_m⊕W_m,

da´le Q_m je projekcˇnı´ opera´tor do W_m - sˇka´lovane´ verze W₀, kde f(.) ∈ W_m ⇔ f(2^−m.)∈ W0. Podobneˇ jeWmtvorˇen waveletovy´mi funkcemi{φ_mn}_∀n,∀m∈Z. Pak

P_m+1 =P_m⊕Q_m je projekcˇnı´ opera´tor doV_m+1.

Jak jizˇ bylo zmı´neˇno, MRA umozˇnˇuje sestavit ortonorma´lnı´ waveletovskou ba´zi {ψ_mn(t)}_∀n,∀m∈Z, kdeψmn(t) = 2⁻^m²ψ(2^−mt−n), m, n∈Ztak, zˇe pro kazˇdou funkci f(t)∈L²(R)platı´:

Pm+1f =Pmf +Qmf =

=

n∈Z

amnφmn+

n∈Z

dmnψmn=

n∈Z

⟨P_mf, φmn⟩φmn+

n∈Z

⟨Q_mf, ψmn⟩ψmn. Koeficientya_mnse nazy´vajı´ aproximacˇnı´mi, nı´zkofrekvencˇnı´mi, sˇka´lovy´mi nebo trendo- vy´mi. Koeficientydmnpak detailnı´mi, vysokofrekvencˇnı´mi, waveletovsky´mi nebo doplnˇ- kovy´mi.

Ortonormalita je zarucˇena na jednotlivy´ch u´rovnı´chm, tj.

⟨φ_mk, φml⟩=δkl=

 1, k=l 0, k̸=l . Pro skala´rnı´ soucˇin mezi sousednı´mi u´rovneˇmi pak platı´

⟨φ_m,k, φm+1,l⟩=hl−2k, k, l∈Z, 

∀k

h²_k = 1.

Konstrukceψje da´na na´sledujı´cı´ procedurou. Necht’l²je diskre´tnı´ analog prostoruL²(R). Je-liφ∈V0 ⊂V1a{φ(2t−n)}je ortonorma´lnı´ ba´zı´V1, pak posloupnost koeficientu˚hn∈l² splnˇuje tzv.dilatacˇnı´ rovnici

(18)

φ(t) =√ 2

n∈Z

hnφ(2t−n), (5)

kdeh_n jsou sˇka´lovacı´ filtracˇnı´ koeficienty, ktere´ zajisˇt’ujı´ ortonormalitu. Pokud ma´φ(t) kompaktnı´ nosicˇ, pak je pocˇet teˇchto koeficientu˚ nenulovy´. Vyrˇesˇenı´m rovnice (5) odstar- tovala e´ra konstrukce ortonorma´lnı´ch waveletu˚.

Definujme

ψ(t) =√ 2

n∈Z

g_nφ(2t−n), (6)

pak wavelety ψ_mn(t) = 2⁻^m²ψ(2^−mt−n), m, n ∈ Z tvorˇı´ ortonorma´lnı´ waveletovske´

ba´ze prostoru˚Wm, ktere´ se nazy´vajı´ Daubechiesove´. Tyto wavelety nemajı´ osy symetrie a ortonormalita je zarucˇena mezi ru˚zny´mi u´rovneˇmim. V prˇı´padeˇ jen ortogona´lnı´ ba´ze platı´

φ(t) =

n∈Z

h_nφ(2t−n), ψ(t) =

n∈Z

g_nφ(2t−n). (7)

3.2 Diskre´tnı´ waveletova´ transformace - DWT

Spojita´ waveletova´ transformace ma´ sve´ nevy´hody prˇi realizaci, jde zejme´na o [34]:

• Redundance dat (nadbytecˇnost) - po CWT dostaneme nekonecˇne´ mnozˇstvı´ koeficientu˚, ktere´ nelze prakticky vyuzˇı´t.

• Pro veˇtsˇinu funkcı´ nema´ CWT analyticke´ rˇesˇenı´, je proto nutne´ pocˇı´tat numericky.

Na´sledujıćı´ text je cˇerpań z [32]. K zı´skańı´ prˇiblizˇne´ho vy´sledku CWT se prova´dı´ jejı´

diskre´tnı´ aproximace. Prˇedpis pro diskre´tnı´ aproximaci signa´luf(t)lze zapsat f(t) =

∞



m=−∞

∞



n=−∞

d_m,nψ_m,n(t).

kde koeficienty d_m,n znacˇı´ diskre´tnı´ waveletovou transformaci signa´lu f(t). Mysˇlenka DWT je stejna´ jako u CWT, ale metody se lisˇı´. CWT prova´dı´ konvoluci waveletu prˇı´mo se signa´lem, zatı´mco DWT se provede konvolucı´ vstupnı´ho signa´lu soucˇasneˇ s nı´zkopa´smovy´m a vysokopa´smovy´m filtrem. Nı´zkopa´smovy´ filtr je definova´n posloupnostı´h_n, kde je typicky jen pa´r nenulovy´ch hodnot. Vysokopa´smovy´ filtr se znacˇı´gn. Nı´zkopa´smovy´

filtr se sestavı´ s vyuzˇitı´m vysokopa´smove´ho jako hn= (−1)ⁿg1−n, kde vza´jemna´ ortogonalita filtru˚



n

hngn+2j = 0

(19)

pro vsˇechnaj ∈ Zje splneˇna. Po konvoluci obou filtru˚ se vstupnı´m signa´lem, jsou oba vy´stupy podvzorkova´ny na polovinu, kdy se jednodusˇe kazˇdy´ druhy´ vzorek vynecha´.

Po filtraci s g_n dostaneme detailnı´ koeficienty a po filtraci s h_n se koeficienty nazy´vajı´

aproximacˇnı´. Proces je zna´zorneˇn na obra´zku 1. Je zde zobrazena banka filtru˚, ktera´ ma´

strukturu stromu, rozdeˇlujı´cı´ signa´l do neˇkolika komponent. Aproximacˇnı´ koeficienty v kazˇde´m stupni dekompozice, mohou by´t opeˇt filtrova´ny, cˇı´mzˇ se postupneˇ buduje strom.

Dekompozice se mu˚zˇe opakovat za u´cˇelem zvy´sˇenı´ frekvencˇnı´ho rozlisˇenı´.

Pro rekonstrukci obrazu se pak prova´dı´ IDWT, ktera´ je prova´deˇna v opacˇne´m porˇadı´ nezˇ DWT. Mı´sto podvzorkova´nı´ signa´lu se provede nadvzorkova´nı´ a to tak, zˇe se jednotlive´

koeficienty prokla´dajı´ nulami. Da´le se provede konvoluce shnagn, kdy jejich soucˇet da´va´

aproximacˇnı´ koeficienty (v prˇı´padeˇ, zˇe byl proveden jen jeden krok DWT, tak dostaneme pu˚vodnı´ signa´l).

Obra´zek 1:Dekompozice signa´lu pomocı´ banky filtru˚ (prˇevzato z [32])

Vzorkujme nynı´ parametrya,bdle

a=a^m₀ , b=n·b0·a^m₀ , m, n∈Z, tı´m dostaneme diskretizovanou waveletovskou funkci

ψ_m,n(t) = 1

a^m₀ ψ

a^−m₀ t−n·b₀

, (8)

kde a0 > 1 a b0 > 0, dilatace a translace jsou urcˇeny pomocı´ m a n. Pak waveletova´

transformace s diskre´tnı´mi wavelety pro spojity´ signa´lf(t)je definova´na

F_m,n = 1

a^m₀

+∞



−∞

f(t)ψ

a^−m₀ t−n·b₀

dt. (9)

Hodnoty F_m,n, zvane´ take´ jako waveletovske´ nebo detailnı´ koeficienty jsou da´ny na dilatacˇneˇ-translacˇnı´ mrˇı´zˇce nadm, n. Zpeˇtna´ diskretizovana´ waveletova´ transformace je formulova´na

f(t) =

∞



m=−∞

∞



n=−∞

Fm,nψm,n(t). (10)

(20)

Sˇka´lova´nı´ dyadicke´ mrˇı´zˇky

Dyadicka´ mrˇı´zˇka je jednou z nejjednodusˇsˇıćh a nejvıće efektivnıćh diskretizacı´ pro prak- ticke´ ućˇely a take´ nejbeˇzˇneˇji pouzˇı´vana´ metoda ke konstrukci ortonorma´lnı´ waveletovske´

ba´ze. Dyadickou mrˇı´zˇku dostaneme, kdyzˇ zvolı´me parametrya0 = 2ab0 = 1. Rovnici (8) pak lze prˇepsat jako dyadicky´ wavelet

ψ_m,n(t) = 1

√2^m ψ

2^−mt−n

. (11)

Pak lze dyadickou waveletovou transformaci s waveletem (11) zapsat

Fm,n =

+∞



−∞

f(t)ψm,n(t)dt. (12)

Prˇedpis pro inverznı´ dyadickou waveletovou transformaci je shodny´ s (10).

Jelikozˇ pracujeme se signa´ly konecˇne´ de´lky, uved’me, jak je definovana´ diskre´tnı´ wa- veletova´ transformace (DWT), s kterou budeme pracovat. Prˇedpisy pro konvoluci i s podvzorkova´nı´m jsou da´ny

a_k+1 =

M



l=1

a_k(l)·h(l−2k), (13)

d_k+1=

M



l=1

a_k(l)·g(l−2k), (14)

kdeM je velikost signa´lu,ak prˇedstavuje vstupnı´ signa´l nebo aproximacˇnı´ koeficienty z prˇedchozı´ u´rovneˇ. Vy´sledkem jsou aproximacˇnı´ koeficienty a_k+1 a detailnı´ koeficienty d_k+1. Inverznı´ diskre´tnı´ waveletova´ transformace (IDWT)je realizova´na tak, zˇe se vy´stupy DWT nadvzorkujı´ (prokla´da´nı´ nulou) a na´sledneˇ se provedou konvoluce s jednotlivy´mi filtry, tedy

a_k=

M



l=1

a_k+1(l)·h(l−k) +

M



l=1

d_k+1(l)·g(l−k). (15)

(21)

3.2.1 Proble´m konecˇne´ de´lky signa´lu˚

Proble´m se projevuje na okrajı´ch intervalu analyzovane´ho signa´lu po DWT. Je du˚sledkem konecˇne´ de´lky obou signa´lu˚ u DWT prˇi konvoluci. Dle charakteru signa´lu lze tento nezˇa´doucı´ jev zcela nebo cˇa´stecˇneˇ eliminovat pomocı´ [34]:

• doplneˇnı´ signa´lu nulami- chybeˇjıćı´ cˇa´st nutna´ pro vy´pocˇet konvoluce se doplnı´ nulami, je to jednoduche´ rˇesˇenı´, ktere´ veˇtsˇinou zaprˇıćˇinı´ proble´my na okrajıćh signa´lu po DWT,

• symetrizace - doplneˇnı´ pu˚vodnı´m signa´lem symetricky kolem okrajove´ho bodu, vyvola´ vznik nesrovnalostı´ v prvnı´ derivaci a tedy i na okrajı´ch intervalu signa´lu po DWT, vhodne´ pro 2D transformaci obrazu˚,

• periodizace - doplneˇnı´ signa´lu periodicky´m opakovańı´m pu˚vodnı´ho signa´lu, vhodne´ zejmeńa pro signa´ly periodicke´ho charakteru, nevyvola´va´ vznik nesrov- nalostı´ na okrajıćh signa´lu po DWT.

3.2.2 Waveletova´ transformace obrazu

Doposud jsme si uvedli, jak se provede DWT v prˇı´padeˇ jednorozmeˇrne´ho signa´lu, cˇı´mzˇ jsme zı´skali detailnı´ a aproximacˇnı´ koeficienty. My se vsˇak budeme zaby´vat obrazovy´mi funkcemi, ktere´ jsou veˇtsˇinou dvourozmeˇrne´. Princip DWT pro 2D obrazy zu˚sta´va´

stejny´. Nejprve se aplikuje 1D DWT na rˇa´dky a pote´ se na vy´sledek te´to transformace aplikuje znovu 1D DWT na sloupce. Tohle je jeden krok waveletove´ transformace neboli prvnı´

stupenˇ dekompozice. Vy´sledkem je obraz transformovany´ do cˇtyrˇech cˇa´stı´ (subpa´sem):

• HH - diagona´lnı´ obraz, detaily,

• HL - vertika´lnı´ obraz, detaily,

• LH - horizonta´lnı´ obraz, detaily,

• LL - aproximacˇnı´ cˇa´st dane´ u´rovneˇ obsahujı´cı´ nejvı´ce informace.

Aproximacˇnı´ cˇa´st se pak pouzˇije pro druhy´ stupenˇ dekompozice, viz obra´zek 2.

Obra´zek 2:Sche´ma DWT pro 2D obraz s dveˇma stupni dekompozice (prˇevzato z [34])

Zpeˇtna´ 2D DWT se provede obdobneˇ - jednorozmeˇrna´ IDWT nejprve na rˇa´dky a pak na sloupce.

(22)

3.3 Prˇehled waveletu ˚

Vy´sledek procesu s waveletovou transformacı´ za´visı´ na pouzˇite´ vlnce. Existuje neˇkolik stovek ru˚zny´ch waveletu˚ [34]. V na´sledujı´cı´m textu uved’me neˇktere´ typy waveletu˚ spo- lecˇneˇ s jejich vlastnostmi a grafem materˇske´ho i otcovske´ho waveletu, ktery´ byl prˇevzat z [35].

3.3.1 Haaru˚ v wavelet

Jedna´ se o nejjednodusˇsˇı´ wavelet, jednoduchy´ k implementaci, ktery´ je vsˇak nespojity´

[34]. Neumozˇnˇuje hladkou rekonstrukci signa´lu. Neˇkdy se take´ oznacˇuje jako wavelet Daubechies 2. V neˇktery´ch literatura´ch se mu˚zˇe oznacˇovat i jako Daubechies 1.

Vlastnosti:

• je symetricky´,

• ma´ kompaktnı´ nosicˇ,

• vhodny´ pro CWT i DWT,

• ortogona´lnı´ i biortogona´lnı´,

• ma´ explixitnı´ vyja´drˇenı´

ψ(x) =







1, 0≤x < ¹₂

−1, ¹₂ ≤x <1 0, jinde

.

Obra´zek 3:Haaru˚v wavelet

(23)

3.3.2 Daubechies wavelety

Tato trˇı´da waveletu˚ nema´ explicitnı´ vyja´drˇenı´, kromeˇ waveletu Daubechies 2. Pouzˇı´va´

se cˇı´selne´ vyja´drˇenı´ ve formeˇ filtracˇnıćh koeficientu˚, ktere´ poprve´ spocˇı´tala Ingrid Dau- bechies (1988) [3]. Ortonorma´lnı´ wavelety s2M =N nenulovy´mi filtracˇnı´mi koeficienty se znacˇı´ DAUBN(dbN), resp. DAUB2M(db2M), tedy naprˇ. wavelet DAUB 2 je jizˇ zmı´- neˇny´ Haaru˚v wavelet [34]. V te´to praći jsme se drzˇeli znacˇenı´, kdyNje pocˇet nenulovyćh koeficientu˚.

Vlastnosti:

• jsou asymetricke´,

• majı´ kompaktnı´ nosicˇ,

• vhodne´ pro CWT i DWT,

• nemajı´ explicitnı´ vyja´drˇenı´.

Vlastnosti pro vsˇechny Daubechies wavelety jsou stejne´, uved’me proto nynı´ jen pru˚beˇhy neˇkteryćh z nich, ktere´ jsou da´le v praći vyuzˇı´vańy. A tedy wavelety: Daubechies 4, Daubechies 8 a Daubechies 16.

Obra´zek 4:Wavelet Daubechies 4

(24)

3.3.3 Wavelet Cohen-Daubechies-Feauveau 9/7

Wavelet pouzˇı´vany´ u ztra´tove´ JPEG 2000 komprese, oznacˇovany´ jako CDF 9/7 nebo take´

Bior 4.4. Reverznı´ biortogona´lnı´ vlnky majı´ stejne´ vlastnosti jako biortogona´lnı´, znacˇı´ se RbioNr.N_d, kdeNr, N_dje pocˇet nenulovy´ch koeficientu˚ pro rekonstrukci a dekompozici [36].

Vlastnosti:

• je symetricky´,

• vhodny´ pro DWT,

• nenı´ ortogona´lnı´, ale je biortogona´lnı´,

• ma´ explicitnı´ vyja´drˇenı´, ale pouzˇı´va´ se aproximace ve formeˇ koeficientu˚.

(25)

Obra´zek 7:Wavelet Cohen-Daubechies-Feauveau 9/7 (Biorthogonal 4.4)

3.3.4 Wavelet Coiflet 2

Coiflet wavelety jsou konstruova´ny podobneˇ jako Daubechies wavelety, znacˇı´ se CoifN, kdeN je rˇa´d,1≤N ≤5. De´lka filtru je netypicky6N [36].

Vlastnosti:

• te´meˇrˇ symetricky´,

• nema´ explicitnı´ vyja´drˇenı´.

Obra´zek 8:Wavelet Coiflet 2

3.3.5 Wavelet Symlet 6

Symlet wavelety jsou konstruova´ny stejneˇ jako Daubechies wavelety, ale je kladen du˚raz na co nejveˇtsˇı´ symetrii. Znacˇı´ se SymN, kdeN ≤2. De´lka filtru je2N [36].

(26)

Vlastnosti:

• te´meˇrˇ symetricky´,

• nema´ explicitnı´ vyja´drˇenı´.

Obra´zek 9:Wavelet Symlet 6

3.3.6 Komplexnı´ wavelet

Jako poslednı´ uved’me poneˇkud odlisˇny´ komplexnı´ wavelet, ktery´ ma´ rea´lnou i imagi- na´rnı´ slozˇku, jezˇ jsou zobrazeny na obra´zku 10. Koeficienty pouzˇite´ pro tento wavelet jsme zı´skali z [9]. Sˇka´lovacı´ koeficienty majı´ podobu



−3−i

√

15,5−i

√

15,30 +i2

√

15,30 +i2

√

15,5−i

√

15,−3−i

√ 15

 /64.

Jedna´ se o komplexnı´, symetricky´, ortogona´lnı´ wavelet nazy´vany´ SCD-6 [9].

(27)

Obra´zek 10:Komplexnı´ wavelet SCD-6

3.4 Vy´beˇr waveletu

Pro vy´beˇr toho spra´vne´ho waveletu se lze drzˇet jizˇ zna´my´ch faktu˚ [34]:

• Komplexnı´ wavelety, naprˇ. typu Morlet, dobrˇe detekujı´ oscilace, nevhodne´ jsou pro osamocene´ singularity.

• Pro detekci singularit a sˇpicˇek je vhodne´ pouzˇı´vat rea´lne´ wavelety s ma´lo oscilacemi.

• Asymetricke´ wavelety se hodı´ k detekci zmeˇn gradientu.

• Symetricke´ wavelety nezpu˚sobujı´ fa´zovy´ posun mezi sˇpicˇkou (singularitou, osci- lacı´) v signa´lu a polohou dane´ho koeficientu prˇi transformaci.

• K soucˇasne´ detekci amplitudy a fa´ze se pouzˇı´va´ komplexnı´ wavelet.

Lze se drzˇet take´ na´sledujıćı´ho postupu [9]. Necht’B = (W1, W2, ..., Wk)je banka ortogona´lnıćh waveletu˚ aX(M ×N)je matice vstupnı´ho signa´lu (obrazu). Vy´beˇr optima´l- nı´ho waveletu pro vybrana´ dataX_ije zalozˇen na minimalizaci entropicke´ho funkciona´lu B_iôpt=arg minBE(Xi, B):

E(X_i, B) =−

j

p⁽ⁱ⁾_j ·lnp⁽ⁱ⁾_j , (16) kdep⁽ⁱ⁾_j =|a⁽ⁱ⁾_j |²/

a⁽ⁱ⁾



2 l2, 

a⁽ⁱ⁾



2 l2 =

(j)|a⁽ⁱ⁾_j |², a⁽ⁱ⁾_j je prvkem vektoru waveletovyćh koeficientu˚, spocˇı´tanyćh beˇhem zpracovańı´ vektoruX_iv ba´ziW_l, l= 1,2, ..., k.

Spocˇı´tali jsme pro jednotlive´ wavelety dle (16) jejich entropii (nazy´va´ se Shannonova entropie) pro vsˇechny stupneˇ dekompozice, ktery´ch je pro obra´zek512×512px deveˇt.

Vy´sledek lze videˇt v tabulce 1, kde minima´lnı´ hodnota entropie pro dany´ wavelet je zvy´razneˇna. Nejle´pe je na tom komplexnı´ wavelet SCD-6. Nejhu˚rˇe dopadly vlnky Rbio 4.4, ktera´ ma´ dokonce zvysˇujı´cı´ se entropii pro jednotlive´ stupneˇ a take´ ocˇeka´vana´ Haarova vlnka.

(28)

Shannonovaentropiesvlnkami StupenˇHaarDaub4Daub8Daub16Rbio4.4Coif2Sym6SCD-6 1.10,866910,866910,867110,867210,870410,866810,866610,1745-0,0000i 2.10,866810,866710,867010,867010,874110,866610,86649,4825+0,0000i 3.10,866710,866610,866910,866910,879810,866410,86628,7914+0,0001i 4.10,866610,866610,866810,866910,887910,866210,86598,1024+0,0003i 5.10,866610,866510,866810,866710,898310,866010,86577,4179+0,0005i 6.10,866610,866410,866710,866610,904710,865610,86516,7447-0,0000i 7.10,866510,866310,866510,865810,908310,864610,86376,0891+0,0042i 8.10,866510,866210,865710,864510,913410,862910,86115,5028+0,0219i 9.10,866510,866110,864710,862010,910510,859310,85585,0593-0,0064i Tabulka1:HodnotyShannonovyentropie

(29)

4 Metrika k urcˇova´nı´ kvality obrazu

Prˇi zpracova´vańı´ obrazu je velmi du˚lezˇite´ umeˇt posoudit vy´sledek zpracovańı´. V neˇkteryćh prˇı´padech si lze vystacˇit s vizua´lnı´m posouzenı´m kvality zpracovane´ho obrazu (subjektivnı´ posouzenı´), ale to pouze v prˇı´padech, kdy rozdı´ly v obrazech jsou znacˇne´.

Zava´dı´ se proto metoda pro objektivnı´ posouzenı´ kvality, kterou vyuzˇijeme ve vsˇech oblastech zpracova´nı´ obrazu jako metriku.

4.1 Peak Signal to Noise Ratio (PSNR)

Mezi nejjednodusˇsˇı´ metody k posouzenı´ kvality obrazu patrˇı´ metodaPSNR-sˇpicˇkovy´

odstup signa´l/sˇum. Tato metoda nevyuzˇı´va´ k posouzenı´ kvality vlastnosti lidske´ho oka. K vy´pocˇtu je zapotrˇebı´ mı´t pu˚vodnı´ (nezkresleny´) obraz. Kvu˚li sˇiroke´mu spektru mnoha signa´lu˚ se uda´va´ v logaritmicke´m meˇrˇı´tku a jednotkou je decibel [dB]. Rozmezı´ hodnot pro 8 bitovy´ signa´l by´va´ typicky 20 - 40 dB, kde vysˇsˇı´ hodnota znacˇı´ vysˇsˇı´ kvalitu obrazu.

Pro 16 bitova´ data pak 60 - 80 dB. Prˇi vy´pocˇtu vyuzˇı´va´ tzv.strˇednı´ kvadratickou chybu, ktera´

se znacˇı´MSE(Mean Squared Error) a pro dvourozmeˇrny´ obrazovy´ signa´l je definova´na jako [24]

MSE= 1

M N

M



i=1 N



j=1

(X(i, j)−Y(i, j))²,

kdeX(i, j)aY(i, j)jsou hodnoty pixelu˚ pu˚vodnı´ho a zkoumane´ho obrazu aM, N jsou rozmeˇry teˇchto obrazu˚. Hodnota PSNR se pak vypocˇı´ta´ [24]

PSNR= 10·log₁₀

MAX² MSE

 ,

kde MAX znacˇı´ maxima´lnı´ hodnotu pixelu, tj. pro 8 bitovy´ signa´l hodnotu 255. Existujı´ i dalsˇı´ metriky, vı´ce objektivneˇjsˇı´, ktere´ lze rovneˇzˇ nale´zt v [24], my vsˇak budeme pouzˇı´vat pouze metriku PSNR.

(30)

5 Aplikace waveletove´ transformace

V prˇedchozıćh kapitolaćh jsme si prˇedstavili teorii waveletove´ transformace. Ukazˇme nynı´, jak ji lze vyuzˇı´t pro ru˚zne´ aplikace v digita´lnı´m zpracovańı´ obrazu. Na´sledujıćı´

podkapitoly obsahujı´ podrobnosti o jednotlivy´ch aplikacı´ch. Mezi neˇ patrˇı´:

• odstranˇova´nı´ sˇumu v obraze,

• komprese obrazu,

• u´prava kontrastu v obraze,

• rozpozna´va´nı´ vzoru˚ v obraze.

Prˇejdeˇme tedy k jednotlivy´m cˇa´stem.

5.1 Odstran ˇ ova´nı´ obrazove´ho sˇumu

Kazˇdy´ digita´lnı´ obraz je do jiste´ mı´ry postihnut sˇumem. Ve veˇtsˇineˇ prˇı´padu˚ se jedna´

o nezˇa´doucı´ jev, ktery´ je nutno odstranit. Princip odstranˇova´nı´ sˇumu pomocı´ waveletove´ transformace je zna´zorneˇn na obra´zku 11. Nejprve se provede doprˇedna´ waveletova´ transformace obrazu, pak se pomocı´ vhodne´ prahovacı´ metody vynulujı´ koeficienty prˇedstavujı´cı´ sˇum a nakonec se obraz zpeˇtneˇ zrekonstruuje pomocı´ inverznı´ waveletove´

transformace, cˇı´mzˇ zı´ska´me odsˇumeˇny´ obraz.

Obra´zek 11:Blokove´ sche´ma principu odsˇumova´nı´ s vyuzˇitı´m waveletovy transformace

Pojem prahova´nı´ (anglicky thresholding) je obecneˇ rˇecˇeno modifikace hodnot, ktere´ jsou nizˇsˇı´ cˇi vysˇsˇı´ nezˇ zvoleny´ pra´h. Rozlisˇujeme dva typy prahova´nı´, ktere´ urcˇujı´, jaky´m zpu˚sobem se budou, v nasˇem prˇı´padeˇ koeficienty po waveletove´ transformaci, upravovat.

A teˇmi jsou

• tvrde´ pra´hova´nı´,

• meˇkke´ pra´hova´nı´.

(31)

V prˇı´padeˇ tvrde´ho prahovańı´ (angl. hard thresholding) jsou vsˇechny hodnoty, ktere´ jsou nizˇsˇı´ nebo rovny nastavene´mu prahu vynulovańy. Ostatnı´ hodnoty zu˚sta´vajı´ stejne´. Prˇes- neˇji je tento proces vyja´drˇen na´sledujıćı´ funkcı´

η(x) =

0 pro|x| ≤T,

x pro|x|< T. (17)

Naproti tomu meˇkke´ prahova´nı´ (angl. soft thresholding), kde hodnoty, ktere´ u tvrde´ho pra´hova´nı´ zu˚staly nezmeˇny, jsou nynı´ zveˇtsˇeny, respektive zmensˇeny o dany´ pra´h. Na´- zorneˇjsˇı´ vysveˇtlenı´ da´va´ tato funkce

η(x) =







x−T pro x > T, 0 pro|x| ≤T, x+T pro x <−T.

(18)

Nynı´ prˇejdeme k metoda´m prahovańı´, ktere´ na´m urcˇujı´, jaky´ pra´h je nejvhodneˇjsˇı´ pro dany´ obraz. Jiny´mi slovy jsou tyto metody adaptivnı´. V praći se sezna´mı´me se trˇemi metodami prahovańı´ a teˇmi jsou

• VisuShrink

• SureShrink

• BayesShrink

Nezˇ si popı´sˇeme jednotlive´ metody prahovańı´, je vhodne´ si zave´st tzv.univerza´lnı´ pra´h, ktery´ je za´rovenˇ jednou z nejjednodusˇsˇıćh metod prahovańı´. Pra´h T se touto metodou spocˇte dle vztahu

T =σ

2 logN , (19)

kdeN je de´lka signa´lu,σje smeˇrodatna´ odchylka sˇumu.

5.1.1 VisuShrink

Prvnı´ z metod prahova´nı´ je metoda VisuShrink. Jedna´ se o nejjednodusˇsˇı´ metodu k odstranˇova´nı´ sˇumu, se kterou budeme pracovat. Tato metoda byla poprve´ prˇedstavena matematiky Donoho a Johnstone v roce 1995 [4]. Nevy´hodou te´to metody je, zˇe nedoka´zˇe odstranit sˇum typuspeckle[5], poradı´ si pouze s aditivnı´m sˇumem.

K metodeˇ VisuShrink je potrˇeba odhadnout smeˇrodatnou odchylku sˇumuσ. To lze prove´st s vyuzˇitı´m detailnı´ch koeficientu˚ waveletove´ transformace

(32)

σ = median({|gj−1,k|:k= 0,1, ...,2^j−1−1})

0.6745 , (20)

kdegj−1,k prˇedstavuje detailnı´ koeficienty waveletove´ transformace. Vyuzˇı´vajı´ se pra´veˇ tyto koeficienty, protozˇe je zde nejvı´ce zastoupen sˇum. Takto odhadnuta´ smeˇrodatna´ odchylka se vyuzˇije v univerza´lnı´m prahu (19), cˇı´mzˇ zı´ska´me pra´h pro metodu VisuShrink.

Prˇi samotne´m prahova´nı´ se projedou pouze detailnı´ koeficienty, sˇka´lovacı´ koeficienty zu˚stanou nezmeˇneˇny.

5.1.2 SureShrink

Tato metoda je podobna´ metodeˇ VisuShrink, lisˇı´ se v tom, zˇe pra´h se volı´ pro ka- zˇdou u´rovenˇ a cˇa´st dekompozice zvla´sˇt’. Pro smeˇrodatnou odchylku sˇumu se pouzˇije opeˇt vztah (20) s tı´m rozdı´lem, zˇe se budou postupneˇ uplatnˇovat detailnı´ koeficienty po waveletove´ transformaci (HHx, HLx, LHx koeficienty). Zvoleny´ pra´h je da´n kombinacı´

univerza´lnı´ho prahu (19) a tzv. Stein’s Unbiased Risk Estimator (SURE) prahu (viz [6]).

Hodnota vy´sledne´ho prahuT je pak da´na T =min

S, σ

2 logN ,

kdeSje hodnota SURE prahu,N je de´lka signa´lu aσje smeˇrodatna´ odchylka sˇumu.

5.1.3 BayesShrink

Model te´to metody [7] mu˚zˇe by´t vyja´drˇen jako Y =X+V,

kdeY prˇedstavuje waveletovou transformaci zasˇumeˇne´ho obrazu,Xje waveletova´ transformace pu˚vodnı´ho obrazu aV znacˇı´ waveletovou transformaci zasˇumeˇny´ch cˇa´stı´ s nor- ma´lnı´m rozdeˇlenı´mN(0, σ²_v). Nebot’XaV jsou vza´jemneˇ neza´visle´, odchylkyσ_y²,σ_x²aσ_v² zy,xavjsou da´ny

σ_y²=σ_x²+σ_v².

V [8] bylo uka´za´no, zˇe odchylka sˇumuσ_v² mu˚zˇe by´t odhadnuta z prvnı´ dekompozicˇnı´

u´rovneˇ z koeficientu˚ HH, resp. HH1jako

σ_v² =

median(|HH1|) 0.6745

2

.

BayesShrink pra´hova´nı´ je stejneˇ jako prˇedchozı´ metody adaptivnı´, urcˇuje pra´h pro kazˇde´

subpa´smo zvla´sˇt’, stejneˇ jako metoda SureShrink. Vy´sledny´ pra´h je stanoven prˇedpisem

(33)

T =





 σ²_v

σx proσ_v²< σ_y², max{|A_m|} jinak,

kdeσ_x=

 max

σ²_y−σ²_v,0

aA_mjsou jednotlive´ waveletovske´ koeficienty dle subpa´sma, v jake´m je pra´h pocˇı´ta´n.

5.1.4 Maza´nı´ singula´rnı´ch cˇı´sel v SVD rozkladu matice paketove´ho roz- kladu

Poslednı´ metodou odsˇumova´nı´ obrazu (viz [9]), kterou nelze prˇı´mo zarˇadit mezi metody prahovacı´, jelikozˇ se skla´da´ z vı´cero kroku˚. Skla´da´ se tedy z teˇchto kroku˚:

• Jelikozˇ obrazovy´ signa´l je dvoudimenziona´lnı´ a pro dalsˇı´ pra´ci se signa´lem potrˇebu- jeme signa´l jednorozmeˇrny´, prvnı´m krokem je ”vyskla´dat” vsˇechny rˇa´dky za sebe do jednoho jednorozmeˇrne´ho vektoru. Vy´sledny´ vektor je sice velmi velky´, tudı´zˇ je proces vy´pocˇetneˇ na´rocˇneˇjsˇı´, ale umozˇnı´ to jednodusˇsˇı´ pra´ci s nı´m.

• Vy´beˇr optima´lnı´ho waveletu a waveletove´ ba´zeB^optna za´kladeˇ minima´lnı´ entropie:

B^opt=arg min_BE(X, B)

• Po waveletove´ transformaci do maxima´lnı´ mozˇne´ u´rovneˇ dekompozice se vybere optima´lnı´ hladina na za´kladeˇ prˇedchozı´ho kroku a sestavı´ se matice paketove´ho rozkladu.

• Jakmile ma´me matici paketove´ho rozkladu z obrazove´ho vektoru, provedeme SVD rozklad (naprˇ. viz [10]) te´to matice. Serˇadı´me si podle velikosti vsˇechna singula´rnı´

cˇı´sla a od nejmensˇı´ho postupneˇ nulujeme. Pote´ zpeˇtneˇ zrekonstruujeme matici paketove´ho rozkladu po odmaza´nı´ singula´rnı´ch cˇı´sel.

• Provedeme zpeˇtnou waveletovou transformaci z matice paketove´ho rozkladu a z vy´sledne´ho jednorozmeˇrne´ho signa´lu, nynı´ uzˇ odsˇumeˇne´ho, vyskla´da´me vy´sledny´

dvourozmeˇrny´ obraz.

5.1.5 Porovna´nı´ metod

Pro tuto kapitolu o odsˇumovańı´ obrazu jsme pro testovańı´ pouzˇı´vali obra´zek Lenny o velikosti2048×2048 px. Jako prvnı´ jsme zminˇovali, rozdı´l mezi tvrdy´m a meˇkky´m prahovańı´m. Meˇkke´ prahovańı´ poskytuje ostrˇejsˇı´ vy´sledky (vıće zachova´va´ hrany) v porovnańı´ s prahovańı´m tvrdy´m, kde obraz vıće vyhladı´, a tedy i nechteˇne´ artefakty v obraze. Rozdı´ly nejsou znacˇne´, dokud se nepouzˇije prˇı´lisˇ velky´ stupenˇ dekompozice (viz obra´zek 12), proto zvolene´ prahovańı´ za´visı´ na dane´ aplikaci. Pro dalsˇı´ systematicke´

(34)

Obra´zek 12:Rozdı´l mezi meˇkky´m (vlevo) a tvrdy´m (vpravo) prahova´nı´m po cˇtyrˇech (nahorˇe) a sˇesti (dole) stupnı´ch dekompozice

porovna´nı´ vy´sledku˚ budeme pouzˇı´vat pouze tvrdy´ typ prahova´nı´, nebot’poskytuje lepsˇı´

vy´sledek, jak lze i videˇt z hodnot PSNR z obra´zku 12.

Da´le jsme si prˇedstavili trˇi metody prahova´nı´. Nejprve ukazˇme (obra´zek 13) na nejjedno- dusˇsˇı´ Haaroveˇ vlnce, zˇe nenı´ dobre´ volit prˇı´lisˇ vysoky´ stupenˇ dekompozice. Jak lze videˇt z obra´zku 13 a take´ z experimentu˚, je vhodne´ volit mezi druhy´m azˇ cˇtvrty´m stupneˇm dekompozice. V prˇı´padeˇ vysˇsˇı´ho stupneˇ docha´zı´ ke znacˇne´ degradaci obrazu a hodnota PSNR se snizˇuje. V dalsˇı´m porovna´va´nı´ proto vyuzˇijeme trˇetı´ stupenˇ dekompozice.

(35)

Obra´zek 13:Porovna´nı´ neˇkolika stupnˇu˚ dekompozice s Haarovou vlnkou

Nynı´ ve zbytku te´to kapitoly porovna´me jednotlive´ metody v za´vislosti na pouzˇite´ vlnce (waveletu).

Graficky zna´zorneˇne´ porovna´nı´ mu˚zˇeme videˇt na obra´zku 14. Porovna´vali jsme metody VisuShrink, SureShrink, BayesShrink pro ru˚zne´ typy vlnek. Konkre´tneˇ vlnky typu Haar, Daubechies 4, Daubechies 8 a Daubechies 16. Pouzˇili jsme trˇetı´ stupenˇ dekompozice a tvrdy´ typ prahova´nı´. Hodnoty PSNR jsou zobrazeny v leve´m dolnı´m rohu kazˇde´ho obrazu. Znovu prˇipomenˇme, zˇe metody jsou adaptivnı´, tudı´zˇ pra´h se volı´ automaticky na za´kladeˇ vstupnı´ho obrazu. Nejostrˇejsˇı´ vy´sledky poda´va´, nehledeˇ na pouzˇitou vlnku, metoda BayesShrink. Naopak nejrozostrˇeneˇjsˇı´ vy´sledky metoda SureShrink.

Haarova vlnka v porovna´nı´ s ostatnı´mi vlnkami typu Daubechies poda´va´ poneˇkud de- gradovany´ obraz. Haarova vlnka je nejjednodusˇsˇı´ vlnkou vu˚bec, tudı´zˇ je ocˇeka´vatelne´, zˇe nebude tou nejlepsˇı´ volbou v odsˇumova´nı´ obrazu. Dle hodnot PSNR, Haarova vlnka poda´va´ take´ nejhorsˇı´ vy´sledek. Prˇijatelny´ vy´sledek lze videˇt pouze u metody BayesShrink.

Tato metoda vsˇak zanecha´va´ bı´le´ a cˇerne´ tecˇky v obraze a v prˇı´padeˇ Haarovy vlnky jsou tyto tecˇky nejviditelneˇjsˇı´. Jak jsme jizˇ rˇekli, metoda BayesShrink poskytuje nejostrˇejsˇı´ vy´- sledek, ale ten je za cenu mı´rne´ho vy´skytu sˇumu. U metod VisuShrink a SureShrink lze povazˇovat za nejlepsˇı´ vlnku Daubechies 4. Od vlnky Daubechies 8 se v obraze zacˇı´najı´

vyskytovat artefakty v podobeˇ zdvojenı´ v mı´stech hran. Nejhorsˇı´ vizua´lnı´ vy´sledek je u metody SureShrink s vlnkou Daubechies 16, kde dosˇlo ke znacˇne´mu prˇehlazenı´ obrazu, i kdyzˇ hrany se snazˇı´ zu˚stat zachova´ny, jsou vsˇak zdvojeny kvu˚li artefaktu˚m v obraze. Porovna´me-li si vsˇak hodnoty PSNR, tak zjistı´me, zˇe se hodnoty od vizua´lnı´ho posouzenı´ kvality neˇkdy lisˇı´. Naprˇı´klad artefakty v obraze mohou by´t velmi neprˇijatelne´

a prˇesto hodnoty PSNR vysˇly nejle´pe. Je proto nutne´, by´t prˇi posuzovańı´ kvality obez- rˇetny´. Za´veˇrem lze rˇıćt, zˇe pokud hleda´me kompromis mezi tı´m, jakou vlnku zvolit pro odsˇumovańı´ obrazu, tak spra´vnou volbou se jevı´ vlnka Daubechies 4.

(36)

Obra´zek 14:Porovna´nı´ jednotlivy´ch metod s ru˚zny´mi druhy vlnek

Podı´va´me-li se na vy´sledek porovna´nı´ poslednı´ metody pro odstranˇova´nı´ sˇumu pomocı´

SVD rozkladu matice paketove´ho rozkladu, kde jsme opeˇt pouzˇili Haarovu, Daubechies 4, Daubechies 8 a Daubechies 16 vlnku. Vyuzˇili jsme opeˇt obra´zek Lenny o velikosti 2048×2048px. Po experimentech, nejlepsˇı´ vy´sledek jsme dostali, pokud jsme vynulovali

(37)

singula´rnı´ cˇı´sla mensˇı´ nezˇ 9. Mensˇı´ hodnota nezˇ 9 obraz te´meˇrˇ nezmeˇnila, veˇtsˇı´ hodnota naopak obraz hodneˇ rozmazala. Graficke´ zna´zorneˇnı´ lze videˇt na obra´zku 15. V prˇı´padeˇ Haarovy vlnky dosˇlo k veˇtsˇı´mu rozmazańı´ obrazu nezˇ u zbylyćh. Rozdı´ly mezi vsˇemi vlnkami jsou ale velmi male´, o cˇemzˇ vypovı´da´ i hodnota PSNR (zobrazena´ v leve´m spodnı´m okraji obrazu˚ na obra´zku 15). Pocˇty vymazanyćh singula´rnıćh cˇı´sel pro pouzˇite´

vlnky jsou:

• Haar: 1972 z 2048,

• Daubechies 4: 1972 z 2048,

• Daubechies 8: 1973 z 2048,

• Daubechies 16: 1973 z 2048.

Obra´zek 15:Porovna´nı´ metody pro odstranˇova´nı´ sˇumu pomocı´ SVD rozkladu matice paketove´ho rozkladu

Uka´zali jsme dalsˇı´ mozˇnou metodu pro odstranˇovańı´ obrazove´ho sˇumu, ktera´ vsˇak ne- poskytuje tak dobry´ vy´sledek jako metody vyuzˇı´vajıćı´ prahovańı´.

(38)

5.2 Komprese obrazu

Za´kladnı´ mysˇlenkou komprese obrazu je zmensˇit velikost datove´ho obrazove´ho sou- boru prˇi co nejveˇtsˇı´m zachova´nı´m kvality pu˚vodnı´ho obrazu. Komprese mu˚zˇe by´t ztra´- tova´ i bezeztra´tova´. Pro u´cˇel komprese obrazu se ve veˇtsˇineˇ prˇı´padu˚ pouzˇı´va´ ztra´tova´, kde se vyuzˇı´va´ nedokonalosti lidske´ho oka (snı´zˇenı´ barev, redukce detailu˚). Jelikozˇ my pro jednoduchost pracujeme s cˇernobı´ly´mi obrazy, bude na´s zajı´mat komprese obrazu pomocı´ redukce detailu˚.

Za´kladnı´m ukazatelem u´cˇinnosti komprese je tzv.kompresnı´ pomeˇr, neboli podı´l nekom- primovany´ch dat ku komprimovany´m datu˚m. Snazˇı´me se tedy o co nejvysˇsˇı´ kompresnı´

pomeˇr prˇi zachova´nı´ dostatecˇne´ kvality obrazu.

Waveletova´ transformace je skveˇly´ na´stroj ke kompresi obrazu, nebot’umozˇnˇuje obrazovy´

signa´l rozlozˇit do ru˚zny´ch frekvencˇnı´ch hladin (nı´zke´ a vysoke´ frekvence) a podle potrˇeby neˇktere´ frekvence obrazu (vysoke´ = detaily) eliminovat.

V ra´mci experimentu jsme vzali obra´zek Lenny o velikosti 512×512 px, provedli do- prˇednou waveletovou transformaci na trˇi hladiny (stupneˇ dekompozice) a na´sledneˇ pro jednotlive´ vlnky zkousˇeli nulovat jednotlive´ hladiny (pouze detailnı´ koeficienty) a zkou- mali, jak tı´m bude vy´sledny´ obraz po zpeˇtne´ waveletove´ transformaci ovlivneˇn. Vy´sledek lze videˇt na obra´zku 17. Pro u´cˇel komprese na´s zajı´ma´ veˇtsˇinou pouze vynulovany´ prvnı´

stupenˇ dekompozice (koeficienty HH1, LH1, HL1), ktery´ poskytuje pomeˇrneˇ slusˇny´ vy´sledek, kdyzˇ uva´zˇı´me, zˇe tı´mto ihned zkra´tı´me pameˇt’nutnou k ulozˇenı´ obrazu na cˇtvrtinu.

Alternativou by mohlo by´t, odmazat pouze koeficienty HH1 a LH1 (viz obra´zek 16), pokud by ztra´ta detailu˚ byla nad u´nosnou mez. Pak by jsme usˇetrˇili polovinu pameˇti.

Vynulovat vı´ce nezˇ jednu hladinu nenı´ prˇı´lisˇ vhodne´, jelikozˇ tı´m dojde k prˇı´lisˇ velke´ ztra´teˇ obrazovy´ch detailu˚.

Obra´zek 16:Vynulovane´ HH1a LH1koeficienty s vyuzˇitı´m Daubechies 16 vlnkou, PSNR =87,4449dB

(39)

Obra´zek 17:Porovnańı´ obrazu˚ po vynulovańı´ jednotlivyćh stupnˇu˚ dekompozice pro ru˚zne´ typy vlnek

Tabulka 2 zobrazuje spocˇtene´ hodnoty PSNR (Peak Signal to Noise Ratio) pro jednotlive´

vlnky v prˇı´padeˇ vynulova´nı´ prvnı´ho azˇ trˇetı´ho stupneˇ dekompozice (detailnı´ koeficienty).

Cˇı´m vysˇsˇı´ je tato hodnota, tı´m lze kompresi povazˇovat za kvalitneˇjsˇı´.

Vlnka, ktera´ poskytuje nejlepsˇı´ vy´sledek je Daubechies 8, poprˇı´padeˇ Daubechies 16. Tyto vlnky prˇi prvnı´m stupni dekompozice pouze jemneˇ rozlozˇı´ detaily do nenulovy´ch ko-

(40)

eficientu˚. Ostatnı´ koeficienty jsou z velke´ cˇa´sti rovny nule (nebo jsou velmi blı´zko nule, tudı´zˇ je lze zanedbat). Dı´ky tomu nedojde k degradaci obrazu odmaza´nı´m du˚lezˇity´ch detailu˚ v obraze.

PSNR [dB]

Vlnka 1 z 3 2 z 3 3 z 3

HAAR 78,9677 74,5637 71,5531 DAUB 4 81,4724 76,6105 73,0128 DAUB 8 82,9228 77,0885 73,2153 DAUB 16 82,8703 77,4963 73,4292 CDF 9/7 82,1918 76,9513 73,1549

Tabulka 2:PSNR hodnoty pro data z obra´zku 17

Podotkneˇme, zˇe jsme doposud na transformovana´ obrazova´ data s vynulovany´mi koeficienty neaplikovali zˇa´dny´ kompresnı´ algoritmus (bezeztra´tovy´). Provedli jsme pouze cˇa´st rˇeteˇzce (viz obra´zek 18) prˇi kompresi obrazu. Tato cˇa´st, kdy nulujeme koeficienty je ztra´tova´ a pra´veˇ v te´to cˇa´sti urcˇujeme, jak moc chceme obrazova´ data zkomprimovat.

Pote´ na´sleduje neˇjaky´ vhodny´ bezeztra´tovy´ algoritmus, ktery´ ma´ za u´kol tyto data jesˇteˇ vı´ce zredukovat, ale tak, aby se dala opeˇt zrekonstruovat.

Obra´zek 18:Sekvence kroku˚ prˇi typicke´ kompresi obrazu s vyuzˇitı´m waveletove´ transformace

(41)

5.2.1 Od JPEG po kompresi JPEG 2000

JPEG standard (Joint Photographic Experts Group) byl vytvorˇen v roce 1994 jako vy´- sledek procesu, ktery´ zapocˇal jizˇ v roce 1986. Tato skupina odbornı´ku˚ pro zpracova´nı´

obrazu, nominovańa Mezina´rodnı´ organizacı´ pro normalizaci a vy´znamny´mi spolecˇ- nostmi, pracovala na vy´robeˇ tohoto standardu pro spojite´ ko´dovańı´ obrazu. Vy´sledkem byl ztra´tovy´ kompresnı´ algoritmus (forma´t pro ulozˇenı´ obrazovyćh dat), zalozˇeny´ na diskre´tnı´ kosinove´ transformaci (DCT). V dobeˇ sve´ho vzniku byl nejrozsˇı´rˇeneˇjsˇı´m obrazovy´m forma´tem na internetu. Brzy se vsˇak uka´zalo, zˇe je JPEG nedostatecˇny´ pro rˇadu aplikacı´. Dosˇlo proto na rozsˇı´rˇenı´ tehdejsˇı´ho JPEG standardu, to vsˇak nebylo dostatecˇne´

kvu˚li proble´mu s vlastnicky´mi pra´vy [23]. Bylo trˇeba prˇijı´t s lepsˇı´m standardem. DCT nahradila diskre´tnı´ waveletova´ transformace a mohl tak postupneˇ vzniknout novy´ standard pro kompresi obrazu.

Nezˇ prˇejdeme k nove´mu standardu ukazˇme jesˇteˇ, jak vypada´ proces [19] prˇi JPEG kompresi, ktery´ je zobrazen na obra´zku 19. Sesta´va´ se z teˇchto kroku˚

Obra´zek 19:Proces JPEG komprese (prˇevzato z [20])

• Nejprve je trˇeba obraz prˇedzpracovat. V prˇı´padeˇ barevne´ho obrazu prˇeve´st z RGB do YCrCb barevne´ho modelu, tzn. do jasove´ a dvou chrominacˇnı´ch slozˇek. Barev- nostnı´ slozˇky je mozˇno podvzorkovat. Kazˇda´ z teˇchto slozˇek se pak zpracova´va´

zvla´sˇt’.

• Na´sledneˇ kazˇdou slozˇku rozdeˇlit do bloku˚ o velikosti 8×8 pixelu˚.

• Pro kazˇdy´ blok se provede DCT.

• Koeficienty po DCT jsou da´le kvantizova´ny, tj. vydeˇleny kvantizacˇnı´ maticı´ a zao- krouhleny. Kvantizacˇnı´ matice je stejna´ pro vsˇechny bloky.

• Pote´ jsou takto upravene´ koeficienty komprimovańy pomocı´ RLE algoritmu (Run- Length encoding) a zako´dovańy do sekvence nul a jednicˇek Huffmannovy´m ko´do- vańı´m.

• Poslednı´m krokem je bud’ ulozˇenı´ dat, nebo datovy´ prˇenos.

V prˇı´padeˇ dekomprese obrazu je postup opacˇny´. RLE, Huffmannovo ko´dova´nı´ a DCT je bezeztra´tovy´ proces (stejneˇ jako waveletova´ transformace). K samotne´ ztra´teˇ docha´zı´ prˇi kvantizaci, kdy se drˇı´ve zaokrouhlene´ koeficienty vyna´sobı´ kvantizacˇnı´ maticı´.

JPEG standard je sta´le nejvıće popula´rnı´ forma´t pro ukla´dańı´ obrazu˚ na webovyćh serve- rech. Rozlisˇenı´, prˇi ktere´m je komprimovań, je dostatecˇne´ pro beˇzˇne´ prohlı´zˇenı´ na webu.

(42)

Avsˇak lide´, kterˇı´ pracujı´ s digita´lnı´mi obrazy, identifikovali mnoho proble´mu˚, v ktery´ch je JPEG nedostatecˇny´. Mezi hlavnı´ nevy´hody ([21]) JPEG standardu patrˇı´

• Neumozˇnˇuje bezeztra´tovou kompresi - pro mnoho aplikacı´ je ztra´ta informace neprˇijatelna´.

• Oddeˇlenı´ obrazu˚- rozdeˇlenı´ obrazu na bloky 8×8 znamena´, zˇe jsou zpracova´ny neza´visle na sobeˇ. To je nevy´hodne´, pokud bychom se snazˇili vyuzˇı´t homogenity oblasti, ktera´ je veˇtsˇı´ nezˇ 8×8 pixelu˚.

• Vliv bloku˚- tı´m, zˇe je obraz blokoveˇ rozdeˇlen, nelze cˇasto zajistit hladky´ prˇechod mezi bloky v komprimovane´m obraze.

• Vliv hran- DCT pracuje s kosinovou funkcı´ a tedy pracuje nejle´pe, pokud vstupnı´

data jsou periodicka´. To vsˇak nenı´ typicka´ vlastnost v rˇa´dcıćh a sloupcıćh digita´lnıćh obrazu˚.

• Globa´lnı´ transformace- jaka´koliv chyba cˇi odchylka ve vstupnı´m obraze se projevı´

ve vy´stupnı´m.

Novy´ standard byl vyvinut stejnou skupinou odbornı´ku˚ jako standard JPEG. Vznikl JPEG 2000. Meˇl slouzˇit jako na´hrada standardu JPEG, ktery´ meˇl prˇedcˇit v mnoha vlastnostech.

Hlavnı´ vy´hody ([21]) JPEG 2000 vu˚cˇi JPEG jsou

• Lepsˇı´ kompresnı´ pomeˇr- JPEG 2000 produkuje vysoce kvalitnı´ obrazy prˇi nizˇsˇı´m bitove´m toku (0,025 bpp a nizˇsˇı´m) nezˇ JPEG.

• Progresivnı´ prˇenos signa´lu - JPEG 2000 doka´zˇe zrekonstruovat digita´lnı´ obrazy (prˇi zvysˇujı´cı´ mı´rˇe rozlisˇenı´), jak jsou data prˇijı´ma´ny prohlı´zˇecˇem.

• Tiling - umozˇnˇuje uzˇivateli rozdeˇlit obraz do bloku˚, ktere´ jsou da´le samostatneˇ zpracova´va´ny, stejneˇ jako v JPEG. Toto rozdeˇlenı´ (tiling) nemusı´ vsˇak by´t jen 8×8 pixelu˚.

• Oblasti za´jmu (ROI) - uzˇivatel mu˚zˇe indentifikovat tyto oblasti, ktere´ jsou pak zako´dova´ny s veˇtsˇı´m rozlisˇenı´m nezˇ ostatnı´ oblasti, naprˇ. oblicˇeje.

• Veˇtsˇı´ velikost obrazu- JPEG standard umozˇnˇuje obrazy do velikosti64 000×64 000 bodu˚. JPEG 2000 naproti tomu obrazy azˇ do rozlisˇenı´4 294 967 295×4 294 967295 bodu˚.

• Vı´cena´sobne´ kana´ly- JPEG standard podporuje kompresi trˇı´ kana´lu˚ (barevne´ obrazy). JPEG 2000 mu˚zˇe podporovat kompresi azˇ 256 kana´lu˚ (slozˇek). Tak velke´

mnozˇstvı´ slozˇek je beˇzˇne´ pro satelitnı´ data.

Podobneˇ jako JPEG, tak i komprese JPEG 2000 se skla´da´ ze 4 hlavnı´ch kroku˚:

prˇezpracovańı´, transformace, kvantizace, zako´dovańı´. Narozdı´l od JPEG, kvantizace je volitelna´, pokud si uzˇivatel prˇeje bezeztra´tovou kompresi. Mı´sto Huffmanova ko´dovańı´