Jak działa kompresja wideo cz.2 - Estymacja ruchu

Wektory ruchu

Dla każdego makrobloku w aktualnej klatce estymacja ruchu polega na znalezieniu w poprzednio kodowanej klatce (zwanej klatką odniesienia, reference frame) obszaru najbardziej podobnego, pod względem przyjętego kryterium podobieństwa - na przykład minimalnej średniej różnicy między poszczególnymi pikselami obu klatek. Następnie wyznacza się tzw. wektor ruchu (motion vector), który określa przestrzenne przesunięcie, jakie wykonuje dany blok przy zmianie klatki. Koder oblicza różnicę między odpowiednimi pikselami obu bloków, wyznaczając tzw. błąd predykcji, który jest transmitowany do odbiornika wraz z wektorem ruchu. Wektor ruchu służy do zlokalizowania w poprzednio odkodowanej klatce bloku odniesienia, do którego dodawane są odkodowane różnice i w ten sposób odtwarzana jest aktualna klatka. Większość standardów kompresji pomija ten etap, jeżeli koder nie jest w stanie odnaleźć najbardziej podobnego bloku w ramce odniesienia. W takim wypadku kodowany jest dany makroblok w całości.

Tyłem do przodu

Rys. 1. Metoda estymacji ruchu w algorytmach kompresji wideo

Ze względu na zastosowany sposób kompresji poszczególne klatki w sekwencji wideo mają różne nazwy. Okresowo w sekwencji pojawia się klatka zakodowana wyłącznie z wykorzystaniem metod stosowanych w kompresji obrazów statycznych, która nazywana jest klatką typu I (intra frame). Głównym powodem stosowania takich klatek jest chęć zapobiegania kumulacji błędów. Jako niezależna od innych klatka typu I nie jest obarczona jakimikolwiek wcześniej pojawiającymi się błędami. Dzięki stosowaniu klatek typu I możliwe jest również przewijanie filmu i oglądanie go od dowolnie wybranego momentu.

Dwa pozostałe typy klatek nie są już całkowicie niezależne. Wyróżnia się klatki, które są kodowane różnicowo (Predicted frames), na podstawie jedynie klatek je poprzedzających oraz dwukierunkowo (Bidirectionally predicted frames).

Komplikacje

Rys. 2. Filtrowanie generowanego obrazu w trakcie i po procesie dekodowania

Najprostszym sposobem na realizację algorytmu estymacji ruchu jest analiza każdego bloku 16x16 klatki odniesienia i wybranie obszaru najlepiej pasującego. Niektóre ze stosowanych kryteriów to suma bezwzględnych różnic (SAD - Sum of Absolute Difference) i suma kwadratów różnic (SSD - Sum of Squared Difference). Miary te są często wyznaczane tylko dla składowej luminancji. Drobiazgowe przeszukiwanie obszaru o rozmiarze 48x24 piksele wymaga blisko 8 mld operacji arytmetycznych na sekundę w rozdzielczości 640x480 i szybkości 30 klatek na sekundę.

Różne rodzaje przeszukiwania

Ze względu na tak wysokie obciążenie obliczeniami, praktyczne implementacje estymacji ruchu nie używają szczegółowego przeglądania. Zamiast tego algorytmy estymacji używają różnych metod wyboru ograniczonej liczby potencjalnych wektorów ruchu. Dalsza analiza jest wówczas przeprowadzana tylko na obszarach 16x16 pikseli powiązanych z tymi najbardziej obiecującymi wektorami. Jednym z rozwiązań jest wybór określonych wektorów ruchu w kilku etapach. Na przykład pięć początkowych wektorów zostaje wybranych i przeanalizowanych. Wyniki są używane do eliminacji obszarów niespełniających wymagań. Umożliwia to koncentrację na najbardziej podobnych obszarach. W kolejnym kroku wybiera się kolejnych pięć wektorów i cała operacja się powtarza. Po kilku takich krokach zostaje wreszcie znaleziony najbardziej optymalny wektor ruchu.

Inne rozwiązanie polega na analizie wektorów ruchu, które zostały wyznaczone dla wcześniej przetwarzanych bloków w klatce aktualnej i poprzedniej, otaczających bieżący makroblok. Można w ten sposób próbować przewidzieć, jaki ruch może nastąpić w aktualnym makrobloku. To z kolei pozwala na wytypowanie kilku najbardziej odpowiednich wektorów, na których będzie przeprowadzana dalsza analiza.

Podział na mniejsze bloki

Niektóre kodeki, a w tym m.in. H.264, umożliwiają podział makrobloków o typowym rozmiarze 16x16 pikseli na mniejsze bloki. Dopuszczalne są różne kombinacje rozmiarów, w tym 8x8, 4x8, 8x4 oraz 4x4. Pozwala to na zmniejszenie błędu predykcji. Każdy z tych mniejszych bloków może mieć swój własny wektor ruchu. Jeśli zastosuje się taki schemat estymacji, cała operacja rozpoczyna się od znalezienia najlepszego dopasowania dla całego bloku 16x16. Jeżeli operacja taka kończy się sukcesem, nie ma potrzeby dalszego podziału na mniejsze bloki. W przeciwnym wypadku rozpoczyna się podział makrobloku na bloki 8x8 pikseli.

Jednak nawet poważna redukcja liczby analizowanych wektorów ruchu nie zmniejsza obciążenia obliczeniowego. Wprowadzenie estymacji ruchu sprawia, że kodowanie sekwencji wideo jest dużo bardziej skomplikowane obliczeniowo, niż dekodowanie. Estymacja ruchu zajmuje blisko 80% czasu pracy procesora. Z tego powodu wiele procesorów dedykowanych do aplikacji multimedialnych zawiera specjalne instrukcje, których wykorzystanie przyśpiesza obliczenia miar podobieństwa. Często praktykuje się wprowadzanie dodatkowych procesorów pomocniczych, których zadaniem jest odciążenie jednostki głównej. Przykładem pierwszego rozwiązania jest rdzeń ARM11 wykorzystujący instrukcje przyśpieszające obliczenia miary SAD oraz niektóre rozwiązania firmy Texas Instruments z rodziny procesorów DSP TMS320C55xx, które zawierają dodatkowe koprocesory, również dedykowane do obliczeń SAD. Warto zauważyć, że koder, oprócz klatki bieżącej, musi przechowywać w pamięci także jedną lub dwie klatki odniesienia. Wymagania wobec buforów służących do przechowywania tych klatek są często większe niż możliwości wewnętrznych pamięci. Skutkuje to koniecznością instalowania szybkich pamięci dodatkowych.

Sekrety

Oprócz przedstawionych powyżej metod wyboru odpowiednich wektorów ruchu istnieje wiele innych sposobów, w tym szeroki zestaw rozwiązań chronionych prawami autorskimi. Większość standardów kompresji wideo określa jedynie format skompresowanego strumienia danych i etapy procesu dekodowania, pozostawiając operacje kodowanie niezdefiniowane. Dzięki temu koder może realizować różne rozwiązania estymacji ruchu i to właśnie algorytm zastosowany w tej operacji stanowi największą różnicę między różnymi koderami wideo, które działają w danym standardzie. Wybór techniki estymacji ruchu w ogromny sposób wpływa na wymagania co do komplikacji obliczeń i jakości kompresji. Z tego powodu szczegóły algorytmów są pilnie strzeżonymi tajemnicami. W dekoderze dominują algorytmy kompensacji ruchu. Ich zadaniem jest wyznaczenie wartości pikseli w każdym makrobloku, przy użyciu wektorów ruchu przesyłanych w strumieniu skompresowanych danych. Jeżeli oba elementy wektora ruchu, określające przesunięcie bloku w poziomie i w pionie, są wartościami całkowitymi operacja odnalezienia konkretnego bloku w ramce odniesienia polega po prostu na skopiowaniu danego bloku. Jeżeli natomiast którykolwiek z elementów wektora nie jest wartością całkowitą, do zlokalizowania odpowiedniego obszaru pikseli stosuje się interpolację. Następnie zostaje odkodowany błąd predykcji, który w kolejnym etapie jest sumowany z makroblokiem odnalezionym w kroku poprzednim.

Kompensacja i estymacja

W porównaniu z estymacją ruchu, realizowana w dekoderze operacja kompensacji jest operacją znacznie mniej skomplikowaną obliczeniowo. Estymacja ruchu musi uwzględniać złożone operacje obliczania parametrów SAD lub SSD dla znacznej liczby makrobloków. Tymczasem kompensacja ruchu w dekoderze po prostu kopiuje odpowiedni blok z klatki odniesienia dla każdego makrobloku. Z tego powodu kompensacja ruchu zajmuje w dekoderze około 40% czasu pracy procesora.

Podobnie jak w przypadku estymacji ruchu także kompensacja wymaga przechowywania w pamięci jednej lub dwóch klatek odniesienia. Warto jednak zauważyć, że w przeciwieństwie do estymacji, kompensacja ruchu wymaga znacznie mniejszej liczby odwołań do pamięci. W idealnym przypadku kompresja stratna powinna usuwać z obrazu tylko te mniej znaczące informacje, których braku oko nie jest w stanie dostrzec w zrekonstruowanym obrazie lub w szybko zmieniającej się sekwencji wideo. Dzięki temu odtworzony obraz powinien, z punktu widzenia przeciętnego obserwatora, być identyczny z oryginałem. W praktyce jednak nie da się całkowicie zniwelować wpływu kompresji na jakość.

Do najczęściej występujących niekorzystnych zjawisk w kompresji wideo należy uwidacznianie konturów poszczególnych bloków oraz tzw. dzwonienie. Pierwsze z wymienionych zjawisk związane jest z podziałem obrazu na bloki o rozmiarze 8x8 pikseli. Każdy z bloków jest odtwarzany z pewnym błędem, a różnice te stają się szczególnie widoczne na krawędziach sąsiadujących ze sobą bloków. Drugie zjawisko występuje w momencie pojawienia się zniekształceń wokół krawędzi poszczególnych obiektów w obrazie. Efekt dzwonienia pojawia się, gdy na etapie kodowania, w procesie kwantyzacji, zostanie usunięta zbyt duża ilość informacji zawartej we współczynnikach AC.

W celu redukcji obu opisywanych zjawisk algorytmy kompresji często uwzględniają wykorzystanie filtrów, głównie dolnoprzepustowych SOI. Powodują one jednak konieczność przeprowadzania dodatkowych obliczeń. Łącznie filtry stosowane do usunięcia obu zjawisk mogą zajmować procesor przez więcej czasu niż sama operacja dekodowania. Na przykład w MPEG-4 o prostym profilu i poziomie 1 (176x144 pikseli, 15fps) dekoder optymalizowany dla procesora ARM9E wymaga, aby układ pracował z częstotliwością 14MHz, w czasie dekodowania umiarkowanie złożonego strumienia wideo. Jeżeli uwzględnione jest łagodzenie konturów poszczególnych bloków procesor musiałby pracować z częstotliwością 33MHz. Jeżeli natomiast dodatkowo istniałaby konieczność zapobiegania powstawaniu efektu dzwonienia, częstotliwość pracy procesora powinna ulec zwiększeniu do około 39MHz.

Po czy w trakcie?

Filtry, usuwające niekorzystne efekty uboczne kompresji, mogą być wprowadzane jako oddzielne operacje. Taki krok zapewnia projektantom systemów większą swobodę w wyborze najlepszych filtrów. To z kolei umożliwia zredukowanie złożoności obliczeniowej w momencie, gdy jest to korzystne. Gdy nie przeprowadza się wstępnej filtracji, dekoder używa odtworzonej klatki, która nie jest odfiltrowana, jako ramki odniesienia dla dekodowania kolejnych klatek. Dodatkowo wymagany jest wówczas bufor przechowujący klatki w ostatecznej, odfiltrowanej postaci.

Drugim rozwiązaniem jest włączenie operacji filtrowania w procesie dekodowania. Klatka odniesienia zostaje wstępnie odfiltrowana zanim służy jako podstawa w dalszym procesie dekodowania. Takie rozwiązanie wymaga, aby koder stosował te same metody filtrowania jak dekoder. Związana z tym potrzeba wprowadzenia filtrów w koderze zwiększa wymagania co do procesora realizującego kodowanie ale jednocześnie poprawia jakość obrazu. Ponadto dodatkowy bufor wymagany w przypadku, gdy filtrowanie odbywa się na już odkodowanych danych, jest w przypadku zintegrowanych algorytmów filtrowania i kompresji niepotrzebny.

Przetwarzanie kolorów

Inną trudnością pojawiającą się przy kompresji strumieni wideo jest różnica między sposobem, w jaki kolor jest reprezentowany w kodekach a tym, w jaki jest on rozumiany w kamerach i wyświetlaczach. Algorytmy kompresji traktują kolorowe obrazy jako złożenie składowej luminancji i dwóch składowych chrominancji, tymczasem w kamerach kolor jest przedstawiany w zapisie RGB. Z tego powodu czerwone, zielone i niebieskie piksele zarejestrowane przez kamerę muszą być przetworzone do wartości odpowiadających składowym: luminancji i chrominancji zanim zostaną skomprymowane. Algorytm takiego przetwarzania wymaga około 12 operacji arytmetycznych dla każdego piksela obrazu, wyłączając konieczność interpolacji związaną mniejszą rozdzielczością bitową zapisanych składowych chrominancji. Dla VGA o rozdzielczości 640x480 pikseli i szybkości 30fps takie przetwarzanie takie wymaga przeprowadzenia ponad 10 mln operacji na sekundę.

Złoty środek

Kompresja sekwencji wideo opiera się na wielu operacjach związanych z przetwarzaniem sygnałów, takich jak opisywana estymacja ruchu, różnego rodzaju transformaty oraz różne sposoby kodowania. Mimo, że większość współczesnych algorytmów kompresji działa w oparciu o tych kilka podstawowych operacji to istnieje olbrzymia różnorodność wśród samych algorytmów i sposobów ich implementacji. W związku z tym, często także wymagania stawianie możliwościom obliczeniowym koderów i dekoderów są różne. Decydując się na wybór określonego algorytmu lub układu scalonego kodeka należy więc znać różnorodne sposoby jego implementacji, tak aby dostosować wybraną metodę do możliwości sprzętu. Nie należy starać się o najbardziej wyszukane rozwiązania, gdy od efektu końcowego nie oczekuje się zbyt wysokiej jakości. Z kolei czasem warto zainwestować w lepszy sprzęt. Dogłębne zrozumienie zasad przetwarzania sygnałów, praktycznych implementacji poszczególnych funkcji kodera obrazów oraz szczegółowych możliwości używanego procesora decyduje o wydajnym dopasowaniu algorytmu kompresji strumienia wideo do architektury procesora.

Monika Jaworowska