CALIC (Context-based Adaptive Lossless Image Codec)

Kryteria modelowania kontekstu dla bezstratnego kodowania obrazu w znaczeniu maksymalnej kompresji i in¿ynierskiej przydatnoœci (stosowalnoœci) s¹ nastêpuj¹ce: a) silna dekorelacja - przyjêty model obrazu pozwala ca³kowicie okreœliæ i zredukowaæ statystyczn¹

nadmiarowoœæ Ÿród³a.

b) uniwersalnoœæ - model obrazu mo¿e szybko przystosowaæ siê (adoptowaæ) do nieznanej statystyki Ÿród³a.

c) niski koszt obliczeniowy - same konteksty oraz modelowanie obrazu i predykcja oparte na tych kontekstach mog¹ byæ efektywnie obliczane (wyznaczane).

d) niskie wymagania pamiêciowe - przestrzeñ pamiêci przeznaczona do gromadzenia kontekstów i informacji zwi¹zanych z tymi kontekstami u¿ywana w modelowaniu i predykcji nie powinna byæ nadmierna.

Trzy-stopniowy schemat kodowania predykcyjnego z przeplotem.

Na ka¿dym etapie przeprowadzane jest przeplatane próbkowanie obrazu oryginalnego. Niech obraz oryginalny, wielopoziomowy ze skal¹ szaroœci, o szerokoœci W i wysokoœci H bêdzie opisany przez I i

[ , j], 0 ≤ i < W, 0 ≤ j < H .

i

j

Pierwszy etap

Drugi etap

Trzeci etap

Rys. 1. Schemat modelowania kontekstu do trzy etapowej predykcji kodowanych wartoœci w CALIC-u.

Pierwszy etap

A. tworzony jest podobraz o dwukrotnie zmniejszonej rozdzielczoœci w obu kierunkach W / 2 × H / 2 w sposób nastêpuj¹cy:

µ

 I[ i

2 ,2 j] + I[ i

2 + ,

1 2 j + ]

1

[ i, j] =,



, 0 i W / 2, 0 j H / 2



2



≤ <

≤ <

B. podobraz koduje siê wykorzystuj¹c typowy kontekst dla DPCM, np.

[ i, j

]

1

[ i

,

1 j]

i

[

1, j 1] - i

[

1, j 1]

$

µ µ

µ

µ

µ

=

− +

−

+

−

−

−

+

, 0 ≤ i < W / 2, 0 ≤ j < H / 2

2

4

Wspó³czynniki predykcji zosta³y wyznaczone metod¹ regresji liniowej przy pomocy zbioru obrazów treningowych (zaokr¹glone zosta³y do potêgi dwójki ze wzglêdu na prostotê obliczeñ).

Drugi etap

A. ten sam podobraz jest stosowany jako kontekst predykcji WH/2 pikseli obok wartoœci pikseli obrazu oryginalnego w sposób nastêpuj¹cy:

chcemy zakodowaæ wartoœci pikseli

I[ i

2 ,2 j], I[ i

2 + ,

1 2 j + ]

1 , 0 ≤ i < W / 2, 0 ≤ j < H / 2

B. liniowa predykcja - aby zakodowaæ wartoœci I[2i,2j] stosuje siê nastêpuj¹cy model liniowej predykcji: I[ i

2

,

1 2 j

]

1

I[ i

2

,

1 2 j

]

1

I[ i

2

,

1 2 j

]

1

$ x = .

0 9 [

µ i, j] +

−

+ +

−

− +

+

−

6

- 0 05

. ( I i

[2 − 2,2 j] + I i

[2 ,2 j − 2]) - 0.15( [

µ i + ,

1 j] + [

µ i, j + ]).

1

Natomiast wartoœci I[2i+1,2j+1] nie potrzeba ju¿ kodowaæ. S¹ one rekonstruowane z zale¿noœci: I[ i

2 + ,

1 2 j + ]

1 = 2 [

µ i, j]− I[ i

2 ,2 j].

Mo¿e przy tym wyst¹piæ b³¹d obciêcia reszty u³amkowej, gdy przy liczeniu œredniej diagonalnej suma dwóch wartoœci pikseli jest liczb¹ ca³kowit¹ nieparzyst¹ (mo¿na go zignorowaæ).

Trzeci etap

A. nale¿y zakodowaæ dwie pozosta³e wartoœci pikseli obrazu oryginalnego z ka¿dego elementarnego bloku czterech pikseli, a mianowicie

