Jak działa kompresja wideo cz.1 - Kodowanie obrazów statycznych

Istnieją różne standardy kompresji, różniące się między sobą jakością odtworzonych obrazów, stopniem uzyskanej kompresji, oraz wymaganiami co do mocy obliczeniowej, jakie nakłada na procesor realizacja danego algorytmu. Często korzystniejszą wartość jednego parametru uzyskuje się kosztem pogorszenia innego. Najczęstszym kompromisem jest pogodzenie się z utratą jakości odtworzonego obrazu i dzięki temu uzyskanie większego współczynnika kompresji.

Rys. 1. Schemat procedury kompresji obrazów

Sekwencja wideo składa się z następujących kolejno po sobie osobnych obrazów, tzw. klatek (frame). W związku z tym kompresja wideo w dużej mierze korzysta z technik używanych w kodowaniu obrazów statycznych, np. w formacie JPEG. Standard ten w przypadku niektórych metod kompresji wideo realizuje tzw. kodowanie wewnątrzobrazowe (intraframe), w którym wykorzystuje się właściwości pojedynczej klatki, rozpatrywanej jako całość. W kodowaniu całych sekwencji obrazów korzysta się z bardziej zaawansowanych algorytmów, w tym z tzw. międzyobrazowego (interframe). Polega to na wykorzystaniu związków, jakie występują między kolejnymi obrazami w sekwencji.

Niemal wszystkie stosowane powszechnie standardy kompresji wideo są stratne. Wykorzystuje się fakt, że rozróżnienie wszystkich szczegółów w szybko zmieniającej się sekwencji obrazów jest bardzo trudne.

Dyskretna transformata cosinusowa

Rys. 2. Działanie transformaty cosinusowej

Aby w drugiej części artykułu opisać kodowanie obrazów dynamicznych, warto najpierw omówić algorytm kompresji obrazów JPEG. Pierwszym etapem algorytmu kompresji w standardzie JPEG jest podział przetwarzanego obrazu na bloki o określonym rozmiarze, na przykład 8x8 pikseli. Następnie na każdym z bloków jest przeprowadzana transformata cosinusowa (DCT - Discrete Cosine Transform). DCT nie jest operacją powodującą straty w oryginalnym obrazie. Odwrotna transformata cosinusowa (IDCT - Inverse Discrete Cosine Transform) mogłaby zostać użyta do odtworzenia na podstawie współczynników DCT obrazu idealnie zgodnego z oryginałem. DCT pozwala oddzielić bardziej dostrzegalne informacje od tych mniej widocznych, które można z obrazu usunąć.

Pojedyncza dwuwymiarowa operacja obliczenia DCT lub IDCT na bloku o rozmiarze 8x8 pikseli wymaga kilkuset cykli instrukcji w typowym procesorze DSP. Algorytmy kompresji wideo wymagają tymczasem przeprowadzania olbrzymiej liczby operacji DCT lub IDCT na sekundę. Na przykład dekoder wideo w standardzie MPEG-4 VGA o rozdzielczości 640x480 i szybkości wynoszącej 30 klatek na sekundę wymagałby około 216 tys. operacji IDCT na sekundę. W starszych kodekach wideo takie obliczenia pochłaniały 30% czasu pracy procesora. W nowszych, bardziej wymagających algorytmach, takich jak H.264, odwrotna transformata, która często jest już inna niż IDCT zabiera tylko kilka procent czasu pracy dekodera. Ponieważ transformata DCT oraz inne rodzaje transformat operują na małych blokach obrazu, wymagania co do pamięci są zazwyczaj pomijalne.

Kwantyzacja

Rys. 3. Kwantyzacja

Po przeprowadzeniu transformaty i wyznaczeniu jej współczynników dla poszczególnych bloków obrazu kolejnymi operacjami są: kwantyzacja oraz kodowanie. Kwantyzacja zmniejsza precyzję współczynników wysokoczęstotliwościowych. Polega ona na przeskalowaniu wszystkich współczynników przez odpowiadające im wartości ze specjalnych tablic kwantyzacji, a następnie zaokrągleniu otrzymanych wyników. W odbiorniku przeprowadzana jest operacja odwrotna, a mianowicie dekwantyzacja. Odtworzone współczynniki nie są równe współczynnikom oryginalnym, ale ich wartości są wystarczająco zbliżone do oryginałów. Skutkuje to utratą mniej dostrzegalnych szczegółów. Następnie w wyniku IDCT zostają odtworzone również przybliżone wartości poszczególnych pikseli obrazu.

W starszych rozwiązaniach, takich jak standard MPEG-2, dekwantyzacja zajmowała około 3-15% czasu pracy procesora. W algorytmie H.264 czas ten, podobnie jak wymagania co do pamięci, jest pomijalny.

Kodowanie

Rys. 4. Uporządkowanie zygzakowate współczynników DCT.

Następnym etapem jest kodowanie, w którym wykorzystuje się pewne specyficzne właściwości analizowanych współczynników. Po procedurze kwantyzacji uzyskuje się tablice współczynników o charakterystycznym układzie. Przeważającą ich część stanowią wartości zerowe. Stosuje się nawet specjalne zygzakowate uporządkowanie współczynników, które pozwala ustawić je w taki sposób, aby możliwe było uzyskanie jak najdłuższego ciągu występujących kolejno po sobie zer. Jest to zabieg, który umożliwia skorzystanie ze specjalnej techniki kodowania RLC (Run-Length Coding). Pozwala ono uniknąć konieczności nadmiarowego kodowania powtarzających się zer.

