Prétraitement : analyse de la vidéo et détection d’attributs de bas niveau 

Dans cette thèse, nous nous sommes, dans un premier temps, focalisés sur l’adaptabilité des résumés. Les règles de production, décrites dans la section précédente, peuvent être exprimées sous forme de contraintes à satisfaire. Par conséquent, nous proposons de considérer le problème de création automatique de résumés comme un problème de satisfaction de contraintes (PSC), où la façon avec laquelle le résumé doit être créé est définie par un ensemble de contraintes.

Pour répondre aux besoins d’adaptation des résumés créés automatiquement, nous avons proposé une approche basée sur la programmation par contraintes (PPC). La PPC a pour objectif de trouver une ou plusieurs solutions qui satisfont des contraintes ex-primées en utilisant un solveur de contraintes. La PPC vient de l’intelligence artificielle, c’est un outil puissant et efficace pour la résolution des problèmes NP-complets et pour la modélisation et la résolution des problèmes d’optimisation combinatoire. Elle a été utilisée pour résoudre les problèmes dans différents domaines, comme les logiciels d’op-timisation pour le trafic aérien et la gestion des portes d’embarquement, la construction de véhicules, la planification d’horaires, la gestion de la rotation du personnel, etc.

Un des avantages de l’approche proposée est qu’elle assure une séparation claire entre la modélisation et la résolution du problème. En d’autres termes, entre les règles de production du résumé et l’algorithme de génération du résumé (ici, le solveur de contraintes). Différents types de résumés peuvent être générés simplement, en ajou-tant de nouvelles contraintes ou en fournissant des paramètres de haut niveau pour les contraintes existantes. Notre méthode de création automatique de résumés n’est donc  pas une boîte noire qui doit être complètement revue si l’utilisateur souhaite adap-ter le résumé. Notre approche est souple et extensible, dans le sens où elle permet à l’utilisateur de configurer facilement le résumé final en fonction de ses besoins en ajou-tant/modifiant une contrainte sans être amené à revoir l’ensemble du modèle ou à mo-difier n’importe quel paramètre interne. La figure 1.1 met en évidence cette séparation :

D’autre part, la programmation par contraintes permet de spécifier des contraintes et une fonction de coût à optimiser. Les contraintes peuvent être utilisées pour modéliser les règles de production qui doivent être obligatoirement respectées. Tandis que la fonc-tion de coût à optimiser peut être utilisée pour minimiser ou maximiser une grandeur spécifique. En d’autres termes, cette fonction définit ce qu’il est souhaitable d’avoir (ou pas) dans le résumé final, sans que cela soit obligatoire. En s’appuyant sur la programmation par contraintes, nous proposons trois modèles pour la création automatique de résumés de vidéos. Ces modèles se distinguent par leur flexibilité, c’est à dire leur capacité d’exprimer les règles de production du résumé. Ils se distinguent aussi par leur efficacité, c’est-à-dire leur capacité à trouver rapidement des solutions au problème de satisfaction de contraintes proposé. Aborder l’ensemble de ces aspects constitue les deux premières contributions de cette thèse (adaptation des résumés et séparation entre les règles de production et l’algorithme de génération du résumé).

La troisième contribution de cette thèse concerne la procédure d’évaluation de la qualité des résumés générés automatiquement. Nous avons évalué la méthode proposée, tout d’abord, en utilisant des mesures objectives et, ensuite, en lançant une campagne d’évaluation à large échelle effectuée par les utilisateurs.

Différents types de résumés ont été générés/récupérés sur un ensemble de 12 matchs de tennis (environ 28, 5 heures de vidéo). L’évaluation a été réalisée avec la collaboration de 61 personnes. Les résultats obtenus ont été soigneusement analysés en utilisant non seulement des mesures quantitatives, mais aussi des tests statistiques. Au-delà de l’évaluation de notre méthode, cette étude impliquant les utilisateurs nous permet de proposer des recommandations importantes concernant le protocole d’évaluation dans ce contexte.

Le reste du présent manuscrit s’organise en six chapitres, qui s’articulent autour de deux parties :

– Le chapitre 2 s’intéresse, dans une première partie, aux différentes approches de création automatique de résumés proposées dans les travaux existants. Ces travaux sont classés en quatre grandes catégories selon le principe sur lequel ils sont fon-dés et selon la forme souhaitée du résumé résultant. Nous présentons, également, quelques travaux proposés dans le cadre de la compagne TRECVID. Dans une deuxième partie de ce chapitre, nous nous intéressons aux différentes méthodes d’évaluation de la qualité des résumés générés, proposées dans le cadre de TREC-VID et dans un contexte général. Nous présentons quelques protocoles et quelques critères d’évaluation. Nous examinons comment les travaux existants ont abordé ce sujet.

– Le chapitre 3 présente quant à lui, le paradigme de la programmation par contraintes. Nous rappelons quelques définitions des problèmes de satisfaction et d’optimisation de contraintes, des méthodes et des stratégies de résolution. Nous terminons par un exemple illustratif d’un problème de satisfaction de contraintes, nous présentons quelques modèles possibles utilisés pour sa résolution.

Le chapitre 4 présente d’abord deux modèles différents du problème de création de résumés vidéo basés, tous les deux, sur une segmentation en plans de la vidéo d’en-trée. Nous introduisons les modèles basés sur la programmation par contraintes, leurs avantages et leurs limites. Nous présentons une étude expérimentale sur l’efficacité des modèles ainsi que sur la qualité des résumés générés. Ensuite, dans le chapitre 5, nous introduisons un nouveau modèle qui s’affranchit de toute pré-segmentation du flux au-diovisuel et qui ne dépend d’aucune frontière de plan. Pour cela, nous avons été amenés à implémenter l’ensemble des relations de l’algèbre d’intervalles de Allen. Nous présen-tons le principe de ce modèle. Nous décrivons les nouvelles contraintes globales pro-posées et implémentées avec leurs algorithmes de filtrage. Nous présentons une étude comparative avec les modèles du chapitre 4 ainsi qu’une évaluation de la qualité des résumés résultants. Enfin, le chapitre 6 explique les difficultés liées à l’évaluation de la qualité des résumés générés. Nous présentons, par la suite, notre expérience menée par des tests utilisateurs ainsi que le protocole d’évaluation proposé.

