Brevet FR2696255A1 — publié le 19940401

Procédé de détermination de vecteurs de mouvement. La présente invention concerne un procédé de détermination de vecteurs de mouvement pour un signal image subdivisé en images complètes ou partielles, chaque image étant divisée en blocs et un vecteur de mouvement étant déterminé pour chaque bloc en au moins deux stades, un certain nombre de vecteurs de mouvement étant supposés comme possibles à chaque stade et, pour chacun de ces vecteurs de mouvement, une fonction d'écart étant respectivement utilisée pour chaque point d'image du bloc, en fonction des valeurs de laquelle le vecteur le plus favorable est sélectionné et est retenu, éventuellement, comme l'un des vecteurs supposés comme possibles pour un stade suivant. Un tel procédé est, par exemple, décrit dans la revue 'Proceedings of the IEEE, Vol 73, N O 4, avril 1985, pages 523 à 548 " Ce procédé, qualifié la plupart du temps de Block Matching Algorithm à trois stades, fournit pour une image complète ou une image partielle d'un signal image divisé en un nombre pré-déterminé de blocs, chaque fois un vecteur de mouvement qui est valable pour tous les points d'image du bloc qui lui est affecté et indique leur mouvement entre deux images On présume à cet effet que tous les points d'image d'un bloc sont soumis au même mouvement Le procédé opère en trois stades, étant entendu qu'un nombre prédéterminé de vecteurs de mouvement est supposé comme possible dans chaque bloc, et que, pour chacun de ces vecteurs de mouvement à l'aide d'une fonction d'écart pour chaque point d'image individuel est contrôlé lequel des vecteurs reproduit le mieux le mouvement réellement présent Dans la fonction d'écart, en principe, pour chaque point d'image du bloc, dont il faut contrôler un vecteur de mouvement, le point d'image de l'image actuelle est comparé au point d'image correspondant déplacé du vecteur de mouvement à contrôler dans l'image précédente Plus l'écart entre les deux points est important, plus la valeur de la fonction d'écart pour ce point d'image est grande Par sommation pour tous les points d'image du bloc, on obtient alors une valeur de la fonction d'écart qui indique, pour tous les points d'image du bloc, la qualité de reproduction du mouvement réellement présent par la valeur du vecteur de mouvement accepté Plus la valeur de la fonction d'écart est grande, moins bonne sera la reproduction du mouvement réel - par le vecteur de mouvement correspondant. On procède de la sorte en trois stades à la recherche du vecteur de mouvement le plus favorable Dans le premier stade, on choisit les vecteurs de mouvement qui présentent des valeurs s'écartant fortement l'une de l'autre Le vecteur de mouvement le plus favorable trouvé de la manière décrite ci-dessus dans le premier stade parmi les vecteurs de mouvement supposés comme possibles est choisi dans le deuxième stade quasiment comme point de départ Dans le deuxième stade, on supposera comme possibles, tout autour de ce vecteur de mouvement, d'autres vecteurs de mouvement dont les valeurs s'éparpillent autour de la valeur du vecteur de mouvement déterminé dans le premier stade comme vecteur le plus favorable Dans le deuxième stade, toujours de la manière décrite ci-dessus, on déterminera le vecteur de mouvement le plus favorable qui est choisi comme point de départ pour le troisième stade Dans le troisième stade, autour de ce vecteur déterminé, on supposera comme possibles d'autres vecteurs qui ne s'écartent que relativement peu du vecteur de mouvement déterminé dans le deuxième stade Dans le troisième stade, toujours de la manière décrite ci-dessus, on déterminera le vecteur le plus favorable qui représente la valeur finale et qui reproduit de manière relativement précise le mouvement présent dans le bloc. Ce procédé a l'inconvénient qu'une erreur, qui intervient dans le premier stade lors de la détermination du vecteur de mouvement, ne peut être corrigée que partiellement dans les stades suivants En d'autres termes, si un vecteur de mouvement est complètement faux dès le premier stade, il ne peut plus être corrigé de manière déterminante dans les stades suivants Une telle erreur, en particulier, lors de la détermination du vecteur de mouvement dans le premier stade, est surtout due aux bruits de fond, mais également à des zones à structure périodique dans lesquelles une même structure se reproduit (par exemple une clôture en lattis) à une distance déterminée du point de départ Dans de tels cas, un vecteur de mouvement erroné est fréquemment déterminé dans le premier stade, vecteur qui ne peut plus être soumis qu'à une correction:faibl e:dans;-lés stades suivants. C'est un but de l'invention de développer le procédé du type spécifié dans le premier paragraphe, de telle sorte qu'il soit moins sujet à ce genre d'erreurs. Ce but est atteint selon l'invention par le fait que: dans le premier stade, * a: on soustrait une valeur prédéterminée de la valeur déterminée de la fonction d'écart du vecteur qui a la plus petite longueur et, ensuite, on procède à la comparaison avec les valeurs déterminées de la fonction d'écart des autres vecteurs de mouvement supposés comme possibles et, dans un stade suivant, on soustrait une valeur prédéterminée chaque fois de la valeur du vecteur de mouvement, qui a été déterminée dans le stade précédent comme vecteur de mouvement le plus favorable, et on compare la valeur ainsi réduite de la fonction d'écart de ce vecteur aux valeurs de la fonction d'écart des autres vecteurs du même stade pour déterminer le vecteur le plus favorable. L'invention est basée sur le fait que les erreurs mentionnées plus haut, lors de la détermination des vecteurs de mouvement, en particulier, dans le premier c stade, sont dues surtout au fait que l'on détermine un mouvement qui en réalité n'est pas du tout présent C'est le cas en, particulier, lorsque le signal image est bruité Il peut alors se présenter, par apparition fortuite de valeurs d'image dues au bruit, un semblant de mouvement, qui n'est pas du tout réel C'est le cas de la même manière pour les autres stades du procédé Même pour la structure périodique de ce contenu image, il y a risque que l'on détermine un mouvement qui n'est pas présent réellement et qui n'est que simulé par la structure périodique. Selon l'invention il est donc prévu, dans le premier stade du procédé, de réduire la valeur de la fonction d'écart du vecteur de plus petite longueur d'une valeur prédéterminée De manière générale, au cours du premier stade, on choisit un ensemble de vecteurs de mouvement supposés comme possibles, parmi lesquels un vecteur de valeur zéro qui indique donc qu'il n'y a pas de mouvement De la manière décrite ci- dessus, dans le premier stade, on détermine la fonction d'écart pour chacun de ces vecteurs On compare les valeurs des fonctions d'écart pour chacun de ces vecteurs de mouvement les unes aux autres et on accepte comme le plus favorable, le vecteur de mouvement dont la valeur de la fonction d'écart est la plus petite Conformément à l'invention, avant cette comparaison des valeurs des fonctions d'écart des vecteurs de mouvement supposés comme possibles, on réduit d'une valeur prédéterminée la valeur de la fonction d'écart du vecteur de la plus petite longueur, de manière générale, de la longueur zéro Ce n'est qu'ensuite que l'on effectue la comparaison de cette valeur réduite de la fonction d'écart avec les valeurs de la fonction d'écart des autres vecteurs. Par cette réduction de la valeur de la fonction d'écart du vecteur de la plus petite longueur, il est acquis que ce vecteur de mouvement est choisi en priorité Par dû 2696255 soustraction d'une valeur de sa fonction d'écart, ce vecteur de mouvement est quasiment préféré et on le choisira en cas de doute lorsque les valeurs des fonctions d'écart des vecteurs de mouvement supposés comme possibles présentent des valeurs similaires. Par cette procédure, en particulier, dans les cas décrits ci-dessus de bruit ou de contenu image répétitif, on choisira en cas de doute le vecteur de mouvement de la plus petite longueur (en règle générale de la longueur nulle) De la sorte, le procédé est dès le premier stade nettement moins sujet aux erreurs décrites. Dans les autres stades du procédé, on suppose à nouveau quelques vecteurs de mouvement comme possibles et on choisit parmi ceux-ci, de la manière décrite plus haut, le vecteur de mouvement le plus favorable Dans ce cas, le vecteur de mouvement déterminé comme le plus favorable dans le premier stade est quasiment choisi comme centre Les valeurs des autres vecteurs de mouvement, qui sont supposés comme possibles, sont choisies, de telle sorte qu'ils se situent autour des vecteurs de mouvement déterminés dans le premier stade Après détermination des fonctions d'écart pour les vecteurs de mouvement supposés comme possibles du deuxième stade, on déduit selon l'invention du vecteur déterminé dans le premier stade à nouveau une valeur prédéterminée De la sorte, dans le deuxième stade, c'est ce vecteur qui sera traité de préférence, si bien que, dans le cas de valeurs similaires des autres vecteurs supposés comme possibles, on choisira le vecteur déterminé dans le premier stade Cela vaut également pour un éventuel troisième stade o l'on donnera la préférence de la même manière au vecteur de mouvement déterminé précédemment comme le plus favorable dans le deuxième stade, et l'on retirera une valeur prédéterminée de la valeur de sa fonction d'écart, avant comparaison avec les valeurs des fonctions d'écart des autres vecteurs de mouvement supposés comme possibles dans le troisième stade. Dans les autres stades également, on obtiendra les avantages décrits ci- dessus Le procédé est, de manière générale, moins sensible au bruit et aux contenus d'images périodiques; de la sorte, on obtient simultanément l'avantage que, pour des blocs voisins, on détermine des vecteurs de mouvement relativement semblables la plupart du temps, ce qui n'est pas le cas dans le procédé selon l'état de la technique, en particulier, dans le cas d'images bruitées. Le procédé est utilisable de manière particulièrement avantageuse dans un encodeur HD-MAC, qui doit transmettre des vecteurs de mouvement à un décodeur HD-MAC, de telle sorte que cet encodeur soit en mesure de reproduire correctement t - des mouvements Par ailleurs, ces vecteurs de mouvement sont également nécessaires dans le codeur lui-même. Un développement de l'invention prévoit, pour le procédé dans lequel les vecteurs de mouvement supposés comme possibles sont, dans le premier stade largement distribuées, dans un deuxième stade distribuées plus étroitement autour du vecteur déterminé dans le premier stade, et dans un troisième stade distribuées encore plus étroitement autour de la valeur déterminée dans le deuxième stade, que la valeur soustraite dans le premier stade de la valeur de la fonction d'écart du vecteur de la plus petite longueur soit plus grande que la valeur soustraite dans le deuxième stade de la valeur de la fonction d'écart du vecteur de mouvement déterminé auparavant dans le premier stade comme le plus favorable, et que la valeur soustraite dans le deuxième stade de la valeur de la fonction d'écart du vecteur de mouvement déterminé dans le premier stade comme le plus favorable soit plus grande que la valeur soustraite dans le troisième stade de la valeur de la fonction d'écart du vecteur de mouvement déterminé auparavant dans le deuxième stade comme le plus favorable. Dans le procédé à trois stades décrit ci-dessus, on choisit dans le premier stade les valeurs des vecteurs de mouvement supposés comme possibles, de telle sorte qu'ils s'éparpillent de manière relativement large Dans le deuxième stade les valeurs des vecteurs supposés comme possibles sont déjà regroupées plus étroitement et, dans le troisième stade, elles sont les plus proches les unes des autres Grâce à cette procédure, il est acquis que le premier stade indique quasiment une sorte de direction approximative du mouvement, qui est alors affinée dans les stades suivants, pour atteindre enfin la valeur finale du mouvement Dans le cadre de cette procédure, il est avantageux que les valeurs soustraites selon l'invention des vecteurs de mouvement respectivement préférés soient choisies différemment de manière adéquate dans chaque stade du procédé Dans le premier stade, il faut choisir un niveau relativement grand pour la valeur qui sera soustraite de la valeur de la fonction de distribution du vecteur dans le premier stade et les valeurs soustraites au cours des stades deux et trois devront êtres choisies à des niveaux respectivement plus petits Il en résulte une adaptation des valeurs soustraites et donc quasiment du degré de préférence du vecteur de la fonction d'écart duquel la valeur est soustraite, à la mesure de la dispersion des valeurs des vecteurs de mouvement acceptés dans le stade en question. Le procédé selon l'invention sera expliqué plus en détail ci-après avec référence à la figure unique du dessin annexé qui représente schématiquement un fragment d'un bloc d'une image complète ou d'une image partielle, sur laquelle le procédé de détermination des vecteurs de mouvement en trois stades est utilisé. Le dessin représente dans la direction des X une échelle de 6 à + 6 et dans la direction des Y également une échelle de 6 à + 6 Sur la figure, sont reportés neuf cercles destinés à indiquer les vecteurs de mouvement supposés comme possibles dans le premier stade L'un des vecteurs de mouvement est disposé au centre et porte les valeurs X = O et Y = 0 Ce vecteur de mouvement reproduit donc le cas o il n'y a pas de mouvement Les autres huit vecteurs de mouvement dans le premier stade sont distribués de manière relativement large et, dans l'exemple représenté sur la figure, ils s'écartent dans la direction des X et/ou des Y chacun de la valeur 3 par rapport au vecteur de mouvement X = 0, Y = 0. Dans le premier stade du procédé est formée, pour chacun de ces neuf vecteurs de mouvement, une fonction d'écart qui peut apparaître différente, mais qui est choisie dans chaque cas, de telle sorte qu'elle indique l'écart existant entre un point du bloc présent et le point d'image correspondant du bloc correspondant de l'image précédente, qui a été déplacé selon le vecteur de mouvement respectivement accepté La fonction d'écart ainsi déterminée pour chaque point d'image du bloc est sommée pour un vecteur de mouvement accepté si bien que la somme indique la qualité du vecteur de mouvement accepté en moyenne pour les points d'image du bloc. Selon l'invention, cette valeur de sommation de la fonction d'écart du vecteur de plus petite longueur est réduite d'une valeur prédéterminée Dans le cas d'exemple de la figure, le vecteur de plus petite longueur est celui qui correspond à X = O, Y = O La valeur de la fonction d'écart pour tous les points d'image de ce vecteur est à présent réduite d'une valeur prédéterminée Ce n'est qu'ensuite que la valeur de la fonction d'écart de ce vecteur de mouvement est comparée aux valeurs des fonctions d'écart des huit autres vecteurs de mouvement supposés comme possibles. Pour le deuxième stade on choisit, comme point de départ, le vecteur de mouvement dont la valeur de la fonction d'écart (ou la valeur réduite de la fonction d'écart) est la plus petite Lorsque, par exemple, les valeurs des fonctions d'écart pour les neuf vecteurs de mouvement présentent des valeurs similaires dans le premier stade, on choisira le vecteur de mouvement de valeur X = 0, Y = 0, car sa valeur a été réduite selon l'invention d'une valeur prédéterminée, de sorte que la valeur ainsi réduite est plus petite que la valeur de la fonction d'écart des autres vecteurs de mouvement et est donc choisie comme la plus favorable Dans la représentation de la figure, on part du fait que ce n'est pas le cas, mais que le vecteur de mouvement de valeur X = 3, Y = 3 présente une fonction d'écart nettement plus faible, qui est encore plus faible que la valeur réduite de la fonction d'écart du vecteur de mouvement de valeur X = 0, Y = O Dès lors, en dépit de la réduction de la valeur de la fonction d'écart du vecteur X = 0, Y = 0, on choisira le vecteur de mouvement de valeur X = 3, Y = 3. Dans le deuxième stade du procédé, on choisit le vecteur de mouvement déterminé dans le premier stade comme l'un des vecteurs de mouvement supposés comme possibles dans le deuxième stade Les autres vecteurs de mouvement supposés comme possibles dans le deuxième stade se regroupent autour de la valeur de ce vecteur de mouvement Ils sont caractérisés dans la figure par des étoiles La distance des huit autres vecteurs de mouvement par rapport au vecteur de mouvement central déterminé comme optimal dans le premier stade est moindre que la distance des huit vecteurs de mouvement dans le premier stade par rapport au vecteur de mouvement central de valeur X = 0, Y = 0. Dans le deuxième stade, on procède en principe de la même manière que dans le premier stade à une détermination des valeurs des fonctions d'écart et à une comparaison des valeurs des fonctions d'écart Avant cette comparaison, on soustrait une valeur prédéterninée de la valeur de la fonction d'écart du vecteur de mouvement déterminé auparavant dans le premier stade comme vecteur de mouvement optimal pour X = 3, Y = 3 Cette valeur soustraite est cependant moindre que celle dont la valeur de la fonction d'écart du vecteur de mouvement X = 0, Y = O a été réduite dans le premier stade. De même, dans le deuxième stade, dans le cas de valeurs similaires de tous les neuf vecteurs de mouvement, on choisira dans le doute le vecteur de mouvement central, c'est-à-dire, donc le vecteur qui a été déterminé dans le premier stade comme le vecteur de mouvement optimal. Le vecteur de mouvement déterminé dans le deuxième stade comme optimal (sur la figure, le vecteur X = 5, Y = 5) est à nouveau choisi dans le troisième stade comme vecteur de mouvement central autour duquel se regroupent les autres vecteurs de mouvement supposés comme possibles du troisième stade Ceux-ci sont symbolisés dans la figure par des carrés. Dans le troisième stade, on répète la procédure du deuxième stade o l'on réduit d'une valeur prédéterminée le vecteur qui a été déterminé comme optimal dans le deuxième stade par rapport à la valeur de sa fonction d'écart Cette valeur de réduction prédéterminée est à nouveau plus petite que la valeur choisie dans le deuxième stade comme terme soustractif du vecteur de mouvement déterminé auparavant dans le premier stade. En résumé, on choisit dans chacun des trois stades, en cas de doute, le vecteur de mouvement central Ceci a surtout l'avantage que, dans le cas de valeurs fortuites, qui peuvent se présenter dans l'image surtout en cas de bruit, aucun mouvement qui ne soit pas réel n'est indiqué par le vecteur de mouvement déterminé. C'est pratiquement une espèce de "pré-tension" du vecteur de mouvement de valeurs X = O, Y = O dans le premier stade ou dans les stades deux et trois du vecteur de mouvement qui a été déterminé dans le stade précédent. il, __ - REVENDICATIONS: 1 Procédé de détermination de vecteurs de mouvement pour un signal image subdivisé en images complètes ou en images partielles, chaque image étant divisée en blocs et un vecteur de mouvement étant déterminé pour chaque bloc en au moins deux stades, un certain nombre de vecteurs de mouvement étant supposés comme possibles à chaque stade et, pour chacun de ces vecteurs de mouvement, une fonction d'écart était respectivement utilisée pour chaque point d'image du bloc en fonction des valeurs de laquelle le vecteur le plus favorable est sélectionné et est retenu, éventuellement, comme l'un des vecteurs supposés comme possibles pour un stade suivant, caractérisé en ce que, dans le premier stade, on soustrait une valeur prédéterminée de la valeur déterminée de la fonction d'écart du vecteur qui a la plus petite longueur et, ensuite, on procède à la comparaison avec les valeurs déterminées de la fonction d'écart des autres vecteurs de mouvement supposés comme possibles et, dans un stade suivant, on soustrait respectivement une valeur prédéterminée chaque fois de la valeur de la fonction d'écart du vecteur de mouvement, qui a été déterminée dans le stade précédent comme vecteur de mouvement le plus favorable, et on compare la valeur ainsi réduite de la fonction d'écart de ce vecteur à la valeur de la fonction d'écart des autres vecteurs du même stade pour déterminer le vecteur le plus favorable. 2 Procédé selon la revendication 1, dans lequel les vecteurs de mouvement supposés comme possibles sont, dans le premier stade, largement distribuées, dans un deuxième stade, distribuées plus étroitement autour du vecteur déterminé dans le premier stade et, dans un troisième stade, distribuées encore plus étroitement autour du vecteur déterminée dans le deuxième stade, caractérisé en ce que la valeur soustraite dans le premier stade de la valeur de la fonction d'écart du vecteur de la plus petite longueur est plus grande que la valeur soustraite dans le deuxième stade de la valeur de la fonction d'écart du vecteur de mouvement déterminé auparavant dans le premier stade comme le plus favorable, et que la valeur soustraite dans le deuxième stade de la valeur de la fonction d'écart du vecteur de mouvement déterminé dans le premier stade comme le plus favorable soit plus grande que la valeur soustraite dans le troisième stade de la valeur de la fonction d'écart du vecteur de mouvement déterminé auparavant dans le deuxième stade comme le plus favorable.