I[ i

2 + ,

1 2 j], I[ i

2 ,2 j + ]

1 , 0 ≤ i < W / 2, 0 ≤ j < H / 2.

Wykorzystano kontekst '360 stopni' sk³adaj¹cy siê z czterech pikseli najbli¿szego s¹siedztwa w rastrze cztero-po³¹czeniowym oraz dwóch pikseli z s¹siedztwa oœmio-po³¹czeniowego (wszystkie one s¹ ju¿

wczeœniej kodowane oraz dekodowane, a wiêc dostêpne w procesie rekonstrukcji).

B. zastosowano nastêpuj¹cy model predykcji:

3

I[ i

,

1 j

]

1

I[ i

,

1 j

]

1

$ x = ( I[ i − ,

1 j] + I[ i, j − ]

1 + I[ i + ,

1 j] + I[ i, j + ])

1 −

−

− +

+

−

8

4

Modelowanie i kwantyzacja kontekstu.

Dot¹d dla modelowania kontekstów predykcji poszczególnych pikseli wykorzystywano wartoœci odpowiednio K = 4, 9, 6 (1,2 i 3 etap) s¹siednich pikseli Aby przy entropijnym kodowaniu uzyskaæ minimaln¹

d³ugoœæ kodu wyjœciowego dla zbioru wartoœci e = x − x$ (gdzie $ x wyznaczono dla ka¿dej wartoœci x w trójetapowej predykcji) potrzeba maksymalizowaæ prawdopodobieñstwo warunkowe p( e / x ,..., x ).

1

K

U¿ywaj¹c standardowych metod np. kodowania arytmetycznego z za³o¿onym modelem Markowa n - tego rzêdu potrzeba by okreœliæ w sposób istotny statystycznie model o 2 ZK stanach ( Z- liczba poziomów szaroœci), co jest niebagatelnym problemem! (tzw. problem rozrzedzenia kontekstu). Zastosowano wiêc nastêpuj¹cy model kwantyzacji kontekstu w celu prostszego okreœlenia wartoœci prawdopodobieñstw warunkowych oraz korekcji przewidywanej wartoœci w pêtli sprzê¿enia zwrotnego. Tak wiêc:

A. aby u³atwiæ modelowanie kontekstu b³êdów DPCM kwantyzuje siê kontekst x , x ,..., x zwi¹zany z 1

2

K

przewidywan¹ wartoœci¹ $ x do liczby binarnej t = t ... t sk³adaj¹cej siê z K bitów tak, ¿e: K

1

0

x

if

≥ x$

t

k

=

, 1 ≤ k ≤ K.

k

1 x

if

< x



$

k

Liczba t reprezentuje wy¿szego rzêdu przestrzenn¹ strukturê modeluj¹cego kontekstu, czyli cechê obrazu, która mo¿e wskazywaæ na zachowanie siê b³êdu predykcji DPCM (korelacja). Mo¿na w ten sposób uwzglêdniæ krawêdzie, rogi, tekstury, które nie mog³y byæ uchwycone przez DPCM.

B. obliczana jest tak¿e wartoœæ dyskryminatora mocy b³êdu, który charakteryzuje zmiennoœæ wartoœci kontekstu (jego g³adkoœæ), w nastêpuj¹cy sposób:

K

∆ =

|

$|.

k −

∑ w x x

k

k =1

Na jej podstawie mo¿na estymowaæ prawdopodobieñstwo warunkowe b³êdu predykcji jako p(e/ ) zamiast p( e / x ,..., x ). Aby zlikwidowaæ problem 'rozrzedzenia kontekstu' przy estymacji p(e/ ) dokonywana jest 1

K

kwantyzacja wartoœci na L poziomów (w praktyce najczêœciej L= 8). £¹cz¹c teraz, jako iloczyn kartezjañski L

K

× 2 , kwantowany do L poziomów dyskryminator oraz 2 K kwantowanych wzorców tekstury kontekstu t otrzymujemy ostatecznie kwantyzacjê 2 ZK stanów Ÿród³a Markowa w znacznie zredukowan¹

k

liczbê L K

2 stanów. Te stany nazywane s¹ kwantowanym kontekstem i oznaczone s¹ nastêpuj¹co: C d t 0 ≤ d < L 0 ≤ t

K

( , ),

,

< 2 .

Pozostaje oczywiœcie problem jak dobraæ wartoœci wspó³czynników w . Wartoœæ jest ustalana jako k

œredniokwadratowa estymata | e|. Stosuj¹c standardow¹ metodê regresji liniowej okreœla siê wiêc wartoœci K

wspó³czynników w . Tak wiêc maj¹c przyk³adowy predyktor DPCM $ x =

a x (w jednym z trzech

k

∑ k k

k =1

etapów predykcji), jest wyznaczany treningowy zbiór S wartoœci | |

e =| x − $|

x oraz | x − $ x|,1 ≤ k ≤ K .

k

Nastêpnie wartoœci w , 1 ≤ k ≤ K s¹ obliczane metod¹ regresji liniowej tak, aby zminimalizowaæ wartoœæ: k

K





{| |

e − } =

| x

∑ ∆ ∑ − $ x|− w | x − $| x

∑ k k 

S

S 

k =1



na treningowym zbiorze danych.

Adaptacyjne, oparte na kontekœcie modelowanie b³êdu (wraz z drug¹ faz¹ kwantyzacji) Jednak L K

2 stanów kontekstów modeluj¹cych to jednak dalej za du¿o do dobrej estymacji prawdopodobieñstw warunkowych, w tym przypadku p(e/C(d,t)). Wobec tego nastêpuje: A. estymowanie warunkowej wartoœci oczekiwanej E{e/C(d,t)} poprzez wyznaczenie odpowiedniej œredniej próbek e( d, t) dla ró¿nych kwantowanych kontekstów. Intuicyjnie znacznie mniej próbek potrzeba do dobrej estymacji warunkowej wartoœci oczekiwanej ni¿ prawdopodobieñstwa ( O( n− .05)

O( n− .04

versus

)). Poniewa¿ œrednia warunkowa e( d, t) lepiej estymuje b³¹d predykcji DPCM w kwantowanym kontekœcie C(d,t), mo¿na skompensowaæ b³¹d DPCM poprzez modyfikacjê predykcji x z $ x na predykcjê x z & x = $ x + e( d, t) . & x jest nowym, adaptacyjnym nieliniowym opartym na kontekœcie predyktorem (mechanizm sprzê¿enia zwrotnego b³êdu predykcji z opóŸnieniem jednego kroku). Wykorzystuj¹c nowy predyktor mamy teraz nowy b³¹d predykcji: ε = x − x& dla entropijnego kodowania b³êdu. Rozk³ad wartoœci b³êdu predykcji zachowuje w tym przypadku postaæ rozk³adu Laplace'a, ale jest wyraŸnie wyostrzony.

B. optymalizacja kwantyzatora Q wartoœci Kryterium kwantyzacji jest minimalizacja warunkowej entropii wartoœci b³êdów zale¿nej od p( /Q( )). Ze zbioru obrazów treningowych obliczamy zbiór wartoœci par ( ) i u¿ywamy standardowej dynamicznej techniki wyboru wartoœci 0 = q < q < ⋅⋅⋅ < q q

L− <

L = ∞

0

1

1

dziel¹ce przedzia³ wartoœci na L podprzedzia³ów:

S = { ε| q ≤ ∆ < q } , takich ¿e wra¿enie: d

d

d +1

−

( ε)log ( ε| ε ∈

∑ p

p

S )

d

ε

osi¹ga minimum.

Dwa procesy poszukiwania optymalnego schematu kwantyzacji (szukanie wspó³czynników i podzia³

przedzia³u wartoœci na L podprzedzia³ów) mog¹ byæ przeprowadzane równie¿ w sposób ³¹czny (kwantyzacja ³¹czna).

C. entropijne kodowanie wartoœci - adaptacyjne entropijne kodowanie (najlepiej arytmetyczne) z u¿yciem tylko L prawdopodobieñstw warunkowych p( /Q( ) =d), 0 ≤ d < L dla poszczególnych wartoœci .

Przerzucanie znaku b³êdu predykcji

Znaki warunkowych œrednich próbek ε ( d, t) mog¹ byæ u¿yte do wyostrzenia prawdopodobieñstw warunkowych p( /Q( ) =d), a wiêc redukcji warunkowej entropii. Dla dwóch ró¿nych kontekstów C( d , t ) i 1

C( d , t ), wartoœci warunkowych œrednich próbek ε ( d, t ) i ε ( d, t ) mog¹ mieæ przeciwne znaki i 2

1

2

odpowiednio ró¿ne wartoœci p( ε| C( d, t )) i p( ε| C( d, t )) . Dla ustalonej wartoœci 0 ≤ d < L mo¿na 1

2

rozdzieliæ prawdopodobieñstwo p( /Q( ) =d) na dwa: p ( ε| d) p( ε| d, ε ( d, t

+

=

) ≥ )

0 , p ( ε| d) p( ε| d, ε ( d, t

−

=

) < )

0 .

Oczywistym jest, ¿e oba prawdopodobieñstwa warunkowe p i p daj¹ ni¿sz¹ entropiê ni¿

+

−

p( /Q( ) =d) (bardziej wyró¿niona jest statystyka b³êdu). Wydaje siê jednak ¿e wówczas podwajaj¹ siê: zu¿ycie pamiêci oraz rozmycie kontekstów.

Mo¿na zaobserwowaæ, ¿e p ( ε| Q(∆) d

+

= ) oraz p ( ε| Q(∆) d

−

= ) s¹ w przybli¿eniu swoim

lustrzanym odbiciem wzglêdem wartoœci oczekiwanej (równej zero) rozk³adu p = p

. Mo¿na wiêc

+ + p−

przerzuciæ p symetrycznie wzglêdem osi zerowej (

ε

) i na³o¿yæ na p otrzymuj¹c obci¹¿any

−

p ( | d

− −

)

+

estymator prawdopodobieñstwa $(

p ε| Q(∆) = d) o mniejszej wariancji w stosunku do p( /Q( ) =d) - rys. 2.

Zastosowanie tego estymatora pozwala zmniejszyæ œredni¹ bitow¹ kodu bez dodatkowej pamiêci oraz bez rozrzedzenia kontekstu.

Dzia³anie: przed kodowaniem ε = x − x& , koder sprawdza czy ε ( d, t) < 0 na podstawie kontekstu C(d,t).

Jeœli tak - jest kodowany, a w pozosta³ych przypadkach . Poniewa¿ dekoder tak¿e zna C(d,t) i ε ( d, t) mo¿e jeœli to konieczne odwróciæ znak, aby zrekonstruowaæ wartoœæ ε.

Rys. 2. Wyostrzanie prawdopodobieñstwa warunkowego p = p poprzez przerzucanie p .

+ + p−

−

Najwa¿niejsze zalety metody kompresji CALIC

Z³agodzenie problemu rozrzedzenia kontekstu poprzez:

• rozró¿nienie kontekstu C(d,t) dla modelowania b³êdu oraz kontekstu Q( ) dla warunkowego kodowania entropijnego b³êdu predykcji;

• estymatê pojedynczego parametru wartoœci oczekiwanej zamiast szeregu prawdopodobieñstw warunkowych dla danego kontekstu.

Pozwoli³o to uzyskaæ du¿¹ liczbê kontekstów przy modelowaniu b³êdu, aby uchwyciæ bardziej z³o¿one struktury b³êdu (z³o¿one korelacje) w celu zwiêkszenie efektywnoœci kodowania.

Opis algorytmu

Algorytm sk³ada siê z trzech g³ównych sk³adników:

• adaptacyjna predykcja,

• modelowanie kontekstu,

• kodowanie z entropi¹ warunkow¹,

przy czym modelowanie kontekstu wp³ywa zarówno na predykcjê jak i entropijne kodowanie.

Algorytm:

Dla ka¿dego z trzech etapów:

INICJALIZACJA: N(d,t)= 1, S(d,t)= 0, 0 ≤ d < L, 0 ≤ t < 2 K .

PARAMETRY: wyznaczone wczeœniej optymalne wartoœci a , w ,1 ≤ k ≤ K.

k

k

Dla ka¿dego piksela x z danego etapu

^

K

0. x =

a x

x , x ,..., x

∑ dla kontekstu predykcji

;

k k

1

2

K

k =1

K

^

1. ∆ = ∑ w ( x - x);

k

k

k =1

2. d=Q( );

3. wyznacz wzorzec tekstury t = t ... t : K

1

^

IF ( x < x) t = 0 ELSE t = ,

1 1 ≤ k ≤ K;

k

k

k

_

4. e = S( d , t) / N ( d , t);

.

^

_

5. x = x+ e;.

6. ε = x − x;

7. S(d,t)=S(d,t)+ ; N(d,t)=N(d,t)+1;

8. IF N ( d , t) ≥ 128

S( d , t) = S( d , t) / ; 2 N ( d , t) = N ( d, t) / ; 2

9. IF S(d,t)<0 koduj (- ,d) ELSE koduj ( ,d); END;

END.