Kompensacja ruchu

 
Większość współczesnych kodeków wideo korzysta z pewnej oczywistej zależności między poszczególnymi klatkami sekwencji wideo. Otóż jeśli kompresowana jest scena w miarę naturalna, to znaczy to co na ekranie ma pewną ciągłość, to klatka obrazu i jej sąsiedzi w ogólności niewiele się od siebie różnią. Zatem nie sposób z tej sytuacji nie skorzystać, aby zwiększyć stopień kompresji bez utraty jakości. Jednak samo dostrzeżenie różnic i wyliczenie prostej różnicy klatek w formie rastra i zakodowanie tej różnicy niczym pojedynczego obrazka tak jak to robi koder JPEG nie jest wystarczająco efektywne. Prosta różnica między sąsiednimi klatkami wprawdzie w części będzie niemal zerowa, jednak dostrzegalne będą wyraźne kontury poruszających się obiektów, które kompresują się nienajlepiej. Gorzej, jeśli to kamera jest w ruchu, wtedy wszystko na ekranie się porusza i prosta rastrowa różnica dwóch sąsiednich klatek jest znaczna. Właśnie po to kodeki wideo stosują mechanizm kompensacji ruchu, który postaram się zilustrować, podpierając się biblioteką OpenCV.

 

Przygotowania

Najpierw przydałyby się jakieś dwie sąsiadujące ze sobą klatki z jakiegoś wideo. Wybór padł na przerośniętego królika. Aby szybko wyłapać klatki posłużę się ffmpegiem:

Powyższa komenda jest trochę nieefektywna, bo dekoduje film od początku, a ja potrzebuję tylko 50 ramek począwszy od 241 sekundy. Można było dodać jeszcze jedno -ss przed -i .

Wybrałem sobie dwie sąsiednie klatki:

twoframes

Żeby różnica między nimi była bardziej widoczna, sporządziłem animowanego gifa:

bbb

 

Estymacja ruchu – wyszukiwanie wyczerpujące

Zadaniem kompensacji ruchu w koderach wideo jest takie przekształcenie klatki numer 1, aby była prawie identyczna z klatką numer 2.
Po pierwsze, wszystkie popularne kodeki wideo operują na blokach. Obraz dzielony jest na bloki, np 16×16 pikseli, 8×8 pikseli. W nowszych kodekach (np h.264) stosowane sa różne rozmiary bloku w ramach tej samej klatki, właśnie po to, żeby uczynić kompensację ruchu jeszcze dokładniejszą.
Algorytm kompensacji polega w tym przypadku w ogólności ze składania bloków drugiej klatki używając różnych bloków “wyciętych” z klatki pierwszej. Taka bardziej wyrafinowana forma przedszkolnej wycinanki. O tyle ciekawa, że do skonstruowania dwóch różnych bloków klatki następnej może zostać użyty ten sam, lub prawie ten sam fragment klatki poprzedniej.

Metod wyszukiwania najlepszego fragmentu do wycięcia jest bardzo wiele. Każdy kodek implementuje je po swojemu, żeby sprostać wymaganiom użytkowników odnośnie jakości kompresji i szybkości kodowania. Wiadomo jednak, że najlepszy efekt da przeszukiwanie wyczerpujące, czyli rozpatrzenie wszelkich możliwych kombinacji w celu znalezienia maksymalnego podobieństwa fragmentu klatki 1 (o rozmiarze bloku) do danego bloku klatki 2. I tutaj możemy jedynie ograniczyć otoczenie, w którym te poszukiwania będą prowadzone.
Kryterium, które wybieram dla znalezienia najlepszego dopasowania naszej wycinanki, to suma kwadratów różnic między pikselami “wycinka”, a pikselami bloku, do którego dopasowujemy wycinek. Zaprezentuję to, skupiając się na ogonku królika.
Przyjąłem wielkość bloku 8×8 pikseli, oraz obszar poszukiwań odległy o 16 pikseli w każdą stronę od bloku.

search_area

Bloku oznaczonego w klatce 2 na czerwono (ogonek) poszukiwał będę w klatce 1 w otoczeniu oznaczonym czerwoną ramką.

match

Tak się składa, że obszar w klatce 1, który wykazuje największe podobieństwo do czerwonego obszaru w klatce 2 to też kawałek ogonka (zielony obszar). Podobne wyszukiwanie przeprowadzam dla każdego bloku w klatce 2.I tak po kolei szukamy takich wycinków, aby za ich pomocą “zrekonstruować” klatkę 2. Wektor pomiędzy blokiem dopasowanym (zielonym) a oryginalnym (czerwonym) jest niczym innym tylko “wektorem ruchu” znanym z kodeków. Jednak wektor ruchu niekonieczne wyznacza rzeczywisty, fizyczny ruch, czyli optical flow. Chociaż w większości przypadków wektory ruchu można wprost powiązać z poruszającymi się przedmiotami w scenie wideo.

Poniżej animacja, jak poprzez wyszukiwanie wyczerpujące, z wycinków klatki 1 została “zrekonstruowana” klatka 2. Na przykładzie króliczego ogonka, żeby było lepiej widać.

comp

A teraz porównanie oryginalnej klatki 2 (po lewej) i klatki 2 “zrekonstruowanej” z wycinków klatki 1 (po prawej).

reconstruct

Całkiem nieźle, tło jest w zasadzie idealnie zrekonstruowane, a królik nadal wygląda jak królik, chociaż – niczym monstrum Frankensteina – pozszywany jest z kawałków, dokładnie o rozmiarach  8x8px. Tak to wygląda na animowanym gifie.

recon_ani

 

I po co tyle wysiłku?

A po to, że jak już wspomniałem, zwyczajna rastrowa różnica klatek może się bardzo źle kodować, szczególnie podczas gdy kamera nie jest nieruchoma, tylko się przesuwa (pan), albo zbliża/oddala (zoom), wtedy klatka różnicowa będzie zawierała bardzo wiele szczegółów. W takim razie zobaczmy jak wygląda różnica klatki 1 i klatki 2 i porównajmy z rożnicą zrekonstruowanej klatki 2 i klatki 2.

diff

Skompensowana różnica (po prawej) jest mniej wyraźna niż prosta różnica (piksel po pikselu) obu klatek, można przypuszczać, że po zastosowaniu transformaty kosinusowej, kwantyzacji i kodowania entropijnego (czyli tego, co koder MPEG2 zrobi później z powyższym obrazkiem) skompensowana klatka różnicowa będzie nieco mniejsza niż bez zastosowania kompensacji. W tym przypadku tylko nieznacznie mniejsza (wziąłem oba powyższe obrazki, otworzyłem GIMP-em, zapisałem jako JPEG i plik obrazujący skompensowaną różnicę jest o kilka kB mniejszy od pliku ze zwykłą różnicą), jednak w scenariuszach o których wspominałem wcześniej (kamera wykonująca pan scan, zoom, itp) kompensacja ruchu wniesie bardzo istotną poprawę stopnia kompresji.  Do tego należy dodać, że mechanizmy kompensacji ruchu we współczesnych kodekach są dużo bardziej wyrafinowane. Chociażby w przypadku h.264, który oferuje kodowanie wektorów ruchu z precyzją cwierćpikselową, dodatkowo zmieniającą się wielkość bloku w zależności od charakteru ruchu, wreszcie możliwość kompensacji używając nie jednej, nawet nie dwóch, ale kilku klatek odniesienia.

Podsumowując:

Kodek stosujący kompensację ruchu, aby wysłać kolejną zakodowaną klatkę wysyła najpierw wektory ruchu, które pozwalają zrekonstruować zgrubnie klatkę kolejną używając obecnej, a następnie wysyła zakodowaną, skompensowaną różnicę klatki kolejnej i jej zrekonstruowanej wersji, czym przysłania niedociągnięcia rekonstrukcji.

 

Kod źródłowy

Pozwalam sobie załączyć kod źródłowy aplikacji realizujacej mój chałupniczy algorytm kompensacji ruchu, przy pomocy biblioteki OpenCV. Prezentowana metoda nie ma wiele wspólnego z tymi stosowanymi w rzeczywistych kodekach, choć pewnie dość blisko jej do tej stosowanej w MPEG-1 video. Algorytm jest jedynie ilustracją procesu, który wykorzystywany jest w koderach wideo do poprawy stopnia kompresji. Enjoy.

 

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="">