Podręcznik

Ograniczenia efektywności bezstratnego JPEG doprowadziły do opracowania i przyjęcia w 1996 roku nowego standardu kompresji obrazów rodziny JPEG -- JPEG-LS (lossless and near lossless). 

Główne etapy bezstratnej/prawie bezstratnej kompresji obrazów według standardu JPEG-LS, tj. modelowanie kontekstu, predykcja, kodowanie błędu predykcji oraz alternatywny mod sekwencji podobnej (w szczególnym przypadku kompresji bezstratnej - identycznej), przedstawiono na rys. 1.8.

Rys. 1.8 Schemat blokowy kodera JPEG-LS.

Modelowanie kontekstu polega na w pierwszej kolejności na ustaleniu rozmiaru i kształtu najbliższego sąsiedztwa każdego z kodowanych pikseli. Na podstawie rozkładu wartości pikseli sąsiedztwa: a) wybierany jest tryb kodowania; b) obliczana jest przewidywana wartość piksela, c) konstruowany jest statystyczny model błędów predykcji (tj. różnicy pomiędzy wartością piksela i wartością przewidywaną). Lokalny kontekst z JPEG-LS pokazano na rys. 1.9. 

Rys. 1.9  Lokalny, przyczynowy kontekst wystąpienia kodowanego piksela $f$ w przestrzeni obrazu, wykorzystany w standardzie JPEG-LS do wyboru trybu kodowania, w nieliniowej predykcji oraz przy modelowaniu błędu predykcji na etapie binarnego kodowania; sąsiednie piksele o wskaźnikach pozycji $a,b,c$ stanowią elementy kontekstu predykcji rzędu 3, natomiast poszerzony zbiór pikseli $f_a,f_b,f_c,f_d$ został użyty w ocenie lokalnych zależności danych do selekcji trybu kodowania oraz zwiększenia efektywność modelu źródła stosowanego w kodowaniu binarnym.

Kontekst określony na podstawie czterech danych o położeniu $a$, $b$, $c$ i $d$ pozwala po pierwsze określić, czy informacja zawarta w wartości $f$ ma być kodowana w trybie regularnym czy w trybie sekwencji próbek identycznych:

• tryb sekwencji pikseli podobnych jest wybierany wówczas, gdy estymacja na podstawie kontekstu wskazuje, że wartości sąsiednich pikseli z dużym prawdopodobieństwem są prawie identyczne, z tolerancją dopuszczalną w kodowaniu prawie bezstratnym (identyczne w kodowaniu bezstratnym);
• tryb regularny jest wybierany wówczas, gdy z estymacji kontekstowej wynika, że nie istnieje duże prawdopodobieństwo wystąpienia kolejnych pikseli prawie identycznych, z tolerancją dopuszczalną w kodowaniu prawie bezstratnym (identycznych w bezstratnym); wówczas stosowana jest predykcja wartości kodowanego piksela na podstawie kontekstu jego wystąpienia.

Kodowanie sekwencji próbek podobnych

Charakter kontekstu ustalany jest za pomocą prostej estymacji gradientów lokalnych pikseli sąsiednich według zależności: $d_1=f_d-f_b$, $d_2=f_b-f_c$, \\ $d_3=f_c-f_a$. Warunek kontekstu pikseli podobnych w przypadku kompresji odwracalnej  wygląda następująco: $d_1=d_2=d_3=0$, co oczywiście oznacza identyczność pikseli sąsiedztwa: $f_a=f_b=f_c=f_d$. Dopuszczając stratność procesu kompresji, redefiniowany jest warunek kontekstu pikseli podobnych (z dokładnością $\sigma$) w sposób następujący: $\forall_{i \in \{1,2,3\}} |d_i| \leq \sigma$. Przy spełnieniu powyższych warunków wartość piksela kodowana jest w trybie sekwencji próbek podobnych. 

Oczekiwana jest wtedy seria kolejnych próbek o wartościach identycznych z $f_a$ zakończona pojawieniem się piksela o innej wartości lub końcem aktualnego wiersza. Długość serii jest kodowana z wykorzystaniem adaptacyjnej wersji kodu Golomba $EG_m$ (kod elementarny z ograniczeniem wartości rzędu $m$ do potęgi dwójki). W przypadku przerwania serii pikseli podobnych kodowana jest różnica pomiędzy $f$ i $f_b$ (modulo rozmiar skończonego alfabetu wartości pikseli). 

Nieliniowa predykcja trybu regularnego

W przypadku nie spełnienia warunku podobieństwa (identyczności) przez wartości pikseli sąsiedztwa  kodowanego piksela stosowany jest bardziej złożony tryb regularny (dominujący w przypadku obrazów naturalnych), wykorzystujący nieliniową predykcję z trójelementowego kontekstu oraz statystyczne modelowanie kontekstu i adaptacyjny kod Golomba do kodowania błędu predykcji.

