Algorytm dopasowywania bloków

Algorytm dopasowywania bloków to sposób lokalizowania pasujących makrobloków w sekwencji cyfrowych klatek wideo w celu oszacowania ruchu . Założenie leżące u podstaw szacowania ruchu polega na tym, że wzorce odpowiadające obiektom i tłu w klatce sekwencji wideo poruszają się w obrębie klatki, tworząc odpowiednie obiekty w kolejnej klatce. Można to wykorzystać do wykrycia redundancji czasowej w sekwencji wideo, zwiększając skuteczność kompresji wideo między ramkami poprzez zdefiniowanie zawartości makrobloku przez odniesienie do zawartości znanego makrobloku, który jest minimalnie inny.

Algorytm dopasowywania bloków polega na podzieleniu bieżącej klatki wideo na makrobloki i porównaniu każdego z makrobloków z odpowiednim blokiem i sąsiednimi sąsiadami w pobliskiej klatce wideo (czasami tylko z poprzednią). Tworzony jest wektor , który modeluje ruch makrobloku z jednego miejsca do drugiego. Ruch ten, obliczony dla wszystkich makrobloków składających się na ramkę, stanowi ruch estymowany w ramce.

Obszar wyszukiwania dobrego dopasowania makrobloku jest określany przez „parametr wyszukiwania”, p, gdzie p jest liczbą pikseli na wszystkich czterech bokach odpowiedniego makrobloku w poprzedniej klatce. Parametr wyszukiwania jest miarą ruchu. Im większa wartość p, tym większy ruch potencjalny i możliwość znalezienia dobrego dopasowania. Pełne przeszukanie wszystkich potencjalnych bloków jest jednak zadaniem kosztownym obliczeniowo. Typowe dane wejściowe to makroblok o rozmiarze 16 pikseli i obszar wyszukiwania p = 7 pikseli.

Dopasowywanie bloków i filtrowanie 3D wykorzystuje to podejście do rozwiązywania różnych odwrotnych problemów związanych z odtwarzaniem obrazu , takich jak redukcja szumów i usuwanie rozmycia zarówno w przypadku zdjęć, jak i cyfrowego wideo .

Motywacja

Szacowanie ruchu to proces określania wektorów ruchu , które opisują transformację z jednego obrazu 2D do drugiego; zwykle z sąsiednich klatek w sekwencji wideo. Wektory ruchu mogą odnosić się do całego obrazu (oszacowanie globalnego ruchu) lub określonych części, takich jak prostokątne bloki, obszary o dowolnym kształcie, a nawet poszczególne piksele. Wektory ruchu mogą być reprezentowane przez model translacyjny lub wiele innych modeli, które mogą przybliżać ruch prawdziwej kamery wideo, takie jak obrót i translacja we wszystkich trzech wymiarach i zoom.

Zastosowanie wektorów ruchu do obrazu w celu przewidywania transformacji do innego obrazu, ze względu na poruszającą się kamerę lub obiekt na obrazie, nazywa się kompensacją ruchu . Połączenie szacowania ruchu i kompensacji ruchu jest kluczowym elementem kompresji wideo stosowanej w formatach MPEG 1, 2 i 4, a także w wielu innych kodekach wideo .

Kompresja wideo oparta na szacowaniu ruchu pomaga oszczędzać bity, wysyłając zakodowane obrazy różnicowe, które mają z natury mniejszą entropię niż wysyłanie w pełni zakodowanej klatki. Jednak najbardziej kosztowną obliczeniowo i pochłaniającą duże zasoby operacją w całym procesie kompresji jest szacowanie ruchu. W związku z tym szybkie i niedrogie obliczeniowo algorytmy szacowania ruchu wymagają kompresji wideo.

Metryki oceny

Metryka dopasowania makrobloku do innego bloku jest oparta na funkcji kosztu. Najpopularniejszym pod względem kosztów obliczeniowych jest:

Średnia różnica lub średnia bezwzględna różnica (MAD) = ${\ Displaystyle {\ Frac {1} {N ^ {2}}} \ suma _ {i = 0} ^ {n-1} \ suma _ {j = 0} ^ {n-1} | C_ {ij} -R_{ij}|}$

Średni błąd kwadratowy (MSE) = $\ Displaystyle {\ Frac {1} {N ^ {2}}} \ suma _{i=0}^{n-1}\suma _{j=0}^{n-1}(C_{ij}-R_{ij})^{2}}$

gdzie N to rozmiar makrobloku, a i $}$$}$ R_ to piksele porównywane odpowiednio w bieżącym makrobloku i makrobloku odniesienia.

Obraz z kompensacją ruchu, który jest tworzony przy użyciu wektorów ruchu i makrobloków z ramki odniesienia, charakteryzuje się szczytowym stosunkiem sygnału do szumu (PSNR),

