Brevet FR2940492A1 — publié le 20100625

Procédé d'estimation de mouvement multi-résolutions L'invention concerne un procédé d'estimation de mouvement mufti-5 résolutions. Elle s'applique notamment aux domaines de l'analyse, du codage et du transcodage de vidéos. Une séquence vidéo comporte de par sa nature même une importante redondance statistique tant dans le domaine temporel que spatial. Cette 10 redondance peut être utilisée d'une part pour compresser ladite séquence et d'autre part dans le but d'analyser et de caractériser son contenu en identifiant, par exemple, les zones en mouvement des images de ladite séquence. Ainsi, les algorithmes d'estimation de mouvement recherchent dans des images de référence le bloc ou la zone qui correspond le mieux à 15 un bloc ou une zone donnée de l'image en cours de traitement, ladite image étant appelée image courante dans la suite de la description. Un vecteur estimation de mouvement est obtenu, ledit vecteur correspondant au déplacement du bloc ou de la zone entre deux images. De nombreuses applications nécessitent aujourd'hui la mise en oeuvre 20 d'algorithmes permettant d'analyser en temps réel le mouvement physique au sein d'une séquence vidéo. Pour cela, des algorithmes de type � block matching �, habituellement désignés par l'acronyme BMA, peuvent être utilisés. Dans ce cas, l'image courante est découpée en blocs de MxN pixels. L'algorithme BMA recherche ensuite pour un bloc donné de l'image courante 25 un bloc correspondant dans une image de référence. Pour cela, une distance de mesure D est calculée entre le bloc de l'image courante et chaque candidat. Un exemple de mesure D utilisant un Lagrangien est décrit dans l'article de G. Sullivan et T. Wiegand intitulé � Rate-Distortion Optimization for Video Compression �, IEEE Signal Processing Magazine, pp. 74-90, 30 Novembre 1998. L'optimisation par Lagrangien permet d'améliorer l'homogénéité du champ de mouvement obtenu par BMA. La version la plus simple d'algorithme BMA réalise une recherche complète dans une fenêtre donnée de p pixels de largeur, c'est-à-dire que chaque bloc de l'image de référence présent à l'intérieur de ladite fenêtre est 35 un candidat à considérer. Cette technique requiert une importante puissance de calcul. Ainsi, des algorithmes plus rapides ont été proposés, comme par exemple le modèle hiérarchique HME, acronyme venant de l'expression anglo-saxonne � Hierarchical Motion Estimator �, ou le modèle amélioré HDS, acronyme venant de l'expression anglo-saxonne � Hierarchical Diamond Search �. Les algorithmes de type BMA permettent ainsi de générer un champ de mouvement composé de vecteurs de mouvement, un vecteur étant associé à chacun des blocs analysés. Les algorithmes de type DME, acronyme venant de l'expression anglo-saxonne � Dominant Motion Estimator �, ont pour but d'estimer le mouvement relatif de l'arrière plan des images de la séquence vidéo. Celui-ci est du, par exemples, à des mouvements de caméra, aux effets de zoom ou à une prise de vue panoramique. L'algorithme utilise comme entrées des vecteurs de mouvement résultant, par exemple, d'une estimation BMA, et procède ensuite à l'estimation des paramètres d'un modèle de mouvement, un modèle affine à deux dimensions, par exemple. Pour les zones homogènes d'une image ainsi que pour les zones à texture unidirectionnelle, la fiabilité des vecteurs de mouvement estimés par un algorithme de type BMA est habituellement mauvaise. En effet, dans ces zones, ces vecteurs ne correspondent pas forcément à un mouvement réel. Dans le cadre d'une application de segmentation des images de la séquence vidéo à analyser, des résultats incohérents peuvent alors être obtenus. En effet, les zones homogènes suivant le mouvement dominant ne sont alors pas détectées. De plus, si les vecteurs ainsi obtenus sont utilisés par un algorithme de type DME, l'estimation de mouvement global n'utilise comme entrée qu'un nombre réduit de vecteurs de mouvement corrects. En conséquence, la précision des résultats n'est pas bonne. Un but de l'invention est notamment de pallier les inconvénients précités. A cet effet l'invention a pour objet un procédé d'estimation de mouvement d'une séquence vidéo dont les images sont découpées en blocs de pixels, l'estimation de mouvement étant effectuée par l'analyse de N versions d'une même image correspondant à des niveaux de résolution différents, ladite analyse commençant par le niveau de plus faible résolution et se terminant par le niveau de plus haute résolution de l'image courante. Une estimation du champ de mouvement est effectuée pour les différents niveaux de résolution et les paramètres de mouvement dominants sont estimés sur au moins un niveau de basse ou de moyenne résolution, lesdits paramètres étant utilisés comme prédictions pour l'estimation du champ de mouvement d'un niveau de résolution plus élevé. Selon un aspect de l'invention, les paramètres de mouvement dominant estimés pour un niveau donné sont mémorisés afin d'être utilisés comme prédictions lors de l'estimation de champ de mouvement de ou des images suivant l'image courante pour le même niveau de résolution. Les vecteurs du champ de mouvement d'un niveau de résolution donné peuvent être utilisés, par exemple, comme prédictions pour l'estimation du champ de mouvement du niveau de résolution supérieure. Les paramètres de mouvement dominant estimés pour un niveau de résolution donné sont, par exemple, mémorisés afin d'être utilisés pour initialiser l'étape d'estimation des paramètres de mouvement dominant de ou des images suivant l'image courante pour le même niveau de résolution. Dans un mode de réalisation, les paramètres de mouvement dominant vérifient un modèle affine à deux dimensions. Dans un autre mode de réalisation, pour l'estimation des paramètres de mouvement dominant des niveaux de basses et moyennes résolutions, un paramètre de translation est estimé et que pour les niveaux de résolution les plus hauts, 6 paramètres vérifiant un modèle affine à deux dimensions sont déterminés. Pour un bloc de pixels d'un niveau de résolution donné de l'image courante, la meilleure prédiction disponible pour l'estimation des vecteurs du champ de mouvement peut être choisie telle que la distance de mesure D est minimisée, ladite distance s'exprimant par une équation de type D=SAD+XxC dans laquelle : SAD est la somme des différences absolues entre le bloc courant et le bloc de référence ; C est le coût de codage des vecteurs de mouvement, c'est-à-dire la distance mesurée entre le vecteur mouvement et un indicateur de coût ; est une constante réelle.35 Selon un aspect de l'invention, l'indicateur de coût correspond à la médiane des vecteurs de mouvement des blocs voisins. Selon un autre aspect de l'invention, l'indicateur de coût correspond à une prédiction correspondant aux paramètres d'estimation de mouvement 5 dominant. Le choix entre un indicateur de coût correspondant à la médiane des vecteurs de mouvement des blocs voisins et un indicateur de coût correspondant aux paramètres d'estimation de mouvement dominant est choisi par bloc en fonction, par exemple, de la meilleure prédiction de vecteur 10 mouvement. Dans un mode de mise en oeuvre, l'algorithme réalisant l'estimation de mouvement dominant à un niveau de résolution donné est initialisé par les paramètres de mouvement dominant estimés pour l'image courante à un niveau de plus basse résolution. 15 Un taux de confiance de l'estimation de mouvement effectuée sur l'image courante est déterminée, par exemple, en calculant le taux de vecteur suivant le mouvement dominant au niveau de plus haute résolution D'autres caractéristiques et avantages de l'invention apparaîtront à 20 l'aide de la description qui suit donnée à titre illustratif et non limitatif, faite en regard des dessins annexés parmi lesquels : - la figure 1 illustre le principe de l'estimation de mouvement multi-résolutions ; 25 - la figure 2 donne un exemple de diagramme mettant en oeuvre le procédé selon l'invention ; - la figure 3 présente une manière de réaliser l'estimation de mouvement dominant dans le cadre de l'invention. 30 La figure 1 illustre le principe de l'estimation de mouvement multirésolutions. Les algorithmes de type BMA tels que décrits précédemment impliquent une complexité calculatoire importante. De manière à réaliser une estimation de mouvement sur une séquence vidéo, il est alors conseillé d'utiliser intelligemment ce type d'algorithme. Le contenu des séquences vidéo est pris en compte par les techniques de prédiction de mouvement. En effet, les champs de mouvement présentent habituellement des propriétés de continuité spatiale et temporelle. Ainsi, il est possible de prédire le mouvement d'un bloc donné à partir du mouvement de ses blocs voisins et des images précédentes. Un ensemble de prédictions est alors disponible. Dans la suite de la description, une prédiction correspond à un vecteur candidat représentant le mouvement d'un bloc entre deux images et devant être testé afin de vérifier qu'il correspond bien au mouvement réel dudit bloc. Chaque prédiction est évaluée en calculant, par exemple, une distance de mesure D. A titre d'exemple, cette distance de mesure pourra être la somme des différences absolues, désignée par l'acronyme SAD venant de l'expression anglo-saxonne � Sum of Absolute Differences �. Ce SAD représente la distorsion entre le bloc courant et le bloc de référence. Le coût de codage C des vecteurs de mouvement peut être pris en compte grâce à l'introduction d'un coefficient de Lagrange afin de minimiser les distorsions introduites par l'estimation. La distance D peut être décrite par l'expression suivante : D=SAD+XxC (1) 20 Une recherche du meilleur vecteur de mouvement est alors effectuée au voisinage de la meilleure prédiction en utilisant, par exemple, un schéma de recherche locale. Un exemple d'algorithme permettant de réaliser ce type de recherche est décrit dans l'article d'Alexis Michael Tourapis intitulé 25 � Enhanced Predictive Zonal Search for Single and Multiple Frame Motion Estimation �, proceedings of Visual Communications and Image Processing, pages 1069-1079, 2002. De nombreux autres algorithmes de type BMA existent et se distinguent de par la manière dont est déterminé l'ensemble des prédictions pour un bloc ainsi que par le schéma de recherche locale 30 choisi. Une manière permettant de réduire la complexité de calcul est d'utiliser une approche multi-résolution. L'algorithme HME, acronyme venant de l'expression anglo-saxonne � Hierarchical Motion Estimator �, en est un exemple. De l'image courante est déduite une pyramide d'images. Cette 35 pyramide d'images est composée de plusieurs images déduites de l'image courante, chacune desdites images représentant un niveau de recherche. Le niveau 0 correspond à l'image courante à pleine résolution. Un niveau de basse ou de moyenne résolution est un niveau différent du niveau 0, ce dernier correspondant au niveau de plus haute résolution de la pyramide d'images. Le niveau n+1 correspond à l'image obtenue par filtrage passe-bas et sous échantillonnage de l'image de niveau n. L'image de niveau n+1 a donc une résolution plus faible que l'image de niveau n. Dans un premier temps, un champ de mouvement est estimé sur le niveau le plus haut, c'est-à-dire sur l'image de plus basse résolution. Ensuite, ledit champ de mouvement est amélioré en utilisant les vecteurs du champ de mouvement obtenu au niveau supérieur en tant que prédiction, et ce en descendant les niveaux de la pyramide d'image jusqu'à atteindre le niveau 0. Pour un bloc donné, les vecteurs de mouvements des blocs voisins qui ont déjà été calculés sont également utilisés comme prédictions. L'estimation est ensuite affinée en recherchant le meilleur vecteur mouvement autour de la meilleure prédiction. L'exemple de la figure 1 illustre le principe de l'estimation de mouvement multi-résolution. Trois niveaux sont considérés. Le niveau 0 correspond à l'image à analyser et dont la résolution n'est pas réduite. Les niveaux 1 et 2 correspondent à l'image à analyser après altération de la résolution, la résolution du niveau 2 étant moins bonne que pour le niveau 1. Le processus d'estimation commence au niveau le plus élevé, c'est-à-dire au niveau 2 pour l'exemple de la figure 1. L'image est analysée bloc par bloc. Pour un bloc donné 100, une ou plusieurs prédictions sont disponibles. En effet, il est possible d'avoir plusieurs prédictions pour chaque bloc à analyser, et ce en tenant compte, par exemple, du mouvement des blocs voisins ou bien des images précédentes, mais aussi du résultat de l'estimation de mouvement au niveau supérieur. Pour chaque prédiction, un affinement peut être effectué de manière à trouver le meilleur candidat possible 101 correspondant le mieux au mouvement réel du bloc analysé. Une prédiction 102 pour le bloc en cours d'analyse 106 au niveau 1 peut être le résultat de l'estimation de mouvement réalisée pour le même bloc mais au niveau supérieur 101. L'affinement de la recherche mène ensuite à une estimation plus fine 103. Le même principe est ensuite reproduit au niveau 0, avec une des prédictions 104 correspondant au résultat de l'estimation au niveau supérieur et un affinement permettant d'obtenir le résultat final 105. Le choix de la meilleure prédiction et du vecteur final résultant de l'affinement mentionné précédemment est réalisé, par exemple, en calculant et en comparant la distance D pour chaque vecteur candidat. Le résultat de ces calculs par niveau est un champ de mouvement composé d'un ensemble de vecteurs, un vecteur dudit champ étant associé à un bloc de l'image courante. Même si l'approche multi-résolution de type HME permet de réduire la complexité, celle-ci reste importante. Pour accélérer encore les calculs, il est possible, afin d'améliorer la recherche locale autour d'une prédiction, de mettre en oeuvre un algorithme appelé HDS, acronyme venant de l'expression anglo-saxonne � Hierarchical Diamond Search �. Cet algorithme réalise une estimation de mouvement multi-résolution tout en utilisant une étape d'affinement basée sur une recherche récursive en diamant. La meilleure prédiction est affinée par recherche locale en utilisant un petit motif de plusieurs blocs en forme de diamant ou de carré. La figure 2 donne un exemple de mise en oeuvre du procédé selon l'invention. Les images de la séquence vidéo à analyser sont traitées les unes après les autres. Une mémoire d'image 200 contient la pyramide d'images multi-résolution associée à l'image courante ainsi que la ou les images de référence à utiliser pour l'estimation de mouvement. La pyramide de l'image courante 201 ainsi que la ou les pyramides d'images de référence 202 sont utilisées pour effectuer les différentes estimations décrites ci-après. Dans cet exemple, une approche multi-résolution à 5 niveaux, indexés de 0 à 4, est utilisée. Une estimation BMA du champ de mouvement est effectuée pour les images basse résolution en commençant par le niveau 4 203, pour ensuite traiter le niveau 3 204, le niveau 2 205, le niveau 1 206 et le niveau 0 208. Les vecteurs du champ de mouvement résultant de l'estimation sur le 35 niveau 1 sont utilisés comme prédiction afin d'estimer les paramètres de mouvement dominant 207. En d'autres termes, l'estimation de mouvement dominant est d'abord calculée pour un champ de mouvement basse résolution, soit au niveau 1. L'estimation de mouvement dominant peut être réalisée, par exemple, suivant un modèle affine à deux dimensions. Dans ce cas, cette estimation revient à estimer pour chaque bloc de l'image à analyser les paramètres de mouvement dominant ao, a1, a2 et bo, b1, b2 vérifiant l'équation : vx a ~a a \ ' x \ _ 0 + 1 2 wyi aboi ~b~ b2ii 10 dans laquelle vX et vy sont les coordonnées d'un vecteur V du champ de mouvement et X et Y sont les coordonnées permettant de localiser le bloc en cours de traitement pour lequel est réalisé l'estimation de mouvement dominant. 15 Les paramètres de mouvement dominant sont ensuite utilisés pour ajouter une nouvelle prédiction lors de l'estimation du champ de mouvement pour le prochain niveau de résolution. Cette prédiction est évaluée de la même manière que les autres prédictions disponibles pour chaque bloc en calculant, par exemple, la distance de mesure D précédemment explicitée à 20 l'aide de l'expression (1). La fiabilité de l'estimation de champ de mouvement s'en trouve ainsi améliorée. Le terme C de l'expression (1) représente le coût de codage du vecteur de mouvement, c'est-à-dire la distance mesurée entre le vecteur de mouvement et un indicateur de coût. La médiane des vecteurs de mouvements des blocs voisins est habituellement choisie comme 25 indicateur de coût. La prise en compte du coût de codage permet d'obtenir un champ de mouvement plus homogène. Dans le cadre de l'invention, il est possible d'utiliser deux indicateurs de coût différents, ledit indicateur étant choisi en fonction de la meilleure prédiction de vecteur mouvement : soit la prédiction venant de l'estimation de 30 mouvement dominant soit la médiane précédemment décrite. Les zones suivant le mouvement dominant sont alors identifiées directement, même dans le cas de zones homogènes. (2) A titre d'illustration, le ciel est habituellement une zone homogène. En utilisant un algorithme d'estimation de mouvement appartenant à l'état de l'art, un mouvement nul est en général associé à cette zone, même en présence de mouvements de caméra. En utilisant l'estimation de mouvement dominant, le mouvement de caméra est identifié et la zone de ciel est contrainte de suivre ce mouvement dominant, ce qui correspond le mieux au mouvement réel. L'estimation de champ de mouvement suivi du calcul des paramètres de mouvement dominant à chaque niveau mène à une approche récursive 10 avec une complexité de calcul raisonnable. Les paramètres de mouvement dominant du niveau 1 sont stockés en mémoire 211 pour être utilisé pour l'analyse de la prochaine image en tant que prédiction 214 pour l'estimation 206 du champ de mouvement de niveau 1. L'utilisation du mouvement dominant est rejetée 213 pour l'image entière 15 si les paramètres ne sont pas fiables au sens d'un critère de fiabilité estimé avec lesdits paramètres. Les paramètres de mouvement dominant estimés 207 au niveau 1 sont utilisés d'autre part comme prédiction pour l'estimation 208 du champ de mouvement de niveau 0. Le meilleur jeu de paramètres du mouvement 20 dominant est choisi pour toute l'image 212, c'est-à-dire le résultat de l'estimation de mouvement dominant réalisée au niveau supérieur 207, les paramètres de mouvement dominant mémorisés 210 ou aucun paramètre. Le champ de mouvement de niveau 1 est également utilisé en tant que prédiction pour l'estimation de champ de mouvement de niveau 0. Une 25 estimation 209 des paramètres de mouvement global est également effectuée suite à l'estimation du champ de mouvement de niveau 0. Pour cela, les prédictions utilisées en entrées sont d'une part le champ de vecteur de niveau 0, d'autre part les paramètres de mouvement global estimés 215 se basant le champ de mouvement de niveau 1, et enfin les paramètres de 30 mouvement global de niveau 0 estimés lors de l'analyse de l'image précédente et stockés en mémoire 214. Plusieurs résultats 217 sont disponibles suite à l'analyse d'une image appartenant à une séquence vidéo. Il peut être décidé d'avoir comme sortie le champ de mouvement CM résultant de l'estimation de champ effectuée 35 sur l'image haute résolution. D'autre part, le taux de confiance TC, ainsi que les paramètres de mouvement dominant MD estimés au niveau 0 peuvent être présentés en sortie et utilisés pour des traitements postérieurs. Le taux de confiance TC peut être défini, par exemple, comme le taux de vecteurs suivant le mouvement dominant au niveau 0. La figure 3 présente une manière de réaliser l'estimation de mouvement dominant dans le cadre de l'invention. Les paramètres de mouvement dominant sont estimés en utilisant un algorithme de type moindre carré pondéré récursif. Le modèle d'estimation de mouvement dominant peut être adapté en fonction du niveau de résolution. Ainsi, pour les résolutions moyennes et basses, seul un paramètre de translation peut être estimé, alors que pour les résolutions les plus hautes, un modèle affine à 6 paramètres tels que celui précédemment explicité peut être utilisé. L'algorithme d'estimation des paramètres de mouvement dominant a pour but d'estimer les valeurs desdits paramètres par l'utilisation de l'algorithme aux moindres carrés pondérés. Trois types de paramètres initiaux peuvent être utilisés pour initialiser l'algorithme. Ces trois types d'initialisation sont appelés initialisation temporelle, initialisation hiérarchique et initialisation simple. L'entrée principale de l'algorithme d'estimation de mouvement dominant est un champ de mouvement CM. Les paramètres utilisés pour l'initialisation temporelle, notés initialisation 1, sont les paramètres de mouvement dominant 214, 216 calculés pour une image précédemment traitée et stockés 210, 211 en mémoire. Les paramètres utilisés pour l'initialisation hiérarchique, notés initialisation 2, sont les paramètres de mouvement dominant calculés pour l'image courante à un niveau de résolution inférieur 215. Si aucune des initialisations 1 et 2 n'est fiable, une initialisation est calculée à partir de tous les vecteurs du champ de vecteur CM grâce à un algorithme des moindres carrés simple non pondérés 302. Si les paramètres d'initialisation temporelle sont disponibles, une évaluation 300 en est faite. Il est ensuite vérifié 303 que le résultat 307 est fiable, au sens qu'il ne comprend pas un nombre d� REVENDICATIONS1- Procédé d'estimation de mouvement d'une séquence vidéo dont les images sont découpées en blocs de pixels, l'estimation de mouvement étant effectuée par l'analyse de N versions d'une même image correspondant à des niveaux de résolution différents, ladite analyse commençant par le niveau de plus faible résolution et se terminant par le niveau de plus haute résolution de l'image courante, ledit procédé étant caractérisé en ce qu'une estimation d'un champ de mouvement (203, 204, 205, 206, 208) est effectuée pour les différents niveaux de résolution et que les paramètres de mouvement dominants sont estimés (207) sur au moins un niveau de basse ou de moyenne résolution, lesdits paramètres étant utilisés comme prédictions pour l'estimation du champ de mouvement d'un niveau de résolution plus élevé. 2- Procédé selon l'une quelconque des revendications précédentes caractérisé en ce que les paramètres de mouvement dominant estimés pour un niveau donné sont mémorisés (211) afin d'être utilisés comme prédictions (214) lors de l'estimation de champ de mouvement de ou des images suivant l'image courante pour le même niveau de résolution. 3- Procédé selon l'une quelconque des revendications précédentes caractérisé en ce que les vecteurs du champ de mouvement d'un niveau de résolution donné sont utilisés comme prédictions pour l'estimation du champ de mouvement du niveau de résolution supérieure. 4- Procédé selon l'une quelconque des revendications précédentes caractérisé en ce que les paramètres de mouvement dominant estimés pour un niveau de résolution donné sont mémorisés (210, 211) afin d'être utilisés pour initialiser (214, 216) l'étape d'estimationdes paramètres de mouvement dominant de ou des images suivant l'image courante pour le même niveau de résolution. 5- Procédé selon l'une quelconque des revendications précédentes caractérisé en ce que les paramètres de mouvement dominant vérifient un modèle affine à deux dimensions. 6- Procédé selon l'une quelconque des revendications 1 à 4 caractérisé en ce que pour l'estimation des paramètres de mouvement dominant des niveaux de basses et moyennes résolutions, un paramètre de translation est estimé et que pour les niveaux de résolution les plus hauts, 6 paramètres vérifiant un modèle affine à deux dimensions sont déterminés. 7- Procédé selon l'une quelconque des revendications précédentes caractérisé en ce que pour un bloc de pixels d'un niveau de résolution donné de l'image courante, la meilleure prédiction disponible pour l'estimation des vecteurs du champ de mouvement est choisie telle que la distance de mesure D est minimisée, ladite distance s'exprimant par une équation de type D =SAD + X x C dans laquelle : SAD est la somme des différences absolues entre le bloc courant et le bloc de référence ; C est le coût de codage des vecteurs de mouvement, c'est-à-dire la distance mesurée entre le vecteur mouvement et un indicateur de coût ; est une constante réelle. 8- Procédé de selon la revendication 7 caractérisé en ce que l'indicateur de coût correspond à la médiane des vecteurs de mouvement des blocs voisins. 9- Procédé selon l'une quelconque des revendications 7 ou 8 caractérisé en ce que l'indicateur de coût correspond à une prédiction correspondant aux paramètres d'estimation de mouvement dominant. 10- Procédé selon les revendications 8 et 9 caractérisé en ce que le choix entre un indicateur de coût correspondant à la médiane des vecteurs de mouvement des blocs voisins et un indicateur de coût correspondant aux paramètres d'estimation de mouvement dominant est choisi par bloc en fonction de la meilleure prédiction de vecteur mouvement. 11- Procédé selon l'une quelconque des revendications précédentes caractérisé en ce que l'algorithme réalisant l'estimation de mouvement dominant à un niveau de résolution donné est initialisé (215) par les paramètres de mouvement dominant estimés pour l'image courante à un niveau de plus basse résolution. 12- Procédé selon l'une quelconque des revendications précédentes caractérisé en ce qu'un taux de confiance (TC) de l'estimation de mouvement effectuée sur l'image courante est déterminée en calculant le taux de vecteur suivant le mouvement dominant au niveau de plus haute résolution.