Segmentation en plans

La segmentation en plans est l'identification automatique, par des méthodes informatiques, des limites des plans dans une vidéo.



Catégories :

Bon article - Indexation vidéo - Technique cinématographique

Recherche sur Google Images :


Source image : fr.wikipedia.org
Cette image est un résultat de recherche de Google Image. Elle est peut-être réduite par rapport à l'originale et/ou protégée par des droits d'auteur.

Page(s) en rapport avec ce sujet :

  • Plan ; Histogramme ; Analyse contenu ; Transition ; Détection ; Méthode... Segmentation ; Découpage ; Recherche information ; Enregistrement vidéo... (source : cat.inist)

La segmentation en plans est l'identification automatique, par des méthodes informatiques, des limites des plans dans une vidéo. Cela consiste à repérer automatiquement les points de montage définis à l'origine par le réalisateur, en mesurant les discontinuités entre les images successives de la vidéo. Ces points de montage sont bien entendu connus du réalisateur de la vidéo, mais ne sont le plus souvent pas divulgués, ou disponibles. Afin d'éviter à un opérateur humain un long et fastidieux repérage des plans par visionnage, des méthodes automatiques ont été développées par les chercheurs en informatique.

C'est le problème le plus ancien et le plus étudié en indexation vidéo, reconnu comme étant une brique de base indispensable pour permettre l'analyse et la recherche de vidéos[1]. Il n'existe pour le moment que peu d'applications directes de la segmentation en plans pour le grand public, ou dans des logiciels de vidéo numérique. Cependant, c'est une étape majeure dans l'analyse de la vidéo, donnant la possibilité la définition et l'utilisation de techniques de recherche d'information dans des vidéos.

Définition

La segmentation en plans consiste à déterminer les différents plans d'une vidéo. Ceci n'a de sens que si la vidéo contient effectivement des plans, c'est-à-dire qu'elle a été montée par un réalisateur. Certains types de vidéos (vidéo-surveillance, vidéos personnelles... ) ne se prêtent par conséquent pas à ce type de technique. Les vidéos le plus souvent reconnues sont des films ou des émissions de télévision.

La segmentation en plans est quelquefois (incorrectement) nommée «segmentation en scènes»[2], par certains chercheurs. La segmentation en scènes est cependant une tâche différente, qui consiste à identifier les scènes, cette notion étant définie comme un regroupement de plans partageant une certaine cohérence sémantique[3].

On peut aussi se référer à la segmentation en plans comme à un «inverse Hollywood problem»[4], pour souligner qu'il s'agit de l'opération inverse du montage : c'est la déconstruction de la vidéo afin d'identifier les briques de base filmées par le réalisateur : les plans.

Différents types de transitions entre plans

Il existe de particulièrement nombreuses façons de réaliser une transition entre deux plans. La plus simple est la transition brusque : on passe d'un plan à un autre sans image de transition. Pour rendre ce passage plus souple, les réalisateurs ont imaginé une grande variété de transitions progressives, les fondus au noir, les fondus enchaînés, les volets, et bien d'autres, rendues de plus en plus aisées par l'utilisation de l'informatique, et même de logiciels grand public de montage vidéo.

Pour la segmentation en plans, les chercheurs ne distinguent le plus souvent que deux types : les transitions brusques (appelées aussi coupures, de l'anglais «cut»), et les transitions progressives, qui incluent l'ensemble des autres types de transitions.

Historique

Un exemple de transition progressive : un fondu au noir.

Les premiers travaux sur la segmentation en plans remontent au début des années 1990. C'est la plus ancienne des tâches d'indexation vidéo et la plus explorée[1]. À ceci deux raisons principales :

De particulièrement nombreux algorithmes ont été publiés dans les années 1990 et 2000. Une difficulté importante est la comparaison des résultats des différents algorithmes proposés, testés sur des corpus différents en termes de taille et de contenu. La création de TRECVID en 2003 a été une étape importante, car elle a introduit des mesures de performances standard et , en particulier, des contenus communs, qui permettent une comparaison non biaisée des performances. La taille du corpus est assez importante (400 heures en 2007), mais le contenu reste assez homogène (journaux télévisés et documentaires surtout).

Une initiative identique a été lancée en France en 2005 sous le nom d'ARGOS, avec des contenus apportés par l'INA et le CERIMES[5].

Un autre problème lié à la performance des algorithmes apparaît dès les premières recherches. Si les résultats de détection pour les transitions brusques sont rapidement assez bons, ce n'est pas le cas pour les transitions progressives. On voit alors apparaître à la fin des années 1990 et au début des années 2000 de nombreux articles se concentrant sur les difficultés de détection des transitions progressives[6], [7], [8].

En 2002, Alan Hanjalic, de l'Université de technologie de Delft, publie un article au titre provocateur : «Shot Boundary Detection : Unraveled and Resolved ?»[1] (traduction : Segmentation en plans : un problème résolu ?), où il affirme que le problème principal des méthodes proposées est leur grande sensibilité aux valeurs de seuils, la conséquence étant que des réglages manuels doivent être effectués selon les types de vidéos à traiter. Il préconise alors l'emploi de techniques robustes de statistiques, basées sur la théorie de la décision.

Bien que de nombreux points soient toujours à résoudre (évaluation sur de grands corpus hétérogènes, performances faibles de la détection des transitions progressives, dépendance aux réglages manuels... ), Hanjalic officialise par le titre de son article, le fait que la segmentation en plans est reconnue par la communauté scientifique comme un problème «résolu».

Méthodes

L'idée principale à la base des méthodes de segmentation en plans est que les images au voisinage d'une transition sont fortement disidentiques. On cherche alors à repérer les discontinuités dans le flux vidéo.

Le principe général est d'extraire une observation sur chaque image, et de définir ensuite une distance[9] (ou mesure de similarité) entre observations. L'application de cette distance entre deux images successives, sur la totalité du flux vidéo, produit un signal unidimensionnel, dans lequel on cherche alors les pics (resp. creux si mesure de similarité), qui correspondent aux instants de forte dissimilarité.

Variations de la distance entre histogramme de luminance de 2 images successives sur la séquence d'introduction du film Le Seigneur des Anneaux. Les transitions brusques sont marquées par des ronds rouges, les transitions progressives par des triangles verts.

Observations et distances

Un exemple de transition progressive : un volet.

L'observation la plus simple est tout simplement la totalité des pixels de l'image. Pour 2 images I1 et I2 de dimension N×M, la distance évidente est alors la moyenne des différences absolues pixels à pixels (distance L1)  :

d(I_1,I_2)=\frac{1}{NM}\sum_{i=1}ˆ{N}\sum_{j=1}ˆ{M}|I_1(x_i,y_j)-I_2(x_i,y_j)|

Des approches plus raffinées peuvent ne mesurer que les changements significatifs, en filtrant les pixels qui génèrent des différences trop faibles, qui ne font qu'ajouter du bruit[10].

Malheureusement, les techniques dans le domaine pixellique sont particulièrement sensibles aux mouvements d'objets ou de caméra. Des techniques de bloc matching ont bien été proposées pour diminuer la sensibilité au mouvement, mais les méthodes dans le domaine pixellique ont été beaucoup supplantées par les méthodes basées sur les histogrammes.

L'histogramme, de luminance ou de couleur, est une observation particulièrement utilisée. Elle est facile à calculer, et est assez robuste au bruit ainsi qu'aux mouvements d'objets, dû au fait qu'un histogramme ignore les modifications spatiales dans l'image. De particulièrement nombreuses techniques de calcul (sur l'image entière, sur des blocs... ) et de distances (L1, la similarité cosinus, Test du χ²[11]... ) ont été proposées. Une comparaison des performances de différentes observations, sur des contenus vidéo variés, a montré que l'utilisation d'histogrammes produisait des résultats stables et de bonne qualité[12].