${\ Displaystyle {\ tekst {PSNR}} = 10 \ log _ {10} {\ Frac {({\ tekst {wartość szczytowa oryginału dane}})^{2}}{\text{MSE}}}}$

Algorytmy

Algorytmy dopasowywania bloków są badane od połowy lat 80. Opracowano wiele algorytmów, ale poniżej opisano tylko niektóre z najbardziej podstawowych lub najczęściej używanych.

Wyczerpujące wyszukiwanie

Algorytm ten oblicza funkcję kosztu w każdej możliwej lokalizacji w oknie wyszukiwania. Prowadzi to do najlepszego możliwego dopasowania makrobloku w ramce odniesienia z blokiem w innej ramce. Wynikowy obraz z kompensacją ruchu ma najwyższy szczytowy stosunek sygnału do szumu w porównaniu z jakimkolwiek innym algorytmem dopasowywania bloków. Jest to jednak najbardziej rozbudowany obliczeniowo algorytm dopasowywania bloków spośród wszystkich. Większe okno wyszukiwania wymaga większej liczby obliczeń.

Zoptymalizowane dopasowywanie bloków hierarchicznych (OHBM)

Zoptymalizowany algorytm dopasowywania bloków hierarchicznych (OHBM) przyspiesza wyczerpujące wyszukiwanie w oparciu o zoptymalizowane piramidy obrazów.

Wyszukiwanie w trzech krokach

Jest to jeden z najwcześniejszych algorytmów szybkiego dopasowywania bloków. Działa w następujący sposób:

1. Zacznij od lokalizacji wyszukiwania w środku
2. Ustaw wielkość kroku S = 4 i wyszukaj parametr p = 7
3. Przeszukaj 8 lokalizacji +/- S pikseli wokół lokalizacji (0,0) i lokalizacji (0,0)
4. Wybierz spośród 9 wyszukiwanych lokalizacji, tę z funkcją minimalnego kosztu
5. Ustaw nowy początek wyszukiwania na wybraną powyżej lokalizację
6. Ustaw nowy rozmiar kroku jako S = S/2
7. Powtarzaj procedurę wyszukiwania, aż S = 1

Wynikowa lokalizacja dla S=1 to ta z funkcją minimalnego kosztu, a makroblok w tej lokalizacji jest najlepiej dopasowany.

W tym algorytmie występuje redukcja obliczeń o współczynnik 9. Dla p=7, podczas gdy ES szacuje koszt dla 225 makrobloków, TSS ocenia tylko dla 25 makrobloków.

Dwuwymiarowe wyszukiwanie logarytmiczne

TDLS jest blisko spokrewniony z TSS, jednak jest dokładniejszy do szacowania wektorów ruchu dla dużego rozmiaru okna wyszukiwania. Algorytm można opisać w następujący sposób,

1. Zacznij od wyszukiwania lokalizacji w centrum
2. Wybierz początkowy rozmiar kroku, powiedzmy S = 8
3. Wyszukaj 4 lokalizacje w odległości S od środka na osiach X i Y
4. Znajdź lokalizację punktu z funkcją najmniejszego kosztu
5. Jeśli punkt inny niż środek jest najlepiej dopasowanym punktem,
   1. Wybierz ten punkt jako nowy środek
   2. Powtórz kroki od 2 do 3
6. Jeśli najlepiej dopasowany punkt znajduje się w środku, ustaw S = S/2
7. przeszukiwanych jest wszystkie 8 lokalizacji wokół środka w odległości S
8. Ustaw wektor ruchu jako punkt z funkcją najmniejszego kosztu

Nowe wyszukiwanie w trzech krokach

TSS używa jednolicie przydzielonego wzorca sprawdzania i jest podatny na pomijanie małych ruchów. NTSS jest ulepszeniem w stosunku do TSS, ponieważ zapewnia schemat wyszukiwania ukierunkowany na środek i ma możliwość zatrzymania się w połowie w celu zmniejszenia kosztów obliczeniowych. Był to jeden z pierwszych powszechnie akceptowanych szybkich algorytmów i często używany do implementacji wcześniejszych standardów, takich jak MPEG 1 i H.261.

Algorytm działa w następujący sposób:

1. Zacznij od lokalizacji wyszukiwania w środku
2. Wyszukaj 8 lokalizacji +/- S pikseli przy S = 4 i 8 lokalizacji +/- S pikseli przy S = 1 wokół lokalizacji (0,0)
3. Wybierz spośród 16 wyszukiwanych lokalizacji tę z funkcją minimalnego kosztu
4. Jeśli funkcja minimalnego kosztu występuje w punkcie początkowym, zatrzymaj wyszukiwanie i ustaw wektor ruchu na (0,0)
5. Jeśli funkcja minimalnego kosztu występuje w jednej z 8 lokalizacji przy S = 1, ustaw nowy początek wyszukiwania na tę lokalizację
   1. Sprawdź sąsiednie wagi dla tej lokalizacji, w zależności od lokalizacji może sprawdzić 3 lub 5 punktów
