- Estimation de mouvement
-
L'estimation de mouvement ou Motion estimation(en) est un procédé qui consiste à étudier le déplacement des objets dans une séquence vidéo, en cherchant la corrélation entre deux images successives afin de prédire le changement de position du contenu. Le mouvement est un réel problème en vidéo puisqu'il décrit un contexte en trois dimensions alors que les images sont une projection de scènes 3D dans un plan en 2D. En général, il est représenté par un vecteur de mouvement qui décrit une transformation d'une image en deux dimensions vers une autre. Les vecteurs de mouvement lient deux blocs par projection des blocs sur une même image, c'est-à-dire que les coordonnées du vecteur ne sont définies que spatialement sans contraintes temporelles. Les blocs en question sont différents selon l'algorithme : toute l'image peut être lié au vecteur comme c'est le cas pour l'estimation de mouvement global, ou juste des parties spécifiques de l'image, tels que des blocs rectangulaires, des formes arbitraires ou même par pixel. Les vecteurs peuvent être représentés par un modèle traditionnel ou par de nombreux autres modèles qui peuvent se rapprocher du mouvement d'une caméra vidéo réelle, tel que la rotation et la translation dans les trois dimensions sans oublier le zoom. Cette technique de prédiction est surtout utilisée en compression vidéo, en robotique et en traitement d'image. Il existe plusieurs méthodes d'estimation de mouvement, les plus connues étant le Block-Matching et le flot optique.
Sommaire
Domaines d'application
En compression vidéo, l'estimation de mouvement fait partie du processus de prédiction inter qui tente de profiter de la redondance temporelle des images précédemment encodées pour prédire le mouvement et ainsi compresser les données plus efficacement que par prédiction spatiale. Techniquement, l'algorithme recherche dans une image dite de référence un bloc similaire à un bloc de l'image source et enregistre le vecteur de mouvement qui les relie pour l'encoder. L'estimation de mouvement est suivie par la compensation de mouvement qui a pour but d'appliquer les vecteurs de mouvement trouvés à l'image afin de synthétiser la transformation de la prochaine image. En d'autres termes, l'image définie par les blocs ciblés par les vecteurs n'est généralement pas identique à l'image source. Pour pourvoir décoder une image, il est nécessaire d'établir la différence entre les blocs ciblés et les blocs sources et de l'encoder. Elle est présente dans plusieurs normes vidéo dont MPEG-1, MPEG-2 et MPEG-4 ainsi que dans beaucoup de codecs vidéo.
L'estimation de mouvement est également utilisé pour le traitement d'image afin de cibler les objets et définir plus précisément leur contour. Elle est surtout lié aux techniques de segmentation et de filtrage dans une image.
En robotique, ce procédé permet de prédire le déplacement ou la position des objets afin d'améliorer l'interaction du modèle avec l'environnement extérieur.
Les algorithmes existants
Les algorithmes de recherche pour trouver des vecteurs de mouvement peuvent être définies en deux catégories : les méthodes basées sur le pixel dite directe et celles basées sur le contenu dite indirecte[1],[2].
Méthodes directes
Flot optique
La technique qui se rapproche le plus de l'estimation de mouvement se nomme le flot optique (en), dont les vecteurs correspondent au mouvement perçu au niveau des pixels. En estimation de mouvement, la correspondance exacte de la position des pixels dans chaque image n'est pas une nécessité.
Le Block-matching
L'algorithme de Block-Matching est une méthode de corrélation cherchant le bloc le plus ressemblant dans l’image de référence au bloc courant. L'image courante est divisée en blocs non chevauchés de tailles identiques qui sont vus comme des blocs indépendants où les pixels composant chaque bloc ont la même allure de mouvement. L'application est généralement limitée dans une fenêtre de recherche qui se dessine autour du bloc courant, pour des raisons de performances hardware. Afin de déterminer le meilleur des blocs similaires, l'algorithme compare la différence entre le bloc source et les autres blocs à l'aide d'un critère de qualité tel que la SAD et le bloc ciblé qui minimise cette règle est retenu.
Autres techniques
- La corrélation de phase et les techniques fréquentielles
- Les algorithmes récursifs au niveau pixel.
- Maximum a posteriori/Réseau de Markov : estimateur de type Bayésien.
Mesures d'évaluation
Pour évaluer le meilleur vecteur de mouvement pour un bloc, plusieurs critères d'évaluation existent pour les méthodes directes:
- 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
Méthodes indirectes
Les méthodes indirectes utilisent le contenu, telles que le détecteur de Harris et cherchent le contenu semblable entre chaque image, souvent avec une fonction statistique appliquée sur une zone globale ou locale. Le but de cette fonction est de supprimer les zones qui ne correspondent pas au mouvement courant. Les fonctions statistiques sont également utilisées dans les méthodes de RANSAC.
Références
- P.H.S. Torr and A. Zisserman, « Feature Based Methods for Structure and Motion Estimation » sur http://www.robots.ox.ac.uk. Consulté le 26 janvier 2011
- M. Irani and P. Anandan, « All About Direct Methods » sur http://pages.cs.wisc.edu. Consulté le 26 janvier 2011
- (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)
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Motion estimation » (voir la liste des auteurs)
Annexes
Articles connexes
Wikimedia Foundation. 2010.
