FR 2729266 A1 19960712 FR 9500204 A 19950110 PROCEDE D'INTERPOLATION D'IMAGES DESCRIPTION Domaine technique La présente invention concerne un procédé d'interpolation d'images par triangulation et transformation géométrique. Io Etat de la technique antérieure Le domaine technique de rinvention est celui de rinterpolation d'images, que cette interpolation soit temporelle ou stroscopique. De manière générale rinterpolation inter-images temporele i5 consiste en la construction et rinsertion dcirmages supplémentaires par un système de réception. De la qualité des images ainsi reconstituée dépend en partie la qualité du système de compression ou de restitution. Dans le cadre des systèmes de codage d'images a réduction de débit numérique (comme par exemple celui défini par la recommandation H.261 du CCITT (organisation dont la nouvelle appellation est UIT.T) pour le codage de la vidéo à p fois 64 kbit/s), un sous-échantillonnage des images au codeur est un des moyens utilisés. Les images non transmises sont alors dupliquées ou interpolées par le décodeur, ce qui constitue un moyen simple de réduire de manière significative le débit crd'informations nécessaire à la transmission du signal vidéo. Différents procédés d'interpolation crd'images utilisant une estimation et une compensation de mouvement ont été proposés (voir les références[1], [2] et [3] données en fin de description). Une image interpolée peut aussi être utilisée comme une image de prédiction dans certaines méthodes de codage (comme c'est le cas pour la norme de l'ISOIEC 11172.2 dite MPEG1): elles sont appelées alors 'Bframes', "P-frames". L'interpolation temporelle d'images est aussi utile dans le cas d'applications médicales pour lesquelles on peut souhaiter une exposition SP 10057.C/DB minimale du patient à l'appareil de prise de vues (rayons-X par exemple) en réduisant le nombre de vues, c'est-à-dire d'images. Une autre application est celle de l'interpolation d'images dans le cas de la stéréoscopie. On parle alors d'images interpolées stéréoscopiques. Les procédés d'interpolation crd'images se réduisent dans de nombreuses mises en oeuvre pratiques à une simple recopie à partir de rimage précédente (relecture d'une mémoire) ou à une interpolation linéaire. Des études basées sur l'estimation de mouvement ont été proposés par quelques auteurs (voir les références [1] et [3D. Souvent, le calcul des vecteurs de mouvement est fait sur des blocs de tailles rectangulaires (ou carrées) N x M. La triangulation des images a surtout été proposée pour améliorer la prédiction d'images dans le cas de schémas inter-images avec estimation-compensation de mouvement (voir les références [4] et [5). La notion d'image bidirectionnelle n'est, dclassiquement, pas utilisée avec une estimation de mouvement basée triangle mais seulement avec une base de blocs. Dans un procédé classique d'interpolation temporelle, les séquences obtenues par simple recopie de l'image précédente présentent I'inconvénient d'être saccadées. L'utilisation d'une simple interpolation linéaire produit de plus un effet d'ombrage et de flou qui sont très génants. Dans des procédés plus élaborés, il est nécessaire d'identifier plusieurs zones, telles que le fond ou les objets en mouvement, ou de calculer des masques de segmentation. Mais les interpolations utilisant des vecteurs mouvements obtenus sur des blocs de taille M x N ne permettent pas de former une image interpolée continue issue d'un champ de vecteur dense. Les procédés connus qui visent à obtenir des champs de vecteurs plus denses et plus continus nécessitent le calcul des vecteurs vers l'avant (futur de rimage (n-k) vers rimage (n)) et vers ranière (passé de rimage (n) vers l'image (n-k)) afin d'identifier des zones d'occlusion (voir la référence [ID. Les procédés existants à ce jour ne permettent pas facilement, et en un seul passage, crobtenir un champ de vecteurs pour l'image à interpoler qui couvre l'image de façon continue. Un des problèmes les plus importants à résoudre pour l'interpolation par compensation de mouvement est la détermination c'un SP 10057.C/DB vecteur mouvement pour chaque point de l'image à interpoler. Des phénomènes tels que des occlusions, des effets de zooms, des ambiguïtés sur la nature du point (fond ou objet en mouvement) produisent des lacunes dans le plan de l'image interpolée qui doivent être comblées, et des ambiguïtés qui doivent être résolues afin d'éviter les artefacts dans rimage interpolée. Pour résoudre ces problèmes, rinvention a pour objet un procédé permettant de produire des images interpolées en utilisant des champs de vecteurs denses et continus. L'invention a également pour objet de minimiser la quantité d'informations à transmettre. Exposé de l'invention L'invention propose un procédé dans lequel on utilise une triangulation des images et une estimation des mouvements de sommets pour réaliser une interpolation d'images sous-échantillonnées temporellement ou stéréoscopiquement Avantageusement on calcule un vecteur mouvement pour chaque point de l'image à interpoler, sans problème d'indétermination ou d'ambiguïté et sans nécessiter un double calcul vers ravant et vers l'arrière. Avantageusement l'étape de cacul des sommets (ou noeuds) des triangles est réalisée automatiquement. L'une des originalités principales du procédé de rinvention réside dans le fait que les sommets sont calculés par le système luI-mme, sans transmission d'information supplémentaire. Avantageusement le procédé de rinvention peut être amélioré par la transmission d'informations supplémentaires afin d'augmenter la qualité de rinterpolation. Dans ce cas, l'invention peut faire partie intégrante d'un système de codage utilisant des modes de prédiction bidirectionnelles. Dans un mode de réalisation avantageux le procédé de l'invention comprend successivement les étapes suivantes: - mémorisation des images n et n-p; triangulation complète d'une image de référence permettat de réaliser une triangulation à partir d'un ensemble de points choisis dans l'image d'après certaines caractéristiques prédéterminées; SP 10057.CIDB -estimation du mouvement et des déformations de ces triangles pour l'image n-k+p avec 0 efficace dans un système de reconstitution en codant rerreur crinterpolation. Le procédé de triangulation est alors appliqué sur des points privilégiés dont la détermination est faite de manière univoque dès lors que les images considérées sont identiques. Ainsi, rensemble des cinq étapes précédentes peut être réasé par le décodeur sans la transmission ou rutilisation de données suppletai pour calculer rimage interpolée prédite. SP 10057.C/DB Un codage classique est alors réalisé sur le signal crerreur entre l'image vraie et sa prédiction (r'image interpolée). On peut ainsi utiliser une interpolation par triangulation dans un codage quelconque. Aux cinq étapes précédentes sont donc ajoutés pour toute image (n-k+ p) avec 0 classique de rimage erreur de prédiction. 15. Au décodage (ou plus généralement avec tout système de traitement inverse) la sixième étape est la même et la sepfième étape devient: rerreur de prédiction est décodée et ajoutée à r'image erreur de prédiction calculée dans la sixième étape. L'invention utilisée dans le cadre crd'un système de compression permet d'utiliser rimage interpolée comme une prédiction pour laquelle des données complémentaires peuvent être transmises à raide crd'un procéd classique (par exemple un codage par transformation du signal dcrerreur entre rimage vraie et sa prédiction interpolée avec le procédé de rinvention). Le procédé de rinvention ne nécessite pas de transmettre les points caractéristiques (sommets des triangles et vecteurs) utilisés. Ce même procédé de rinvention est applicable pour le calcul d'images intermédiaires dans le cas d'images stéréoscopiques. Le rendu de séquences animées dans lesquelles des images ont été omise est très nettement amélioré. Par exemple, une mise en oeuvre du procédé crinterpolation crd'images sur des séquences codées avec H.261 à 10 Hz montre un gain très visible et important en terme de SNR. Le rendu stéréoscopique pour lequel le nombre de vues a été limité est grandement amélioré. SP 10057.C/DB Brève description des dessins - La figure 1 illustre la on d'une image; - la figure 2 illustre une interpolation inter-image par compensation de mouvement basée sur une décomposition triangulaire crune image; - la figure 3 illustre le fonctionnement crd'un mode de réalisation de l'invention; - la figure 4 illustre rétape de détermination des sommets et de la triangulation; - la figure 5 illustre le déplacement des sommets d'un triangle englobant un point considéré; - ces figures 6A, 6B et 6C illustrent le calcul des points de l'image en fonction de leurs vecteurs estimés; - la figure 7 illustre de manière générale ce mode de réalisation de rinvention. Exposé détaillé de rinvention Comme représenté sur la figure 1, une image est représentée par un ensemble de triangles adjacents. Les sites de référence considérés sont les sommets de chaque triangle, de manière à ce que rimage transfomnée obtenue soit continue. Les images (n) et (n-k) entre lesquelles les images sont à interpoler sont mémorisées afin que les calculs nécessaires à la mises en oeuvre du procédé puissent être réalisés. Le nombre d'images qui peuvent être interpolées est variable: il dépend de la valeur de k Les images (n) et (n-k) peuvent consister en des images d'une même scène à des temps (n) et (n-k) différents (cas d'interpolation tempomle), ou en des images représentant une même scène au même instant sous des angles de vue différente (cas d'interpolation stéréoscopique). Plusieurs techniques de triangulation sont connues et ont déjà été proposées pour des applications de prédiction dans le codage rd'image, mais l'originalité du présent procédé provient du fait que la technique est utilisée pour SP 10057.C/DB une interpolation et que la transmission des sommets des triangles peut être omise. La figure 2 illustre une interpolation inter-image par compensation de mouvement basée sur une décomposition triangulaire d'une image. Mode interpolation pure Ce premier mode réalisation de rl'invention, représenté sur la figure 3, comprend la succession des étapes suivantes: Une première étape consiste à mémoriser les images (n) et (n-k). Ces images (n) et (n-k) sont celles qui sont connues par le système de reconstruction. Dans le cas dcrun décodeur, il s'agit des images reconstruites à partir des informations transmises par un codeur. Le nombre crimages qu'il est possible crd'interpoler correspond à la valeur (k-1). Une seconde étape consiste en la triangulation complète de l'image de référence, qui dans ce mode peut être rimage (n) ou rimage (n-k) suivant la mise en oeuvre choisie. Dans cette étape de triangulation un maillage automatique est mis en oeuvre dans le cadre du procédé. Il consiste à réaliser une triangulation à partir crd'un ensemble de points choisis dans l'image d'après certaines caractéristiques prédéterminées. En particulier, on peut choisir des points de gradient important, comme des points de différence temporelle importante. Les sommets sont choisis parmi ces points de telle façon qu'ils soient répartis dans toute rimage. Un exemple de maillage peut étre le suivant: rimage (n-k) est soumise à un filtrage passe-haut. L'image de gradient obtenue, qui peut être seuillée, foumrnit rensemble des points parmi lesquels seront choisis les sommets. Cette sélection se fait, par exemple, en définissant un intervalle minimum entre chaque sommet, cet intervalle tenant compte du nombre total de sommets, des dimensions de rimage et du nombre de points de gradient obtenus. Un autre procédé simple de sélection consiste à ne retenir que les NbMax points de SP 10057.CIDB gradients les plus grands. Un exemple de masque de gradient utilisé pour le filtrage passe-haut est alors: O -1 01 -1 4 -1 O -1 0) Le nombre de sommets NbMax est un paramètre qui peut être variable en fonction de la précision recherchée et de la complexité admise. Les paramètres issus de cette deuxième étape sont les coordonnées des sommets (ou noeuds) Sà des triangles. Une troisièeme étape est restimation du mouvement et des déformations de ces triangales pour rimage (n-k+p) avec O de codage basé triangle du type de celui proposé dans les référeces [3] et [4]. Les paramètres issus de cette troisième étape sont les estimations des vecteurs déplacement des sommets entre rimage (n-k) et l'image (n-k+p) notés DS(,.),_+p). A partir de ces vecteurs on calcule les coordonnées des sommets déplacés S;,.k+p). La description de la détermination des sommets est illustrée sur la figure 4 sur laquelle on a: - NbG = nombre de points de gradient; - NbD = nombre de points de différence; - Dimrlm = dimensions de rimage; - NbMax =nombre de sommets total. La triangulation peut être ceUe définie par Delaunay dans la référence [6]. SP 10057.C/DB Une quatrième étape consiste à calculer les vecteurs pour chaque point des triangles de l'image (n-k+p) à interpoler, c'est--dire à faire une estimation des déformations. L'évolution de chaque triangle est représentée par une transformation affine. Ce type de transformation permet la résentation d'un grand nombre de transformations telles que des rotations, des zooms, des translations. Pour chaque point (xy) de la région considérée, la position transformée (x', y) correspondante est donnée par la relation suivante: (yf) (c ") d (f) o les coefficients a, b, c, d, e, f sont déterminés pour chaque triangle. la valeur des composantes du vecteur déplacement au point considéré est calculé comme suit: {u(x,y) = x'-x = (a -1)x -by - e - a -a2x -a3x v(x, y) = y'-y = cx - (d-1)y- f a4 - a5x - a,y ou encore, sous forme matricielle: Fui [1X y 0 0 0la a V 0 0 o 1 x y a Comme représenté sur la figure 5 les six composantes ai sont calcules en fonction des déplacements aux sommets (ou noeuds) Se.", du triangle englobant le point considéré: u1, x,yY, 0 0 0 a u2 1X2 Y2 0 a u3 1 X3 y3 0 00 0= I[cD] 0 [a] v, 0 0 0 x1 yx a4 [4o1[ v2 0 0 0 1 x2Y2 Ca V3 0 0 1 X3 Y3 LaJ SP 10057.C/DB Pour déterminer les coefficients ai en fonction des déplacements nodaux, l'inverse de la matrice (D est calculé: X2y3 - X3Y2 X3y1 - XtY3 XIY2 - X2A a1 a. a3 [Dr' d et(O) Y2 - Y3 Y3 - Y, Y - Y2 det O X3 - X2 Xi - X3 X2Xl.det A Y2 Y3 avec: det(o) = x2y3 - x3y2 - x3y1, - xy3 - x1y2 -xy1 La matrice est inversible si le détermninant est différent de zéro, c'est-à-dire si raire du triangle est non nulle, et donc si le triangle n'est pas dégénéré. Le vecteur déplacement en tout point p = (x,y)f s'obtient avec le calcul suivant: D(p)=D(X, Y) [u(: Y)] [i x y O O O]at 1SP):(x'Y) (xy)l:O 0 0 1 x y avec: []= [01][U,] [-1r'd[; Une cinquième étape consiste à calculer les points de rInage (nk+p) en fonction de leurs vecteurs estimés. Dans le procédé de rImnvention l'image est représentée par un ensemble de triangles adjacents, comme ilustré sur les figures 6A, 68 et 6C. Lm(k) correspond à la valeur de rimage m au point k. Cette valeur L peut étre en particulier la luminance ou toute autre caatiti recherchée de rimage. SP 10057.C/DB L'algorithme proposé utilise un champ de vecteurs continu du fait du modèle considéré. Si ron considère les informations de structure et de mouvement, la valeur LIn.+P, par exemple la luminance, de rimage à interpolr est calculée pour chaque triangle de la manière suivante: 4 (X) (T -dCi(X d D)+a4X _ ( T -)D) D(p) =D(xy)= [v(xy)j = Lo o o 1 X Y] 1o avec: [^] [[Or rt:][(W] Le changement de la valeur de (p) permet de calculer une nouvelle image interpolée en reprenant les calculs à partir de la quatrième étape. Le mode de rinvention ainsi défini est représenté, de manière générale, sur la figure 7. Mode interpolation augnngmntée et intégrée de type "images bidirectonneils" Dans un second mode de réalisation, le procédé de rinvention peut aussi s'intégrer à un système de codage à réduction de débit ou être rendu plus efficace dans un système de reconstitution en codant rerreur crinterpolation. Le procéedé de triangulation est appliqué sur des points privilégiés dont la détermination est faite de manière univoque dés lors que les images considérées sont identiques: il s'agit par exemple du chotix des NbMax points de gradient les plus grands avec un masque de calcul prdéfni. SP 10057.C/DB Ainsi, l'ensemble des cinq étapes décrites précédemment peut étre réalisé par le décodeur sans la transmission ou l'utilisation de données supplémentaires pour calculer rimage interpolée prédite. Un codage classique est alors réalisé sur le signal d'erreur entre rimage vraie et sa prédiction (rimage interpolée). Ce procédé permet d'utiliser une interpolation par triangulation dans un codage quelconque. Aux étapes du paragraphe précédent sont donc ajoutées pour toute image (n-k+p) avec 0 entre l'image à transmettre (n-k+p) et rimage interpolée (n- k+p) issue du calcul de la cinquième étape, - dans une septième étape, on réalise le codage par un procédé dclassique de rimage erreur de prédiction. Au décodage (ou plus généralement avec tout système de traitement inverse), la sixième étape reste la même et la septième étape devient: l'erreur de prédiction est décodée et ajoutée à rimage erreur de prédiction calculée dans la sixième étape. SP 10057.CIDB REFERENCES [1] J. Ribas-Corbera, J. Sklanski, Interframe interpolation of cinematic sequences", JVCIR, Vol. 4, No. 4, décembre 1993, page 392 s [2] C. Cafforio, F. Rocca, S. Tubaro, "Motion compensation image interpolation", IEEE Transaction on Communications, Vol. 38, No. 2, Février [3] R. Thoma, M. Bierling, "Motion compensating interpolation considering covered and uncovered background", Signal Processing: Image comm., Vol. 1, No. 2, octobre 1989 [4] J.J. Jacq., C. Roux, "Recalage monomodalité automatique en imagerie médicale 2D et 3D a I'aide d'un algorithme génétique traditionner, 9ème congrès de reconnaissance des formes et intelligence artificielle, AFCET/AFIA, Paris, janvier 1994 [3] H. Brusewitz, "Motion estimation with triangles", Proc 3rd Int. Conference on 64kbps coding of moving video, free session, Rotterdam, Pays-Bas, septembre 1990 [4] H. Brusewitz, "Method of motion compensation and elastic deformation in picture sequences", demande de brevet PCT numéro WO 92/03799 déposée le 12 août 1991 [51 Y. Nakaya, HKi Harashima, "An iterative motion estimation method using triangular patches for motion estimation, SPIE Symp. on Visual Comm. and Image Proc., 1991 [6] Y. Correc, E. Chapuis, "Fast computation of Delaunay triangulations", Adv. Eng. Software, 1987 SP 10057.C/DB REVENDICATIONS 1. Procédé d'interpolation d'image, caractérisé en ce que l'on utilise une triangulation des images et une estimation des mouvements des sommets pour réaliser une interpolation d'images sous-échantillonnées temporellement ou stéréoscopiquement. 2. Procédé selon la revendication 1, caractérisé en ce qu'on calcule un vecteur mouvement pour chaque point de rimage à interpoler. 3. Procédé selon la revendication 1, caractérisé en ce que I'étape de calcul des sommets des triangle est réalisée automatiquement. 4. Procédé selon la revendication 1, caractérisé en ce que les sommets sont calculés sans transmission d'information supplémentaire. 5. Procédé selon la revendication 1, caractérisé en ce qu'il comprend une étape de transmission d'informations supplémentaires afin d'augmenter la qualité de l'interpolation. 6. Procédé selon la revendication 1, caractérisé en ce qu'il comprend successivement les étapes suivantes: - mémorisation des images n et n-k; triangulation complète d'une image de référence permettant de réaliser une triangulation à partir d'un ensemble de points choisis dans l'image d'après certaines caractéristiques prédéterminées; - estimation du mouvement et des déformations de ces triangles pour rimage n-k+p avec 0 vecteurs estimés. 7. Procédé selon la revendication 6, caractérisé en ce que, dans rétape de triangulation, on met en oeuvre un maillage automatique. 8. Procédé selon la revendication 6, caractérisé en ce que, dans rétape de triangulation, I'image de référence est rimage n ou rimage n-k. SP 10057.C/DB 9. Procédé selon la revendication 6, caractérisé en ce que, dans l'étape de triangulation, I'image n-k est soumise à un filtrage passe-haut. 10. Procédé selon la revendication 6, caractérisé en ce que les points choisis dans l'étape de triangulation sont des points de gradient important ou des points de différence temporelle importante. 11. Procédé selon la revendication 6, caractérisé en ce que, dans l'étape de calcul des vecteurs, la valeur des composantes du vecteur déplacement au point considéré est calculée comme suit: u(x,y) = x'-x =(a-1)x + by +e - a1 +a2x +ay v(x, y) = y'-y = cx +(d -1)y + f - a4 + asx +a6y 12. Procédé selon la revendication 11, caractérisé en ce que les six composantes a, sont calculées en fonction des déplacements aux sommets de l'image n-k+p du triangle englobant le point considéré. 13. Procédé selon la revendication 6, caractérisé en ce que la triangulation est appliqué sur des points privilégiés dont la détermination est faite de manière univoque, dès lors que les images considérées sont identiques 14. Procédé selon la revendication 13, caractérisé en ce qu'un codage classique est réalisé sur le signal d'erreur entre rimage vraie et rimage interpolée, ce qui permet d'utiliser une interpolation par triangulation dans un codage quelconque. 15. Procédé selon la revendication 14, caractérisé en ce que, au codage ou au décodage, le calcul du signal d'erreur est constitué rd'une différence seuillée ou non entre l'image à transmettre (n-k+p) et rimage interpolée (n-k+p) issue du calcul de retape de calcul des vecteurs. 16. Procédé selon la revendication 14, caractérisé en ce que, au codage, le codage est réalisé par un procédé classique de rimage erreur de prédiction. 17. Procédé selon la revendication 14, caractérisé en ce que, au décodage, l'erreur de prédiction est décodée et ajoutée à rimage erreur de prédiction calculée. SP 10057.C/DB