Algorytmy Kompresji Stratnej

Kompresja stratna i model percepcji

Kompresja bezstratna zachowuje wszystkie dane wejściowe. Jej przeciwieństwem jest , która trwale zmniejsza precyzję wybranych danych albo je usuwa. Po dekompresji otrzymuje się przybliżenie oryginału. W materiałach audio, obrazach i wideo wybór informacji wynika z właściwości sygnału oraz modelu percepcji. Wyższy stopień kompresji wiąże się więc z kontrolowaną utratą jakości. Stopień tej utraty zależy od parametrów kodera, dlatego ten sam format może dawać różne rozmiary pliku i różną jakość.

Kompresję stratną stosuje się między innymi w strumieniowaniu wideo, zapisie zdjęć i transmisji rozmów. Koder analizuje sygnał, ustala jego istotne składowe i przydziela im różną dokładność. Do podstawowych rodzin należą kodowanie transformatowe, wykorzystywane między innymi w JPEG, MPEG i MP3, kodowanie predykcyjne oraz kompresja fraktalna oparta na samopodobieństwie obrazu. W każdym przypadku etap stratny należy odróżnić od późniejszego kodowania entropijnego, które może zmniejszyć strumień bez kolejnej utraty informacji.

Kodowanie transformatowe

Kodowanie transformatowe jest jedną z podstawowych metod kompresji stratnej. Stosuje się je w wielu standardach obrazu, wideo i audio, w tym w JPEG, MPEG i MP3. Sama transformata jest bezstratną zmianą reprezentacji, natomiast utrata informacji następuje później, podczas kwantyzacji lub innego ograniczania precyzji. Dobór transformacji wpływa na to, czy energia sygnału skupi się w małej liczbie współczynników i czy powstanie dużo wartości bliskich zeru.

Zmiana dziedziny reprezentacji

Surowe wartości, takie jak jasność pikseli lub amplituda próbki audio, mogą zawierać silne zależności. Transformata przedstawia je w innej dziedzinie matematycznej, na przykład w dziedzinie częstotliwości, gdzie łatwiej rozdzielić składowe o różnej istotności.

Transformata konwertuje zbiór danych z jednej reprezentacji na inną bez utraty informacji w samej operacji. Nowa reprezentacja może ułatwić późniejszą kwantyzację i kodowanie bezstratne. Kodowanie transformatowe służy przede wszystkim dwóm celom. W obrazie zależności przestrzenne są zastępowane opisem częstotliwościowym, a w audio podobny opis umożliwia rozdzielenie pasm o różnej wrażliwości słuchu:

Dekorelacja: W obrazach sąsiednie piksele często są silnie skorelowane. Transformata ogranicza te zależności, aby współczynniki opisujące sygnał były mniej zależne od siebie.
Kompakcja energii: Właściwie dobrana transformata skupia dużą część energii sygnału w niewielu współczynnikach. Pozostałe współczynniki mają często małe wartości i mogą zostać zapisane z mniejszą precyzją.

Dyskretna transformata kosinusowa (DCT)

Często stosowaną transformatą w kompresji stratnej jest . JPEG oraz wybrane standardy MPEG stosują ją na blokach pikseli, zwykle o rozmiarze 8x8, zamiast na całym obrazie jednocześnie. Praca na blokach ogranicza pamięć potrzebną do obliczeń, lecz przy silnej kwantyzacji może powodować widoczne granice bloków.

Dwuwymiarowa DCT pobiera blok wartości pikseli 8x8 i przekształca go w blok 8x8 współczynników częstotliwości. Położenie współczynnika określa kombinację częstotliwości w kierunku poziomym i pionowym, dlatego w JPEG współczynniki skanuje się zygzakiem przed kodowaniem.

Lewy górny współczynnik, współczynnik DC, opisuje średnią jasność lub kolor całego bloku 8x8. Dla typowych obrazów skupia znaczną część energii bloku.
Pozostałe 63 współczynniki to współczynniki AC. Opisują szczegóły i tekstury, od niższych częstotliwości położonych bliżej współczynnika DC do wyższych częstotliwości w prawym dolnym rogu.

Interaktywny blok DCT pokazuje wpływ zachowania współczynników niskoczęstotliwościowych oraz obraz po wyzerowaniu pozostałych współczynników.

