Block matching

Algorisme de Block matching

Block matching és un algorisme utilitzat en l'estimació de moviment, consistent en l'eliminació de redundància temporal entre dos o més fotogrames successius. S'ha convertit en una tècnica fonamental en la majoria dels estàndards de compressió i codificació de vídeo basats en la compensació de moviment.

Cadascuna de les imatges que pertanyen a una seqüència de vídeo es divideix en blocs rectangulars (generalment quadrats), anomenats macroblocs. El mètode pretén detectar el moviment entre imatges respecte als macroblocs que la constitueixen.

Els blocs del fotograma actual són comparats amb els blocs del fotograma de destí o de referència (anterior a l'actual, generalment el primer), desplaçant l'actual al llarg d'una regió concreta de píxels del fotograma de destí.

Un criteri de semblança determina l'elecció del bloc amb major similitud (o que minimitza un error experimental) d'entre els candidats dins de la finestra de recerca de mida fixa del fotograma de referència. Si el bloc escollit no es troba a la mateixa posició en ambdues frames, significa que s'ha mogut. La distància del bloc coincident entre el fotograma actual i el de referència es defineix com el vector de desplaçament estimat, i serà el que s'assignarà a tots els píxels del macrobloc.

En el cas ideal, els píxels corresponents dels blocs coincidents serien exactament iguals. No obstant això, aquest cas s'esdevé en molt rares ocasions, ja que la forma dels objectes en moviment varia respecte al punt de vista de l'observador o la llum reflectida sobre la seva superfície, i sempre es veurà afectat pel soroll. Blocs que presenten un mateix patró de desplaçament poden combinar-se formant objectes en moviment, la qual cosa pot resultar molt atractiva en aplicacions de rastreig.

Regió d'exploració

• La grandària de la regió on dur a terme la recerca és important per trobar el bloc adequat. Desgraciadament, el cost computacional augmenta ràpidament (de forma quasi quadràtica) amb l'increment d'aquesta finestra. El que es fa habitualment és escollir una finestra de superfície lleugerament superior la mida màxima possible dels objectes mòbils.
• Un camp d'exploració petit suposarà que els vectors de desplaçament trobats seran també reduïts, la qual cosa resulta adequada si es treballa amb seqüències de moviment lent, a més a més de reduir la computació necessària.
• El nombre de píxels que separa els diferents blocs candidats que es volen analitzar dins la finestra es correspon amb la longitud del pas de recerca. Si aquesta longitud és igual a un píxel, significa que estem realitzant una recerca exhaustiva o Full Search. En canvi, si optem per un pas major, augmentem la velocitat del procés en reduir el nombre de candidats, però augmentem l'error d'estimació del vector.

Elecció del bloc

Especifica la posició, les dimensions, la ubicació de l'inici de recerca i l'escala dels blocs amb què actuarà l'algorisme.

• Escollir el format concret dels blocs no és trivial. Generalment, els blocs més grans són menys sensibles al soroll, mentre que un bloc de dimensions reduïdes presenta uns contorns més ben definits. El principal factor a l'hora d'escollir les dimensions és la mida dels objectes a rastrejar. Altres factors a tenir en compte són la quantitat de soroll que presenta la seqüència i la textura tant dels objectes com del fons.
• També apareix l'anomenat problema d'obertura quan es treballa amb objectes de color uniforme. Els blocs a l'interior d'aquests objectes no semblen estar movent-se perquè tots els que l'envolten són del mateix color. Unes dimensions de bloc superiors poden ser escollides per pal·liar aquest problema.
• La majoria dels algorismes de block matching utilitzen l'origen de la finestra d'exploració com el centre inicial de recerca i no exploten la correlació entre els blocs que pertanyen a un mateix objecte de la imatge en moviment. Per millorar la precisió es podria utilitzar aquesta correlació per tal de predir una posició inicial que reflectís la tendència de moviment del bloc, permetent així trobar el seu vector de moviment òptim de manera més eficient.
• En gran part dels mètodes de recerca recents, la direcció dels vectors de moviment dels blocs escollits determinen la ubicació del punt d'inici de la següent recerca.

Criteri de comparació

Per exposar els principals criteris de semblança, representats per C(x,y), agafarem un macrobloc quadrat de dimensions n x n. Es mesurarà la diferència entre un bloc del fotograma actual (Fa) i un del de referència (Fr), amb un vector de desplaçament (x,y).

• Sumatori de diferències absolutes (Sum of Absolute Differences, SAD):

$\rightarrow C(x,y)=\sum _{i=1}^{n}\sum _{j=1}^{n}|F_{a}(i,j)-F_{r}(i+x,j+y)|$

• Sumatori de diferències al quadrat (Sum of Squared Differences, SSD):

$\rightarrow C(x,y)=\sum _{i=1}^{n}\sum _{j=1}^{n}(F_{a}(i,j)-F_{r}(i+x,j+y))^{2}$

• Error absolut mitjà (Mean Absolute Error, MAE):

$\rightarrow C(x,y)={\frac {1}{n^{2}}}\sum _{i=1}^{n}\sum _{j=1}^{n}|F_{a}(i,j)-F_{r}(i+x,j+y)|$

• Error quadràtic mitjà (Mean Squared Error, MSE):

$C(x,y)={\frac {1}{n^{2}}}\sum _{i=1}^{n}\sum _{j=1}^{n}(F_{a}(i,j)-F_{r}(i+x,j+y))^{2}$

Altres criteris que tenen un ús estès són la Correlació creuada normalitzada (Normalized Cross Correlation, NCC), la Classificació per diferència de píxel (Pixel Difference Classification, PDC), la Projecció Integral o el MPC (que es basa a ponderar cadascuna de les diferències segons un llindar escollit).

Mètode de recerca

Estratègies intel·ligents que especifiquin on buscar a possibles blocs candidats poden reduir la computació necessària considerablement.

Recerca exhaustiva o Full Search (FS)

És el procediment d'exploració millor i més simple. Realitza una comparació exhaustiva amb tots els blocs que es troben a l'interior de la finestra de recerca, trobant així els vectors de moviment òptims. A causa de l'alt cost computacional requerit per aquest mètode (massa elevat per dur-lo a terme en aplicacions en temps real), al llarg de les últimes dues dècades s'han desenvolupat una gran varietat d'algorismes per obtenir una estimació molt més ràpida amb una distorsió de bloc similar. Per reduir el nombre d'operacions, es pot optar tant per disminuir el nombre de possibles candidats com per reduir els càlculs necessaris per a cada un d'ells. Els més destacats són descrits a continuació per ordre cronològic d'aparició.

Recerca en 3 passos (TSS, 3SS)

Recerca en 3 passos

Logarítmica en 2D

Recerca ortogonal

Recerca creuada

Recerca en espiral

Recerca en 4 passos

Malgrat que va ser dissenyat l'any 1981, s'ha convertit en un dels mètodes més populars per la seva simplicitat i el seu alt rendiment.

En primer lloc, s'escull la longitud del pas de recerca. Des del centre, es comparen els vuit blocs situats en els punts cardinals a la distància d'un pas i se n'escull un en funció d'algun dels criteris comentats anteriorment. A continuació, es redueix la longitud del pas a la meitat, i des del nou centre es tornen a comparar vuit blocs. Finalment, es redueix novament el pas (fins que val 1 píxel) i es repeteix el procés de nou.

Recerca logarítmica en 2D (TDL)

Algorisme també dissenyat l'any 1981 i molt semblant a l'anterior. Consisteix en una recerca distribuïda en etapes on es va reduint la finestra successivament fins a assolir el cas trivial. Tot i que requereix més passos que el 3SS, acostuma a proporcionar més precisió, especialment quan la finestra de recerca és gran.

El bloc al centre de la regió d'exploració i els quatre candidats a un pas de distància situats en els eixos vertical i horitzontal (formant una creu en forma de ‘+'), són comparats amb el bloc actual per determinar la millor coincidència. Si el bloc escollit és el del centre, la longitud del pas es redueix a la meitat; si no és així, l'altre bloc escollit és el nou centre i es torna a iniciar el procés. Quan la longitud del pas arriba a ser 1, els nou blocs al voltant del centre són comparats per trobar el requerit.

Algorisme de recerca ortogonal (OSA)

Mètode híbrid basat en el funcionament dels dos anteriors (3SS i OSA) i introduït l'any 1987. Després d'escollir la longitud del pas (generalment la meitat del desplaçament màxim dins de la finestra), s'inicia amb una etapa horitzontal i una altra vertical.

Es procedeix a l'anàlisi del bloc central i dels dos candidats a ambdós costats de l'eix x, i el que obté un valor de distorsió inferior es converteix en el centre de la següent fase vertical. Ara són els blocs superior i inferior, situats a l'eix y, els que juntament amb el central són comparats, escollint de nou el centre de l'etapa que segueix. Després de les iteracions horitzontal i vertical, la longitud del pas es redueix a la meitat (sempre que sigui menor que 1), i es repeteix el procés de nou. Si fos 1, s'atura i declara a una de les tres posicions de la fase vertical com a bloc òptim.

Algorisme de recerca creuada (CSA)

Aquest algorisme, introduït l'any 1990, manté una certa similitud amb el TDL. El procés d'exploració inicial és quasi idèntic; l'única diferència és que els candidats que són escollits constitueixen una creu en forma de ‘x' en lloc de ‘+'.

La longitud del pas de recerca es redueix a la meitat a cada iteració fins que és igual a 1. En aquesta darrera etapa, si el candidat amb mínima distorsió es troba a la posició inferior esquerra o superior dreta, l'avaluació dels quatre nous blocs seguirà una distribució en creu ‘+'. D'altra banda, si l'escollit es troba en el punt superior esquerra o inferior dret, l'exploració es realitzarà en forma de ‘x'.