Le dernier chapitre de ce manuscrit est enfin consacré aux conclusions, en dressant un bilan critique des principales contributions de cette thèse, et en proposant quelques pistes de travaux futurs ainsi qu’une liste des publications associées aux travaux de cette thèse.

De nombreux travaux de recherche dédiés à la création automatique de résumés de vidéos ont été proposés [MA08, RK14]. Dans les travaux existants, les résumés de vi-déos peuvent être de deux types. Le premier consiste à extraire un ensemble d’images, le deuxième consiste à créer une nouvelle vidéo à partir de la vidéo d’entrée. Le pre-mier type, généralement appelé résumé statique de la vidéo, est une collection d’images représentatives qui sont soigneusement extraites à partir de la vidéo. Ces images sont appelées images-clés. Chacune d’entre elles représente le contenu visuel d’une partie de la vidéo. La visualisation de ce type de résumé est rapide et la complexité de son algorithme de création est généralement faible. Le second type, également connu sous le nom de résumé dynamique de vidéo, est un ensemble de segments vidéo sélectionnés à partir de la vidéo d’entrée. Ce type de résumés conserve les propriétés dynamiques de la vidéo d’entrée et par conséquent il est plus agréable à regarder qu’un résumé statique. Il est également plus expressif, car il comprend à la fois de l’information visuelle et audio. Mis à part quelques cas d’utilisation spécifiques où la sélection d’un ensemble d’images représentatives est suffisante, un résumé sous forme d’une vidéo est généralement plus utile dans la pratique. Même si l’approche que nous avons proposée peut s’appliquer pour générer, à la fois, les résumés statiques et les résumés dynamiques de vidéos, nous avons mis l’accent, dans ce chapitre, plutôt sur ce dernier type de résumés (résumés dynamiques).

Dans ce chapitre, nous décrivons les techniques existantes de création de résumés vidéo regroupés en quatre catégories sur la base de leurs principes. La dernière section de ce chapitre est dédiée au problème de l’évaluation de la qualité des résumés générés.

L’objectif de ces approches est de simuler et de modéliser l’attention des utilisateurs pour créer le résumé vidéo. Ces approches procèdent généralement en trois étapes.

Segmentation : une première étape consiste à segmenter la vidéo en un ensemble d’uni-tés de base. Une unité de base peut être temporelle (une seconde, plusieurs se-condes, une minute, …). Elle peut être sous forme de segments (plans, scènes, …) ou même d’une image.

Calcul de scores et création de courbes : la deuxième étape consiste à calculer un score pour chaque unité de base de la vidéo d’entrée. Ce score reflète l’importance qui peut être attribuée à l’unité de base et donne une indication sur la probabilité pour qu’elle soit sélectionnée et incluse dans le résumé. En pratique, les scores sont calculés en se basant sur des algorithmes de détection de caractéristiques de bas niveau (le volume de l’audio, l’intensité de mouvement, la luminosité… ). Ces caractéristiques permettent d’identifier des moments susceptibles d’attirer l’atten-tion humaine. Les scores calculés sont utilisés par la suite pour créer une courbe modélisant l’attention des utilisateurs. Par exemple, l’attention de l’utilisateur est souvent captée par des événements visuels, acoustiques ou textuels. Par consé-quent, des caractéristiques visuelles, acoustiques et textuelles sont détectées pour créer respectivement des courbes d’attention visuelles, acoustiques et textuelles. Une courbe de synthèse modélisant l’attention humaine est obtenue par la fusion de ces différentes courbes.

Sélection d’extraits : la dernière étape consiste à analyser la courbe d’attention finale et à sélectionner les extraits à inclure dans le résumé. La sélection d’extraits est basée sur la détection des images (ou des séquences) qui correspondent aux pics de la courbe moyennant l’application d’un seuil (les extraits ayant des scores supérieurs à ce seuil sont sélectionnés) ou l’utilisation d’un intervalle de temps (des extraits d’une durée de 30 secondes ayant un pic au centre sont sélectionnés).

Dans [LYG+08, LL09], la génération de résumés est basée sur la création d’un mo-dèle d’attention visuelle uniquement. Le modèle proposé est calculé en utilisant des histogrammes de couleurs et de luminosité qui servent à détecter les régions d’intérêt dans une image (personnes ou objets). Cette méthode est limitée puisqu’elle n’utilise ni l’information audio ni l’information textuelle pour générer les résumés vidéo. Cette limitation a été traitée en partie par Evangelopoulos et al. [ERP+08] qui ont proposé un modèle de saillance audiovisuelle en combinant deux modèles d’attention visuelle et acoustique. Le modèle de saillance acoustique est créé en se basant sur l’extraction des composantes AM-FM (modulations temporelles d’amplitude et de fréquence) du si-gnal audio. Le signal audio est modélisé par la somme du changement de fréquence et d’amplitude. Les structures saillantes sont alors les signaux de modulation sous-jacents. Quant au modèle de saillance visuelle, il est créé en se basant sur la couleur, l’intensité de l’image et le mouvement des objets. Les deux modèles sont combinés en un modèle de saillance audiovisuelle Mav définit par : Mav = wa.Ma + wv.Mv (2.1)

