Brevet FR2663178A1 — publié le 19911213

i Procédé d'estimation hiérarchique du mouvement dans une séquence d'images La présente invention concerne une procédé d'estimation hiérarchique du mouvement dans une séquence d'images basée sur la décomposition du spectre des images en sous bandes. Les algorithmes classiques d'estimation de mouvement travaillant directement sur les images et basés sur des techniques de corrélation ou de gradient ne donnent pas de résultats satisfaisants dans le cas de grands mouvements ainsi que dans les zones uniformes des images Par ailleurs, le mouvement des détails fins des images est généralement très mal rendu. Le but de l'invention est de pallier les inconvénients précités. A cet effet, l'invention a pour objet, un procédé d'estimation hiérarchique du mouvement dans une séquence d'images caractérisé en ce qu'il consiste à effectuer une décomposition hiérarchique de l'image par niveaux de résolutions, à estimer un mouvement global au niveau de résolution le plus grossier et à affiner l'estimation dans chaque niveau au fur et à mesure que la résolution augmente. L'invention a pour principal avantage qu'elle permet de calculer un champ de vecteurs déplacement entre deux images successives d'une séquence Ce champ peut être défini pour chaque pixel de l'image, avec une précision de déplacement inférieure à 1 pixel De plus avec l'apport de deux pyramides d'images hautes fréquences à résolutions croissantes il permet de restituer le mouvement de détails fins de l'image, qui disparaîtrait dans une simple estimation monopyramidale basse fréquence. Le procédé selon l'invention a également pour avantage de pouvoir être utilisé dans tous les dispositifs de traitement d'images nécessitant un champ de mouvement proche du champ réel tels que les dispositifs de codage par compensation de mouvement dans le cadre par exemple des applications de télévision haute définition, ou encore les dispositifs de conversion de standard 50 HZ/60 HZ, de désentrelacement de trames ou de conversion 50 HZ/100 HZ. D'autres caractéristiques et avantages de l'invention apparaîtront ci-après à l'aide de la description qui suit faite en regard des dessins annexés qui représentent. la figure 1, une pyramide multi résolution; la figure 2, une décomposition d'image en sous bandes; la figure 3, un mode de réalisation d'une cellule élémentaire de décomposition d'une image en sous bandes; la figure 4, un mode de réalisation d'une cellule élémentaire de reconstitution d'image à partir de ses sous bandes. la figure 5, une découpe du spectre de l'image suivant trois itérations successives. la figure 6, un arbre de décomposition d'image obtenu à partir d'une cascade de trois cellules élémentaires. la figure 7, une structure tripyramidale obtenue pour quatre niveaux de résolution. la figure 8, un vecteur mouvement représenté entre deux images successives. les figures 9 et 10, deux exemples de projection de vecteurs déplacement d'une image de résolution grossière vers une image de résolution plus fine. la figure 11, une illustration des choix possibles entre vecteurs déplacement proposés. la figure 12, un exemple de fusion d'estimations obtenus sur les pyramides haute fréquence pour le calcul de l'estimation sur la pyramide basse fréquence. la figure 13, une illustration de l'algorithme de traitement mis en oeuvre par le procédé selon l'invention. la figure 14, une courbe d'interpolation permettant d'estimer les champs de mouvement avec une précision inférieure au pixel. Selon l'invention l'analyse du mouvement dans une séquence d'images a lieu de façon hiérarchique Elle consiste à estimer d'abord un mouvement global à un niveau de résolution grossier de l'image, puis à affiner cette estimation au fur et à mesure que la résolution des images traitées augmente. La figure 1 décrit une pyrapide multirésolution d'images, composée d'un ensemble d'images de résolution 2-J o jappartient à l'intervalle jo,j J, l'image pleine résolution correspondant à j=o Ainsi, l'estimation faite à un niveau de résolution 2-i sert d'initialisation à l'estimation faite au niveau de résolution supérieur 2 (j 1) L'invention utilise 3 telles pyramides multirésolution, une pyramide d'images basses fréquences et 2 pyramides d'images hautes fréquences Ces trois pyramides sont obtenues naturellement en utilisant une décomposition hiérarchique en sous-bandes des images. Un mode de découpe du spectre d'une image est représenté à la figure 2, suivant quatre bandes de fréquence Il' I 2, I 3 et I 4 J représentés dans un repère orthonormé à deux dimensions, comportant deux axes W x et W y sur lesquels sont portés respectivement les fréquences spatiales W x et U) y mesurées respectivement en cycles par largeur d'image et hauteur d'image. La bande I 1 correspond au domaine des basses fréquences et les trois autres bandes I 22 I 3 et I 4 correspondent à celui des hautes fréquences Un tel découpage peut par exemple être obtenu au moyen d'une cellule de découpe organisée de la manière représentée à la figure 3 Cette cellule comporte un premier ensemble de filtres (H 1) passe haut monodimensionnels référencés ( 11, 12 et 13) couplés à des circuits déciminateur par deux ( 21, 22 et 23) et un deuxième ensemble de filtres (Ho) passe bas monodimensionnels ( 31 32 et 33) couplés à des circuits décimateur par deux ( 41, 42 et 43) Les filtres 11 et 32 opèrent respectivement un premier filtrage suivant les colonnes de l'image I appliquée sur leur entrée. Les filtres 12 et 31 opèrent un filtrage suivant les lignes de l'image sur les points déjà filtrés et décimés par deux par le filtre passe haut 11 et le décimateur 21 Les filtres 13 et 33 opèrent un filtrage suivant les lignes de l'image sur les points déjà filtrés et décimés par deux par le filtre passe bas 32 et le décimateur 41 Les sorties des filtres 33, 13, 31 et 12 sont à leur tour décimés par deux pour former respectivement la décomposition de l'image initiale I en les quatre sous bandes I 1, I 2, 13 et 14 de la figure 2. La reconstruction de l'image I à partir des images partielles Il' I 2, I 3 et I, peut être obtenue de la manière représentée à la figure 4 au moyen de filtres (G 1) 51 à 53 et de filtres (Go) 54, 56 et 57 de fonction de transfert défini dans le plan complexe de la variable complexe Z par les relations: GO (Z) = 2 H 1 (-Z) /D (Z) ( 1) G 1 (Z) = -2 Ho (-Z) / D (Z) ( 2) o D (Z) = H (Z) H 1 (-Z) Ho (-Z) H 1 (Z) ( 3). Sur la figure 4 les éléments d'image obtenus dans les sous bandes I 1, I 2, I 3 et 14 sont appliqués respectivement aux entrées des filtres 56, 52, 54 et 51 aux travers de suréchantillonneurs par 2 référencés respectivement de 61, 64. Les sorties des filtres 51, 54 d'une part et 52 ' 56 d'autre part, sont couplées respectivement aux circuits additionneurs 71 72 Les sorties des circuits additionneurs 71, 72 sont couplés respectivement aux filtres 55, 57 au travers respectivement de sur échantillonneurs 81, 82. L'image résultante I est obtenue à la sortie d'un circuit additionneur ( 9) couplé respectivement aux sorties des filtres 55, 575 Les filtres Go et G 1 décrits par les formules ( 1) et ( 2) permettent une reconstruction parfaite de l'image originale quelque soit les filtres H et H 1 Néanmoins, il est préférable, pour des raisons de stabilité numérique en arithmétique finie, d'utiliser des filtres à réponse impulsionnelle finie RIF De plus, les filtres à réponse impulsionnelle finie RIE peuvent être construits avec une phase linéaire mieux adaptée au traitement d'images, en particulier lorsque les images filtrées correspondant aux résolutions intermédiaires présentent de l'intérêt Dans ces conditions les filtres de reconstruction doivent avoir des fonctions de transfert définies comme suit Go (Z) = 2 H 1 (-Z) ( 4) et G 1 (Z) = -2 H (-Z) ( 5) les relations ( 4) et ( 5) ont pour avantage de supprimer le repliement interbande. La condition de reconstruction parfaite de l'image L originale s'écrit alors: D (Z) = Z A titre indicatif, il pourra être utilisé pour réaliser les filtres H et H 1 des filtres connus sous les abréviations "t QME"t ou "CQF" de "Quadrature Miror Filter" ou "Conjugate Quadrature Filter" dont des descriptions peuvent être trouvées dans les articles: de M J D Johnston ayant pour titre "Filter family design for use in quadrature miror filter" et publié dans Proceeding ICAST 1980 pages 291294; ou de M K J Smith et TP Barnwell ayant pour titre "Exact reconstruction technics for tree structured subband codors" publié dans la revue IEEE ASSP vol 34 na 3 juin 86; ou encore dans la thèse de M C Galand ayant pour titre "Codage en sous bande, théorie et application à la compression numérique du signal de parole" Nice 1983. L'agencement des cellules élémentaires de décomposition du type de celles décrites aux figures 3 et 4 1 o présente l'avantage qu'il permet des découpages de spectre suivant des formes très variées Une découpe hiérarchique du spectre est utilisée pour l'estimateur de mouvement. Un exemple utilisant trois cellules de découpe est représenté à la figure 5 et l'arbre de décomposition correspondant est montré à la figure 6. Cette décomposition fournit directement trois pyramides d'images hautes fréquences de résolution croissante. Sur la figure 5 les images hautes fréquences s'étendant dans la direction de l'axe horizontal des fréquences X de l'image sont formées par les blocs 3 2 2 2 et 1 2 Les images hautes fréquences s'étendant dans la direction de l'axe vertical des fréquences Y sont formées par les blocs 3 3 2 3 et 1 3 et les images hautes fréquences selon les directions X et Y sont formées par les blocs 3 4 2 4 et 1 4. Chacune met en relief un type donné des détails de l'image en particulier les contours verticaux pour la première, les contours horizontaux pour la seconde. Seules ces deux premières pyramides sont utilisées efficacement pour l'estimation du mouvement la première servant à mettre en évidence le mouvement horizontal des contours verticaux de l'image, la seconde, le mouvement vertical des contours horizontaux de l'image La troisième pyramide n'est pas retenue par le fait que la nature des images qui la composent est généralement trop bruitée. La décomposition des figures 5 et 6 permet également de fournir une pyramide d'images basses fréquences composée des blocs I 31, I 21 > Iil et I s'il est retenu à chaque étage l'image Il de la figure 2 issue du filtrage passe bas des lignes et des colonnes et d'un souséchantillonnage par 2. Une structure tripyramidale correspondante pour quatre niveaux de résolution est représentée à la figure 7. Cette structure montre qu'il y a toujours à chaque niveau de résolution trois images, une image basses fréquences, une image hautes fréquences suivant l'axe horizontal et une image hautes fréquences suivant l'axe vertical. La détermination du champ de mouvement a lieu par un calcul d'estimation hiérarchique sur ces trois pyramides Il s'agit comme le montre la figure 8 pour chaque pixel X = (i,;) d'une image courante 1 (t) de déterminer le pixel Xp= (i'-j') correspondant dans l'image précédente I(t-1) Le vecteur mouvement D (X) est défini par D = (i'-i, j'-j) et est tel que I (t-l, Xp) = I (t, X) Le principe général de l'estimateur de mouvement peut être décrit comme suit: 3 estimations hiérarchiques sont menées en parallèle sur les 3 pyramides Les 2 estimations obtenues sur les pyramides hautes fréquences ne servent qu'à enrichir à chaque niveau de résolution l'estimation obtenue sur la pyramide basse fréquence (qui constitue l'information réellement utile). Ceci se fait par fusion de l'information obtenue sur les 3 pyramides à chaque niveau de résolution, l'estimation résultante étant attribuée à la pyramide basse fréquence. Chaque estimation hiérarchique procède de la manière suivante: Le déplacement calculé, au point correspondant sur l'image au niveau de résolution inférieur sert de prédiction à l'estimation au niveau de résolution supérieur. Si D 2 -(j+ 1) désigne le vecteur calculé sur une image de résolution 2 (j+ 1), et D 2-j désigne le vecteur à calculer sur l'image à la résolution courante 2 J D 2-j est alors donné par: D 2-j = 2 x D 2 -(j+ 1) + d D Cela revient à estimer le vecteur d D, qui représente une petite variation autour de la prédiction la quelle est égale à deux fois le vecteur estimé au niveau de résolution précédent étant donné le facteur de sous échantillonnage. En première approximation, comme montré sur la figure 9, le mouvement d'un point situé au niveau inférieur peut être utilisé comme possible initialisation du mouvement des 4 points au niveau de résolution considéré. Néanmoins, une telle approche n'offre qu'une seule initialisation (ou prédiction) possible pour l'estimation du mouvement en chaque point du niveau considéré. Il paraît plus réaliste de projeter l'estimation obtenue à un niveau inférieur sur 16 points l'entourant au niveau de résolution supérieur Comme le montre la figure 10 on dispose alors de quatre prédicteurs possibles en chaque point de ce niveau au lieu d'un seul, ce qui ne peut qu'améliorer l'estimation Pour le point 10 sur cette figure sa contribution comme prédicteur est apportée à 16 points du niveau de résolution plus fin et le point 1 i de niveau fin utilise comme prédiction 4 points du niveau grossier On autorise à chaque niveau de résolution une correction de _ 1 pixel autour du prédicteur. Comme le montre la figure 11, cela revient à tester 9 vecteurs possibles autour de 4 vecteurs de prédiction D O en limitant l'excursion du vecteur d D à 1 pixel en X et en Y. Cette limitation de l'excursion du vecteur d D à _ 1 pixel fixe l'amplitude maximale du mouvement à estimer. Naturellement en considérant N niveaux de décomposition, à 1 pixel au niveau de résolution k, correspond 2 k-I pixels sur l'image originale (soit le niveau 1) En choisissant le prédicteur nul au niveau le plus grossier k, le mouvement maximal estimé en sortie de la pyramide devient N 1 N-i 2 k = il Dmax// k=O k = O Ceci correspond par exemple à une amplitude maximum de mouvement de 31 pixels pour une décomposition à 5 niveaux. A un niveau de résolution donné, on dispose en chaque point de 4 prédicteurs possibles qui engendrent chacun, comme le montre la figure 11, neuf vecteurs possibles. Le choix du vecteur mouvement au point considéré doit donc être fait parmi 36 vecteurs Le vecteur choisi est celui qui minimise l'erreur de recalage sur une fenêtre de 3 x 3 pixels centrée sur le point considéré. En désignant par It l'image courante, _ It_ 1 l'image précédente et par Dx = (U,V) le vecteur déplacement testé par le point x de coordonnées (i, j) l'erreur de reala e est donnée par la différence inter images déplacées DFD (X,D) -) 2 -D g > -> 2 DFD(X,D)= ( DD(XD)= (I(t-1,j+k-u(X),j+l-V(X) (t,i+k,j+l)) k = -1,1 1 = -1,1 Le vecteur déplacement D choisi est celui qui donne la différence inter image déplacée DFD (X,D) la plus faible. Cependant lorsque l'estimation a lieu dans une zone uniforme de l'image, et donne des valeurs nulles pour les différences inter image déplacées DFD (X,D) quelque soit le vecteur proposé, le critère précédant n'est alors plus pertinent et il y a alors un risque de divergence de l'algorithme. Ceci est résolu en effectuant un test sur la différence existante entre la valeur minimale de l'ensemble des différences inter image déplacées DFD (X,D) et la valeur maximale. Si cette différence est trop faible, il est choisi de conserver toujours le même prédicteur parmi les quatre prédicteurs possibles De telles estimations précédentes ont lieu de façon indépendante sur les deux pyramides hautes fréquences précédemment décrites. Pour l'estimation sur la pyramide basses fréquences, à chaque niveau de résolution le champ de mouvement estimé est enrichi par la fusion des informations de détails provenant des hautes fréquences. Comme les images hautes fréquences sont majoritairement à zéro excepté sur les contours des objets seuls les mouvements estimés sur ces contours sont intéressants pour affiner le mouvement estimé sur la pyramide basses fréquences, et les informations sur les zones bruitées des images hautes fréquences ne sont pas prises en compte Ceci est obtenu en fixant un seuil de pertinence sur les images hautes fréquences, avant de retenir le mouvement calculé correspondant. Ce seuil est fixé en fonction de la variance V de la sous bande considérée Un point d'une sous bande haute fréquence est dans ces conditions pris en compte si la valeur absolue de la luminance est supérieure à KV en ce point. Il est à noter que les sous bandes hautes fréquences sont à moyenne nulle Un exemple de fusion est représenté à la figure 12 Sur cette figure à chaque point Xi de l'image basse fréquence correspond des points Xix et X y sur les images hautes fréquences en X et en Y. Quatre cas de figures sont à considérer dépendant du fait que le seuil peut être atteint dans l'une ou plusieurs des quatre bande d'images. Dans un premier cas, si le seuil n'est pas atteint ni en X ni en Y, cela signifie qu'il n'y a pas d'information sur les hautes fréquences et le mouvement qui est pris en considération est celui estimé sur les basses fréquences. Dans un deuxième cas o le seuil est atteint en Xx et pas en X le choix est effectué entre deux vecteurs y > déplacement possibles, l'un DBF = ( V(x) estimé sur les basses fréquences, l'autre DUF = (U (Xx)' il V(x)) dont la composante en X est estimée sur les hautes fréquences. Dans un troisième cas o le seuil est atteint en Xy et pas en Xx le choix est effectué entre deux vecteurs déplacement, l'un DBF = (U(X) V(X)) estimé sur les basses fréquences, et l'autre: DHF (U (X)' V (Xy)) dont la composante en Y est estimée sur les hautes fréquences. Enfin, suivant un quatrième cas o le seuil est atteint en X et en X le choix est effectué entre X y quatre vecteurs. Un premier: DBF (U (X) V(x) estimé sur les basses fréquences, un deuxième: DHF 1 (U (Xx)' V (X)) dont la composante en X est estimée sur les hautes fréquences, un troisième:DHF 2 = (U (X)' V (Xy)) dont la composante en Y est estimée sur les hautes fréquences, et un quatrième: DHF 3 = (U (Xx) V) dont la composante est estimée sur les hautes fréquences en X et Y. Dans tous les cas le vecteur choisi est celui que minimise l'erreur de recalage sur l'image basses fréquences. Ainsi, l'estimation sur la pyramide basses fréquences prend en compte à chaque niveau les estimations sur les images de détails au même niveau Ce champ fusionné est ensuite utilisé comme montré à la figure 13 comme prédicteur de l'estimation au niveau suivant. Ainsi, à chaque niveau de résolution 2, 3 et 4 représenté sur la figure 13 une estimation dans chaque sous bande est effectué avec en prédiction l'estimation dans la même sous bande ou niveau précédent et une fusion est effectuée des trois estimations reportées dans la sous bande basses fréquences. L'estimation au niveau 1 est effectuée dans l'image originale avec pour prédiction de la fusion des estimations au niveau 2. Naturellement la précision de l'estimation à 1 pixel issue du dernier niveau de résolution du champ de mouvement peut encore être améliorée en interpellant par exemple l'image source avec 2 ou 4 etc ou plus de points en X et en Y pour obtenir des précisions d'estimations de 1/2, 1/4 etc 1/2 K pixels Mais comme cette solution peut devenir rapidement très coûteuse, il paraît préférable d'utiliser une méthode d'interpolation rapide consistant à rechercher le minimum de chaque différence inter image déplacée DFD en fonction d'une des deux variables U et V, l'autre restant constante comme ceci est représenté à la figure 14, o la courbe DFD est tracée à V constant. Le tracé est effectué pour trois valeurs de U (U-1, U et U+ 1) La parabole ainsi obtenue présente un minimum d'abscisse correspondante Dx qui est la composante en X du déplacement La même opération peut être effectuée dans la direction Y de l'image ou obtient ainsi un vecteur déplacement D réel = (Dx, D y) avec une précision inférieure au pixel. Cette méthode est en effet très rapide car le critère DFD (U, V) est calculé pour les 9 vecteurs voisins du vecteur choisi lors du choix Dans le pire des cas, o le vecteur choisi est sur l'un des coins du carré de pixels représenté, il n'y a que deux valeurs de DFD (D) à calculer pour effectuer l'interprétation par la parabole Par contre il n'y a aucune valeur à calculer s'il est au centre et une seule valeur à calculer pour les autres points. REVENDICATIONS 1 Procédé d'estimation hiérarchique du mouvement dans une séquence d'images caractérisé en ce qu'il consiste à effectuer une décomposition hiérarchique de l'image par niveaux de résolutions (I 31, I 32, I 33; 21 ' 122 > 23 Iil, I 12 I 13; I), à estimer un mouvement global au niveau de résolution le plus grossier et à affiner l'estimation (I 31, I 32 > I 33) dans chaque niveau au fur et à mesure que la résolution augmente. 2 Procédé selon la revendication 1 caractérisé en ce qu'il consiste à construire trois pyramides d'images à résolution croissantes, une pyramide d'images basses fréquences (I 31, I 21 ' il,) et deux pyramides d'images hautes fréquences suivant les directions horizontale ( 3 2, 2 2, 1 2) et verticale des images (I 3 4, 2 4 ' l A 4 3 Procédé selon les revendications 1 et 2 caractérisé en ce qu'il consiste à effectuer l'analyse du mouvement à l'aide d'une décomposition hiérarchique en sous bandes de l'image analysée en conservant à chaque niveau de la décomposition la bande basse fréquence (Il) et les bandes hautes fréquences (I 2 ' 3) représentant respectivement les contours verticaux et horizontaux de l'image. 4 Procédé selon la revendication 3 caractérisé en ce qu'il consiste à estimer le mouvement de chaque point de l'image courante en effectuant une mise en correspondance d'un bloc de points Nx N, centré autour du point courant, avec des points homologues dans l'image précédente la recherche du déplacement au niveau courant de résolution s'effectuant autour du déplacement calculé au niveau précédent. * 14 Procédé selon les revendications 3 et 4 caractérisé en ce que l'estimation point à point du mouvement est réalisée de façon hiérarchique sur chacune des trois pyramides. 6 Procédé selon l'une quelconque des revendications 4 à 6 caractérisé en ce qu'il consiste à utiliser pour chaque estimation quatre vecteurs de prédiction (Do) et à retenir pour vecteur déplacement la prédiction qui donne la différence interimage déplacée (DFD) la plus faible. 7 Procédé selon la revendication 6 caractérisé en ce qu'il consiste pour commencer une estimation à un niveau de résolution déterminé, à utiliser quatre vecteurs de prédiction (Do) du niveau de réseau résolution inférieur et à rechercher au voisinage de chacun des quatre vecteurs, le vecteur déplacement (Do) qui donne la différence inter image déplacée (DFD) la plus faible. 8 Procédé selon l'une quelconque des revendications 2 à 5 caractérisé en ce qu'il consiste à effectuer l'estimation de mouvement de façon indépendante sur chaque pyramide d'images hautes fréquences et à enrichir chaque niveau de résolution par les informations de mouvement obtenues sur les hautes fréquences de l'image. 9 Procédé selon la revendication 6 caractérisé en ce qu'il consiste à conserver toujours le même vecteur de prédiction dans les zones uniformes de l'image. 10 Procédé selon l'une quelconque des revendications 6 à 8 caractérisé en ce qu'il consiste à effectuer une estimation parabolique du vecteur déplacement pour obtenir une précision à mieux que -I prixel.