Rys. 5. Trzy przykładowe bloki skwantowanych współczynników DCT oraz te same współczynniki odczytywane zygzakiem.

Kodowanie RLC występuje zazwyczaj w parze z kodowaniem VLC (Variable-Length Coding), ze zmienną długością słowa kodowego. W metodzie tej symbole pojawiające się częściej są reprezentowane przez krótsze słowa kodowe, podczas gdy symbole pojawiające się rzadziej są kodowane przy pomocy większej liczby bitów.

Dekodowanie

W czasie odtwarzania obrazu odwracane są wszystkie etapy przetwarzania poszczególnych bloków przeprowadzone w koderze. Kroki podjęte na etapie kodowania VLC są poprzez VLD (Variable-Length Decoding). VLD jest operacją dużo bardziej złożoną obliczeniowo, niż VLC, które wymaga jednorazowego odszukania w tabeli kodowanego symbolu. Tymczasem VLD wymaga, w większości implementacji wielokrotnego porównywaniem poszczególnych bitów kodu symbolu z bitami w tabeli w celu znalezienia identycznego kodu. Przeciętnie dekodowanie VLD wymaga przeprowadzenia około 11 operacji na jeden bit. Z tego powodu wymagania związane z przetwarzaniem danych w procesie VLD są proporcjonalne do określonej przepustowości strumienia wideo. VLD może zająć nawet blisko 25% czasu pracy procesora.

Najnowsze standardy, takie jak H.264, zastępują lub rozbudowują opisywane wcześniej algorytmy RLC i VLC w celu osiągnięcia jeszcze większej kompresji. Na przykład w H.264 możliwe jest użycie zarówno adaptacyjnego kodowania (CAVLC - Context-Adaptive VLC), jak i adaptacyjnego kodowania arytmetycznego (CABAC - Context-Adaptive Arithmetic Coding). CABAC całkowicie zastępuje kodowanie ze zmienną długością słowa kodowaniem arytmetycznym, które jest bardziej wydajne mimo, że jest operacją bardziej złożoną obliczeniowo. CABAC może zająć blisko 50% czasy pracy dekodera H.264.

Intraframe

Wszystkie do tej pory opisywane etapy operowały niezależnie na poszczególnych blokach o rozmiarze 8x8 pikseli. Ponieważ jednak obrazy zazwyczaj zawierają fragmenty, które są większe niż blok 8x8 większą kompresję można uzyskać, jeżeli weźmie się pod uwagę fakt, że sąsiednie bloki są przeważnie bardzo do siebie podobne. Aby z tego skorzystać, etapem poprzedzającym kwantyzację jest operacja predykcji. W kroku tym kodek usiłuje określić informację zawartą w danym bloku korzystając z informacji z bloków sąsiednich. Niektóre kodeki, takie jak na przykład MPEG-4, wprowadzają ten krok w dziedzinie częstotliwości, czyli operując na współczynnikach transformaty DCT. Z kolei inne algorytmy (na przykład H.264) przeprowadzają ten etap bezpośrednio na wartościach poszczególnych pikseli. Takie rozwiązanie jest ogólnie określane mianem predykcji wewnątrzobrazowej (intraframe).

W kroku tym dekoder usiłuje wyznaczyć wartości współczynników DCT lub wartości pikseli w danym bloku bazując na odkodowanych współczynnikach lub wartościach pikseli z bloków sąsiednich. W związku z tym koder oblicza różnicę między aktualną wartością i wartością z sąsiedniego bloku. Następnie kodowana jest właśnie ta obliczona różnica, zamiast wartości rzeczywistej. W dekoderze wartości są rekonstruowane poprzez analogiczną, odwrotną operację. Ponieważ kodowana różnica jest mała w porównaniu z oryginalną wartością, więc i liczba bitów potrzebna do zakodowania ulega zmniejszeniu. Standard MPEG-4 różnicowo koduje pierwszy współczynnik DCT w każdym wierszu i w każdej kolumnie bloku 8x8 pikseli. Sposób taki jest określany mianem predykcji AC-DC (AC-DC prediction). Takie rozwiązanie może wymagać znacznej mocy procesora. Jednak predykcja AC-DC trwa zazwyczaj niedługo i zazwyczaj ma pomijalnie mały wpływ na obciążenie procesora. W standardzie H.264 predykcja jest przeprowadzana bezpośrednio na wartościach pikseli i w związku z tym transformata DCT jest przeprowadzana zawsze na wartościach obliczonych różnic. Wartości pikseli nie są więc nigdy transformowane bezpośrednio.

Kodowanie koloru

Obrazy kolorowe są zazwyczaj przedstawiane w przestrzeni kolorów RGB. W kodowaniu sekwencji wideo wykorzystuje się zapis w przestrzeni YCbCr. Oznacza to, że obraz opisuje składowa luminancji Y oraz składowe różnicowe chrominancji Cb i Cr, niosące informacje o kolorach. Taki sposób opisu został przyjęty z tego względu, że oko ludzkie jest bardziej czułe na informację o luminancji obrazu, niż o jego kolorze. W algorytmach kompresji wideo chrominancja jest kodowana z dwukrotnie mniejszą rozdzielczością. W powszechnie stosowanych standardach oprócz bloków 8x8 używa się większej jednostki podziału danych. Jest to tzw. makroblok o wymiarze 16x16 pikseli. Makroblok zawiera więc cztery bloki o rozmiarze 8x8 pikseli luminancji i dwa bloki 8x8 odpowiadające składowym chrominancji.

Druga część artykułu "Jak działa kompresja wideo - Estymacja ruchu"

Monika Jaworowska