Skalárne kvantovanie obrazu

Skalárne kvantovanie delíme na:

• Optimálne lineárne skalárne kvantovanie
• Optimálne nelineárne skalárne kvantovanie
• Suboptimálne skalárne kvantovanie

O optimálnom kvantovaní hovoríme vtedy, ak rozhodovacie a kvantizačné úrovne sú rozložené najlepšie ako je vzhľadom na obmedzujúce parametre možné. Suboptimálne kvantovanie nemusí byť pre daný vstupný signál/obraz najvhodnejšie, ale vzhľadom na požiadavky je prijateľné.

Kvantovanie je ireverzibilný t. z. nevratný proces. Kvantovaním vždy dochádza k strate informácie. Čim je menšia množina kvantizačných hodnôt, tým je táto informačná strata väčšia. Z matematického hľadiska sa skalárnym kvantovaním transformuje postupnosť náhodných premenných  na postupnosť diskrétnych náhodných premenných . Vyššie spomínanú chybu budeme nazývať kvantizačný šum, ktorý je daný ako rozdiel medzi vstupnou hodnotou vzorky a jej kvantovanou hodnotou.

Pre účely neskoršieho vyhodnocovania kvantizačného šumu nás bude zaujímať jeho výkon daný štatistickou strednou hodnotou, ktorý potom v pomere k strednej kvadratickej hodnote (disperzie) vstupných náhodných vzoriek predstavuje parameter odstup signálu od šumu.

Pre strednú hodnotu výkonu kvantizačného šumu platí:

Pre strednú hodnotu výkonu pôvodného signálu môžeme písať:

Nakoniec hodnota odstupu signálu od šumu S/Š alebo v anglosaskej literatúre SNR (Signal to Noise Ratio) daná v dB je definovaná takto:

Hodnotu kvantizačného šumu je možné ovplyvňovať troma spôsobmi:

1. Voľba počtu kvantizačných úrovní 

• Čím viac kvantizačných úrovní, tým bude kvantizačná úroveň bližšie k hodnote vstupnej vzorky.

2. Rozložením rozhodovacích a kvantizačných úrovní

• Niekedy je vhodnejšie, ak je kvantizačný krok pre rôzne úrovne iný. Vstupný signál sa pre rôzne úrovne môže chovať inak. Niekedy v istej oblasti je zmena hodnoty vzorky jemnejšia ako v inej. Vhodné rozloženie rozhodovacích a kvantizačných úrovni vo veľkej miere závisí aj od štatistických vlastností obrazu.

3. Využitím štatistických vlastnosti vstupnej premennej

Optimálne lineárne skalárne kvantovanie (OLSK)

Lineárny N-úrovňový kvantizátor má rozhodovacie a kvantizačné úrovne rozložené rovnomerne. Teda kvantizačný krok ∆ je rovnaký pre každú úroveň. Prevodová charakteristika N-úrovňového kvantizátora je zobrazená na nasledujúcom obr. 1. Lineárny skalárny kvantizátor môže mať začiatok rozhodovacej oblasti rozložený dvojako.

Obr. 1 Prevodové charakteristiky OLSK

Tieto dva rozloženia rozhodovacích a kvantizačných úrovní sa líšia v začiatku súradnicového systému. Prvý variant je využiteľný tam kde nie je potrebné uvažovať kvantizačnú úroveň s hodnotou 0. Pri tomto type kvantizátora kvantizačné úrovne sú posunuté od hodnoty 0 o ∆/2. Pri druhom variante sa uvažuje aj kvantizačná úroveň s hodnotou 0. Kvantizačné úrovne sú od začiatku súradnicového systému  rozložené rovnomerne s krokom ∆. Rozhodovacie úrovne sú posunuté o ∆/2.

Návrh OLSK