6. Ten, który daje najniższą wagę, jest najbliższym dopasowaniem, ustaw wektor ruchu na to miejsce
7. Jeśli najniższa waga po pierwszym kroku była jedną z 8 lokalizacji w S = 4, następuje normalna procedura TSS
   1. Wybierz spośród 9 wyszukiwanych lokalizacji, tę z funkcją minimalnego kosztu
   2. Ustaw nowy początek wyszukiwania na wybraną powyżej lokalizację
   3. Ustaw nowy rozmiar kroku jako S = S/2
   4. Powtarzaj procedurę wyszukiwania, aż S = 1

Zatem ten algorytm sprawdza 17 punktów dla każdego makrobloku, a najgorszy scenariusz polega na sprawdzeniu 33 lokalizacji, co wciąż jest znacznie szybsze niż TSS

Proste i wydajne wyszukiwanie

Ideą TSS jest to, że powierzchnia błędu spowodowana ruchem w każdym makrobloku jest unimodalna . Powierzchnia jednomodalna to powierzchnia w kształcie misy, taka że wagi generowane przez funkcję kosztu rosną monotonicznie od globalnego minimum. Jednak powierzchnia jednomodalna nie może mieć dwóch minimów w przeciwnych kierunkach, a zatem 8-punktowe przeszukiwanie stałego wzorca TSS można dalej modyfikować, aby uwzględnić to i zapisać obliczenia. SES jest rozszerzeniem TSS, które uwzględnia to założenie.

Algorytm SES ulepsza algorytm TSS, ponieważ każdy krok wyszukiwania w SES jest podzielony na dwie fazy:

• Pierwsza faza :

 • Podziel obszar poszukiwań na cztery  ćwiartki  • Rozpocznij wyszukiwanie od trzech lokalizacji, jednej w środku (A) i innych (B i C), S=4 lokalizacje oddalone od A w kierunkach ortogonalnych • Znajdź punkty w ćwiartce wyszukiwania dla drugiej fazy za pomocą rozkład wag dla A, B, C: • Jeśli (MAD(A)>=MAD(B) i MAD(A)>=MAD(C)), wybierz punkty w drugiej ćwiartce fazy IV • Jeśli (MAD(A) >=MAD(B) i MAD(A)<=MAD(C)), wybierz punkty w drugiej ćwiartce I fazy • If (MAD(A)<MAD(B) i MAD(A)<MAD(C)), wybierz punkty w drugiej ćwiartce fazy II • Jeśli (MAD(A)<MAD(B) i MAD(A)>=MAD(C)), wybierz punkty w drugiej ćwiartce fazy III 

• Druga faza:

• Znajdź lokalizację o najniższej wadze • Ustaw nowy początek wyszukiwania jako punkt znaleziony powyżej

• Ustaw nowy rozmiar kroku jako S = S/2

• Powtarzaj procedurę wyszukiwania SES, aż S=1

• Wybierz lokalizację o najniższej wadze, ponieważ wektor ruchu SES jest bardzo wydajny obliczeniowo w porównaniu z TSS. Jednak osiągnięty szczytowy stosunek sygnału do szumu jest słaby w porównaniu z TSS, ponieważ powierzchnie błędów nie są w rzeczywistości ściśle jednomodalne.

Wyszukiwanie w czterech krokach

Four Step Search to ulepszenie w stosunku do TSS pod względem niższych kosztów obliczeniowych i lepszego szczytowego stosunku sygnału do szumu. Podobnie jak NTSS, FSS również wykorzystuje z ukierunkowaniem na środek i zapewnia zatrzymanie w połowie drogi.

Algorytm działa w następujący sposób:

1. Zacznij od lokalizacji wyszukiwania w środku
2. Ustaw wielkość kroku S = 2, (niezależnie od szukanego parametru p)
3. Przeszukaj 8 lokalizacji +/- S pikseli wokół lokalizacji (0,0)
4. Wybierz spośród 9 wyszukiwanych lokalizacji, tę z funkcją minimalnego kosztu
5. Jeśli minimalna waga zostanie znaleziona w środku okna wyszukiwania:
   1. Ustaw nowy rozmiar kroku jako S = S/2 (czyli S = 1)
   2. Powtórz procedurę wyszukiwania od kroków 3 do 4
   3. Wybierz lokalizację o najmniejszej wadze jako wektor ruchu
