Estimation de mouvement
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Consultez la liste des tâches à accomplir en page de discussion.
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 problème mal posé 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ée 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.
Domaines d'application
modifierEn 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
modifierLes 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
modifierFlux optique
modifierLa technique qui se rapproche le plus de l'estimation de mouvement se nomme le flux optique, 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
modifierL'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 matérielles. 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
modifier- 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
modifierPour é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
modifierLes 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.
Notes et références
modifier- (en) P.H.S. Torr and A. Zisserman, « Feature Based Methods for Structure and Motion Estimation » [PDF], sur ox.ac.uk (consulté le )
- (en) M. Irani and P. Anandan, « All About Direct Methods » [PDF], sur wisc.edu (consulté le )
- (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
modifierSources
modifier- (en) E. G. Richardson, H.264 and MPEG-4 Video Compression: Video Coding for Next-generation Multimedia, Chichester, John Wiley & Sons Ltd., (ISBN 0-470-84837-5)
