Ostatní integrální transformace – sinová a cosinová

tyto transformace pracují se stejnými (upravenými) algoritmy jako FT, jsou však přizpůsobeny pro výpočty pouze určitých koeficientů a mají i určité specifické vlastnosti.

Diskrétní cosinová transformace DCT

Tato transformace se používá, v případě, že na „koncích“ signálu je nulová derivace. Obsahuje pouze cosinové složky (výsledný signál je sumací cosinových průběhů). Oproti FT však počítá s jinými frekvencemi (násobek 2, u FT celé cykly, zde i „půlcykly“). Výhodou oproti FT je to, že energie je „stažena“ do nižších frekvencí a proto se lépe hodí k využití u kompresních algoritmů.

Idea této transformace vychází z Fourierovy transformace, která převádí časový obraz signálu na frekvenční spektrum, ve kterém se dá lehce analyzovat signál. Transformace jsou lineární, tzn. lze převést signál i zpátky, na původní obraz. Zde mluvíme o diskrétní verzi, proto značíme Diskrétní Fourierovu transformaci jako DFT - discrete Fourier transform. Existuje i varianta pro rychlé počítačové zpracování odvozená od FFT.

Jelikož v tomto předmětu se zabýváme 2D obrazovými informacemi, uveďme přímo 2D tvar, kdy vstupní obraz je dvourozměrná matice, a nad ní má DFT následující tvar:

FFT (celé periody), sin T, cos T (i půlperiody)

F(u,v) je vzorec přímé DFT a f(x,y) je vzorec zpětné DFT dle [17]. Tato transformace ale má nevýhodu, že F(u,v) je komplexní funkce (tedy má reálnou a imaginární část) ale využívá jen reálné členy. Proto výsledek zabere v paměti dvojnásobek místa. Proto vznikly způsoby výpočtu, které vedou k optimalizaci. Diskrétní kosinová transformace (DCT) vychází z diskrétní Fourierovy transformace (DFT), která převádí časový obraz signálu na frekvenční spektrum, ve kterém se obraz lépe analyzuje. DCT obsahuje pouze reálnou část komplexního spektra a proto zabírá při výpočtu v paměti poloviční místo oproti diskrétní Furierově transformaci. Dle [4] slouží pro výpočet DCT pro dvourozměrný čtvercový signál s (obraz) vzorec:

Principem je, že vstupní signál násobíme diskrétním harmonickým signálem pro který platí:

Bázi lze fyzicky znázornit na následujícím obrázku.

Tuto kosinusovou funkci se snažíme proložit jak v horizontálním, tak i ve vertikálním směru a tak dostaneme výstupní frekvenční obraz signálu. Vstupem do výpočtu je dvourozměrná čtvercová matice rozměru N s hodnotami s(m,n).

Obr. Bázové funkce DCT [RTJP]

Lze odvodit, že pokud nemá dojít ke ztrátě informace, pak je li hodnota s n-bitová, musí být t (n+3)-bitová pro zajištění přesnosti [2]. Samozřejmě tento vztah platí pro DCT velikosti 8x8, pro větší se musí samozřejmě zvětšit i obor hodnot výsledku.

Další proměnný koeficient C uvnitř vzorce pro DCT se počítá jako:

Vzorec pro výpočet DCT se také velmi často zapisuje již přímo ve tvaru pro matici o velikosti 8x8, jeho tvar pak je:

Význam prvků t(i,j) je obdobný jako u DFT, t(0,0) udává střední hodnotu celého transformovaného signálu a ostatní prvky napravo či dolů udávají frekvenční koeficienty postupně rostoucích frekvencí. To detailně popisují obrázky v obrázkové galerii. Hlavní rozdíl mezi DCT a DFT je ten, že DCT výsledné spektrum rozmázne do více s frekvencí klesajících peaků, ale stále umístěných kolem levého horního rohu, kdežto DFT se snaží o umístění komplexně sdružených prvků do levého horního / pravého dolního rohu. (případně zbývajících rohů) Proto se někdy výsledek DFT logicky přeskládává tak, aby tyto „rohy“ se přemístily doprostřed okna, kde se tím pádem soustředí většina energie obrázku. Z toho plynou důsledky pro použití DCT versus DFT. DCT se používá pro kompresi obrazu, a to také díky své výpočetní nenáročnosti.

Vstupní data v případě digitálního obrazu je dvourozměrná matice A(x,y) o x sloupcích a y řádcích. Výstupem je matice T(i,j) o stejném rozměru jako matice A. DCT se spočítá podle vzorce

(1)

kde

pro u=0, jinak C(u) = 1, pro u > 0

Malé n je rozměr čtvercového bloku v pixelech.

K DCT existuje i inverzní transformace, která převede frekvenční spektrum zpět na původní obraz.

(2)

Diskrétní kosinová transformace se využívá pro ztrátovou kompresi obrazu do formátu JPEG. Transformace se aplikuje nejčastěji na čtvercové matice o velikosti 8x8 pixelů. Obraz se tedy rozdělí na čtverečky, které se potom zpracovávají jeden po druhém. Vzorec (1) lze poté přepsat do tohoto tvaru

(3)

Matice T obsahuje tzv. DC koeficienty tvořící frekvenční mapu. Při kompresi se využívá toho, že lidské oko není citlivé na vysoké frekvence. Amplitudy těchto frekvencí jsou umístěny v pravém dolním rohu matice. Naopak nejnižší frekvence jsou v levém horním rohu. Prvek T(0,0) udává střední hodnotu celého transformovaného obrazu a má největší vliv na celková obrazová data v matici. Pro kompresi se pak používá tzv. kvantizační matice. Skupina JPEG definovala optimální kvantizační matici, která respektuje anatomii lidského oka a měla by znamenat rovnováhu mezi kvalitou a mírou komprese. Tato matice má největší hodnoty právě v místech, kde jsou vysoké frekvence. Má tvar

(4)

Po vydělení matic zůstane v T matici velký počet nul. Zig-zag metodu se převede matice T na řádkový vektor, kde první prvek představuje DC člen a poslední nejvyšší frekvenci.Na tento vektor se použije bezeztrátová komprese RLE (Run Length Encoding). A poté se ještě zakóduje pomocí Huffmanova kódování. Výsledkem je zkomprimovaný obraz ve formátu JPEG. V obrazové galerii na obr. 4 je příklad zkomprimovaného obrázku pro několik různých hodnot kvantizačního faktoru q, který se může pohybovat od 0-100.

Dalším rozdílem mezi DCT a DFT je rozložení výsledného spektra – pokud by jsme vybírali pouze část výsledného spektra pro další použití, tak u DFT je ve středové čtvrtině 69 % výkonu celého spektra, kdežto u DCT je v této čtvrtině 99,78 % výkonu, což je pro kompresi a následnou rekonstrukci zvláště výhodné. Tato statistika se dá úpravou bázových vektorů ještě zlepšit.

Bohužel bázové vektory, jsou u této transformace pevně dány, a tak jsou výstupní signály neefektivní. Toto řeší následující transformace. Diskrétní kosínová transformace se ve zpracování obrazu používá při ztrátové kompresi formátu JPEG. Nevýhodou DCT transformace je, že předpokládá stejný rozptyl hodnot v osách x a y obrazu. Tento problém řeší LV transformace, kde se využívá transformace tak, aby body byly rozmístěny kolem jedné osy s co nejmenším rozptylem. To umožňuje vyšší stupeň komprese.

Tato transformace se využívá ve formátu JPEG a MPEG.Výsledek takto transformovaného obrázku zpracovává JPEG formát, který výstupní blok koeficientů transformovaného obrázku 8x8 vynásobí kvantizační maticí (to z důvodu optimalizace pro lidské oko), zaokrouhlí, přečte koeficienty pomocí zig-zag metody (která je navržena s ohledem k vlastnostem DCT, že ukládá koeficienty blíže k levému hornímu rohu), takto získaný vektor se dále komprimuje pomocí RLE komprese, a získaná data se nakonec komprimují pomocí klasického Huffmanova kódování. Velmi podrobně je celý postup komprese do JPEG formátu popsána v [18] a [10].

Obrázek 1. transformace pruhů (DFT přeskládána do přirozeného zobrazení)

Obrázek 2. Koeficienty transformace obecného obrázku – nalevo FFT, napravo DCT

Obrázek 3. – porovnání bázových vektorů KLT (nalevo) a DCT (napravo)

Obrázek 4. Princip komprese JPEG

obr. 2 Postup při kompresi JPEG

a) b) c)

Obrázek 5. DCT aplikovaná na testovací obraz. a) testovací obraz, b) DCT z celého obrazu (spektrum celého obrazu) c) DCT z rozsekaného obrazu na čtverečky 8x8 (JPEG)

Diskrétní sinová transformace

Obsahuje pouze sinové složky (výsledný signál je sumací sinových průbšhů). Tato transformace se využívá, jsou-li hodnoty na „krajích“ signálu nulové.

[1] Jan Čapek, Peter Fabian, Komprimace dat – principy a praxe

ISBN 80-7226-231-9, Computer Press Brno, 2000

[2] Digitální obrazová technika – standard JPEG http://www.volny.cz/mills1/digital/jpeg/jpeg3.htm

[3] Do hlubin JPEG
http://www.builder.cz/art/homepage/dohlubinjpg.htm

[4] Discrete Cosine Transform
http://planetmath.org/encyclopedia/DCT.html

[5] Dr. Talyor, Bryan Davis alias Mojo Discrete Cosine Transform and Karhunen Loéve Transform Approximation of Correlated Signals
Digital Signal Processing Foundations, 1999
http://plaza.ufl.edu/badavis/EEL5701_Project.doc

[6] Development of a Fine-grained Parallel Karhunen-Loève Transform
http://privatewww.essex.ac.uk/~fleum/jpdsPapv3.pdf

[7] http://www.ieee.cz/mtt/soutez05/prace/typl/dipltypl.pdf

[8] Transform Coding (dobře čtivé, skenováno z nějaké knihy )

http://www.cs.uiowa.edu/~jjkari/196_05fall/transform.pdf

[9] Transform Coding

http://gps-tsc.upc.es/GTAV/Torres/Teaching/IVC-Notes/transform_english.pdf

[10] Grafické formáty

http://mdg.vsb.cz/jdolezal/Pgrafika/Prednaska/GrafickeFormaty.html

[11] Compression of color images, Ricardo de Queiroz, Xerox Corporation

http://signal.ece.utexas.edu/~queiroz/papers/compcolor.pdf

[12] Porovnání jednotlivých integrálních transformací ke kompresi obrázků.

http://www.sendme.cz/sklad/index.html