Segmentation dense d’une séquence d’images au sens du mouvement

Télécharger le fichier pdf d’un mémoire de fin d’études

Méthodes séquentielles travaillant sur une paire d’i-mages consécutives

Cet ensemble de méthodes contient notamment des approches qui consistent à segmenter un champ dense de mouvement estimé au préalable [Wang 94a, Ayer 95, Pedersini 96] ; des approches qui, visant à obtenir une estimation plus précise du flot optique, proposent de travailler simultanément à l’estimation et la segmentation d’un champ dense de mouvement [Black 96a, Black 96b, Ju 96, Mémin 02] ; ainsi que des ap-proches qui cherchent à obtenir de manière directe la segmentation sans avoir à estimer explicitement le flot optique [Irani 92, Odobez 98, Cremers 05].
Lorsqu’une de ces méthodes est utilisée pour segmenter toute une séquence d’images, on imagine aisément que si chaque paire d’images consécutives est traitée de manière totalement indépendante, la cohérence temporelle entre les segmentations des diﬀérents instants n’est pas garantie. Pour tenter de remédier au problème, les traitements séquen-tiels de ce type utilisent généralement en guise d’initialisation à chaque nouvel instant t une carte de segmentation prédite ft0 par compensation de la carte de segmentation qui vient d’être obtenue pour l’instant t − 1.

Segmentation d’un champ de mouvement dense estimé au préa-lable

À partir d’un champ de mouvement dense estimé au préalable, Wang et Adel-son [Wang 94a] résument le problème de la segmentation basée sur le mouvement à la détermination d’un ensemble de modèles paramétriques décrivant au mieux le mou-vement « observé ». À partir d’une partition initiale régulière du champ dense de mouvement, un ensemble de modèles paramétriques de mouvement est estimé par ré-gression linéaire standard. Un modèle lié à une forte erreur résiduelle est considéré comme aberrant puisqu’il ne fournit pas une bonne description du mouvement pour la région sur laquelle il a été estimé. Il est donc éliminé. Des modèles présentant des paramètres de valeurs similaires sont regroupés par l’algorithme de clustering des k- moyennes dans l’espace des paramètres de mouvement, afin de produire un seul modèle à partir du centre du cluster. La segmentation se fait pixel à pixel en testant chacun des modèles-hypothèses, c’est-à-dire en calculant la distance euclidienne entre le vecteur de mouvement issu du champ dense et le vecteur de mouvement synthétisé à partir du modèle paramétrique testé. Chaque pixel est assigné au modèle qui décrit le mieux son mouvement, c’est-à-dire au modèle pour lequel cette distance est minimale. Si la distance minimale reste supérieure à un seuil donné, le pixel considéré n’est pas classé. De manière itérative, à partir de la nouvelle segmentation, les modèles de mouvement sont mis à jour et les ensembles connexes de pixels non-classés produisent de nouvelles hypothèses à condition que leur taille soit suﬃsante pour permettre l’estimation stable d’un modèle. Le processus d’assignation recommence avec les nouveaux modèles, ainsi de suite jusqu’à atteindre la stabilité lorsque peu de pixels changent encore de classe. La diﬀérence inter-images déplacée (« Displaced Frame Diﬀerence » (DFD)) est utilisée pour aﬃner la segmentation dans les régions toujours non-classées. Ces régions corres-pondent généralement à des régions proches des frontières de mouvement où le flot optique est moins précis. Pour l’image suivante, puisqu’a priori le mouvement évolue lentement d’une image à l’autre, les modèles et les régions resteront sensiblement les mêmes. Les modèles courants sont donc utilisés à nouveau pour classer les régions, et très peu d’itérations sont nécessaires pour atteindre la stabilité. La figure 1.3 présente le diagramme simplifié de l’algorithme.
Ayer et Sawhney [Ayer 95] proposent une première formulation probabiliste du pro-blème. Étant donnés les paramètres des modèles de mouvement, les distributions de probabilités des résidus sont modélisées par des mélanges de gaussiennes. Le nombre adéquat de modèles est déterminé en fonction de la complexité de la modélisation se-lon le principe « Minimum Description Length » (MDL) [Rissanen 83]. L’approche proposée fait appel à l’algorithme itératif d’EM (Espérance-Maximisation). L’étape E correspond à l’estimation des supports de couches par calcul des probabilités d’ap-partenance d’un pixel à une couche étant donnés le nombre de modèles, les estimées des paramètres de ces modèles et les variances. L’étape M correspond à l’estimation des nouveaux paramètres de mouvement, des nouvelles proportions des modèles et des nouvelles variances, étant donnés les nouveaux supports de couches.
Pedersini et al. [Pedersini 96] se basent principalement sur la méthode de Wang et Adelson [Wang 94a] mais procèdent à la classification en deux temps : d’abord la classification des régions « fiables » (i.e. sur lesquelles le champ de mouvement est jugé fiable), puis la classification des régions « non fiables ». Comme dans [Wang 94a], à partir d’une partition régulière de l’image, un modèle paramétrique est estimé pour chaque région par régression linéaire. Mais contrairement à [Wang 94a], l’estimation ne se fait non pas sur la région entière mais uniquement sur une portion de cette région, portion dont le champ de mouvement est jugé fiable via une procédure de seuil sur la DFD. C’est également la DFD, invoquant cette fois le vecteur de mouvement synthétisé à partir du modèle paramétrique testé, qui est utilisée comme critère de classification des régions « fiables ». Une approche de régularisation basée sur les modèles de champs de Markov aléatoires (« Markov Random Fields » (MRF)) est proposée pour obtenir la segmentation finale (y compris dans les régions « non fiables »). Si deux pixels voisins ont des vecteurs de mouvement diﬀérents, un terme de régularisation spatiale basé sur une mesure de régularité du champ de mouvement pénalise le fait de classer ces deux pixels dans une même région.

