Rörelsekompensation

Rörelsekompensation är en av de huvudsakliga algoritmerna  som används vid bearbetning och komprimering av videodata . Algoritmen använder likheten med närliggande bildrutor i videosekvensen och hittar rörelsevektorerna för enskilda delar av bilden (vanligtvis block på 16x16 och 8x8). Användningen av kompensation gör det möjligt att upprepade gånger öka kompressionsförhållandet under kompression på grund av borttagandet av redundans i form av matchande delar av ramar. Används inte bara för komprimering, utan också för videofiltrering , ändring av bildhastighet , etc.

Idén med algoritmen

Att lösa problemet med komprimering har varit ett avgörande problem sedan tillkomsten av digital video. För utvärdering, låt oss ta en videosekvens med följande parametrar:

• Bildstorlek: 720×576 (standardstorlek för europeisk TV ( PAL ), 414 720 pixlar)
• Bildhastighet: 25 fps (även standard för PAL)
• Färgrepresentation: YV12 ( YUV 4:2:0) (16 bitar per 4 pixlar + 8 bitar vardera = 12 bitar per pixel)

Som ett resultat kommer det att ta 14,8 megabyte att spela in eller sända en sekund av sådan video utan komprimering, exklusive ljud och serviceinformation. För att lagra en och en halv timmes film kommer det redan att behövas 79 920 megabyte (78 gigabyte ).

I nästan vilken video som helst är intilliggande ramar lika, har gemensamma objekt, som i regel rör sig parallellt. Och det är ganska naturligt att vilja koda video på ett sådant sätt att objekt inte kodas många gånger, utan en del av deras förskjutningar beskrivs enkelt.[ neutralitet? ]

Även i det här exemplet, om vi tar och packar den 0:e ramen och alla bilder av interframe-skillnaden med arkiveraren, får vi en märkbar[ hur mycket? ] kompressionsförstärkning. Men denna vinst kan ökas avsevärt.

Ett exempel på hur algoritmen fungerar

På grund av den höga beräkningskomplexiteten hos mönsterigenkänningsalgoritmer och den otillräckliga noggrannheten i deras arbete, används olika metoder för att snabbt hitta rörelsevektorer (naturligtvis, inte utan förlust).

1. Den aktuella ramen laddas.
2. Ramen är uppdelad i block (t.ex. 16×16).

3. Block förbigås (varje block bearbetas separat i detta fall).
4. När man räknar ett block, förbigås ett visst område av blocket i sökandet efter maximal överensstämmelse med bilden av blocket på föregående bildruta inom detta område.

5. Sålunda, efter att sökningen är klar, får vi en uppsättning vektorer som indikerar "rörelsen" av bildblock mellan bildrutor. Dessa vektorer kan naturligtvis användas för att skapa en bild av en kompenserad bildruta som bättre approximerar den bildruta för vilken rörelsekompensation utfördes.

Implementeringsfrågor

När du skriver en algoritm kan frågan uppstå - "Hur man utvärderar "likheten" mellan bildfragment?". Några av alternativen:

• Beräkning av SSD (summan av kvadrerade avvikelser ). För ett par block ger det bra resultat i kvalitet (särskilt med riktmärken, eftersom PSNR-måttet (beräknat baserat på standardavvikelsen) är det vanligaste), men kräver betydande resurser (multiplikation är en långsam operation, även tabellen med kvadrater påskyndar inte processen särskilt mycket) och är mycket känslig för förändringar i ljusstyrka. Ju mindre SSD, desto mer lika blocken.
• Jämförelse efter karakteristiska punkter. Kan vara mycket snabb (genom att bara passera ett litet antal punkter), men kan korrelera mycket dåligt med bättre mätvärden.
• Beräkning av SAD (summan av absoluta skillnader). Körs på rimlig tid och ger acceptabelt resultat kvalitetsmässigt (men har dålig ljudtolerans). Den används faktiskt och har bra hastighetsprestanda tack vare användningen av SIMD- tillägg (som gör att du kan utföra många subtraktioner samtidigt utan att använda "intelligenta" processorverktyg för parallellisering av beräkningar).

Den vanligaste beräkningen är SAD. Nästa fråga är: "Hur söker man efter önskat block?"

• Fullständig uppräkning (fullständig sökning). I något område runt det bearbetade blocket söks koordinaterna för det önskade blocket. Om vi ​​har ett block på 16×16 och ett sökområde på ±32 × ±32, måste vi beräkna SAD 4096 gånger för varje bearbetat block. Detta är långsamt, men det ger ett garanterat bästa resultat för ett givet mått.
• Mönstersökning. Går snabbt och ger inte det bästa resultatet.
• Spiralsökning. Räknar,[ av vem? ] att ju närmare blocket är det nuvarande, desto mer sannolikt är det att det är det du letar efter. Och dess noggrannhet minskar från mitten till kanterna av sökområdet. Har en extra fördel. På bilden (i den här artikeln) med rörelsevektorer är långa vektorer synliga på himlen, eftersom en fullständig uppräkning användes från det övre vänstra hörnet av sökområdet, även om det är uppenbart att det praktiskt taget inte finns någon skillnad med nollvektorer , men långa vektorer försämrar kompressibiliteten för vektorfältet, och nollvektorer - nej. I en spiralsökning finns det alltid nollvektorer på de oförändrade sektionerna.

Implementeringsexempel

Implementering av brute force-metoden i C++