Block matching

Algoritme utilisat en la estimació de moviment, consistent en l'eliminació de redundància temporal entre dos o més fotogramas successius. S'ha convertit en una tècnica fonamental en la majoria dels estàndarts de compressió i codificació de video basats en la compensació de moviment.

Cada una de les imàgens pertanyents a una seqüència de video es dividix en blocs rectangulars (generalment quadrats) denominats macrobloques. El método pretén detectar el moviment entre imàgens sobre els macrobloques que les constituïxen.

Els blocs del fotograma actual són cotejats en els blocs del fotograma de destí o de referència (anterior a l'actual, generalment el primer), esgolant l'actual a lo llarc d'una regió concreta de píxels del fotograma de destí.

Un criteri de semblança determina l'elecció del bloc en major similitut (o que minimisa un error medit) d'entre els candidats dins de la finestra de busca de tamany fix del fotograma de referència. Si el bloc elegit no es troba en la mateixa posició en abdós frames, significa que s'ha mogut. La distància del bloc coincidente entre el fotograma actual i el de referència es definix com el vector de desplaçament estimat, i serà el que se li assigne a tots els píxelés del macrobloque.

En el cas ideal, els píxels corresponents dels blocs coincidentes serien exactament iguals. No obstant, eixe cas succeïx en molt rares ocasions, ya que la forma dels objectes en moviment varia sobre el punt de vista de l'observador o la llum reflectida sobre la seua superfície, i sempre nos vorem afectats pel soroll. Erro al crear miniatura:

Blocs que presenten un mateix patró de desplaçament poden combinar-se formant objectes en moviment, la qual cosa pot resultar molt atractiu en aplicacions de rastreig.

Regió d'exploració

• El tamany de la regió a on portar a terme la busca és important per a donar en el bloc adequat. Desgraciadament, el cost computacional aumenta ràpidament (de forma casi quadràtica) en l'increment d'esta finestra. Lo habitual és elegir una finestra de superfície llaugerament superior al màxim tamany possible dels objectes mòvils.

• Un camp d'exploració chicotet supondrà que els vectores de desplaçament trobats seran també reduïts, la qual cosa resulta adequat si es treballa en seqüències de moviment llent, ademés de reduir la computació necessària.

• El número de píxels que separa als diferents blocs candidats que es volen analisar dins de la finestra es correspon en la llongitut del pas de busca. Si eixa llongitut és igual a un píxel, significa que estem realisant una busca exhaustiva o Full Search. Si de lo contrari optem per un pas major, incrementem la velocitat del procés en reduir el número de candidats, pero incrementem l'error d'estimació del vector.

Elecció de bloc

Especifica la posició, el tamany, l'ubicació de l'inici de busca i l'escala dels blocs en els que actuarà l'algoritme.

• Elegir el tamany correcte dels blocs no és trivial. Generalment, els blocs majors són menys sensibles al soroll, mentres que un bloc de dimensions reduïdes presenta uns contorns més be definits. El principal factor a l'hora de triar les dimensions és el tamany dels objectes a rastrejar. Atres factors a tindre en conte són la cantitat de soroll que presenta la seqüència i la textura tant dels objectes com del fondo.

• També apareix el denominat problema d'obertura quan es treballa en objectes de color uniforme. Els blocs en l'interior de dits objectes no semblen estar movent-se perque tots els que li rodegen són del mateix color. Un tamany de bloc superior pot ser triat per a paliar este problema.

• La majoria dels algoritmes de block matching utilisen l'orige de la finestra d'exploració com el centre inicial de busca i no exploten la correlació entre els blocs pertanyents a un mateix objecte de l'image en moviment. Per a millorar la precisió es podria fer us de dita correlació en la finalitat de predir una posició inicial que reflectira la tendència de moviment del bloc, permetent aixina trobar el seu vector de moviment òptim de forma més eficient.

• En gran part dels métodos de busca recents, la direcció dels vectores de moviment dels blocs elegits determinen l'ubicació del punt d'inici de la següent busca.

Vore també

• Compensació de moviment
• Efecte bloc
• Codificador de video