Estimation et segmentation simultanées du mouvement pour une estimation plus précise du flot optique

Dans les formulations classiques du problème de l’estimation du flot optique, l’hy-pothèse de conservation de l’intensité lumineuse et la contrainte de continuité spatiale sont violées entre autres dès que l’on considère plusieurs objets se déplaçant indépen-damment les uns des autres et générant des occultations. Black et Anandan [Black 96a] proposent une méthode pour estimer de manière robuste plusieurs mouvements para-métriques dans une même image. Appliquée aux formulations du flot optique, cette méthode robuste permet de réduire la sensibilité à ce type de violations.
Black et Jepson [Black 96b] segmentent d’abord une image en régions en s’appuyant sur l’information de luminance, puis ils estiment le mouvement dans chaque région en utilisant des modèles paramétriques de mouvement. Le mouvement peut être estimé de manière précise à condition que la segmentation fournie soit correcte, ce qui n’est pas garanti en utilisant seulement l’information de luminance.
Ju et al. proposent le modèle « Skin and Bones » [Ju 96]. Ils fixent une partition ré-gulière de l’image (des patchs de petite taille). Puisque ces patchs fixés peuvent contenir des régions de mouvement diﬀérent, ils modélisent dans chaque région plusieurs mou-vements aﬃnes en utilisant une procédure d’estimation en couches, extension directe des modèles de mélange [Jepson 93]. Ces patchs de mouvements aﬃnes constituent les « os » rigides et sont connectés entre eux par une « peau » flexible qui traduit une cohérence spatiale entre les paramètres de patchs voisins. Mémin et Pérez [Mémin 02] introduisent un modèle qui combine eﬃcacement un lissage local non paramétrique et une représentation paramétrique plus globale par régions. Le système proposé permet de procéder simultanément à l’estimation dense du mouvement préservant les discontinuités et à la segmentation basée sur le mouvement.

Segmentation paramétrique directe sans estimation de champ de mouvement

