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:

ffmpeg -i big_buck_bunny_480p_h264.mov -ss 241 -vframes 50 bbimg/bb%02d.png

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:

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

 

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.

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

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ć.

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

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.

 

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.

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.

#include <opencv2/highgui/highgui.hpp>
#include <opencv2/imgproc/imgproc.hpp>
#include <vector>

using namespace std;

static const unsigned BLOCK_SIZE = 8;
static const unsigned SEARCH_SIZE = 16;

static const char* FRAME_1_FNAME = "bb32.png";
static const char* FRAME_2_FNAME = "bb33.png";

static const char* RECONSTRUCT_FNAME = "reconstruct.png";

static const char* DIFF_FNAME = "diff.png";
static const char* COMP_DIFF_FNAME = "cdiff.png";

static cv::Point bestMatch(cv::Mat& pattern, cv::Mat& area)
{
    cv::Point res;
    unsigned patternWidth = pattern.size().width;
    unsigned patternHeight = pattern.size().height;
    unsigned areaWidth = area.size().width;
    unsigned areaHeight = area.size().height;

    uint32_t minsumsquares = ~(0U);
    cv::Mat calc(pattern.size(), pattern.type());
    for (unsigned yy = 0; yy + patternHeight < areaHeight; ++yy) {

        for (unsigned xx = 0; xx + patternWidth < areaWidth; ++xx) {
            cv::Mat areaRect = area(cv::Range(yy, yy + patternHeight), cv::Range(xx, xx + patternWidth));
            cv::absdiff(areaRect, pattern, calc);
            cv::multiply(calc, calc, calc);
            cv::Scalar sumsquares_s = cv::sum(calc);
            unsigned sumsquares = (unsigned)sumsquares_s(0) + sumsquares_s(1) + sumsquares_s(2);
            if (sumsquares < minsumsquares) {
                minsumsquares = sumsquares;
                res.x = xx;
                res.y = yy;
            }
        }
    }
    return res;
}

int main()
{
    cv::Mat img0 = cv::imread(FRAME_1_FNAME);
    cv::Mat img1 = cv::imread(FRAME_2_FNAME);
    cv::Mat reconstruct(img1.size(), img1.type());
    cv::Mat diff(img1.size(), img1.type());

    const unsigned rows = img0.size().height;
    const unsigned cols = img0.size().width;

    cv::Mat img0_16(img0.size(), CV_16UC3);
    cv::Mat img1_16(img0.size(), CV_16UC3);

    img0.convertTo(img0_16, CV_16U);
    img1.convertTo(img1_16, CV_16U);

    // iterate over rows
    for (unsigned yy = 0; yy + BLOCK_SIZE <= rows; yy += BLOCK_SIZE) {
        // over columns
        for (unsigned xx = 0; xx + BLOCK_SIZE < cols; xx += BLOCK_SIZE) {
            unsigned startx = (xx > SEARCH_SIZE) ? xx - SEARCH_SIZE : 0;
            unsigned starty = (yy > SEARCH_SIZE) ? yy - SEARCH_SIZE : 0;
            unsigned xshift = (xx - startx);
            unsigned yshift = (yy - starty);
            unsigned stopx = ((xx + BLOCK_SIZE + SEARCH_SIZE) < cols) ? xx + BLOCK_SIZE + SEARCH_SIZE : cols;
            unsigned stopy = ((yy + BLOCK_SIZE + SEARCH_SIZE) < rows) ? yy + BLOCK_SIZE + SEARCH_SIZE : rows;
            cv::Mat area = img0_16(cv::Range(starty, stopy), cv::Range(startx, stopx));
            cv::Mat pattern = img1_16(cv::Range(yy, yy + BLOCK_SIZE), cv::Range(xx, xx + BLOCK_SIZE));
            cv::Point matchVector = bestMatch(pattern, area);
            matchVector.x -= xshift;
            matchVector.y -= yshift;
            cv::Mat srcRect = img0(cv::Range(yy + matchVector.y, yy + matchVector.y + BLOCK_SIZE), cv::Range(xx + matchVector.x, xx + matchVector.x + BLOCK_SIZE));
            cv::Mat dstRect = reconstruct(cv::Range(yy, yy + BLOCK_SIZE), cv::Range(xx, xx + BLOCK_SIZE));
            srcRect.copyTo(dstRect);
        }
    }
    cv::imwrite(RECONSTRUCT_FNAME, reconstruct);

    absdiff(img0, img1, diff);
    cv::imwrite(DIFF_FNAME, diff);

    absdiff(img1, reconstruct, diff);
    cv::imwrite(COMP_DIFF_FNAME, diff);

    return 0;
}