Kompresja stratna
obrazów
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