SPIHT

SPIHT (Set Partitioning in Hierarchical Trees) 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.^[1] SPIHT vychází z algoritmu EZW (Embedded Zerotree Wavelet), 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í. 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). 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

Algoritmus SPIHT pracuje s tzv. prostorovými stromy (spatial orientation trees). 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ů ${\displaystyle c}$, kde ${\displaystyle c_{0}}$ je stejnosměrná složka a ${\displaystyle c_{i}}$ s 1 ≤ ${\displaystyle 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žší. Vyjma DC koeficientu má každý prvek s indexem ${\displaystyle i}$ své dva přímé potomky na indexech ${\displaystyle 2i}$ až ${\displaystyle 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). DC koeficient je prvek s indexy ${\displaystyle (0,0)}$. Vyjma něj má každý prvek s indexy ${\displaystyle (i,j)}$ své čtyři přímé potomky na souřadnicích ${\displaystyle (2i,2j)}$ až ${\displaystyle (2i+1,2j+1)}$, tedy ${\displaystyle (2i,2j)}$, ${\displaystyle (2i+1,2j)}$, ${\displaystyle (2i,2j+1)}$ a ${\displaystyle (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. 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. Tato množina se značí ${\displaystyle {\mathcal {H}}}$ (highest pyramid level). Pro dvourozměrnou variantu stromu bude tedy obsahovat indexy ${\displaystyle (0,1)}$, ${\displaystyle (1,0)}$, ${\displaystyle (1,1)}$, případně ${\displaystyle (0,0)}$.

Druhou je množina indexů přímých potomků uzlu. Značí se jako ${\displaystyle {\mathcal {O}}}$ (offspring) a pro dvourozměrnou variantu stromu může být definována jako ${\displaystyle {\mathcal {O}}(i,j)=\{(2i,2j),(2i+1,2j),(2i,2j+1),(2i+1,2j+1)\}}$. 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 ${\displaystyle {\mathcal {D}}}$ (descendant). 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 ${\displaystyle {\mathcal {L}}}$ a spadají sem všichni následníci uzlu vyjma jeho přímých potomků. Množina je definována jako ${\displaystyle {\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ů. 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čí ${\displaystyle S_{n}({\mathcal {T}})}$, kde ${\displaystyle {\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 ${\displaystyle S_{n}(\{(i,j)\})}$ jako ${\displaystyle S_{n}(i,j)}$.

${\displaystyle S_{n}({\mathcal {T}})=\left\{{\begin{array}{lr}1:&\max \limits _{(i,j)\in {\mathcal {T}}}\{|c_{i,j}|\}\geq 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. Počáteční množina je tvořena množinami ${\displaystyle \{(i,j)\}}$ a ${\displaystyle {\mathcal {D}}(i,j)}$ pro všechna ${\displaystyle (i,j)\in {\mathcal {H}}}$. První pravidlo říká, že pokud je množina všech následníků ${\displaystyle {\mathcal {D}}(i,j)}$ významná, je rozdělena na ${\displaystyle {\mathcal {L}}(i,j)}$ a čtyři samostatné prvky ${\displaystyle (k,l)\in {\mathcal {O}}(i,j)}$. Druhé pravidlo říká, že jestliže je významná množina ${\displaystyle {\mathcal {L}}(i,j)}$, je tato rozdělena na čtyři množiny ${\displaystyle {\mathcal {D}}(k,l)}$ s ${\displaystyle (k,l)\in {\mathcal {O}}(i,j)}$.

Vlastní algoritmus

Vlastní algoritmus pracuje se třemi seznamy. První seznam se značí LIS (list of insignificant sets), tedy seznam nevýznamných množin. Druhý se značí LIP (list of insignificant pixels) a obsahuje seznam nevýznamných koeficientů. Třetím je seznam LSP (list of significant pixels) a obsahuje seznam významných koeficientů. Seznamy LIP a LSP reprezentují jednotlivé koeficienty. Seznam LIS reprezentuje buď množinu ${\displaystyle {\mathcal {D}}(i,j)}$ nebo ${\displaystyle {\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 ${\displaystyle {\mathcal {D}}(i,j)}$ a typ B reprezentuje ${\displaystyle {\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 (sorting pass). Třetí částí je průchod množinou LSP – tento krok se nazývá upřesňovací průchod (refinement pass). 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^[1].

(Inicializace)
n := ⌊log2(MAX)⌋;
LSP := ϕ;
LIP := ${\displaystyle {\mathcal {H}}}$;
LIS := pouze ty prvky z ${\displaystyle {\mathcal {H}}}$, které mají přímé potomky, jako prvky typu A;

(Srovnávací průchod)
for each ${\displaystyle (i,j)}$ ∈ LIP do
    odešli ${\displaystyle S_{n}(i,j)\,}$;
    if ${\displaystyle S_{n}(i,j)\,}$ = 1 then přesuň ${\displaystyle (i,j)}$ do LSP a odešli znaménko ${\displaystyle c_{i,j}\,}$; end if
end for
for each ${\displaystyle (i,j)}$ ∈ LIS do
    (Zpracování prvku typu A)
    if prvek je typu A then
        odešli ${\displaystyle S_{n}({\mathcal {D}}(i,j))\,}$;
        if ${\displaystyle S_{n}({\mathcal {D}}(i,j))\,}$ = 1 then
            for each ${\displaystyle (k,l)}$ ∈ ${\displaystyle {\mathcal {O}}(i,j)}$ do
                odešli ${\displaystyle S_{n}(k,l)\,}$;
                if ${\displaystyle S_{n}(k,l)\,}$ = 1 then přidej ${\displaystyle (k,l)}$ do LSP a odešli znaménko ${\displaystyle c_{k,l}\,}$; end if
                if ${\displaystyle S_{n}(k,l)\,}$ = 0 then přidej ${\displaystyle (k,l)}$ na konec LIP; end if
            end for
            if ${\displaystyle {\mathcal {L}}(i,j)}$ ≠ ϕ then
                přesuň ${\displaystyle (i,j)}$ na konec LIS jako prvek typu B;
                go to (Zpracování prvku typu B);
            else
                odeber z LIS prvek ${\displaystyle (i,j)}$;
            end if
        end if
    end if
    (Zpracování prvku typu B)
    if prvek je typu B then
        odešli ${\displaystyle S_{n}({\mathcal {L}}(i,j))\,}$;
        if ${\displaystyle S_{n}({\mathcal {L}}(i,j))\,}$ = 1 then
            přidej každý ${\displaystyle (k,l)}$ ∈ ${\displaystyle {\mathcal {O}}(i,j)}$ na konec LIS jako prvek typu A;
            odeber ${\displaystyle (i,j)}$ z LIS;
        end if
    end if
end for

(Upřesňovací průchod)
for each ${\displaystyle (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 ${\displaystyle |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é. Dekodér postupně upřesňuje hodnoty vlnkových koeficientů. Když je koeficient přesunut do LSP, dekodér ví, že je jeho hodnota ${\displaystyle 2^{n}\leq |c_{i,j}|<2^{n+1}}$. Dekodér tedy použije tuto informaci spolu s příchozí informací o znaménku a nastaví rekonstruovaný koeficient ${\displaystyle {\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 ${\displaystyle {\hat {c}}_{i,j}}$ hodnotu ${\displaystyle 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í. 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í).

Související články

• EZW – myšlenkový předchůdce algoritmu SPIHT
• SPECK – podobný algoritmus od W. A. Pearlmana
• EBCOT – algoritmus kódování DWT použitý ve standardu JPEG 2000

Reference

Externí odkazy

• (anglicky) domácí stránka algoritmu