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. YCrCb,

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 ... 2N  1] [ 2N  1 ... 2N  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 YCrCb
¨ð
Tylko do użycia z nie-odwracalną transformatą falkową (9-7)

RCT (Reversible Color Transform)
¨ð
stałopozycyjna aproksymacja ICT
¨ð
dla C1 i C2 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 28 x 28 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 ...
Transformata falkowa 5-3
¨ð
Transformata DWT, implementacja metodÄ… liftingu
(X  piksele wiersza przed transformatÄ…, Y  po transformacie, 2 koki: najpierw nieparzyste Y)
X + X Y2n- 1 + Y2n+ 1 + 2
ïÅ‚ śł ïÅ‚ śł
2n 2n+ 2
Y2n = X +
Y2n+ 1 = X -
2n
2n+ 1
ïÅ‚ śł
ïÅ‚ śł
4
2
ðÅ‚ ûÅ‚
ðÅ‚ ûÅ‚
¨ð
następnie parzyste Y to tworzą pasmo L, nieparzyste  pasmo H
L H
¨ð
przekształcenie jest odwracalne kosztem ekspansji alfabetu (o ile?)
¨ð
Transformata odwrotna
Y2n- 1 + X + 2 X + X
ïÅ‚ śł ïÅ‚ śł
2n+ 1 2n 2n+ 2
X = Y2n - X = Y2n+ 1 +
2n 2n+ 1
ïÅ‚ śł ïÅ‚ śł
4 2
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
Kwantyzacja współczynników
transformaty

Dla kompresji bezstratnej z krokiem 1

Dla stratnej
(U  współczynniki przed kwantyzacją, V  po kwantyzacji,
"  krok kwantyzacji)
V =
ðÅ‚U / " ûÅ‚Å" sgn(U )

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
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