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.
Especifica la posició, les dimensions, la ubicació de l'inici de recerca i l'escala dels blocs amb què actuarà l'algorisme.
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).
→ C ( x , y ) = ∑ i = 1 n ∑ j = 1 n | F a ( i , j ) − F r ( i + x , j + y ) | {\displaystyle \rightarrow C(x,y)=\sum _{i=1}^{n}\sum _{j=1}^{n}|F_{a}(i,j)-F_{r}(i+x,j+y)|}
→ C ( x , y ) = ∑ i = 1 n ∑ j = 1 n ( F a ( i , j ) − F r ( i + x , j + y ) ) 2 {\displaystyle \rightarrow C(x,y)=\sum _{i=1}^{n}\sum _{j=1}^{n}(F_{a}(i,j)-F_{r}(i+x,j+y))^{2}}
→ C ( x , y ) = 1 n 2 ∑ i = 1 n ∑ j = 1 n | F a ( i , j ) − F r ( i + x , j + y ) | {\displaystyle \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)|}
C ( x , y ) = 1 n 2 ∑ i = 1 n ∑ j = 1 n ( F a ( i , j ) − F r ( i + x , j + y ) ) 2 {\displaystyle 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).
Estratègies intel·ligents que especifiquin on buscar a possibles blocs candidats poden reduir la computació necessària considerablement.
É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ó.
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.
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.
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.
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'.
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.
Aquest darrer algorisme va ésser dissenyat l'any 1996, i como segueix un funcionament força complex, s'exposarà en quatre punts:
