FR 2845179 A1 20040402 FR 0211952 A 20020927 L'invention concerne un procédé et un dispositif de regroupement d'images clés par utilisation d'attributs spatiaux-temporels. Le regroupement, plus connu sous l'appellation anglaise de " clustering ", a pour but de grouper des données en exploitant des mesures de distances ou similarités entre celles-ci, des données faiblement distantes étant regroupées au sein d'une même classe. Une application relative aux 10 données vidéo numériques concerne la construction automatique de résumés vidéo. La figure 1 représente un schéma général d'un procédé de construction d'un résumé vidéo d'une séquence d'images. Dans une première étape 1, la séquence vidéo est découpée en plans vidéo. Une deuxième étape 2 extrait des images caractéristiques ou images clés des différents plans de la séquence. Pour chaque image clé, c'est l'étape 3, une signature est calculée, par exemple à partir d'attributs de l'image tels que la couleur, la structure.... L'étape suivante 4 a pour but de 20 regrouper les différents plans qui se ressemblent en groupes de plans ou " clusters ". Une mesure de similarité est ainsi effectuée, à partir d'un calcul quelconque de distances entre les signatures des images clés associées à chaque plan. L'étape suivante 5 fabrique le résumé en extrayant une image clé par groupe de plans. Ce procédé permet de réduire le nombre de plans caractéristiques, par exemple lors de séquences vidéo avec plans alternés, pour créer des résumés vidéo, des index Une approche connue s'attaquant aux problèmes de regroupement 30 de plans pour la construction de résumés vidéo est celle proposée par Yeung et Yeo dans le document "Segmentation of video by clustering and graph analysis", Computer Vision and Image Understanding, vol 71, no 1, July, pp 94-109, 1998. A chaque couple de plans est associée une distance qui est une mesure sur les différences entre signatures. Outre la distance entre 35 signatures, la méthode proposée s'attache à ne pas rassembler de plans dont la distance temporelle est supérieure à un seuil temporel T. L'idée sous- jacente repose sur l'hypothèse que des plans appartenant à une même unité sémantique ne peuvent être très distants. Cette hypothèse présente également l'avantage de limiter le nombre de regroupements potentiels et ainsi de limiter le cot calculatoire. L'algorithme de regroupement utilisé 5 fonctionne sur des regroupements successifs de plans en commençant par les plus semblables jusqu'à ce que les distances soient toutes supérieures à un seuil. Dans cette méthode, si deux plans sont séparés de plus de T images, le regroupement n'est pas possible. Dans l'article cité, T est fixé à 10 une valeur de l'ordre de quelques milliers d'images. Le problème principal de cette méthode réside dans le fait que ce seuil est fixe, qu'il a une incidence importante sur le résultat final et qu'il est de ce fait difficile à fixer a priori. Par exemple, si une scène de dialogue dure plus de 3000 images et si cette valeur dépasse le seuil temporel, un surdécoupage a lieu. Tous les plans 15 ainsi regroupés doivent être proches deux à deux à la fois visuellement et temporellement. La taille des groupes ainsi générés est de ce fait relativement limitée. Le résultat final de cet algorithme de clustering se caractérise par l'obtention de groupes relativement uniformes en nombre de plans, ce nombre étant généralement faible et de toutes façons limité par la 20 valeur du seuil T. L'invention a pour but de pallier les inconvénients précités. Elle a pour objet un procédé de regroupement d'images d'une séquence vidéo constituée de plans et représentée par une structure en graphe, un noeud du 25 graphe représentant un plan ou une classe de plans définie par des images clés et les noeuds étant reliés par des arêtes, caractérisé en ce qu'il comporte l'itération suivante: sélection d'une arête ak reliant les noeuds ni et nj - calcul du potentiel du noeud nm, fusion des deux noeuds ni et nj, en 30 fonction des distances entre les attributs des images clés définissant la classe de plans du noeud ni et ceux des images clés définissant la classe de plans du noeud nj et en fonction de la distance temporelle de ces images clés, - calcul du potentiel de chaque arête reliant le noeud fusionné nm à un 35 autre noeud du graphe précédemment relié au noeud ni ou nj, en fonction des distances entre les attributs des images clés définissant la classe de plans du noeud fusionné et ceux des images clés définissant la classe de plans de l'autre noeud et en fonction de la distance temporelle entre ces images clés, la nouvelle classe de plans associée au noeud fusionné comprenant les images clés des classes de plans des noeuds fusionnés, fusion des deux noeuds et validation du nouveau graphe si l'énergie de ce graphe, qui est la somme des potentiels des noeuds et des arêtes, est inférieure à l'énergie du graphe avant la fusion. Selon une mise en oeuvre particulière de l'invention, le graphe est initialisé en affectant un noeud à chaque plan et en créant des arêtes d'un 10 noeud à un autre noeud si les plans relatifs à ces noeuds sont séparés d'un nombre maximal prédéterminé T de plans. Selon une mise en oeuvre particulière de l'invention, la valeur de potentiel associé aux arêtes et aux noeuds est une fonction respectivement décroissante et croissante de la distance temporelle. 15 Le calcul de similarité des images prend en compte la distance entre signatures, par exemple la différence entre histogrammes, et la distance temporelle entre images clés définissant les plans. Cette contrainte temporelle est adaptative, deux plans trop éloignés initialement pour être 20 regroupés pouvant se retrouver potentiellement " regroupables " en cas de fusion de plans intermédiaires. L'algorithme de calcul est basé sur une minimisation énergétique par fusion s'appuyant sur une structure de graphe. Contrairement à la méthode précédente, pour appartenir à un groupe d'images, aussi appelé par la suite 25 classe d'images ou classe de plans, une image candidate doit être proche visuellement et temporellement d'au moins une image du groupe. Un avantage de l'invention est la prise en compte des images même éloignées temporellement, du fait de la fusion, tout en favorisant le regroupement d'images temporellement proches. Un autre avantage réside dans le fait que seule une image d'un groupe doit être similaire à l'image candidate pour autoriser la fusion. Les groupes ainsi créés peuvent comporter plus d'éléments que dans le cas de la méthode classique. Le schéma proposé permet de générer des groupes plus hétérogènes, moins dépendants de valeurs de seuils donc plus proches des 35 données, sans pour autant rendre les calculs trop complexes ou trop longs. 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 schéma général de la construction de résumés vidéo, - la figure 2a, un exemple de graphe initial, - la figure 2b, le résultat de ce graphe après une itération, - la figure 3 un organigramme de minimisation de l'énergie du graphe. La méthode proposée s'appuie sur une structure de graphe. Un graphe est constitué d'un ensemble de noeuds et d'arêtes. Un noeud ni symbolise un plan ou groupe de plans vidéo similaires suivant la distance visuelle et temporelle choisie, chaque plan Pi étant représenté par au moins une image clé. Les arêtes relient les noeuds entre eux, deux noeuds non 15 reliés par une arête n'étant pas potentiellement fusionnables. Une taille de fenêtre temporelle T est choisie. Elle est donnée en nombre maximal de plans T séparant deux plans dans la séquence vidéo. Lors de l'initialisation du graphe, des arêtes sont créées à partir d'un noeud donné correspondant à un plan donné vers chacun des noeuds dont les 20 plans se trouvent dans la fenêtre temporelle de ce plan donné. D'une manière pratique, les noeuds sont d'abord reliés par des arêtes selon le déroulement séquentiel de la séquence vidéo. Ce cheminement est ensuite pris en compte, lors de l'adjonction des arêtes complémentaires, pour l'application de la fenêtre temporelle. Alors, la valeur 25 entière T choisie pour cette étape d'initialisation du graphe signifie que seuls les noeuds séparés au maximum de T noeuds du noeud considéré sont pris en compte pour le calcul des arêtes initiales partant de ce noeud. Une arête initiale aqj n'est créée entre le noeud ni et le noeud nj que si la distance temporelle dT séparant ces noeuds auxquels sont associés les plans Pi et Pj 30 est inférieure à un seuil T. Cette contrainte n'est effective qu'à l'initialisation du graphe, les fusions ultérieures de noeuds permettant de relier des noeuds beaucoup plus éloignés à l'origine, si nécessaire. Le choix de ce seuil à l'initialisation est fait dans un but d'optimisation du temps de calcul très dépendant du nombre d'arêtes. L'initialisation du graphe est effectuée en créant un noeud par plan vidéo. La figure 2a représente un graphe initial constitué d'un ensemble de 6 plans vidéo symbolisés par les noeuds 1 à 6. Dans l'exemple de la figure 2a, à titre d'illustration simplifiée, le seuil temporel ou fenêtre temporelle à l'initialisation est fixé à T=1. Le seuil est en réalité choisi égal à 6 dans notre implémentation. Dans l'exemple donc, les arêtes sont créées entre un noeud 5 et les noeuds séparés de ce noeud d'un plan au maximum. La figure 2b, qui correspond à la fusion des noeuds 2 et 4 pour donner le noeud 7 montre cependant que, dés la première itération, les noeuds 6 et 7, reliés par des arêtes, sont en dehors de la fenêtre temporelle. L'énergie du système est égale à la somme des potentiels des arêtes 10 et des noeuds. Le but est de regrouper ou fusionner les noeuds de manière à diminuer l'énergie globale du système. Pour définir l'énergie globale du système, la notion de potentiel V, de noeud et Va d'arête est introduite. Un potentiel est calculé à partir d'une distance de base entre deux images Ii et Ij, distance temporelle et distance 15 entre attributs. La valeur du potentiel associé à une arête au est définie à l'aide d'une fonction décroissante de la distance. Plus les distances temporelles et les distances entre attributs sont importantes, plus le potentiel est faible. L'objectif global de l'algorithme étant de minimiser l'énergie globale du 20 système, plus les plans attachés à deux noeuds seront proches selon les distances précédemment définies, plus les potentiels des arêtes seront élevés et plus la fusion et donc l'élimination des arêtes sera favorisée. La valeur du potentiel associé au noeud nk est définie à partir d'une fonction croissante de la distance. Plus les distances temporelles ou les 25 distances entre attributs calculées entre les images appartenant à deux noeuds distincts sont faibles, plus le potentiel associé au noeud fusion est faible, donc plus le système sera enclin à fusionner les deux noeuds pour créer un noeud de faible potentiel. Soient Va(ninj) et Vn(nm) respectivement les potentiels d'une arête 30 reliant les noeuds ni et nj et d'un noeud nm Nous décrivons dans un premier temps le potentiel lié aux arêtes. On calcule ici les potentiels " inter-images " de l'arête pour chacun des couples formés d'une image parmi les images associées à un noeud extrémité de l'arête et d'une image parmi les images associées à un noeud autre extrémité 35 de l'arête. Il s'agit, en d'autres termes, des potentiels calculés à partir des distances croisées entre les images associées au premier noeud et celles associées au deuxième noeud aux extrémités de l'arête. Le potentiel Va(nbnj) d'une arête s'écrit alors en fonction des distances croisées entre les images Ik appartenant à ni et les images Il appartenant à nj. La valeur minimale suivante est calculée: Va (ni,nj) = min (Watt Fa(Katt,datt,datt(Ik,I1)) + wT Fa(KT,dT,dT(Ik,I1))) Va (ni'jikePi,iirPj o: Pm représente l'ensemble des images associé au noeud nm Fa est une fonction décroissante watt et WT représentent les poids liés aux attributs et au temps (dans notre implémentation, watt=3 et WT=) datt(Ik,I,) est la fonction distance associée aux attributs 15 caractéristiques des deux images datt représente la moyenne des distances entre images calculées sur le graphe initial d(Ik, Il) est la distance temporelle séparant les deux images dT est égal à T, T représentant le seuil temporel 20 KattetKr sont deux constantes L'ensemble des images associé au noeud nm est également appelé classe de plans associée au noeud nim. Cette classe regroupe l'ensemble des images des classes de plans fusionnés. La distance entre attributs peut être prise comme une différence classe à classe entre histogrammes caractérisant chaque image. La distance temporelle est quant à elle définie comme le nombre de plans séparant les deux plans auxquels appartiennent les images Ik et Il. Dans l'implémentation, la fonction décroissante Fa est de la forme 30 suivante Fa (K, d, d) K K(d-d) l+ed Des valeurs de potentiel sont également calculées pour les noeuds du graphe. Lorsque deux noeuds ni et nj correspondant aux images-clé Ii et Ij appartenant respectivement aux classes de plan Pi et Pj sont fusionnés pour créer un nouveau noeud nk, les images Ji et Ij sont intégrées dans la nouvelle 5 classe de plans Pk associée au noeud nk. Le nombre d'images associées augmente ainsi au fur et à mesure des fusions. D'une manière générale, le nombre d'images associées à un nouveau noeud correspond à la somme des images associées aux noeuds fusionnés générant le nouveau noeud. Le potentiel d'un noeud fusion d'un premier et deuxième noeud est 10 obtenu à partir des potentiels calculés sur l'ensemble des couples d'images formés d'une image associée au premier noeud et d'une image associée au second noeud. Cette valeur est fonction de la distance entre attributs datt et de la distance temporelle dT. Il y a autant de potentiels calculés qu'il y a de couples d'images. La valeur choisie est celle qui donne le potentiel minimum. 15 Le potentiel Vn(nm) d'un noeud issu de la fusion de deux noeuds ni et nj existants est donc défini par la fonction suivante: J/%(n. =n yn)= min (watt * Fn (Katt, datt" dat (Ik' Il)) + WT Fn (KT, d T (Ik Il))) Le potentiel d'un noeud fusion est donc calculé à partir des distances 20 croisées entre les images appartenant à chacun des noeuds candidats à la fusion. Dans l'implémentation, la fonction croissante Fn est de la forme suivante Fn (K, d, d) 1- K =Fa (K, d, d) (d-d) 1+e d A l'initialisation du graphe, le potentiel des noeuds est nul. Il y a une image clé par noeud. C'est au cours du processus de fusion que ce potentiel prend une valeur strictement positive. Le facteur K utilisé dans les fonctions Fa et F, est un paramètre qui 30 influence la courbure de la fonction. Plus K est important, plus la fonction tend vers 0 ou vers 1 rapidement quand on s'éloigne de la valeur moyenne d. En terme de potentiel, plus K est important, plus les variations de d autour de la valeur moyenne entraînent des variations importantes du potentiel. Dans le cas de la fonction attachée à la distance entre attributs, Kait peut être pris égal à 2. Dans le cas de la fonction attachée à la distance temporelle, KT peut être pris égal à 7. Lors du calcul d'un potentiel relatif à un couple d'images (I', Ij), plus 5 les images traitées sont éloignées, temporellement ou selon leurs attributs, plus le potentiel de l'arête correspondant à ces deux images est faible, plus le potentiel du noeud correspondant au couple d'images fusionné est fort. La contrainte temporelle apparaît donc sous deux formes dans notre 10 algorithme: - par l'existence o non d'une arête entre deux noeuds, cette existence étant initialement liée à la distance temporelle séparant deux plans - par l'influence de la distance temporelle séparant deux images sur 15 la valeur du potentiel associé aux arêtes ou aux noeuds L'énergie globale du système est égale à la somme des potentiels associés à chaque arête et à chaque noeud. Un processus itératif de fusions est mis en oeuvre pour obtenir une 20 configuration du système ayant l'énergie globale la plus faible possible. Le but de chaque itération est de faire décroître l'énergie globale. Le calcul de l'énergie minimale nécessiterait d'essayer toutes les combinaisons possibles. Ce nombre pouvant être considérable, en fonction du nombre de plans, le schéma de minimisation énergétique choisi est un schéma sous-optimal. Il 25 ne garantit pas que la solution trouvée corresponde à la configuration minimisant l'énergie totale du système. Il présente cependant l'intérêt d'être rapide tout en fournissant une solution énergétique acceptable. Plus la distance entre deux images est faible, plus le potentiel de 30 l'arête relatif à ces deux images est fort donc plus le potentiel de l'arête reliant les noeuds correspondants est élevé. On cherche à diminuer l'énergie globale du système donc à éliminer les arêtes de plus fort potentiel, ce qui revient à éliminer le potentiel relatif à ces arêtes, les potentiels des arêtes sortant des noeuds fusionnés étant recalculés. Ce qui correspond bien à 35 vouloir regrouper les images les plus proches, aussi bien du point de vue attributs que du point de vue temporel. Le potentiel d'un noeud obtenu après fusion des deux noeuds aux extrémités de l'arête supprimée est recalculé. Plus les distances entre les images associées aux noeuds à fusionner sont grandes, plus les potentiels du noeud fusionné relatifs aux couples d'images sont importants, plus le 5 potentiel de ce noeud qui est la valeur minimum parmi ces potentiels est important. Dans l'exemple de la figure 2b, les noeuds 2 et 4 sont fusionnés pour donner le noeud 7. Les images clé des noeuds 2 et 4 sont donc maintenant 10 associées au noeud 7. Le potentiel du noeud 7 est calculée ainsi que les potentiels des nouvelles arêtes partant de ce noeud, définissant ainsi la nouvelle configuration. Le processus itératif de réduction d'énergie mis en oeuvre est décrit à 15 la figure 3. La première étape référencée 6 vérifie si toutes les arêtes du graphe ont été testées. Dans l'affirmative, les itérations sont terminées et les plans ou images clés se trouvent regroupées en classes de plans, créées au fur et à 20 mesure des fusions des noeuds du graphe. Dans la négative, l'étape suivante est l'étape 7 qui prend en compte une arête ak non testée du graphe dont les extrémités sont les noeuds que l'on appellera ni et nj. Les arêtes sont par exemple sélectionnées en fonction de leur valeur énergétique dans l'ordre décroissant des valeurs du potentiel 25 associé. En effet une arête de fort potentiel supprimée entraîne a priori une baisse énergétique importante. L'étape suivante 8 effectue un calcul de l'énergie du graphe en supposant une fusion des noeuds ni et nj. En plus du potentiel du noeud fusionné, le potentiel des nouvelles arêtes reliant le nouveau noeud à 30 l'ensemble des noeuds adjacents aux noeuds ni et nj est pris en compte pour le calcul de l'énergie du nouveau graphe. Si l'énergie trouvée est supérieure à l'énergie avant fusion, test effectué à l'étape 9, on retourne à l'étape 6 puis à l'étape 7 pour traiter l'arête suivante, dans le cas ou toutes les arêtes n'ont pas été testées. Dans le cas o l'énergie calculée est inférieure à l'énergie du graphe avant fusion, l'étape suivante est l'étape 10 qui valide la fusion des noeuds ni et nj1 et le nouveau graphe qui en découle. L'étape suivante 6 vérifie si toutes les arêtes ont été testées. Il s'agit 5 des arêtes non modifiées par la fusion des noeuds mais également des nouvelles arêtes calculées lors de cette fusion. Dans l'affirmative, le graphe final est celui validé à l'étape précédentesO. Une simplification consiste à utiliser un critère d'arrêt sous optimal permettant d'éviter le parcours exhaustif des arêtes. Cette simplification 10 consiste en l'arrêt de la minimisation dès que la fusion potentielle de deux noeuds entraîne une augmentation de l'énergie. Cette simplification est rendue acceptable par la sélection intelligente des arêtes dans l'ordre décroissant de leur valeur de potentiel. Le schéma présenté est globalement sous-optimal du fait du 15 caractère non réversible de la fusion. Le passage à une minimisation de l'énergie optimale peut être envisagé moyennant un cot calculatoire élevé. Le choix de la fonction d'énergie et des potentiels que nous venons de définir nous permet de simplifier le schéma de minimisation énergétique. 20 En effet, le fait de choisir le minimum des potentiels fait que si le potentiel associé à un noeud provenant de la fusion de deux noeuds est inférieur à la somme des potentiels de ces deux noeuds alors la fusion des deux noeuds entraîne nécessairement une baisse du potentiel des arêtes voisines. On peut donc se contenter d'une étude locale de la variation d'énergie, tout en 25 assurant une baisse globale de cette énergie. Le procédé décrit permet d'obtenir un processus de fusion performant malgré la limitation calculatoire. Celle-ci concerne les possibilités d'appariements initiaux limitées, le nombre d'arêtes étant limité à l'initialisation. Elle concerne également l'exploitation d'une fenêtre réduite à l'initialisation. Cependant, du fait du processus de fusion, des plans éloignés peuvent être regroupés. Les potentiels prennent en compte les distances temporelles et entre attributs. Ils autorisent des fusions si les images clés, bien que distantes, sont très ressemblantes ou bien, si les images clés bien 35 que moyennement ressemblantes, sont très proches temporellement. REVENDICATIONS 1 Procédé de regroupement d'images (4) d'une séquence vidéo constituée de plans et représentée par une structure en graphe, un noeud du graphe représentant un plan ou une classe de plans définie par des images clés et les noeuds étant reliés par des arêtes, caractérisé en ce qu'il comporte l'itération suivante: 10 - sélection d'une arête ak (7) reliant les noeuds ni et nj - calcul du potentiel du noeud nm (8), fusion des deux noeuds ni et nj, en fonction des distances entre les attributs des images clés définissant la classe de plans du noeud ni et ceux des images clés définissant la classe de plans du noeud nj et en fonction de la distance 15 temporelle de ces images clés, - calcul du potentiel de chaque arête (8) reliant le noeud fusionné à un autre noeud du graphe précédemment relié aux noeuds ni ou nj, en fonction des distances entre les attributs des images clés définissant la classe de plans du noeud fusionné et ceux des images clés 20 définissant la classe de plans de l'autre noeud et en fonction de la distance temporelle entre ces images clés, la nouvelle classe de plans associée au noeud fusionné comprenant les images clés des classes de plans des noeuds fusionnés, - fusion des deux noeuds et validation du nouveau graphe (10) si 25 l'énergie de ce graphe, qui est la somme des potentiels des noeuds et des arêtes, est inférieure à l'énergie du graphe avant la fusion (9). 2 Procédé selon la revendication 1, caractérisé en ce que le graphe 30 est initialisé en affectant un noeud à chaque plan et en ce que des arêtes sont créées d'un noeud à un autre noeud si les plans relatifs à ces noeuds sont séparés d'un nombre maximal prédéterminé T de plans. 3 Procédé selon la revendication 1, caractérisé en ce que la valeur de potentiel associé aux arêtes et aux noeuds est une fonction respectivement décroissante et croissante de la distance temporelle. 4 Procédé selon la revendication 2, caractérisé en ce que le potentiel d'une arête reliant deux noeuds ni et nj est calculé selon l'équation suivante: Va(ni,nj) min (Watt.Fa(Kaatt,dattdatt(Ik,I1))+wT.Fa(KT,dT,dT(Ik, I1))) Ik EPi,lIlEPj et en ce que le potentiel d'un noeud né de la fusion de deux noeuds ni et nj est défini par la fonction suivante: VI (nm =ni U nj)= min (Watt * Fn(Kaa datdat (,(I"I))+ WT F,(KrTdrT,dr(IkI,))) lk Pi,Ij P1 o: Pi représente la classe de plans associée au noeud n, et comportant les images /k Fa est une fonction décroissante Fn est une fonction croissante watt et WTreprésentent les poids liés aux attributs et au temps datt(IbIl) est la fonction distance associée aux attributs caractéristiques des deux images dattreprésente la moyenne des distances entre images calculées sur le graphe initial dr(Ik,,I1) est la distance temporelle séparant les deux images dT est égal à T qui représente le seuil temporel Katt et KT sont deux constantes Procédé selon la revendication 4, caractérisé en ce que la fonction 30 décroissante est de la forme Fa (K, d, d) K K(d-d) l+ed et en ce que la fonction croissante est de la forme Fn(K,d,d)=1 K K (d-d) l+ed 6 Procédé selon la revendication 1, caractérisé en ce que les 5 itérations sont arrêtées dés que la fusion potentielle de deux noeuds (8) entraîne une augmentation de l'énergie (9), les arêtes étant sélectionnées (6), pour le calcul des fusions, dans l'ordre décroissant de leur valeur de potentiel.