SPIHT

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

SPIHT[1] (Set Partitioning in Hierarchical Trees) je kvantovací algoritmus navržený pro aplikaci na koeficienty vzniklé pyramidovým rozkladem vlnkovou transformací. 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 komprimovaných signálů mají při vhodně zvolené vlnkové transformaci příznivý charakter. Lze na nich pak 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[editovat | editovat zdroj]

Strom vlnkových koeficientů.

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ů 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žší. Vyjma DC koeficientu má každý prvek s indexem i své dva přímé potomky na indexech 2i2i+1. Situaci znázorňuje obrázek níže.

Vector of wavelet coefficients.svg

U transformace obrazu (tedy dvourozměrného signálu) je situace obdobná. Koeficienty zde nereprezentuje vektor ale matice (dvourozměrné pole). Kořen stromu (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)(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.

Matrix of wavelet coefficients.svg

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 včetně DC koeficientu. Tato množina se značí \mathcal{H} (highest pyramid level). Pro dvourozměrnou variantu stromu bude tedy obsahovat indexy (0,0), (0,1), (1,0) a (1,1).

Druhou je množina indexů přímých potomků uzlu. Značí se jako \mathcal{O} (offspring) 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)\}. 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} (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 \mathcal{L} a spadají sem všichni následníci uzlu vyjma jeho přímých potomků. 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ů. 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 : & 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 \{(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[editovat | editovat zdroj]

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 \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 (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 := \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é. 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}| < 2^{n+1}. 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[editovat | editovat zdroj]

Existuje množství modifikací tohoto algoritmu. Častou úpravou 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í).

Reference[editovat | editovat zdroj]

  1. a b Said, A.; Pearlman, W. A.: A New Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees. IEEE Transactions on Circuits and Systems for Video Technology, ročník 6, č. 3, June 1996: s. 243–250, doi:10.1109/76.499834. URL http://www.cipr.rpi.edu/research/SPIHT/EW_Code/csvt96_sp.pdf

Externí odkazy[editovat | editovat zdroj]