FR 2846502 A1 20040430 FR 0213978 A 20021028 L'invention concerne un procédé de sélection de germes pour le regroupement d'images clés d'une séquence vidéo ainsi que le procédé de regroupement. Elle concerne également un procédé d'extraction automatique de plans d'intérêt dans une séquence vidéo. Le domaine est celui de la construction d'index pour la navigation interactive intra-vidéo ou celui de la structuration vidéo, c'est à dire l'ordonnancement des plans qui permet de définir une table des matières. Une séquence vidéo est composée de plans, chaque plan 10 correspondant à des ruptures de prise de vue, qui peuvent eux-mêmes être regroupés en scènes. La structuration implique une étape de classification des plans. Celle-ci n'est bien sr possible qu'à condition que le contenu de la vidéo soit structurable, par exemple dans des domaines tels que le sport, les journaux télévisés, les interviews... Usuellement, les classes sont préalablement définies par des méthodes d'apprentissage supervisées ou non, puis les plans candidats d'une vidéo sont attachés à l'une des classes, sur la base d'une mesure de similarité. La classification des plans est une étape fondamentale du processus de structuration de la vidéo. De nombreuses méthodes de classification et de représentation des plans sont proposées, mais peu s'attachent à l'identification de ces classes. Par exemple, dans un contexte de création de résumé vidéo, 25 l'article de S. Uchihashi, J. Foote, A. Girgensohn, J. Boreczsky intitulé "Vidéo Manga: Generating Semantically Meaningful Video Summaries ", Proc. ACM Multimedia, Orlando, FL, pp 383-392, November 1999, décrit une méthode de regroupement hiérarchique dans l'étape de structuration de la séquence. Le résultat est représenté sous la forme d'un arbre. A l'initialisation, chaque 30 image de la vidéo est assignée à une classe ou cluster. Puis les images similaires sont regroupées en fusionnant itérativement les 2 clusters les plus proches à chaque étape. A la racine, on trouve le cluster maximal contenant l'ensemble des images. Par la suite le nombre de clusters désiré est sélectionné en spécifiant la distance des clusters fusionnés à leur père. Par 35 cette méthode, les plans similaires sont regroupés, mais on ne trouve pas d'informations sur la nature des plans. En revanche pour la structuration de journaux télévisés, comme décrit dans l'article de H.J Zhang, S.Y. Tan, S.W. Smoliar, G. Yihong intitulé "Automatic parsing and indexing of news video", Multimedia Systems, 2(6) :256-265, 1995, on cherche à distinguer 2 types de plans: ceux qui se 5 rapportent au présentateur et ceux qui concernent les reportages. Les plans du présentateur sont identifiés à l'aide de caractéristiques spatiales: typiquement, une personne au premier plan et une incrustation en haut à droite ou à gauche. La première étape consiste à définir un modèle A de l'image représentative d'un plan du présentateur. A la deuxième étape, les 10 plans sont étiquetés comme appartenant à A ou non, à l'aide d'une mesure de similarité utilisant des descripteurs locaux, l'image-clé étant préalablement segmentée en régions. Dans cette méthode, on modélise d'abord un plan d'intérêt, puis on sélectionne tous les plans qui se rapprochent de ce modèle. Une autre application de la sélection des plans d'intérêt est 15 d'identifier les plans se rapportant à l'interviewé et ceux de l'interviewer dans une vidéo d'interview. Dans cette approche, par exemple décrite dans l'article de O. Javed, S. Khan, Z. Rasheed, M. Shah intitulé "A Framework for Segmentation of Interview Videos", IASTED Intl. Conf. Internet and Multimedia Systems and Applications, Las Vegas, November, 2000, on 20 s'intéresse plus à l'information portée par les transitions entre plans, couplée à la connaissance de la structure d'une vidéo d'interview, plans alternés de l'interviewer et de l'interviewé, qu'à l'analyse du contenu de la scène. Toutefois un algorithme de détection de peau est utilisé pour déterminer le nombre de personnes dans l'image. Les questions étant typiquement plus 25 courtes que les réponses, l'hypothèse utilisée est que les plans de l'interviewer sont parmi les plus courts. Les images-clés des N plus courts plans ne contenant qu'une personne sont corrélées pour trouver le plan le plus répétitif. On obtient ainsi une matrice NxN de corrélation dont on somme les lignes. L'image-clé correspondant à la somme maximale est alors 30 identifiée comme l'image-clé de l'interviewer. Elle est à nouveau corrélée avec toutes les autres images pour trouver tous les plans s'y rapportant. La figure 1 représente, de manière connue, un schéma général de la construction de résumés vidéo. Dans une première étape référencée 1, la 35 séquence d'images est découpée en plans, les plans correspondant à des ruptures de prise de vue. Pour chaque plan, une ou plusieurs images caractéristiques sont sélectionnées, il s'agit d'images-clés. C'est l'objet de l'étape 2. Pour chaque image-clé, une signature est calculée à l'étape 3, utilisant des descripteurs locaux ou attributs, par exemple la couleur, les contours, la texture.... L'étape 4 effectue une sélection de plans d'intérêt en 5 fonction de ces signatures ou attributs et un résumé est fabriqué à l'étape 5 à partir de ces plans d'intérêt. La nature des plans d'intérêt varie en fonction de l'application visée. Par exemple, pour les journaux télévisés, il peut s'agir du présentateur. Ces plans d'intérêt correspondent souvent aux plans 10 majoritaires, c'est à dire à une prise de vue dominante. En effet, dans certaines séquences, notamment sportives, les moments les plus intéressants sont caractérisés par une prise de vue commune et répétitive au cours de la séquence, par exemple lors d'un match de football, de tennis, de base- ball.... L'invention concerne plus particulièrement l'étape de sélection des plans d'intérêt. La méthode proposée s'appuie sur la signature de chaque image-clé, associée à une métrique, afin de déterminer de façon binaire l'appartenance ou non des plans à la classe des plans d'intérêt. Concernant le partitionnement ou " clustering ", il existe de nombreux algorithmes. Parmi les plus utilisés, on trouve le K-means basé sur le calcul du barycentre des attributs ou sa variante le K-medoid qui prend en compte le point physique, c'est à dire l'image la plus proche du barycentre, qui sont des algorithmes itératifs. A partir d'une partition initiale, le K-means 25 ou K-medoid regroupe les données en un nombre fixé de classes. Ce regroupement est très sensible à la partition initiale. D'autre part, il nécessite la fixation a priori du nombre de classes, c'est à dire une connaissance a priori du contenu de la vidéo. Dans le cas contraire, il ne garantit pas l'obtention d'un partitionnement optimal de la séquence vidéo traitée. 30 L'invention a pour but de pallier les inconvénients précités. Elle a pour objet un procédé de sélection de germes parmi un ensemble d'imagesclés d'une séquence vidéo pour le regroupement d'images-clés de plans majoritaires de la séquence vidéo, caractérisé en ce qu'il met en oeuvre les 35 étapes suivantes: - tirage aléatoire de p candidats dans l'ensemble d'images- clés, p étant calculé de manière à obtenir une très bonne probabilité de tirer une image-clé d'un plan majoritaire, - calcul du cot C pour chaque candidat, fonction de la distance 5 des images-clés de l'ensemble à celle du candidat, la distance étant relative aux signatures, - sélection du candidat (kl) minimisant le cot C, - détermination d'un sous-ensemble (1k) parmi l'ensemble d'images-clés tel que les images-clés formant le dit sous-ensemble ont une 10 distance au candidat inférieure à un seuil T, détermination d'un germe (k2) parmi les images-clés du sous-ensemble (1k) tel qu'il minimise la fonction de cot C pour ce sous-ensemble, suppression des images-clés du sous-ensemble (1k) pour former un nouvel ensemble d'images-clés pour au moins un nouveau tirage 15 aléatoire et détermination d'un nouveau germe selon les 5 étapes précédentes. Selon une mise en oeuvre particulière, le tirage aléatoire est du type Monte-Carlo, p étant calculé par la formule de Monte-Carlo. Selon une mise en oeuvre particulière, les images-clés sont 20 pondérées, quant à leur signature, en fonction de la longueur des plans de la séquence vidéo qu'elles caractérisent et le tirage aléatoire est biaisé par le poids des images-clés. L'invention concerne également un procédé de regroupement (clustering) de plans d'une séquence d'images vidéo, la séquence étant 25 découpée en plans, un plan étant représenté par une ou plusieurs imagesclés, au moins une signature ou attribut étant calculé pour les images-clés, comportant une phase de partitionnement des images-clés à partir d'une comparaison des attributs des images-clés, caractérisé en ce qu'il comporte une phase d'initialisation pour la sélection d'au moins deux images-clés ou 30 germes à partir desquelles sont effectuées les comparaisons pour le regroupement, la sélection étant effectuée selon le procédé de la revendication 1. Selon une mise en oeuvre particulière, le procédé est caractérisé en ce que les phases d'initialisation et de partitionnement sont réitérées, les 35 images-clés du cluster le plus compact obtenu à l'itération précédente étant éliminées de l'ensemble traité à cette itération précédente pour fournir un nouvel ensemble sur lequel est effectuée la nouvelle itération. L'invention concerne également un procédé de sélection de plans d'intérêt, ces plans étant majoritaires dans la séquence vidéo, caractérisé en 5 ce qu'il met en oeuvre le procédé décrit ci-dessus, les plans d'intérêt correspondant au regroupement effectué autour du premier germe sélectionné. Plus le nombre n de germes retenus pour initialiser l'algorithme de 10 clustering est important, plus les clusters sont compacts donc cohérents au sens de la métrique utilisée. Le nombre n de germes retenus pour initialiser l'algorithme est fixé mais le nombre de classes obtenues n'est pas connu a priori. Le procédé permet l'identification des plans majoritaires dans la 15 séquence. Lors de la première itération, le premier cluster obtenu représente ces plans majoritaires. Les itérations suivantes permettent d'affiner la classification et de diminuer le taux de mauvaises classifications. Il est ainsi possible de retrouver l'ensemble des plans se rapportant à une prise de vue majoritaire afin d'éliminer les séquences secondaires. Dans l'hypothèse o 20 ces plans majoritaires sont des plans d'intérêt, le procédé permet d'extraire automatiquement les plans d'intérêt de la séquence vidéo. D'autres particularités et avantages de l'invention apparaîtront clairement dans la description suivante donnée à titre d'exemple non limitatif 25 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 2, un algorithme de sélection de germes, - la figure 3, le résultat du clustering sur une séquence de tennis. 30 L'algorithme de traitement pour le partitionnement des images fonctionne en deux phases successives. La première consiste à sélectionner des plans candidats pour le regroupement, il s'agit de l'algorithme de sélection de germes. La deuxième phase a pour objet d'affecter chaque plan 35 à l'un des groupes représentés par les germes, il s'agit de l'algorithme de classification des plans proprement dit. La phase de sélection des germes s'appuie sur l'hypothèse des plans majoritaires et assure que lors de la première itération de l'algorithme de partitionnement, un plan correspondant à la prise de vue d'intérêt est sélectionné en premier. Les plans appartenant à la classe dite d'intérêt sont alors étiquetés " plans d'intérêt ", les autres " plans de non-intérêt ". La première phase consiste en une sélection des représentants des classes " intérêt " / " non intérêt ". L'hypothèse sur laquelle repose la sélection est que les plans 10 appartenant à la prise de vue que nous cherchons sont majoritaires en terme de nombre d'images dans l'ensemble de la séquence. Nous faisons l'hypothèse qu'au moins la moitié des images-clés représentant nos plans correspond bien au modèle cherché. Afin de donner plus d'importance aux plans longs et de satisfaire 15 l'hypothèse, un coefficient représentatif de l'importance du plan, en termes de longueur relative, est attaché à chaque image-clé, pour donner plus de poids aux plans majoritaires. Ce coefficient de pondération est pris en compte dans les étapes ultérieures, notamment dans les calculs de distance. Il serait bien sr tout aussi envisageable de rattacher plusieurs imagesclés à 20 un plan proportionnellement à la longueur de celui-ci. Dans ce cas, du fait du volume plus important de données à traiter, le temps de traitement serait augmenté. Initialisation de l'algorithme L'étape d'initialisation de l'algorithme de partitionnement (clustering), qui constitue elle-même l'algorithme de sélection de germes, consiste à trouver des germes pour la classification dans l'espace des signatures. Le nombre des images étant important, il est procédé par tirage aléatoire de p images-clés. Afin de s'assurer, sous l'hypothèse de plans 30 d'intérêt majoritaires, de tirer au moins une image-clé représentative d'un plan majoritaire, le nombre p est calculé suivant la méthode d'échantillonnage de Monte-Carlo. Dans cette formule, le taux de contamination des données est biaisé par le poids des images-clés. La méthode d'échantillonnage de Monte-Carlo est connue et décrite par 35 exemple dans l'article de P. Meer, D. Mintz, A. Rosenfeld intitulé: "Robust regression methods for computer vision: a revieW' - International Journal of Computer Vision, Vol:6, n'1, P. 59-70 (1991). Il faut s'assurer également de ne jamais effectuer 2 fois le même tirage. Seule une image-clé parmi les p images tirées sera retenue comme germe pour l'initialisation de l'algorithme de clustering, comme indiqué par la suite. La figure 2 décrit un algorithme de sélection de n germes. Les différents rectangles référencés A à F représentent l'ensemble des imagesclés tel qu'il évolue lors du traitement. L'étape 6 regroupe l'ensemble des images-clés candidates dans 10 l'ensemble des signatures. A l'origine, c'est à dire lors de la première itération, il s'agit de l'ensemble des images-clés de la séquence vidéo traitée. Cet ensemble est représenté par le rectangle A. Ces images sont caractérisées par leurs signatures, par exemple les couleurs dominantes qui sont les composantes d'un vecteur multidimensionnel affecté à chaque 15 image. L'étape suivante 7 effectue un tirage aléatoire d'un candidat suivant une méthode numérique d'échantillonnage de type Monte-Carlo. L'étape suivante 8 calcule, pour l'image tirée, son cot. Par exemple, ce cot peut être défini par la fonction 20 C= E f(e12) avec: e1 = distance quadratique pondérée entre la signature retenue, c'est à dire celle de l'image sélectionnée ou candidat, et la signature de l'image i de l'ensemble, f(e,2) = e,2 si e12 T2 o T est l'écart type de la distribution des distances pondérées à l'image sélectionnée. Les étapes 7 et 8 sont réitérées p fois, p étant une valeur calculée par la formule de Monte-Carlo. La valeur p correspond alors au tirage 30 minimum permettant de garantir avec une forte probabilité qu'une imageclé représentant un plan majoritaire a été tirée. Cette probabilité dépend du taux de contamination, c'est à dire du pourcentage d'images- clés d'intérêt dans l'ensemble. Par exemple p est de l'ordre de 10 pour une probabilité de 99% et un taux de contamination minimum de 50%. Bien sr, un tirage aléatoire 35 selon une autre méthode peut être effectué à l'étape 7, le nombre p étant lié à cette probabilité qu'au moins une image-clé représentant un plan majoritaire a été tirée. On obtient donc p candidats, éléments représentés en noir dans le rectangle B. Parmi les p candidats auxquels sont affectés p cots, une sélection est effectuée qui consiste à choisir le candidat ki correspondant au cot le plus faible, c'est l'objet de l'étape 9. Etant donné les 5 hypothèses, ce candidat correspond à l'image- clé.Cet élément est désigné par une flèche dans le rectangle C. L'étape 10 réalise un calcul de l'écarttype T de la distribution par rapport au candidat kM. L'étape suivante 11 détermine, pour le tirage ou candidat k1 retenu, le sous-ensemble Ik des éléments dont la distance au candidat des 10 signatures est inférieure à un seuil T. Il s'agit ici de l'écart-type de la distribution des distances au candidat mais ce seuil pourrait tout aussi bien être une valeur fixée a priori. Ce sous-ensemble est entouré dans le rectangle D. La détermination du germe k2, dans le sous-ensemble Ik, pour 15 initialiser le K-médod, est effectuée à l'étape suivante 13. C'est l'élément du sous-ensemble Ik minimisant la fonction de cot C. Il s'agit d'un minimum local. L'étape 14 mémorise ce germe k2. Ce germe est désigné par une flèche dans le sous-ensemble Ik représenté dans le rectangle F. L'itération est effectuée par reblouclement de l'étape 11 sur l'étape 20 6 par l'intermédiaire d'une étape 12. Après détermination du sous-ensemble Ik, étape 11, l'étape 12 élimine de l'ensemble des images-clés, les éléments composant ce sous-ensemble. L'ensemble des images-clés candidates est donc restreint en écartant les éléments du sous-ensemble 1k, qui contient des images-clés trop proches du germe précédemment trouvé. Les éléments 25 du nouvel ensemble, représenté dans le rectangle E, sont regroupés à l'étape 6 et exploités pour une nouvelle itération. Le nombre d'itérations, c'est à dire de germes sélectionnés, est fixé à n, n étant une valeur prédéfinie. L'étape 14 mémorise donc n germes k2. Du fait de l'hypothèse, les plans recherchés étant majoritaires, les 30 poids de chacune des images qui les représentent sont parmi les plus importants. Cela nous assure qu'ils correspondent au groupe le plus compact au sens métrique utilisé. Nous sommes alors certains que le premier germe cherché correspond à un représentant de la classe " intérêt ". La deuxième phase consiste en la mise en oeuvre de l'algorithme de partitionnement des plans. La partition ou groupement des plans à partir des germes est effectuée de manière classique en groupant les images-clés de signatures les plus proches de celles des germes. A chaque germe trouvé correspond un groupe. Chaque plan représenté par sa signature est attribué au germe le 5 plus proche. Si une signature est équidistante de 2 germes ou trop distantes des germes, elle est retenue comme un nouveau germe et le partitionnement des plans recommence en tenant compte de ce nouveau germe. Les plans ou images-clés du cluster correspondant au premier germe sont étiquetés " intérêt", les autres plans sont étiquetés " non10 intérêt ". Cette méthode n'est pas robuste dans le sens o la classification n'est pas optimale, puisqu'on oblige un plan à s'associer avec l'un des clusters prédéterminés par l'initialisation sauf dans l'un des 2 cas précédemment cités. Une mise en oeuvre particulière de l'invention consiste 15 à réaliser une itération de l'algorithme de partitionnement permettant de rendre la méthode robuste. Une fois tous les plans regroupés en clusters, on calcule la moyenne et écart-type de la distribution des distances au germe pour chaque cluster obtenu. Seul le cluster le plus compact est retenu. Les autres clusters 20 sont " relâchés ", c'est à dire qu'un nouvel ensemble constitué de ces seuls autres clusters est exploité pour la mise en oeuvre ultérieure des algorithmes d'initialisation et de classification. Les processus d'initialisation et de classification sont donc réitérés pour toutes les images-clés restantes. Une itération est donc effectuée à partir d'un ensemble obtenu en éliminant de 25 l'ensemble correspondant à l'itération précédente, le cluster le plus compact trouvé lors de cette itération précédente. Plusieurs critères d'arrêt des itérations peuvent être mis en oeuvre: - un seul germe est sélectionné, c'est à dire que le processus 30 d'initialisation ne génère plus qu'un germe. Les images-clés candidates traitées par l'algorithme d'initialisation sont suffisamment rapprochées pour correspondre au sous-ensemble Ik et donc à un seul germe. - les moyennes des distances intra-clusters sont presque égales. Autrement dit, une nouvelle itération de l'algorithme de partitionnement 35 n'apportera pas d'information supplémentaire. - il ne reste plus suffisamment d'images-clés et l'on obtiendrait des clusters unité. Les images-clés candidates sont très différentes, ne générant que des sous-ensembles Ik d'une seule image. L'algorithme a été implémenté et testé sur plusieurs séquences de tennis. La figure 3 montre le résultat de l'algorithme de clustering sur une séquence de tennis contenant 97 plans, avec n=3. Le cluster n01, en haut de la figure, représente les plans intérêts, 10 ici les vues du terrain de tennis. Les autres clusters contiennent des gros plans et des vues du public. Les applications concernent par exemple la création d'un résumé long en concaténant les plans sélectionnés. Les plans sélectionnés peuvent 15 également servir d'entrée à un algorithme de structuration plus complexe pouvant s'appuyer sur la connaissance a priori de la prise de vue. Dans l'exemple décrit, la signature utilisée est un vecteur de couleurs dominantes associé à une distance quadratique simplifiée. On peut 20 imaginer d'autres critères permettant de caractériser les séquences vidéo à partitionner, par exemple la texture, les contours...Ces critères sont choisis de manière à pouvoir caractériser des plans d'intérêt. REVENDICATIONS 1 Procédé de sélection de germes (14) parmi un ensemble d'images-clés d'une séquence vidéo pour le regroupement d'images-clés de 5 plans majoritaires de la séquence vidéo, caractérisé en ce qu'il met en oeuvre les étapes suivantes: - tirage aléatoire (7) de p candidats dans l'ensemble d'imagesclés, p étant calculé de manière à obtenir une très bonne probabilité de tirer une image-clé d'un plan majoritaire, - calcul du cot C (8) pour chaque candidat, fonction de la distance des imagesclés de l'ensemble à celle du candidat, la distance étant relative aux signatures, - sélection du candidat (ki) (9) minimisant le cot C, détermination d'un sous-ensemble (1k) (11) parmi l'ensemble 15 d'imagesclés tel que les images-clés formant le dit sous-ensemble ont une distance au candidat inférieure à un seuil T (10), - détermination d'un germe (k2) (13) parmi les images-clés du sous-ensemble (Ik) tel qu'il minimise la fonction de cot C pour ce sous-ensemble, - suppression des images-clés du sous-ensemble (1k) (12) pour 20 former un nouvel ensemble d'images-clés pour au moins un nouveau tirage aléatoire et détermination d'un nouveau germe selon les 5 étapes précédentes. 2 Procédé selon la revendication 1, caractérisé en ce que le tirage 25 aléatoire est du type Monte-Carlo, p étant calculé par la formule de MonteCarlo. 3 Procédé selon la revendication 1, caractérisé en ce que les images-clés sont pondérées, quant à leur signature, en fonction de la 30 longueur des plans de la séquence vidéo qu'elles caractérisent et en ce que le tirage aléatoire est biaisé par le poids des images-clés. 4 Procédé selon la revendication 1, caractérisé en ce que le cot C est fonction des distances quadratiques entre la signature du candidat et 35 celles des images-clés du sous-ensemble et en ce que T est l'écart-type de la distribution des distances des images-clés de l'ensemble au candidat. fonction de la distribution des distances des images-clés de l'ensemble au candidat, Procédé selon la revendication 1, caractérisé en ce que la signature d'une image est relative à la couleur dominante. 6 Procédé de regroupement (clustering) de plans d'une séquence d'images vidéo, la séquence étant découpée en plans (1), un plan étant représenté par une ou plusieurs images-clés (2), au moins une signature ou 10 attribut étant calculé pour les images-clés (3), comportant une phase de partitionnement des images-clés à partir d'une comparaison des attributs des images-clés, caractérisé en ce qu'il comporte une phase d'initialisation pour la sélection d'au moins deux images-clés ou germes à partir desquelles sont effectuées les comparaisons pour le regroupement, la sélection étant 15 effectuée selon le procédé de la revendication 1. 7 Procédé selon la revendication 6, caractérisé en ce que la phase de partitionnement met en oeuvre un algorithme du type K-means ou Kmedod. 8 Procédé selon la revendication 6, caractérisé en ce que les phases d'initialisation et de partitionnement sont réitérées, les imagesclés du cluster le plus compact obtenu à l'itération précédente étant éliminées de l'ensemble traité à cette itération précédente pour fournir un nouvel 25 ensemble sur lequel est effectuée la nouvelle itération. 9 Procédé selon la revendication 8, caractérisé en ce que le critère d'arrêt pour les itérations est fonction du nombre d'images-clés n'appartenant pas au cluster le plus compact sélectionné ou bien est fonction 30 des moyennes des distances intra-clusters. Procédé de sélection de plans d'intérêt (4), ces plans étant majoritaires dans la séquence vidéo, caractérisé en ce qu'il met en oeuvre le procédé selon la revendication 6, les plans d'intérêt correspondant au 35 regroupement effectué autour du premier germe sélectionné.