Článok sa zaoberá aplikáciou Householderovho algoritmu ortogonalizácie bázových funkcií zovšeobecnenej diskrétnej kosínusovej transformácie obrazových segmentov. Testovanie tohto algoritmu ortogonalizácie sme uskutočnili na syntetizovaných a tiež na reálnych obrazových segmentoch. Householderov algoritmus ortogonalizácie vypočíta všetky ortogonálne bázové funkcie naraz, je veľmi presný, vykazuje výrazne malú (takmer nulovú) strednú kvadratickú chybu pre jednotlivé testované obrazové segmenty. Nevýhodou Householderovho algoritmu je najmä časová náročnosť výpočtu, ktorá so zväčšujúcimi sa blokmi v obrazovom segmente rastie. Je však vhodnejší v porovnaní s Gram-Schmidtovym algoritmom ortogonalizácie bazových funkcií, ktorý počíta s postupnou ortgonalizáciou a v niektorých prípadoch sa vyznačuje nestabilitou, najmä pri veľkých veľkostiach blokov, čím môže dôjsť k strate ortogonality medzi bázovými funkciami a tým k vytváraniu neortogonálnej bázy.

1. Úvod

Jedným zo základných nástrojov kompresie dát pri kódovaní videa je transformácia obrazu pomocou diskrétnej kosínusovej transformácie (DCT), ktorá sa používa v medzinárodných štandardov ako MPEG 1, MPEG 2, MPEG-4, H.261 a H.263 [1 – 3]. Klasická DCT používaná v štandardných videkodekoch prináša so sebou aj niekoľko nevýhod. Jednou z nich je zhoršená reprodukcia obrysu vizuálneho objektu. Kódovanie obrazu však využíva veľké množstvo transformačných algoritmov kódovania. Medzi tieto patria aj blokovo-orientované alebo oblastne-orientované obrazové kódovanie. Princíp blokovo-orientovaného kodéra (JPEG, H.261, MPEG) spočíva v rozčlenení obrazu do pravouhlých blokov obrazových prvkov (op) a kódovanie každého bloku osobitne ([7], [8], [9]), čo však môže spôsobiť zviditeľnenie hraníc blokov v rekonštruovanom obraze, nazývané tiež blokový efekt (zvlášť pri nízkych bitových rýchlostiach).

Väčšina týchto algoritmov nevyžíva interblokovú koreláciu, čo je ich nevýhodou. V oblastne-orientovanom obrazovom kódovaní [5], [6], [11] sú samostatne kódované hranice segmentov v jednotlivých blokoch. Vzhľadom na potrebu prenášať tvar segmentu [19] nemusí byť oblastne-orientovaný kodér nevyhnutne účinnejší ako tradičný blokovo-orientovaný kodér. Ale v prípade výkonnej reprezentačnej schémy segmentu (t.j. jeho tvaru aj obsahu) je možné dosiahnuť ďalšiu kompresiu údajov a lepšiu kvalitu obrazu pri transformačnom kódovaní [12], [13]. Bloková schéma takého systému transformačného kódovania obrazu je na obr. 1. Zhoršená reprodukcia segmentov vizuálnych objektov je jednou z nevýhod pri použití klasickej DCT [10], [4]. Algoritmus DCT s ortogonalizáciou jej bázových funkcií pre dané segmenty pomocou Gram- Schmidtovej [15, 16] alebo Householderovej metódy [4] umožňuje lepšiu reprodukciu obrazových segmentov.

Obr. 1. Bloková schéma princípu účinného transformačného kódovania obrazových segmentov.

2. Householderov algoritmu ortogonalizácie bázových funkcií DCT

Algoritmus DCT na skvalitnenie reprodukcie obrazových segmentov pri jeho spätnej transformácii je založený na poznaní binárneho tvaru vizuálneho objektu [17]. Na obr. 2 je zobrazený binárny tvar vizuálneho objektu daného vstupného obrazu, výber jedného z jeho blokov so segmentom a usporiadanie hodnôt op segmentu do vektora podľa tvaru tohto segmentu v danom bloku.