W standardzie kompresji bezstratnej JPEG-LS wykorzystano prosty kontekst predykcji trzeciego rzędu składający się z elementów o położeniu $a$, $b$ i $c$ jak na rys.1.9. Model predykcji MED/MAP  jest nieliniowy, określony dla wartości $f$ następująco:

gdzie wartość przewidywana $\hat f$ ustalana jest adaptacyjnie na okoliczność znajdującej się w najbliższym sąsiedztwie krawędzi obiektu (gdy $f_c$ nie jest medianą pikseli sąsiedztwa), bądź też na okoliczność obszaru łagodnego ($f_c\) jest medianą).

Dodatkowo, błąd predykcji $\epsilon =f-\hat f$ jest korygowany za pomocą składnika zależnego od kontekstu, aby skompensować systematyczny błąd odchylenia w predykcji. Obciążenie operatora predykcji jest możliwe wskutek wykorzystania predykcji medianowej oraz przybliżeń $\hat f$ do wartości całkowitej (w skończonym zbiorze punktów).

Po predykcji według (1.4) wartość $\hat f$ jest korygowana zależnie od odchylenia błędu predykcji przy danym konteście. Założono dwustronny geometryczny, symetryczny rozkład błędów predykcji ze środkiem (wartością średnią) w przedziale . Celem jest utrzymanie środka rozkładu błędów w tym przedziale. Procedura wykorzystuje sumaryczną wartość błędów próbek zanotowanych przy tym samym kontekście kodowania.

Zmienna odchylenia błędu B[Q] pozwala na aktualizację wartości korekcji predykcji C[Q] najwyżej o jeden w każdej iteracji. WartośćC[Q] obliczana jest zgodnie z procedurą jak niżej, podobnie jak aktualna postać B[Q]:

Przykład 1.1. Oprogramowanie: korekcja błędu predykcji związana z obciążeniem operatora predykcji w JPEG-LS

/* Aktualizacja zmiennych B[Q] i C[Q]; zmienna C[Q] zawiera wartość korekcji wartości przewidywanej Px; SIGN równe jeden oznacza kontekst 'dodatni' */
B[Q] = B[Q] + E; /* suma błędów predykcji E */
N[Q] = N[Q] + 1; /* liczba wystąpień Q od inicjalizacji */ 

if (B[Q] <= -N[Q]) {<br />    B[Q] = B[Q] + N[Q]; C[Q] = C[Q] - 1;<br />    if (B[Q] <= -N[Q])  B[Q] = -N[Q] + 1;<br /> } else if (B[Q] > 0) {<br />    B[Q] = B[Q] - N[Q]; C[Q] = C[Q] + 1;<br />    if (B[Q] > 0) B[Q] = 0;<br /> }
....
if (SIGN == +1)  /* korekcja przewidywań */
   Px = Px + C[Q];
else Px = Px - C[Q];

Skorygowany błąd predykcji jest następnie kodowany z wykorzystaniem adaptacyjnego kodu Golomba, którego podstawowy parametr (tj. rząd) dobierany jest na podstawie rozkładu wartości błędu predykcji przy danym kontekście.

Modelowanie kontekstu

Chcąc objąć modelem statystycznym entropijnego kodowania szerszy niż w predykcji obszar potencjalnych zależności danych zdefiniowano najbliższe sąsiedztwo 4 pikseli $a$, $b$, $c$, $d$,  jak na rys. \ref{Rys_jpegls}. Na jego podstawie określono wykorzystany w kodowaniu binarnym, skwantowany kontekst  rzędu~4 składający się z następujących różnic:

gdzie wartości błędów predykcji $\epsilon=f-\hat f$ obliczane są według modelu predykcji (1.4). Wykorzystując kontekst (1.5) do estymacji prawdopodobieństw warunkowych konstruowany jest model $P(\epsilon |\Delta \epsilon _1,\Delta \epsilon _2,\Delta \epsilon _3)$. 

Alfabet każdego z trzech elementów kontekstu $C^{(4)}=(\Delta \epsilon _1,\Delta \epsilon _2,\Delta \epsilon _3)$ zmniejszono za pomocą operatora kwantyzacji $Q(\cdot )$ o $2T+1$ regionach indeksowanych: $\{-T,-T+1,\ldots,-1,0,1,\ldots,T\}$, co daje $(2T+1)^3$ różnych kontekstów. Przykładowo, dla $T=4$ mamy indeksy regionów: $\{-4,-3,\ldots, 3, 4\}$, co daje $9^3=729$ stanów modelu kontekstu. Kwantyzacja $Q(\cdot )$ nie musi być równomierna (o stałej szerokości przedziału kwantyzacji). W JPEG-LS dopuszczono kwantyzację nierównomierną, np. według następujących przedziałów domyślnych (zakładając $T=4$): $\{0\},\pm \{1,2\},\pm \{3,4,5,6\},\pm \{7,8,\ldots,20\},\pm \{\Delta \epsilon >20\}$. Procedurę kwantyzacji alfabetu kontekstu przedstawia poniższy fragment kodu:

Przykład 1.2. Oprogramowanie: kwantyzacja alfabetu kontekstu przy kodowaniu błędów predykcji w JPEG-LS

/* Różnica błędów predykcji E w punkcie i jest kwantowana do wartości QEi; T1,T2,T3 to dobierane granice przedziałów*/
if (Ei <= -T3) QEi = -4;
else if (Ei <= -T2) QEi = -3;
else if (Ei <= -T1) QEi = -2;
else if (Ei < 0) QEi = -1;
else if (Ei == 0) QEi = 0;
else if (Ei < T1) QEi = 1;
else if (Ei < T2) QEi = 2;
else if (Ei < T3) QEi = 3;
else Ei = 4;

Domyślnie T1=3, T2=7, T3=27. Okazuje się, że dla mniejszych zbiorów danych, np. obrazów o rozmiarach 64$\times$64, lepiej jest użyć jeszcze silniejszej kwantyzacji kontekstów, np. do 63 stanów trójelementowego kontekstu z alfabetem składającym się z pięciu symboli zamiast dziewięciu. Daje to poprawę efektywności kompresji, ponieważ model o mniejszej liczbie stanów może być bardziej wiarygodny.

Aby dodatkowo zmniejszyć liczbę stanów modelu z pamięcią ustala się znak kontekstu kodowanej wartości. Kontekst ''ujemny'' zamieniany jest na ''dodatni'', a model konstruowany jest wyłącznie na podstawie  kontekstów ''dodatnich''. Adaptacyjnie modyfikowany model w chwili $t$ (używany do kodowania $\epsilon _{t+1}$) określa prawdopodobieństwo wystąpienia określonej wartości $\epsilon _{t+1}$ zależnie od kontekstu $C_{\mathbf{t}}=C_t^{(3)}=\mathbf{c}=(g_1,g_2,g_3)$ (określony w każdej chwili jak na rys. 1.9). Jeśli pierwszy niezerowy element kontekstu zaczynając od $g_1=Q(\Delta \epsilon _1)$ jest ujemny, odwracane są znaki wszystkich elementów niezerowych. ''Dodatni'' kontekst $-\mathbf{c}$ warunkuje wtedy prawdopodobieństwo symbolu w kodzie binarnym. Założono w tym przypadku symetryczność rozkładu:

gdzie $\varepsilon \in A_{\mathcal{E}}$. Takie rozwiązanie zakłada kodowanie wartości $-\epsilon _{t+1}$ dla kontekstów ''ujemnych'', co należy uwzględnić podczas dekodowania. 

Uzyskano zmniejszenie liczby stanów do $((2T+1)^3+1)/2=365$.

Binarne kodowanie błędu predykcji

Na etapie rozwoju standardu JPEG-LS jako kod binarny stosowano metodę Huffmana z modelem z pamięcią, a także optymalizowany algorytm adaptacyjny kodu Golomba. Pozwoliło to uzyskać bardzo szybką metodę kompresji obrazów o dużej efektywności. Dodatkowy wzrost efektywności kosztem większej złożoności obliczeniowej można uzyskać wykorzystując kodowanie arytmetyczne (proponowane rozszerzenie JPEG-LS) \cite{LOCOA}. Używany jest tutaj analogiczny sposób kwantyzacji kontekstu i alfabetu na podstawie sąsiedztwa 5 pikseli. 

W finalnej wersji standardu wykorzystano szybki kod Rice'a $R_k$ rzędu $k$, gdzie $k$ jest dobierane zależnie od kontekstu i zmieniane adaptacyjnie. Wartość $k$ dla danego kontekstu jest uaktualniana za każdym razem, gdy kodowana jest próbka poprzedzona tym kontekstem. Metoda modyfikacji $k$ wykorzystuje skumulowaną sumę modułów błędów predykcji wartości pikseli występujących przy danym kontekście jak niżej:

Przyklad 1.3. Oprogramowanie: dynamiczne ustalanie optymalnego rzędu kodu Rice'a JPEG-LS

/* Zmienna A[0..364] zawiera sumę modułów błędów predykcji kontektu Q;  w N[0..364] liczone są przypadki wystąpień Q od inicjalizacji; A[Q]  i N[Q] są aktualizowane zgodnie z aktualnym błędem predykcji E*/
A[Q] = A[Q] + abs(E); /* aktualizacja zmiennych */
N[Q] = N[Q] + 1;
...
for(k=0; (N[Q]<<k)<A[Q]; k++); /* wyznaczenie rzędu k */