Przykład: kodowanie obrazu JPEG

JPEG jest przykładem kodowania transformatowego stosowanego do obrazów nieruchomych.

Krok 1: zmiana przestrzeni barw i podpróbkowanie chrominancji: Obraz jest konwertowany z RGB (czerwony, zielony, niebieski) do YCbCr. Składowa Y opisuje luminancję, a Cb i Cr chrominancję. Wzrok jest mniej czuły na drobne zmiany koloru niż na zmiany jasności, dlatego Cb i Cr mogą być podpróbkowane, na przykład przez zapis jednej wartości dla bloku 2x2. Jest to pierwszy etap stratny. Konkretne proporcje podpróbkowania zależą od wybranego schematu, na przykład 4:4:4, 4:2:2 lub 4:2:0.
Krok 2: podział na bloki i DCT: Każda składowa (Y, Cb, Cr) jest dzielona na bloki 8x8 pikseli. DCT przekształca każdy blok, czyli 64 wartości, w 64 współczynniki. Współczynnik DC opisuje składową stałą, a współczynniki AC opisują zmiany w obrębie bloku.
Krok 3: kwantyzacja, czyli etap stratny: Każdy z 64 współczynników DCT jest dzielony przez odpowiednią wartość z 64-elementowej tabeli kwantyzacji, a wynik jest zaokrąglany do liczby całkowitej.
$\text{Współczynnik skwantyzowany} = \operatorname{round}\left(\frac{\text{Współczynnik DCT}}{\text{Wartość kwantyzacji}}\right)$
W tabeli wartości są zwykle mniejsze dla niższych częstotliwości i większe dla częstotliwości wyższych. Kwantyzacja zamienia wiele małych współczynników AC w zera i ogranicza precyzję pozostałych, trwale usuwając część informacji. Skala tabeli zależy od implementacji. Edytor może udostępniać ustawienie jakości od 1 do 100, lecz taki zakres nie jest elementem samego standardu. Niższa jakość zwykle oznacza większe dzielniki, większą utratę danych i mniejszy plik. Dekoder odtwarza przybliżone współczynniki przez mnożenie przez tabelę, dlatego samej liczby jakości nie można używać do przewidywania ani bezpośredniego porównywania wyniku wizualnego.
Krok 4: kodowanie entropijne: Blok 64 skwantyzowanych współczynników zawiera wiele zer, więc można go dalej kompresować bezstratnie. W profilu bazowym JPEG kody Huffmana opisują kategorię współczynnika, a dla współczynników AC także długość serii zer. Dodatkowe bity przenoszą amplitudę współczynnika.

Dekoder odczytuje dane zakodowane bezstratnie, wykonuje dekwantyzację przez pomnożenie przez te same wartości tabeli, stosuje odwrotną DCT i składa bloki w obraz. Oryginalna precyzja utracona podczas kwantyzacji nie jest odzyskiwana. Z tego powodu wielokrotne zapisywanie obrazu w JPEG może stopniowo zwiększać błędy kwantyzacji.

Kodowanie predykcyjne dla sygnałów audio

Kodowanie predykcyjne wykorzystuje zależność między kolejnymi próbkami. Jest stosowane między innymi do sygnałów audio, w których sąsiednie próbki często mają podobne wartości.

Różnica między próbką a predykcją

Zamiast kodować pełną wartość każdej próbki sygnału audio, koder wyznacza przewidywaną wartość na podstawie próbek poprzednich. Następnie oblicza błąd predykcji, czyli różnicę między predykcją i próbką rzeczywistą. Dla sygnałów o silnej korelacji błąd ma mniejszy zakres niż próbka, więc do jego zapisu wystarcza mniej bitów.

Proces staje się stratny, gdy błąd predykcji jest kwantyzowany przed transmisją. Ograniczona liczba bitów zmniejsza jego precyzję, a małe błędy mogą zostać zaokrąglone do zera. Dekoder oblicza tę samą predykcję, dodaje odebrany błąd skwantyzowany i uzyskuje przybliżenie oryginalnej próbki. W wersji bezstratnej błąd można kodować dokładnie, natomiast wersje adaptacyjne zmieniają krok kwantyzacji zgodnie z zakresem sygnału.