Irani et al. [Irani 92] proposent une approche hiérarchique descendante fonctionnant de manière séquentielle. Les couches de mouvement sont extraites une par une, par le biais d’estimations successives du mouvement dominant par la méthode de régression standard des moindres carrés. Une fois le mouvement dominant estimé, les régions correspondant à des résidus faibles sont détectées puis exclues de la région d’analyse avant que le processus soit relancé sur les données restantes. Néanmoins les méthodes de ce type ne fonctionnent généralement pas de manière satisfaisante en l’absence d’un mouvement dominant bien défini. D’autre part, une estimation imprécise du premier modèle de mouvement peut empêcher la bonne détection des autres mouvements.
Odobez et Bouthemy [Odobez 98] proposent une méthode de segmentation dite « directe » non seulement dans le sens où elle ne requiert pas l’estimation d’un champ de mouvement, mais aussi dans le sens où un estimateur robuste multi-résolution [Odobez 95] fournit en une seule itération des modèles paramétriques jugés suﬃsam-ment précis pour ne pas avoir à alterner les habituelles étapes d’estimation des modèles de mouvement et de classification dont les itérations jusqu’à convergence peuvent s’avé-rer très coûteuses en temps de calcul.
Cremers et Soatto [Cremers 05] encouragent une frontière de mouvement de lon-gueur minimale. Ils proposent donc deux représentations appropriées de cette frontière de mouvement. La première, assez contraignante, est basée sur les splines et permet par exemple de suivre un objet en mouvement. La seconde, plus avancée, est une formula-tion implicite basée sur les lignes de niveaux (« level sets »). Elle permet de segmenter plusieurs régions en mouvement. Néanmoins elle reste une approche locale, et ne permet donc pas de traiter convenablement le cas de nouveaux objets entrant dans la scène assez loin de la frontière en cours d’évolution.

Segmentation par regroupement de régions élémentaires four-nies par une sur-segmentation spatiale initiale

Morier et al. [Morier 97] proposent une méthode de représentation hiérarchique des séquences d’images. Cette méthode repose sur une technique de segmentation d’image basée sur des procédures de détection de contours et de fermeture de contours par croissance de régions [Benois-Pineau 92]. Les régions issues de cette segmentation spa-tiale initiale correspondent au niveau de base de la représentation hiérarchique. Les niveaux supérieurs sont construits par fusion progressive des régions sur des critères d’homogénéité de mouvement inspirés de ceux introduits dans [Wu 96].
Moscheni et al. [Moscheni 98] procèdent d’abord à la sur-segmentation de la pre-mière image de la paire en s’appuyant sur les informations de couleur. Ils aﬃnent ensuite cette sur-segmentation en vérifiant l’homogénéité spatio-temporelle propre à chacune des régions obtenues en considérant cette fois les deux images constituant la paire. Si nécessaire, une région peut être divisée à nouveau en régions plus petites, toujours en utilisant l’information de couleur. Les diﬀérentes couches de mouvement sont formées par regroupements successifs de deux régions voisines basés sur une mesure de similarité spatio-temporelle qui met en jeu, d’une part, les informations de mouvement contenues dans la représentation paramétrique et dans la distribution résiduelle des deux régions, et d’autre part, les luminances contenues sur la frontière commune aux deux régions.

Méthode travaillant sur une paire d’images distantes

Contrairement aux travaux mentionnés précédemment qui s’intéressent au mouve-ment estimé entre deux images consécutives, Wills et al. [Wills 03 ] ont développé une méthode de segmentation de deux images distantes pour lesquelles l’estimation du flot optique n’est pas eﬃcace car les mouvements présents sont relativement grands. En se basant sur des correspondances de points d’intérêt entre deux images distantes I et I0, Wills et al. proposent une variante de l’algorithme de RANSAC pour partitionner cet ensemble de correspondances et estimer un modèle homographique de mouvement pour chacun des groupes obtenus. La segmentation dense de l’image I (resp. I0) est obtenue par minimisation d’une fonction d’énergie globale composée d’un terme lié aux modèles « avant » (resp. « arrière ») de mouvement et d’un terme de lissage spatial. L’algorithme de graph-cuts est utilisé pour la minimisation de la fonction d’énergie. La cohérence temporelle entre les deux cartes de segmentation est finalement assurée par intersection des segmentations « avant » et « arrière ». La méthode proposée permet donc d’obtenir la segmentation dense de deux images distantes en ignorant totalement les images in-termédiaires. La segmentation de ces images intermédiaires n’est pas mentionnée dans l’article. Plusieurs exécutions, indépendantes les unes des autres, lancées sur diﬀérentes paires d’images distantes d’une même séquence n’assureront malheureusement pas une consistance temporelle des diﬀérentes segmentations.

Méthodes travaillant sur un groupe d’images

