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

i W

j H

[ , ],

,

0

0

≤ <

≤ <

.

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

H

/

/

2

2

×

w

sposób nastêpuj¹cy:

µ[ , ] ,

/ ,

/

i j

I i j

I i

j

i W

j H

= 






≤ <

≤ <

[ , ] + [ + ,

+ ]

,

2 2

2

1 2

1

2

0

2 0

2

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

$

[ ,

]

[

, ]

/ ,

/

µ µ

µ

µ

µ

=

− +

−

+

−

−

−

≤ <

≤ <

i j

i

j

i

j

i

j

i W

j H

1

1

2

1

1

1

1

0

2 0

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ñ).

i

j

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 j I i

j

i W

j H

[ , ], [

,

],

/ ,

/

2 2

2

1 2

1

0

2 0

2

+

+

≤ <

≤ <

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

$

. [ , ]

[

,

]

[

,

]

[

,

]

[

, ]

[ ,

]).

x

i j

I i

j

I i

j

I i

j

I i

j

I i j

i

j

i j

=

+

−

+ +

−

− +

+

−

−

−

+

+

+

0 9

2

1 2

1

2

1 2

1

2

1 2

1

6

0 05

2

2

1

1

µ

µ

µ

- . ( [2

,2 ] + [2 ,2

]) - 0.15(

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

I i

j

i j

I i j

[

,

]

[ , ]

[ , ]

2

1 2

1

2

2 2

+

+ =

−

µ

.

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

j I i j

i W

j H

[

,

], [ ,

],

/ ,

/

2

1 2

2 2

1

0

2 0

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:

$

( [

, ]

[ ,

]

[

, ]

[ ,

])

[

,

]

[

,

]

x

I i

j

I i j

I i

j

I i j

I i

j

I i

j

=

−

+

− +

+

+

+

−

−

− +

+

−

3

8

1

1

1

1

1

1

1

1

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

K

( / ,...,

)

1

.

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

K

1

2

, ,...,

zwi¹zany z

przewidywan¹ wartoœci¹ $x do liczby binarnej

t t

t

K

=

...

1

sk³adaj¹cej siê z K bitów tak, ¿e:

t

x

x

x

x

k

k

k

=

≥







≤ ≤

0
1

if

if

<

1 k 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:

∆ =

−

=

∑

w x

x

k

k

K

k

1

|

$

|.

Na jej podstawie mo¿na estymowaæ prawdopodobieñstwo warunkowe b³êdu predykcji jako p(e/ ) zamiast

p e x

x

K

( / ,...,

)

1

. Aby zlikwidowaæ problem 'rozrzedzenia kontekstu' przy estymacji p(e/ ) dokonywana jest

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

k

otrzymujemy ostatecznie kwantyzacjê

2

ZK

stanów Ÿród³a Markowa w znacznie zredukowan¹

liczbê

L

K

2

stanów. Te stany nazywane s¹ kwantowanym kontekstem i oznaczone s¹ nastêpuj¹co:

C d t

d

L

t

K

( , ),

,

0

0

2

≤ <

≤ <

.

Pozostaje oczywiœcie problem jak dobraæ wartoœci wspó³czynników w

k

. WartoϾ jest ustalana jako

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

wspó³czynników

w

k

. Tak wiêc maj¹c przyk³adowy predyktor DPCM $x

a x

k

k

K

k

=

=

∑

1

(w jednym z trzech

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

$

|

e x x

= −

oraz |

$

|,

x

x

k K

k

−

≤ ≤

1

.

Nastêpnie wartoœci

w

k

,

1

≤ ≤

k

K

s¹ obliczane metod¹ regresji liniowej tak, aby zminimalizowaæ wartoœæ:

{| |

}

|

$

|

|

$

|

e

x x

w x

x

k

k

k

K

S

S

−

=

− −

−













=

∑

∑

∑

∆

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

O n

(

)

(

)

.

.

−

−

0 5

0 4

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

0

1

1

=

< < ⋅⋅⋅ <

<

= ∞

−

q

q

q

q

L

L

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

S

q

q

d

d

d

=

≤ <

+

{ |

}

ε

∆

1

, takich ¿e wra¿enie:

−

∈

∑

p

p

S

d

( )log ( |

)

ε

ε ε

ε

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

( , )

1

i

C d t

( , )

2

, wartoœci warunkowych œrednich próbek

ε ( , )

d t

1

i

ε ( , )

d t

2

mog¹ mieæ przeciwne znaki i

odpowiednio ró¿ne wartoœci p C d t

( | ( , ))

ε

1

i p C d t

( | ( , ))

ε

2

. Dla ustalonej wartoœci

0

≤ <

d

L

mo¿na

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

p

=

+

+

−

. Mo¿na wiêc

przerzuciæ

p

−

symetrycznie wzglêdem osi zerowej ( p

d

−

−

( | )

ε

) i na³o¿yæ na

p

+

otrzymuj¹c obci¹¿any

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

p

=

+

+

−

poprzez przerzucanie

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

2

≤ <

t

K

.

PARAMETRY: wyznaczone wczeœniej optymalne wartoœci

a w

k K

k

k

,

,1

≤ ≤

.

Dla ka¿dego piksela x z danego etapu

0.

x

a x

x x

x

k k

K

k

K

^

, ,...,

=

=

∑

dla kontekstu predykcji

1

2

1

;

1.

∆ =

=

∑

w x

k

k

k

K

( - x)

^

1

;

2. d=Q( );
3. wyznacz wzorzec tekstury

t t

t

K

=

...

1

:

IF

ELSE

(

)

,

;

^

x

x t

t

k

K

k

k

k

<

=

=

≤ ≤

0

1 1

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

N d t

N d t

( , )

( , ) / ; ( , )

( , ) / ;

=

=

2

2

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

END;

END.