Stratne metody kompresji
Potrzeba kompres i ogromnych ilości danych obrazowych zmusza do dalszych poszukiwań
efektywnie szych metod kompres i. Skuteczność metod odwracalnych w zastosowaniu do kompres i obrazów
okazu e się w wielu wypadkach niewystarcza ąca. Statystyczne metody są nieefektywne ze względu na brak
stac onarne statystyki. Histogram wyznaczony z wielu obrazów danego typu bardzo często est płaski. Metody
słownikowe z kolei napotyka ą te same problemy. Brak powtarza ących się długich sekwenc i w ciągu
kodowanych danych także znacznie ogranicza efekty kompres i.
Stratne metody kompres i reduku ące informac ę w stopniu dopuszczalnym dla konkretnych zastosowań
(zachowu ące podstawową naturę obrazu, istotne szczegóły, lub też wrażenie ciągłości obiektów) pozwala ą
uzyskać znacznie wyższe stopnie kompres i, sta ą się więc szansą znacznie korzystnie szego rozwiązania
zagadnienia kompres i obrazów danego typu.
Oryginalne ane obrazo e
Dekompozycja lub transformacja
K antyzacja
Ko o anie bito e
Skompreso ane ane obrazo e
Rys.1. Ogólny schemat algorytmu stratne kompres i.
Dwa pierwsze składniki, t . dekompozyc a lub transformac a oraz kwantyzac a wchodzą w skład
pierwsze fazy modelowania procesu kompres i. Kole ne fazie binarnego kodowania odpowiada składnik
kodowania symboli powyższego schematu. Znaczenie tych składników zmienia się w zależności od techniki.
Dekompozyc a obrazu lub transformac a wykonywana est w celu ograniczenia dynamiki danych obrazowych,
eliminac i nadmiarowości, a także by zapewnić taką reprezentac ę, która pozwoli na bardzie skuteczne
kodowanie. Poprzez kwantyzac ę zmnie sza się liczbę możliwych symboli. Rodza i stopień kwantyzac i ma
decydu ący wpływ zarówno na stopień kompres i, ak i poziom strat w procesie kompres i. Kwantyzac a powinna
być przeprowadzona także w taki sposób, by uzyskać optymalny kod wy ściowy. Według teorii informac i łączna
kwantyzac a sekwenc i zmiennych losowych, pomiędzy którymi występu e zależność, est zawsze lepsza od
niezależne kwantyzac i każde zmienne . Tak więc wektorowa kwantyzac a (VQ), eliminu ąca zależności
pomiędzy kole nymi zmiennymi losowymi, est skutecznie sza od kwantyzac i skalarne (SQ). Jedynie w
przypadku, gdy te zmienne losowe są niezależne ( eśli można e np. opisać wielowymiarowym rozkładem
Gaussa), zastosowanie SQ da e wyniki porównywalne z VQ. Zdekorelowany sygnał, otrzymany w wyniku
transformac i (np. KLT, DCT, wavelet) sygnału oryginalnego (z rzeczywistego obrazu), nie est niestety
niezależny, więc zastosowanie VQ do kwantyzac i wartości współczynników powinno zwiększyć efektywność
kompres i poprzez silnie sze 'uniezależnienie' danych. Jednak w praktyce zastosowanie VQ w algorytmach
kompres i napotyka na szereg problemów. Małe rozmiary bloków, t . 4� 4, nie są efektywne przy transformacy ne
kompres i. Jeśli natomiast uży emy bloków o większych rozmiarach, np. 8� 8 czy 16� 16, wówczas rozmiary
wektorów sta ą się zbyt duże dla praktycznych aplikac i VQ (gubione są szczegóły obrazu ze względu na
konieczność ograniczenia rozmiarów książki kodowe ). Złożoność VQ powodu e, że maksymalny rozmiar
wektora, pozwala ący na w miarę zadawala ącą rekonstrukc ę obrazu oryginalnego, wynosi 16-20. Przykładowo
Kuo i Hsu zwiększyli nieznacznie stopień kompres i obrazów niemedycznych przy danym poziomie zniekształceń
poprzez zastosowanie kwantyzac i wektorowe zamiast skalarne (przy podziale obrazu na bloki o rozmiarach
4� 4), a Wu i Coll zastosowali VQ w blokach 8� 8, ale edynie dla wolnozmiennych regionów obrazu. W
większości zastosowań VQ (w dziedzinie obrazu) do kompres i obrazów medycznych wykorzystu e się bloki o
rozmiarach 2� 2 i 2� 4.
Istnie ą dwa zasadnicze schematy skalarne kwantyzac i wartości współczynników transformaty w
blokach. Pierwszy z nich wykorzystu e strefową selekc ę próbek (zonal sample selection), zachowu ąc wartości
współczynników tylko w pewne strefie transformowanego bloku danych, przy czym dla pozostałych przy mowana
est wartość zero. Ponieważ większość obrazów ma dolnopasmowe spektrum częstotliwościowe, taki model
kwantyzac i pozwala zachować większość informac i zawarte w obrazie, usuwa ednak bezwzględnie
współczynniki wyższych częstotliwości.
Przy strefowe selekc i próbek stosowane są dwa modele kwantyzac i, przy czym pierwszy z nich
zakłada stałą średnią liczbę bitów wyraża ącą skwantowane wartości współczynników, drugi natomiast zmienną.
W pierwszym modelu kwantyzac a est zwykle równomierna, a liczbę bitów zapisu wartości kole nych
współczynników (i związaną z nią liczbę poziomów kwantyzac i) można przy ąć a priori (dużą dla niskich i małą
dla wysokich częstotliwości). Stosu e się także adaptacy ny przydział różne ilości bitów współczynnikom w
zachowywane strefie (przy stałe całkowite liczbie bitów), minimalizu ąc błąd kwantyzac i. Wymaga to ednak
dwukrotnego przeglądania danych, kiedy to na pierw wyznaczana est średnia warianc a dla każde pozyc i
współczynnika w bloku obrazu, a potem przydzielana est liczba bitów do zapisu skwantowanych wartości
proporc onalnie do logarytmu warianc i każdego współczynnika. Konieczne est wówczas umieszczenie macierzy
przydziału bitów w skompresowanym pliku danych (rozmiar macierzy est proporc onalny do poziomu
adaptacy ności).
Przykładem może być rozwiązanie, w którym w zależności od całkowite warianc i (energii) bloki dzielone
są na klasy, następnie dla każde z klas obliczana est macierz przydziału bitów i rozmiar strefy. Oczywiście
wszystkie informac e o klasach muszą być przesłane do dekompresora.
W drugim modelu kwantyzac i ze strefową selekc ą próbek stosu e się na częście nierównomierny
optymalny (w sensie minimalnego średniokwadratowego błędu kwantyzac i) kwantyzator Lloyda-Maxa,
pro ektowany dla każdego współczynnika, przy czym zerowy współczynnik (składowa stała) est modelowany
na częście rozkładem Rayleigha, a pozostałe współczynniki rozkładem Gaussa lub Laplace'a. Liczba poziomów
kwantyzac i est ustalana proporc onalnie do logarytmu (o podstawie 2) warianc i tych rozkładów.
Wszystkie te metody, wykorzystu ące nawet na bardzie złożone modele statystyczne rozkładu wartości
współczynników w blokach, ma ą podstawową wadę, którą est mała adaptacy ność. Wszelkie próby przydziału
bitów, w zależności od globalne czy lokalne statystyki, wprowadza ą strefową selekc ę próbek, eliminu ąc rzadko
występu ące, wysokoczęstotliwościowe składowe obrazu.
Drugim schematem kwantyzac i est progowa selekc a próbek (threshold sample selection). Pozwala ona
na wyeliminowanie na większe wady strefowego schematu selekc i prze awia ące się w możliwości pominięcia
wartości współczynnika zawiera ącego znaczącą energię, który znalazł się poza zachowywaną strefą, co może
powodować duży błąd rekonstrukc i. Dobiera się bowiem poziom progu, powyże którego współczynniki podlega ą
kwantyzac i i kodowaniu, przy czym powsta e problem pamiętania pozyc i współczynników, które przekracza ą
wartość progu w każdym bloku. Do zakodowania pozyc i używa się na częście technik kodowania długości
sekwenc i. W schemacie z progową selekc ą stosu e się zarówno równomierne ak i nierównomierne modele
kwantyzac i, z technikami entropi nego kodowania dla równomierne kwantyzac i. Struktura kwantyzatora może
być także skonstruowana ako funkc a położenia poszczególnych współczynników w bloku. Dla uproszczenia taka
tablica kwantyzac i może być stosowana dla wszystkich bloków w obrazie, przy czym może być całościowo
przeskalowana w celu osiągnięcia różnych stopni kompres i z ednoczesną zmianą błędu kwantyzac i i poziomu
zniekształceń w rekonstruowanym obrazie. Wartości występu ące w tablicy kwantyzac i winny być związane z
funkc ą czułości kontrastu HVS i odpowiadać zmianom psychowizualnym, bądz
innym zmianom (np. w wartości
diagnostyczne ) wprowadzanym przez błąd kwantyzac i poszczególnych współczynników.
Ostatni etap kodowania skwantowanych danych sprowadza się do zastosowania możliwie efektywne
techniki odwracalne . Zasadniczo każdy ze składników schematu stratne kompres i może być zaimplementowany
w wers i adaptacy ne i nieadaptacy ne schematu. Algorytm kompres i est adaptacy ny eśli struktura składników,
bądz
ich parametrów zmienia się lokalnie w ramach obrazu wykorzystu ąc zmienność lokalne statystyki.
Adaptacy ność pozwala na zwiększenie efektywności kosztem wzrostu stopnia złożoności schematu kodu ącego,
może też występować w wers i przyczynowe i nieprzyczynowe .
Standard JPEG
Specyfikac a normy standardu JPEG zawiera:
" opis procesu przetwarzania z
ródłowych danych obrazowych w dane obrazowe skompresowane;
" opis procesu przetwarzania skompresowanych danych obrazowych w zrekonstruowane dane obrazu;
" wskazania dotyczące praktycznych implementac i standardu;
" opis zakodowane reprezentac i skompresowanych danych obrazowych.
Specyfikac a nie opisu e kompletne zakodowane reprezentac i obrazu, może ona zawierać pewne parametry
zależne od aplikac i. W normie zna du ą się cztery techniki kompres i, a mianowicie:
1. Podstawowy proces kodowania (baseline process).
2. Rozszerzony , bazu ący na DCT proces kodowania (extended DCT- based process).
3. Bezstratny proces kodowania (lossless process).
4. Hierarchiczny proces kodowania (hierarchical process).
Kodowanie każdego składnika obrazu (luminanc a, składowe chrominanc i) przebiega analogicznie. W
podstawowym procesie kodowania dane we ściowe muszą być ośmiobitowe. Obraz est dzielony na bloki 8x8 i
każdy blok est transformowany za pomocą DCT, przy czym kodowanie obrazu przebiega sekwency nie, tzn. z
lewe strony na prawą zaczyna ąc od góry obrazu i przemieszcza ąc się na dół. Obliczone 64 współczynniki z
każdego bloku podlega ą kwantyzac i. Każdy ze współczynników est dzielony przez odpowiada ącą mu wartość
w tablicy kwantyzac i. Tablicę tę można dobrać w zależności od aplikac i. Współczynniki są następnie ustawiane
w ednowymiarowy ciąg danych według sekwenc i zygzak. Tak uszeregowane dane z poszczególnych bloków są
następnie kodowane, przy czym składową stałą kodu e się różnicowo, tzn. kodu e się edynie różnicę pomiędzy
wartością składowe stałe obecnego bloku i poprzedniego. Do kodowania używa się kodu Huffmana, przy czym
tablica Huffmana nie est ob ęta normą.
Rys.2. Schemat blokowy algorytmu kompres i wykorzystu ącego DCT.
Proces dekompres i przebiega dokładnie odwrotnie, przy czym dekoder musi posługiwać się dokładnie
tymi samymi tablicami specyfikac i (tablica kwantyzac i, Huffmana). Umożliwia to format zapisu, w którym tablice
specyfikac i poprzedzone odpowiednimi markerami umieszczone są w pliku razem z danymi skompresowanymi.
Dokładny opis formatu zna du e się w normie.
Rozszerzony proces kompres i umożliwia kompres ę zarówno 8- mio ak i 12- to bitowych danych, przy
czym kodowanie może być nie tylko sekwency ne, ale i progresywne. W modzie progresywnym poszczególne
bloki współczynników są kodowane w te same kole ności, ale w wielu skanach dzielących współczynniki
każdego bloku na poszczególne pasma. Związane est to ednak z zapewnieniem dodatkowego bufora pamięci
do przechowania wartości współczynników z całego obrazu po fazie kwantyzac i, a przed statystycznym
kodowaniem tych wartości. Są one następnie kole no kodowane w skanach zbiera ących wartości w określonym
paśmie ze wszystkich bloków.
W normie występu ą dwa rodza e procedur progresywnego kodowania. Pierwsza, nazywana selekc ą
widma, dzieli współczynniki ustawione według sekwenc i zygzak na kole ne pasma, które zawiera ą poszczególne
części częstotliwościowego spektrum każdego z bloków. Druga procedura związana est z precyz ą, z aką
kodowane są współczynniki w każdym z pasm i nazywana est sukcesywną aproksymac ą. Na pierw kodowana
est pewna liczba bardzie znaczących bitów wartości tych współczynników, a następnie mnie znaczące bity.
Można progresywnie kodować współczynniki edynie przy pomocy procedury selekc i widma, ak też z
wykorzystaniem obu procedur. Wówczas mamy do czynienia z tzw. pełną progres ą. Ze stwierdzeń zawartych w
opisie normy wynika, że zastosowanie selekc i widmowe , akkolwiek wygodne dla wielu zastosowań, da e
porównywalne bądz
nieco gorsze wyniki kompres i niż sekwency na metoda kodowania, podczas gdy przy pełne
progres i skuteczność kompres i może się okazać nieco większa.
W rozszerzonym procesie kodowania możliwe est także arytmetyczne kodowanie, a tablica warunków
(conditioning table) est wówczas zapamiętywana ako tablica specyfikac i.
Proces kodowania bezstratnego u ęty w standardzie nie wykorzystu e DCT, lecz polega na
predyktywnym kodowaniu wartości piksela na podstawie trzech wartości pikseli sąsiednich. Dla danego skanu
można wybrać edną z ośmiu predykc i przedstawionych na rys. 3. Następnie oblicza się różnicę pomiędzy
wartością przewidywaną Px, a rzeczywistą wartością piksela i kodu e się otrzymaną różnicę odpowiednio
dostosowaną metodą Huffmana lub arytmetycznie. W metodzie Huffmana stosu e się 17 kategorii różnicowych
wartości, a w kodowaniu arytmetycznym budu e się dwuwymiarowy model statystyczny.
Numer
Pre ykcja
0 Bez pre ykcji
1 Px=Ra
c b
2 Px=Rb
3 Px=Rc
a x
4 Px=Ra Rb-Rc
5 Px=Ra ((Rb-Rc)/2)
6 Px=Rb ((Ra-Rc)/2)
7 Px=(Ra Rb)/2
Rys.3. Przestrzenna relac a pomiędzy pikselami (a,b,c), których wartości służą do wyznaczania wartości
przewidywane w pikselu x. Obok rodza e predykc i dla bezstratnego kodowania.
Predykc a 0 może być używana dla różnicowego kodowania w modzie hierarchicznym, 1,2 i 3 to predykc e
ednowymiarowe wykorzystywane głównie na skra u obrazów, podczas gdy predykc e 4-7 są dwuwymiarowe.
Można tą metodą odwracalnie kodować od 2 do 16 bitowe wartości pikseli obrazu. Można więc go z łatwością
implementować do kompres i szerokie klasy obrazów.
Hierarchiczny proces kodowania polega na kompres i obrazu poprzez zakodowanie sekwenc i kadrów
tego obrazu (różnicowo lub nieróżnicowo) o różne rozdzielczości za pomocą rozszerzonego procesu kodowania
(wykorzystu ącego DCT) lub metody bezstratne . Można także połączyć te dwie metody i po kodowaniu opartym
na DCT w ostateczne fazie zastosować kodowanie bezstratne (bez fazy kwantyzac i). Wówczas
zrekonstruowany obraz różni się od oryginalnego edynie wskutek błędów przybliżeń wartości DCT i IDCT .
Tworzy się zrekonstruowane składniki odniesienia obrazu różne rozdzielczości i kodu e się różnice
pomiędzy obrazem oryginalnym a tymi składnikami odniesienia. Stosowanie filtrów próbku ących obraz
oryginalny z różną rozdzielczością tworzy charakterystyczną piramidę przestrzenne rozdzielczości.
Mod hierarchiczny może być stosowany alternatywnie, aby zwiększyć akość rekonstruowanych
składników obrazu o dane rozdzielczości. Oferu e progresywną prezentac ę czy transmis ę, ale est na częście
użyteczna edynie w systemach posługu ących się wielorozdzielczymi wers ami danych obrazów.
Standard MPEG
Od 1988 roku nad standardem kompres i sekwenc i obrazów pracu e grupa znana ako MPEG (Moving
Picture Experts Group). W ramach ISO-IEC/JTC1/SC2/WG11 opracowała ona standard dla gromadzenia i
odtwarzania ruchomych obrazów i dz
więku na różnych nośnikach cyfrowych z szybkością 1-1.5 mbitów/s. W
1992 roku ostatecznie został przy ęty standard, znany ako MPEG-1 (dotyczący głównie aplikac i dla transmis i
prowadzonych z szybkością około 1,2 megabitów/s - prędkość CD-ROM). W roku 1994 zakończono prace nad
pro ektem standardu MPEG-2 dotyczącym telewiz i interakcy ne oraz telewiz i wysokie rozdzielczości HDTV,
nieco póz
nie opracowano standard MPEG-4 dla silne kompres i obrazów (bardzo małe średnie bitowe) w
wideotelefonii, baz danych obrazów wideo itp. Opracowu ąc normy MPEG poszukiwano kompromisu pomiędzy
efektywnością algorytmu (tak aby można było osiągać dla sekwenc i wyższe stopnie kompres i, niż w kompres i
każdego obrazu z osobna) a swobodą dostępu do dowolne ramki w sekwenc i (na proście est w przypadku
oddzielne redukc i danych w każdym z obrazów w sekwenc i). W algorytmie MPEG niektóre obrazy w sekwenc i
kodowane są ednoobrazowo, inne zaś międzyobrazowo, przy czym występu ą dwa rodza e kodowania
międzyobrazowego: predykcy ny i interpolacy ny. Algorytm MPEG kompres i sekwenc i obrazów opiera się na
dwóch podstawowych technikach:
" blokowe kompensac i ruchu dla redukc i nadmiarowości czasowych,
" opartym na transformacie kosinusowe (DCT) schemacie stratne kompres i dla redukc i nadmiarowości
przestrzennych (wewnątrzobrazowych).
Techniki kompensac i ruchu są realizowane za pomocą modelu predykatora przyczynowego (kodowanie
predyktywne) lub nieprzyczynowego (kodowanie interpolacy ne), przy czym określa się postać estymatorów
ruchu dla bloków 16� 16. Parametry tych estymatorów są transmitowane (lub zapisywane) razem z informac ą
przestrzenną (po zakodowaniu przy pomocy metod o zmienne długości kodu). Błędy predykc i są następnie
kompresowane z wykorzystaniem techniki oparte na DCT.
Redukcja nadmiarowości międzyobrazowych
W sekwenc i MPEG występu ą trzy typy kadrów:
" Obrazy kodowane ednoobrazowo (I - intrapictures), wykorzystywane ako odniesienie do predykc i i
interpolac i pozostałych obrazów.
" Kadry predykcy ne (P - predicted) są kodowane względem poprzednich obrazów (I lub P) oraz są używane
ako kadry referency ne dla kadrów następnych.
" Kadry interpolowane (B - bidirectional prediction), pozwala ą uzyskać na silnie szą kompres ę, ale wymaga ą
zarówno kadrów odniesienia spośród obrazów poprzedza ących ak i następnych (kadry I i P). Kadry
interpolowane nie są nigdy wykorzystywane ako referency ne.
Organizac a obrazów est elastyczna i może być dostosowana do wymagań konkretnych aplikac i.
Relac e pomiędzy trzema rodza ami kadrów przedstawia rys. 4.
Predykcja
I
B
B
B
P
B
B
B
Interpolacja
I
Rys. 4. Schemat międzyobrazowego kodowania w MPEG.
Estymacja ruchu
We wszystkich przypadkach, kiedy obraz est kodowany z uwzględnieniem kadru odniesienia, w celu
poprawy skuteczności kompres i, stosowana est estymac a ruchu. Polega ona na wyekstrapolowaniu z sekwenc i
obrazów informac i o ruchu określonych obiektów. Standard MPEG określa sposób reprezentac i informac i o
ruchu ako eden lub dwa wektory ruchu (w zależności od rodza u predykc i) przypada ące na po edynczy obiekt,
którym est blok o rozmiarach 16� 16. Natomiast standard nie specyfiku e sposobu wyznaczania tych wektorów.
Kompensacja ruchu
Na częście stosowaną techniką redukc i nadmiarowości w sekwenc i obrazów est predykc a.
Kompensac a ruchu poprzez predykc ę zakłada, że "lokalnie" bieżący obraz może być modelowany ako
translac a poprzedniego obrazu w sekwenc i. Informac a o ruchu est częścią informac i konieczne do
odtworzenia obrazu ze skompresowane reprezentac i.
Kompensac a ruchu przez interpolac ę pozwala poprawić mechanizm dostępu do dowolnie wybranego
kadru z sekwenc i, zredukować wpływ błędów transmis i oraz szumu. Jednocześnie można osiągnąć wzrost
efektywności kompres i dzięki lepszemu mechanizmowi przewidywania, uwzględnia ącemu zmiany informac i
zawarte w obrazach po awia ących się w sekwenc i póz
nie . Aby zwiększyć elastyczność techniki kompres i
sekwenc i obrazów, dla każdego bloku 16� 16 w kadrach interpolowanych możliwy est wybór ednego z czterech
typów predykc i (brak predykc i, predykc a wprzód, predykc a w tył, interpolac a) przedstawionych w tabeli 1.
_
TABELA 1. Typy predykc i stosowane w MPEG; oznaczenia: x - współrzędne elementu obrazu, mv01 - wektor
ruchu w odniesieniu do obrazu I0 , - wektor ruchu w odniesieniu do obrazu I2 .
21
Typ bIoku Predykator Błąd predykcji
^
^
Brak predykc i
I1(x) - I (x)
1
I (x) = 128
1
^
^ ^
Predykc a wprzód
I1(x) - I (x)
1
I (x) = I (x + mv01)
1 0
^
^ ^
Predykc a w tył
I1(x) - I (x)
1
I (x) = I (x + mv21)
1 2
^
^^ ^
Interpolac a
1
I1(x) - I (x)
1
I (x) = [I (x +mv01) + I (x +mv21)]
10 2
2
Informac a o ruchu dla każdego bloku est kodowana różnicowo względem informac i wyznaczone w
bezpośrednio poprzedza ącym bloku. Zakres danych opisu ących różnicowe wektory ruchu są dobierane dla
konkretne aplikac i - charakteru sekwenc i obrazów, ich rozdzielczości, rodza u zare estrowanego ruchu i est
bezpośrednio związany z założonym obszarem poszukiwań optymalnego estymatora ruchu dla każdego bloku.
Redukcja nadmiarowości przestrzennych
Kodowanie obrazów oryginalnych i różnicowych (z predykc i) oraz składowych obrazu (luminanc a,
składowe chrominanc i) przebiega podobnie. W podstawowym schemacie kompres i ośmiobitowe dane
we ściowe dzielone są na bloki 8x8, w których niezależnie obliczana est DCT. Współczynniki transformaty z
każdego bloku podlega ą równomierne kwantyzac i, a następnie uszeregowaniu według sekwenc i zygzak i
kodowaniu. Do kodowania używa się zmodyfikowane metody Huffmana (w połączeniu z metodą kodowania
długości sekwenc i).
4. Wybrane techniki stratnej kompresji
Stratne kodowanie predykcyjne (Lossy Predictive Coding)
W algorytmach DPCM wyznaczona przez model predykc i wartość est ode mowana od rzeczywiste
wartości kole nych pikseli tworząc obraz różnicowy o dużo mnie sze korelac i pomiędzy wartościami pikseli niż
obraz oryginalny. W stratne DPCM obraz różnicowy podlega procesowi kwantyzac i, który ma decydu ący wpływ
zarówno na stopień kompres i ak i na akość rekonstruowanego obrazu.
W procesie dekompres i predykc a może być oparta edynie na zrekonstruowanych wartościach pikseli,
które mogą różnić się od rzeczywistych wartości wskutek redukc i informac i przeprowadzone podczas
kwantyzac i. By zapewnić identyczną predykc ę podczas kompres i i dekompres i, w czasie kodowania także
korzysta się ze zrekonstruowanych wartości pikseli do określania przybliżeń, co prowadzi do umieszczenia etapu
kwantyzac i w pętli predykc i. Przedstawia to rys.5.
KOMPRESJA
Zako o ane
Obraz
ane obrazo e
oryginalny
Ł K antyzacja Ko o anie
-
Pre ykcja Ł
DEKOMPRESJA
Zako o ane Obraz
ane obrazo e zrekonstruo any
Deko o anie
Ł
Pre ykcja
Rys.5. Blokowy schemat stratne techniki DPCM.
Pro ektowanie efektywnych algorytmów DPCM sprowadza się do optymalizac i procesu predykc i oraz
kwantyzac i. Ze względu na umieszczenie kwantyzac i w pętli predykc i istnie e silna zależność pomiędzy błędem
predykc i i błędem kwantyzac i i na lepsza w tym przypadku połączona optymalizac a prowadzi do złożonych
modeli. Uniknąć ich można poprzez oddzielną optymalizac ę obu procesów, która est dobrą aproksymac ą
połączone według kryterium błędu średniokwadratowego.
Stosu e się predykc ę różnych rzędów, edno- i dwuwymiarową, globalną, lokalną i adaptacy ną.
Predykc a 2D da e lepsze rezultaty przy kompres i obrazów w stosunku do metod 1D zarówno w ocenie ilościowe
(stosunek sygnału do szumu rośnie o około 3 dB), ak też w wyraz
ne subiektywne poprawie akości obrazów,
wyraża ące się głównie w mnie szych zniekształceniach ukośnych krawędzi.
Proces kwantyzac i może być pro ektowany przy użyciu wizualnych bądz
statystycznych kryteriów. Do
typowych zniekształceń wprowadzanych w procesie kwantyzac i należą: ziarnisty szum, a także zniekształcenia
ostrych (slope overload) i łagodnych krawędzi (edge busyness). Szum ziarnisty po awia się w ednolitych
obszarach, gdzie niewielkie zmiany wartości sąsiednich pikseli powodu ą fluktuac e na wy ściu kwantyzatora.
Zniekształcenia konturów w mie scach występowania ostrych zboczy sygnału 2D, takie ak ich rozmycie i nieraz
dodatkowa degradac ę obrazu w ich sąsiedztwie) w wyniku kwantyzac i związane est z faktem, iż gradient
przyrostu wartości wy ściowych kwantyzac i nie nadąża za dużym gradientem danych obrazowych. Natomiast
zniekształcenia łagodnych krawędzi (przesuwanie, odkształcanie) spowodowane są fluktuac ą procesu
kwantyzac i. Rysunek 6 zawiera schematyczne zobrazowanie tych zniekształceń.
Sygnał
Zniekształcenie
oryginalny
ostrych zboczy
Sygnał
rekonstruowany
Szum
ziarnisty
Zniekształcenie
krawędzi łagodnych
Rys.6. Typowe zniekształcenia występu ące w technice DPCM.
Adaptacy ność technik DPCM może być realizowana w dziedzinie predykc i, kwantyzac i lub w obydwu.
Adaptacy na predykc a zwykle reduku e błąd predykc i przed fazą kwantyzac i, co powodu e że przy tym samym
stopniu kompres i zmnie szona dynamika sygnału na we ściu kwantyzatora powodu e mnie szy błąd kwantyzac i i
lepszą akość rekonstruowanego obrazu.
Z drugie strony adaptacy na kwantyzac a ma na celu zmnie szenie błędu kwantyzac i bezpośrednio
przez dobór progów kwantyzac i i poziomów rekonstrukc i zgodnie z lokalną statystyką obrazu.
Choć techniki predykcy ne typu DPCM były historycznie pierwszymi stosowanymi technikami kompres i
ze stratą informac i i wprowadzone póz
nie metody transformat ortogonalnych okazały się efektywnie sze, to
ednak predykc a ako metoda nie straciła swego znaczenia. Zwiększa ona efektywność zarówno hybrydowych
technik transformacy nych, ak i rozwi anych ostatnio technik filtrów hierarchicznych.
Metody transformacji ortogonalnych
Ogólny schemat technik kompres i zwanych metodami transformac i ortogonalnych (transform encoding
- TE) zawiera na częście podział obrazu o rozmiarach N � N na mnie sze bloki n � n i wykonanie ednolite
(unitary) transformac i każdego z tych bloków. Jednolita transformata est odwracalną liniową transformatą, które
ądro opisu e zbiór zupełny ortonormalnych dyskretnych funkc i bazowych. Celem transformac i est usunięcie
korelac i występu ących w obrazie oryginalnym. Dekorelac ę osiąga się zasadniczo przez fakt, iż po transformac i
energia sygnału (2-D) zawarta est edynie w niewielkie liczbie współczynników transformaty. Umożliwia to
efektywną kompres ę wskutek usunięcia wielu wartości pozostałych współczynników w procesie kwantyzac i, bez
większego wpływu na akość rekonstruowanego obrazu. Odpowiedni dobór współczynników kwantyzac i
(uwzględnia ący funkc ę czułości kontrastu) pozwala często uzyskać przy pomocy techniki transformacy nych
wizualnie bezstratną kompres ę.
Podstawowy schemat blokowy metod transformac i ortogonalnych przedstawiony est na rys.7.
KOMPRESJA
Kod
Obraz
Podział na Kwantyzacja wyjściowy
oryginalny
Transformacja
bloki n n i kodowanie
DEKOMPRESJA
Kod Obraz
wejściowy zrekonstruowany
Dekodowanie Transformata A
ączenie
i rekonstrukcja odwrotna bloków n n
Rys.7. Blokowy schemat kompres i metod transformac i ortogonalnych.
2-D transformac e stosowane do kompres i obrazów są rozłączne, tzn. ądro transformaty może ulec
dekompozyc i na dwa 1-D ądra wyszczególnia ące rozłączne horyzontalne i wertykalne operac e. Stąd też 2-D
transformac a na bloku � pikseli może być wykonana w dwu krokach, 1-D n-punktowe transformac i wzdłuż
każdego wiersza w bloku, a następnie 1-D n-punktowe transformac i wzdłuż każde kolumny należące do
danego bloku.
N-punktowa transformac a może być interpretowana w dwo aki sposób. Albo ako obrót n-wymiarowego
układu współrzędnych, definiowany przez wartości pikseli z bloku obrazu, transformu ący wektor oryginalny w
równoważny wektor o lepsze podatności na kompres ę, albo ako dekompozyc a oryginalnego bloku obrazu w
zbiór n ortogonalnych funkc i bazowych, których współczynniki są kształtowane przez wartości pikseli w tym
bloku.
Do na bardzie pożądanych cech ortogonalne transformac i stosowane w algorytmach kompres i należą:
1) całkowita dekorelac a danych obrazowych, co oznacza upakowanie na większe ilości energii w na mnie sze
liczbie współczynników;
2) niezależne od rodza u obrazu funkc e bazowe, tzn. zastosowanie zbioru funkc i bazowych, który da e
optymalne (w znaczeniu wysokie dekorelac i) wyniki niezależnie od statystyki danych obrazowych,
szczególnie istotne gdy bloki obrazów są silnie niestac onarne;
3) szybka implementac a, czyli szybkie algorytmy zmnie sza ące liczbę operac i wyliczania transformaty z P(n2 )
do P(n�"log n), co dla rozłącznych 2-D transformat zmnie sza liczbę operac i z P(n4 ) do P(2n2 log n). Zapis
P(x) oznacza proporc onalnie do x.
Optymalną transformac ą z punktu widzenia pierwsze cechy est transformata Karhunen-Loeve'go -
KLT, tzn. określona liczba współczynników transformaty zawiera większą część całkowite energii sygnału niż w
akie kolwiek inne transformacie. Niestety zbiór funkc i bazowych KLT zależy od statystyki obrazu, a estymac a
funkc i korelac i obrazu est obliczeniowo kosztowna, przy czym szybkie algorytmy obliczania KLT nie istnie ą.
Spośród pozostałych transformat edynie dyskretna kosinusowa transformata (DCT) w zastosowaniu do
typowych obrazów o duże korelac i wartości pikseli da e efektywność praktycznie nie różniącą się od KLT.
Zamodelowanie korelac i pomiędzy wartościami sąsiednich pikseli w obrazie za pomocą z
ródła Markowa
pierwszego rzędu i sklasyfikowanie transformat ortogonalnych według takich kryteriów ak rozkład warianc i
współczynników (wprost proporc onalne do zawarte informac i), efektywność upakowania energii, resztkowa
korelac a (miara korelac i aka pozostała w przestrzeni transformaty) oraz stopień zniekształceń przy
maksymalne redukc i bitów doprowadziło do stwierdzenia, iż według każdego z tych kryteriów DCT est
transformac ą optymalną.
Podobnie funkc e bazowe DCT pokrywa ą się ze zbiorem funkc i bazowych KLT danych obrazowych
przy takim samym modelu obrazu. Ponadto istnie ą szybkie algorytmy bezpośredniego obliczania DCT, ak też z
wykorzystaniem algorytmów FFT.
W pewnych aplikac ach zna du ą zastosowanie także inne transformaty, takie ak chociażby dyskretna
transformata sinusowa (DST), która w pewnych modelowych sytuac ach est identyczna z KLT, używana w
technice rekursywnego kodowania bloków (recursive block coding) zmnie sza ące efekt artefaktów powsta ących
na granicy bloków, dyskretna transformata Fouriera (DFT), głównie ze względu na powszechność zastosowań
szybkich algorytmów transformac i, czy też transformata Walsh-Hadamard'a (WHT), akkolwiek skromna w
możliwościach dekorelac i, ze względu na prostą implementac ę stała się ednak popularna w hardware'owych
zastosowaniach.
Kwantyzacja współczynników transformat
Obok przeprowadzenia efektywne transformac i na blokach obrazu oryginalnego o odpowiednio
dobranych rozmiarach w technikach TE istotnym est także proces kwantyzac i współczynników
transformaty, które są następnie kodowane.
Istnie ą dwa główne pode ścia do schematu kwantyzac i. Strefowa selekc a próbek (zonal
sample selection) zachowu e wartości współczynników tylko w pewne strefie transformowanego bloku
danych, przy czym wartości pozostałych sprowadza do zera. Ponieważ większość obrazów ma
dolnopasmowe spektrum częstotliwościowe taki model kwantyzac i pozwala zachować większość
informac i zawarte w obrazie, usuwa ednak bezwzględnie współczynniki wysokoczęstotliwościowe.
Można stosować stałą liczbę bitów dla skwantowanych wartości (np. 8 bitów dla dwóch
na niższych częstotliwości i 6 dla pozostałych) lub też zmienną liczbę bitów w zależności od statystyki
amplitud współczynników w blokach (mnie szy błąd kwantyzac i). Wymaga to ednak dwukrotnego
przeglądania danych, kiedy to na pierw wyznaczana est średnia warianc a dla każde pozyc i
współczynnika w bloku obrazu, a potem przydzielana est liczba bitów do zapisu kwantowanych
wartości proporc onalnie do logarytmu warianc i każdego współczynnika. Koniecznym est wówczas
umieszczenie macierzy przydziału bitów w skompresowanym pliku.
Większą efektywnością charakteryzu ą się adaptacy ne odmiany takich algorytmów, które w
zależności od różne lokalne statystyki w poszczególnych blokach, na pierw w zależności od całkowite
warianc i (energii) bloku dzielą e na klasy, po czym dla każde z klas obliczana est macierz przydziału
bitów i rozmiar strefy. Oczywiście wszystkie informac e o klasach muszą być przesłane do
dekompresora.
W powyższych metodach każdy współczynnik ma przydzieloną stałą liczbę bitów (w całym
obrazie bądz
ego części). Skutecznie szą kompres ę można osiągnąć stosu ąc kody o zmienne
długości. Jest to spowodowane faktem, iż zazwycza rozkład amplitud współczynników nie est
ednosta ny i można go zamodelować rozkładem Gaussa lub Laplace'a. Można następnie stosu ąc np.
równomierną kwantyzac ę o odpowiednio dobranych progach oraz kodowanie arytmetyczne lub
Huffmana skwantowanych wartości współczynników utworzyć skompresowany zbiór danych
reprezentu ących archiwizowany obraz.
Drugim schematem kwantyzac i est progowa selekc a próbek (threshold sample selection).
Pozwala ona na wyeliminowanie na większe wady strefowego schematu selekc i prze awia ące się w
możliwości pominięcia wartości współczynnika zawiera ącego znaczącą energię, który znalazł się poza
zachowywaną strefą, co może powodować duży błąd rekonstrukc i. Dobiera się bowiem poziom progu,
powyże którego współczynniki podlega ą kwantyzac i i kodowaniu, przy czym powsta e problem
pamiętania pozyc i współczynników, które przekracza ą wartość progu w każdym bloku. Do
zakodowania pozyc i używa się na częście technik kodowania długości sekwenc i.
W schemacie tym stosu e się zarówno równomierne ak i nierównomierne modele kwantyzac i, z
technikami entropi nego kodowania dla równomierne kwantyzac i.
Struktura kwantyzatora może być także skonstruowana ako funkc a położenia poszczególnych
współczynników w bloku. Dla uproszczenia taka tablica kwantyzac i może być stosowana dla wszystkich
bloków w obrazie, przy czym może być całościowo przeskalowana w celu osiągnięcia różnych stopni
kompres i z ednoczesną zmianą błędu kwantyzac i i poziomu zniekształceń w rekonstruowanym
obrazie. Wartości występu ące w tablicy kwantyzac i winny być związane z funkc ą czułości kontrastu
HVS i odpowiadać zmianom psychowizualnym, bądz
innym zmianom (n.p. w wartości diagnostyczne )
wprowadzanym przez błąd kwantyzac i poszczególnych współczynników.
Blokowa dwupoziomowa kwantyzacja
W technice blokowe dwupoziomowe kwantyzac i (Block Truncation Coding - BTC) obraz est
dzielony na niepokrywa ące się bloki pikseli o rozmiarach n � n (na częście 4 � 4). Następnie
niezależnie dla każdego bloku przeprowadza się binarną kwantyzac ę wartości pikseli dobiera ąc próg
odpowiednio do lokalne statystyki bloku. Powsta ąca wówczas reprezentac a poszczególnych bloków
składa się z binarne mapy � wskazu ąca poziom rekonstrukc i dla każdego piksela oraz z dwu
wartości rekonstruowanych poziomów. Dekompres a est więc prostym procesem rekonstruowania
wartości pikseli według dostarczone binarne mapy poziomów.
Na prostszym sposobem określenia progu est obliczenie średnie wartości piksela w bloku, a
następnie średnie wartości segmentów wyznaczonych przez wartość progową mogą posłużyć ako dwie
wartości poziomów rekonstrukc i. Z te podstawowe realizac i wynika ą główne zalety i wady techniki
BTC.
Główną zaletą est zachowanie dokładne odtworzenie ostrych krawędzi w zrekonstruowanym
obrazie, podczas gdy większość stratnych metod kompres i powodu e rozmycie ostrych krawędzi. Wady
związane są przede wszystkim z wprowadzaniem artefaktów polega ących na zniekształcaniu
łagodnych konturów wewnątrz bloków, spowodowanych gwałtownym skokiem pomiędzy wartościami
poziomów rekonstrukc i, oraz wprowadzaniu nieciągłości krawędzi na granicach bloków wynika ących z
niezależnego przetwarzania sąsiednich bloków.
Optymalizac a techniki BTC odbywa się w trzech zasadniczych kierunkach. Konstruu e się
bardzie złożone modele kwantyzac i wykorzystu ąc trzy stopnie swobody (próg i dwie wartości
poziomów rekonstrukc i). Niektóre z nich zachowu ą trzy centralne momenty statystyczne (wartość
średnia, warianc a, asymetria), inne wprowadza ą element minimalizac i błędu średniokwadratowego.
Ponadto stosu e się wiele technik do kodowania map binarnych oraz poziomów rekonstrukc i.
Zamiast wartości poziomów kodu e się często wartość średnią i odchylenie standardowe bloku przy
pomocy dwuwymiarowe kwantyzac i (joint quantization) lub kwantyzac i wektorowe , powodu ąc
dodatkową stratę informac i w bloku, lecz zwiększa ąc znacznie efektywność kompres i. Kodowanie
mapy binarne można w ogóle pominąć, podobnie ak warianc i w przypadku, gdy warianc a danego
bloku est mała. Wówczas do strumienia wy ściowego zostanie przesłana edynie wartość średnia. Dla
wyższych wartości warianc i kodowanie mapy bitowe może odbywać się przy pomocy różnego rodza u
technik. Do często stosowanych należą techniki wyznacza ące w mapie i kodu ące edynie bity
niezależne oraz kwantyzac a wektorowa.
Opracowano także metody adaptacy ne w odniesieniu do wielkości bloków. Przystosowu ąc się
do lokalnych statystycznych własności obrazów można zmnie szać lub zwiększać rozmiary bloków
zwiększa ąc skuteczność kompres i. Wprowadza się także próby likwidac i niekorzystnych efektów
powsta ących na granicy bloków.
Wektorowa kwantyzacja.
Pierwszym krokiem w technice kompres i zwane kwantyzac ą wektorową (vector quantization -
VQ) est dekompozyc a obrazu oryginalnego w n-wymiarowe wektory obrazu. Wektory mogą być
tworzone na wiele różnych sposobów. Do na częstszych należy formowanie tró wymiarowych wektorów
z trzech składników koloru - RGB po edynczych pikseli, czy też n-wymiarowych wektorów z
uporządkowanych kole no wartości pikseli bloku o wymiarach n = k � l, gdzie wartości k i l określa ą
rozmiar bloku. Ponadto obraz może być na pierw modyfikowany przed utworzeniem wektorów, np.
przez transformac ę DCT, które współczynniki mogą być następnie wykorzystane ako współrzędne
wektora.
Każdy wektor obrazu est następnie porównywany z pewnym zbiorem reprezentatywnych
wzorców, zwanych wektorami kodu, który pochodzi z utworzone wcześnie n-wymiarowe księgi kodów.
Na odpowiednie szy wektor est dobierany na podstawie zdefiniowane reguły minimalnego
zniekształcenia. Miara tego zniekształcenia powinna być z edne strony prosta obliczeniowo, z drugie
zaś dobrze odpowiadać subiektywne ocenie degradac i akości obrazu. Na częście stosowaną w VQ
miarą zniekształceń est błąd średniokwadratowy (MSE), który odpowiada kwadratowi Euklidesowe
odległości pomiędzy dwoma wektorami. W niektórych aplikac ach stosowany est ważony błąd
średniokwadratowy.
Ostatni etap procesu kompres i polega na zapisaniu do pliku (transmis i) indeksów wybranych
wektorów, które na lepie przybliża ą wektory obrazu, za pomocą log2 Nwk bitowych kodów, gdzie Nwk
oznacza ilość wektorów zawartych w księdze kodowe . Przy dekompres i indeksy te służą do odczytania
odpowiednich wektorów z księgi kodów, z których składany est zrekonstruowany obraz, co czyni
algorytm dekompres i bardzo prostym.
Kompres a w VQ osiągana est w przypadku, gdy liczba wektorów księgi kodów est mnie sza
od ilości wszystkich wektorów obrazu, a średnia bitowa wynosi (log2 Nwk ) / n bitów/piksel (n-liczba
bitów konieczna do opisania wektora obrazu). Teoretycznie VQ może osiągnąć efektywność bliską
granicznego stopnia zniekształceń, eśli n ". W rzeczywistości wzrost wymiarowości wektorów,
akkolwiek zmnie sza średniokwadratowy błąd kwantyzac i, ednak prowadzi do problemów związanych
z zapisaniem i przeszukiwaniem ogromne księgi kodów.
Bardzo istotnym etapem w technice VQ est konstrukc a księgi kodowe zwana fazą
klasteryzac i. Jest ona głównym czynnikiem różniącym wiele opracowanych w ostatnich latach
algorytmów VQ i składa się z dwu zasadniczych elementów:
- generac a księgi kodów, ustala ąca akie wektory kodu winny się znalez
ć w zbiorze wektorów
przybliża ącym wektory obrazowe;
- pro ektowanie księgi kodów, mówiące o konstrukc i zbioru kodów umożliwia ące szybkie
przeszukiwanie i efektywną reprezentac ę wektorów.
Do na popularnie szych sposobów generac i księgi kodów należy algorytm opracowany przez
zespół Linde, Buzo, Gray (LBG), gdzie używany est treningowy zbiór obrazów, reprezentatywny dla
obrazów, które chcemy kompresować. W skra nym przypadku można wygenerować optymalną książkę
kodów dla po edynczego obrazu, ale est to kosztowne czasowo i istnie e konieczność dołączenia księgi
kodowe do skompresowanego kodu. Inne rozwiązania wykorzystu ą np. sieci neuronowe (algorytm
Kohonena).
Ponieważ w celu odnalezienia wektora kodu o minimalnym zniekształceniu w stosunku do
wektora obrazu wymagane est przeszukiwanie księgi kodów dla kole nych wektorów obrazu,
czasochłonność i nieefektywność tego procesu zwłaszcza w przypadku duże księgi kodów znacznie
ogranicza obszar zastosowań technik VQ. By usprawnić ten proces budu e się księgę kodów z
wykorzystaniem struktury drzewa, gdzie każdy węzeł zawiera m gałęzi, a węzły z kolei zgrupowane są
na p = logm Nwk poziomach drzewa. W poszukiwaniu właściwego wektora przeszukiwane są tylko
niektóre gałęzie drzewa, co zmnie sza liczbę koniecznych porównań z P(n�" Nwk ), w przypadku
przeglądania całe księgi, do P(nmlogm Nwk ). Jednakże rośnie niestety obszar pamięci, w którym musi
być zgromadzona księga kodów z P(n�" Nwk ) do P(nm( Nwk -1) / (m -1) ze względu na konieczność
gromadzenia wektorów z każdego poziomu (także ostatniego). Księga kodów est tworzona poprzez
zastosowanie algorytmu LBG dla każdego węzła do generac i księgi kodów o rozmiarze m.
Efektywność kompres i prostego algorytmu VQ, wykorzystu ącego księgę kodów o strukturze
drzewa est zazwycza mnie sza od skuteczności kompres i analogiczne metody z księgą kodów z
pełnym przeszukiwaniem, ze względu na mnie szy zbiór, w którym poszuku e się optymalnego wektora
kodu po wyborze określonych gałęzi w węzłach.
Stosowane są także struktury drzewa z nie ednolitą ilością gałęzi w każdym drzewie. W drzewie
stożkowym (tapered tree) liczba gałęzi w węzłach drzewa zwiększa się w miarę przesuwania się w dół
drzewa, co da e nieco większą efektywność algorytmów wykorzystu ących tę strukturę kosztem większe
złożoności. Z kolei w strukturze okro onego drzewa (pruned tree) usuwa się z dużego drzewa,
utworzonego w momencie inic alizac i, pewne wektory kodu zaczyna ąc od podstawy , tak aby uzyskać
założoną średnią długość kodu przy minimalnym zniekształceniu, lub też na mnie szą średnią długość
kodu dla danego zniekształcenia. Podstawowa idea polega na usuwaniu tych gałęzi, których
nieobecność w księdze kodów nie powodu e znaczących zniekształceń rekonstruowanego obrazu.
Optymalizac ę stosunku kompres i do zniekształceń przeprowadza się bada ąc o ile zwiększy się
zniekształcenie kosztem zmnie szenia długości kodu na skutek usunięcia danego listka drzewa. W
efekcie powsta e niezrównoważone drzewo o dłuższych i krótszych gałęziach, które wprowadza
zmienną długość kodu dla poszczególnych wektorów kodowych.
Inną metodą pro ektowania księgi kodów est struktura iloczynowa, w które est ona formowana
ako iloczyn kartez ański kilku mnie szych ksiąg kodów. Jeśli wektor charakteryzu ą pewne niezależne
cechy, np. położenie i wielkość, dla każde z tych cech może być wyznaczona oddzielna księga kodów.
Ostateczny wektor kodu est złożeniem wektorów z poszczególnych ksiąg opisu ących poszczególne
cechy.
Księga kodów ze strukturą iloczynową est nieco mnie efektywna (w znaczeniu skuteczności kompres i)
niż księga z pełnym przeszukiwaniem tego samego efektywnego rozmiaru, ale pozwala uzyskać
zrekonstruowane obrazy o wyższe akości przy tym samym stopniu złożoności księgi i ednakowe
średnie bitowe . Wiąże się to z faktem, że przy te same złożoności, efektywny rozmiar księgi kodów ze
strukturą iloczynową est większy oraz może być użyty do zakodowania wektorów o wyższych
wymiarach przy tym samym stopniu kompres i obrazu.
Kodowanie pasmowe (subpasmowe)
W technice pasmowego kodowania (subband encoding - SBE) obraz est poddawany filtrac i w
dziedzinie 2D przy pomocy filtrów dolno- i górnoprzepustowych. W e efekcie powsta e szereg 2D zbiorów
współczynników, z których każdy zawiera dane z określonego zakresu częstotliwości przestrzennych (pasma
będące częścią pasma obrazu oryginalnego).
Ponieważ każdy z subpasmowych obrazów ma zredukowaną szerokość pasma w stosunku do obrazu
oryginalnego, mogą być one próbkowane z mnie szą rozdzielczością (downsampling). Ta pierwsza faza procesu
kompres i składa ąca się z filtrac i i próbkowania nazywana est analizą. Potem następu e kodowanie każdego z
obrazów pasmowych. Można do tego celu użyć tego samego lub różnych dekoderów dla każdego pasma, przy
czym powinny być one dostosowane do charakterystyki obrazu danego pasma. Stosu e się nie tylko różne
stopnie kompres i dla poszczególnych pasm, lecz nawet w pewnych zastosowaniach zupełnie odmienne techniki
kompres i.
Proces dekompres i polega na próbkowaniu zwiększa ącym rozdzielczość rekonstruowanych przy użyciu
odpowiednich filtrów obrazów pasmowych, a następnie zsumowaniu tych obrazów w eden całościowy obraz.
Proces ten nazywa się syntezą obrazu.
Tworzenie pasmowych obrazów samo w sobie nie wprowadza elementu kompres i. Ze względu ednak
na znaczącą redukc ę korelac i pomiędzy wartościami pikseli w stosunku do obrazu oryginalnego, obrazy te mogą
być znacznie efektywnie kodowane niż obraz oryginalny.
Do kluczowych elementów techniki SBE należy zestaw filtrów stosowanych do analizy i syntezy obrazu,
a także algorytmy kodowania obrazów pasmowych.
Przykładowo aby dokonać dekompozyc i całego pasma sygnału 1-D na dwa pod-pasma, zestaw filtrów
do analizy powinien zawierać filtr dolnoprzepustowy i górnoprzepustowy z  nie nakłada ącymi się
charakterystykami częstotliwościowymi, ciągłymi, ze stałym wzmocnieniem w całym paśmie. Idealne filtry w
praktyce są ednak nie realizowalne, stąd też by uniknąć eliminac i pewnych częstotliwości z pasma sygnału
podczas analizy, stosu e się filtry o pokrywa ących się charakterystykach częstotliwościowych, co z kolei
prowadzi do zniekształceń utożsamiania (aliasing). By rozwiązać ten problem stosu e się na częście lustrzane
filtry kwadratowe (quadrature mirror filter - QMF), które pozwala ą wyeliminować błąd utożsamiania i uniknąć
błędów kodowania.
Dwuwymiarowe filtrac i dokonu e się na częście stosu ąc filtry 1-D na pierw w ednym, a potem w drugim
wymiarze. Przykład analizy i syntezy obrazu przedstawia rys.8.
Analiza
Synteza
Rys.8. Schemat wavekletowe analizy oraz syntezy obrazu.
Do na częście stosowanych technik kompres i obrazów pasmowych należą:
" kodowanie DPCM, szczególnie przydatne przy małe liczbie pasm, gdy obrazy pasmowe zachowały eszcze
silną korelac ę między pikselami;
" kodowanie DPCM/PCM, efektywne przy większe ilości pasm, gdzie dla na niższych pasm (z silną korelac ą)
stosu e się kodowanie DPCM, a dla pozostałych bezpośrednią kwantyzac ę (PCM);
" wektorowa kwantyzac a, w które wektory są formowane z obrazów pasmowych na częście na dwa
sposoby. Pierwszy polega na wyznaczeniu wektorów w obrębie poszczególnych obrazów pasmowych
(typowo bloki 4 � 4), dla których powsta e edna lub więce książek kodowych dla poszczególnych pasm.
Inna metoda polega na tworzeniu wektorów z elementów każdego obrazu poprzez łączenie pikseli o tym
samym przestrzennym położeniu w obrazach pasmowych. Formowana est wówczas edna książka kodowa,
która określa stopień kompres i i akość rekonstruowanego obrazu.
Relacja pomiędzy SBE a TC
Występu ąca zarówno w SBE ak i w TC częstotliwościowa reprezentac a oryginalnych danych
obrazowych stanowi o dużym podobieństwie tych technik. Różnią się one głównie organizac ą danych
we ściowych, co przedstawia rysunek 9.
Bloki po transformacji Pasmo e obrazy
a a a a
b b b b
a b a b a b
a b
a a a a
b b b b
c c
c c
a a a a
b b b b
a b a b a b a b
a a a a
b b b b
c c c c
a b a b a b a b
c c c c
c c c c
c c c c
a b a b a b a b
c c c c
c c c c
c c c c
a)
b)
Rys.9. Porównanie transformatowe i subpasmowe reprezentac i obrazu; a) transformatorowa, b) subpasmowa.
Rysunek 9.a) przedstawia współczynniki transformaty (n.p. DCT) od a (na niższa częstotliwość) do d
(na wyższa częstotliwość) obliczone w blokach pikseli 2 � 2 obrazu oryginalnego. Natomiast rysunek 10.b)
zawiera powstałe w wyniku analizy, przy użyciu filtrów 2 � 2 i próbkowaniu z poziomem 2:1 zmnie sza ącym
dwukrotnie liczbę pikseli w każdym kierunku, obrazy pasmowe z wartościami a, b, c, d (loku ącymi się w
poszczególnych pod-pasmach).
W praktyce relac a pomiędzy ądrem transformaty a postacią filtrów służących do analizy i syntezy est
bardzie złożona, niż to wynika z przykładu. Wiąże się to z faktem, iż zazwycza długości stosowanych
operatorów filtrów est większa niż poziom próbkowania. Odpowiada to zachodzące ortogonalne transformacie
(lapped orthogonal transform - LOT), obliczane na pokrywa ących się blokach pikseli. Jest ona stosowana w celu
usunięcia artefaktów powsta ących na granicach bloków. Tego typu artefakty praktycznie nie występu ą w SBE.
Kodowanie hierarchiczne
Technika hierarchicznego kodowania (hierarchical encoding - HE) polega na takim kodowaniu obrazu,
które umożliwia ego zrekonstruowanie na różnym poziomie akości lub w wers ach o różne rozdzielczości.
Przykładem aplikac i techniki HE są obrazowe bazy danych z możliwością szybkiego przeszukiwania, gdzie
użytkownik korzysta z wygodne opc i przeglądania niskorozdzielczych wers i obrazu w celu odnalezienia
poszukiwanego obrazu. Następnie można wysubtelnić ten obraz w sposób progresywny. Ten rodza algorytmów
hierarchicznych nazywany est progresywną transmis ą. Może być on także stosowany do transmis i obrazów
przez kanały o wąskim paśmie w stosunku do liczby danych, np. linie telefoniczne, szczególnie w przypadku, gdy
szybkie rozpoznanie obrazu est konieczne lub gdy czas transmis i est ograniczony. Przykładowo technika ta
zna du e zastosowanie w poligrafii, w wo sku, czy też w telemedycynie. W progresywne transmis i informac a
zawarta w obrazie oryginalnym est dzielona na części, które są kodowane (transmitowane) według odpowiednie
sekwenc i. Następnie następu e kole ne dekodowanie (odbieranie) informac i i rekonstruowanie coraz
doskonalsze aproksymac i obrazu oryginalnego. Do podstawowych cech progresywne transmis i należy zaliczyć:
" uzyskanie dużych stopni kompres i dla wczesnych aproksymac i oryginału;
" maksymalne wykorzystanie poprzednio transmitowanych danych i zminimalizowanie dodatkowe informac i
przekazywane w kole nych etapach;
" możliwość uzyskania efektywne kompres i całego obrazu oraz rekonstrukc i z dużą wiernością względem
oryginału ( eśli transmitowana est różnicowa mapa błędu wówczas możliwa est transmis a bezstratna);
" algorytmy kodowania/dekodowania są względnie szybkie i podatne hardware'owym implementac om.
Urządzenia wy ściowe zainstalowane w systemie z bazą danych obrazowych mogą wymagać wers i
obrazu o różne rozdzielczości lub akości. Jest to przykład wieloużytkowego środowiska (multiuse environment),
które est innym rodza em zastosowań HE. Do tych urządzeń można na częście zaliczyć monitor HDTV,
wysokorozdzielcza drukarka laserowa, niskorozdzielczy nada nik do linii telefonicznych itd. Cechy
charakterystyczne technik HE stosowanych w środowiskach wieloużytkowych są podobne ak w progresywne
aproksymac i. Można edynie dodać szybki i skuteczny dostęp do wers i obrazu o dane rozdzielczości czy
pożądanym poziomie akości. Ponadto techniki te winny zapewnić efektywne algorytmy dekompres i ze względu
na częste czytanie (dekodowanie) obrazu przy ednokrotnym ego wpisaniu do bazy.
Poziom 3
N/8)
(N/8
Poziom 2
(N/4 N/4)
Poziom 1
N/2)
(N/2
Poziom 0
(N N)
Obraz oryginalny
Rys.10. Struktura piramidy charakterystyczna dla technik HE wykorzystu ących hierarchię o zmienne
rozdzielczości.
Wspólnym aspektem obu zastosowań est potrzeba konstrukc i hierarchii obrazów, tzn. sposobu
organizac i danych obrazowych ze względu na ich ważność. Zasadniczo poszczególne poziomy w hierarchii
odnoszą się do obrazu rekonstruowanego z pewną rozdzielczością lub poziomem akości. Choć hierarchie
danych zna du ą liczne zastosowanie w przetwarzaniu obrazów poza zagadnieniem kompres i i stosowane są
różne wskaz
niki do wyznaczenia poziomów, ednak w technikach kompres i do na częście stosowanych należą
hierarchie o stałe i zmienne rozdzielczości. W przypadku hierarchii o stałe rozdzielczości rekonstruowany obraz
est takiego samego rozmiaru ak obraz oryginalny i wartość każdego piksela est korygowana przy
przechodzeniu z ednego poziomu na drugi. Przyrost średnie liczby bitów kodu przypada ących na piksel obrazu
est mnie więce stały, ednak niekoniecznie odpowiada to stałe poprawie akości rekonstruowanego obrazu. Jest
ona szczególnie przydatna w algorytmach progresywne transmis i. Natomiast techniki wykorzystu ące hierarchie
o zmienne rozdzielczości (szczególnie przydatne w wieloużytkowym środowisku), w których obrazy
odpowiada ące poszczególnym poziomom różnią się przestrzenną rozdzielczością, charakteryzu ą się
ekspotenc alną zmianą przyrostowe średnie bitowe przy przechodzeniu pomiędzy różnymi poziomami. W
technikach tych powsta e charakterystyczna piramidalna struktura, gdzie bazą piramidy est obraz o pełne
rozdzielczości obrazu oryginalnego. Przykład takie piramidy przedstawia rysunek 10, gdzie zależności pomiędzy
wartościami pikseli na kole nych poziomach tworzą typową strukturę drzewa.
Do typowych technik z hierarchią o stałe rozdzielczości należy:
" kodowanie map bitowych, kiedy to binarna mapa każdego bitu wartości pikseli (o rozmiarach oryginału)
może być progresywnie kodowana (transmitowana) w sekwenc i, zaczyna ąc od mapy bitu na bardzie
znaczącego;
" wektorowa kwantyzac a o strukturze drzewa, gdzie poszczególne etapy progresywne transmis i mogą
zawierać kole ne bity indeksu na lepszego przybliżenia obrazu oryginalnego w książce kodowe .
Zakodowanie w ostatnim etapie różnicowe mapy błędu może umożliwić bezstratną rekonstrukc ę obrazu;
" hierarchiczne kodowanie z wykorzystaniem transformat ortogonalnych, w którym progresywnie można
kodować w każdym etapie kole ne współczynniki transformaty (zaczyna ąc od składowe stałe ) lub też
kodować ednocześnie wszystkie współczynniki, ale przy ograniczone liczbie bitów wyraża ących ich
wartości. Poszczególne rozwiązania obok rodza u zastosowane transformaty różnią się także metodą
hierarchicznego uporządkowania informac i zawarte w wartościach współczynników.
W technikach z hierarchią o zmienne rozdzielczości używa się takie metody budowania struktury
piramidy ak algorytmy kole nego próbkowania zmnie sza ącego rozdzielczość danych reprezentu ących obraz
oryginalny na danym etapie (subsampling pyramid), zastępowania bloków pikseli (typowo 2 � 2) średnią ich
wartości (mean pyramid), formowania predykc i z ograniczone liczby danych i e ode mowania od obrazu
oryginalnego, w celu uzyskania obrazu resztkowego (prediction/residual pyramid) itp.
Do edne z na popularnie szych w ostatnich latach metod kompres i należy metoda falek (wavelet),
zaliczana do technik HE o zmienno-rozdzielcze hierarchii z subpasmową piramidą. W metodzie te stosu e się
dwa filtry ednowymiarowe: filtr dolnoprzepustowy L i związany z nim górnoprzepustowy H, tworzący tzw. obrazy
szczegółowe. Kole nym krokiem est ednowymiarowe próbkowanie. W ednym kroku redukcy nym, który
dokładnie odpowiada schematowi pasmowego kodowania z rys.8, powsta ą trzy obrazy szczegółowe (po filtrac i
HH, HL, LH) i eden obraz dolnopasmowy (po filtrac i LL). Kole ny etap filtrac i dotyczy edynie subpasma LL
(schemat podstawowy) lub też pasm wybranych (algorytmy z doborem na lepsze bazy). W zależności od
rozmiarów obrazu oryginalnego ilość etapów dekompozyc i obrazu oryginalnego wynosi zwykle trzy lub cztery.
Zastosowanie transformaty wavelet w algorytmach kompres i da e znacznie szersze możliwości
budowania modeli kwantyzac i i kodowania pod kątem optymalne akości psychowizualnego odbioru
rekonstruowanych obrazów. Praktycznie nieograniczona ilość możliwych postaci funkc i bazowych transformaty
rozszerza asortyment filtrów stosowanych w metodach pasmowego kodowania (subband coding). Transformata
wavelet pozwala uzyskać zbliżony do transformaty kosinusowe poziom dekorelac i danych oryginalnych przy
uniknięciu artefaktów blokowych. Lokalne funkc e bazowe przekształceń waveletowych, definiowane ako
niezerowe na skończonym nośniku (o niewielkie zazwycza długości w stosunku do rozmiarów zbioru), mogą być
konstruowane w zależności od lokalnych właściwości przetwarzanych zbiorów danych, co pozwala uzyskać
dobrą reprezentac ę sygnałów niestac onarnych. Funkc om tym odpowiada określona postać filtrów o skończone
długości. Przy konstrukc i filtrów po awia ą się ednak pewne problemy. Dla ortogonalne (ortonormalne ) bazy
waveletowe edynie sko arzone z nimi filtry NOI (o nieskończone odpowiedzi impulsowe ) ma ą liniową fazę. Jeśli
nośnik sta e się ograniczony (niezbędne w praktycznych zastosowaniach), otrzymu emy filtry SOI (o skończone
odpowiedzi impulsowe ) z nieliniową fazą (filtr est niesymetryczny). Powodu e to dodatkowe zniekształcenia w
procesie kompres i-dekompres i, szczególnie na granicach filtrowanych zbiorów danych o skończone długości. W
celu zminimalizowania tego z awiska wprowadza się na granicach cykliczne rozszerzenia zbiorów danych.
Lepszym sposobem est budowa biortogonalne bazy waveletowe o nieco gorszych czasami własnościach
dekorelac i danych, która pozwala skonstruować zwarte, symetryczne filtry SOI o liniowe fazie. Pary dolno- i
górnoprzepustowych filtrów realizu ących przekształcenie wavelet stanowią na częście parę QMF. Przykładem
lustrzane pary filtrów dolno- i górnoprzepustowych zastosowanych po raz pierwszy w falkowe kompres i przez
Mallata są filtry ortogonalne prezentowane poniże .
N -4 -3 -2 -1 0 1 2 3 4
L(n) 0.023 -0.078 -0.035 0.307 0.542 0.307 -0.035 -0.078 0.023
H(n) 0.030 0.023 0.078 -0.035 -0.307 0.542 -0.307 -0.035 0.078
Wybór optymalnej techniki kompresji stratnej
Pytanie o na lepszy algorytm stratne kompres i est często stawiane, lecz niestety nie ma na nie
ednoznaczne odpowiedzi. Mogą istnieć na odpowiednie sze algorytmy dla konkretnych aplikac i, przy czym
zarówno termin odpowiedniości ak i dokładne określenie zakresu aplikac i zależy od wielu czynników.
Przykładowo, kiedy kompres a est stosowana w transmis i obrazów, na lepie by było, gdyby operac e kompres i i
dekompres i były wykonywane w czasie rzeczywistym, a złożoność struktury kodu odporna za zakłócenia
występu ące w kanale transmis i. Istotna est także możliwość buforowania strumienia danych wy ściowych z
kodera w związku ze zmienia ącą się często prędkością transmis i w kanale oraz dopuszczalny poziom błędu
rekonstrukc i po stronie odbiornika (np. w telemedycynie). Są to wymagania zupełnie inne ak w przypadku
kompres i obrazów w celu zminimalizowania za mowane przez nie pamięci w obszerne bazie danych
obrazowych.
Lista czynników wpływa ących na wybór optymalnego algorytmu kompres i est długa i może być
rozszerzana w zależności od zastosowań. Ponadto waga poszczególnych czynników zmienia się w zależności od
aplikac i. I tak zaliczyć do nich można czułość na typ obrazu we ściowego (dynamika, szumy, korelac a pomiędzy
wartościami pikseli itd.), zamierzony stopień kompres i (relac a akość obrazu, a stopień kompres i), stały stopień
kompres i przy zadane akości obrazów, asymetria koder/dekoder, możliwość progresywne kompres i, warunki
konkretne implementac i, toleranc a błędu kanału itd.