Cet ensemble regroupe des méthodes où les mouvements mis en jeu peuvent être estimés aussi bien entre images consécutives [Shi 98], qu’entre une image de réfé-rence fixée et des images pouvant être plus éloignées [Ke 01, Ke 02, Xiao 05b, Liu 05, Schoenemann 08]. Les travaux de Dupont et al. [Dupont 06b, Dupont 06c , Dupont 06a] font également partie de cet ensemble de méthodes mais sont décrits dans la section 1.5.

Mouvements estimés entre images consécutives seulement

Shi et Malik [Shi 98] n’utilisent pas le flot optique mais s’appuient tout de même sur une mesure locale, celle de distribution de probabilité de déplacement instantané en chaque pixel calculé entre images consécutives, mesure appelée « profil de mouvement ». La segmentation des images de la séquence se fait en construisant un graphe pondéré, dans lequel chaque nœud correspond à un pixel. Le voisinage spatio-temporel considéré autorise la création d’arcs entre pixels distants au plus de 3 images dans le temps et 5 pixels dans l’espace 2. En utilisant une simple corrélation croisée comme mesure de similarité entre les profils de mouvement de deux pixels voisins, le graphe est segmenté par le critère « normalized cut » qui revient à chercher les vecteurs propres d’une ma-trice associée au graphe. Seule l’information de mouvement est utilisée. L’approche est non-paramétrique et présente l’avantage de ne pas dépendre d’un état d’initialisation. Cependant, elle ignore toute contrainte globale, ce qui a le désavantage de la rendre instable pour des séquences bruitées, même légèrement.
L’approche est simultanée dans le sens où elle permet l’obtention de plusieurs cartes de segmentations à la fois. Toutefois, pour limiter le temps de calcul, les auteurs ont recours à deux stratégies. D’une part, le nombre de nœuds dans le graphe est limité en réduisant la résolution des images d’un facteur 3. D’autre part, le nombre d’images prises en compte simultanément est fixé : le traitement d’une longue séquence se fait finalement de manière séquentielle en utilisant une fenêtre temporelle glissante centrée sur chaque nouvel instant.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Introduction générale
I Segmentation d’une séquence d’images au sens du mouvement
Introduction de la première partie
1 État de l’art des méthodes de segmentation basée sur le mouvement
1.1 Présentation du problème et de son intérêt
1.1.1 Segmentation basée sur le mouvement
1.1.2 Définitions
1.2 Méthodes séquentielles travaillant sur une paire d’images consécutives
1.2.1 Segmentation d’un champ de mouvement dense
1.2.2 Estimation et segmentation simultanées du mouvement
1.2.3 Segmentation paramétrique directe
1.2.4 Segmentation par regroupement de régions élémentaires
1.3 Méthode travaillant sur une paire d’images distantes
1.4 Méthodes travaillant sur un groupe d’images
1.4.1 Mouvements estimés entre images consécutives seulement
1.4.2 Mouvements estimés entre une référence fixée et une deuxième image
1.5 Cheminement de Dupont et al
1.6 Problématique et approches proposées
1.6.1 Problématique
1.6.2 Approches proposées
2 Minimisation de l’énergie par coupe minimale/flot maximal
2.1 Notations et définitions relatives aux graphes
2.2 Équivalence entre coupe minimale et flot maximal dans un graphe
2.2.1 Algorithmes de flot maximal par saturation de chemins
2.2.2 Algorithmes de flot maximal par poussage de flot
2.2.3 Algorithmes récents de « Dynamic Graph Cuts » et « Active Cuts »
2.3 Minimisation d’une fonction d’énergie
2.3.1 Cas d’une classification binaire
2.3.2 Cas d’une classification multi-étiquettes
2.4 Relations de voisinage
2.5 Ajout de contraintes fortes
2.6 Alternatives importantes aux algorithmes de coupes de graphes
2.6.1 Le recuit simulé (« simulated annealing »)
2.6.2 Les modes conditionnels itérés (ICM)
2.6.3 La propagation bouclée de croyances (LBP)
2.6.4 L’algorithme « Tree-ReWeighted Message Passing » (TRW)
2.6.5 L’algorithme « Fast Primal-Dual » (Fast-PD)
2.7 Conclusion
3 Estimation du mouvement
3.1 Estimation de champs denses de mouvement
3.1.1 Contraintes locales
3.1.2 Méthodes fréquentielles
3.1.3 Méthodes de mise en correspondance de blocs
3.1.4 Méthodes différentielles
3.1.5 Approches multi-résolution
3.1.6 Filtre bilatéral
3.1.7 Estimateurs utilisés
3.2 Modèles de mouvement
3.2.1 Le modèle affine
3.2.2 Le modèle projectif
3.2.3 Modèles non paramétriques
3.2.4 Modèle retenu
3.2.5 Estimation des paramètres du modèle affine
4 Segmentation dense d’une séquence d’images au sens du mouvement
4.1 Critère lié au mouvement
4.1.1 Terme de mouvement basé sur la DFD
4.1.2 Extension à un triplet d’images
4.1.3 Terme de mouvement d’image à mosaïque
4.1.4 Corrélation croisée normalisée
4.1.5 Résidu entre vecteur et modèle de mouvement
4.1.6 Comparaison des différents termes
4.2 Critère d’apparence couleur
4.2.1 Nombre de gaussiennes que comporte un mélange
4.2.2 Estimation d’un mélange de gaussiennes
4.3 Contrainte temporelle
4.4 Contrainte de rigidité
4.5 Contrainte de lissage ou de régularisation spatiale
4.6 Prédiction de la segmentation et restriction de la région à segmenter
4.6.1 Prédiction de la segmentation
4.6.2 Restriction de la région à segmenter
4.7 Génération automatique des mosaïques de couches
4.8 Fonction d’énergie globale
4.8.1 Premier schéma basé sur les triplets d’images consécutives
4.8.2 Second schéma basé sur les mosaïques
5 Résultats expérimentaux
5.1 Résultats de segmentation du premier schéma
5.1.1 Résultats de segmentation sur la séquence Mobile & Calendar
5.1.2 Résultats de segmentation sur la séquence Flowergarden
5.1.3 Résultats de segmentation sur la séquence Carmap
5.1.4 Temps de calcul
5.2 Résultats de segmentation du second schéma
5.2.1 Validation de notre critère de mouvement entre image et mosaïque
5.2.2 Résultats de segmentation sur la séquence Flowergarden
5.2.3 Résultats de segmentation sur la séquence Carmap
5.3 Applications
5.3.1 Suppression d’un objet vidéo
5.3.2 Édition d’une mosaïque et propagation à toute la séquence
5.4 Aspects semi-automatiques
5.4.1 Segmentation interactive d’une image
5.4.2 Résumé des différents types d’interactions
5.5 Discussion
5.5.1 Sur le réglage des paramètres
5.5.2 Sur les aspects semi-automatiques
5.5.3 Sur l’apparition d’une nouvelle couche
5.5.4 Sur la durée des séquences traitées
Conclusion de la première partie
II Clustering d’un ensemble de trajectoires de points
Introduction de la deuxième partie
6 État de l’art des méthodes de clustering de trajectoires de points
6.1 Approches hiérarchiques
6.1.1 Hiérarchie, dendrogramme et algorithme d’agrégation
6.1.2 Distances entre séries temporelles
6.2 Approches de factorisation
6.2.1 Idée générale
6.2.2 Projection des trajectoires
6.2.3 Estimation des sous-espaces et clustering
6.2.4 Trajectoires de différentes longueurs
6.3 Approches de clustering spectral
6.4 Approches basées sur l’algorithme de RANSAC
6.4.1 Algorithme de RANSAC
6.4.2 Variantes de l’algorithme de RANSAC
6.5 Approche de Pundlik et Birchfield
6.6 Conclusions
7 Clustering de trajectoires de points de différentes longueurs
7.1 Nouvelle formulation du problème
7.1.1 Modèle de trajectoire affine
7.1.2 Erreur résiduelle de mouvement
7.2 Algorithme de clustering proposé
7.2.1 Adaptation de l’algorithme de J-linkage
7.2.2 Rejet des trajectoires aberrantes
7.3 Résultats expérimentaux sur la base de données Hopkins
7.4 Résultats expérimentaux sur des trajectoires de différentes longueurs
7.5 Classification a posteriori des trajectoires mises à l’écart
Conclusion de la deuxième partie
Conclusion générale
Glossaire
Bibliographie