où wa et wv sont les poids attribués respectivement au modèle de saillance acoustique Ma et au modèle de saillance visuelle Mv. Les poids sont déterminés par le moindre carré de leurs valeurs individuelles dans l’intervalle [0, 1] suivant la normalisation des courbes.

Les mêmes auteurs ont proposé une extension de leurs travaux en introduisant, en complément des modèles de saillance visuelle et acoustique déjà décrits, un modèle de saillance textuelle [EZS+09]. L’information textuelle est récupérée à partir de la trans-cription de la piste audio. Pour cela, le flux audio est segmenté en utilisant la techno-logie de reconnaissance automatique de la parole. Les segments audio sont délimités par l’image de début et l’image de fin de chaque mot. Les scores sont attribués pour  chaque mot en utilisant l’étiquetage morpho-syntaxique (POS tagger : Part-of-speech tag-ger). L’équation 2.1 est étendue et utilisée pour la fusion des trois modèles de saillance (visuelle, acoustique et textuelle).

Une étape très importante dans le processus de création de résumés vidéo en utilisant les modèles d’attention, est la fusion des modèles d’attention partiels donnant naissance à un modèle d’attention final. Dans [MHL+05], la combinaison des différents modèles d’attention partiels peut être effectuée, soit par des systèmes de fusion linéaires (donnés par l’équation 2.1) où un poids est affecté à chaque modèle calculé (les poids sont ajustés en fonction de l’importance du modèle), soit par une combinaison non-linéaire [HZ05] pour obtenir de meilleurs résultats de décision en ce qui concerne le processus de fusion.

Dans [NMZ05], Ngo et al. ont introduit une approche basée sur la construction de graphes. Cette approche est décomposée en deux étapes. La première étape consiste à classer les plans en utilisant l’algorithme de coupes normalisées (normalized cuts al-gorithm) [SM00]. Dans la deuxième étape, la vidéo est représentée sous la forme d’un graphe temporel orienté de plans. Le graphe est similaire au graphe STG (scenes transition graph) présenté dans [YYW+95]. Les valeurs de l’attention basée sur le mouvement sont attribuées à chaque nœud du graphe. Le résumé est généré à partir du graphe en tenant en compte à la fois la structure de la vidéo et les valeurs de l’attention.

Par ailleurs, un autre travail original a été proposé dans [LGF+10]. Les auteurs dé-crivent un processus expérimental qui applique l’imagerie par résonance magnétique fonctionnelle (fMRI) pour étudier la dynamique et l’interaction entre le flux multimédia et la réponse du cerveau humain pour estimer les poids utilisés dans la fusion des mo-dèles. Ils ont identifié 36 régions d’intérêt dans le cerveau humain à partir desquelles une série de signaux est extraite et utilisée pour modéliser la réponse du cerveau.

Dans [LK03], des scores sont calculés pour chaque image de la vidéo d’entrée. Chaque score est associé à un attribut tel que l’occurrence des visages, l’occurrence du texte, le zooming de la caméra et le volume audio. Des conditions sont exprimées par un expert sur ces différents attributs sous forme d’un ensemble d’inégalités. Les inéga-lités impliquent les attributs et un ensemble de seuils fixés par l’expert. Le résumé final est composé des images qui satisfont toutes les conditions exprimées. Pour éviter une segmentation excessive, un algorithme glouton est utilisé pour maximiser le score total et réduire le nombre d’extraits sélectionnés à partir de la vidéo d’origine. Dans [GGR+14], Gygli et al. ont proposé une approche de création de résumés de vidéos personnelles. La vidéo est tout d’abord segmentée en se basant sur le mouve-ment dans les images. L’importance d’un segment est ensuite estimée en utilisant un ensemble d’attributs de bas et de haut niveau tels que la couleur, la luminosité, la détection de monuments, de personnes et le suivi des objets. Enfin, en utilisant les scores reflétant l’attention humaine pour chaque segment, le problème de création du résumé est formalisé sous forme d’un problème de sac à dos (Knapsack problem) qui maximise l’importance totale dans le résumé.

Bien que les approches basées sur des modèles d’attention soient simples et offrent un bon formalisme pour introduire et résoudre le problème de création de résumés vi-déo, les résultats obtenus présentent des limitations. Les caractéristiques de bas niveau détectées sont essentiellement pondérées et additionnées pour construire la courbe mo-délisant d’attention humaine, ce qui ne garantit pas forcément une corrélation avec les intérêts réels de l’utilisateur. D’autre part, ces approches impliquent trop de paramètres fixés de façon heuristique ou bien empirique. Ces paramètres sont difficiles à mettre en place, en particulier les cœfficients (poids) de pondération des différents caractéristiques de bas niveau ainsi que le seuil final appliqué sur la courbe d’attention résultante. Enfin, une fois que le modèle est formé, il est très difficile de le modifier afin de prendre en considération un nouveau type de vidéo ou un nouveau critère (un nouveau attribut de bas niveau par exemple visage, volume,…).

D’autres travaux visent à créer des résumés sous forme d’aperçus utilisés pour donner aux utilisateurs une idée générale sur l’ensemble du contenu vidéo.

Une façon triviale de créer des résumés sous forme d’aperçu de la vidéo est de l’accé-lérer. Le principe consiste à condenser la vidéo originale en accélérant tout simplement sa lecture. Le système Video Cue proposé dans [PAS+99] est un exemple qui adopte une vitesse de lecture plus rapide lors de la lecture de la vidéo pour produire une vue d’ensemble. Bien que le temps de visualisation soit réduit, les propriétés de la vidéo sont déformées et la compréhension de l’audio est affectée. Une autre façon triviale de créer ce genre de résumés (vue d’ensemble) est d’ignorer des images à partir de la vi-déo d’origine [LSK05], ce qui permet de réduire la durée de la vidéo, mais en contre partie, permet d’introduire des distorsions. Ce compromis est formulé en utilisant une optimisation MINMAX qui minimise la distorsion maximale par segment.

