Algorithme de block-matching

Un algorithme de block-matching ((en) Block Matching Algorithm) est une méthode utilisée pour encoder le mouvement dans une séquence vidéo en localisant des blocs similaires entre deux images. En compression vidéo, plusieurs normes vidéo telles que H.264 et MPEG-2 utilisent un algorithme de block-matching dans la partie estimation de mouvement de l'encodage d'une inter-trame.

Dans un encodage vidéo, l'objectif de l'algorithme est de trouver un bloc similaire (bloc cible) au bloc à encoder à partir d'une ou plusieurs images de référence qui peuvent apparaître future ou passée par rapport l'image courante. Il peut être utilisé pour découvrir des redondances temporelles dans une séquence vidéo tel qu'un objet sans mouvement dans une vidéo, ce qui accroît l'efficacité de compression d'une image et celle de la conversion des normes de télévision.

Cet algorithme est utilisé dans différents domaines comme la compression, la stéréoscopie, le suivi d’objets et la stabilisation. Il s’attaque aux problèmes d’estimation des mouvements au niveau local.

Critères d'évaluation métrique

Pour définir le meilleur bloc cible, l'algorithme se base sur des critères d'évaluation métrique qui mesurent la différence de contenu entre les deux blocs et les compare avec tous les autres blocs cibles potentiels. Voici des exemples de critères:

• Erreur quadratique moyenne ou MSE pour Mean square error.
• Somme des différences absolues ou SAD pour Sum of Absolute Differences
• Différence absolue moyenne ou MAD pour Mean Absolute Difference
• Somme des carrés des résidus ou SSE pour Sum of Squared Errors
• Somme des différences absolues transformées ou SATD pour Sum of Absolute Transformed Differences

Les algorithmes de block-matching

Pour trouver un bloc cible dans une image de référence, l'algorithme parcourt l'image bloc par bloc dans un certain ordre. De nombreuses manières existent et chacune possède généralement un ordre de parcours différent. Par exemple, le Cross Search Algorithm commence par le bloc de l'image de référence qui se situe à la même position que celui de l'image courante et identifie le meilleur des quatre points voisins (qui correspondent au point d'une croix en X) à l'aide du critère prédéfini puis il se place sur ce point et recommence la recherche sur ses quatre points voisins avec un plus grand degré de précision. A partir de ce nouveau point, il recommence la recherche afin d'augmenter la précision du vecteur. Le bloc cible correspond au bloc pointé par le vecteur de mouvement ayant les même dimensions que le bloc d'origine. En général, la précision du vecteur est définie jusqu'au quart de pixel^[1].

Voici une liste des algorithmes d'estimation de mouvement utilisés dans les normes de codage vidéo.

• Cross Search Algorithm (CSA)
• Full Search Algorithm (FSA)
• Spiral Search
• Three Step Search
• Two Dimensional Logarithmic Search (TDL)
• Binary Search (BS)
• Four Step Search (FSS)
• Orthogonal Search Algorithm (OSA)
• Hierarchical Search Algorithm (HSA)
• Diamond Search (DS)

Références

• (en) E. G. Richardson, H.264 and MPEG-4 Video Compression: Video Coding for Next-generation Multimedia, Chichester, John Wiley & Sons Ltd., septembre 2003 (ISBN 0-470-84837-5) 
• ThomasWiegand, Gary J. Sullivan, « “Overview of the H.264/AVC Video Coding Standard » sur http://ip.hhi.de, IEEE, 2003. Consulté le 19 janvier 2011

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Block-matching algorithm » (voir la liste des auteurs)

Annexes

Articles connexes

• H.264
• Inter-trame

Liens externes

• (en) tutoriels H.264

• Portail des télécommunications
• Portail de l’imagerie numérique