Brevet FR2880717A1 — publié le 20060714

L'invention concerne un procédé de segmentation spatio-temporelle d'une image vidéo d'une séquence d'images. Le domaine est celui du traitement vidéo. Dans un exemple, le procédé met en oeuvre un algorithme de type ligne de partage des eaux aussi connu sous l'appellation anglaise de watershed . L'algorithme de type ligne de partage des eaux que l'on io appellera aussi LPE par la suite, issu de travaux sur les outils de morphologie mathématique, appartient à la famille des algorithmes de segmentation à croissance de régions. La LPE simule l'écoulement de l'eau le long d'un relief. Cette approche considère une image à niveau de gris comme un relief topographique, l'altitude étant la valeur du niveau de gris. Ce relief comporte des minima locaux qui représentent des zones connexes de l'image où tous les pixels sont à un même niveau de gris et pour lesquels il est impossible d'atteindre un pixel d'altitude inférieure sans avoir une montée au préalable. L'algorithme de détermination classique des lignes de partage des eaux est basé sur le principe de l'immersion: - on perce un trou dans chaque minimum local du relief, - on procède à une inondation du relief à partir des minima régionaux, de manière à ce que le niveau des eaux monte à vitesse constante et soit uniforme dans tous les bassins de capture, chaque fois que les eaux issues de deux minima régionaux se rencontrent, on construit une digue le long de la ligne de crête, de manière à ce que les eaux issues de deux bassins de capture différents ne se mélangent pas, - une fois le relief totalement immergé, les digues formées sont les lignes de partages des eaux. Si aucune précaution n'est prise, l'utilisation d'un tel algorithme provoque une sur-segmentation de l'image par ces lignes de partage des eaux, le nombre de points d'inondation, les minima locaux de l'image, étant considérable. Une des solutions possibles à ce problème de sur-segmentation consiste à inonder l'image à partir de marqueurs germes. De façon intuitive, il s'agit ici de ne pas percer un trou sur chacun des minima du relief à inonder, mais uniquement à certains endroits de notre choix. Ainsi, les marqueurs sont les seules sources inondant le relief. Les points ou pixels inondés sont marqués, au fur et à mesure de l'inondation, une région, définie par le marqueur germe, étant finalement constituée d'un ensemble de pixels marqués. Cette opération de constitution de régions est aussi appelée par la suite extraction de marqueurs. Les zones de l'image non marquées sont appelées des zones incertaines. Lorsque l'inondation est terminée, la partition résultante a autant de régions que de marqueurs. io Une autre solution, pour le prétraitement de l'image, consiste en un filtrage du paramètre sur lequel doit porter la segmentation, par exemple la luminance, de manière à aplanir les zones afin de diminuer le nombre de minima locaux. La figure 1 décrit un algorithme de segmentation morphologique spatio-temporelle, basé sur la LPE, classiquement utilisé pour obtenir une partition de l'image. Une image courante I(t) est traitée à une première étape référencée 1 qui effectue une segmentation morphologique spatiale de l'image. L'image I(t) et une image suivante I(t+nT) sont traitées lors d'une étape référencée 2 qui effectue une estimation de mouvement entre les deux images. L'étape référencée 3 reçoit des informations de l'étape 1 et de l'étape 2 pour réaliser une fusion de régions. Cette étape permet de fusionner des régions adjacentes en fonction d'un critère d'homogénéité basé sur le mouvement. Cette fusion vise à obtenir des objets au sens sémantique du terme. Après fusion, une image segmentée est obtenue à l'étape 4, fruit de cette partition spatio-temporelle. L'étape de segmentation spatiale est décrite plus en détail au regard de la figure 2. L'image courante I(t) subit d'abord un prétraitement, tel qu'un filtrage morphologique, étape référencée 5. Ce pré-traitement, filtrage passe-bas ou de type érosion-dilatation, permet d'aplanir l'image incidente, de simplifier l'image afin de faciliter l'extraction de régions. L'étape suivante 6 effectue cette opération d'extraction. Les pixels sont marqués, pour définir des régions, en procédant par exemple par extraction de zones quasi plates ou par agrégations successives de pixels voisins en fonction de leurs gradients morphologiques. Les marqueurs spatiaux conditionnent totalement la qualité de la partition et le nombre de 35 régions final. Les pixels non marqués sont assignés à une région grâce à l'étape de décision référencée 7. Cette étape exploite l'algorithme de lignes de partage des eaux. Après cette étape de segmentation spatiale, la fusion des régions, étape référencée 3, est effectuée. Cette étape permet de fusionner des régions adjacentes en fonction d'un critère d'homogénéité basé sur le mouvement, information provenant de l'étape 2. Cette fusion vise à obtenir des objets au sens sémantique du terme. Par exemple, des régions voisines affectées du même mouvement ou d'un mouvement proche sont privilégiées io dans la fusion. Cependant, la segmentation spatiale basée sur des informations spatiales, telles que la luminance, a tendance à créer des faux contours et à considérer un objet ou des parties d'objet comme faisant partie de l'arrière plan ou faisant partie d'un autre objet. En cas de défaillance de la segmentation spatiale, par exemple un objet et le fond considérés comme une unique région, il est impossible de retrouver cet objet dans la partition finale. La fusion des régions ne permet pas de retrouver les objets au sens sémantique du terme. Un des buts de l'invention est de pallier les inconvénients précités. Elle a pour objet un procédé de segmentation spatio-temporelle d'une image vidéo d'une séquence d'images réalisant une estimation de mouvement entre une image courante et une image précédente pour déterminer un mouvement dans l'image courante, comportant les étapes suivantes: - construction de régions spatiales à partir d'un ou plusieurs paramètres spatiaux caractéristiques du contenu de l'image, courante, - construction de régions temporelles à partir d'un ou plusieurs paramètres temporels relatifs au mouvement dans l'image courante, caractérisé en ce qu'il comporte également les étapes suivantes: - classement de régions temporelles en régions d'intérêt, - sélection d'une région spatiale ayant des pixels en commun avec une région temporelle d'intérêt, - calcul d'un premier pourcentage de pixels de la région spatiale qui sont communs avec la région temporelle d'intérêt, - calcul d'un deuxième pourcentage de pixels de la région temporelle d'intérêt qui sont communs avec la région spatiale, - fusion ou scission de la région spatiale en fonction de ces pourcentages. Selon une mise en oeuvre particulière, le procédé est caractérisé en ce qu'une fusion de la région spatiale commune à la région temporelle est réalisée, fusion avec la région temporelle, si le premier pourcentage est supérieur à un seuil et en ce qu'une scission de la région spatiale commune à la région temporelle est réalisée, scission dans la io région spatiale, si le deuxième pourcentage est supérieur à un seuil. Selon une mise en oeuvre particulière, le procédé est caractérisé en ce qu'il comporte une étape de traitement de points incertains, c'est à dire non affectés à une région lors de leur construction, exploitant un algorithme de partage des eaux et en ce que cet algorithme traite les régions temporelles d'intérêt comme des régions abouties. Selon une mise en oeuvre particulière, le procédé est caractérisé en ce qu'une région temporelle est classée d'intérêt en fonction de données prédéterminées relatives à la séquence, telles que prise de vue. Selon une mise en oeuvre particulière, le procédé est caractérisé en ce qu'une région temporelle est déclarée d'intérêt si un mouvement associé à la région est non conforme au mouvement dominant dans l'image. Selon une mise en oeuvre particulière, le procédé est caractérisé en ce que, pour le classement en région temporelles d'intérêt, il met en oeuvre les étapes suivantes: - calcul d'un taux de décorrélation entre deux images successives, - si le taux de décorrélation est inférieur à un seuil, une région temporelle est déclarée d'intérêt si un mouvement associé à la région est 30 non conforme au mouvement dominant dans l'image. Selon une mise en oeuvre particulière, le procédé est caractérisé en ce que, pour le classement en région temporelles d'intérêt, il met en oeuvre les étapes suivantes: - calcul d'un taux de décorrélation entre deux images successives, - si le taux de décorrélation est supérieur à un seuil, détermination des régions temporelles ayant un mouvement conforme au mouvement dominant dans l'image pour former un premier ensemble, les autres régions temporelles formant un deuxième ensemble, calcul du centre de gravité de chacun des ensembles pour choisir comme régions d'intérêt, l'ensemble des régions ayant le centre de gravité le plus proche du centre de l'image. Selon une mise en oeuvre particulière, le procédé est caractérisé en ce qu'un filtrage morphologique est effectué avant la construction de régions spatiales. Selon une mise en oeuvre particulière, un paramètre temporel io est déduit du champ de vecteurs mouvement filtré. La solution proposée consiste à utiliser l'information de mouvement en amont de la segmentation morphologique spatiale. L'invention a pour principal avantage d'améliorer la partition finale et de permettre une meilleure estimation des formes sémantiques des objets en mouvement. Ces formes sémantiques sont préservées, au moins pour ceux ayant une caractéristique importante au niveau perceptuel. D'autres particularités et avantages de l'invention apparaîtront clairement dans la description suivante donnée à titre d'exemple non limitatif, et faite en regard des figures annexées qui représentent: - la figure 1, un algorithme de segmentation morphologique spatio-temporelle selon l'art antérieur, - la figure 2, un algorithme de segmentation morphologique spatiale selon l'art antérieur, - la figure 3, un algorithme de segmentation selon l'invention, - la figure 4, une segmentation de séquence d'images en plans, La figure 3 décrit un algorithme de segmentation morphologique spatio-temporelle selon l'invention. Une image courante I(t) est traitée aux étapes référencées 8 et 9 qui effectuent successivement des opérations de simplification et d'extraction de marqueurs spatiaux correspondant respectivement à celles décrites précédemment aux étapes 5 et 6 de la segmentation spatiale. La construction de régions spatiales se fait à partir d'un ou plusieurs paramètres spatiaux caractéristiques du contenu de l'image, par exemple la luminance et/ou la chrominance des pixels de l'image. La fonction de marquage, le critère d'homogénéité, est par exemple la plus petite distance de luminance. L'image courante I(t) et une image suivante I(t+nT) sont traitées à l'étape 10 qui effectue une estimation de mouvement entre ces images pour fournir un champ de vecteurs mouvement. Cette estimation de mouvement peut être obtenue par exemple par un estimateur de mouvement de type block matching ou de type pel recursif . D'autres méthodes d'estimation peuvent être exploitées. L'étape suivante 11 réalise une simplification, par filtrage, de ce champ de vecteurs mouvement. io L'étape 12 qui suit effectue une extraction de régions temporelles, à partir d'un ou plusieurs paramètres temporels relatifs au mouvement, pour obtenir des régions homogènes en mouvement. Ces régions sont par exemple construites par absorption de pixels, initialement autour de marqueurs germes, et fonction de la différence dans les informations de mouvement provenant des vecteurs mouvement du champ de mouvement attribués aux pixels. L'étape suivante 13 consiste en une détermination des marqueurs temporels d'intérêt, c'est à dire des régions temporelles d'intérêt. Cette étape, qui définit des classes d'intérêt, est importante, car les opérations de fusion/scission des régions sont effectuées à partir de ce critère d'intérêt. Dans notre exemple, l'étape 13 détermine 2 classes, une première classe regroupant les zones ou régions subissant le mouvement dominant et une deuxième classe regroupant les zones ne subissant pas le mouvement dominant. Ce type de dissociation est par exemple effectué via une binarisation d'histogramme. Une première méthode simple, pour le calcul de l'histogramme, consiste à effectuer une binarisation sur le module du vecteur mouvement, il s'agit d'un histogramme à une dimension, ou bien sur la valeur de chacune des composantes dx et dy des vecteurs de mouvement, il s'agit d'un histogramme à deux dimensions. Une autre méthode plus robuste consiste à estimer les paramètres affines du mouvement dominant présent dans la séquence vidéo. Les pixels conformes au modèle affine obtenus sont alors classés comme subissant le mouvement dominant. Les autres, ceux qui ne sont pas conformes au modèle, sont classés, quant à eux, comme ne subissant pas le mouvement dominant. Les régions sont numérotées afin de les différencier, un label est attribué à chaque région. Les régions temporelles sont classifiées, celles appartenant à la classe d'intérêt sont appelées marqueurs temporels d'intérêt. Les labels des régions temporelles d'intérêt sont appelés labels temporels d'intérêt. La détermination de la classe d'intérêt peut se faire de 2 façons: - de façon implicite: on dispose, avant même d'effectuer le procédé de segmentation, de suffisamment d'informations a priori pour io déterminer la classe d'intérêt, par exemple via des méta-données concernant la prise de vue de la caméra ou bien via la simple connaissance de la séquence à traiter. - de façon explicite: on ne dispose d'aucune information a priori sur la séquence à traiter. La classe d'intérêt est déterminée via des critères temporels. A titre d'exemple, on peut calculer la décorrélation inter images afin de classifier la séquence, par exemple selon des plans avec mouvement ou fixes. La valeur de décorrélation permet de mesurer le degré de dissimilitude de 2 images successives. Pour des plans vidéo stationnaires, la valeur issue de décorrélation est quasi nulle. A l'opposé, en présence de forts mouvements, la valeur augmente fortement. Selon un mode de réalisation, la valeur de décorrélation decorr est calculée selon la formule suivante: decorr = I(i, j; t) I(i, j; t - 1) avec I(i, j;t) la valeur de luminance I d'un pixel de coordonnée (i, j) dans l'image relative à l'instant t. La figure 4 présente l'évolution temporelle d'une valeur de décorrélation inter images sur la totalité d'une séquence connue sous l'appellation foreman . L'axe des abscisses correspond à un numéro d'image dans la séquence, l'axe des ordonnées est proportionnel à un taux de décorrélation. La séquence est découpée en trois parties. Une première partie de la séquence, jusqu'à l'image 166 correspond à un plan quasi fixe sur la tête de foreman, une deuxième partie, à partir de l'image 167, correspond à un plan travelling, une troisième partie, jusqu'à l'image 300 correspond à un plan quasi fixe. L'hypothèse de base est que tout objet non conforme au mouvement dominant est d'intérêt. Ainsi, pour les images correspondant à un plan quasi fixe, les zones d'intérêt sont les objets mobiles et, pour les images correspondant à un travelling, les zones d'intérêt deviennent les objets fixes. Le calcul de la valeur de décorrélation permet de définir l'activité spatio-temporelle de la séquence: 1) decoor = 0, séquences fixes, 2) decoor faible, séquences en faible mouvement io 3) decoor forte, séquences en très fort mouvement. Il y a un risque de non validation de l'hypothèse en particulier lorsque les images sont peu corrélées. Si les tailles des zones non conformes et des zones conformes sont très proches, il y a alors risque d'ambiguïté. Ainsi, lorsque la valeur de décorrélation est supérieure à un seuil, un premier calcul consiste à déterminer les zones temporelles conformes au mouvement dominant dans l'image et celles non conformes à ce mouvement dominant. Un calcul du centre de gravité de chaque ensemble de régions est ensuite effectué : soit G1, l'ensemble des régions non conformes et G2, l'ensemble des régions conformes. L'ensemble des régions pour lequel le centre de gravité est le plus proche du centre de l'image est considéré comme regroupant les régions temporelles d'intérêt. On prend ici en compte une donnée de haut niveau constatant que les zones d'intérêt sont généralement centrées sur l'image. Afin de préserver les formes sémantiques des objets, une étape de fusion 14 des 2 cartes de marqueurs temporels et spatiaux, c'est à dire des régions temporelles et spatiales de l'image, est réalisée. La figure 5a représente une carte de marqueurs spatiaux pour une image de la séquence foreman . Sur cet exemple, l'image 5a montre le visage de foreman sur-segmenté spatialement, 8 régions homogènes suivant un critère spatial forment le visage de foreman , et en outre de nombreuses zones incertaines, les zones sombres sur l'image. La figure 5b représente une carte des marqueurs temporels associés. La fusion permet de regrouper ou de scinder des régions à partir de l'information issue des marqueurs temporels. Dans l'exemple, il s'agit uniquement de fusion. L'image 5c est le résultat de la fusion des marqueurs temporels et spatiaux. Les régions spatiales ou les zones incertaines qui appartiennent à une région marquée temporellement sont ici fusionnées. On retrouve, par conséquent, la forme sémantique du personnage foreman . L'idée générale est de réaliser une fusion ou une scission d'une région spatiale en fonction du degré de recouvrement de cette région spatiale avec la région temporelle d'intérêt. Plus il y a de pixels en commun, plus on favorise la fusion. Cette étape permet de préserver les zones d'intérêt d'une extension de fusion spatiale. Une description plus précise de l'algorithme de fusion de io marqueurs est donnée ci-dessous. Une première étape détermine les pixels de l'image ayant à la fois un label spatial et un label temporel d'intérêt. Une deuxième étape effectue un choix entre la fusion et la scission, en fonction du degré de recouvrement des régions. Pour tous les labels des marqueurs spatiaux ayant des points en commun avec des marqueurs temporels d'intérêt: - calcul du pourcentage a de pixels en commun en prenant comme référence la taille de la région spatiale concernée. Si, par exemple, une région Rs correspondant à un label d'un marqueur spatial chevauche une région Rt correspondant à un label d'un marqueur temporel d'intérêt, le pourcentage a correspond au nombre de pixels de la région Rs se trouvant dans la région Rt par rapport au nombre total de pixels de la région Rs. - calcul du pourcentage R de pixels en commun en prenant comme référence la taille de la région temporelle concernée. La valeur 13 correspond, dans notre exemple, au nombre de pixels de la région Rs se trouvant également dans la région Rt par rapport au nombre total de pixels de la région Rt. Si a est supérieur à un seuil S, alors la région spatiale est fusionnée à la région temporelle. La région spatiale et son label sont supprimés. Par exemple, si la région spatiale appartient complètement à la région temporelle d'intérêt, la fusion est effectuée et la région spatiale disparaît. Dans l'autre cas, tous les pixels communs aux deux marqueurs sont associés au label marqueur temporel considéré. La région spatiale et son label ne sont pas supprimés. Si R est supérieur à un seuil T, alors la région spatiale est scindée en deux en fonction du marqueur temporel. Une région spatiale et un label sont ajoutés. Il n'y a pas de fusion avec la région temporelle. A titre d'exemple, des valeurs de seuil peuvent être 55% pour S et 80% pour T. L'étape suivante, référencée 15 effectue la gestion des points incertains contenus dans la carte de marqueurs spatiaux. Un point incertain est un pixel de l'image qui n'a pu être agrégé à une région spatiale. io Dans le cas où un point incertain se trouve dans une région temporelle, il est inclus dans cette région. Tous les points incertains se trouvant dans une région temporelle sont affectés à cette région temporelle. Pour les autres points incertains, l'étape met en oeuvre un algorithme de ligne de partage des eaux modifié. La décision watershed est dite modifiée car elle tient compte d'une zone privilégiée, définie par les marqueurs temporels d'intérêt, à ne plus modifier. L'étape de décision consiste à affecter un label aux pixels dits incertains et en dehors des régions temporelles. Cette décision s'effectue en prenant en compte une contrainte supplémentaire qui est le type de marqueurs de la région d'absorption: - s'il s'agit de marqueurs spatiaux, l'affectation de ce label se fait en fonction d'une métrique particulière, par exemple la différence suivant une certaine composante, luminance, texture..., entre le pixel incertain et la région qui pourrait potentiellement absorber ce pixel. Différents types de marqueurs spatiaux peuvent être utilisés, couleur, texture, mouvement... Par exemple, la liste de pixels adjacents à une région spatiale est établie. Un classement de ces pixels est effectué en fonction du paramètre choisi, par exemple en fonction de la différence entre la luminance du point et la luminance moyenne de la région considérée. Le pixel ayant la plus faible différence est fusionné avec la région, créant ainsi une région modifiée avec une nouvelle liste de pixels adjacents et ainsi de suite. - s'il s'agit de marqueurs temporels d'intérêt, ils ne sont soumis à aucune règle particulière d'absorption. Les régions labellisées par ce type de marqueurs sont, dans notre cas, considérées comme des régions abouties au sens sémantique du terme et elles ne peuvent pas croître par absorption de pixels incertains. Ce type de marqueurs agit comme un masque sur l'image. Les applications potentielles de l'invention concernent les codeurs de deuxième génération effectuant un codage par régions d'intérêt, codées plus fidèlement que les autres régions. Elles concernent également l'analyse d'image, l'analyse du contenu d'une scène vidéo, la recherche dans une base de données... 12 REVENDICATIONS 1 Procédé de segmentation spatio-temporelle d'une image vidéo d'une séquence d'images réalisant une estimation de mouvement (2, 10) entre une image courante et une image précédente pour déterminer un mouvement dans l'image courante, comportant les étapes suivantes: - construction de régions spatiales (6, 9) à partir d'un ou plusieurs paramètres spatiaux caractéristiques du contenu de l'image, io courante, - construction de régions temporelles (12) à partir d'un ou plusieurs paramètres temporels relatifs au mouvement dans l'image courante, caractérisé en ce qu'il comporte également les étapes suivantes: - classement de régions temporelles (13) en régions d'intérêt, - sélection (14) d'une région spatiale ayant des pixels en commun avec une région temporelle d'intérêt, - calcul d'un premier pourcentage (14) de pixels de la région spatiale qui sont communs avec la région temporelle d'intérêt, - calcul d'un deuxième pourcentage (14) de pixels de la région temporelle d'intérêt qui sont communs avec la région spatiale, - fusion ou scission (14) de la région spatiale en fonction de ces pourcentages. 2 Procédé selon la revendication 1, caractérisé en ce qu'une fusion (14) de la région spatiale commune à la région temporelle est réalisée, fusion avec la région temporelle, si le premier pourcentage est supérieur à un seuil et en ce qu'une scission (14) de la région spatiale commune à la région temporelle est réalisée, scission dans la région spatiale, si le deuxième pourcentage est supérieur à un seuil. 3 Procédé selon la revendication 1, caractérisé en ce qu'il comporte une étape de traitement de points incertains (15), c'est à dire non affectés à une région lors de leur construction, exploitant un algorithme de partage des eaux et en ce que cet algorithme traite les régions temporelles d'intérêt comme des régions abouties. lo 4 Procédé selon la revendication 1, caractérisé en ce qu'une région temporelle est classée d'intérêt en fonction de données prédéterminées relatives à la séquence, telles que prise de vue. Procédé selon la revendication 1, caractérisé en ce qu'une région temporelle est déclarée d'intérêt si un mouvement associé à la région est non conforme au mouvement dominant dans l'image. 6 Procédé selon la revendication 1, caractérisé en ce que, pour le classement en région temporelles d'intérêt, il met en oeuvre les étapes suivantes: - calcul d'un taux de décorrélation entre deux images successives, - si le taux de décorrélation est inférieur à un seuil, une région temporelle est déclarée d'intérêt si un mouvement associé à la région est non conforme au mouvement dominant dans l'image. 7 Procédé selon la revendication 1, caractérisé en ce que, pour 20 le classement en région temporelles d'intérêt, il met en oeuvre les étapes suivantes: - calcul d'un taux de décorrélation entre deux images successives, - si le taux de décorrélation est supérieur à un seuil, détermination des régions temporelles ayant un mouvement conforme au mouvement dominant dans l'image pour former un premier ensemble, les autres régions temporelles formant un deuxième ensemble, calcul du centre de gravité de chacun des ensembles pour choisir comme régions d'intérêt, l'ensemble des régions ayant le centre de gravité le plus proche du centre de l'image. 8 Procédé selon la revendication 6 ou 7, caractérisé en ce que le calcul du taux de décorrélation est effectué selon l'équation decorr = I(i, j; t) I(i, j; t -1) avec I(i, j;t) la valeur de luminance I d'un pixel de coordonnée (i, j) dans l'image relative à l'instant t. 9 Procédé selon la revendication 1, caractérisé en ce qu'un filtrage morphologique (8) est effectué avant la construction de régions spatiales. Procédé selon la revendication 1, caractérisé en ce qu'un paramètre temporel est déduit du champ de vecteurs mouvement filtré (11). i0