Recerca en espiral (SS)

Proposat el 1995, aquest mètode que aquí s'exposa busca combinar algunes idees del 3SS amb les d'altres algorismes, aconseguint accelerar els càlculs necessaris. Igual que en OSA, es pren com a longitud del pas de recerca la meitat del desplaçament màxim dins de la finestra. A continuació, el punt de mínim error s'escull d'entre nou blocs escollits de la següent manera: cinc es prenen de la creu en forma de ‘+' al voltant del centre, i els altres quatre de cadascuna de les cantonades de la finestra. La següent fase segueix la mateixa filosofia, fins que el pas es veu reduït a 1.

Recerca en 4 passos (4SS)

Aquest darrer algorisme va ésser dissenyat l'any 1996, i como segueix un funcionament força complex, s'exposarà en quatre punts:

1. Per començar es fixa un pas de valor 2, i es prenen nou blocs al voltant del centre de la finestra. Es calcula l'error corresponent a cadascú per localitzar al que presenta una distorsió menor. Si aquest bloc resulta ser el central, se segueixen les instruccions explicades al punt 4. Si no ho és, es continua amb el punt 2.
2. Es desplaça el centre de la següent fase al bloc escollit, mantenint la longitud del pas a 2. El patró de recerca a seguir en el procés dependrà de la posició del punt de mínim error de l'etapa prèvia.
3. Continuant amb la mateixa estratègia de recerca, arribarà un moment en què el punt escollit sigui el central, passant al punt 4 i final.
4. Es redueix la longitud del pas a 1 i s'examinen els nou blocs al voltant del centre per trobar, finalment, l'òptim.

Vegeu també

• Còdec de vídeo

Enllaços externs

• Pàgina Web oficial de l'IEEE
• Publicacions recents de l'IEEE
• Pàgina Web oficial del MPEG Arxivat 2008-11-09 a Wayback Machine.
• Pàgina Web oficial de la ITU