Cesko.wiki SPIHT
Author
Albert FloresSPIHT je kvantovací algoritmus navržený pro aplikaci na koeficienty vzniklé pyramidovým rozkladem vlnkovou transformací. V roce 1996 jej publikovali výzkumníci Amir Said a William A. Pearlman. SPIHT vychází z algoritmu EZW , který dále zdokonaluje.
Z praktičtějšího úhlu pohledu se jedná o algoritmus, který progresivně ukládá vlnkové koeficienty do toku bitů. Při dekódování tohoto toku se koeficienty postupně zpřesňují. +more Jeho práci lze tedy kdykoli přerušit a kvalita uložených koeficientů odpovídá doposud vyprodukovanému výstupu.
Algoritmus při svém postupu zohledňuje spojitost mezi koeficienty na různých úrovních rozkladu. Rozložený signál je na každé úrovni reprezentován dvojnásobným množstvím koeficientů v každém rozměru než na úrovni předchozí (směrem od kořene k listům). +more Vlnkové koeficienty jsou mezi sousedními měřítky (rozlišeními) silně korelovány. Lze na nich vypozorovat, že hodnota každého koeficientu bude s velkou pravděpodobností menší než hodnota jeho předchůdce. Tohoto faktu využíval již algoritmus EZW. SPIHT je sice implementačně náročnější, při stejné kvalitě však dosahuje kratšího výstupního toku bitů. Existují i různé modifikace tohoto algoritmu.
Prostorové stromy
Strom vlnkových koeficientů. +more Algoritmus SPIHT pracuje s tzv. prostorovými stromy . Jedná se o datovou strukturu reprezentující vlnkové koeficienty. Strom začíná kořenem. V případě jednorozměrného signálu má každý uzel dva následníky. U dvourozměrného obrazu bude mít každý uzel následníky čtyři. Listy reprezentují nejvyšší frekvence.
Příklad Vlnkovou transformací jednorozměrného diskrétního signálu o osmi vzorcích vznikne strom koeficientů c, kde c_0 je stejnosměrná složka a c_i s 1 ≤ c_i ≤ 7 jsou výstupy horních propustí (dále jen AC koeficienty, indexy 4-7 značí nejvyšší frekvence). Vyjma stejnosměrné složky lze koeficienty reprezentovat stromem jako na obrázku vpravo.
V případě jednorozměrného signálu lze prostorový strom reprezentovat jako jediný vektor (tedy jednorozměrné pole koeficientů). Vektor začíná DC koeficientem (prvek s indexem 0) a následují koeficienty postupně od nejvyšší úrovně rozkladu po nejnižší. +more Vyjma DC koeficientu má každý prvek s indexem i své dva přímé potomky na indexech 2i až 2i+1. Koeficient s indexem 1 tvoří kořen stromu. Situaci znázorňuje obrázek níže.
U transformace obrazu (tedy dvourozměrného signálu) je situace obdobná. Koeficienty zde nereprezentuje vektor ale matice (dvourozměrné pole). +more DC koeficient je prvek s indexy (0,0). Vyjma něj má každý prvek s indexy (i,j) své čtyři přímé potomky na souřadnicích (2i,2j) až (2i+1,2j+1), tedy (2i,2j), (2i+1,2j), (2i,2j+1) a (2i+1,2j+1). Situaci znázorňuje obrázek níže. Tato struktura odráží vztahy mezi vlnkovými koeficienty, které vznikly pyramidovým rozkladem.
Obdobná situace nastane i u vícerozměrných signálů. Pro popis algoritmu SPIHT je ještě podstatné stanovit nad prostorovými stromy jednu operaci, resp. +more definovat několik množin.
První z nich je množina indexů (souřadnic) kořenů. Spadají sem koeficienty z nejvyšší úrovně rozkladu, případně též DC koeficient. +more Tato množina se značí \mathcal{H} . Pro dvourozměrnou variantu stromu bude tedy obsahovat indexy (0,1), (1,0), (1,1), případně (0,0).
Druhou je množina indexů přímých potomků uzlu. Značí se jako \mathcal{O} a pro dvourozměrnou variantu stromu může být definována jako \mathcal{O}(i,j) = \{(2i,2j), (2i+1,2j), (2i,2j+1), (2i+1,2j+1)\}. +more Pořadí není podstatné, ale musí být vždy stejné.
Třetí je množina indexů všech následníků uzlu (tedy i těch nepřímých). Označuje se jako \mathcal{D} . +more Do této množiny tedy patří všichni přímí potomci, všichni přímí potomci přímých potomků a tak dál až k listům stromu.
Další množinou je množina indexů všech nepřímých následníku uzlu. Označuje se \mathcal{L} a spadají sem všichni následníci uzlu vyjma jeho přímých potomků. +more Množina je definována jako \mathcal{L}(i,j) = \mathcal{D}(i,j) - \mathcal{O}(i,j).
K efektivní implementaci práce se stromy koeficientů lze využít Mortonův rozklad. Nyní je třeba definovat operaci významnosti na množině koeficientů. +more Množina je významná tehdy, pokud je významný alespoň jeden její prvek. V ostatních případech je nevýznamná. Operace významnosti se značí S_n(\mathcal{T}), kde \mathcal{T} je množina indexů. Definici lze zapsat jako následující rovnici. Ke zjednodušení zápisu jednoprvkových množin lze psát S_n(\{(i,j)\}) jako S_n(i,j).
: S_n(\mathcal{T}) = \left\{ \begin{array}{lr} 1 : & \max\limits_{(i,j)\in\mathcal{T}} \{|c_{i,j}|\} \ge 2^n \\ 0 : & \text{jinak} \end{array} \right.
Algoritmus SPIHT pracuje v jedné ze svých částí s dělením množin a používá přitom množiny právě definované. Dělení množin probíhá podle následujících dvou jednoduchých pravidel. +more Počáteční množina je tvořena množinami \{(i,j)\} a \mathcal{D}(i,j) pro všechna (i,j) \in \mathcal{H}. První pravidlo říká, že pokud je množina všech následníků \mathcal{D}(i,j) významná, je rozdělena na \mathcal{L}(i,j) a čtyři samostatné prvky (k,l) \in \mathcal{O}(i,j). Druhé pravidlo říká, že jestliže je významná množina \mathcal{L}(i,j), je tato rozdělena na čtyři množiny \mathcal{D}(k,l) s (k,l) \in \mathcal{O}(i,j).
Vlastní algoritmus
Vlastní algoritmus pracuje se třemi seznamy. První seznam se značí LIS , tedy seznam nevýznamných množin. +more Druhý se značí LIP a obsahuje seznam nevýznamných koeficientů. Třetím je seznam LSP a obsahuje seznam významných koeficientů. Seznamy LIP a LSP reprezentují jednotlivé koeficienty. Seznam LIS reprezentuje buď množinu \mathcal{D}(i,j) nebo \mathcal{L}(i,j). Prvky tohoto seznamu jsou tedy dvojího typu. K jejich rozlišení je ve zmíněné práci použito následující značení - typ A reprezentuje \mathcal{D}(i,j) a typ B reprezentuje \mathcal{L}(i,j).
Algoritmus pracuje iterativně a vlastní jádro sestává ze tří částí. První je průchod množinou LIP, následuje průchod množinou LIS - tyto kroky se nazývají srovnávací průchod . +more Třetí částí je průchod množinou LSP - tento krok se nazývá upřesňovací průchod ('). Při srovnávacím průchodu jsou koeficienty v LIP testovány na významnost a případně přesunuty do LSP. Obdobně jsou na významnost testovány množiny v LIS a podle uvedených pravidel případně rozděleny. Nově vzniklé množiny jsou umístěny zpět do LIS. Dělením vzniklé samostatné koeficienty jsou podle významnosti umístěny buďto do LIP nebo LSP. Jako následující algoritmus je uvedena původní varianta.
(Inicializace) n := ⌊log2(MAX)⌋; LSP := ϕ; LIP := \mathcal{H}; LIS := pouze ty prvky z \mathcal{H}, které mají přímé potomky, jako prvky typu A;
(Srovnávací průchod) for each (i,j) ∈ LIP do odešli S_n(i,j)\,; if S_n(i,j)\, = 1 then přesuň (i,j) do LSP a odešli znaménko c_{i,j}\,; end if end for for each (i,j) ∈ LIS do (Zpracování prvku typu A) if prvek je typu A then odešli S_n(\mathcal{D}(i,j))\,; if S_n(\mathcal{D}(i,j))\, = 1 then for each (k,l) ∈ \mathcal{O}(i,j) do odešli S_n(k,l)\,; if S_n(k,l)\, = 1 then přidej (k,l) do LSP a odešli znaménko c_{k,l}\,; end if if S_n(k,l)\, = 0 then přidej (k,l) na konec LIP; end if end for if \mathcal{L}(i,j) ≠ ϕ then přesuň (i,j) na konec LIS jako prvek typu B; go to (Zpracování prvku typu B); else odeber z LIS prvek (i,j); end if end if end if (Zpracování prvku typu B) if prvek je typu B then odešli S_n(\mathcal{L}(i,j))\,; if S_n(\mathcal{L}(i,j))\, = 1 then přidej každý (k,l) ∈ \mathcal{O}(i,j) na konec LIS jako prvek typu A; odeber (i,j) z LIS; end if end if end for
(Upřesňovací průchod) for each (i,j) ∈ LSP vyjma těch prvků přidaných v posledním srovnávacím průchodu do odešli n-tý nejvýznamnější bit |c_{i,j}|\,; end for
(Další krok) n := n-1; go to (Srovnávací průchod);
Algoritmus pro dekódování vytvořeného bitového toku pracuje zcela shodně jako uvedený algoritmus pro kódování s tím rozdílem, že je slovo „odešli“ nahrazeno slovem „načti“. Seznamy LIS, LIP a LSP u kodéru a dekodéru musejí být tedy v každém okamžiku stejné. +more Dekodér postupně upřesňuje hodnoty vlnkových koeficientů. Když je koeficient přesunut do LSP, dekodér ví, že je jeho hodnota 2^n \le |c_{i,j}| . Dekodér tedy použije tuto informaci spolu s příchozí informací o znaménku a nastaví rekonstruovaný koeficient \hat{c}_{i,j} = \pm 1{,}5 \times 2^n. Podobně v průběhu upřesňovacího průchodu přičte nebo odečte dekodér od \hat{c}_{i,j} hodnotu 2^{n-1}. Nastavuje tedy odhadovanou hodnotu koeficientů do poloviny možného intervalu - je to klíčová výhoda algoritmu SPIHT.
Modifikace
Existuje množství modifikací tohoto algoritmu. Jednou z možných úprav je předsunutí upřesňovacího průchodu před srovnávací. +more Tím se sníží výpočetní náročnost, protože se odbourá potřeba sledovat nově přidané prvky seznamu LSP. Jestliže jsou dále prvky seznamů procházeny vždy v pevném pořadí od kořene k poslednímu listu, zmizí skok ze zpracování uzlu typu A do zpracování uzlu typu B (v podstatě příkaz goto). LIS, LSP a LIP již pak vlastně nejsou seznamy, nýbrž množiny (které se procházejí vždy ve stejném pořadí).
Reference
Externí odkazy
[url=https://web.archive.org/web/20090714121704/http://www.cipr.rpi.edu/research/SPIHT/]domácí stránka algoritmu[/url]