Obr. 2. a), c) Vstupný obraz a výber bloku so segmentom; b), d) výber bloku so segmentom z binárneho tvaru vizuálneho objektu; e) usporiadanie hodnôt op segmentu do vektora podľa tvaru segmentu v bloku.

Podľa toho, koľko je a ako sú rozložené op v segmente daného bloku, je možné vytvárať nové bázové funkcie DCT. Podľa tvaru segmentu sa z bázových ortogonálnych funkcií klasickej DCT vyberú iba tie hodnoty, ktoré sú na tých istých pozíciách ako op segmentu v bloku. Vyberajú sa po riadkoch od ľavého okraja segmentu po pravý okraj, zhora dole a usporiadajú sa do vektorov, ako je znázornené na obr. 2e. Takto získaný vektor je vlastne nová bázová funkcia, pričom sa vytvorí len toľko bázových funkcií, koľko je op v segmente. Tieto bázové funkcie však nie sú ortogonálne, preto sa musia ortogonalizovať. Tým, že je známy tvar segmentu op v bloku, tak vieme pre ich rôzne tvary vytvárať im zodpovedajúce systémy ortogonálnych bázových funkcií. Potom pomocou nich možno vykonať DCT obrazových segmentov v daných blokov.

Vo všeobecnosti platí, že ak skalárny súčin dvoch funkcií b = b(x_i,y_i) a d = d(x_i,y_i) je rovný nule (t.j. < b, d > = 0), tak funkcie nazývame ortogonálne. Aby sme získali vlastnosť ortogonality s ohľadom na tvar segmentu, musíme použiť do funkcií súradnice iba tých dvojíc (x_i,y_j) op, ktoré sa nachádzajú vo vnútri segmentu. Iná možnosť je tá, že použijeme váhovú funkciu v(x_i,y_j), ktorá je mimo segmentu rovná nule a vo vnútri jednej (obr.3 vpravo)

(1)

Je zrejmé, že nové funkcie (vektory) vytvorené z pôvodnej ortogonálnej bázy DCT hodnotami op nachádzajúcimi sa na pozíciách určených tvarom segmentu nemôžu byť ortogonálne, keď zoberieme do úvahy viaceré rôzne tvary týchto segmentov v obraze. Segmenty sa odlišujú nielen svojím tvarom, ale aj počtom op, ktoré obsahujú. Preto je nevyhnuté nájsť špecifické ortogonálne bázové funkcie pre každý jeden odlišný segment. Ortogonalizáciu bázových funkcií vykonáme Householderovym algoritmom, na ktorý sme sa bližšie zamerali. Na obr.3 vľavo je ukážka matice segmentu vybraného bloku s reálnymi hodnotami jeho op, vpravo je jej váhovaná verzia (binárne hodnoty op) a dole je systém bázových dvojrozmerných kosínusových funkcií vzhľadom na daný tvar segmentu.

Obr.3 Vľavo – ukážka matice reálneho obrazového segmentu doplnená nulovými hodnotami všade tam, kde sú op mimo segment; vpravo – matica jeho váhovanej verzie (binárna reprezentácia obrazového segmentu); dole – bázové obrazy vzhľadom na daný tvar segmentu [18].

Vo všeobecnosti uvažujme maticu R (horná trojuholníková matica pozostávajúca z ortogonálnych koeficientov) a maticu U o rozmere n x n pozostávajúcu z n lineárne nezávislých bázových funkcií u_k, každá je daná n – bodmi odobranými z pôvodnej ortogonálnej bázy DCT na miestach zodpovedajúcim tvaru segmentu ([14], [15]). Householderov algoritmus používa nasledujúcu spôsob ortogonalizácie, pri ktorom musí platiť, že PU=R. Chceme, aby matica P o rozmere n x n pozostávala z ortogonálnych bázových funkcií (zohľadňujúcich tvar segmentu). Táto matica sa nazýva Householderovou maticou. Začneme najprv s Householderovou maticou P₁ s rozmerom n x n, pre ktorú platí [4]

(2)