D’autres approches sont basées sur la mesure de la similarité entre les différentes parties de la vidéo et l’élimination de la redondance. Afin de sélectionner des images représentatives qui soient assez différentes les unes des autres et qui représentent bien la totalité du contenu de la vidéo, une comparaison de toutes les images de la vidéo entre elles, est effectuée.

La méthode proposée dans [CF02], permet de sélectionner des extraits qui maxi-misent la similarité moyenne entre l’extrait sélectionné et le reste de la vidéo. La sélec-tion des extraits est basée sur le calcul de la factorisation non-négative d’une matrice de similarité. Le résumé final peut être généré sous forme d’une combinaison de plans, comme dans la méthode proposée dans [GL01]. Les plans sont regroupés en un en-semble de clusters en fonction de leur similarité visuelle. Le plan le plus long de chaque cluster est retenu pour représenter celui ci. Dans d’autre méthodes, le résumé final peut être généré sous forme d’une combinaison de sous-plans, comme dans [NT99]. La mé-thode proposée découpe la vidéo en un ensemble de sous-plans en calculant l’activité de mouvement local. Une fois les sous-plans détectés, l’algorithme proposé calcule l’in-dice de l’intensité de mouvement pour chaque sous-plan et ne retient que ceux qui ont l’indice le plus élevé. L’indice de l’intensité de mouvement correspond à la quantité de l’activité visuelle au sein de chaque sous-plan. Il est calculé en appliquant la fonction de filtrage de transformée en ondelettes 1D.

Dans [Gon03], les plans sont classés en utilisant un arbre couvrant de poids mini-mal (minimum spanning tree en anglais) où les nœuds représentent les plans de la vidéo et chaque arête représente la distance entre deux plans dans l’espace des attributs. Un graphe biparti est utilisé pour éliminer les doublons et garder les plans qui sont visuel-lement distincts. Un résumé vidéo est ainsi créé. Un autre résumé est créé en utilisant la technique d’analyse sémantique latente (LSA, Latent semantic analysis en anglais) ap-pliquée sur les transcriptions de parole. Un algorithme d’alignement audiovisuel à base de graphes est utilisé pour aligner les deux résumés. Plusieurs autres méthodes basées sur des graphes orientés sont proposées notamment dans [LLK04, LKL05]. Les nœuds correspondent aux différents plans de la vidéo. À chaque nœud est associé un poids qui est la durée du plan correspondant. Les arêtes du graphe représentent la distance entre les plans (calculée par une fonction combinant la similarité visuelle et la distance temporelle). Étant donné que la durée totale du résumé est la somme des poids des nœuds (plans à sélectionner), les auteurs ont proposé de trouver le plus long chemin du graphe ayant la somme des poids des nœuds appartenant à un intervalle de tolérance [dmin..dmax].

L’algorithme TV-MMR (Text Video Maximal Marginal Relevance) proposé dans [LMR+11] est basé sur le calcul de la similarité visuelle en plus de l’information textuelle pour la création des résumés vidéo. L’algorithme permet de sélectionner, de manière ité-rative, des images dont le contenu visuel est le plus similaire au contenu vidéo, mais en même temps le plus différent des images déjà sélectionnées dans le résumé. L’informa-tion textuelle est récupérée à partir de la transcription de la piste audio en utilisant le système ASR Automatic Speech Recognition. Le résumé est le résultat de la concaténation d’un ensemble de segments audiovisuels courts de durée prédéfinie, sélectionnés à par-tir de la vidéo d’entrée. Le résumé optimal est le résumé qui maximise la quantité totale du contenu visuel tout en préservant la cohérence de l’information textuelle.

Dans [DR14], le problème de création automatique de résumés vidéo est considéré comme un problème de sélection d’un ensemble optimal d’extraits qui minimise la dis-tance entre la vidéo d’entrée et le résumé généré. Cette distance est mesurée en utili-sant une courbe d’indices HIP (Heterogeneity Image Patch) qui représente la dissemblance entre la vidéo d’entrée et le résumé vidéo. Le calcul des valeurs des indices HIP est basé sur les pixels et ne nécessite pas l’information sémantique ni l’estimation complexe du mouvement de la caméra.

Selon les travaux présentés dans [STC10], un résumé vidéo doit répondre à deux critères essentiels qui sont < la couverture > : le résumé doit représenter la totalité de la vidéo d’origine et < la diversité > : les différentes parties du résumé sont assez distinctes et assez différentes. Un aperçu rapide de la vidéo est fourni en sélectionnant des extraits à partir de la vidéo qui maximisent < la couverture > et < la diversité >. Les auteurs ont proposé une formulation mathématique de ces deux critères et une fonction de coût à optimiser.

Ces approches permettent de couvrir la totalité du contenu audiovisuel et de fournir une vue d’ensemble de la vidéo, mais ils ne garantissent pas que le résumé généré puisse attirer l’attention des utilisateurs.

Une autre façon de créer des résumés vidéo est de détecter les moments forts (appelés en anglais highlights) de la vidéo d’entrée.

L’un des premiers travaux utilisant ce principe est le projet Informedia [SK95]. ce projet se base sur la détection de caractéristiques audiovisuelles de bas niveau. Un ré-sumé audio est créé en correspondance avec les mots-clés qui sont extraits à partir de la transcription audio en utilisant la technique TF-IDF. D’une autre part, un résumé vi-déo est créé en utilisant la détection de visages, la détection de texte et la détection du mouvement de la caméra. Ce résumé est créé en utilisant un système de classement qui considère que les images présentant les visages ou le texte sont les plus importantes, les images statiques qui suivent le mouvement de la caméra sont moins importantes…

etc. Bien que l’intégration de l’information visuelle, audio et textuelle soit la meilleure façon de comprendre une vidéo, la génération de résumés basés sur une telle technique nécessite encore une intervention manuelle.

Le système Vabstract présentée dans [PLF+96], propose de créer une bande annonce comprenant des moments forts d’un film en sélectionnant des scènes vidéo intéressantes. Dans cette méthode, les auteurs ont choisi les scènes comme unités à sélectionner. Une scène est un ensemble d’images consécutives tournant autour d’une même action et liées sémantiquement. Les scènes contenant des objets, des personnes, des scènes d’action, du dialogue… sont extraites et classées comme intéressantes.

Un nouvel algorithme de classification a été proposé dans [PN05]. Cet algorithme utilise une approche de clustering basée sur l’utilisation de graphes non orientés mesu-rant la similarité visuelle entre toutes les paires d’événements d’une vidéo. Les moments forts sont détectés en sélectionnant le clip représentatif de chaque cluster et en se basant sur les propriétés des clusters : la taille du cluster et la globalité d’un événement. La glo-balité d’un événement est un critère calculé en utilisant le nombre de chaînes diffusant cet événement et la fréquence de diffusion de ce dernier. La sélection des clips respecte bien évidemment la contrainte de la durée autorisée du résumé final.

Dans [LHC10], Liu et al. ont proposé une méthode basée sur la suppression des images non pertinentes en fonction de l’intérêt de l’utilisateur afin de garder les mo-ments forts de la vidéo. Pour définir son intérêt, l’utilisateur fournit quelques images qui contiennent un objet d’intérêt (sans localiser précisément l’objet) et d’autres images qui ne contiennent pas l’objet d’intérêt. C’est une méthode qui repose sur l’interven-tion humaine dans la boucle de détection d’objets adapté aux intérêts des utilisateurs. La méthode de création de résumés est semi-automatique et repose sur l’apprentissage faiblement supervisé.

D’autres approches ont identifié les rôles principaux et les communautés de rôles afin de détecter les événements intéressants dans une vidéo. Dans ce contexte, une tech-nique de création de résumés de films a été proposée dans [TKL+13]. Elle est basée sur l’exploration des relations entre les rôles qui sont regroupées en communautés. Les rôles sont détectés en utilisant la détection de scène et la classification de visages.

Le système LiveLight proposé dans [ZX14], décrit une approche de création de résu-més présentant le contenu audiovisuel le plus important et le plus intéressant de la vidéo d’entrée. L’approche est basée sur l’apprentissage d’un dictionnaire d’une vidéo donnée en utilisant la méthode group sparse coding [BPS+09]. Cela consiste à construire un dic-tionnaire en utilisant la quantification vectorielle sur un grand ensemble de descripteurs visuels (couleur, texture, angles et forme) à partir d’un ensemble d’apprentissage. Un algorithme du plus proche voisin est utilisé pour compter le nombre d’occurrences de chaque mot du dictionnaire dans la vidéo. Le dictionnaire est mis à jour au fil de l’avancement de la vidéo. Le résumé est ensuite généré en combinant les segments qui sont à l’origine de la mise à jour du dictionnaire.

La création de résumés basés sur la détection des événements intéressants est une tâche difficile dans l’absence d’une connaissance a priori du type de la vidéo en question. Dans ce contexte, plusieurs techniques ont été proposées pour détecter les moments forts dans des vidéos de types spécifiques où certaines caractéristiques particulières peuvent être utilisées, comme les vidéos de sport et les vidéos de journaux télévisés. Pour les vidéos de sport en terme général (quel que soit la discipline), des travaux basés sur la détection d’événements tel que dans [XRD03] ont été proposés. D’autres qui abordent en particulier des vidéos de basket-ball [ZE01], des vidéos de baseball [CHG02, RGA00] ou encore des vidéos de football [CDV11, ETM03, SC03], où un modèle de chaîne de Markov, intégré par un algorithme EM (espérance-maximisation) est utilisé pour détec-ter les pauses et les phases de jeu. Quant aux vidéos de journaux télévisés, un système de questions-réponses est proposé dans [YCZ+03], introduisant une approche de pon-dération pour classifier les plans de la vidéo qui contiennent des mots associés très fréquents en utilisant la transcription de la parole. Afin de détecter les événements in-téressants, d’autres travaux ciblent un autre type spécifique de vidéo, les vidéos égo-centriques [LG13, LG15]. Les vidéos égocentriques sont des vidéos acquises avec des caméras portées par des personnes donnant une vue rapprochée sur les actions de la personne qui porte la caméra. Ces méthodes sont basées sur la détection de personnes et d’objets d’intérêt.

Ces approches sont très spécifiques et exigent généralement une phase d’apprentis-sage pour chaque type de vidéos.

Ces approches sont basées sur les messages courts des microblogues récupérés à partir des réseaux sociaux, tel que Twitter, qui est un service de microblogage (service de messages courts), permettant à l’utilisateur de poster des brefs messages appelés tweets.

Plusieurs travaux de recherche ont exploré l’association d’un contenu textuel au contenu audiovisuel afin de déterminer les segments importants d’une vidéo. Twitter représente une source intéressante de telle information textuelle. Dans le cas de pro-grammes de télévision diffusés en direct, Twitter permet aux utilisateurs de discuter, d’exprimer leur opinion et de réagir en temps réel.