Les méthodes utilisant l'histogramme souffrent cependant de défauts importants : elles ne sont pas robustes à des changements brutaux d'illumination (flashs de photographes, soleil... ), ni à des mouvements rapides.

Pour résoudre ces problèmes, une autre observation est souvent utilisée[2], [13], [14], [15] : les contours de l'image. Ceux-ci sont détectés sur chaque image, grâce à une méthode de détection de contours et , peut-être après recalage, les contours sont comparés. Cette technique est robuste au mouvement, ainsi qu'aux changements d'illumination[14]. Par contre, la complexité est élevée.

D'autres observations ont été proposées : caractérisation du mouvement de caméra[16], ou détection dans le domaine compressé à partir des cœfficients DCT[17], [18], ou encore une combinaison d'observations, par exemple intensité et mouvement[2].

Détection des discontinuités

L'application d'une métrique sur les observations des images successives produit un signal unidimensionnel, dans lequel il faut alors identifier les discontinuités, qui indiquent un changement de plan.

La méthode la plus simple est un seuillage du signal, avec une valeur fixe. Cette méthode souffre de nombreux désavantages : adaptation manuelle du seuil selon le corpus, sensibilité au bruit, au mouvement... Une méthode plus robuste consiste à adapter localement le seuil, en le calculant, par exemple, comme étant la moyenne du signal dans une fenêtre autour du pic reconnu[19].

Une méthode plus satisfaisante est de déterminer la valeur du seuil à partir d'une estimation de la distribution des discontinuités[20]. La distribution est supposée gaussienne de paramètres \mathcal{N}(\mu,\, \sigmaˆ2) et le seuil est défini comme S = μ + rσ, où r est utilisé pour régler le nombre de fausses alarmes.

Une approche mieux fondée théoriquement est d'utiliser la théorie de la décision[18]. De façon classique, deux hypothèses sont définies pour chaque image : transition ou non-transition, et la décision est prise en comparant le rapport de vraisemblance au rapport des probabilités a priori. L'emploi d'une méthode d'estimation bayésienne sert à résoudre quelques problèmes liés à cette approche particulièrement simple[21].

Une méthode particulièrement différente est élaborée par Truong et al. [22], qui proposent de ne pas prendre une décision locale, mais une décision globale, en essayent de trouver la segmentation optimale sur la totalité de la vidéo reconnue. Les auteurs adoptent une démarche basée sur le maximum a posteriori, pour trouver la segmentation qui maximise la probabilité P (S | O) , la probabilité que la segmentation S soit optimale, connaissant les observations O. Afin d'éviter une exploration systématique de l'ensemble des segmentations envisageables, une technique de programmation dynamique est utilisée.

Améliorations

Un exemple de transition progressive complexe : un fondu enchaîné.

Les méthodes exposées jusque là ne sont pas forcément efficaces pour détecter les transitions progressives. Heng et al. [14] font remarquer que la majorité des méthodes sont basées sur une mesure de la différence des observations entre images adjacentes, et que ces différences peuvent être faibles pour des transitions progressives.

Pour résoudre ce problème, des techniques basées sur la détection et/ou le suivi d'objets ont été proposées[14]. L'idée générale est que le suivi d'un objet indique une continuité, et que la perte de suivi, peut indiquer une transition. D'autres proposent de modéliser particulièrement le comportement de chaque type de transition progressive (fondu au noir, fondu enchaîné, volet... ) par des méthodes heuristiques et des techniques de double seuillage[19], ou un réseau de neurones[6].

Les fondus enchaînés sont spécifiquement complexes à détecter, et certains travaux se concentrent seulement sur cette tâche[6]. D'autres se concentrent sur les volets, surtout parce que c'est une technique particulièrement utilisée à la télévision[7].

Un autre problème majeur est celui des changements brutaux d'illumination, flashs, spots, apparition/disparition du soleil... Des méthodes spécifiques ont été développées pour diminuer les fausses alarmes liées à ces évènements, en s'aidant de la détection de contours[13] ou d'un post-processing[19].