s jednotkovou maticou E a normovaným stĺpcovým vektorom w (w^Tw=1). P₁ je symetrická a ortogonálna matica, ako to vidno z týchto nasledujúcich dvoch rovníc

(3)

(4)

Pre špeciálny vektor w, ktorého odvodenie ukážeme neskôr, dostaneme maticu P₁, ktorá umiestňuje prvý stĺpec matice U do stĺpcového vektora len s jedným nenulovým prvkom na prvej pozícii. Pre prvý stĺpec matice U t.j. vektor x a prvý stĺpec jednotkovej matice E t.j vektor e₁ môžeme napísať

(5)

pričom a má opačné znamienko ako i-tá zložka vektora x, kde x_i je prvá súradnica vektora x a vektor e₁=(1,0,0,…,0)^T. Aplikovaním P₁ na U⁽⁰⁾ = U dostaneme novú maticu U⁽¹⁾

(6)

Prvý riadok tejto matice U⁽¹⁾ je aj prvým riadkom požadovanej matice R a prvý stĺpec obsahuje nuly pod prvým prvkom. Teraz zostrojíme maticu P‘₂, ktorá je menšia o jeden riadok (o prvý) a jeden stĺpec (prvý) oproti P₁, to znamená, že má veľkosť (n-1) x (n-1). Táto matica sa použije v rov.(5) namiesto P₁ spolu s vektorom x, ktorý obsahuje teraz (n-1) prvkov druhého stĺpca matice U⁽¹⁾, t.j.

(7)

Nakoniec maticu P‘₂ prispôsobíme pomocou jednotkovej matici tak, aby sme získali maticu P₂ požadovaného rozmeru n x n

(8)

Jej súčinom s maticou U⁽¹⁾ získame maticu U⁽²⁾, ktorej teraz už prvé dva riadky sú identické s riadkami hľadanej matice R

(9)

Po (n-1) krokoch dostaneme maticu U^(n-1), ktorá je identická s požadovanou maticou R

(10)

Všetky matice P_k sú ortogonálne, preto súčin matíc P je tiež ortogonálny, pričom

a tiež platí

(11)

Pre maticu U môžeme napísať, že U=P^TR.Ďalej musíme vybrať taký vektor w, ktorý vyhovuje rovnici ke₁ = P‘_kx. Tento vektor je daný vzťahom [4]

(12)

Householderov algoritmus ortogonalizácie vypočíta všetky ortogonálne bázové funkcie naraz, kým Gram-Schmidtov algoritmus [14] počíta s postupnou ortgonalizáciou jednoduchých bázových funkcií. Householderov algoritmus je matematicky lepšie predložený v tom, že všetky výpočty sú uskutočnené prostredníctvom ortogonálnych matíc. Na druhej strane, ak lineárne nezávislé funkcie vstupujú do Schmidtového algoritmu, môže sa stať, že výsledné funkcie nie sú ortogonálne, čo je spôsobené akumuláciou chýb v procese zaokrúhľovania [16]. Hoci oba algoritmy sú celkom rozdielne, dávajú tie isté ortogonálne funkcie, ak zanedbáme vplyv zaokrúhľovacích chýb a škálovacieho faktora. Householderov algoritmus dáva ortogonálne bázové funkcie v riadkoch na rozdiel od Schmidtovho algoritmu, ktorý dáva ortogonálne bázové funkcie po stĺpcoch, pričom bázové funkcie u Householderovho algoritmu sú dokonca ortonormálne. Pri Schmidtovej metóde sa ortogonálne bázové funkcie musia ešte normalizovať [14], [15].

3. Simulačné výsledky

Ortogonalizáciu zovšeobecnenej DCT vzhľadom na ľubovoľný tvar segmentu sme vykonali pomocou Householderovho algoritmu. Segmenty sa odlišovali svojim tvarom a počtom op, ktoré obsahovali.

3.1 Pre syntetizovaný segment

Uvažujme segment zvoleného tvaru reprezentovaný maticou X o rozmere 4×4

(13)

V ďalšom si názorne ukážeme, ako sa budú z ortogonálnej bázy 2-rozmernej DCT vyberať funkcie podľa daného tvaru hore uvedeného segmentu, ktoré sa potom budú ortogonalizovať Householderovym algoritmom. Z definičných vzťahov pre DCT vieme získať úplný systém 2-rozmerných diskrétnych ortogonálnych kosínusových funkcií, pričom vyjdeme z jadra 1-rozmernej DCT o veľkosti N = 4. To je uvedené v rov. (14), kde vo výslednej matici je v každom jej riadku možné vidieť hodnoty 1-romerných diskrétnych kosínusových funkcií.

(14)

Zo systému 1-rozmerných diskrétnych kosínusových funkcií získame pomocou ich vzájomných súčinov systém 2-rozmerných diskrétnych kosínusových funkcií veľkosti 4×4 tvoriacich jadro 2-rozmernej DCT. Na obr.4. je kvôli veľkosti zobrazená iba časť tohto 2-rozmerného systému ortogonálnych bázových funkcií DCT (úplný systém by v tomto prípade tvorilo 16 týchto 2-rozmerných funkcií). V prvom riadku a v prvom stĺpci sú uvedené prvé dve 1-rozmerné diskrétne kosínusové funkcie idúce za sebou (t.j funkcie z prvých dvoch riadkov matice z rov.14). V každom štvorci je tak možné vidieť 2-rozmerné diskrétne kosínusové funkcie, ktoré vznikli prenásobením hodnôt z prvého riadku a prvého stĺpca. Žltou farbou je vyznačený tvar segmentu (rov.13) v prvej 2-rozmernej bázovej funkcii (submatici) DCT a podľa tohto tvaru budeme vyberať iba tie hodnoty z bázových funkcií, ktoré sú na tých istých pozíciách ako op segmentu a ukladať ich do vektorov x.

Obr.4. Časť bázy 2-rozmerných ortogonálnych kosínusových funkcií s vyznačeným tvarom daného segmentu.

Daný segment má 10 prvkov, preto vyberieme iba 10 hľadaných funkcií z 10-tich submatíc 2-rozmernej DCT z celkového počtu 16. Načítavame po riadkoch, zhora dole a ukladáme do vektorov. Takto sme získali bázu 10 kosínusových funkcií (vektorov) podľa tvaru segmentu (x₀, x₁, … ,x₉), ktorá však nie je ortogonálna. Na jej ortogonalizáciu použijeme Householderov algoritmus uvedený v predchádzajúcej kapitole.

Po ortogonalizácii Householderovym algoritmom dostaneme maticu P ortogonálnych kosínusových bázových funkcií (ortogonálne bázové funkcie sú v riadkoch matice P a po jej transponovaní dostaneme ortogonálne bázové funkcie v stĺpcoch). Platí

(15)

t.j. (10×1)-1, pričom

Získané ortogonálne bázové funkcie musia spĺňať podmienky ortogonality a ortonormality, t.j. všeobecne

a

(17)

pričom v Tab.1 sú uvedené dosiahnuté výsledky testu ortonormality pre hore uvedené bázové funkcie.

Tab.1 Test ortogonality a ortonormality nájdených bázových funkcií Householderovým algoritmom

Vlastnosť ortogonality bázových funkcií dáva možnosť použiť ich pri výpočte priamej a spätnej zovšeobecnenej DCT pre daný vstupný segment (matica X) podľa nasledujúcich transformačných vzťahov (vo vektorovom tvare)

(18)

(19)

kde P je transformačná ortogonálna matica t.j. platí P^TP=E

(20)

(21)

Matica spektrálnych koeficientov

(22)

a matica rekonštruovaného obrazu

(23)

Stredná kvadratická odchýlka dosiahla hodnotu

(24)

, kde M=10. Z výslednej hodnoty strednej kvadratickej chyby je zrejmé, že vstupný segment a rekonštruovaný segment môžeme považovať za totožný, čo znamená, že vypočítané ortogonálne bázové funkcie Householderovým algoritmom sú správne vypočítané.

3.2 Pre reálne obrazové segmenty