Le système EpicPlay [TB12] calcule, durant une émission de sport diffusée en direct, le nombre de tweets postés par minute. Cela permet l’élaboration d’une courbe dont les pics correspondent probablement à des événements intéressants. Le même principe a été utilisé par le système TwitInfo [MBB+11] où une étiquette est attribuée à chaque pic de la courbe. Les pics sont étiquetés par un terme, choisi à partir du texte des tweets, en utilisant le critère TF-IDF (term frequency inverse document frequency) [SJ72].

L’outil Statler présenté dans [SKC10], examine les tweets qui sont reliés à la diffusion en direct d’un évènement médiatique (pas forcément du sport). La relation entre le flux d’annotations Twitter et le flux du contenu médias est établie en se basant sur deux métriques. La première métrique est le taux de conversation (retweet) entre les auteurs des tweets. L’outil considère que les moments durant lesquelles les utilisateurs s’échangent le plus (en utilisant le caractère < @ >) sont des moments intéressants. La deuxième métrique est la taille des tweets : plus les tweets sont longs, plus l’événement correspondant est intéressant.

Une autre méthode est proposée dans [TYO11]. Le flux des tweets est considéré comme un flux de documents textuels. Les auteurs proposent une technique de sélection de tweets représentatifs. Elle s’appuie sur une méthode de clustering qui tient compte de l’information temporelle des documents. Cette technique est inspirée du problème Fa-cility Location Problem (figure 2.1). La similarité entre deux documents est calculée en tenant compte de la fréquence des mots communs entre eux et aussi de la distance temporelle qui les sépare. Le résumé est composé de l’ensemble des tweets sélectionnés avec leurs horodateurs (timestamps). Cette méthode peut générer à la fois un résumé tex-tuel et un résumé vidéo puisque chaque tweet sélectionné correspond à un événement intéressant dans la vidéo d’entrée.

Une autre méthode qui n’aborde pas explicitement la création de résumés vidéo, mais qui pourrait être utilisée comme une caractéristique supplémentaire et intéres-sante dans la création de ce type de résumés, est la méthode proposée par Zhao et al. dans [ZWV11]. Le but de cette méthode est d’extraire la réaction émotionnelle des téléspectateurs en temps réel envers un événement télévisé diffusé en direct. Les évé-nements sont détectés par une augmentation significative du nombre de tweets pendant une courte durée en utilisant une fenêtre temporelle glissante. Pour chaque événement, un ensemble de mots-clés caractérisant les tweets dans le voisinage de l’événement sont extraits. Ces mots-clés sont utilisés pour extraire un sentiment en le comparant à un ensemble de mots prédéfinis et représentant des classes de sentiments.

Ces approches, basées sur les tweets, sont puissantes, mais elles sont limitées aux programmes TV diffusés en direct qui sont très populaires et qui génèrent un grand nombre de tweets en temps réel. Les tweets doivent être associés à d’autres caracté-ristiques. Seuls, ils peuvent détecter des événements socialement importants, mais ne garantissent pas qu’un résumé basé sur ces événements soit intéressant et couvre l’en-semble des parties intéressantes de l’émission TV.

TRECVID (TREC Video Retrieval) est une campagne internationale annuelle d’évaluation proposée par le NIST (National Institute of Standard and Technology). Son objectif principal est de promouvoir la recherche dans l’analyse de contenus multimédia. TRECVID est souvent considéré comme le projet d’évaluation le plus complet de ces dernières an-nées. Une évaluation des résultats des participants est effectuée sur un corpus de très grande taille (plus de 35000 vidéos) en fournissant deux corpus vidéo différents : un cor-pus d’apprentissage et un corpus de test ainsi que des méthodes de mesure standards permettant de comparer les performances des différents systèmes proposés.

La campagne TRECVID comprend chaque année différentes tâches auxquelles les participants peuvent participer :

– détection de plans ;

– détection de copies vidéo ;

– détection des événements à partir de données de vidéo-surveillance ;

– indexation sémantique et extraction d’attributs de haut niveau (parole, inté-rieur/extérieur, …) ;

– recherche d’informations (personne, lieu, objet, …) ;

– création de résumés vidéo à partir des épreuves de tournage de BBC (BBC rushes).

Nous nous intéressons ici à la dernière tâche, celle de la création automatique de résumés vidéo à partir des épreuves de tournage provenant de l’archive de la chaîne TV BBC. Cette problématique était le sujet de nombreux travaux de recherche sur plusieurs  années (notamment 2007 [OSK07] et 2008 [OSA08]). Les épreuves de tournage (rushes) sont les vidéos originales produites lors des tournages et qui serviront par la suite pour le montage. Autrement dit, il s’agit de vidéos à l’état brut présentant une redondance importante. Contrairement aux vidéos éditées, les épreuves de tournage contiennent d’autres types d’informations redondantes comme par exemple les plans inutiles qui peuvent être insérés pendant l’enregistrement de la vidéo (mouvement intermédiaire de la caméra), ou encore les scènes enregistrées à maintes reprises. Le but principal de cette tâche est d’évaluer la capacité des méthodes, qui ont été développées dans ce cadre, à éliminer les parties répétitives et peu intéressantes. L’idée derrière ces méthodes est de sélectionner un ensemble de segments non redondants à partir des épreuves de tournage et de les assembler pour former un résumé. Ce dernier devrait présenter les objets prin-cipaux (fixes ou en mouvement) et les événements intéressants (principalement visuels) des épreuves de tournage tout en minimisant la durée totale qui respectera un rapport de compression minimal (inférieur ou égal à 4% de la durée initiale des épreuves).

Pour cette tâche, TRECVID fournit un corpus de résumés des épreuves de tournage de BBC générés avec un rapport de compression donné. Une base de vidéo MPEG-1 est aussi mise à disposition pour tester et évaluer les méthodes proposées. Le corpus d’apprentissage est composé de 57 vidéos (une totalité de 35 heures). Le corpus de test quant à lui contient 100 vidéos (une totalité de 48 heures).