Performances

Les résultats de la segmentation en plans sont évalués par des mesures issues de la recherche d'information : la précision et le rappel.

Pour les transitions brusques, le calcul de ces deux mesures est simple : une transition est soit bien détectée, manquée, ou fausse. Pour les transitions progressives, qui s'étalent sur plusieurs images, on introduit quelquefois une mesure complémentaire, pour mesurer le nombre d'images effectivement correctement détectées. Suivant les auteurs, les résultats sont quelquefois évalués en distinguant les transitions brusques des transitions graduelles, ou quelquefois en mélangeant les résultats.

La comparaison des résultats entre les différents algorithmes est particulièrement délicate, surtout parce que les performances peuvent énormément fluctuer selon le corpus. Quelques tentatives de comparaison ont bien été lancées[23], [12], mais n'étaient pas totalement satisfaisantes. En 2001, la campagne d'évaluation TREC, originellement dédiée au texte, met en place une «video track», conçue pour l'évaluation des algorithmes pour la vidéo. En 2003, la tâche devient indépendante, sous le nom de TRECVID et met en place la mise à disposition d'un corpus commun et d'une évaluation indépendante.

Les résultats de ces campagnes d'évaluation confirment que les algorithmes ont atteint la maturité en ce qui concerne les transitions brusques, avec de nombreux scores de rappel et de précision supérieurs à 90%. La détection des transitions progressives est , par contre, toujours une tâche complexe, avec des scores généralement de 70% en précision et rappel, les meilleurs algorithmes atteignant quelquefois péniblement les 80%[24].

La complexité des méthodes est aussi évaluée, et est particulièrement différente selon les algorithmes, allant de 20 fois plus rapide que le temps réel, à plus de 20 fois plus lent[24].

Applications

La segmentation en plans est le plus souvent reconnue comme étant de trop bas niveau pour être utilisée telle quelle dans une application de navigation et recherche d'information vidéo. Une avance rapide plan par plan peut cependant avantageusement remplacer une avance rapide respectant les traditions, basée sur un simple saut d'un nombre fixe d'images.

La principale application de la segmentation en plans est d'apporter une base de travail aux algorithmes d'indexation vidéo qui plus est haut niveau. Par exemple pour la détermination des scènes[3], réaliser des résumés vidéo[25], ou encore l'analyse de vidéos de sport[26].

Certains logiciels de montage vidéo, par exemple Windows Movie Maker et VirtualDub, utilisent la segmentation en plans pour générer un pré-découpage pour l'utilisateur, qui sert à faire du montage non linéaire simplement. Pour les cinéphiles intéressés par l'analyse de films, ces techniques peuvent peut-être avoir un intérêt pour déterminer automatiquement le nombre de plans dans un film et leur localisation.

La segmentation en plans est aussi utilisée dans les techniques de restauration d'image, pour la correction des défauts inhérents aux changements de plan, tels que les échos d'étalonnage et les déformations d'image.