6. Jeśli minimalna waga znajduje się w jednym z 8 miejsc innych niż środek:
   1. Ustaw nowy początek w tej lokalizacji
   2. Ustal rozmiar kroku jako S = 2
   3. Powtórz procedurę wyszukiwania od kroków 3 do 4. W zależności od lokalizacji nowego pochodzenia przeszukaj 5 lokalizacji lub 3 lokalizacje
   4. Wybierz lokalizację o najmniejszej wadze
   5. Jeśli najmniejsza waga znajduje się na środku nowego okna, przejdź do kroku 5, w przeciwnym razie przejdź do kroku 6

Wyszukiwanie diamentów

Algorytm wyszukiwania diamentów (DS) wykorzystuje wzorzec punktu wyszukiwania diamentów, a algorytm działa dokładnie tak samo jak algorytm 4SS. Nie ma jednak ograniczeń co do liczby kroków, które może wykonać algorytm.

Do wyszukiwania używane są dwa różne rodzaje ustalonych wzorców,

• Wzorzec wyszukiwania dużego rombu (LDSP)
• Wzorzec wyszukiwania małego rombu (SDSP)

Algorytm działa w następujący sposób:

• LDSP:

1. 1. Zacznij od lokalizacji wyszukiwania w środku
   2. Ustaw rozmiar kroku S = 2
   3. Przeszukaj 8 lokalizacji w pikselach (X,Y) takich, że (|X|+|Y|=S) wokół lokalizacji (0,0) za pomocą wzorca rombowego punktu wyszukiwania
   4. Wybierz spośród 9 wyszukiwanych lokalizacji, tę z funkcją minimalnego kosztu
   5. Jeśli minimalna waga znajduje się w środku okna wyszukiwania, przejdź do kroku SDSP
   6. Jeśli minimalna waga zostanie znaleziona w jednym z 8 miejsc innych niż środek, ustaw nowy początek na to miejsce
   7. Powtórz LDSP

• SDSP:

1. 1. Ustaw nowe źródło wyszukiwania
   2. Ustaw nowy rozmiar kroku jako S = S/2 (czyli S = 1)
   3. Powtórz procedurę wyszukiwania, aby znaleźć lokalizację o najmniejszej wadze
   4. Wybierz lokalizację o najmniejszej wadze jako wektor ruchu

Algorytm ten znajduje globalne minimum bardzo dokładnie, ponieważ wzorzec wyszukiwania nie jest ani za duży, ani za mały. Algorytm wyszukiwania diamentowego ma szczytowy stosunek sygnału do szumu zbliżony do algorytmu wyszukiwania wyczerpującego przy znacznie niższych nakładach obliczeniowych.

Adaptacyjne wyszukiwanie wzoru Rood

Algorytm przeszukiwania adaptacyjnego wzorca rood (ARPS) wykorzystuje fakt, że ogólny ruch w klatce jest zwykle spójny , tzn. jeśli makrobloki wokół bieżącego makrobloku poruszały się w określonym kierunku, istnieje duże prawdopodobieństwo , że bieżący makroblok będzie również miał podobny wektor ruchu . Algorytm ten wykorzystuje wektor ruchu makrobloku bezpośrednio po jego lewej stronie do przewidywania własnego wektora ruchu.

Adaptacyjne wyszukiwanie wzoru tęczowego przebiega w następujący sposób:

1. Zacznij od lokalizacji wyszukiwania w centrum (początek)
2. Znajdź przewidywany wektor ruchu dla bloku
3. Ustaw rozmiar kroku S = max (|X|,|Y|), gdzie (X,Y) to współrzędna przewidywanego wektora ruchu
4. Wyszukaj rozłożone punkty wzoru tęczowego wokół początku układu współrzędnych o wielkości kroku S
5. Ustaw punkt o najmniejszej wadze jako początek
6. Wyszukiwanie za pomocą wzorca wyszukiwania małych rombów (SDSP) wokół nowego punktu początkowego
7. Powtarzaj wyszukiwanie SDSP, aż punkt o najmniejszej wadze znajdzie się w środku SDSP

Wyszukiwanie wzoru tęczowego bezpośrednio umieszcza wyszukiwanie w obszarze, w którym istnieje duże prawdopodobieństwo znalezienia dobrze pasującego bloku. Główną zaletą ARPS w porównaniu z DS jest to, że jeśli przewidywany wektor ruchu wynosi (0, 0), nie marnuje czasu obliczeniowego na wykonywanie LDSP, ale bezpośrednio rozpoczyna korzystanie z SDSP. Co więcej, jeśli przewidywany wektor ruchu znajduje się daleko od środka, ARPS ponownie oszczędza na obliczeniach, przeskakując bezpośrednio do tej okolicy i używając SDSP, podczas gdy DS nie spieszy się z LDSP.

Linki zewnętrzne

1. http://www.mathworks.com/matlabcentral/fileexchange/8761-block-matching-algorithms-for-motion-estimation

2. https://www.ece.cmu.edu/~ee899/project/deepak_mid.htm