De nombreuses méthodes ont été évaluées dans le cadre des compagnes TRECVID. La majorité des travaux effectués autour de la création de résumés vidéo à partir des épreuves de tournage s’appuient sur trois phases : (1) une phase de segmentation de la vidéo en un ensemble d’unités de base, (2) une phase de clustering des unités détectées et (3) une phase de sélection d’extraits à inclure dans le résumé. Les unités de base peuvent être des scènes, des plans, des sous-plans, des segments vidéo de durée fixe ou même des images de la vidéo.

Le plan est souvent considéré comme l’unité de base la plus appropriée pour la créa-tion de résumés. Dans ce cas, un clustering des plans est utilisé dans le but de détecter et éliminer les plans redondants. Certaines caractéristiques sont utilisées pour classer heu-ristiquement l’importance des plans telles que la couleur [NDM+08], les visages [BT08], la longueur des plans [SRT08], le mouvement de la caméra [KSV+08] ou l’intensité de mouvement que présente le plan [RJ09].

Dans [SRT08], le clustering des plans est effectué en formant un graphe dont les nœuds représentent tous les plans de la vidéo. Une arête non orientée est ajoutée entre chaque paire de nœuds et le poids de l’arête est la distance entre les deux images clés des deux plans en question. Un arbre couvrant de poids minimal est ensuite calculé. Toutes les arêtes restantes ayant un poids supérieur à un seuil sont supprimées faisant apparaître un ensemble de clusters de nœuds (plans). Le plan le plus long de chaque cluster est sélectionné. Le nombre de visages, l’intensité de mouvement et la taille du cluster sont utilisés pour classer et sélectionner parmi les plans candidats ceux à in-clure dans le résumé final. Truong et Venkatesh [TV06] ont classé les plans selon des descripteurs calculés par la méthode des SIFT (Scale-invariant feature transform) qui est une méthode permettant de transformer une image en un ensemble de vecteurs de ca-ractéristiques qui sont invariants par transformations géométriques usuelles [Low99]. Une image clé est sélectionnée à partir de chaque cluster de plans en se basant sur un ensemble de règles comme par exemple la sélection du visage le plus grand ou bien, dans l’absence de visages, la sélection de la plus longue distance relative avec la caméra. Dans [BT08], une première étape consiste à éliminer les plans courts (durée inférieure à 10 images). Le clustering effectué sur les plans restants, se base sur l’extraction de carac-téristiques visuelles telles que l’occurrence des visages et l’intensité du mouvement. Une version modifiée de l’algorithme de la plus longue sous-séquence commune est appli-quée. Les liens qui se chevauchent sont supprimés. Un extrait est sélectionné à partir de chaque cluster en se basant sur un ensemble de règles prédéfinies comme par exemple la durée minimale et maximale d’un extrait sélectionne, la durée entre deux extraits et la durée totale maximale de tous les extraits sélectionnés. Dans [WFW+08], un cluste-ring hiérarchique est effectué afin de sélectionner les images représentatives et éliminer les parties répétitives. La vidéo est segmentée tout d’abord en un ensemble de plans. Chaque plan est divisé en sous-plans. Un sous-plan inclut les images consécutives du plan qui sont très similaires. La similarité est calculée en utilisant un histogramme d’in-tersection des couleurs. Un seuil de similarité est fixé empiriquement, au dessus duquel deux plans sont considérés similaires. Enfin, chaque sous-plan est divisé en un ensemble de segments vidéo ayant chacun une durée égale à une seconde. Le résumé final est la concaténation d’un ensemble de ces segments d’une seconde. Une étape de filtrage des segments redondants et non utiles est réalisée : les segments d’une seconde contenant des images de couleur uniforme et les plans de durée très courts sont éliminés. Un score est calculé pour chaque segment d’une seconde en se basant sur des caractéristiques de bas niveau comme la couleur, les bordures, la détection de visages, le mouvement dominant et l’information audio. Après avoir été trié selon leurs scores, un ensemble de segments d’une seconde, ayant un score supérieur à un seuil, est sélectionné et concaténé pour former le résumé final. Un clustering est également effectué dans [LLR+08] pour la sélection des images clé en utilisant un histogramme local de couleur. L’approche consiste à décomposer une vidéo en plans et à appliquer, par la suite, un alignement global entre toutes les paires de plans. L’alignement est effectué en utilisant un algo-rithme d’alignement de séquences. Dans le système PICSOM [KSV+08], la sélection des extraits vidéo s’appuie sur une pondération linéaire pour favoriser les images à proxi-mité du centre de chaque plan de la vidéo. Les scores attribués aux extraits contenant des visages, de la parole, des objets ou du mouvement caméra sont par la suite in-crémentés selon des poids heuristiques. Ren et Jiang [RJ09] ont proposé une structure hiérarchique pour modéliser les épreuves de tournage (plan, sous-plans…) et ont utilisé le clustering basé sur l’algorithme des k plus proches voisins (K-NN) pour l’élimination de la redondance. Le plan le plus représentatif est sélectionné à partir de chaque cluster en fonction de sa longueur (le plan le plus long du cluster est sélectionné afin de maximi-ser la conservation du contenu visuel dans le résumé) et l’intensité de mouvement qu’il présente (maximiser la quantité de mouvement dans le résumé). Tang et al. [TZL+06] ont proposé un clustering basé sur la détection de caractéristiques de haut niveau comme les activités des personnages d’une scène, le dialogue entre les différents personnages et les la reconnaissance des bâtiments. L’élimination des plans répétitifs s’appuie sur l’extraction d’une tranche spatiotemporelle à partir de chaque plan plutôt que sur l’ex-traction d’uniquement une image représentative. Une tranche spatiotemporelle est un ensemble d’images consécutives extraites sur une période de temps. La similarité entre les tranches spatiotemporelles est calculée en comparant leurs histogrammes respectifs définis sur les différentes caractéristiques détectées. Afin d’effectuer un clustering sur les plans et éliminer la redondance, deux méthodes sont utilisées dans [QBPM+08] : l’algorithme des k plus proches voisins (K-NN) dans un premier temps et un clustering hiérarchique dans un second temps. Pour les deux méthodes, plusieurs attributs de bas et de moyen niveau sont détectés à partir des épreuves de tournage : activité de l’audio, activité du mouvement, images indésirables, visage et mouvement de la caméra. Une méthode ad-hoc de fusion des ces attributs hétérogènes est utilisée.