Zmień krok kwantyzatora i predyktor, aby obserwować zmianę błędu oraz sygnału odtwarzanego w pętli DPCM.

Ta technika, znana jako różnicowa modulacja impulsowo-kodowa (DPCM), występuje w kodekach mowy i audio. Jej skuteczność wynika z tego, że dla wielu sygnałów sąsiednie próbki są podobne, więc błąd predykcji ma małą amplitudę i łatwiej go zakodować. Odmiana ADPCM dodatkowo dobiera krok kwantyzatora, aby lepiej wykorzystać dostępne bity przy zmianach poziomu sygnału.

Kompresja fraktalna obrazu

Kompresja fraktalna jest mniej powszechną metodą stratnej kompresji obrazu. Wykorzystuje samopodobieństwo, czyli podobieństwo fragmentów obrazu do innych fragmentów w różnych skalach.

Dopasowanie bloków i opis transformacjami

Algorytm wyszukuje fragmenty, które można przybliżyć przeskalowanymi lub przekształconymi wersjami innych fragmentów obrazu. Przykładem może być mała chmura podobna do większej chmury w innym miejscu albo fragment paproci podobny do struktury liścia.

Kodowanie zapisuje parametry przekształceń zamiast wartości każdego piksela. Dla małego regionu docelowego algorytm wybiera większy region źródłowy i dopasowuje transformację afiniczną obejmującą skalowanie, obrót oraz zmianę jasności i kontrastu. Zbiór takich parametrów opisuje sposób odtworzenia obrazu. Region źródłowy może pochodzić z innej części obrazu, a dopasowanie zwykle minimalizuje określoną miarę błędu między blokiem źródłowym i docelowym.

Dekodowanie jest iteracyjne. Rozpoczyna się od obrazu początkowego i wielokrotnie stosuje zapisane przekształcenia. opisuje warunki zbieżności iteracji do atraktora. Atraktor jest przybliżeniem zakodowanego obrazu i nie musi odtwarzać oryginału bez błędu. Liczba iteracji wpływa na koszt dekodowania i na to, jak szybko obraz osiąga stabilny wygląd.

Właściwości i ograniczenia

Kompresja fraktalna ma kilka charakterystycznych właściwości:

Duża redukcja danych: W wybranych naturalnych i teksturowanych obrazach dopasowanie bloków może dać duży stopień kompresji.
Zależność od rozdzielczości wyjściowej: Parametry transformacji można oceniać przy różnych rozdzielczościach, ponieważ opis nie zawiera siatki wszystkich pikseli. Szczegóły przy powiększeniu zależą jednak od jakości dopasowania.
Kosztowne kodowanie: Wyszukiwanie najlepiej dopasowanych bloków wymaga wielu porównań, dlatego kodowanie jest obliczeniowo drogie. Dekodowanie jest zwykle prostsze.

Koszt kodowania oraz historyczne kwestie patentowe ograniczyły zastosowanie tej metody. Nie osiągnęła ona tak szerokiej adopcji jak metody transformacyjne, między innymi JPEG. W praktyce wynik zależy także od strategii wyszukiwania bloków, ograniczeń transformacji i przyjętej miary podobieństwa.

Połączenie kodowania transformacyjnego i predykcyjnego

Kodowanie transformatowe, predykcyjne i fraktalne reprezentują różne sposoby redukcji danych stratnych. Wiele kodeków wideo łączy transformację, predykcję między klatkami i kodowanie entropijne. W standardzie H.262 predykcja z kompensacją ruchu wykorzystuje podobieństwo kolejnych klatek, a DCT koduje dane obrazu i błędy predykcji. Dobór transformacji, predykcji, kwantyzacji i przepływności określa kompromis między rozmiarem strumienia i jakością odtworzonego sygnału. Ten sam układ elementów może pracować z innymi tablicami kwantyzacji, rozmiarami bloków lub trybami predykcji zależnie od standardu i profilu. Końcowe kodowanie entropijne usuwa statystyczną redundancję z reprezentacji po kwantyzacji. Dekoder odwraca ten etap dokładnie, natomiast błąd kwantyzacji pozostaje w odtworzonym sygnale.