Blockmatchningsalgoritm

En Block Matching Algorithm är ett sätt att lokalisera matchande makroblock i en sekvens av digitala videorutor för rörelseuppskattning . Det underliggande antagandet bakom rörelseuppskattning är att mönstren som motsvarar objekt och bakgrund i en bildruta av videosekvens rör sig inom ramen för att bilda motsvarande objekt på den efterföljande bildrutan. Detta kan användas för att upptäcka tidsmässig redundans i videosekvensen, vilket ökar effektiviteten av videokomprimering mellan bildrutorna genom att definiera innehållet i ett makroblock med hänvisning till innehållet i ett känt makroblock som är minimalt annorlunda.

En blockmatchningsalgoritm innefattar att dela upp den aktuella bildrutan i en video i makroblock och jämföra vart och ett av makroblocken med ett motsvarande block och dess närliggande grannar i en närliggande bildruta av videon (ibland bara den föregående). En vektor skapas som modellerar förflyttningen av ett makroblock från en plats till en annan. Denna rörelse, beräknad för alla makroblock som innefattar en ram, utgör den uppskattade rörelsen i en ram.

Sökområdet för en bra makroblockmatchning avgörs av "sökparametern", p, där p är antalet pixlar på alla fyra sidorna av motsvarande makroblock i föregående bildruta. Sökparametern är ett mått på rörelse. Ju större värdet på p, desto större är den potentiella rörelsen och möjligheten att hitta en bra matchning. En fullständig sökning av alla potentiella block är dock en beräkningsmässigt dyr uppgift. Typiska ingångar är ett makroblock med storleken 16 pixlar och ett sökområde på p = 7 pixlar.

Blockmatchning och 3D-filtrering använder detta tillvägagångssätt för att lösa olika omvända problem med bildåterställning, såsom brusreducering och suddighet i både stillbilder och digital video .

Motivering

Rörelseuppskattning är processen för att bestämma rörelsevektorer som beskriver transformationen från en 2D-bild till en annan; vanligtvis från intilliggande bildrutor i en videosekvens. Rörelsevektorerna kan relatera till hela bilden (global rörelseuppskattning) eller specifika delar, såsom rektangulära block, godtyckligt formade lappar eller till och med per pixel. Rörelsevektorerna kan representeras av en translationsmodell eller många andra modeller som kan approximera rörelsen hos en riktig videokamera, såsom rotation och translation i alla tre dimensionerna och zoom.

Att tillämpa rörelsevektorerna på en bild för att förutsäga omvandlingen till en annan bild, på grund av att kameran eller föremålet i bilden rör sig, kallas rörelsekompensation . Kombinationen av rörelseuppskattning och rörelsekompensation är en viktig del av videokomprimering som används av MPEG 1, 2 och 4 såväl som många andra video-codecs .

Rörelseskattningsbaserad videokomprimering hjälper till att spara bitar genom att skicka kodade skillnadsbilder som i sig har mindre entropi i motsats till att skicka en helt kodad bildruta. Den beräkningsmässigt dyraste och mest resursextensiva operationen i hela komprimeringsprocessen är dock rörelseuppskattning. Därför är snabba och beräkningsmässigt billiga algoritmer för rörelseuppskattning ett behov av videokomprimering.

Utvärderingsmått

Ett mått för att matcha ett makroblock med ett annat block baseras på en kostnadsfunktion. Den mest populära när det gäller beräkningskostnad är:

Medelskillnad eller Mean Absolute Difference (MAD) = ${\frac {1}{N^{2}}}\sum _{i=0}^{n-1}\summa _{j=0}^{n-1}|C_{ij} -R_{ij}|$

Mean Squared Error (MSE) = ${\frac {1}{N^{2}}}\ summa _{i=0}^{n-1}\summa _{j=0}^{n-1}(C_{ij}-R_{ij})^{2}$