Pri návrhu OLSK je potrebné vychádzať zo štatistických vlastnosti vstupnej postupnosti. V zásade, keďže vstupný signál uvažujeme ako diskrétne hodnoty spojitého signálu symetricky rozdelené okolo nulovej strednej hodnoty, za hlavný štatistický parameter budeme uvažovať spojitú hustotu rozdelenia pravdepodobnosti f(x), pričom x sú možné hodnoty vstupnej postupnosti.   Z uvedeného je jasné, že OLSK spravidla navrhujeme pre kvantovanie špecifických signálov resp. obrazov. Optimálnosť kvantizátora logicky spočíva v minimalizácii strednej kvadratickej chyby resp. v minimalizácii kvantizačného šumu, o ktorom sme pojednávali vyššie. Problematiku kvantizačného šumu ešte rozvinieme. Kvantizačný šum OLSK ma dvojakú povahu, teda skladá sa z dvoch zložiek. Prvá zložka je takzvaný granulačný šum (q₁), ktorý vzniká ako rozdiel medzi vstupnou hodnotou vzorky a jej priradenej kvantizačnej hladiny (hodnoty). Tento šum sa uplatňuje pre všetky kvantizačné hladiny okrem poslednej. Podstata druhej zložky kvantizačného šumu je tvorená rozdielom vzorky a jej priradenej maximálnej kvantizačnej hodnoty. To si je možné predstaviť tak, že ak máme kvantizátor, ktorý priradzuje kvantizačné hodnoty od -5V do 5V a tieto sú odstupňované s krokom 1V, tak ak na vstup privedieme vzorku s hodnotou 15V, tak sa jej priradí posledná kvantizačná hodnota 5V (pravdepodobnosť výskytu takejto vzorky je však veľmi malá).  V tomto prípade hovoríme o šume z preťaženia (q₂). Pre strednú kvadratickú hodnotu kvantizačného šumu môžeme písať (pre zjednodušenie budeme uvažovať 1. variant OLSK):

Pričom:

Z uvedených vzťahov je pre zadané N a známu f(x) možné usúdiť nasledovné:

• Hodnota jednotlivých stredných kvadratických chýb je závislá len od zvoleného kvantizačného kroku ∆
• Ak sa ∆ bude zväčšovať, granulačný šum bude narastať a šum z preťaženia sa bude znižovať.
• Optimálnosť teda bude spočívať v nájdení takej hodnoty kvantizačného kroku pri, ktorom je  kvadrát hodnoty σ_q minimálny.

Hodnotu optimálneho kvantizačného kroku je možné nájsť vyjadrením ∆ z nasledujúcej rovnice:

Analytický výpočet optimálneho kvantizačného kroku s ohľadom na minimalizáciu strednej kvadratickej chyby je pomerne zložitý a často je výhodnejšie použiť tabuľky resp. softvérové prostriedky.

Spravidla je možné uvažovať, že rozloženie pravdepodobnosti poznáme. Môžeme uvažovať napríklad Gaussove alebo Laplaceove rozdelenie pravdepodobnosti s nulovou strednou hodnotou. Vtedy je výhodné uvažovať normovanú strednú kvadratickú chybu šumu, t.z. stredná kvadratická hodnota šumu pre uvažované rozloženie je delená disperziou vstupného signálu.

Potom aj kvantizačný krok budeme uvažovať v jeho normovanej hodnote:

Toto má hlavnú výhodu v tom, že pre zvolené rozloženie pravdepodobnosti a zvolený počet kvantizačných úrovní je možné optimálny kvantizátor navrhnúť pomocou už existujúcich tabuliek. Tieto tabuľky udávajú hodnotu normovaného kvantizačného kroku pre dané rozloženie pravdepodobnosti. Hodnotu optimalného kvantizačného kroku pre uvažovaný signál je daná nasledovne:

Optimálne nelineárne skalárne kvantovanie (ONSK)

Nelineárny N-úrovňový kvantizátor nemá rozhodovacie a kvantizačné úrovne rozložené rovnomerne - nemenia s rovnakým krokom. Výhodou ONSK je, že v porovnaní s OLSK pre rovnaký počet kvantizačných úrovní dosahuje lepší pomer odstupu signálu od šumu. Prevodová charakteristika N-úrovňového kvantizátora je zobrazená na nasledujúcom obr.2.

Obr. 2 Prevodová charakteristika ONSK

Kvadratická hodnota kvantizačného šumu je daná ako:

kde a_i sú rozhodovacie úrovne a b_i sú kvantizačné úrovne. Krajné rozhodovacie úrovne a₁ a a_N+1 sú rovné nekonečnu. f(x) predstavuje rozloženie pravdepodobnosti jednotlivých kvantizačných úrovní. Pre zvolené f(x) je teda hodnota šumu závislá jedine od rozloženia rozhodovacích a kvantizačných úrovní. Z uvedeného vyplýva, že pre návrh je potrebné nájsť (určiť) hodnoty a_i a b_i. Optimálne rozloženie možno nájsť pomocou riešenia sústavy nelineárnych rovníc:

Táto sústava je často riešená iteračnou metódou tak, že sa zvolí prvá kvantizačná úroveň b₁ a aplikáciou predchádzajúcich rovníc sa určí rozhodovacia úroveň a_2. Z nej potom b₂ a takto sa pokračuje, až kým sa nedôjde k a_N a b_N, ktoré sú známe. Nasledujúcou nerovnicou sa overí, či zvolená hodnota b₁ bola vhodne určená.

Ak podmienka nerovnice nie je splnená, je potrebné zvoliť novú hodnotu b1  a proces zopakovať.

Metóda návrhu ONSK kompandovaním.

Princíp tejto metódy návrhu ONSK spočíva v prepočte rozhodovacích a kvantizačných úrovní OLSK cez nelineárnu kompresnú funkciu g(x). Bloková schéma ONSK s kompandovaním je na obr. 3

Obr. 3 Bloková schéma ONSK s kompandovaním

Z obr. 3 je zrejmé, že vstupné vzorky sú najprv prevedene kompresnou funkciou a až následne na to sú kvantované pomocou OLSK. Kvantizačná úroveň OLSK sa následne prevedie cez expanznú funkciu, čím sa získa kvantizačná úroveň ONSK pre vstupnú vzorku. Tento proces je zobrazený na obr. 4

Obr. 4 Proces transformácie OLSK na ONSK

Z obr. 4 je možné vidieť, že vzorka X_n bola cez kompresnú krivku prevedená na vertikálnu os odkiaľ bola prevodovou charakteristikou OLSK opäť prevedená na horizontálnu os, odkiaľ bola nakoniec cez expanznú krivku prevedená na finálnu kvantizačnú úroveň ONSK.

Optimálnosť ONSK je dosiahnutá voľbou optimálnej kompresnej charakteristiky. Túto je možné pre vstupný rozsah vzoriek z intervalu <V₁, V₂> vypočítať pomocou nasledovného vzťahu:

kde f(a) je hustota rozdelenia pravdepodobnosti. Ak sa na vzťah pozrieme bližšie zistíme, že po integrovaní menovateľ zlomku bude reálne číslo a čitateľ bude funkcia premennej x. Výpočet optimálnej krivky g(x) môže byť náročný a v praxi sa zvyknú používať normované logaritmické priebehy zobrazené na obr. 5.

Za predpokladu, že platí g(x) = V ak x = V, tieto priebehy sú definované vzťahom:

Obr. 5 Logaritmické kompresné funkcie

Na záver ešte uvedieme výpočet hodnoty kvantizačného šumu, pre ktorý platí vzťah:

Pričom g’(x) je deriváciou kompresnej funkcie g(x).

Suboptimálne skalárne kvantovanie

Hoci je možné zrátať resp. uvažovať štandardné štatistické parametre obrazu (napr. Gaussové alebo Laplassové rozloženie pravdepodobnosti) nakoniec aj tak každý obraz má štatistické parametre trochu iné. Nevýhodou optimálnych algoritmov je, že pre každý obraz je potrebné navrhnúť optimálny kvantizátor. Taký prístup je v spracovaní obrazov nepraktický. Preto sa častejšie stretávame s kvantovaním pomocou kvantizačných indexov. Tieto indexy sa vypočítajú pomocou zaokrúhlenia podielu hodnoty obrazového prvku a veľkosti kvantizačného krok.  To je možné zapísať nasledovne: 

kde Q_i,j je hodnota kvantizačného indexu a xi_,j je hodnota obrazového prvku. Na strane prijímača je potom možné získať kvantizačnú úroveň tak, že sa priajaté kvantizačné indexy prenásobia počtom úrovní. Veľkosť kroku je daná podielom hodnoty maximálnej kvantizačnej úrovne a počtu kvantizačných úrovní. 

Na obr. 6 je zobrazený obraz Lena, histogram a hodnota SNR pre N = 32, 16, 8, 4, 2

Pri obrazoch transformovaných pomocou niektorej z diskrétnych ortogonálnych transformácií (napr. DCT) je možné každý transformačný koeficient kvantovať rozdielnym krokom. Najznámejšie sú kvantizačné matice pre JPEG algoritmus. Kvantizačná matica pre blok 8x8 môže vyzerať nasledovne:

Je zrejmé, že čím je hodnota prvku matice vyššia tým je kvantovanie výraznejšie.