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:

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. À 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êmes 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

  1. M. GHANBARI, « The Cross-Search Algorithm for Motion Estimation »(Archive.orgWikiwixArchive.isGoogle • Que faire ?), IEEE, (consulté le )

Annexes

Articles connexes

Liens externes

  • Portail des télécommunications
  • Portail de l’imagerie numérique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.