där N är storleken på makroblocket, och $}}$$\$ displaystyle är pixlarna som jämförs i aktuellt makroblock respektive referensmakroblock

Den rörelsekompenserade bilden som skapas med hjälp av rörelsevektorerna och makroblocken från referensramen kännetecknas av Peak signal-to-noise ratio ( PSNR),

${\text{PSNR}}=10\log _{10}{\frac {({\text{topp till toppvärde för original data}})^{2}}{\text{MSE}}}$

Algoritmer

Block Matching-algoritmer har undersökts sedan mitten av 1980-talet. Många algoritmer har utvecklats, men bara några av de mest grundläggande eller vanligaste har beskrivits nedan.

Uttömmande sökning

Denna algoritm beräknar kostnadsfunktionen på varje möjlig plats i sökfönstret. Detta leder till bästa möjliga matchning av makroblocket i referensramen med ett block i en annan ram. Den resulterande rörelsekompenserade bilden har det högsta signal-brusförhållandet jämfört med någon annan blockmatchningsalgoritm. Detta är dock den mest beräkningsmässigt omfattande blockmatchningsalgoritmen av alla. Ett större sökfönster kräver ett större antal beräkningar.

Optimerad hierarkisk blockmatchning (OHBM)

Algoritmen för optimerad hierarkisk blockmatchning (OHBM) påskyndar den uttömmande sökningen baserat på de optimerade bildpyramiderna.

Trestegssökning

Det är en av de tidigaste snabba blockmatchningsalgoritmerna. Det går enligt följande:

1. Börja med sökplatsen i mitten
2. Ställ in stegstorlek S = 4 och sökparameter p = 7
3. Sök efter 8 platser +/- S pixlar runt platsen (0,0) och platsen (0,0)
4. Välj bland de 9 sökta platserna, den med lägsta kostnadsfunktion
5. Ställ in det nya sökursprunget till den ovan valda platsen
6. Ställ in den nya stegstorleken som S = S/2
7. Upprepa sökningen tills S = 1

Den resulterande platsen för S=1 är den med lägsta kostnadsfunktion och makroblocket på denna plats är den bästa matchningen.

Det finns en minskning av beräkningen med en faktor 9 i denna algoritm. För p=7, medan ES utvärderar kostnaden för 225 makroblock, utvärderar TSS endast för 25 makroblock.

Tvådimensionell logaritmisk sökning

TDLS är nära relaterat till TSS men det är mer exakt för att uppskatta rörelsevektorer för en stor sökfönsterstorlek. Algoritmen kan beskrivas enligt följande,

1. Börja med sökplatsen i mitten
2. Välj en första stegstorlek, säg S = 8
3. Sök efter 4 platser på ett avstånd av S från centrum på X- och Y-axeln
4. Hitta platsen för punkt med lägsta kostnadsfunktion
5. Om en annan punkt än mitten är den bästa matchande punkten,
   1. Välj denna punkt som nytt centrum
   2. Upprepa steg 2 till 3
6. Om den bästa matchningspunkten är i mitten, ställ in S = S/2
7. söks alla 8 platser runt centrum på ett avstånd S
8. Ställ in rörelsevektorn som punkten med lägsta kostnadsfunktionen

Ny trestegssökning

TSS använder ett enhetligt tilldelat kontrollmönster och är benäget att missa små rörelser. NTSS är en förbättring jämfört med TSS eftersom det tillhandahåller ett centrumorienterat söksystem och har bestämmelser för att stoppa halvvägs för att minska beräkningskostnaden. Det var en av de första allmänt accepterade snabba algoritmerna och användes ofta för att implementera tidigare standarder som MPEG 1 och H.261.

Algoritmen fungerar enligt följande:

1. Börja med sökplatsen i mitten
2. Sök efter 8 platser +/- S pixlar med S = 4 och 8 platser +/- S pixlar med S = 1 runt plats (0,0)
3. Välj bland de 16 sökta platserna, den med lägsta kostnadsfunktion
4. Om minimikostnadsfunktionen inträffar vid ursprunget, stoppa sökningen och ställ in rörelsevektorn till (0,0)
5. Om minimikostnadsfunktionen förekommer på en av de 8 platserna vid S = 1, ställ in det nya sökorigin till denna plats.
   1. Kontrollera intilliggande vikter för denna plats, beroende på plats kan den kontrollera antingen 3 eller 5 punkter
6. Den som ger lägst vikt är den som ligger närmast, ställ in rörelsevektorn till den platsen
7. Om den lägsta vikten efter det första steget var en av de 8 platserna vid S = 4, följer den normala TSS-proceduren
   1. Välj bland de 9 sökta platserna, den med lägsta kostnadsfunktion
   2. Ställ in det nya sökursprunget till den ovan valda platsen
   3. Ställ in den nya stegstorleken som S = S/2
   4. Upprepa sökningen tills S = 1

Således kontrollerar den här algoritmen 17 punkter för varje makroblock och det värsta scenariot involverar kontroll av 33 platser, vilket fortfarande är mycket snabbare än TSS

Enkel och effektiv sökning

Tanken bakom TSS är att felytan på grund av rörelse i varje makroblock är unimodal . En unimodal yta är en skålformad yta så att vikterna som genereras av kostnadsfunktionen ökar monotont från det globala minimumet. Emellertid kan en unimodal yta inte ha två minimum i motsatta riktningar och följaktligen kan 8-punktssökningen med fast mönster av TSS modifieras ytterligare för att inkorporera detta och spara beräkningar. SES är en förlängning av TSS som införlivar detta antagande.

SES-algoritmen förbättras jämfört med TSS-algoritmen eftersom varje söksteg i SES är uppdelat i två faser:

• Första fasen :

 • Dela sökningsområdet i fyra  kvadranter  • Börja sökning med tre platser, en i mitten (A) och andra (B och C), S=4 platser bort från A i ortogonala riktningar • Hitta punkter i sökkvadranten för andra fasen med hjälp av viktfördelningen för A, B, C: • Om (MAD(A)>=MAD(B) och MAD(A)>=MAD(C)), välj punkter i andra fas kvadrant IV • Om (MAD(A) >=MAD(B) och MAD(A)<=MAD(C)), välj punkter i andra fas kvadrant I • Om (MAD(A)<MAD(B) och MAD(A)<MAD(C)), välj punkter i andra fas kvadrant II • Om (MAD(A)<MAD(B) och MAD(A)>=MAD(C)), välj punkter i andra fas kvadrant III 

• Andra fasen:

• Hitta platsen med lägst vikt. • Ställ in det nya sökorigin som punkten ovan

• Ställ in den nya stegstorleken som S = S/2

• Upprepa SES-sökningsproceduren tills S=1

• Välj den plats med lägst vikt eftersom rörelsevektor SES är beräkningsmässigt mycket effektiv jämfört med TSS. Emellertid är det uppnådda toppsignal-brusförhållandet dåligt jämfört med TSS eftersom felytorna inte är strikt unimodala i verkligheten.

Fyrstegssökning

Fyrstegssökning är en förbättring jämfört med TSS när det gäller lägre beräkningskostnad och bättre toppsignal-brusförhållande. I likhet med NTSS, använder FSS också center- biased sökning och har ett halvvägsstopp.

Algoritmen fungerar enligt följande:

1. Börja med sökplatsen i mitten
2. Ställ in stegstorlek S = 2, (oavsett sökparameter p)
3. Sök 8 platser +/- S pixlar runt plats (0,0)
4. Välj bland de 9 sökta platserna, den med lägsta kostnadsfunktion
5. Om minimivikten finns i mitten av sökfönstret:
   1. Ställ in den nya stegstorleken som S = S/2 (det vill säga S = 1)
   2. Upprepa sökproceduren från steg 3 till 4
   3. Välj plats med minst vikt som rörelsevektor
