@CT 0 @LM 1 @RM 66 @PL 65 @TB -----T-----T-----T-----T-----T-----T-----T-----T-----T-----T-----T-----T-----T-----T-----T-----T-----T-----T-----T-----T-----T-----T @MT 3 @MB 3 @PO 10 @PN 1 @OP @HE # @LH 6 @LH 3 estn prehlsenie estne prehlasujem, e diplomov prcu som vypracoval samostatne na zklade literatry, ktor citujem v zozname pouitej literatry. @LH 6 V Bratislave da .......... .............. Podpis @LH 3 @LH 6 @LH 3 Poakovanie Na tomto mieste by som rd vyjadril poakovanie Ing.J.Polecovi za jeho cenn rady, pripomienky a vestrann pomoc pri @LH 6 vypracovan diplomovej prce. @LH 3 OBSAH: Pouit skratky a symboly ................................8 vod......................................................10 1 Transforman kompresn postupy.........................11 1.1 Kombinovan transforman kdovanie ..................13 2 Homomorfn filtrcia....................................15 3 Diskrtne ortogonlne transformcie.....................17 3.1 Jednorozmern DOT.....................................17 3.2 Dvojrozmern DOT......................................17 3.3 Pouit ortogonlne transformcie.....................19 3.3.1 Diskrtna fourierova transformcia (DFT)............19 3.3.2 Diskrtna hartleyho transformcia (DHYT)............20 3.3.3 Diskrtna kosnusov transformcia (DCT)............20 3.3.4 Haarova transformcia (HT)..........................21 3.3.5 Walsh - Hadamardove transformcie (WHT,WPT,WST).....21 3.3.6 ikm transformcia(SHT,SPT,ST).....................22 3.3.7 DFT a DHYT s preusporiadanymi bzami................23 3.3.7.1 Preusporiadanie vsledku DFT......................23 3.3.7.2 Preusporiadanie vsledku a bzy DHYT (DHYT2)......24 4 Popis programovho vybavenia............................25 4.1 Veobecn charakteristiky programu....................25 4.2 Popis uvateskho rozhrania.........................26 4.2.1 Normlny reim......................................25 4.2.1.1 pecifikcia vstupov..............................27 4.2.1.1.1 Zadvanie vstupnch parametrov..................27 4.2.1.1.2 Pomocn vstupn sbory..........................30 4.2.1.2 pecifikcia vstupov.............................30 4.2.1.2.1 Vstupy do sborov..............................30 4.2.1.2.2 Textov vstupy na terminlov obrazovku........31 4.2.1.2.3 Vstupy grafickho charakteru na terminl.......31 4.2.2 Dekompresn reim...................................32 4.2.3 Manulny reim......................................32 4.2.4 Grafick nadstavba..................................33 4.2.4.1 Prezeranie obrazovch dt.........................33 4.2.4.2 Histogramy obrazovch dt.........................34 4.3 Popis tuktry programu..............................35 4.3.1 Kompletn truktra v reime normal.................35 4.3.2 Kompletn trukra programu v dekompresnom reime...36 4.3.3 Kompletn trukra programu v manulnom reime......36 4.4 Popis jednotlivch funknch skupn blokov............37 4.4.1 Logaritmus a exponovanie dt........................37 4.4.2 Spracovanie UIS zloky pri CTC kdovan.............37 4.4.2.1 Ziv - Lempel kdovanie............................37 4.4.2.2 Kdovanie Run Lenght a Huffmanovm kdom..........37 4.4.3 DOT.................................................38 4.4.4 Kvantizcia a filtrcia maticou.....................39 4.4.5 Linerna kvantizcia................................40 4.4.6 Orezvanie a naberanie spektra......................40 4.4.7 Kdovanie/dekdovanie spektra.......................42 4.4.8 Ruenie spektra.....................................44 4.4.9 Vpoet entrpi a kompresi........................45 4.4.10 Delenie na bloky...................................46 4.5 Popis zdrojovch sborov..............................46 Zver.....................................................48 Zoznam pouitej literatry................................49 Prloha...................................................50 Pouit skratky a symboly 8 1D - Jednodimenzionlny 2D - Dvojdimenzionlny bpp - bits per pixel BC - kdovanie typu bzy, DOT - diskrtna ortogonlna transformcia, DFT - Diskrtna Fourierova transformcia DFT2 - 2D DFT s preusporiadanou bzou DCT - Diskrtna Cosnusov trasformcia DHYT - Diskrtna Hartleyho transformcia DHYT2 - DHYT s preusporiadanou bzou DI - dvojkov inverzia EC - entropick kodr EOB - End Of Block F - Filter GI - Preusporiadanie pomocou Grayovho kdu H - Entropia HT - Haarova transformcia JSM - Jednosmern zloky spektra KOE - Koeficienty obnovy energie LIS - doln obrazov sbor, mat - prvky kvantizanej matice MS - pam sekvennch spektier. O - otzka slo P - predspracovanie, PBL - poet blokov PBR - poet bitov potrebn na uschovanie relneho sla Q - kvantiztor, R - znenie redundancie 13 Tmto, v sasnosti u tandardnm, postupom je mon dosahova vysok kompresn pomery pri ete dostatonej "itatenosti" obrazu. Schmu transformanho kdera meme vylepi pouitm pouitm novch transformci, alebo oivenm niektorch starch, pouvanch doteraz na kdovanie alebo aproximciu inch druhov signlov, prpadne ich adaptvnym vberom. Systm sa me taktie adaptova aj vekosou transformovanho bloku: @LH 6 Ŀ Ŀ Ŀ   VB Ĵ BC Ĵ   vstup   EC vstup Ŀ Ŀ Ŀ Ŀ Ĵ S Ĵ DOT Ĵ Ĵ Q Ĵ vzork. MS sig.       Ŀ  Ĵ ...8, 16, 32,... @LH 3   Obr.1.3. Transforman kodr s adaptvnou vekosou  transformovanch blokov a s adaptvnym vberom 2D  diskrtnej ortogonlnej transformcie. 1.1 Kombinovan transforman kdovanie  V tejto modifikcii sa obrazov sbor rozdel na 2 asti podla jeho stochastickch vlastnost. Prvou asou je horn obrazov sbor, ktor je reprezentovan najvym hornm bitom obrazovch vzoriek (UIS) alebo niekokmi najvymi bitmi. Druhou je doln obrazov sbor, reprezentovan zvynmi dolnmi bitmi obrazovch vzoriek @LH 6 (LIS). 4.Popis programovho vybavenia. 25 @LH 3 Program bol vytvoren pod operanm systmom BSD UNIX 4.2 (Ultrix) v jazyku C. Pretoe nevyuva iadne pecifick funkcie rznych verzii UNIXU, je prenositeln aj na systmy HP UX, SUN OS, Linux, SCO UNIX. Aby to bolo zaruen je grafick podpora programu napsana pouitm len zkladnej grafickej kninice "Xlib", ktor sa tandartne dodva s X Windows. Pri vytvran programu bol kladen draz na matematick sprvnos a prenositenos. Z tohto dvodu je program rozdelen na 12 zdrojovch sborov (modulov), ktor predstavuj samostatn logick celky.Popis vi as 4.5. 4.1 Veobecn charakteristiky programu.  Hlavn oblasti pouitia programu by sa dali uvies v nasledujcich bodoch: . Transforman kdovanie ( monos CTC ) ( rzne modifikcie ) . Filtrcie ( monos Homomorfnej filtrcie ) ( rzne typy zonlnych filtrov, napr.DP ) . Nelinerne aj linerne kvantizcie spektra (napr. CCIR kvantizanou maticou) . Vnanie umelho ruenia v spektre @LH 6 . Potanie entrpi obrazovch a spektrlnych dt @LH 3 Program m pritom nasledujce monosti: . Delenie obrazovch dt na rovnak bloky typu 2r x 2s  . Pouitie hybridnch transformci kombincou 12 DOT (rzne pre smer X a Y ) uvedench v prlohe v TAB.1 . . Automatick opakovan vykonvanie transformanho postupu . dekompresia zakdovanch dt 26 . zjednoduen reim prce(len transformcie obrazu) . 2 odlin spsoby spracovania UIS pri CTC . 3 spsoby rieenia orezvania spektra . 3 spsoby urenia vekosti orezvania spektra . pouitie kvantizanej matice ako filtranej 4.2 Popis uvateskho rozhrania.  Za elom zachovania kompatibility programu pri span z rznych typov terminlov je zkladnm reimom behu programu textov md. Grafick rozhranie tvoria dva samostatn programy, ktor ukazuj bu obrazov data, alebo histogram. Tieto s span (volitene) poas behu programu ako samostatn procesy, take pre uvateov bez grafickho terminlu zostane funknos programu nezmenen, a na monos vizulneho sledovania obrazovch informci poas behu programu. Program me pracova v troch zkladnch reimoch. Charakter sa uruje pri tartovan programu: 1. Normlny reim tartovanie: a) b) 2. Dekompresn reim tartovanie: -back { } 3. Manulny reim tartovanie: -man Pri nekorektnom odtartovan sa vype krtky HELP a beh programu sa ukon. @LH 6 Ŀ 29 Vypisova spektrum ako sbor relnych isel ? (0=nie,1=nekvantonan,2=nakvantovan) Ŀ Vypisova spektr do sborov ? O.11 Kresli spektr ? O.12 Upravova nzvy vstupnch sborov? O.13 (Pre vetky 3 otzky 0=nie,1=no) @LH 3 OBR 4.1 Sslednos zadvania vstupnch parametrov @LH 6  Ŀ Ŀ Kruhov ruenie Zig - Zag ruenie > Ŀ Ŀ Zadaj rel.amplitdu, Zadaj o robi tvar, hranicu ("DATA"= ta aie dta Ŀ "END" = ukoni naitavanie) END < Ŀ Zadaj polohu maxima (x, y) Zadaj rel.amplitdu, tvar,hranicu @LH 3 @LH 6 @LH 3 OBR 4.2 Sslednos zadvania parametrov ruenia  . Vstupn obrazov sbor je vo formate PIC (vi prloha ). . Bliie popisy vznamov konkrtnych zadanch hodnt a otzok s pri popisoch jednotlivch ast programu pre ktor s uren. . Poloky oznaen (*) a (**) maj odlin formt zadvania.Umouje sa tm viacnsobn prevdzanie celho transformanho postupu pre ich rzne hodnoty . . Pre (*) sa zadvaj 2 hodnoty: maximum, minimum.Vpoet sa zane s maximom a v kadom nasledujcom kroku sa hodnota bude deli 2, pokm sa nedosiahne minimum. . Pre (**) sa zadvaj 3 hodnoty: maximum, minimum, krok. Vpoet sa zane s maximom a v nslednch vpotoch sa bude zmenova o krok, pokm sa nedosiahne minimum. Modifiktor * v nzvoch sborov je uren pouitou DOT. 31 Tvorba a modifikcia nzvov uvedench sborov je podmienen zadanmi vstupnmi parametrami. Poda odpoved pri zadvan s mon nasledovn modifikcie: 4) O.9 - Ak odpove je "0" nevytvraj sa iadne vstupn sbory okrem sboru analyza 5) O.10 - Ak odpove je "0" nevytvra sa sbor *.flo 6) O.11 - AK odpove je "0" nie s vytvran sbory sp*.pic 7) O.13 - Ak je odpove "1" s nzvy vetkch vstupnch sborov (okrem sboru analyza) modifikovan pridanm sla na zaiatok, urujceho kok krt sa opakuje transforman postup ( vhodn pri viacnsobnom transformanom kdovan). 4.2.1.2.2 Textov vstupy na terminlov obrazovku  Program poas svojho behu vypisuje na terminl informcie o aktulnom stave vpotu,priom s vypisovan okrem informci vypisovanch do sboru analza aj niektor menej dleit iastkov vsledky. Presmerovanm tohto vstupu pri tarte programu, zskame pln prehlad o akcich vykonanch poas behu programu. 4.2.1.2.3 Vstupy grafickho charakteru na terminl  Poas behu programu mu by tmto spsobom zobrazovan vetky obrazov dta vypsan do vstupnch sborov (vi. 4.2.4 ). Ich zobrazovanie je podmienen odpoveou "1" na O.12 . @LH 6 Ŀ 33 Zadaj transformcie pre smer X a Y (zadvaj sa textov skratky uveden v TAB.1) Zadaj typ transfomcie (1=priama,-1=sptn) Zadaj rozmery transformanho poa (x a y) Zadvanie vstupnch dt transformanho poa po riadkoch @LH 3 OBR.4.3 Zadvanie vstupnch hodnt v reime manual @LH 6 @LH 3  Poda toho, ak transformcia bola poadovan, me by zadvanie dt rozdelen na zadvanie pola relnej a imaginrnej asti dt (analogicky je to aj pri vypisovan transformovanch dt). 4.2.4 Grafick nadstavba 4.2.4.1 Prezeranie obrazovch dt. (program "ushow.c")  Program zobrazuje obsah danho vstupnho sboru, priom sa redpoklad,e vstupn dta s vo formte PIC. tartovanie rogramu je : 1) show {nepovinne [ir] [host]} i - zobraz inverzne r - zobraz v root okne [host] - aplikcia sa zobraz na display "host" 2) show V druhom prpade vype krtky HELP a spta sa na meno vstupnho sboru. Po vykreslen dt je mon s obrazom prevdza jednoduche opercie: upravova mierku, invertova obraz, zisova hodnoty obrazovch bodov. OVLDANIE: m - zmenenie rozmerov obrzku na polovicu v - zvsenie rozmerov obrzku na dvojnsobok o - nastavenie originlnych rozmerov obrzku 34 i - invertovanie zobrazovanch dt r - presun obrazovch dt do root okna a ukonenie q - ukonenie av tlaidlo myi - uke sradnice aktulnej pozcie a hodnotu obrazovho bodu prav tlaidlo myi - ako av + zmen zobrazovaciu polohu dajov na aktulnu Charakteristiky: 1) Pri zmene vekosti okna sa mierka dt automaticky prispsob 2) Data pri Grayscale alebo Color displayoch s zobrazovan v 128 odtieoch edi. 3) Pri Black - White displayoch je automaticky uskutonen dithering obrazovch dt. 4.2.4.2 Histogramy obrazovch dt. (program "uhisto.c")  Program zobrazuje histogram a pota entropiu danho vstupnho sboru, priom sa predpoklad, e vstupn dta s vo formte PIC. tartovanie programu je : 1) histo 2) histo V druhom prpade vype krtky HELP a spta sa na meno vstupnho sboru. OVLDANIE: q - ukonenie programu tlaidl myi - uke poetnos hodnoty na aktulnej pozcii kurzoru Charakteristiky: 1) Pri zvovan okna automaticky prispsobuje geometriu zobrazovania @LH 6 36 @LH 3 Pozn.: V truktre s vyznaen miesta, kde sa vytvraj vstupn informcie. Prpadn modifikcie zvisia @LH 6 od zadania parametrov vi 4.2.1.1.1 @LH 3 4.3.2 Kompletn truktra programu v dekompresnom reime @LH 6  Ŀ Natanie vstupnch parametrov Ŀ Natanie globlnych parametrov z *.cmp Ŀ Dekdovanie UIS zloky Ŀ Dekdovanie spektrlnych dt Ŀ Sptn naberanie spekt. dt Ŀ Transformcia kvant. matice Nsobenie kvant. maticou ---> vypisovanie spektier do .pic Ŀ vykreslovanie spektier Sptn DOT Ŀ Exponovanie dt Ŀ Pridanie UIS zloky ---> vypsanie vstupnch Ŀ obrazovch dt Vyhodnotenie MSE @LH 3 Pozn: Prpadn modifikcie truktry zvisia od @LH 6 globlnych parametrov natanch z kompresovanho sboru. @LH 3 @LH 6 4.3.3 Kompletn trukra programu v manulnom reime  Ŀ Natanie vstupnch parametrov a dt Ŀ DOT Ŀ Vypsanie vstupnch pol @LH 3 37 @LH 6 @LH 3 4.4 Popis jednotlivch funknch skupn blokov. 4.4.1 Logaritmus a exponovanie dt  Tento blok podmieuje prevdzanie homomorfnej filtrcie. Jeho innos by sa dala popsa nasledovne: Pri logaritmovan : x(n,m)= ln [x(n,m)+1] Pri exponovan : x(n,m)= exp [x(n,m)-1] n = 0 .. N-1 m = 0 .. M-1 N - X-ov vekost obrazovch dt M - Y-ov vekost obrazovch dt 4.4.2 Spracovanie UIS zloky pri CTC kdovan 4.4.2.1 Ziv - Lempel kdovanie Pri zadvan parametrov sa pre tento blok poaduj 2 hodnoty: 1) Poet UIS rovn - uruje poet UIS bitovch rovn 2) Poet bit/bity - uruje, koko bitov z dt vytvorench z natanch bit. rovn je uloench v jednom byte dt, na ktor sa aplikuje Ziv - Lempel algoritmus. Pouit bol ZL 77 algoritmus, ktor je implementovan v tandartnom programe UNIXu "compress". Dta s preto najskr vypsan do doasnho sboru, na tento sa pouije program compress, vstup je prepsan do sboru .cmp a doasn sbor sa zmae. 4.4.2.2 Kdovanie kombinciou Run Lenght a Huffmanovho kdu.  Pri zadvan parametrov sa pre tento blok poaduj 2 hodnoty: 1) Kdovanie vzdialenosti - udva poet bitov, ktor je pouit na kdovanie potu za sebou rovnakch znakov pri RL kdovan. 38 2) Poet bitov vzorky - udva koko bitov z dt zakdovanch RL kdom sa pouije ako 1 vzorka pre Huffmanov kd ( udva vlastne nepriamo poet rovn pre Huffmanov kd) . Pri tomto postupe je UIS tvoren len 7.bitovou rovinou. Na u sa aplikuje 1D RL kd a na tento nsledne Huffmanov kd. Takto upravnen dta s pripsane do *.cmp. 4.4.3 DOT Implementovanch je 12 DOT, ktorch defincie a popis s v 3.3 .Pouit boli rchle algoritmy typu Cooley Tuckey poda [1]. Je mon poui rzne transformcie v X a Y smere ( hybridn transformcie ). Ak funkcia inch blokov programu zvis od pouitej transformcie, dominantn je transformcia pouit v X smere. truktra bloku pre priamu a sptn DOT: @LH 6 Ŀ Ŀ > blok = 0 .. PBL-1 > blok = 0 .. PBL-1 Ŀ Ŀ natanie obraz. bloku natanie spekt. bloku * Ŀ Ŀ Priama DOT v smere X Sptn DOT v smere Y Ŀ Ŀ Priama DOT v smere Y Sptn DOT v smere X Ŀ Ŀ vypsanie spekt. bloku * vypsanie obraz. bloku @LH 3 Pozn.: (*) - rob preusporiadanie spektra DFT2 poda asti 3.3.7.1 @LH 6 @LH 3 4.4.4 Kvantizcia a filtrcia maticou 39 Pri kvantizcii a filtrcii s postupy nasledovn: @LH 6 Ŀ Ŀ Inicializovanie matice Inicializovanie matice Ŀ Ŀ > blok = 0 .. PBL-1 blok = 0 .. PBL-1 Ŀ Ŀ delenie maticou delenie maticou Ĵ Ĵ - - - - - - : - - - - - - : Ŀ : Linerny kvantiztor - - - - - - : - - - - - - Ŀ > blok = 0 .. PBL-1 OBR 4.4 Filtrcia maticou  Ŀ nsobenie maticou Ĵ : @LH 3 OBR 4.3 Kvantizcia maticou  Pri kvantizci maticou sa jedn o nelinernu kvantizciu priom tento blok prevdza len zmenu dynamiky dt. Vlastn kvantizcia ( linerna ) sa uskutouje mimo bloku. Postup pri inicializcii matice je nasledujci: @LH 6 Ŀ Natanie matice zo sboru Ŀ Prispsobenie matice na vekos bloku Ŀ Ĵ Zadan transformcia matice? nie Ŀ mat(x,y) = 1/mat(x,y) Sptn DCT v smere Y Sptn DCT v smere X Priama DOT v smere X Priama DOT v smere Y mat(x,y) = 1/mat(x,y) Ĵ @LH 3 OBR.4.5 Postup pri inicializcii matice STR zloiek normovan poda vzahu: 46 @LH 6 poet natanch STR zloiek odhad = H.-------------------------------------------- (4.8) @LH 3 pvodn poet vetkch STR zloiek v spektre Pri vyslovan kompresie STR zloiek spektra Huffmanovm kdom nie s bran do vahy prdavn dta potrebn na dekdovanie STR zloiek. ( udva len efektivitu @LH 6 kdu ).Je normovan podobne ako jej odhad. @LH 3 4.4.10 Delenie na bloky ( S )  V tejto asti sa inicializuj truktry, ktor umouj riaden prstup k blokom obrazovch dt, tj. poda sla bloku prideuje iadateom dta a charakteristiku bloku. Tento spsob rieenia je zvolen vzhadom na ahk neskor prechod k pouvaniu nerovnakch blokov ( napr. niektormi @LH 6 algoritmami adaptvnych metd ). @LH 3 4.5 Popis zdrojovch sborov : auto.c - Zkladn funkcie uvateskho rozhrania. Obsluha vetkch troch zkladnch reimov behu programu : normlny, dekompresn, manulny . cos.c - Procedry na vpoet 2D DCT pomocou 1D DFT furier.c - Procedry na vpoet 2D DFT a na preusporiadanie jej spektra. haar.c - Procedry na vpoet 2D HT,1D HT hartley.c - Procedry na vpoet 2D DHYT , na preusporiadanie spektra ( 2D DHYT2) koder.c - Obsahuje riadiacu procedru na upravy v spektre pri kompresii aj pri dekompresii. log.c - Procedry na homomorfn filtrciu, vpoet entropie spektra a na ruenie spektra. matrix.c - Procedry pre prcu s kvantizanou (napr. CCIR) a filtranou maticou, jej adaptciu na vekos 47 bloku a prpadn transformciu. quant.c - Procedry na linerne kvantovanie striedavch a jednosmernch zloiek spektra a na nelinernu kvantizciu / filtrciu . rez.c - Procedry na natavanie spektra a na zonlnu filtrciu riad.c - Hlavn procedry riadiace dopredn a sptn transformciu,prcu v spektre,riadenie sledu akci pri vetkch 3 reimoch behu programu rlcod.c - Procedry na kompakciu UIS pri CTC kdovan kombincou Run Lenght a Huffmanovho kdovania. slant.c - Obsahuje procedry SI na vpoet 2D Slantovch transformcii z WHT. spdecod.c - Procedry na dekdovanie spektrlnych dt specoder.c- Procedry na kdovanie spektrlnych dt tools.c - Sbor pomocnch procedr na prcu s blokmi, sprvu pamti, procesov, prcu s bitovmi dtami trafodef.c- Textov defincie transformci, procedry na sprvu a rozliovanie transformci. ttools.c - Sbor pomocnch procedr pri vpotoch transformci. uhisto.c - Samostatn program na vykreslovanie histogramov zadanch obrzkov a na rtanie ich entropie ushow.c - Samostatn program na vykreslovanie obrzkov vv.c - Procedry na prcu so sbormi walsh.c - Procedry na potanie 2D WHT ziv.c - Procedry na kompakciu UIS pri CTC kdovan pomocou Ziv Lempelovho algoritmu simul.h - Definovanie globlnych premennch a definci