La segmentation en plans est l'identification automatique, par des méthodes informatiques, des bornes 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 évidemment connus du réalisateur de la vidéo, mais ne sont généralement 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, considéré comme étant une brique de base indispensable pour permettre l'analyse et la recherche de vidéos 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.. Il n'existe, au début des années 2000, que peu d'applications directes de la segmentation en plans pour le grand public, ou dans des logiciels de vidéo numérique. Toutefois, c'est une étape majeure dans l'analyse de la vidéo, permettant 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 donc pas à ce type de technique. Les vidéos généralement considérées sont des films ou des émissions de télévision.
La segmentation en plans est parfois (incorrectement) appelée « segmentation en scènes » 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., par certains chercheurs. La segmentation en scènes est toutefois 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 Yingying Zhu, Dongru Zhou, « Scene change detection based on audio and video content analysis », Coll. of Computer Science, Wuhan University, China, Fifth International Conference on Computational Intelligence and Multimedia Applications, 2003..
On peut aussi se référer à la segmentation en plans comme à un « inverse Hollywood problem » Mubarak Shah, « Guest Introduction: The Changing Shape of Computer Vision in the Twenty-First Century », International Journal of Computer Vision, Springer Netherlands, 2002., 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 très 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 généralement que deux types : les transitions brusques (appelées aussi coupures, de l'anglais « cut »), et les transitions progressives, qui incluent tous les autres types de transitions.
Historique
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. À ceci deux raisons principales : C'est une tâche relativement simple à réaliser, à interpréter, et à évaluer. L'identification des plans fournit un résultat considéré comme étant la première étape pour pouvoir résoudre les problèmes d'indexation vidéo de plus haut niveau. La performance des algorithmes de segmentation en plans est donc cruciale pour le domaine en général.
De très 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 du point de vue de la taille et du contenu. La création de TRECVID en 2003 a été une étape importante, car elle a introduit des mesures de performances standard et, surtout, 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 majoritairement).
Une initiative similaire a été lancée en France en 2005 sous le nom d'ARGOS, avec des contenus fournis par l'INA et le CERIMESARGOS Campagne d'évaluation d'outils de surveillance de contenus vidéo.
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 C. W. Ngo, T. C. Pong, R. T. Chin, « Detection of Gradual Transitions through Temporal Slice Analysis », CVPR, 1999..
En 2002, Alan Hanjalic, de l'Université de technologie de Delft, publie un article au titre provocateur : « Shot Boundary Detection: Unraveled and Resolved ? » (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 encore à 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 considérée 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 dissemblables. 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 distanceCe n'est pas toujours une distance au sens mathématique du terme. (ou mesure de similarité) entre observations. L'application de cette distance entre deux images successives, sur l'ensemble 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é.
Observations et distances
L'observation la plus simple est tout simplement l'ensemble des pixels de l'image. Pour 2 images et de dimension N×M, la distance évidente est alors la moyenne des différences absolues pixels à pixels (distance L1):
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 Kiyotaka Otsuji, Yoshinobu Tonomura, and Yuji Ohba, « Video browsing using brightness data », Visual Communications and Image Processing '91: Image Processing, 1991..
Malheureusement, les techniques dans le domaine pixellique sont très sensibles aux mouvements d'objets ou de caméra. Des techniques de bloc matching ont bien été proposées pour réduire la sensibilité au mouvement, mais les méthodes dans le domaine pixellique ont été largement supplantées par les méthodes basées sur les histogrammes.
L'histogramme, de luminance ou de couleur, est une observation très utilisée. Elle est facile à calculer, et est relativement robuste au bruit et aux mouvements d'objets, dû au fait qu'un histogramme ignore les modifications spatiales dans l'image. De très nombreuses techniques de calcul (sur l'image entière, sur des blocs...) et de distances (L1, la similarité cosinus, Test du χ²Akio Nagasaka Yuzuru Tanaka, « Automatic Video Indexing and Full-Video Search for Object Appearances », Second Working Conference on Visual Database Systems, 1991....) 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é John S. Boreczky and Lawrence A. Rowe, « Comparison of video shot boundary detection techniques », Storage and Retrieval for Image and Video Databases (SPIE), 1996..
Les méthodes utilisant l'histogramme souffrent toutefois de défauts importants : elles ne sont pas robustes à des changements brutaux d'illumination (flashs de photographes, soleil...), ni à des mouvements rapides.
Afin de résoudre ces problèmes, une autre observation est fréquemment utilisée Heng W.J.; Ngan K.N, « The implementation of object-based shot boundary detection using edge tracing and tracking », IEEE International Symposium on Circuits and Systems, 1999. Juan M. Sánchez, Xavier Binefa, Jordi Vitrià, « Shot Partitioning Based Recognition of TV Commercials », Multimedia Tools and Applications, 2002. : 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, éventuellement après recalage, les contours sont comparés. Cette technique est robuste au mouvement, ainsi qu'aux changements d'illumination 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.. En revanche, la complexité est élevée.
D'autres observations ont été proposées : caractérisation du mouvement de caméra P. Bouthemy, M. Gelgon, F. Ganansia. « A unified approach to shot change detection and camera motion characterization », Publication interne no1148, IRISA, novembre 1997., ou détection dans le domaine compressé à partir des coefficients DCTBoon-Lock Yeo, Bede Liu, « rapid scene analysis on compressed video », CirSysVideo(5), No. 6, December 1995. T. Kaneko, O. Hori, « Cut Detection Technique from MPEG Compressed Video Using Likelihood Ratio Test », ICPR, 1998., ou encore une combinaison d'observations, par exemple intensité et mouvement.
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 considéré Ba Tu Truong, Chitra Dorai, Svetha Venkatesh « New enhancements to cut, fade, and dissolve detection processes in video segmentation », Proceedings of the eighth ACM international conference on Multimedia, 2000..