6. Om minimivikten hittas på någon av de 8 andra platserna än mitten:
   1. Ställ in det nya ursprunget till den här platsen
   2. Fixera stegstorleken som S = 2
   3. Upprepa sökproceduren från steg 3 till 4. Beroende på platsen för det nya ursprunget, sök igenom 5 platser eller 3 platser
   4. Välj den plats med minst vikt
   5. Om den minst viktade platsen är i mitten av nytt fönster, gå till steg 5, annars gå till steg 6

Diamantsökning

Diamantsökningsalgoritmen (DS) använder ett diamantsökpunktsmönster och algoritmen körs på exakt samma sätt som 4SS. Det finns dock ingen gräns för antalet steg som algoritmen kan ta.

Två olika typer av fasta mönster används för sökning,

• Large Diamond Search Pattern (LDSP)
• Small Diamond Search Pattern (SDSP)

Algoritmen fungerar enligt följande:

• LDSP:

1. 1. Börja med sökplatsen i mitten
   2. Ställ in stegstorlek S = 2
   3. Sök 8 positionspixlar (X,Y) så att (|X|+|Y|=S) runt plats (0,0) med hjälp av ett diamantsökpunktsmönster
   4. Välj bland de 9 sökta platserna, den med lägsta kostnadsfunktion
   5. Om minimivikten hittas i mitten för sökfönstret, gå till SDSP-steget
   6. Om minimivikten hittas på någon av de 8 andra platserna än mitten, ställ in det nya ursprunget till denna plats
   7. Upprepa LDSP

• SDSP:

1. 1. Ställ in det nya sökorigin
   2. Ställ in den nya stegstorleken som S = S/2 (det vill säga S = 1)
   3. Upprepa sökproceduren för att hitta en plats med minst vikt
   4. Välj plats med minst vikt som rörelsevektor

Denna algoritm hittar det globala minimumet mycket exakt eftersom sökmönstret varken är för stort eller för litet. Diamond Search-algoritmen har ett toppsignal-till-brusförhållande nära det för Exhaustive Search med betydligt mindre beräkningskostnader.

Adaptiv Rood Pattern Search

Algoritmen för adaptiv rödmönstersökning (ARPS) använder sig av det faktum att den allmänna rörelsen i en bildruta vanligtvis är koherent , dvs om makroblocken runt det aktuella makroblocket rörde sig i en viss riktning så finns det stor sannolikhet att det aktuella makroblocket kommer också att ha en liknande rörelsevektor . Denna algoritm använder rörelsevektorn för makroblocket till dess omedelbart vänster för att förutsäga sin egen rörelsevektor.

Adaptiv rödmönstersökning körs enligt följande:

1. Börja med sökplatsen i mitten (ursprung)
2. Hitta den förutsagda rörelsevektorn för blocket
3. Ställ in stegstorlek S = max (|X|,|Y|), där (X,Y) är koordinaten för förutsagd rörelsevektor
4. Sök efter rodmönster fördelade punkter runt origo i stegstorlek S
5. Ställ in punkten med minst vikt som ursprung
6. Sök med små diamantsökmönster (SDSP) runt det nya ursprunget
7. Upprepa SDSP-sökning tills minst viktade punkt är i mitten av SDSP

Rödmönstersökning placerar sökningen direkt i ett område där det är stor sannolikhet att hitta ett bra matchande block. Den största fördelen med ARPS framför DS är att om den förutsagda rörelsevektorn är (0, 0), slösar den inte beräkningstid på att göra LDSP, utan den börjar direkt använda SDSP. Dessutom, om den förutsagda rörelsevektorn är långt borta från centrum, sparar ARPS återigen på beräkningar genom att direkt hoppa till den närheten och använda SDSP, medan DS tar sin tid att göra LDSP.

externa länkar

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