Kompresja stratna
obrazów

Stratna kompresja obrazów



Algorytm JPEG (stratny)



Algorytm JPEG2000

Nowoczesne metody kompresji
obrazów



Algorytmy predykcyjne



na podstawie



modelu obrazu



już przetworzonej części obrazu



znanego otoczenia danego piksela



spróbuj przewidzieć barwę piksela (predykcja)



kompresuj błąd predykcji

(różnicę między przewidzianą i rzeczywista barwą)



Algorytmy transformacyjne, kodowanie podpasmowe



obraz przekształć odpowiednią transformatą (DCT, DWT)



kodowania predykcyjnego nie uznaje się za kodowanie transformacyjne



kompresuj macierz współczynników transformaty



stosowane głównie w algorytmach stratnych

Algorytm JPEG (stratny)



Opracowany przez Komitet JPEG w 1992 r.



Popularny do dziś transformacyjny algorytm kompresji

stratnej obrazów barwnych oraz w stopniach szarości,

oparty o całkowitoliczbową transformatę kosinusową DCT

oraz koder Huffmana



algorytm bazowy (baseline codec)



rozszerzenia (extensions)



Wallace, G. K.: The JPEG Still Picture Compression Standard.

Communications of the ACM, April 1991, Vol 34(4), s. 30-44.

Algorytm bazowy JPEG ― zarys



Kroki algorytmu



Transformacja przestrzeni barw (opcjonalnie)



Podpróbkowanie składowych chrominancji (opcjonalnie)



Podział składowych na bloki 8x8 pikseli i zastosowanie transformaty DCT

dla każdego bloku



Kwantyzacja macierzy współczynników transformaty na podstawie tabeli

kwantyzacji



Kodowanie współczynników za pomocą kodów Huffmana



lub arytmetycznie (rozszerzenie)



Zapisanie zakodowanych danych w pliku o strukturze opisanej przez

standard

Algorytm bazowy JPEG



Transformacja przestrzeni barw (opcjonalnie)



Przestrzenie zawierające oddzielne składowe luminancji i

chrominancji, np. YC

r

C

b

,



lub pominięcie transformacji i kompresja wprost obrazu multispektralnego

(jak RGB, CMYK, do 255 składowych)



Kilka celów



dekorelacja składowych, które są kodowane niezależnie od siebie, zatem

poprawa współczynników/jakości



umożliwienie kodowania różnych składowych z różną jakością

Algorytm bazowy JPEG



Podpróbkowanie składowych chrominancji (opcjonalnie)



Oko ludzkie jest znacznie bardziej czułe na jasność obrazu niż na kolor



zarówno pod względem rozdzielczości jak i głębi



Skoro kompresujemy stratnie to można „straty” wprowadzić z

uwzględnieniem czułości oka



składowe chrominancji są podpróbkowane, ich rozdzielczość jest 2-krotnie mniejsza

od składowej luminancji
(BTW: obraz komputerowy to dane już po wstępnym próbkowaniu i kwantyzacji)

Algorytm bazowy JPEG



Kodowanie składowej



Podział składowych na bloki 8x8 pikseli



Transformata DCT dla każdego bloku



Kwantyzacja współczynników transformaty



Kodowanie entropijne

Algorytm bazowy JPEG



Transformata DCT dla bloku 8x8 pikseli



DCT przeprowadzamy po sprowadzeniu nominalnego zakresu jasności pikseli do przedziału
symetrycznego względem 0
[0 ... 2

N

– 1] → [–2

N – 1

... 2

N – 1

– 1]



Współczynniki transformaty niskich częstotliwości zgrupowane są blisko lewego górnego
rogu macierzy



Sam lewy górny róg to składowa stała jasności bloku

Algorytm bazowy JPEG



Kwantyzacja macierzy współczynników transformaty na
podstawie tabeli kwantyzacji (o rozmiarze 8x8)



po DCT, dla składowej o głębi N bpp, współczynniki transformaty
wymagają N+3 bitów



czyli najpierw mamy ekspansję danych



typowo większość współczynników AC ma małe wartości ...