Navrhnutý program na simuláciu zovšeobecnenej DCT umožňuje načítať jednu alebo viacero šedotónových snímok, ďalej ortogonalizáciu je možné realizovať dvoma spôsobmi: 1) s určovaním okna segmentu a 2) s vyhľadaním hraničných blokov, pričom sa ortogonalizácia vykonáva vždy na aktívnej snímke. Pri 1) type ortogonalizácie program čaká na výber okna zo segmentu na aktívnej snímke a po zadaní veľkosti okna (môže byť veľkosti 4×4, 8×8, 16×16) nastáva proces ortogonalizácie Householderovym algoritmom. Pri 2) type ortogonalizácie sa najskôr nastavuje veľkosť hraničných blokov a potom je potrebné nastaviť ďalší parameter a to transparentnosť, čo znamená udať počet nulových op v hraničnom bloku.

Po nastavení transparentnosti si môžeme vybrať, či budeme robiť ortogonalizáciu hraničných blokov alebo selekciu. Po zvolení „ortogonalizácie“ sa vykoná ortogonalizácia Householderovym algoritmom pre nastavené hraničné bloky a po skončení procesu môže nasledovať transformácia alebo filtrácia, ako v predchádzajúcom bode. Po zvolení „selekcie“ sa na obrazovke zobrazí dialóg, v ktorom si vyberieme, či budeme zobrazovať hraničné bloky alebo vnútorné bloky segmentu. Položka v programe “transformácia” je aktuálna až po skončení ortogonalizácie. “Filtrácia” je aktuálna po priamej transformácii, pričom si môžeme zvoliť buď prahovú alebo zonálnu filtráciu [7].

Pre ilustráciu uvádzame dosiahnuté výsledky pre reprezentačný segment (obr.5 vľavo). Pre tento reálny segment sme robili ortogonalizáciu pomocou Householderovho algoritmu. Počet obrazových prvkov tohto segmentu je 115 a veľkosť okna, v ktorom sa daný segment nachádza je 16×32. Po vykonaní ortogonalizácie sme transformovali tento reálny segment priamou zovšeobecnenou DCT (obr.5 v strede). Správnosť výpočtu Householderovým algoritmom sme overili spätnou transformáciou (obr.5 vpravo). Segment po spätnej zovšeobecnenej DCT je rovnaký ako originálny segment vstupujúci do výpočtu, čo sa potvrdilo aj dosiahnutou nulovou strednou kvadratickou chybou rekonštruovaného segmentu.

Obr.5 Vľavo reálny segment, v strede segment po priamej zovšeobecnenej DCT s vykonanou Householderovou ortogonalizáciou, vpravo segment po spätnej zovšeobecnenej DCT.

Niekedy je však potrebné ortogonalizovať iba hraničné bloky segmentu napr. vtedy, ak máme veľký segment (napr. snímka typu hlava-plecia), kde sa netransparentné bloky vo vnútri segmentu transformujú pomocou klasickej DCT [14] a polotransparentné bloky sa ortogonalizujú pomocou uvedeného Householderovho algoritmu.

4. Záver

V článku bola vykonaná zovšeobecnená diskrétna kosínusová transformácia vzhľadom na ľubovoľný tvar segmentu s použitím kosínusových bázových funkcií. Ortogonalizácia daných bázových funkcií pre zvolený tvar segmentu bola uskutočnená pomocou Householderovho algoritmu. Navrhnutý simulačný program umožňuje realizovať zovšeobecnenú DCT pre zadané vstupné segmenty. Householderov algoritmus ortogonalizácie je veľmi presný, stredná kvadratická chyba vychádzala pre jednotlivé ľubovoľné testované obrazové segmenty nulová, rádovo na 10-19. Táto metóda sa javí vhodnejšia na spracovanie vizuálneho objektu a pri kompresií údajov vykazuje menšiu chybu pri spätnej transformácií v porovnaní so Schmidtovym algoritmom ortogonalizácie. Jej nevýhoda spočíva v dlhšom trvaní výpočtu ortogonalizácie a z toho vyplývajúce vysoké nároky na procesor a pamäť počítača. Získané poznatky je možné použiť v oblasti transformačného kódovanie obrazov, ktoré používa oblastne-orientovanú obrazovú segmentáciu.