Contrairement aux méthodes déjà présentées dans cette section, dans [IS08], le clus-tering est effectué sur les scènes et non pas sur les plans. Des histogrammes de couleurs et de texture sont calculés pour chaque image de la vidéo. La vidéo est segmentée en un ensemble de scènes en calculant la distance euclidienne des couleurs moyennes des images successives. Les scènes dupliquées sont, par la suite, éliminées en se basant sur la couleur moyenne.

Le système cost292 [NDM+08] propose une méthode basée à la fois sur la détection de scènes et le clustering des plans. Outre la détection de visages et de mouvement de la caméra, les descripteurs de couleur MPEG-7 sont calculés pour chaque image de la vidéo et utilisés pour le clustering des plans et la détection de scènes. Les clusters sont formés à partir d’une matrice de similarité entre les images de la vidéo. Compte tenu des différents clusters formés et des différentes scènes détectées, des extraits minimisant les répétitions sont sélectionnés et ajoutés au résumé final.

Le problème de ce type d’approches réside dans le fait que ces approches sont lo-cales et utilisent uniquement l’information visuelle pour éliminer la redondance. Ces approches ne rentrent pas dans la compréhension de la scène et ne font pas une analyse approfondie qui va au delà de la redondance et de l’aspect visuel. De ce fait, seuls les plans visuellement similaires sont élagués. Deux cas d’utilisation peuvent illustrer ce problème :

• étant donné un ensemble de plans continus constituant une scène de la vidéo, l’uti-lisateur peut comprendre ce qui se passe dans la scène en regardant seulement un (ou quelques) plans. Toutefois, les plans d’une même scène peuvent ne pas être similaires et par conséquent appartenir à différents clusters. Des plans potentielle-ment non pertinents sont ainsi favorisés et inclus dans le résumé final ;

• étant donné deux plans visuellement similaires appartenant à deux scènes diffé-rentes ou à deux événements différents, l’élimination de l’un de ces plans via le clustering des plans entraînera une compréhension incomplète de l’événement en question dans le résumé.

Simplement accélérer la vitesse de lecture de la vidéo est une autre technique utilisée pour la création de résumés vidéo. L’être humain est capable de comprendre les événe-ments d’une vidéo accélérée jusqu’à 25 fois la vitesse initiale [HCL+07]. Tout comme la méthode de [PAS+99] présentée au début de la section 2.3, Christel et al. [CHL+08] ont participé à la tâche de TRECVID et ont présenté des travaux basés aussi sur l’accéléra-tion de la vidéo. Une première étape consiste à générer un résumé vidéo par accélération de 50 fois la vitesse de lecture de la vidéo originale. Les segments non pertinents sont par la suite détectés et supprimés. L’audio est ajouté au résumé pour améliorer sa com-préhension. Une reconnaissance automatique de la parole est tout d’abord effectuée. Le résultat du module de reconnaissance est divisée en phrases en fonction de la durée de silence dans le discours et de la détection d’un changement d’orateur. Un ensemble de phrases est sélectionné et ajouté au résumé sans tenir compte de la synchronisation entre la vidéo et l’audio. Cette approche permet de créer un résumé qui couvre la majorité de l’épreuve de tournage mais qui contient en contre partie beaucoup de redondance. Bien que cette approche nous permette de créer un résumé de durée réduite, ce dernier inclut inévitablement des parties redondantes ou inutiles.

TRECVID a défini une méthodologie d’évaluation de la qualité des résumés qui se base sur une combinaison de critères objectifs et subjectifs. Une évaluation subjective consiste à juger si le résumé créé inclut des segments intéressants de la vidéo originale et si le résumé contient des redondances. La subjectivité des ces critères vient en partie du fait que les segments jugés intéressants sont annotés par 5 évaluateurs qui sont chargés de créer une vérité terrain et d’attribuer un score pour chaque critère d’évaluation. D’un autre coté, une évaluation objective consiste à mesurer les performances des systèmes proposés tel que la durée du résumé créé et le temps pris par le système pour générer ce résumé.

Deux méthodes de base utilisant des techniques simples de création de résumés sont proposées pour comparer et évaluer les différents systèmes. La première méthode, ba-sique, est une méthode uniforme qui consiste à sélectionner périodiquement un extrait d’une seconde toutes les 25 secondes. Les extraits sont concaténés pour former le résumé final. La durée du résumé est de 4% la durée totale de la vidéo. La deuxième méthode est basée sur la détection des plans en utilisant un seuil sur la différence de la quan-tité de mouvement entre deux images consécutives. La méthode consiste à effectuer un clustering des K-moyennes sur les plans. Le nombre de clusters est égal au nombre de secondes dans le résumé de durée 4% de la durée totale de la vidéo. À partir de chaque cluster, le plan le plus proche du centroïde est sélectionné. Le résumé vidéo est le produit de la concaténation d’une seconde extraite du milieu de chaque plan sélectionné.