... tym mniejsze im wyższej częstotliwości odpowiadają ...



... i małe znaczenie dla percepcji obrazu



każdy z współczynników transformaty DCT dzielimy przez odpowiadający
mu element tabeli kwantyzacji ...



... i zaokrąglamy do najbliższej liczby całkowitej

Algorytm bazowy JPEG



Kwantyzacja macierzy współczynników transformaty na
podstawie tabeli kwantyzacji (o rozmiarze 8x8) ― c.d.



tabela kwantyzacji jest parametrem algorytmu



komitet JPEG przygotował tabele standardowe



dobrane na podstawie eksperymentów
z rzeczywistymi obrazami oraz
rzeczywistymi urządzeniami akwizycji



inne dla luminancji (np. →)
inne dla chrominancji



dzieląc wszystkie współczynniki
przez stałą wartość kontrolujemy
współczynnik kompresji

Algorytm bazowy JPEG



Kwantyzacja macierzy współczynników transformaty na
podstawie tabeli kwantyzacji (o rozmiarze 8x8)



po kwantyzacji układamy
(linearyzujemy) macierz
współczynników w kolejności
Zig-Zag i kodujemy entropijnie

Algorytm bazowy JPEG



Kodowanie współczynników za pomocą kodów prefiksowych



Kodujemy odmiennie współczynniki DC i AC, oba rodzaje współczynników

z użyciem kodów prefiksowych



wygenerowanych algorytmem Huffmana

(w dość złożony sposób ― szczegóły: patrz artykuł Wallace’a)



Współczynniki DC



kodujemy różnice współczynników DC kolejnych bloków



Współczynniki AC



ciąg współczynników AC bloku zwykle zawiera długie podciągi zer;

sufiks ciągu zwykle jest długim ciągiem zer



kodujemy wariantem algorytmu RLE połączonym z kodowaniem Huffmana

Algorytm bazowy JPEG



Dlaczego JPEG jest stratny?



przede wszystkim



podpróbkowanie składowych chrominancji



kwantyzacja



również nie-odwracalne



transformacja przestrzeni barw



DCT

Algorytm JPEG ― rozszerzenia



Rozszerzenia standardu



tryb progresywny względem jakości



tryb hierarchiczny (piramidowy)



kodowanie arytmetyczne
(QM-Coder zamiast algorytmu Huffmana)



inne (praktycznie nie stosowane)

JPEG2000



Nowy standard komitetu JPEG dla stratnej i bezstratnej kompresji obrazów



ITU-T; ISO/IEC: Information technology – JPEG 2000 image coding system: Core

coding system. ITU-T Recommendation T.800 and ISO/IEC International Standard

15444-1, August 2002.



Z roku 2000, następca algorytmu JPEG i Lossless JPEG, wyłoniony w drodze

konkursu (ogłoszonego w 1997) oparty o algorytm CREW (Zandi, Allen, Schwartz,

Boliek)



Algorytm CREW był zgłoszony w odpowiedzi na konkurs, który miał wyłonić algorytm

JPEG-LS. Jako podstawę JPEG-LS wybrano LOCO-I, lecz bogactwo dodakowych

własności algorytmu CREW (innych niż stratna/bezstratna kompresja obrazu jako

całości) skłoniło komitet do rozpoczęcia prac nad JPEG2000.



Christopoulos, C.; Skodras, A.; Ebrahimi, T.: The JPEG2000 Still Image Coding System

an Overview. IEEE Transactions on Consumer Electronics, November 2000, Vol. 46(4),

pp. 1103-27.

JPEG2000 ― zarys



Cechy algorytmu



Algorytm stratnej/bezstratnej kompresji obrazów multispektralnych,

barwnych oraz w stopniach szarości oparty o transformatę falkową



Dla kompresji stratnej i bezstratnej, dostępne możliwości



kodowanie progresywne, w tym progresja: stratne → bezstratne



kodowanie piramidowe



kodowanie progresywne względem ROI (region of interest)



dostęp swobodny do fragmentów obrazu



Dla stratnej



lepsza jakość od JPEG przy tym samym współczynniku

dla współczynników poniżej 0.25 bpp znacznie lepsza



ROI w standardzie (w JPEG formalnie również było jako extension)



niezła odporność na błędy transmisji



poprawienie współczynnika (kosztem pogorszenia jakości) nie wymaga

pełnego dekodowania

JPEG2000 ― zarys



Kroki algorytmu



Sprowadzenie nominalnego zakresu jasności pikseli do przedziału symetrycznego

względem 0 (jak w JPEG)



Transformacja przestrzeni barw (opcjonalnie)



Podział składowej na kafelki (opcjonalnie)



Transformata falkowa kafelka (opcjonalnie)



dekompozycja/kodowanie podpasmowe (subband decomposition)



reprezentacja wielorozdzielcza



Kwantyzacja współczynników transformaty

(właściwie również opcjonalnie)



Kodowanie arytmetyczne skwantowanych współczynników



po dekompozycji na składowe/kafle/warstwy/percints



„obcinanie strumienia bitów”



Zapisanie zakodowanych danych w pliku o strukturze opisanej przez standard



struktura elastyczna, tzn. możliwość kodowania dla wybranej preferencji progresji

Transformacja przestrzeni barw



ICT (Irreversible Color Transform)



RGB → YC

r

C

b



Tylko do użycia z nie-odwracalną transformatą falkową (9-7)



RCT (Reversible Color Transform)



stałopozycyjna aproksymacja ICT



dla C

1

i C

2

ekspansja alfabetu

Podział składowej na kafelki



Realizowany przez nałożenie prostokątnej siatki na obraz,

przy czym



krawędzie siatki nie muszą pokrywać

się z krawędziami obrazu



można dopasować podział do treści

obrazu oraz zasobów komputera



cały obraz może być jednym kafelkiem



rozmiar kafelka typowo jest

rzędu 2

8

x 2

8

pikseli

Kodowanie podpasmowe

Transformata falkowa



Transformata falkowa rzędu I obrazu 2D



... realizowana za pomocą jednowymiarowej transformaty falkowej



zastosowanej najpierw do wierszy obrazu (otrzymujemy pasma L i H)



a następnie do kolumn już przetransformowanego obrazu

(otrzymujemy pasma LL, HL, LH, HH)

L

H

LL

HL

LH

HH

Transformata falkowa

LL

HL

LH

HH

Transformata falkowa



Transformata falkowa wyższych rzędów



do pasma LL zastosuj ponownie transformatę rzędu I

(poniżej rzędy I i III)



reprezentacja wielorozdzielcza: dla rzędu transformaty i

mamy i + 1 poziomów rozdzielczości



typowy rząd transformaty w JPEG2000: V

LL

HL

LH

HH

Transformata falkowa w JPEG2000



Transformata nie-odwracalna do zastosowania przy kompresji stratnej



filtr 9-tap/7-tap Daubechies



real-to-real



Transformata odwracalna dla kompresji bezstratnej oraz stratnej



filtr 5-tap/3-tap Daubechies



integer-to-integer



szczegóły na następnym slajdzie



Realizowalne metodą

liftingu

(9-7 ― w 6 krokach, 5-3 ― w 2 krokach)

(Ingrid Daubechies, Wim Sweldens „Factoring Wavelet Transforms into Lifting Steps”)



Przed transformatą ekstrapolujemy wiersze: (wiersz

rozszerzony wiersz

)

... C B A

A B C D E F G H

H G F ...

... A B C C B A

A B C

C B A A B C C B A ...

L

H



Transformata DWT, implementacja metodą liftingu

(X ― piksele wiersza przed transformatą, Y ― po transformacie, 2 koki: najpierw nieparzyste Y)



następnie parzyste Y to tworzą pasmo L, nieparzyste ― pasmo H



przekształcenie jest odwracalne kosztem ekspansji alfabetu (o ile?)



Transformata odwrotna









+

−

=

+

+

+

2

2

2

2

1

2

1

2

n

n

n

n

X

X

X

Y

Transformata falkowa 5-3









+

+

−

=

+

−

4

2

1

2

1

2

2

2

n

n

n

n

X

Y

Y

X









+

+

=

+

+

+

2

2

2

2

1

2

1

2

n

n

n

n

X

X

Y

X









+

+

+

=

+

−

4

2

1

2

1

2

2

2

n

n

n

n

Y

Y

X

Y

Kwantyzacja współczynników
transformaty



Dla kompresji bezstratnej z krokiem 1



Dla stratnej

(U ― współczynniki przed kwantyzacją, V ― po kwantyzacji,

Δ ― krok kwantyzacji)



koder dobiera krok kwantyzacji tak, aby osiągnąć zadany współczynnik



krok dobierany jest dla każdego podpasma z osobna



jego wartość dołączana jest do zakodowanego obrazu



koder może stosować różne strategie doboru kroku kwantyzacji



kwantyzacja nie jest jedyną metodą kontroli współczynnika w JPEG2000





)

sgn(

/

U

U

V

⋅

∆

=

Kodowanie współczynników po
kwantyzacji



Etap 1.



Podpasma kafelka są dzielone na 

bloki kodowe

(przez nałożenie siatki

prostokątnej na kafelek po kwantyzacji), typowy rozmiar bloku to 64x64.



Blok kodowy dekomponowany jest na

płaszczyzny bitowe

(w kodowaniu

płaszczyzn mniej znaczących bitów uwzględnia się te bardziej znaczące)



Poszczególne bloki kodowe są kodowane niezależnie od siebie (MQ-Coder)



Kodowanie każdej z płaszczyzn bitowych wykonywane jest w trzech

przebiegach kodowania

(Significance/Refinement/Cleanup).



Wynikiem etapu 1 jest kolekcja ciągów bitów uzyskanych w przebiegach

kodowania płaszczyzn bitowych

bloków kodowych pasm komponentu po

kwantyzacji i DCT



Etap 1. pozwala na uwzględnienie preferencji kodowania (współczynnik

kompresji vs. szybkość/ odporność na błędy; ROI)

Kodowanie współczynników po
kwantyzacji



Etap 2.



Definiuje się

warstwy jakości

rekonstrukcji obrazu



przypisując poszczególnym warstwom przebiegi kodowania



warstwy mogą by warunkowo odrzucane



Przebiegi kodowania bloków kodowych grupowane są w

pakiety



Podpasma kafelka dzielone są na prostokątne obszary ―

precints



ograniczenie: każdy z bloków kodowych podpasma musi w całości zawierać się w jednym z

precints



sposób podziału podpasm na obszary precints jest zależny od poziomu rozdzielczości

odpowiadającego danemu podpasmu



pakiet zawiera wszystkie przebiegi kodowania płaszczyzn bitowych należące do danej warstwy

jakości danego precint



Pakiet opisuje dane obrazowe związane z konkretnym obszarem kafelka składowej,

konkretnym podpasmem (a więc poziomem rozdzielczości) i konkretną warstwą jakości.



Grupowanie zakodowanych płaszczyzn bitowych bloków kodowych w pakiety a

następnie określenie kolejności umieszczenia pakietów w strumieniu bitów umożliwia

transmisję progresywną względem jakości albo rozdzielczości

JPEG2000



UWAGA:

to był tylko zarys podstawowego standardu ...



... są również rozszerzenia standardu



uogólniona transformata falkowa



inna kwantyzacja



transformacje przestrzeni barw



inne ...

(standard liczy 200 stron a rozszerzenia standardu ― ponad 300)

Algorytm bazowy JPEG2000



Dlaczego JPEG2000 jest stratny?



przede wszystkim



kwantyzacja



odrzucanie pakietów wyższych warstw jakości



(podpróbkowanie składowych chrominancji jak w JPEG

można zrealizować za pomocą warstw jakości)



również nie-odwracalne



transformacja przestrzeni barw



DWT

Inne metody stosowane w
kompresji stratnej obrazów



Kodowanie predykcyjne



Kwantyzacja wektorowa



Kompresja fraktalna