Literatúra

1. Mihalík, J., Štandardný videokodek MPEG-4. Slaboproudý obzor, 2003, roč. 60, č.2, s.7-11.
2. Mihalík, J., Štandardný videokodek H.263 a jeho porovnanie s H.261. Slaboproudý obzor, 2003, roč. 60, č.1, s.1-7.
3. MPEG Requirements Group. MPEG-4 requirements. ISO/IEC JTC1/SC29/WG11 N1595, Sevilla MPEG meeting, February 1997
4. Gilge, M. – Engelhardt, T.– Mehlan, R., Coding of arbitrarily shaped image segments based on a generalized orthogonal transform. Signal Processing: Image Communication.,vol 1, no.2, 1989, pp.153-180.
5. Gilge, M., Region-oriented transform coding (ROTC) of images. ICASSP, Conference: Acoustics, Speech, and Signal Processing, 1990.
6. Correia, P. – Pereira, F., Video Analysis for Coding: Objectives, Features and Methods, April 1997.
7. Mihalík, J., Kódovanie obrazu vo videokomunikáciách. TU-FEI Košice, 2001.
8. Mihalík, J., Štandardný videokodek H.264/AVC, Slaboproudý obzor, roč. 67, č.4, 2011, str.4-10.
9. Fauzi, M.F.A. – Lewis, P.H., Block-based Against Segmentation-based Texture Image Retrieval. Journal of Universal Computer Science, vol. 16, no. 3 (2010), 402-423.
10. Seyedin, S.A. – Fauzi, M.F.A. – Anuar, F.M., 1-D DCT Shape Faeture for Image Retrieval. IEEE Int. Conf. on Signal and Image Processing Applications, 2009.
11. Březina, A. – Polec, J. – Pavlovičová, J. – Kolingerová, I. – Bandzi, P., Region-based texture coding at very low bitrates. Journal of Electrical Engineering, vol. 56, no. 1-2, 2005, 36–40.
12. Kaup, A. – Aach, T., Coding of Segmented Images Using Shape-Independent Basis Functions, IEEE Transactions on Image Processing, no. 7 (1998), 937–947.
13. Eden, M. – Kocher, M., On the Performance of a Contour Coding Algorithm in the Context of Image Coding. Part I: Contour Segment Coding, Signal Processing 8 (1995), 381–386.
14. Gladišová, I. – Mihalík, J., DCT vizuálneho objektu pomocou ortogonalizácie jej bázových funkcií v oblastiach hraničných blokov. Electrical Engineering and Informatics 3, Proceeding of the Faculty of Electrical Engineering and Informatics of the Technical University of Košice, 2012, s. 310-314.
15. Persson P., Lecture 5: Gram-Schmidtov Orthogonalization. [Online]:
    http://persson.berkeley.edu/18.335/lec5handout6pp.pdf
16. Giraud, L. – Langou, J. – Rozlonik, M., The Loss of Orthogonality in the Gram-Schmidt Orthogonalization Process. Int. Journal of Computers and Mathematics with Applications, Vol.50, 2005, pp.1069-1075.
17. Gladišová, I., Mihalík, J., Zavacký, J., Obrysová reprezentácia a kódovanie binárneho tvaru videoobjektu. Slaboproudý obzor, 2010, roč. 66, č.3, s.14-18.
18. Liu, Jin-Zuo – Ding, Jian-Jiun, Image Compression, [Online]:
    http://disp.ee.ntu.edu.tw/meeting/俊佐/imagecompression.ppt
19. Gladišová, I. – Mihalík, J. – Petráš, J., Vnútrosnímková segmentácia obrazu. In: Posterus.sk., portál pre odborné publikovanie, roč. 8, č. 2 (2015), s. 1-18.

---

Spoluautormi článku sú Ján Mihalík a Miroslav Tóth, Laboratórium číslicového spracovania obrazov a videokomunikácií, Katedra elektroniky a multimediálnych telekomunikácií, Fakulta elektrotechniky a informatiky, Technická univerzita v Košiciach.