Notes et références

  1. abcd (en) Alan Hanjalic, «Shot-boundary detection : unraveled and resolved ?», Fac. of Inf. Technol. & Syst., Delft University of Technology, IEEE Transactions on Circuits and Systems for Video Technology, Feb 2002.
  2. abc (en) Chung-Lin Huang, Bing-Yao Liao, «A robust scene-change detection method for video segmentation», IEEE transactions on circuits and systems for video technology, December 2001.
  3. ab (en) Yingying Zhu, Dongru Zhou, «Scene change detection based on audio and video content analysis», Coll. of Computer Science, Wuhan University, China, Fifth Mondial Conference on Computational Intelligence and Multimedia Applications, 2003.
  4. (en) Mubarak Shah, «Guest Introduction : The Changing Shape of Computer Vision in the Twenty-First Century», Mondial Journal of Computer Vision, Springer Netherlands, 2002.
  5. ARGOS Campagne d'évaluation d'outils de surveillance de contenus vidéo
  6. abc (en) Rainer Lienhart, «Reliable Dissolve Detection», Mondial Journal of Image and Graphics, 2001.
  7. ab (en) Min Wu, Wayne Wolf, Bede Liu, «An Algorithm For Wipe Detection», 1998
  8. (en) C. W. Ngo, T. C. Pong, R. T. Chin, «Detection of Gradual Transitions through Temporal Slice Analysis», CVPR, 1999.
  9. Ce n'est pas forcément une distance au sens mathématique du terme.
  10. (en) Kiyotaka Otsuji, Yoshinobu Tonomura, and Yuji Ohba, «Video browsing using brightness data», Visual Communications and Image Processing'91 : Image Processing, 1991.
  11. Akio Nagasaka Yuzuru Tanaka, «Automatic Video Indexing and Full-Video Search for Object Appearances», Second Working Conference on Visual Database Systems, 1991.
  12. ab (en) John S. Boreczky and Lawrence A. Rowe, «Comparison of video shot boundary detection techniques», Storage and Retrieval for Image and Video Databases (SPIE), 1996.
  13. ab (en) Heng W. J. ; Ngan K. N, «The implementation of object-based shot boundary detection using edge tracing and tracking», IEEE Mondial Symposium on Circuits and Systems, 1999.
  14. abcd (en) Heng W. J. ; Ngan K. N, «High accuracy flashlight scene determination for shot boundary detection», Signal Processing : Image Communication, Volume 18, Number 3, March 2003.
  15. (en) Juan M. Sánchez, Xavier Binefa, Jordi Vitrià, «Shot Partitioning Based Recognition of TV Commercials», Multimedia Tools and Applications, 2002.
  16. (en) P. Bouthemy, M. Gelgon, F. Ganansia. «A unified approach to shot change detection and camera motion characterization», Publication interne no1148, IRISA, novembre 1997.
  17. Boon-Lock Yeo, Bede Liu, «rapid scene analysis on compressed video», CirSysVideo (5), No. 6, December 1995.
  18. ab (en) T. Kaneko, O. Hori, «Cut Detection Technique from MPEG Compressed Video Using Likelihood Ratio Test», ICPR, 1998.
  19. abc (en) Ba Tu Truong, Chitra Dorai, Svetha Venkatesh «New enhancements to cut, fade, and dissolve detection processes in video segmentation», Proceedings of the eighth ACM mondial conference on Multimedia, 2000.
  20. (en) A. Hanjalic, M. Ceccarelli, R. L. Lagendijk, J. Biemond, «Automation of Systems Enabling Search on Stored Video Data», Storage and Retrieval for Image and Video Databases, 1997
  21. (en) Nuno Vasconcelos, Andrew Lippman, «A Bayesian Video Modeling Framework for Shot Segmentation and Content Characterization», Workshop on Content-Based Access of Image and Video Libraries, 1997.
  22. (en) Ba Tu Truong, Venkatesh, S., «Finding the Optimal Temporal Partitioning of Video Sequences», IEEE Mondial Conference on Multimedia and Expo, 2005.
  23. Rainer Lienhart, «Comparison of automatic shot boundary detection algorithms», Storage and Retrieval for Image and Video Databases (SPIE), 1998.
  24. ab (en) TRECVid 2006, «Shot Boundary Task Overview»,
  25. (en) Hsuan-Wei Chen, Jin-Hau Kuo, Wei-Ta Chu, Ja-Ling Wu, «Action movies segmentation and summarization based on tempo analysis», ACM SIGMM mondial workshop on Multimedia information retrieval, 2004.
  26. Ewa Kijak, «Structuration multimodale des vidéos de sports par modèles stochastiques», Thèse de l'Université de Rennes 1, IRISA, Décembre 2003.

Recherche sur Amazone (livres) :




Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Segmentation_en_plans.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 15/04/2009.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu