Estimació de moviment

Entenem estimació de moviment com el procés a partir del qual obtenim els vectors de moviment (VM) de cada macrobloc (MB) de la imatge a codificar respecte a una (o més) imatges de referència. L'estimació de moviment és una part molt important del procés de codificació de vídeo i s'utilitza en estàndards i còdecs tan populars com la família de MPEG's (MPEG-1, MPEG-2, MPEG-4), l'últim H.264/MPEG-4 AVC o el software lliure Theora.

Introducció

La codificació de vídeo pretén representar seqüències d'imatges amb el menor nombre de bits possible. Per això, els mètodes de codificació de vídeo apliquen tant codificació Intraimatge com Interimatge. Amb el primer tipus s'intenta eliminar la redundància espacial dins de cada quadre (frame), mentre que amb la codificació Inter explotem la redundància temporal de la seqüència a codificar. L'estimació i compensació de moviment són els mètodes que permeten aquest tipus de codificació.

La imatge es divideix en blocs (sovint quadrats d'uns quants píxels, per exemple 4x4) i aquests s'agrupen formant MB. Com hem dit l'estimació de moviment ens permet obtenir els VM de cada MB. L'aplicació d'aquests vectors per crear la nova imatge (imatge compensada) s'anomena compensació de moviment que, juntament amb el càlcul de la imatge error entre la imatge compensada i la imatge original que volem codificar, és el que, en la gran majoria de còdecs, s'envia al descodificador.

L'estimació de moviment és un procés amb una alta complexitat de càlcul i sovint representa 2/3 del cost computacional en la codificació de vídeo. Com sempre, ens trobarem amb un compromís de "Rate-distorcion", és a dir temps de processament i mida de fitxer envers qualitat del vídeo comprimit. Això fa que, actualment, moltes de les investigacions dins el camp de la codificació de vídeo se centrin a buscar algorismes que puguin realitzar més eficientment l'estimació de moviment.

Backward vs. Forward

És important diferenciar entre estimació/compensació Backward i estimació/compensació Forward, així com entendre perquè els mètodes de compressió de vídeo fan servir el primer cas. Aquesta classificació diferencia en quina de les dues imatges (referència i a codificar) es defineixen els MB dels quals volem buscar els vectors de moviment que els corresponen.

Parlarem d'estimació Forward si "dibuixem" els MB en la imatge referència. Calculem els VM a partir de la imatge referència. Per a cada MB de la imatge referència busquem on ha anat a parar en la imatge actual (a codificar) i, a partir de la nova posició, extraiem els VM. Pot ser que alguns MB, o píxels, de la imatge referència no apareguin en l'original i que per tant identifiquem una mateixa zona de la imatge a codificar com la més semblant a més d'un MB de la imatge referència (1). Per generar la imatge compensada agafarem cada MB de la de referència i el col·locarem en la nova posició que li correspon segons els VM que hem calculat. Si ens trobem amb (1) alguns píxels de la imatge compensada0 se sobreescriuran i d'altres quedaran sense definir generant "forats".

Aquest problema no passa si apliquem estimació Backward, que defineix els MB en la imatge a codificar i busca on es trobaven (o es trobaran) en la de referència. Calculem els Vm a partir imatge actual. D'aquesta manera, per a omplir cada MB de la imatge compensada anirem a buscar on es trobava en la imatge de referència i en copiarem tots els píxels. Aquí l'únic que fem és omplir MB segons els VM que hem trobat i per tant no hi haurà cap píxel sense definir. És per aquesta raó que els estàndards de codificació de vídeo utilitzen l'estimació Backward i no pas la Forward.

Algorismes

Els estàndards de codificació de vídeo defineixen com ha de ser el bitstream del senyal codificat, però no expliquen com s'ha de fer per a generar-lo. Per tant, existeixen multitud de codificadors de cada estàndard que competeixen entre si per a veure quin d'ells és més eficient.

Hi ha diferents algorismes pel càlcul dels VM, com hem explicat s'està investigant molt sobre això. Diferenciem entre mètodes de cerca exhaustiva i mètodes parcials, que estalvien temps de processament a canvi d'introduir més pèrdues en la seqüència final.

Block Matching

Block matching és el mètode més utilitzat perquè és el més fàcil d'implementar i el que aconsegueix una major qualitat. Per tal de simplificar el problema, assumim:

Moviment només de translació (canvi de posició)
Il·luminació sense canvis
Imatge sense oclusions

Es tracta de realitzar una cerca exhaustiva ("Full Search", FS) píxel a píxel de la zona (de dimensions iguals al MB) de la imatge referència més semblant al MB que estem considerant.

Hi ha diferents mètodes per trobar el MB més semblant en la imatge referència, però en general es tracta de buscar el mínim entra la suma de les diferències entre tots els píxels de la imatge a codificar i de la de referència dins el MB que estem considerant.

En funció de la diferència entre la posició en la imatge actual i la posició en la imatge de referència d'un MB n'extraiem els VM que li corresponen.

Aquesta operació és tan costosa perquè si per cada MB es busqués per tota la imatge (de dimensions MxN i el MB BxB) es realitzarien: (N-B+1)•(M-B+1)•2B operacions per a trobar els VM d'un sol MB, la qual cosa és del tot inviable per a aplicacions a temps real. Per això sempre s'utilitza una finestra de recerca de dimensions 2Bx2B (el doble del MB) i només es busca el MB dins d'aquesta. D'aquesta manera aconseguim reduir notablement el nombre d'operacions, fins a (B+1)²•2B, per a trobar els VM d'un MB i a més aconseguim que aquest procés no depengui de les dimensions de la imatge.

Direccions Continuades

Aquest tipus de mètodes calculen les diferències en menys punts. Hi ha una gran oferta d'algorismes que milloren el cost computacional de l'estimació de moviment assumint que la funció error (SAD) és convexa i només té un mínim relatiu dins la finestra de recerca. Amb aquesta simplificació, que es compleix molt sovint, ja no cal que calculem la SAD de tots els píxels de la finestra, sinó que començarem en un píxel determinat, ens mirarem els del seu voltant i ens mourem pel gradient més negatiu.

La diferència de qualitat entre la utilització d'aquests mètodes i la recerca exhaustiva és pràcticament inapreciable. En funció de quin punt és el primer que calculem i quins ens mirem en cada iteració, trobem els següents mètodes:

Recerca en 3 passos (TSS)
Recerca en 4 passos (4SS)
Recerca en Diaman (DS)
Recerca logarítmica en 2D (TDL)
Algorisme de recerca ortogonal (OSA)
Recerca en espiral (SS)'

Distorsió Parcial

Dins d'aquest grup trobem els algorismes que redueixen el temps de processament a partir de calcular menys diferències cada vegada que desplacem el MB en la imatge de referència. La idea és que si, en algun moment del càlcul de la SAD en una determinada posició, se supera el valor mínim de la SAD total calculada en una posició anterior, no cal que calculem més diferències i podem saltar al següent punt. La gràcia d'aquests mètodes és trobar una SAD mínima com més aviat millor perquè com més aviat trobem el mínim global en la nostre cerca, més aviat podem descartar les SAD's parcials dels altres candidats. Aquests mètodes poden introduir, o no, pèrdues en la seqüència generada, però aquestes pèrdues resulten inapreciables.

Recerca de Distorsió Parcial (PDS) (sense pèrdues)
Recerca de Distorsió Parcial Normalitzada (NPDS) (amb pèrdues)
Recerca de Distorsió Parcial basada en transformada Hadamard (HPDS) (sense pèrdues)

Aproximació Multiresolució

Una altra manera d'estalviar temps és fer l'estimació de moviment delmant primer les dues imatges. D'aquesta manera tant la mida del MB, com la de la finestra s'hauran reduït. Haurem de buscar en menys punts. A l'hora de fer la compensació, però, sí que utilitzarem les imatges en les dimensions originals i els VM que utilitzarem seran els obtinguts en l'estimació, però escalats. D'Aquesta manera aconseguim reduir el temps de processament a canvi de patir una pèrdua de qualitat, que pot resultar important, en la imatge processada, pròpia de qualsevol procés de delmació-interpolació.

Altres entrades interès

Enllaços externs