DCT – fundament kompresji wideo

 
DCT to skrót od Discrete Cosine Transform – czyli dyskretna transformacja kosinusowa. Jest podstawą wielu koderów obrazu i wideo,  przede wszystkim ciągle najszerzej stosowanego kodera do zdjęć JPEG, a ponadto koderów wideo MPEG-1, MPEG-2, VC-1,  H.263. Popularny H.264 używa wariantu DCT pod nazwą Integer Transform, czasem zwaną ICT (Integer Cosine Transform). Transformacja ta w skrócie, (podobnie jak inne transformacje, na przykład oparte o falki) pozwala na pewnego rodzaju rozkład obrazu na składowe o “różnym stopniu szczegółowości”. Masło maślane, więc w dalszej części postaram się wyjaśnić o co chodzi z DCT i przy okazji jak działają współczesne kodery obrazu działające wg schematu transformacja ↣ kwantyzacja ↣ kodowanie entropijne.

Reprezentacja częstotliwościowa

A gdyby tak dało się rozłożyć gotowy obraz – taki malowany, na płótnie, przez artystę – na poszczególne etapy jego tworzenia. Najpierw pewnie byłoby tło, długimi pociągnięciami szerokiego pędzla, niezbyt dokładnie, tak, żeby złapać kolor – nieba, łąki, morza, lasu. Potem byłyby duże obiekty – góry, lasy, jezioro, brzeg morza, chmury. Potem przyszłaby kolej na mniejsze przedmity, a także na doszczegółowienie tych obiektów, które już się znajdują na obrazie. Aż dochodzimy do najdrobniejszych szczegółów, ostatnich pociągnięć pędzla – tak jak tutaj – u Kevina Hilla na jego kanale youtube.

A potem takie nagranie malarza malującego obraz gdyby tak zagrać od końca. W pewnym sensie byłby to rozkład obrazu na elementy coraz mniej szczegółowe.

W pewnym sensie DCT realizuje właśnie taką funkcję. Przy pomocy tej transformacji możemy rozłożyć dowolny obraz na sumę wzorów graficznych utworzonych ze złożenia funkcji kosinus o różnych częstotliwościach. Ponieważ kodery obrazu i wideo operują na  blokach o boku 4-8-16 pikseli takim obrazem rozkładanym na składowe kosinusowe jest pojedynczy blok.

Poniżej zamieszczam znany z Wikipedii obrazek, zawierający wszystkie funkcje bazowe transformacji DCT dla bloku 8×8 pikseli. Obraz – blok 8×8 – zrekonstruowany z jego reprezentacji częstotliwościowej DCT będzie ważoną sumą wszystkich 64 obrazków.

Dctjpeg

W lewym górnym rogu funkcja bazowa to po prostu wypełniony kwadrat, odpowiada on składowej stałej bloku. Potem, wzdłuż osi, poziomo i pionowo, mamy wzory powstałe z funkcji kosinus, o rosnącej częstotliwości w miarę oddalania się od skłądowej stałej. Po przekątnej mamy iloczyny kosinusów z obu kierunków, które tworzą charakterystyczne kratki. W prawym dolnym rogu znajduje się po prostu kratka o oczku wielkości jednego piksela – odpowiada ona maksymalnej częstotliwości funkcji kosinus wzdłuż obu osi. Jak widać, najwięcej “szczegółów”, czyli największą zmienność prezentuje funkcja bazowa z prawego dolnego rogu, zaś najmniej “detali” znajdziemy w górnym lewym rogu, czyli w sąsiedztwie składowej stałej (częstotliwość równa zero). Kolor biały oznacza tu wartość maksymalną (np 255 przy 8 bitach precyzji), a czerń minimalną (np 0). Ale to są jedynie funkcje bazowe. Transformacja kosinusowa ma za zadanie ustalić “udział” każdej (każdej z osobna) z tych funkcji bazowych w transformowanym bloku tak, aby nakładając na siebie wszystkie te pofalowane kwadraciki pomnożone przez odpowiadające im udziały otrzymać pierwotny obraz.

Wzór

Czy musiało do tego dojść? Widocznie musiało, skoro doszło. Czyli wklejam wzór na wyliczenie DCT 8×8, wprost z jednego z dokumentów JPEG:

JPEG_DCT

Gdzie Cu, Cv = 1/sqrt(2) dla u,v = 0
oraz Cu, Cv = 1 dla pozostałych

syx to wartość (jasność) piksela w punkcie (x,y), Svu to wartość udziału odpowiedniej funkcji bazowej, o odpowiednich częstotliwościach w obu kierunkach w obrazie pierwotnym (małe s). Tak więc duże S jest czymś w rodzaju dwuwymiarowego widma małego s, czyli pierwotnego obrazu. Widzimy tu też ten iloczyn dwóch kosinusów, który najlepiej widać na przekątnej obrazka z funkcjami bazowymi. Widzimy też, dlaczego wzdłuż krawędzi pionowej i poziomej, biegnących od lewego górnego rogu mamy czyste kosinusy, ponieważ albo u, albo v są dla nich równe 0, a cos(0) = 1, więc jeden z kosinusów znika.

Co z tego wyjdzie?

Pani Lena Sjööblom, Miss Listopada 1972 magazynu Playboy, prawdopodobnie nie przypuszczała, że stanie się osobą tak sławną i to niemal wyłącznie w środowiskach naukowych, a fragment zdjęcia z poświęconej jej rozkładówki magazynu zagości na tysiącach publikacji naukowych i stron internetowych traktujących o cyfrowym przetwarzaniu obrazów. Tradycja zobowiązuje:

lena

Osoby zafascynowane Panią Leną zapraszam na poświęconą jej stronę. Można się tam nawet doklikać do oryginalnego zdjęcia, które nie jest tak ubodze skadrowane i tym samym tak brutalnie pozbawione szerszego kontekstu jak zdjęcie powyżej.

Pozwolę sobie na nieco większy blok, 16×16 pikseli. Wytnę go z kawałka kawałka Pani Leny, a dokładnie z nosa.

lena_cutout

Oczywiście DCT policzę dla składowej luminancji, lub jak kto woli – w skali szarości.

blk_16x16

I dla tego kawałka wyliczę współczynniki DCT. Przy okazji wzór na DCT  NxN :

dct_NxN
Gdzie Cu, Cv = 1/sqrt(2) dla u,v = 0
oraz Cu, Cv = 1 dla pozostałych

Dla powyższego bloku 16×16 pikseli otrzymałem macierz 256 współczynników DCT:

 

Pewne charakterystyczne własności DCT nie są może widoczne na pierwszy rzut oka, może oprócz tego, że współczynnik w lewym górnym rogu jest liczbą znacznie większą od pozostałych. To składowa stała, czyli miara “jasności” bloku.
Aby zwizualizować jakoś wartości DCT dla omawianego bloku postanowiłem zamienić macierz DCT w obraz, w tym celu najpierw wyciągnąłem wartośc bezwzględną z każdego współczynnika. Ponieważ różnice między współczynnikami bywają znaczne, wyciągnąłem logarytm z każdego współczynnika, żeby przedstawić macierz w skali logarytmicznej, następnie “ręcznie” zmniejszyłem współczynnik odpowiadający składowej stałej, a na końcu przeskalowałem powstałą macierz do przedziału 0-255, tworząc z macierzy bitmapę-obraz. A tak to wygląda:

lena_dct

Im jaśniejszy piksel, tym większa wartość współczynnika (pamiętamy o skali logarytmicznej, różnice są w rzeczywistości dużo większe). Tutaj od razu widać, że cała “energia”, czyli wielkości modułów współczynników koncentrują się w lewym górnym rogu. Innymi słowy, większość informacji obrazowej zawarta jest w składowych o niższych częstotliwościach, w stronę prawego dolnego rogu mamy coraz większe częstotliwości, czyli coraz drobniejsze szczegóły, których zawartość jest jednak bardzo niewielka. Jest to jednocześnie właściwość samej transformacji DCT (zwana energy compaction), a także właściwość typowych rzeczywistych obrazów, że informacja obrazowa w zasadzie skupiona jest w czestotliwościach niskich i średnich. I tutaj otwiera się pole dla właściwej kompresji. A jeśli dodamy do tego fakt, że oko ludzkie jest dość słabo wyczulone na drobne szczegóły, praktycznie nie zauważa niewielkich zmian kontrastu i przy okazji ma tendencje do “wygładzania” tego co widzi, to można przy okazji do wspomnianej kompresji wprowadzić straty. Nasze oko prawdopodobnie w ogóle nie zarejestruje różnic.

Poniżej znajdziecie wynik transformacji całego obrazka blok po bloku – DCT 16x16px:

lena_dct

Transformacja odwrotna

A co najważniejsze, z macierzy współczynników DCT możemy odtworzyć obraz. Służy do tego odwrotna transformacja kosinusowa, oznaczana IDCT (I jak inverse). Obrazek, który otrzymujemy po zastosowaniu odwrotnego DCT na macierzy współczynników niczym nie będzie się różnił od wyjściowego obrazka.

dct_idct

Jeśli chodzi o wzór, to tutaj niespodzianka:

idct_NxN

Gdzie Cu, Cv = 1/sqrt(2) dla u,v = 0
oraz Cu, Cv = 1 dla pozostałych

Niewiele różni się od wzoru na DCT, poza tym, że do sumy trafiły indeksy z domeny współczynników DCT, przez co stałych Cu i Cv nie dało się wywlec przed znaki sum.

Filtrowanie w dziedzinie DCT

Poniżej postaram się zademonstrować to, co napisałem powyżej, czyli właściwość transformaty DCT polegającą na koncentracji informacji w składnikach o niskich częstotliwościach. Z każdego bloku DCT będę kolejno wycinał składniki od coraz wyższych częstotliwości do coraz niższych. Tutaj link do obrazka. Widać, że pomimo całkowitego wycięcia ponad połowy współczynników DCT i zastąpienia ich zerami, obraz po transformacji odwrotnej na pierwszy rzut oka niewiele się różni od oryginalnego obrazu. Po wyrzuceniu około 3/4 współczynników pogorszenie obrazu staje się nieco wyraźniejsze, ale nadal obraz jest bardzo czytelny.

idct_anim

Wygląda na to, że wystarczy zapisać jedynie 1/4 całej informacji obrazowej w postaci współczynników DCT, a widz nie zorientuje się, że obrabowaliśmy go z dużej części informacji zawartej w obrazie.
Na tym mechanizmie opiera się właśnie kompresja obrazu, z tą różnicą, że zamiast wyrzucania współczynników stosuje się odpowiednią kwantyzację, a następnie jakąś metodę kodowania bezstratnego (entropijnego). Dzięki niedoskonałościom naszej percepcji udaje się osiągnąć znaczny stopień kompresji bez dostrzegalnego pogorszenia jakości, dodatkowo w koderach wideo stosuje się kompensację ruchu, aby dodatkowo zwiększyć stopień kompresji wykorzystując naturalną nadmiarowość, jaką niesie ze sobą podobieństwo między dwiema sąsiednimi klatkami wideo.

Kody źródłowe

Liczenie DCT 16×16 wprost ze wzoru podanego wcześnie. Można łatwo wykorzystać poniższy kod do liczenia DCT NxN o dowolnym N, wystarczy zmienić wartość zmiennej BLOCK_SIZE

Przy okazji kawałek liczący odwrotną transformatę:

 

3 przemyślenia nt. „DCT – fundament kompresji wideo

  1. Witam, zaczynam przygodę z OpenCv i nie wiem jak zapisać do obrazu wynik odwrotnej transformaty kosinusowej, mógł bym prosić o pomoc?

  2. Witam. Jaki wpływ na jakość obrazu ma rozmiar bloku? Konkretnie chodzi o parametr PSNR. Czy jeśli użyję większych bloków to jakość zmaleje, czy może zależy to od szczegółowości obrazu (duże jednolite obiekty lub małe i szczegółowe)?

    1. PSNR to szczytowy stosunek sygnału do szumu i wynika on z kwantyzacji. Im mocniejsza kwantyzacja (więcej współczynników DCT zostaje stłumionych) tym mniejszy PSNR. Duże, jednolite obiekty, które dodatkowo pozostają w miarę niezmienne w czasie warto kodować w większych blokach. Natomiast przy braku kwantyzacji nie ma znaczenia jak duże będą bloki.
      Tutaj jako ciekawostkę pozwolę sobie zalinkować dokument pokazujący jak działa mechanizm lookahead / MB-tree, który ma za zadanie optymalnie pokroić wideo na makrobloki.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

Możesz użyć następujących tagów oraz atrybutów HTML-a: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">