Méthodes de graphe pour la segmentation d'images et le suivi d'objets dynamiques

Doctoral thesis English OPEN
Wang , Xiaofang (2015)
  • Publisher: HAL CCSD
  • Subject: Superpixels | Graph based methods | [ SPI.OTHER ] Engineering Sciences [physics]/Other | Image segmentation | Segmentation d'image | Méthodes de graphes

Image segmentation is a fundamental problem in computer vision. In particular, unsupervised image segmentation is an important component in many high-level algorithms and practical vision systems. In this dissertation, we propose three methods that approach image segmentation from different angles of graph based methods and are proved powerful to address these problems. Our first method develops an original graph construction method. We also analyze different types of graph construction method as well as the influence of various feature descriptors. The proposed graph, called a local/global graph, encodes adaptively the local and global image structure information. In addition, we realize global grouping using a sparse representation of superpixels’ features over the dictionary of all features by solving a l0-minimization problem. Extensive experiments are conducted on the Berkeley Segmentation Database, and the proposed method is compared with classical benchmark algorithms. The results demonstrate that our method can generate visually meaningful partitions, but also that very competitive quantitative results are achieved compared with state-of-the-art algorithms. Our second method derives a discriminative affinity graph that plays an essential role in graph-based image segmentation. A new feature descriptor, called weighted color patch, is developed to compute the weight of edges in an affinity graph. This new feature is able to incorporate both color and neighborhood information by representing pixels with color patches. Furthermore, we assign both local and global weights adaptively for each pixel in a patch in order to alleviate the over-smooth effect of using patches. The extensive experiments show that our method is competitive compared to the other standard methods with multiple evaluation metrics. The third approach combines superpixels, sparse representation, and a new midlevel feature to describe superpixels. The new mid-level feature not only carries the same information as the initial low-level features, but also carries additional contextual cue. We validate the proposed mid-level feature framework on the MSRC dataset, and the segmented results show improvements from both qualitative and quantitative viewpoints compared with other state-of-the-art methods. Multi-target tracking is an intensively studied area of research and is valuable for a large amount of applications, e.g. video surveillance of pedestrians or vehicles motions for sake of security, or identification of the motion pattern of animals or biological/synthetic particles to infer information about the underlying mechanisms. We propose a detect-then-track framework to track massive colloids’ motion paths in active suspension system. First, a region based level set method is adopted to segment all colloids from long-term videos subject to intensity inhomogeneity. Moreover, the circular Hough transform further refines the segmentation to obtain colloid individually. Second, we propose to recover all colloids’ trajectories simultaneously, which is a global optimal problem that can be solved efficiently with optimal algorithms based on min-cost/max flow. We evaluate the proposed framework on a real benchmark with annotations on 9 different videos. Extensive experiments show that the proposed framework outperforms standard methods with large margin.; Cette thèse est proposée en deux parties. Une première partie se concentre sur la segmentation d’image. C’est en effet un problème fondamental pour la vision par ordinateur. En particulier, la segmentation non supervisée d’images est un élément important dans de nombreux algorithmes de haut niveau et de systèmes d’application. Dans cette thèse, nous proposons trois méthodes qui utilisent la segmentation d’images se basant sur différentes méthodes de graphes qui se révèlent être des outils puissants permettant de résoudre ces problèmes. Nous proposons dans un premier temps de développer une nouvelle méthode originale de construction de graphe. Nous analysons également différentes méthodes similaires ainsi que l’influence de l’utilisation de divers descripteurs. Le type de graphe proposé, appelé graphe local/global, encode de manière adaptative les informations sur la structure locale et globale de l’image. De plus, nous réalisons un groupement global en utilisant une représentation parcimonieuse des caractéristiques des superpixels sur le dictionnaire de toutes les caractéristiques en résolvant un problème de minimisation l0. De nombreuses expériences sont menées par la suite sur la base de données <Berkeley Segmentation>, et la méthode proposée est comparée avec des algorithmes classiques de segmentation. Les résultats démontrent que notre méthode peut générer des partitions visuellement significatives, mais aussi que des résultats quantitatifs très compétitifs sont obtenus en comparaison des algorithmes usuels. Dans un deuxième temps, nous proposons de travailler sur une méthode reposant sur un graphe d’affinité discriminant, qui joue un rôle essentiel dans la segmentation d’image. Un nouveau descripteur, appelé patch pondéré par couleur, est développé pour calculer le poids des arcs du graphe d’affinité. Cette nouvelle fonctionnalité est en mesure d’intégrer simultanément l’information sur la couleur et le voisinage en représentant les pixels avec des patchs de couleur. De plus, nous affectons à chaque pixel une pondération à la fois local et globale de manière adaptative afin d’atténuer l’effet trop lisse lié à l’utilisation de patchs. Des expériences approfondies montrent que notre méthode est compétitive par rapport aux autres méthodes standards à partir de plusieurs paramètres d’évaluation. Finalement, nous proposons une méthode qui combine superpixels, représentation parcimonieuse, et une nouvelle caractéristisation de mi-niveau pour décrire les superpixels. Le nouvelle caractérisation de mi-niveau contient non seulement les mêmes informations que les caractéristiques initiales de bas niveau, mais contient également des informations contextuelles supplémentaires. Nous validons la caractéristisation de mi-niveau proposée sur l’ensemble de données MSRC et les résultats de segmentation montrent des améliorations à la fois qualitatives et quantitatives par rapport aux autres méthodes standards. Une deuxième partie se concentre sur le suivi d’objets multiples. C’est un domaine de recherche très actif, qui est d’une importance majeure pour un grand nombre d’applications, par exemple la vidéo-surveillance de piétons ou de véhicules pour des raisons de sécurité ou l’identification de motifs de mouvements animaliers.
  • References (181)
    181 references, page 1 of 19

    1 Introduction 1 1.1 Computer Vision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Image Segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3.2 The Challenges of Image Segmentation . . . . . . . . . . . . . 3 1.3.3 Graph Based Image Segmentation . . . . . . . . . . . . . . . 5 1.4 Multi-target Tracking . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4.2 The Challenges of Multi-target Tracking . . . . . . . . . . . . 6 1.4.3 Brief Literature Review . . . . . . . . . . . . . . . . . . . . . 7 1.5 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.6 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . 11

    2 Graph based Methods 13 2.1 Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1.2 Graph Laplacians . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Affinity Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2.1 Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.2 Affinity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3 Graph Cut Cost Function . . . . . . . . . . . . . . . . . . . . . . . . 30 2.3.1 Minimal Cut . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.3.2 Ratio Regions . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.3.3 Normalized Cut . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3.4 Mean Cut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3.5 Ratio Cut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.4 Graph Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

    3 Literature Review: Image Segmentation 39 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.2 Unsupervised Image Segmentation . . . . . . . . . . . . . . . . . . . 40 3.3 Foregound/Background Segmentation . . . . . . . . . . . . . . . . . 47 3.3.1 Interactive Segmentation . . . . . . . . . . . . . . . . . . . . . 47 3.3.2 Class Segmentation . . . . . . . . . . . . . . . . . . . . . . . . 49 3.3.3 Cosegmentation/Object Discovery . . . . . . . . . . . . . . . 49 3.4 Semantic Segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.5 Image Segmentation: Dataset . . . . . . . . . . . . . . . . . . . . . . 52 3.6 Image Segmentation: Evaluation . . . . . . . . . . . . . . . . . . . . 52

    4 A Global/Local Affinity Graph for Image Segmentation 57 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.1.1 Motivation and contribution . . . . . . . . . . . . . . . . . . . 58 4.2 Proposed Global Local Affinity Graph based on Superpixel and Sparse Representation . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.2.1 Multi-scale Superpixels Generation and Representation . . . 61 4.2.2 Global/local Affinity Graph Construction . . . . . . . . . . . 62 4.2.3 Fusing GL-graphs of different visual features and different scales 64 4.2.4 Bipartite Graph Construction and Partition . . . . . . . . . . 66 4.3 Experiment and Analysis . . . . . . . . . . . . . . . . . . . . . . . . 67 4.3.1 Experiments Setup . . . . . . . . . . . . . . . . . . . . . . . . 68 4.3.2 Experimental results using single visual feature . . . . . . . . 69 4.3.3 Results on fusing different graphs and visual features . . . . . 73 4.3.4 Comparison with state-of-the-art algorithms . . . . . . . . . . 74 4.3.5 Algorithm time complexity . . . . . . . . . . . . . . . . . . . 77 4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

    5 Graph-based Image Segmentation Using Weighted Color Patch 81 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.1.1 Motivation and our proposed method . . . . . . . . . . . . . . 82 5.1.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 5.2 Proposed method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.2.1 Local weights computation . . . . . . . . . . . . . . . . . . . 83 5.2.2 Global weights assignment . . . . . . . . . . . . . . . . . . . . 84 5.2.3 Affinity graph construction . . . . . . . . . . . . . . . . . . . 84 5.2.4 Graph partitioning . . . . . . . . . . . . . . . . . . . . . . . . 85 5.3 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.3.1 Results on Prague texture benchmark . . . . . . . . . . . . . 85 5.3.2 Results on Berkeley image database . . . . . . . . . . . . . . 87 5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

    6 Sparse Coding and Mid-Level Superpixel-Feature for `0-Graph Based Unsupervised Image Segmentation 91 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 6.1.1 Motivation and the proposed method . . . . . . . . . . . . . . 92 6.1.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 6.2 Superpixels, mid-level features, and sparse representation . . . . . . . 94 6.2.1 Low-Level Features Detection and Extraction . . . . . . . . . 94 6.2.2 Mid-Level Features Extraction over Superpixels . . . . . . . . 95 6.2.3 Graph Construction and Partitioning . . . . . . . . . . . . . . 96 6.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 6.3.1 Database and Parameter Settings . . . . . . . . . . . . . . . . 97 6.3.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . 98 6.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

    7 Active Colloids Segmentation and Tracking 101 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 7.1.1 Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 7.1.2 Motivation and contribution . . . . . . . . . . . . . . . . . . . 103 7.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 7.2.1 Particles Detection . . . . . . . . . . . . . . . . . . . . . . . . 105 7.2.2 Multiple Object Tracking . . . . . . . . . . . . . . . . . . . . 105 7.3 Proposed Framework for Colloids Detection and Tracking . . . . . . 106 7.3.1 Accurate Active Colloids Detection . . . . . . . . . . . . . . . 106 7.3.2 Active Colloids Tracking . . . . . . . . . . . . . . . . . . . . . 108 7.4 Experiments and Discussion . . . . . . . . . . . . . . . . . . . . . . . 115 7.4.1 Benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 7.4.2 Evaluation Metrics . . . . . . . . . . . . . . . . . . . . . . . . 116 7.4.3 Detection and Analysis . . . . . . . . . . . . . . . . . . . . . . 117 7.4.4 Tracking and Analysis . . . . . . . . . . . . . . . . . . . . . . 118 7.4.5 Code and computational time . . . . . . . . . . . . . . . . . . 122 7.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

    8 Conclusions and Future Work 131 8.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 8.1.1 A Global/Local Affinity Graph for Image Segmentation . . . 132 8.1.2 Graph-based Image Segmentation Using Weighted Color Patch 132 8.1.3 Sparse Coding and Mid-Level Superpixel-Feature for `0- Graph Based Unsupervised Image Segmentation . . . . . . . 133 8.1.4 Active Colloids Tracking: Recover Trajectories Globally via Min-cost/max Flow . . . . . . . . . . . . . . . . . . . . . . . 133 8.2 Perspectives for Future Work . . . . . . . . . . . . . . . . . . . . . . 133 8.2.1 Image Segmentation . . . . . . . . . . . . . . . . . . . . . . . 133 8.2.2 Multi-target Tracking . . . . . . . . . . . . . . . . . . . . . . 135

    A Fusing Generic Objectness and Deformable Part-based Models for Weakly Supervised Object Detection 137 A.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 A.2 Our Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 A.2.1 Initialization of object bounding box estimation . . . . . . . . 139 A.2.2 Detection with deformable part-based models . . . . . . . . . 140 A.2.3 Bounding box post-processing . . . . . . . . . . . . . . . . . . 140 A.3 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 141 A.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

    B The Criteria Set on Prague Texture Benchmark 147 B.1 Region-Based Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . 147 B.2 Pixel-Wise Weighted Average Criteria . . . . . . . . . . . . . . . . . 148 B.3 Clustering Comparison Criteria . . . . . . . . . . . . . . . . . . . . . 150

  • Metrics
    No metrics available
Share - Bookmark