Soutenance mémoire
Qu’est ce qu’un document vidéo ?
Sans rentrer dans les différents types de codage et de compression, un document vidéo peut être vu comme étant la combinaison de deux modes : la vidéo et l’audio, représentés dans un espace discret de temps associé, en général, à une fréquence d’échantillonnage plus élevée que les changements d’états qu’il reflète, ce qui permet au spectateur de le percevoir comme étant continu. Pour simplifier, on peut le définir comme un ensemble de séquences d’images synchronisées avec une ou plusieurs bandes son, formant un tout complet. Ses niveaux hiérarchiques sont : le document complet, l’unité narrative, la scène, le plan, puis l’image. Cette dernière, n’ayant pas un équivalent structurel sur la bande son (la « slice » audio associée à une image dans les fichiers mpeg n’a pas d’autre sens que celui d’être un fragment sonore sur une durée d’1/25ème de seconde) et ne reflétant pas non plus la notion du temps, ne peut former à elle seule un document vidéo : au moins deux images sont nécessaires pour cela. Jusqu’à nos jours c’est le document le plus riche, en matière de sens. Il est composé des seuls deux sens transportables à distance, parmi les cinq avec lesquelles l’homme peut communiquer. Nous comprenons donc pourquoi ce genre de documents prend toute cette importance dans notre vie quotidienne et, par conséquence, dans nos laboratoires.
Analyse vidéo : où sommes nous actuellement ?
La segmentation vidéo comprend la segmentation temporelle, telle que la détection des changements de plan et la détection d’effets de transition spéciaux, et la segmentation spatio-temporelle, telle que la segmentation en objets et leurs suivis. L’indexation vidéo comprend l’indexation bas niveau, telle que l’utilisation des caractéristiques ou des descripteurs comme la couleur, la texture, la forme et le mouvement; l’indexation de niveau sémantique, dite aussi haut niveau, telle que la classification de plans, la segmentation en unités narratives, la détection et l’identification des personnes, et la construction des résumés vidéo, tel que les résumés par images clés ou par détection d’événements importants [Tekalp 04].
La segmentation vidéo
On distingue deux types de segmentation vidéo : la segmentation temporelle et la segmentation spatio-temporelle.
La segmentation temporelle
La segmentation en plans est la technique de segmentation temporelle des enregistrements vidéo la plus répandue et la plus utilisée. Les méthodes de détection de changements de plan localisent les images, à travers lesquelles de grandes différences sont observées dans un certain espace de caractéristiques [Gargi 00, Lienhart 01, Hanjalic 02]. L’espace de caractéristiques se compose habituellement d’une combinaison de couleur et de mouvement. Les changements de plan peuvent être instantanés (cuts) ou apparaître sur plusieurs images, appelés les effets de transition progressifs, tels que les fondus et les volets. Il est plus facile de détecter des cuts que des effets progressifs. La méthode la plus simple pour la détection des cuts est d’analyser les variations d’intensité des pixels entre les images successives. Si un nombre prédéterminé de pixels montre des différences plus grandes qu’une certaine « valeur seuil », alors l’occurrence d’un cut peut être déclarée. Une approche légèrement différente consiste à diviser chaque image en blocs rectangulaires, à opérer des évaluations statistiques dans chaque bloc indépendamment, et à vérifier alors que le nombre de blocs qui ont globalement été modifiés est supérieur à un seuil. Les deux approches peuvent être sensibles au bruit et à la compression. Cependant, il existe de nombreuses solutions qui s’appliquent à la vidéo de manière générique avec une précision plus qu’acceptable [Gargi 00, Lienhart 01, Hanjalic 02]. La micro-segmentation est une segmentation temporelle à une échelle encore plus petite que celle du plan. Elle est basée sur la segmentation en événements, en mouvements de caméra, en entrée-sortie d’objets ou de personnages [Joly 96]. Par opposition, la macrosegmentation effectue une segmentation qui se rapproche de la composition sémantique des documents (segmentation en séquences, en chapitres, en programmes) [Aigrain 95].
Segmentation spatio-temporelle
La segmentation en objets n’est pas un problème facile, principalement parce que la définition des objets vidéo exige habituellement une interprétation sémantique de la scène. Il n’est généralement pas possible de définir de tels objets, sémantiquement significatifs, en termes de caractéristiques de bas niveau, tels que des paramètres de mouvement ou de couleur. Par conséquent, la segmentation et le suivi d’objets sémantiques dans une scène sans contrainte peuvent exiger l’intervention interactive de l’utilisateur. Cependant, dans quelques circonstances bien contraintes, des objets sémantiques peuvent être segmentés et suivis entièrement automatiquement. Par exemple, dans les systèmes de vidéo surveillance [Courtney 97, Foresti 02], où la caméra est stationnaire, des objets dans la scène peuvent être extraits par des méthodes simples de soustraction et de détection de changement d’arrière plan.
Indexation vidéo
Parmi les grandes familles d’outils d’indexation dédiés spécifiquement aux contenus vidéo, on trouve les outils d’indexation de bas niveau, et ceux effectuant une analyse sémantique.
Indexation de bas niveau
Des descripteurs de bas niveau, tels que la couleur, la texture, la forme, et le mouvement, peuvent être associés aux plans ou aux objets. La couleur des images choisies peut être décrite par l’histogramme de couleur ou par les couleurs dominantes [Manjunath 02]. Les paramètres de mouvement de caméra et le taux d’activité décrivent le mouvement au niveau du plan [Manjunath 02, Tan 00]. Le mouvement des objets peut être décrit par des trajectoires [Dagtas 00]. Les sommaires d’images clés et les sommaires de segments importants sont généralement employés dans des applications commerciales. Les images clés, qui se rapportent à une ou plusieurs images représentatives dans un plan, fournissent une représentation compacte. Plusieurs méthodes existent pour choisir automatiquement les images clés par l’analyse des caractéristiques de bas niveau [Dimitrova 02, Antani 02].
Analyse sémantique
L’information sémantique peut être représentée par des annotations structurées ou du texte libre, ou par des modèles sémantiques. Les annotations peuvent être manuelles, ou extraites automatiquement à partir du sous-titrage, par la détection et l’identification de visages, de décors, ou d’actions modélisés spécifiquement. Les modèles sémantiques peuvent décrire des entités, telles que des objets et des événements, et des relations entre elles, qui rendent possible le traitement des requêtes complexes. Certains modèles sémantiques sont considérés comme prolongements des modèles d’Entité Relation (ER) développés pour des documents par les communautés de recherche de base de données et documentaire. L’analyse sémantique de la vidéo induit généralement l’utilisation des caractéristiques cinématographiques et basées Objet. Les caractéristiques cinématographiques ont pour origine l’application de règles classiques de montage et de production, telles que les procédés de réalisation des effets de transitions. Les différentes règles cinématographiques peuvent s’appliquer à différents genres. Par exemple, les films d’action, les séries de télévision, les journaux d’infos, et toutes les émissions de sports ont différentes caractéristiques cinématographiques [Hampapur 02b, Sundaram 02, Ekin 03]. Les méthodes de segmentation et d’identification d’objets peuvent également être employées pour la détection des événements importants [Satoh 01].
|
Table des matières
INTRODUCTION GENERALE
0.1 Motivation
0.2 Problématique et objectifs de la thèse
0.2.1 Problématique
0.2.2 Objectifs
0.3 Organisation de la thèse
1 CHAPITRE 1 : ETAT DE L’ART
1.1 Introduction
1.2 Partie vidéo : Mesures de similarité
1.2.1 Qu’est ce qu’un document vidéo ?
1.2.2 Analyse vidéo : où sommes nous actuellement ?
1.2.2.1 La segmentation vidéo
1.2.2.1.1 La segmentation temporelle
1.2.2.1.2 Segmentation spatio-temporelle
1.2.2.2 Indexation vidéo
1.2.2.2.1 Indexation de bas niveau
1.2.2.2.2 Analyse sémantique
1.2.2.3 Situation actuelle
1.2.3 Qu’est ce qu’une mesure de similarité
1.2.3.1 Une mesure de similarité pour quoi faire ?
1.2.3.2 Quelques définitions
1.2.3.3 Les différentes approches de comparaisons et de mesures
1.2.4 Etat de l’art des mesures de similarité
1.2.4.1 Mesures s’inspirant de celles appliquées aux images
1.2.4.2 Mesures intégrant la dimension du temps
1.2.4.3 Les méthodes avec modèles à priori
1.2.4.4 Méthodes d’échantillonnage
1.2.4.5 Mesure de comparaison générique
1.2.4.6 Mesures permettant d’identifier les copies sans modèles à priori
1.2.4.6.1 Particularité
1.2.4.6.2 Les extractions de répétitions
1.2.4.6.3 Recherche dans les bases de données
1.2.5 Recherche sans considération de l’ordre temporel
1.2.5.1 Mesures permettant la classification en genre
1.2.6 Limites
1.3 Séries chronologiques et méthodes de comparaison
1.3.1 Définitions
1.3.2 Notation
1.3.3 Formulation du problème de la comparaison de séries chronologiques
1.3.4 Les solutions par utilisation de distances
1.3.4.1 Distance de Minkowski
1.3.4.2 Changement d’espaces de représentation
1.3.5 Programmation dynamique
1.3.5.1 Définition
1.3.5.2 La comparaison par déformation temporelle dynamique (DTW)
1.3.6 La distance d’édition
1.3.6.1.1 La distance d’édition pour les séquences de texte
1.3.6.1.2 La distance d’édition et les séquences numériques
1.3.6.2 La plus longue sous séquence commune (PLSC ou LCSS)
1.3.6.2.1 La PLSC pour les séries chronologiques
1.3.6.2.2 Transformations
1.3.6.3 Les méthodes d’approximations du calcul de la PLSC
1.4 Conclusion
2 CHAPITRE 2 : MATRICE DE COMPARAISON
2.1 Introduction
2.2 Stratégie de comparaison des caractéristiques audiovisuelles
2.3 Comparaison de deux séries temporelles
2.3.1 Notations et conventions
2.3.2 IQR : algorithme de l’intersection quadratique récursive
2.3.3 ESSV : algorithme d’extraction des séquences similaires de taille variable
2.3.4 CC : algorithme de calcul du taux de couverture
2.3.5 DiSC : algorithme de comparaison Dichotomique des Séries Chronologiques
2.3.6 Extension pour deux séries de tailles quelconques
2.3.7 Comparaison du CC avec PLSC
2.3.7.1 Algorithme PLSC
2.3.7.2 Comparaison théorique de la complexité
2.3.7.3 Défaut de l’algorithme CC
2.3.7.4 Comparaison expérimentale de complexité et de performance
2.3.8 Comparaison des séquences par morceaux
2.4 Calcul des enveloppes morphologiques de séries chronologiques
2.4.1 Définitions de morpho mathématiques
2.4.2 Deux opérateurs morphologiques : la dilatation et l’érosion
2.4.3 La construction de l’enveloppe morphologique
2.5 Algorithme de comparaison pour une caractéristique audiovisuelle
2.5.1 Typologie des courbes
2.5.2 Comparaison par intersection d’enveloppes
2.5.3 Adaptation de l’algorithme CC
2.5.4 Le structurant morpho mathématique
2.5.5 Entre l’ «efficacité » et la « précision »
2.5.5.1 Le paramètre tMax
2.5.5.2 Le paramètre tMin
2.5.6 Comparaison du PLSC et du CC après adaptation des paramètres
2.5.7 Exemples et résultats
2.6 Matrice de comparaison
2.6.1 Principe
2.6.2 Construction
2.6.3 Remarques
2.6.4 Fusion inter-caractéristiques
2.6.5 Exemples et résultats
2.7 Conclusion
3 CHAPITRE 3 : MESURE DE SIMILARITE
3.1 Introduction
3.2 La similarité entre deux documents vidéo
3.2.1 Une autre définition pour un document vidéo
3.2.2 Définition de l’événement
3.2.3 Définition de l’espace des événements
3.2.4 Exemple
3.2.5 Taille des événements
3.2.6 Nécessité d’une mesure de similarité
3.2.7 Relativité de la similarité
3.2.7.1 Contexte de la mesure
3.2.7.2 Contenu versus composition temporelle
3.2.7.3 La détection de l’invariance
3.2.8 Transitivité de la similarité
3.3 Mesure de similarité de style
3.3.1 Interprétation de la matrice
3.3.2 Densité et répartition des votes
3.3.2.1 Première mesure intuitive
3.3.2.2 Pondération des votes
3.3.3 Identification de scénarios
3.3.3.1 Décalage constant du temps
3.3.3.2 Décalage variable du temps
3.3.3.3 Synchronisme symétrique
3.3.3.4 Synchronisme asymétrique
3.3.3.5 Cas général : combinaison de scénarios
3.3.4 La fonction de pondération
3.3.5 Normalisation des poids
3.3.6 Normalisation des diagonales
3.3.7 Définition de la mesure de similarité
3.4 Pseudo distance de similarité
3.4.1 Pourquoi une distance ?
3.4.2 Proposition d’une pseudo-distance
3.4.3 Mesure de similarité versus pseudo-distance de similarité
3.5 Conclusion
4 CHAPITRE 4 : APPLICATIONS
4.1 Introduction
4.2 Méthodologie
4.2.1 Extraction des caractéristiques
4.2.2 Lecture des matrices de similarités
4.3 Caractéristiques utilisées
4.3.1 Caractéristiques vidéo
4.3.1.1 Outil d’extraction baseindexvid
4.3.1.2 Les deux couleurs dominantes
4.3.1.3 La luminance moyenne
4.3.1.4 Le contraste
4.3.1.5 Les orientations et granularités de texture
4.3.1.6 Le taux d’activité
4.3.2 Caractéristiques audio
4.3.2.1 Outil d’extraction des caractéristiques audio
4.3.2.2 Modulation de l’énergie à 4 Hertz
4.3.2.3 Modulation de l’entropie
4.3.2.4 Paramètres de segmentation
4.4 Conception et mise en œuvre technique
4.4.1 Décodage vidéo
4.4.2 Outils d’extraction et de comparaison
4.4.3 Parallélisation
4.5 Expérience 1 : Etude du style d’un film de cinéma
4.5.1 Description et but
4.5.1.1 Conditions de l’expérience
4.5.2 La matrice de Matrix
4.5.3 Analyse diagonale de la matrice
4.5.4 Analyse de l’effet « PostProduction »
4.5.5 Evaluation Technique
4.6 Expérience 2 : Structuration des flux de télévision
4.6.1 Macro structuration
4.6.2 Description et but
4.6.3 Paramétrisation de tMin et tMax
4.6.4 Analyse des résultats
4.6.4.1 Analyse diagonale de la matrice
4.6.4.2 Analyse globale
4.6.5 Evaluation Technique
CONCLUSION GENERALE
