Brevet FR2648254A2 — publié le 19901214

FR 2648254 A2 19901214 FR 8907673 A 19890609 Procédé et dispositif d'estimation de mouvement dans une séquence d'images anlimées L'invention, objet du présent certificat d'addition, con- cerne un perfectionnement au procédé et aux dispositifs décrits dans la demande de brevet principal n0 88 12468 déposée en France le 23 septembre 1988 au nom de la Demanderesse à la- quelle la présente demande de certificat d'addition est formelle- ment rattachée. Elle s'applique, comme dans la demande de brevet princi- pal, à la réalisation de systèmes de télévision numérique et à la réduction du débit des informations circulant dans ces systè- mes. Dans la demande de brevet principal ci-dessus référencée le procédé décrit consiste, pour estimer le mouvement dans une séquence d'images, à exécuter un algorithme de gradient, du type de celui qui est décrit dans l'article de la publication Bell system technologie vol. 58, pages 631 à 670 de mars 1979 partie I ayant pour titre "Motion compensated television coding" et pour auteur A.N. NETRAVALI et J.D. ROBBINS, initialisé par des valeurs de déplacement estimées dans le plus proche voisinage causal du point courant de l'image. Pour obtenir une convergence plus rapide de l'algorithme, le procédé consiste principalement, à ajouter un paramètre d'inttialisatlon supplémentaire qui est défini, pour chaque point courant d'une trame d'image, par le vecteur déplacement d'un point dans la trame précédente dont la projection dans les directions de ce vecteur déplacement dans la trame courante est la plus proche du point courant. Les risques de fausses estimations qui entrainent des sauts d'image très gênants pour l'oeil se trouvent ainsi limités. Cependant on obtient par cette méthode une convergence de l'algorithme de gradient qui est plus ou moins rapide du fait que la séquence des opérations d'estimation de chaque nouveau déplacement comporte à chaque Itération du calcul, et pour chaque nouvelle valeur de prédiction de dépla- cernent Dpi, des calculs du paramètre de différence inter-image déplacée DFD(Dp), du gradient spatial, d'une fonction de correction incluant des limitations, un calcul d'un nouveau vecteur déplacement D. et un calcul d'une nouvelle valeur J DFD(D]). A cela s'ajoutent une comparaison des valeurs DFD et une sélection du vecteur déplacement Dj à partir d'une part de la valeur absolue la plus faible trouvée du paramètre DFD en comparant cette valeur à un seuil et en fonction d'autre part du nombre d'itérations effectuées. Selon une première variante de réalisation, le mouvement est estimé entre deux trames Ta et Tb à partir des points de la trame Ta et de la trame Tb pour les pixels de l'une des deux trames Taet Tb et le champ de mouvement obtenu est donc attribué à la trame Ta ou à la trame Tb. Selon une deuxième variante de réalisation, le mouvement est estimé entre les trames T et Tb directement pour chaque point de composante de luminance IX et IY d'une trame intermédiaire fictive T.. Dans les deux cas les calculs des J gradients spatiaux du mouvement peuvent être interchangés en tenant compte du fait que dans un premier cas le gradient de la fonction de correction qui est appliqué n'est calculé que dans une image alors que dans le deuxième cas il est calculé dans les deux images. De la sorte plusieurs façons de calculer le gradient spatial peuvent ainsi être envisagées en prenant en compte par exemple des matrices de 8 ou 12 points au voisinage du point courant. Cependant plus le nombre de points pris en compte et le nombre d'itératlons pour effectuer les calculs sont grands plus les temps de calcul sont importants. Pour limiter au maximum les temps de calcul la présente invention propose une amélioration du procédé et des dispositifs décrits dans la demande de brevet principal en ne procédant dans les calculs qu'à une seule itéra- tion et en limitant les calculs de gradients spatiaux à l'examen seulement des luminances des quatre points les plus proches du point extrémité du vecteur déplacement situé dans la trame cou- rante. A cet effet, I'invention a pour objet un procédé d'estima- tion de mouvement dans une séquence d'images animées selon les revendications 1 à 6 et 15 à 22 de la demande de brevet princi- pal caractérisé en ce qu'il consiste, à calculer, en une seule Itération et pour chaque vecteur déplacement estimé DpL une valeur DFD(Dj) de différence inter-images déplacées entre la luminance du point courant et sa valeur de luminance dans la trame précédente décalée de la distance Dp] , à comparer entre elles des valeurs DFD obtenues pour sélectionner le vecteur de déplacement estimé Dpj qui correspond à la valeur DFD(Dpj) la plus faible et à calculer le vecteur déplacement courant Dj par exécution de l'algorithme de gradient à partir du gradient spatial du point extrémité du vecteur déplacement situé dans la trame courante et de la valeur DFD(Dp) correspondante. Selon une autre caractéristique de l'invention le gradient spatial du point courant est calculé en ne prenant en compte que les quatre points les plus proches de chaque point extrémité du vecteur déplacement. L'invention a également pour objet un dispositif pour la mise en oeuvre du procédé précité. Le procédé et le dispositif selon l'invention ont pour principal avantage qu'ils permettent d'améliorer de façon signi- ficative la convergence de l'algorithme de gradient et de facili- ter les traitements en temps réel des images de télévision. D'autres caractéristiques et avantages de l'invention apparaîtront ci-après à l'alde de la description qui est faite en regard des dessins annexés et qui représentent: - la figure 1 un procédé de calcul de nouveaux déplace- ments, sous la forme d'un organigramme, mis en oeuvre par l'invention; la figure 2 une vue pour illustrer le nouveau mode de calcul du gradient du point extrémité du vecteur déplacement dans une trame courante - les figures 3 à 7 des vues pour illustrer deux variantes possibles au traitement des trous en projection temporelle, décrits dans la demande de brevet principal; - la figure 8 un dispositif de filtrage du champ de mouve- ment projeté, avant estimation de mouvement de l'image courante. Comme dans la demande de brevet principal, le procédé d'estimation de mouvement qui fait l'objet de la présente de- mande de certificat d'addition, met en oeuvre un algorithme de gradient qui rend minimal l'écart quadratique des variations locales de luminance de chaque point courant d'une image de télévision entre le point courant et le point qui lui est homolo- gue dans l'image précédente. Dans la demande de brevet principal l'expression de cet algorithme est défini par une relation de la forme delta D = epsilon.DFD(z,D).gradI(z-D, t-T) o epsilon désigne le gain de l'algorithme z désigne les coordonnées spatiales du point courant DFD(z,D) désigne la différence inter-image déplacée, cette différence vérifile, en fonction des luminances I(z,t) et I(z-D,t-T) du point courant aux instants t et t-T une relation de la forme: DFD(z,D) = I(z,t)-I(z-D,t-T) o T désigne la période image ou la période trame. L'utilisation de cet algorithme permet soit d'estimer le mouvement intertrame entre deux trames Taet Tb à partir des points de la trame Ta et de la trame Tb pour les pixels de l'une des deux trames, soit d'estimer le mouvement inter-trame entre deux trames Taet Tb directement pour chaque point d'une trame intermédiaire T1. Les étapes du procédé correspondant à la première va- riante consistent à analyser chaque trame courante point à point en balayant chaque ligne. Le gradient de luminance de chaque point courant de coordonnées z =(X,Y) dans le plan de l'image est alors calculé et savaleur absolue est comparée à une valeur de seuil déterminé de référence S g. Si la valeur du gradient trouvée est Inférieure au seuil S le procédé choisit un g déplacement dans le voisinage causal du point courant P(z,t). Par contre si la valeur du gradient trouvée est supérieure au seuil Sg, le procédé estime quatre nouveaux déplacements à partir de quatre valeurs initiales de déplacement dans le voisi- nage causal du point courant, puis fait le choix d'un déplace- ment parmi les quatre déplacements estimés. Le procédé se dé- roule ainsi par itérations successives, chaque fin d'exécution provoquant l'initialisation du point suivant et l'enregistrement 1 r des déplacements obtenus. Dans la deuxième variante, le procédé est similaire au procédé décrit précédemment, cependant la procédure qui con- siste à comparer le gradient de la luminance du point courant à un seuil et à distinguer deux chemins selon que le gradient est plus grand ou plus petit que ce seuil est supprimée du fait que la luminance de la trame courante T est inconnue. Dans ces J conditions tous les points de la trame fictive T suivent alors la même procédure d'estimation du vecteur mouvement suivant quatre récurrences calculées parallèlement. A la différence des procédures décrites précédemment, le procédé représenté à la figure 1 et qui fait l'objet de la pré- sente demande de certificat d'addition, permet d'effectuer des estimations de mouvement suivant l'une ou l'autre des variantes à l'aide d'une seule itération. Selon une première étape repré- sentée en 100 à la figure 1, une valeur de différence inter-trame déplacée DFD(Dp) est calculée pour chaque vecteur déplacement Dpj estimée. Puis à l'étape 101 une comparaison en:re les valeurs absolues DFD est effectuée pour sélectionner le vecteur déplacement Dpj qui donne lieu à la différence Liter-lmage déplacée minimum. L'estimation du vecteur déplacement courant Dj est alors effectuée par l'exécution des étapes 102 à 107. A l'étape 102 le gradient spatial aux extrémités du vecteur déplacement Dpj est calculé. Ce calcul est effectué en considérant dans chaque trame comme montré à la figure 2 les quatre pixels les plus proches de l'extrémité du vecteur déplacement Dpj contenu dans cette trame. Sur la figure 2, L1, L2, L3 et L4 désignent les luminances de chacun de ces points. La valeur du gradient spatial de composantes (GX, GY) suivant les directions horizontale X et verticale Y de balayage de l'image est donnée en fonction des valeurs L1, L2, L3 et L4 par les relations GX = ((L2-L1)+(L4-L3))/2 et GY = ((L3-L1)+(L4-L2))/2 Cette opération est effectuée pour les trames Ta et Tb. Le gradient Dp] est la moyenne des deux vecteurs gradients. Le calcul du nouveau vecteur déplacement Dj a lieu à l'étape 104 par application de la formule du gradient précédente après avoir évalué à l'étape 103, de la manière décrite dans la demande de brevet principal, les termes de correction à appli- quer. Naturellement, comme cela a été expliqué dans la demande de brevet principal les composantes du vecteur déplacement Dj calculées doivent être limitées et un test est effectué aux étapes 105 et 106 pour vérifier que la valeur Dj obtenue est comprise entre deux valeurs de déplacement prédéterminées -Dmax et +Dmax. Si tel n'est pas le cas, la valeur de Dj qui est retenue est celle du déplacement Dpj sélectionnée à l'étape 101. Cette opération est effectuée pour chaque composante sépa- rément. Il est possible d'effectuer un filtrage spatial du champ de mouvement ainsi obtenu par composante (horizontale et verti- cale). Ceci a l'avantage d'une part de le débruiter, d'autre par de l'homogénéiser et de le préciser dans les zones de l'image à luminance homogène, ou l'information mouvement n'est pas directement mesurable. Ce filtrage peut être effectué avant projection te.nporelle pour la définition du nouveau champ de prédiction. Il peut consister par exemple en un filtrage médian qui a pour effet de débruiter le signal, suivi d'un filtrage moyenneur qui permet de préciser en particulier le mouvement des zones homogènes. Comme dans les procédés décrits dans la demande de bre- vet principal, pour,viter de privilégier un sens de propagation du mouvement dans l'image horizontal ou vertical il est toujours possible soit d'inverser le sens de balayage horizontal d'une ligne sur deux de façon alternée soit encore d'inverser le sens de balayage vertical d'une image sur deux de façon alternée. Mais il est encore possible de faire subir à chaque couple d'image sur lequel est estimé le mouvement une rotation d'un quart de tour de façon à modifier la direction de récursion à chaque image pour que la combinaison de cette rotation et du suivi temporel favorisent l'accélération de la convergence de l'estimateur de mouvement vers le mouvement réel. De même pour combler les trous existants dans le champ de prédiction du mouvement après projection temporelle le procé- dé qui consiste pour le trou courant à considérer les vecteurs s'ils existent des quatre pixels environnants et à définir le vecteur mouvement par la moyenne des composantes des vecteurs existants reste valable. Les trous sont examinés des manières représentées aux figures 3, 4 et 5 en alternant le balayage ligne. Les vecteurs existants sont alors au nombre de quatre au maximum et au nombre de deux au minimum, les pixels situés dans la partie causal ayant déjà été traités. Toutefois deux variantes de réalisation sont encore possibles. Une première peut consister à sélectionner le vecteur qui minimise la valeur absolue de la différence inter-image déplacée DFD pour le pixel trou courant afin de préciser le vecteur associé au trou en reprenant le vecteur indiqué cl-dessus. Une deuxième variante peut aussi consister à sélectionner le vecteur le plus proche de la moyenne des vecteurs. D'autre part, dans le cas de certaines réalisations il peut atussi être envisagé de ne pas prendre en compte le vecteur du pixel précédent si celui-cl correspond à un trou ceci pour des questions de parallélsation du traitement. Il est alors possible de travailler suivant la première variante ou de prendre le vecteur du dernier pixel qui n'était pas un trou suivant la deuxième variante de la façon représentée aux figures 6 et 7. Naturellement la méthode de prédiction temporelle qui exploite largement la corrélation temporelle du mouvement et permet une convergence rapide de l'algorithme récursif reste applicable au procédé qui fait l'objet du présent certificat d'addition. Cependant de la même façon que plusieurs vecteurs spatiaux sont sélectionnés a priori dans leur environnement causal il est aussi possible de sélectionner plusieurs prédicteurs temporels. Par exemple, plusieurs champs de prédic- tion du mouvement peuvent être obtenus par différents filtrages, au moyen par exemple d'une batterie de filtres 108, 109, du champ du mouvement issu de la projection temporelle mémorisé par exemple dans une mémoire 110 comme cela est représenté a la figure 8. Selon l'importance du filtrage du champ de mouvement le champ prédicteur pourra être soit adapté aux zones de rup- ture du mouvement ou au contraire aux zones de l'image à mouve- ment homogène. Une mise en oeuvre du procédé qui vient d'être décrit peut naturellement être effectuée au moyen des dispositifs déjà décrits dans la demande de brevet principal, mais elle peut également avoir lieu en utilisant des structures de microproces- seurs connues convenablement programmés pour l'exécution des étapes du procédé représenté à la figure 1. REVENDICATIONS 1. Procédé d'estimation de mouvement dans une séquence d'images animées selon l'une quelconque des revendications 1 à 6 et 15 à 22 de la demande de brevet principal caractérisé en ce qu'il consiste à calculer,en une seule itération et pour chaque vecteur déplacement estimé Dpj, une valeur DFD(Dpj) de différence inter-images déplacée entre la luminance du point courant et sa valeur de luminance dans la trame précédente déca- lée de la distance Dp, à comparer (101) les valeurs absolues des valeurs DFD obtenues pour sélectionner le vecteur de déplacement estimé Dp] qui correspond à la valeur absolue de DFD(Dpj) la plus faible, oet à calculer (102... 107) le vecteur déplacement courant D] par exécution de l'algorithme de gradient à partir du gradient spatial du vecteur déplacement sélectionné et de la valeur DFD(Dpj) correspondante. 2. Procédé selon la revendication 1 caractérisé en ce que le gradient spatial du point courant est calculé en ne prenant en compte que les quatre points les plus proches de chaque point extrémité du vecteur déplacement. 3. Procédé selon la revendication 2 caractérisé en ce que 2G le gradient de chaque point extrémité du vecteur déplacement est calculé, en mesurant sur chaque ligne située à proximité de part et d'autre du point extrémité du vecteur déplacement, la diffé- rence des valeurs des luminances (L1, L2, L3, L4) des deux points sur chaque ligne adjacente au point extrémité du vecteur déplacement en prenant la moyenne des différences de luminance obtenues sur chaque ligne. 4. Procédé selon la revendication 3 caractérisé en ce que le gradient de chaque point extrémité dr, vecteur déplacement est calculé dans la direction du balayage vertical de l'image en mesurant, sur chaque colonne située à proximité et de part et d'autre du point extrémité du vecteur déplacement, la différence des valeurs des luminances (L1, L2, L3, L4)des deux points sur chaque colonne adjacente au point extrémité du vecteur déplacement en prenant la moyenne des différences des luminances obtenues sur chaque colonne. 5. Procédé selon l'une quelconque des revendications 1 à 4 caractérisé en ce qu'il consiste à faire subir à chaque couple d'image sur lequel est estimé le mouvement, une rotation d'un quart de tour. 6. Procédé selon l'une quelconque des revendications 1 à 5 caractérisé en ce qu'il consiste, pour combler des trous exis- tants dans le champ de prédiction du mouvement après projection temporelle, à considérer pour chaque trou courant, les vecteurs s'ils existent des quatre pixels l'environnant et à définir le vecteur mouvement comme la moyenne des composantes des vec- teurs existants. 7. Procédé selon la revendication 6 caractérisé en ce qu'il consiste pour définir un vecteur associé à un trou, à sélectionner le vecteur qui minimise la valeur absolue de la différence intra-image déplacée DFD pour le pixel trou courant. 8. Procédé selon la revendication 6 caractérisé en ce qu'il consiste à sélectionner le vecteur le plus proche de la moyenne des vecteurs existants. 9. Procédé selon l'une quelconque des revendications 1 à 9 caractérisé en ce qu'il consiste à définir plusieurs prédIcteurs temporels pour chaque point de l'image courante par filtrages au moyen d'une batterie de úiltresdu champ de mouvement Issu de la projection temporelle. 10. Procédé selon l'une quelconque des revendications 1 à 9 caractérisé en ce qu'il consiste à effectuer un filtrage spa- tial du champ de mouvement avant projection temporelle pour définir chaque nouveau champ de prédiction. 11. Dispositif pour la mise en oeuvre du procédé selon l'une quelconque des revendications 1 à 10. 12. Dispositif selon la revendication 10 caractérisé en ce qu'il comprend des moyens pour filtrer les champs de mouvement issus de la projection temporelle.