Keywords: Berkeley Segmentation Dataset, 53 database

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 0 -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.

Many people have contributed to make this thesis a reality, by providing me with their guidance, friendship, love, money, code and data.

I would like to start by thanking my advisor, Prof. Simon Masnou, for teaching me a great deal about research. He has been very supportive and given me the freedom to pursue various projects without objection. He is patient, knowledgeable, smart, funny and easy going. We worked together closely, this thesis would not have been possible without his help and his passion for tackling hard problems. Meanwhile, I would like to express my deeply-felt thanks to my co-advisor, Prof. Liming Chen. He has always been extremely generous with his time, ideas and resources, for his attitude and passion of doing research.

I would also want to thank the members of my doctoral committee, Profs. Su Ruan, Patrick Bouthemy, Christine Fernandez-Maloigne and Anuj Srivastava for their time, feedback and interest in my work. I must also acknowledge the important contributions of my other co-authors Dr. Chao Zhu, Dr. Huibin Li, Boyang Gao, Yuxing Tang and Dongming Chen. Their singular abilities, expertise and creativity were fundamental to this thesis and it was great fun to work and travel with both.

I truly enjoyed the time spent doing research in the Lab LIRIS of Ecole Centrale de Lyon in France. I would like to acknowledge my friend and colleagues, for their countless help, thoughtful suggestions, warm and valuable friendship, and contributions to my research. They are Dr. Chao Zhu, Dr. Huibin Li, Boyang Gao, Ningning Liu, Kai Wang, Yuxing Tang, Dr.Dongming Chen, Huiliang Jin, Wei Chen, Wuming Zhang, Huaxiong Ding, Yihang Tang, Ying Lv, Chen Wang. My special thanks are due to Dr. Huibin Li. He discussed with me about my experiment and provided me thoughtful suggestions on applying sparse representation theory. I have learned so much from him, ranging from solid and beautiful academic paper writing to every useful detail for happy life, which are unforgettable and the most precious time in my life. I am also grateful and very glad to work and discuss with Boyang Gao (extremely knowledgeable in just about everything, helpful, and friendly), for his scientific advice on my project of object tracking. Very pleasant corporation with Yuxing Tang on the object detection domain, and with Dongming Chen on the stereo matching domain. I also thank my friends (too many to list here but you know who you are!) for providing support and friendship that I needed. I would like to thank Joy (I think of her as a big sister.) and Guangyu Zhou for being supportive throughout my time here.

I would like to dedicate this thesis to my family, in particular to my parents, my uncle, brothers and sister. My hard-working parents have deep love to people and the circumstances, they are excellent role model for my life. My brothers and their wives, Qianjin Wang and Chunyan Zhang, Xingfu Wang and Zhenhua Wang, my sister and her husband, they are great man for their support to my academic career for many years, and taking care of our parent with great consideration and love. I am very grateful for having such big, warm and harmony family for their unconditional love and care. I love them so much, and I would not have made it this far without them. I would like particularly acknowledge to my friend, Qian Zhang for his selfless and endless support. Finally, I want to express my acknowledge to

Résumé

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 0 . 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 ou de particules synthétiques et biologiques afin de comprendre les mécanismes sousjacents.

Nous proposons donc une méthode reposant sur la detection puis le suivi de trajectoires de colloïdes massives dans un système de suspension active. Tout d'abord, nous adoptons une méthode de regionalisation par niveau pour segmenter tous les colloïdes de vidéos à long terme dont l'intensité est hétérogène. Par ailleurs, nous utilisons une transformée de Hough circulaire pour affiner la segmentation afin d'identifier les colloïdes individuellement. Ensuite, nous proposons de récupérer les trajectoires de tous les colloïdes simultanément, ce qui est un probléme d'optimisation global qui peut être résolu efficacement avec des algorithmes d'optimisation de type coût minimum / flux maximum. Cette approche est évaluée à partir d'un ensemble de tests reposant sur 9 vidéos différentes de vraies experimentations en physique. Nous montrons ainsi que l'approche proposée surpasse largement les méthodes standards. vi List of Figures The intensity values at pixels p 1 , p 2 and p 3 are similar. However, there is a contour in the middle, which suggests that p 1 and p 2 belong to one group while p 3 belongs to another. Just comparing intensity values at these three locations will mistakenly suggest that they belong to the same group. Right: orientation energy. Somewhere along l 2 , the orientation energy is strong which correctly proposes that p 1 and p 3 belong to two different partitions, while orientation energy along l 1 is weak throughout, which will support the hypothesis that p 1 and p 2 belong to the same group [START_REF] Malik | Contour and texture analysis for image segmentation[END_REF] . . . . . . . . 25 2.4 Multiscale graph compression . . . . . . . . . . . . . . . . . . . . . . 25 2.5 (a) Polka-dot image is convolved with a bank of filters. (b) Textons found via K-means with K = 25, sorted in decreasing order by norm. (c) Mapping of pixels to the texton channels. The dominant structures captured by the textons are translated versions of the dark spots. [START_REF] Malik | Contour and texture analysis for image segmentation[END_REF]. . . . . . . . . . . . . . . . . . . . . . . . 26 2.6 Multi-layer graph model [Kim et al., 2010b]. In (a), the graph nodes V * consist of pixels V and regions V (l) l=1,...,L , generated by varying the parameters of the mean shift algorithm [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF]]. An undirected edge E * represents the relation between a pair of nodes. (b) and (c) show the examples of edges (violet lines) connected to one region and to one pixel, respectively. . . . . . . . . . . . . . . 27 2.7 The proposed bipartite graph model with K over-segmentations of an image. A black dot denotes a pixel while a red square denotes a superpixel [START_REF] Li | Segmentation using superpixels: A bipartite graph partitioning approach[END_REF]. . . . . . . . . . . . . . . . . . . . . . . . . 28 2.8 Illustration of spectral methods for image segmentation. . . . . . . . 35 2.9 Illustration of the geometric partitioning method [START_REF] John R Gilbert | Geometric mesh partitioning: Implementation and experiments[END_REF]]. 36

List of Figures

2.10

The various phases of the multilevel graph bisection. During the coarsening phase, the size of the graph is successively decreased; during the initial partitioning phase, a bisection of the smaller graph is computed; and during the uncoarsening phase, the bisection is successively refined as it is projected to the larger graphs. During the uncoarsening phase the light lines indicate projected partitions, and dark lines indicate partitions that were produced after refinement. . . 36

3.1 Illustration of thresholding result with the Otsu method [START_REF] Otsu | A threshold selection method from gray-level histograms[END_REF]. 41 3.2 Hierarchical segmentation from contours [START_REF] Arbelaez | Contour detection and hierarchical image segmentation[END_REF] . Top Left:Original image. Top Middle: Maximal response of contour detector gPb over orientations.Top Right: Weighted contours resulting from the Oriented Watershed Transform -Ultrametric Contour Map algorithm using gPb as input. Bottom: Contours and corresponding segmentations obtained by thresholding the UCM at levels 0.1(left), and 0.5 (right), with segments represented by their mean color. . . . 42 3.3 A taxonomy of clustering algorithm [Jain et al., 1999] . . . . . . . . 43 3.4 Segmentation generated by mean shift [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF], quick shift [START_REF] Vedaldi | Quick shift and kernel methods for mode seeking[END_REF] and convex shift [START_REF] Yu | Bag of textons for image segmentation via soft clustering and convex shift[END_REF]. 45 3.5 Illustration of the segmentation result by MST based algorithm, FH [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF]. . . . . . . . . . . . . . . . . . 46 3.6 (a), (f), (k) Watershed initialization of nuclei and lymphocytes on prostate and breast cancer histopathology with corresponding segmentation results obtained via GAC [START_REF] Caselles | Geodesic active contours[END_REF]] (b), (g), (l); Method in [START_REF] Ali | An integrated region-, boundary-, shapebased active contour for multiple object overlap resolution in histological imagery[END_REF] (c), (h), (m); magnified region (d), (i), (n) from (b), (g), (l); magnified region (e), (j), (o) from (c), (h) and (m) . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.7 Illustration of comparison of interactive segmentation method. The top row shows the user interaction required to complete the segmentation or matting process: white brush/lasso (foreground), red brush/lasso (background), yellow crosses (boundary). The bottom row illustrates the resulting segmentation. . . . . . . . . . . . . . . . 48 3.8 Illustration of cosegmentation [START_REF] Rother | Cosegmentation of image pairs by histogram matching-incorporating a global constraint into mrfs[END_REF]: given a pair of images, the task is to segment the common part in both images. Compared to GrabCut [START_REF] Rother | Grabcut: Interactive foreground extraction using iterated graph cuts[END_REF], which segment the foreground individually, cosegmentation outperforms traditional foreground/background method. . . . . . . . . . . . . . . . . . . . . 49 3.9 Illustration of cosegmentation [START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF]

4.5

Illustration of the GL-graph's structure: for each over-segmentations, all the superpixels are divided into three sets: small (the green dots), medium (the blue dots) and large (the ink blue dots) according to their area. Over small and large sets, all data points will connect to their adjacent neighbors, while over medium set, each data point will search its neighbors all over the set. Note that bold red lines represent undirected edges connecting data points within sets, while the dashed red lines describe the edges connecting data points between two different sets. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.6

Illustration of the construction of an unbalanced bipartite graph over multi-scale over-segmentations: a yellow dot denotes a pixel, and a white dot denotes a superpixel. The blue lines show that each pixel is only connected to its corresponding superpixel in each scale of over-segmentations which is represented as a pixel-superpixel affinity matrix (upper block matrix), while the yellow lines show undirected edges representing the relationships between two superpixels, represented by a superpixel-superpixel affinity matrix (lower block matrix). 4.9 Visual comparison of the results obtained with the GL-graph and with other graphs. Each line from top to bottom corresponds to the segmentation result obtained with the following graphs: adjacency, kN N , 1 , LRR, and the proposed GL-graph. From left to right, the results for various choices of k = 2, 3, 4, 5. . Note that the result is segmented using the most appropriate feature for each kind of graph according to Table I, e.g. we use the feature mlab for the adjacencygraph and the KN N -graph. . . . . . . . . . . . . . . . . . . . . . . 78 4.10 Visual comparison with SAS. For each experiment, the second image shows the results of SAS, and the third image is obtained with our method. Our results require significantly less tuning for k and are visually better in general, in particular often more accurate. . . . . . 79 4.11 Visual segmentation examples by the proposed method: all images are segmented into 2 regions (k=2). Note that the salient objects or parts can be segmented accurately, such as the plane, boat, flower with insects, elephants, hill. Even multiple objects with large inner color variation can be segmented correctly, as the cactus flowers or the men in water. . path with SSP and tag-then-delete procedure. In (a), the bold blue edges are part of an optimal path found by the SSP among all edges (edges in blue and yellow); in (b), the dash edges in blue and some edges in yellow are tagged and deleted, some new edges in orange are added to connect the node directly with dummy nodes . . . . . . . show two original video frames. (c, d), (e, f), (g, h) are the result obtained by the Otsu's threshold [START_REF] Otsu | A threshold selection method from gray-level histograms[END_REF], local maximum detection method, and wavelet based method [START_REF] Padfield | Coupled minimum-cost flow cell tracking for high-throughput quantitative analysis[END_REF] respectively. 7.7 Visual comparison of different particle detection methods. (a, b) show two original video frames. (c, d), (e, f) are the result obtained by the method proposed in [START_REF] Ivo | Feature point tracking and trajectory analysis for video imaging in cell biology[END_REF] and our method respectively. . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.8 Illustration of cluttered colloid's tracking: ground truth. . . . . . . . 7.9 Illustration of cluttered colloid's tracking: Kalman filter [START_REF] Samuel S Blackman | Multiple-target tracking with radar applications[END_REF]

Computer Vision

Computer vision aims at modeling and imitating human vision using computer software and hardware at different levels. It combines many different branches of knowledge in computer science, mathematics, physiology, and cognitive science. The entire field of computer vision is too broad to be described in details, examples of applications range from industry (e.g. controlling process, automatic inspection), to medicine (e.g. computer-aided diagnosis, tumor detection), biology (e.g. gene expression), or game industry (virtual reality). Although machines are not yet as efficient as the human brain for scene understanding and interpretation, their performances on a few tasks in image denoising, face detection or human pose estimation have reached very good quality. More complex tasks are still intensively studied, as complex image denoising or in painting, image segmentation and classification, object detection and tracking. The reason for such intensive study is that image segmentation and object detection are key steps in a complete computer vision system as illustrated in Fig. 1.1.

Chapter 1. Introduction

Computer Vision

Image acquisition

Preprocessing

Feature extraction

Detection Segmentation

High-level processing Decision making

Graph Theory

In computer vision, graph theory has been successfully applied to solve many tasks, ranging from low-level tasks (e.g. image segmentation, object tracking, stereo matching, etc.), to high-level tasks (e.g. image classification, object recognition, image parsing, etc.). Beyond this, graphs can be used to model many types of relations and processes in physical, biological, social and information systems, see a few examples in Table 1.1. The popularity of graphs has several reasons: 1) graphs provide discrete and mathematically simple representations that are well adapted to the development of efficient and provably correct methods; 2) they offer data representation flexibility; 3) a lot of methods involving graphs have been developed in other contexts than image processing, yet it is very frequently possible to adapt the methods to an image setting.

The Challenges of Image Segmentation

Image segmentation has been a core research subject in computer vision for many decades. At early stage, image segmentation has been formulated as a bottom-up process. It dates back to [START_REF] Wertheimer | Laws of organization in perceptual forms (partial translation)[END_REF] who introduced the Gestalt theory for vision perception and studied the factors of perceptual grouping such as proximity, similarity, and good continuity. The low-level principles underlying the Gestalt theory have inspired many approaches to segmentation. Indeed, low-level homogeneous attributes can lead as in Fig. 1.3 to good segmentations which resemble manually-segmented results. Consequently, many works pursued a single optimal segmentation of an image or a few images using one or two low-level or mid-level (e.g. symmetry) cues. However, due to the ambiguity of low and mid-level cues, it is uneasy to get a successful partition. This illustrates of course that image segmentation is an ill-posed problem. It is an easier task for a human observer who performs the segmentation based on different features homogeneity. An example is illustrated in Fig. 1.4, where we compare the result produced by a recent efficient bottom-up algorithm [START_REF] Li | Segmentation using superpixels: A bipartite graph partitioning approach[END_REF] with the corresponding human segmentation. Ideally, we can segment the image as a water region of uniform color, a sky region of uniform smoothness (note that sky color varies across the image), a region of tree leaves of uniform texture, and so forth. However, the automatic segmentation algo- rithm is hard to cope with various definitions of uniformity throughout the image, although many methods are designed to combine optimally multiple homogeneous measurements [Cheng et al., 2011a]. It is worth to mention that at early stage, another difficulty of image segmentation is that there is no quantitative benchmarks to evaluate the improvement and to compare with other algorithms and most papers only describe the merits of the output segmentations qualitatively, usually based on results obtained on a few images, as summarized in [START_REF] Carreira | Constrained parametric min-cuts for automatic object segmentation[END_REF]. Modern views on the image segmentation have evolved in two aspects: i) one is the role of bottom-up segmentation and ii) the other is taking account mid-level and high-level knowledge to leverage bottom-up segmentation. The underlying force to such change is propelled by : 1) the creation of annotated benchmarks [START_REF] Arbelaez | Contour detection and hierarchical image segmentation[END_REF]] [Shotton et al., 2006][Everingham et al.] and new segmentation performance metrics [PRI] [START_REF] Meila | Comparing clusterings: an axiomatic view[END_REF][START_REF] Martin | A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[END_REF][START_REF] Freixenet | Yet another survey on image segmentation: Region and boundary information integration[END_REF]; 2) the adoption of machine learning techniques to optimize performance on benchmarks; and 3) relaxing the constraint of working with a single partitioning. An approach became popular by computing several independent segmentations, possibly using different algorithms or varying parameters of the same algorithm [START_REF] Li | Segmentation using superpixels: A bipartite graph partitioning approach[END_REF]][Kim et al., 2010b[START_REF] Wang | A graph-cut approach to image segmentation using an affinity graph based on l0-sparse representation of features[END_REF]. Such new understanding turned image segmentation into a hot topic again, after it got stuck in the nineties [START_REF] Joseph | Object recognition in the geometric era: A retrospective[END_REF].

Chapter 1. Introduction

The first aspect mentioned earlier is that the bottom-up methods should not aim to generate completely correct segments, instead the objective should be to use the results of low-level for mid/high-level process in order to obtain the most appropriate segments in the context of prior world knowledge. A good low-level image segmentation algorithm can significantly reduce the complexity of object segmentation and recognition, which forms the core of high-level vision. For example, some methods [START_REF] Jrr Uijlings | Selective search for object recognition[END_REF] apply low-level segmentation techniques to generate object bounding boxes candidates or use the segmentation result as a kind of feature measuring the objectness of a candidate bounding box [START_REF] Alexe | Classcut for unsupervised class segmentation[END_REF]. The derived region proposal or bounding boxes can be used in the object detection and localization. In the saliency detection [Cheng et al., 2011b], performing segmentation has become an essential ingredient to obtain high-quality results. In some scene understanding [START_REF] Li | Towards total scene understanding: Classification, annotation and segmentation in an automatic framework[END_REF] and semantic segmentation [Carreira et al., 2012a] algorithms, the final results are inferred on over-segmented regions generated by efficient low-level segmentation methods, such as Felzenszwalb and Huttenlocher [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF] or Mean shift [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF].

The second aspect concerns the laws stated in Gestalt theory, which is to say that some mid-level (e.g. symmetry) and high-level vision (past experience and closure) play essential role in vision perceptual process. For example, Shotton et al. [START_REF] Shotton | TextonBoost: Joint appearance, shape and context modeling for multi-class object recognition and segmentation[END_REF] incorporate the texture, layout and context using boosting algorithm and the pixel-wise segmentation is achieved with Conditional Random Field (CRF) [START_REF] Lafferty | Conditional random fields: Probabilistic models for segmenting and labeling sequence data[END_REF]. [START_REF] Bibliography | Semantic segmentation using regions and parts[END_REF] proposed region based object detectors which combine top-down poselet detector and global appearance cues.

Graph Based Image Segmentation

In recent years, among the many approaches to image segmentation, graph based methods have become a major trend. In these methods, image segmentation is modeled in terms of partitioning a graph into several sub-graphs such that each of them represents a meaningful object of interest in the image. The very first step is mapping the image elements onto a graph, where the nodes may be pixels, regions, or even user-drawn markers. The graph structure is formed by a set of nodes (also called vertices) and a set of edges that are connections between pairs of nodes. Basically, graph based methods can be categorized into :

• Minimum spanning tree (also called shortest spanning tree) based methods, where the clustering or grouping of image pixels are performed on the minimal spanning tree. The connection of graph vertices satisfies the minimal sum on the defined edge weights, and the partition of a graph is achieved by removing edges to form different sub-graphs. An example of such method is Felzenszwalb and Huttenlocher [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF].

• Graph cut with cost functions. Graph cut is a natural description of image segmentation. Using different cut criteria, the global functions for partitioning the graph will be different. Usually, by optimizing these functions, we can get Chapter 1. Introduction the desirable segmentation. Normalized cut [START_REF] Shi | Normalized cuts and image segmentation[END_REF] and ratio cut [START_REF] Wang | Image segmentation with ratio cut[END_REF]] are such methods.

• Graph cut on Markov random field models: the goal is to combine the high level interactive information with the regularization of the smoothness in the graph cut function. Under the MAP-MRF framework, the optimization of the function is obtained by the classical min-cut/ max-flow algorithms [START_REF] Boykov | Graph cuts and efficient nd image segmentation[END_REF] or its nearly optimal variants, such as multi-label graph cut [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF] and interactive graph cut [START_REF] Rother | Grabcut: Interactive foreground extraction using iterated graph cuts[END_REF].

• Shortest path methods, where the object boundary is defined on a set of shortest paths between pairs of graph vertices. That is to say, the problem of finding the best boundary segment is converted into finding the minimum cost path between two vertices. In a weighted graph, the shortest path will connect the two vertices with the minimized sum of edge weights, and the path can be computed for instance with Dijkstra's algorithm [Dijkstra, 1959b]. Shortest path methods require user interactions to guide the segmentation. Therefore, the process is more flexible and can provide friendly feedback.

Graph based approach is gaining popularity primarily due to its ability in reflecting global image properties. It explicitly organizes the image elements into mathematically sound structures, and makes the formulation of the problem more flexible and the computation more efficient, which might require no discretization by virtue of purely combinatorial operators and thus incur no discretization errors.The segmentation problem is solved in a spatially discrete space by the efficient tools from graph theory.

Multi-target Tracking

Definition

The task of multi-target tracking, also called multiple object tracking, is to follow many moving objects in a dynamic scene. Given a video sequence, multi-target tracking aims to precisely recovering the trajectory of every single, freely moving target from the video. The topic of object tracking is one of the most fundamental tasks in applications of video motion processing, analysis, and data mining, such as human-computer interaction, visual surveillance, and virtual reality. Common application scenarios involve traffic video surveillance for security, sport players tracking to study their motion patterns and parameters during games, cell tracking for research in microbiology, see Fig. 1.5.

The Challenges of Multi-target Tracking

Tracking several objects over time does not only require a correct segmentation of each object at any time, but also a correct identification over time. It is highly challenging and designing an algorithm is generally ad-hoc. It is challenging for various reasons. First of all, visual data is often ambiguous. For example, the objects to be tracked can be missed due to low contrast, noise and occlusion. Second, when multiple objects are close to each other, correspondence ambiguities need to be solved, which leads to more complex problems at every time step. In addition, in realistic applications, the method should take physical constraints into account. This is not only important at the level of individual targets but also regarding interactions between them, which adds to the complexity of the problem.

Brief Literature Review

Object tracking is a well-known problem and a very active research topic in computer vision. Up to now, a substantial body of literature has been proposed dealing with the problem of tracking multiple targets. It is therefore not likely to present a complete review of all works on this topic within the limits of this dissertation. We briefly introduce several very important algorithms in multiple target tracking as well as their extension versions. One typical way to classify multi-target tracking approaches is to distinguish between online methods (e.g. Kalman filters) where the state is estimated at each time step and offline (graph based methods) techniques, which consider an entire temporal sequence at once. In particular, we discuss more on the graph based method proposed for the aim of multi-target tracking in section 1.4.3.2.

Online Methods

One of the most popular approaches to this problem is the Kalman filter proposed by Kalman [START_REF] Emil | A new approach to linear filtering and prediction problems[END_REF]. In its early version, given a sequence of measurements, the Kalman filter estimates the optimal state of a system in a least squares sense and , 1997] have been proposed. The demand for non-Gaussian models later led to the development of stochastic recursive state estimation techniques called particle filters [START_REF] Neil J Gordon | Novel approach to nonlinear/non-gaussian bayesian state estimation[END_REF][START_REF] Isard | Condensation¡ a conditional density propagation for visual tracking[END_REF][START_REF] Doucet | On sequential monte carlo sampling methods for bayesian filtering[END_REF]. Particle filters is used for visual tracking introduced by Isard and Blake to include the posterior probability distribution, e.g. additional density propagation of shape. Later, more complex constraints propagation have been proposed in [START_REF] Vermaak | Maintaining multimodality through mixture tracking[END_REF] and [START_REF] Okuma | A boosted particle filter: Multitarget detection and tracking[END_REF]. Note that the above filtering techniques are intrinsically designed to handle single target. But it is easily and more often employed in multiple-target tracking by solving the data association problem iteratively.

Another more frequently used method is the data association. We present a coarse review and we refer readers to [START_REF] Cox | A review of statistical data association techniques for motion correspondence[END_REF] and [START_REF] Blackrnan | Design and analysis of modern tracking systems[END_REF] for a more thorough discussion. One of the simplest data association techniques is global nearest neighbors [START_REF] Blackrnan | Design and analysis of modern tracking systems[END_REF], which keeps the association with the highest probability for all targets and removes all the other ones. An obvious drawback of global nearest neighbors is that all previous information is discarded as soon as the current time step has been processed. To amend this, Reid proposed a more complex data association method, referred as the multiple hypothesis tracker [START_REF] Donald | An algorithm for tracking multiple targets[END_REF]. The idea is to keep all possible association events from the past observations in memory and to choose the best one at each time step, which is an exhaustive search algorithm. Another class of methods is called probabilistic data association originally in [START_REF] Bar | Adaptive nonlinear filtering for tracking with measurements of uncertain origin[END_REF]. The idea is that probabilities for various sources of origin for each detection are accumulated and propagated through time.

Offline Methods

• Markov Chain Monte Carlo Sampling: Unlike particle filter, Markov Chain Monte Carlo (MCMC) is a more general sampling technique, which works by generating a sequence of variables from a specially crafted Markov Chain. MCMC was first used to solve data association problems by Pasula et al. [START_REF] Pasula | Tracking many objects with many sensors[END_REF], who showed it to be effective for multi-camera traffic surveillance problems involving hundreds of vehicles. [START_REF] Khan | Mcmc-based particle filtering for tracking a variable number of interacting targets[END_REF] introduced a Markov random field motion prior to model the pairwise interaction between targets. The exponential complexity is approached by Markov chain Monte Carlo (MCMC) sampling. [START_REF] Songhwai Oh | Markov chain monte carlo data association for general multiple-target tracking problems[END_REF] proposed a general framework to sample the data association hypothesis using a MCMC approach, and converges to the full Bayesian solution if given enough computational resources.

• Graph-based Methods: Generally, for graph-based tracking, observations are represented by vertices, and costs are assigned to edges to measure relationships between observations. Solution of the multi-object tracking problem is a combinatorial optimization problem of significant complexity and thus becomes a problem of considerable research interest. A common strategy starts Chapter 1. Introduction from a set of short, yet confident tracks, or tracklets, longer trajectories are built based on global information. For example, many early approximation methods proposed greedy bipartite data association on a frame-by-frame basis and can be solved exactly in polynomial time by Hungarian algorithm. [START_REF] Padfield | Coupled minimum-cost flow cell tracking for high-throughput quantitative analysis[END_REF] explicitly modeled cell behaviors in a graph-theoretic framework as a flow network that can be solved efficiently using the minimumcost flow algorithm and extended the standard minimum-cost flow algorithm to account for mitosis and merging events through a coupling operation on particular edges. More recent methods proposed to find globally optimal solutions across the entire sequence by creating network flow graphs. Zhang et al. [Zhang et al., 2008b] defined a graph and solved the data association problem by optimizing the cost flow network in order to find the globally optimal trajectories. Some methods are proposed to solve the data association from constructed graph with other algorithms instead of the min-cost/max flow. [START_REF] Yan | Layered data association using graph-theoretic formulation with application to tennis ball tracking in monocular sequences[END_REF] formulated the association problem as an all-pairs shortest path problem in the graph, where each node is a tracklet, and the edge weight between two nodes is defined according to the compatibility of the two tracklets. [START_REF] Brendel | Multiobject tracking as maximum weight independent set[END_REF] formulated the data association as a maximum weight independent set problem. Their algorithm solves for two-frame tracklets independently, and then links these into complete tracks by using a learned distance measure. [START_REF] Amir Roshan Zamir | Gmcp-tracker: Global multi-object tracking using generalized minimum clique graphs[END_REF] incorporated the whole temporal span of the sequence into the data association problem, and solved the data association problem for one object at a time with generalized minimum clique graphs rather than addressing all of them simultaneously. Butt and Collins [Butt and Collins, 2013b] estimated trajectories in a trellis graph, where each node in the network represents a candidate pair of matching observations between consecutive frames and is solved by relaxing these extra constraints using Lagrangian relaxation.

Contributions

The goal of this dissertation is to contribute to the state of the art in image segmentation and particle tracking using graph-based methods. To this end, four contributions are introduced: • Our second approach builds on the work [START_REF] Buades | A non-local algorithm for image denoising[END_REF] and [START_REF] Ji | Fuzzy c-means clustering with weighted image patch for image segmentation[END_REF], and develop a new feature descriptor, referred as weighted color patch, which represents a pixel with a weighted patch. To alleviate the over-smooth effect caused by considering each member equally in the patch, we assign different weight to each pixel in the patch. The weighted color patch have two main advantages: i) it can smooth local regions by averaging color information and ii) it can capture texture information by considering context neighboring cue. As a result, the proposed weighted color patch has been proved powerful and discriminating, evaluated on the Prague color texture image benchmark and the Berkeley image segmentation database.

• Our third contribution is to develop a new mid-level feature and apply it in a graph-theoretical framework. We build the dictionary from informative patches centered at interest points detected without any supervision, and each mid-level feature is the sparse coding in the dictionary of the low level feature associated with a superpixel. Consequently, the new mid-level features carry not only the same information as the initial low-level features, but also additional contextual cue. Compared with related works and other benchmark algorithms on the MSRC dataset, the key contribution of this paper is that our new mid-level feature is able to describe better the superpixels.

• Our fourth contribution is to propose a robust framework that jointly segment and track accurately massive colloids in long-term videos. Note that all trajectories are recovered simultaneously from a high-quality trellis graph which builds on all frames. The first contribution is the strategy of two-stage graph construction, first coarse graph then refined graph with additional constraints, that guarantees the final tracking result. The second contribution of this work is that a modified min-cost/max flow algorithm enables recovering simultaneously meaningful trajectories in the graph. Finally, we evaluate the proposed framework on real videos, which have been annotated by 9 different graduate students.

• Our final contribution also lies on the discussion on various graph construction algorithms, extensive experiments to compare graphs and features on public available data set, in order to shed light on how to construct discriminative graphs with suitable features and their combinations. Note that a high-quality graph construction can easily be used in other graphical models for solving other problems involving a graph. Moreover, the tracking algorithm is not limited for tracking massive colloids for physics research, it is feasible for other multi-target tracking problems. Finally, we provided a real benchmark by annotating 9 different videos, which can be used to evaluate and compare new proposed algorithms dealing with multi-target tracking task.

Organization of the Thesis

The remainder of this thesis is organized as follows. Chapter 2 provides the basic definitions and results in graph theory and presents a systematic survey of graph construction and graph partitioning relevant to this thesis. Chapter 3 reviews the previous work on image segmentation, since the algorithms presented in this dissertation are mainly on this subject.

The main technical contribution presented in the thesis is divided into three parts. Part 1 (Chapter 4) deals with the essential issue of graph construction. We propose a novel graph construction algorithm by encoding adaptively the local and global image structure information. The technical part of this chapter has been published in [START_REF] Wang | A graph-cut approach to image segmentation using an affinity graph based on l0-sparse representation of features[END_REF] and is described with details in a submitted paper. Then we also present a thorough comparison with various graph constructions on standard image segmentation dataset. Part II (Chapter 5 and 6) presents two methods to employ perceptually meaningful image properties for image segmentation. In chapter 5, a new feature, called weighted color patch, is proposed to compute the weight of edges in graph construction. The proposed method intends to incorporate both color and neighborhood information by representing pixels with color patches, and is proved powerful on the Prague color texture image benchmark and the Berkeley image segmentation database. This chapter is based on [START_REF] Wang | Graph-based image segmentation using weighted color patch[END_REF]. In Chapter 6, we propose a graph-based unsupervised segmentation approach that combines superpixels, sparse representation, and a new mid-level feature to describe superpixels. These mid-level features not only carry the same information as the initial low-level features, but also carry additional contextual cue. This proposed mid-level feature framework is validated on the MSRC dataset and published in [Wang et al., 2013b]. Part III (Chapter 7) deals with the multi-target tracking problems in active colloids systems. We propose an efficient framework to jointly detect and track each colloid in a long-term video. The proposed modified min-cost/max flow algorithm enables to find all colloids' paths simultaneously and our framework is proved powerful on annotated videos.

In Chapter 8, we summarize the contributions that were developed in this thesis and presents a discussion on the relevance and role of each individual methods as well as an outlook for possible future research direction.

Finally, during the period of the thesis, we also cooperated with Yuxing Tang (PhD candidate) on a different topic, namely object recognition and detection. We present the proposed method in Appendix A.

Chapter 2

Graph based Methods

Graph

In graph theory, a graph is a representation of a set of data where some pairs of data elements are connected by links [Wil, Gallier, 2013[START_REF] Ulrike | A tutorial on spectral clustering[END_REF]. The data elements are called vertices, or nodes and the links are called edges, or arcs. In most contexts, a graph is represented as G = (V, E), where V is a set of vertices and E is a set of edges between vertices.

Definitions

Definition 1 A directed graph is a pair G = (V, E), where V = {v 1 , • • • , v n } is a set of nodes, and E ⊆ V × V is a set of ordered pairs of distinct nodes (that is, pairs (u, v) ∈ V × V with u = v), called edges. Definition 2 Anundirected graph is a pair G = (V, E), where V = {v 1 , • • • , v n }
is a set of nodes or vertices, and E is a set of two-element subsets of V (that is, subsets {u, v}, with u, v ∈ V and u = v), called edges.

Since an edge is a set {u, v} with u = v, self-loops are not allowed. Also, for every set of nodes {u, v}, there is at most one edge between u and v. As in the case of directed graphs, such graphs are sometimes called simple graphs.

Definition 3 Given a directed graph G = (V, E) with V = {v 1 , • • • , v n } and E = {e 1 , • • • , e m }, the incidence matrix D(G) of G is the n × n matrix whose entries dij are given by: dij =    -1 if e j = (v i , v k ) for some k +1 if e j = (v k , v i ) for some k 0 otherwise
If G is undirected then the entries of the incident matrix are given by ), where V = {v 1 , . . . , v n } is a set of nodes, and W is a symmetric matrix called the weight matrix, such that w ij ≥ 0 ∀i, j ∈ 1, . . . , n, and w ii = 0 for i = 1, . . . , n.

dij = 1 if e j = {v i , v k } for some k 0 otherwise Definition 4 Given a directed or undirected graph G = (V, E), with V = {v 1 , . . . , v n }, the adjacency matrix A(G) of G is the symmetric n × n matrix (a ij ) such that 1. If G is directed, then a ij = 1 if there is some edge (v i , v j ) ∈ E or some edge (v j , v i ) ∈ E 0 otherwise 2. Else if G is undirected, then a ij = 1 if there is some edge (v i , v j ) ∈ E 0 otherwise Definition 5 A weighted graph is a pair G = (V, W
Since w ii = 0, these graphs have no self-loops. We can think of the matrix W as a generalized adjacency matrix. The case where w ij ∈ [0 1] is equivalent to the notion of a graph as in Definition 2.

Definition 6 Given a graph G = (V, E) with V = {v 1 , . . . , v n }, the degree matrix D for G is a n × n diagonal matrix defined as:

D =      d(v1) d(v 2 ) . . . d(v n )      (2.1)
where the degree d(v i ) of v i is the sum of the weights of the edges adjacent to the node v i , i.e.:

d(v i ) = n j=1 w ij . (2.2)
Note that in the above sum, only nodes v j such that there is an edge {v i , v j } have a nonzero contribution. Such nodes are said to be adjacent to v i .

Given these preliminaries, a series of basic definitions are listed as follows:

1. Given any subset of nodes A ⊆ V , the volume vol(A) of A is the sum of the weights of all edges adjacent to nodes in A, defined as:

vol(A) = v i ∈A d(v i ) = v i ∈A n j=1 w ij (2.3) 2. A graph G = (V , E ) is called a subgraph of G = (V, E) if V ⊂ V , and E = {e ij ∈ E|v i ∈ V and v j ∈ V } 3. A graph is called bipartite graph if V can be partitioned into two subsets V 1 ⊂ V and V 2 ⊂ V , where V 1 ∩V 2 = φ and V 1 ∪V 2 = V , such that E ⊆ V 1 ×V 2 .

Graph Laplacians

In this section we recall various definitions of graph Laplacians and point out their most important properties. In the following we always assume that G is an undirected, weighted graph with weight matrix W , where w ij = w ji ≥ 0. Eigenvalues will always be ordered increasingly, respecting multiplicities. By "the first k eigenvectors" we refer to the eigenvectors corresponding to the k smallest eigenvalues Definition 7 Given a graph G = (V, E) and its degree matrix D and weighted matrix W , the unnormalized graph Laplacian matrix is defined as:

L = D -W.
(2.4)

Remark 1

The matrix L satisfies the following properties:

1. For every vector f ∈ R n we have

f Lf = 1 2 n i,j=1 w ij (f i -f j ) 2 (2.5)
2. L is symmetric and positive semi-definite.

3. The smallest eigenvalue of L is 0, the corresponding eigenvector is the constant one vector I.

4. L has n non-negative, real-valued eigenvalues 0 = λ 1 ≤ λ 2 ≤ . . . ≤ λ n .

Chapter 2. Graph based Methods

Remark 2 Let G be an undirected graph with non-negative weights. Then the multiplicity k of the eigenvalue 0 of L equals the number of connected components A 1 , . . . , A k in the graph. The eigenspace of eigenvalue 0 is spanned by the indicator vectors IA 1 , . . . , IA k of those components.

Definition 8 Given graph G = (V, E), the (normalized) graph Laplacians L sym and L rw of G are defined by:

L sym = D -1/2 LD -1/2 = I -D -1/2 W D -1/2 L rw = D -1 L = I -D -1 W. (2.6)
Remark 3 The normalized Laplacians satisfy the following properties:

1. For every vector f ∈ R n we have

f L sym f = 1 2 n i,j=1 w ij ( f i √ d i - f j d j ) 2 .
(2.7)

2. λ is an eigenvalue of L rw with eigenvector u if and only if λ is an eigenvalue of L sym with eigenvector w = D 1/2 u.

3. λ is an eigenvalue of L rw with eigenvector u if and only if λ and u solve the generalized eigen-problem Lu = λDu.

4. 0 is an eigenvalue of L rw with the constant one vector I as eigenvector. 0 is an eigenvalue of L sym with eigenvector D 1/2 I.

5.

L sym and L rw are positive semi-definite and have n non-negative real-valued eigenvalues 0 = λ 1 ≤ λ 2 ≤ . . . ≤ λ n .

Remark 4 Let G be an undirected graph with non-negative weights. Then the multiplicity k of the eigenvalue 0 of both L rw and L sym equals the number of connected components A 1 , . . . , A k in the graph. For L rw , the eigenspace of 0 is spanned by the indicator vectors IA i of those components. For L sym , the eigenspace of 0 is spanned by the vectors D 1/2 IA i .

Affinity Graph

In graph-oriented methods, many tasks such as clustering, dimensionality reduction, or semi-supervised learning, affinity graph (also called similarity graph in context of spectral clustering) plays an essentially important role for the final result. In practice, data is generally not given in form of a graph, but in terms of affinity/similarity values between points [START_REF] Ulrike | A tutorial on spectral clustering[END_REF]. For example, in the case of image segmentation, first an affinity graph is constructed to encode the relationship of each data and its neighborhood with certain weight measuring by the weights in the range [0 1], and then a graph partitioning algorithm is applied to this graph.

Chapter 2. Graph based Methods

How to construct a good graph describing the relationships between samples has been widely studied in recent years, and it is still an open problem. The quality of graphs is very sensible to the topological structure, the choice of weighting functions and the related parameters:

1. Topology: The graph topology depicts the relationship between data points.

Whether the graph can accurately determine the local neighborhood of each data point is crucial to infer global structure (meaningful segments) from local information, particularly when the data contain a lot of errors. Formally, given a graph G = (V, E), identified by its vertices V = {v 1 , • • • , v n } and its edges E = {v i , v j }, i ≤ n, j ≤ n, i = j, the topology is defined by identifying every edge {v i , v j } within the unit interval [0, 1] and gluing them together at coincident vertices.

2. Affinity: To calculate the affinity for an edge connecting two vertices, choosing an appropriate feature and distance function (also called weighted function) are the two key factors to be considered. The basic rule is that the weights should be large for pixels that should be associated and small otherwise.

Studies on the semi-supervised learning [START_REF] Bibliography | Robust multi-class transductive learning with graphs[END_REF] and subspace clustering [START_REF] Wright | Sparse representation for computer vision and pattern recognition[END_REF], as well as the task of image segmentation [START_REF] Cour | Spectral segmentation with multiscale graph decomposition[END_REF]][Li et al., 2012], find that a desirable good graph can generate reasonable results. Basically, a good graph [START_REF] Cheng | Learning with l1-graph for image analysis[END_REF][START_REF] Wright | Sparse representation for computer vision and pattern recognition[END_REF] should have the following properties:

• High discriminating power. Pixels from the same object are expected to be assigned large affinities, in contrast with pixels from different objects. Therefore, features selection and their appropriate fusion are critical to capture and compensate the different image properties;

• Sparsity. Many works on graph partitioning state that meaningful results derive from a sparse graph [Shi andMalik, 2000] [Cour et al., 2005] because it conveys with low memory cost valuable semantic information of the original high-dimensional data [START_REF] Wright | Sparse representation for computer vision and pattern recognition[END_REF]. Furthermore, due to storage limitations and the need for efficient solving of eigenvector problems, it is inevitable to build a sparse graph;

• Adaptivity. It happens frequently that the data (pixels/regions) is not evenly distributed. Conventional static graphs use fixed size and shape for the neighborhoods that are used for computing affinity weights, which will potentially generate erroneous associations between pixels. In contrast, it is reasonable to ask that different data points should have their corresponding adaptive neighborhood structure.

Up to now, there is a wealthy literature proposing or using various types of graphs for many tasks of machine learning. In this thesis, we classify them into two classes according to graph affinity computation: Chapter 2. Graph based Methods

Pairwise affinity graph:

The weight is calculated based on pairwise distances (e.g. Euclidean distance) to model local relationships between data points and their neighborhood, that is to say, the method uses the distance between two points to measure their similarity. Typically, topology of neighborhood is determined with parameters. For example, each vertice of ε-ball graph chooses to connect with those points whose pairwise distances are smaller than ε [START_REF] Ulrike | A tutorial on spectral clustering[END_REF].

Datum-adaptive affinity graph:

The weight is computed based on reconstruction coefficients, i.e. the distance between any two data points is independent from the other points. The topology of neighborhood is determined depended on all data samples, and each data is supposed to connect to those points which can represent current data linearly. There are many algorithms, e.g. Locally Linear Manifold Clustering [START_REF] Goh | Segmenting motions of different types by unsupervised manifold clustering[END_REF], Sparse Subspace Clustering [START_REF] Elhamifar | Sparse subspace clustering[END_REF]], 1 -graph [START_REF] Cheng | Learning with l1-graph for image analysis[END_REF][START_REF] Wright | Sparse representation for computer vision and pattern recognition[END_REF]], 2 -graph [START_REF] Peng | Constructing l2-graph for subspace learning and segmentation[END_REF], Low Rank Representation [START_REF] Liu | Robust subspace segmentation by low-rank representation[END_REF][START_REF] Liu | Robust recovery of subspace structures by low-rank representation[END_REF]].

Topology

We discuss the graph topology based on the way how the algorithm decides the neighborhood structure, i.e. pairwise graph or datum-adaptive graph. The former, typically means kNN-graph and ε-graph, has been widely applied in different tasks, such as data clustering. Unlike the pairwise affinity graph, in which the edge weights characterize pairwise relations, the edge weights of sparse graph ( 1 -graph, 2 -graph) and LRR-graph are determined in a group manner, and the weights related to a certain vertex characterize how the rest samples contribute to the sparse representation of this vertex. The second option has become increasingly popular, especially in high-dimensional data analysis.

Pairwise Graph

Most graph-cut approaches for image segmentation build a static graph which only models the local neighborhood relationships between the data points [START_REF] Ulrike | A tutorial on spectral clustering[END_REF]. Classical methods (shown in Fig. 2.1) for selecting connected vertices are:

• The ε-neighborhood graph (ε-graph), which connects all points whose pairwise distances are smaller than ε. The pairwise similarity is chosen almost constant, making the constructed graph unweighted. However, selecting a single ε for all nodes in the graph might not properly capture the neighborhood structure of the data points;

• The k-nearest neighbor graph (kNN-graph) connects every point to all points that are among its K-nearest neighbors, and the similarity is computed using pairwise distances. The fact that the kNN-graph's neighborhood size is fixed may lead to include noisy edges in the neighborhood of a data and a "good" number of nearest neighbors k may be different for different objects; • The fully connected graph connects all points with positive similarity with each other. This construction is only useful if the similarity function itself models local neighborhood relationship. In most cases, Gaussian similarity function w(x i , x j ) = e (-(x i -x j ) 2 )/(2σ 2 )) is chosen to compute the similarity, where the parameter σ controls the width of the neighborhood. Obviously, a "good" σ would help in pulling intra-class objects together and in pushing interclass objects far away from each other. Therefore the parameter σ is critical in generating a reliable affinity matrix by controlling the neighborhood size and scaling pairwise similarities.

1 -Graph

Wright et al. [START_REF] Wright | Robust face recognition via sparse representation[END_REF] proposed to use sparse representation for face recognition. They demonstrated that the 1 linear reconstruction error minimization can naturally lead to a sparse representation for human facial images. Elhamifar and Vidal [START_REF] Elhamifar | Sparse subspace clustering[END_REF] firstly proposed to directly use the sparse representation of vectors lying on a union of subspaces to cluster the data into separate subspaces, which is called sparse subspace clustering. [START_REF] Wright | Sparse representation for computer vision and pattern recognition[END_REF] extended the sparse representation based on 1 -minimization to characterize relationships between the data samples, i.e. termed as 1 -graph, in order to accomplish tasks such as image classification. Cheng et al. [START_REF] Cheng | Learning with l1-graph for image analysis[END_REF] proposed a process to build the 1 -graph and designed a series of new algorithms for various machine learning tasks, e.g. data clustering, subspace learning, and semi-supervised learning. They also concluded the advantages of 1 -graph: first, 1 -graph is robust owing to the overall contextual norm formulation and the explicit consideration of data noises. Second, the sparsity of the 1 -graph is automatically determined instead of manually as in k-NN graph and ε-graph. Finally, the 1 -graph is datumadaptive. The number of neighbors selected by 1 -graph is adaptive to each datum,

Chapter 2. Graph based Methods

which is valuable for applications with unevenly distributed data.

Problem formulation: given a set of data samples X = {x 1 , x 2 , . . . , x n } ∈ R m×n , where n is the data number and m is the feature dimension. Denote the 1graph by G = (V, E, W ), where V is the set of n vertices, each of which is identified with a sample in X , and E is the set of edges connecting a pair of vertices, and W = [w ij ] ∈ R n×n is the weighted matrix. The 1 -graph is constructed in an unsupervised manner, with a goal of automatically determining the neighborhood structure as well as the corresponding connection weights for each datum. The process of building the graph is illustrated in Algorithm 1 [START_REF] Wright | Sparse representation for computer vision and pattern recognition[END_REF].

Algorithm 1: 1 -graph construction 1) Input:the data matrix X.

2) Sparse coding: For each datum x i , solve the l 1 -norm minimization problem:

min α i α i 1 subject to x i = D i α i (2.8)
where 1) and α ∈ R m+n-1 .

D i = [x 1 , . . . , x i-1 , x i+1 , . . . , x n , I] ∈ R m×(m+n-
3) Weight matrix construction: for each couple of samples (x i , x j ), the weight is defined as:

w ij = α i j if i > j α i j-1 if i < j.
(2.9)

2.2.1.3 2 -Graph
Peng et al. [START_REF] Peng | Constructing l2-graph for subspace learning and segmentation[END_REF] proposed a novel scheme for finding sparse similarity graphs by eliminating the effect of errors from the representation but from the dictionary by developing l 2 -graph algorithm to corroborate the effectiveness of the scheme. The l 2 -graph can reveal the latent structure of a data distribution, an ability that is important to a lot of applications. Formally, the l 2 -graph also calculates the sparse coefficients α i like other sparse family algorithms by solving :

min α i 1 2 x i -D i α i 2 2 + λ α i 2 2 , (2.10)
where

D i = [x 1 , . . . , x i-1 , x i+1 , . . . , x n ] ∈ R m×n , α ∈ R n ,
and λ ≥ 0 is a regularization parameter. For each x i , solving above optimization problem gives 2.11) where P = (D T D + λI) -1 , and the union of e i (i = 1, . . . , n) is the standard orthogonal basis of R n , i.e., all entries in e i are zero, except for the i-th entry, which is one. The process of building the graph is illustrated in Algorithm 2 [START_REF] Peng | Constructing l2-graph for subspace learning and segmentation[END_REF]:

α i = P D T x i - e i T P D T x i e i T P e i e i (
Chapter 2. Graph based Methods
Algorithm 2: l 2 -graph construction 1) Input:the data matrix X.

2) Sparse coding: For each datum x i , solve the l 2 -norm minimization problem in Eq.2.10 via Eq.2.11, obtain the optimal solution α i , and normalize α i to give a unit l 2 -norm 3) Eliminate the effects of errors by performing the k-NN or ε-ball method over α i , e.g., αi = H k (α i ), where H k (α i ) retains the k largest coefficients of α i and sets the other entries to zero. 4) Weight matrix construction: Construct the weighted matrix W = [w ij ] by connecting node i, denoted by x i , with node j, denoted by x j . Assign the connection weight:

w ij = |α i j | + |α j i | (2.12) 2.2.1.4 LRR-Graph
Like the task of sparse representation, i.e. to recover the subspace structures from the data containing errors, Liu et al. [START_REF] Liu | Robust subspace segmentation by low-rank representation[END_REF] proposed a novel method termed low-rank representation(LRR), which aims at finding the lowest-rank representation of all data jointly. Formally, let

X = [x i , x 2 , • • • , x n ],
the LRR is defined as: min

Z,E = Z * + λ E 2,1 s.t. X = XZ + E (2.13)
where || • || denotes the nuclear norm, also known as the trace norm or Ky Fan norm (sum of the singular values),

||E|| 2,1 = n j=1 n i=1 ([E] ij ) 2
is the l 2,1 -norm for characterizing noise and the parameter λ > 0 is used to balance the effects of the two parts.

Due to the discrete nature of the rank function, the above problem was relaxed to a nuclear norm optimization problem, and it can be solved in polynomial time. The optimization problem Eq.2.13 is convex and can be solved with Augmented Lagrange Multiplier (ALM) [START_REF] Lin | The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices[END_REF], which minimizes the following augmented Lagrange function:

L = J * + λ E 2,1 + tr(Y t 1 (X -XZ -E)) +tr(Y t 2 (Z -J)) + µ 2 (||X -XZ -E|| 2 F + ||Z -J|| 2 F ).
(2.14)

where J = Z.

Minimizing a rank constraint function can address the problems of l 1 -graph. Yet LRR constructs a dense graph and even a block-diagonal matrix, which is not very desirable for graph-based algorithms. To derive a sparse graph, Zhuang et al. [START_REF] Zhuang | Non-negative low rank and sparse graph for semi-supervised learning[END_REF] proposed a novel Non-Negative Low Rank and Sparse graph (NNLRS) which adds a non-negative and sparse constraint on the original LRR model. Global structure of samples is obtained by the low-rank constraint and the locally linear structure is captured by the sparse constraint. The sparsity of the obtained graph is improved and it gets a satisfactory result. The process of building the graph Chapter 2. Graph based Methods [START_REF] Zhuang | Non-negative low rank and sparse graph for semi-supervised learning[END_REF] is illustrated in Algorithm 3: Algorithm 3: Nonnegative low rank and sparse graph construction (NNLRS)

1) Input: the data matrix X, regularized parameters β and λ, threshold θ.

2) Low Rank Representation:

1. Normalize all the samples xi = x i /||x i || 2 to obtain X = { x1 , x2 , . . . , xn }.
2. Solve the following problem:

min Z,E = Z * + β Z 1 + λ E 2,1 s.t. X = XZ + E, Z ≥ 0 (2.15)
and obtain the optimal solution (Z * , E * ).

Normalize all column vectors of

Z * by z * i = z * i /||z * i || 2 ,
and make small values under given threshold θ zeros by:

ẑ * ij = ẑ * ij if ẑ * ij ≥ θ 0 otherwise 3) Weight matrix construction: Construct the weighted matrix W = [w ij ] by: W = ( Ẑ + ( Ẑ) T )/2.
(2.16)

Affinity

From visual inspection, the affinity matrix contains information about the correct segmentation. Ren and Malik remark that "pixels are not natural entities; they are merely a consequence of the discrete representation of images" captures some of problems of pixel-based representation [START_REF] Ren | Learning a classification model for segmentation[END_REF]].

To overcome these ambiguities, it is necessary to incorporate longer range information

Feature Descriptor

In many machine learning task, ranging from data clustering to image classification, feature descriptors have been extensively studied and applied. There is a wealthy literature on designing a powerful feature descriptor which directly leads to large margins on the performance, such as the success of applying the local binary pattern (LBP) for texture image classification [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF] and the scale invariant feature transforms (SIFT) [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF] for object recognition and segmentation. In this thesis, we are not focused on developing feature descriptor nor list all existing features, instead, we mainly review those popular features used for image segmentation. In particular, graph based image segmentation, which involves affinity graph Chapter 2. Graph based Methods construction. There are hundreds of thousands of feature descriptors in the literature, and there are many good surveys [START_REF] Tuytelaars | Local invariant feature detectors: a survey[END_REF]Mikolajczyk, 2008] [Szeliski, 2010] on this topic. In general, based on the way of feature extraction to form feature descriptors for various applications, features can be categorized as local features and global features.

• Local features: A local feature is an image pattern which differs from its immediate neighborhood. It is usually associated with a change of an image property or several properties simultaneously, although it is not necessarily localized exactly on this change. Local features can be points, but also edgels or small image patches. Typically, some measurements are taken from a region centered on a local feature and converted into descriptors.

• Global features: A global image feature describes an image as a whole, which enables to generalize an entire object with a single vector, such as color histograms (CH). In the context of graph construction, there are many literature concerning the topic: what is a good feature descriptor to measure the affinity between two data samples, which imposes great influence on the final result. For example, Fig. 2.2 present two cases of using different features to measure the affinities, where In graph-oriented image segmentation algorithms, there are generally three ways to use the feature to build the affinity graph:

1. Pixel. In this case, each pixel is treated as a vertice in the graph.

(i) Color. Choosing the right color space is also a hot topic in the image segmentation. Although RGB is universal model for video and image display, it is not good for color scene segmentation because of the high correlation among the R,G,B components [START_REF] Cheng | Color image segmentation: advances and prospects[END_REF]. As we assume that two pixels belong to the same region based on the color homogeneity, however, Chapter 2. Graph based Methods in real natural images, the objects' surface exhibit variance in the highlights, shadows, shadings or texture. Thus, many researchers propose to choose a right color space for ad hoc applications. [START_REF] Shi | Normalized cuts and image segmentation[END_REF] suggested to compute the affinity with HSV value for color image. For example, [START_REF] Jrr Uijlings | Selective search for object recognition[END_REF] proposed using multiple color spaces in order to capture all possible segmentation results. To compare different color spaces, Table 2.2 lists color spaces which can be used to compute the affinity.

(ii) Contour. The cue of contour has highly discriminative power to measure the affinity. Most work [START_REF] Malik | Contour and texture analysis for image segmentation[END_REF][START_REF] Fowlkes | Learning affinity functions for image segmentation: Combining patch-based and gradient-based approaches[END_REF][START_REF] Stella | Multiclass spectral clustering[END_REF]] used the "intervening contour" [START_REF] Leung | Contour continuity in region based image segmentation[END_REF]] as gradientbased feature, illustrated in Fig. 2.3. In more detail, given a pair of pixels, consider the straight-line path connecting them in the image plane. If the pixels lie in different segments, then photometric discontinuity will be found somewhere along the line, otherwise the affinity between the pixels should be large. To use the intervening contour cue, extracting edge information is a precedent yet important step. For example, Canny detector [START_REF] Canny | A computational approach to edge detection[END_REF] can be applied to detect the step changes in brightness. Most work suggest that the oriented energy approach (also known as the "quadrature energy" at angle 0 • ) [START_REF] Knutsson | Texture analysis using two-dimensional quadrature filters[END_REF]] can be used to detect and localize these changes in a combination of steps, peak and roof profile. Briefly, it is defined as:

OE 0 • = (I * f 1 ) 2 + (I * f 2 ) 2 (2.17)
where * is the convolution operator. f 1 and f 2 are the quadrature pairs of filters, differ in their spatial phases. The odd-phase filters f 1 are essentially the first-order derivatives, whereas the even-phase filters are the second-order derivatives, both smoothed with Gaussians. OE 0 • has maximum response for horizontal contours. Rotated copies of the two filter kernels are able to pick up composite edge contrast at various orientations.

In particular, it is worth to mention that the joint work of Arbelaez et al. have extensively investigated different features mentioned above and proposed the mP b in their paper [START_REF] Arbelaez | Contour detection and hierarchical image segmentation[END_REF], taking account of combining color, texture etc., which is the state-of-the-art contour detector.

The proposal of multiscale segmentation stems from addressing the segmentation difficulties: (i) camouflage the object by making its boundary edges faint, and (ii) increase clutter by making background edges highly contrasting, particularly those in textured regions. [START_REF] Barbu | Graph partition by swendsen-wang cuts[END_REF] explicitly controls the Markov chain transitions in the space of graph partitions by splitting, merging and re-grouping segmentation graph nodes. Yu [START_REF] Stella | Segmentation using multiscale cues[END_REF] constructs a unified graph encoding edge cues at different image scales, and optimizes the average Ncut cost across all graph levels. Cour et al. [START_REF] Cour | Spectral segmentation with multiscale graph decomposition[END_REF] solved this limitation by computing sparse affinity matrices at multiple scales, setting up cross-scale constraints, and deriving a new eigen problem for this constrained multiscale cut. The intensity values at pixels p 1 , p 2 and p 3 are similar. However, there is a contour in the middle, which suggests that p 1 and p 2 belong to one group while p 3 belongs to another. Just comparing intensity values at these three locations will mistakenly suggest that they belong to the same group. Right: orientation energy. Somewhere along l 2 , the orientation energy is strong which correctly proposes that p 1 and p 3 belong to two different partitions, while orientation energy along l 1 is weak throughout, which will support the hypothesis that p 1 and p 2 belong to the same group [START_REF] Malik | Contour and texture analysis for image segmentation[END_REF] According to [START_REF] Fowlkes | Learning affinity functions for image segmentation: Combining patch-based and gradient-based approaches[END_REF]] the color cue is best captured using patches than pixels. [Wang et al., 2013b] proposed to use a bunch of patches centered on the interest points to represent a superpixel with color histogram.

Chapter 2. Graph based Methods

For texture, although patches are not the only useful way to capture texture information, many works choose to study the texture using patches. [START_REF] Malik | Contour and texture analysis for image segmentation[END_REF] proposed to use windowed texton histogram to compute pairwise similarity. et al., 2013], semantic segmentation [Carreira et al., 2012a]. As pointed in [START_REF] Yu | Bag of textons for image segmentation via soft clustering and convex shift[END_REF], operation based on regions or superpixels allows one to investigate and design features much more versatile and powerful. Inspired from successful applications of bag-of-words in generic object classes, they constructed a histogram for each superpixel to quantitatively indicate the proportion of contribution from a specific texton. There are several appealing advantages [START_REF] Alexe | Classcut for unsupervised class segmentation[END_REF]] [Li et al., 2012]:

• They provide additional structure, i.e. the set of possible segmentations is reduced to those aligning well with image boundaries;

• They reduce the computational complexity of segmentation;

• They enforce local smoothness since superpixels generally occupy consecutive image area in which pixels are likely to be grouped together;

• Large elongated superpixels incorporate long-range grouping cues, which has shown to improve segmentation substantially;

• Superpixels generated by different methods with varying parameters can capture diverse and multi-scale visual contents of a natural image.

Basically, in low-level unsupervised grouping algorithms, single-scale superpixel is used to build the similarity graph, which is furthered partitioned. Later, many works take advantage of multi-scale superpixels to improve the performance. Here, we give more details on two frameworks both of which are state-of-the-art. Kim et al. [Kim et al., 2010a] constructed a multi-layer graph with pixels and superpixels, generated by the mean shift (MS) algorithm with three various parameters, as nodes. The proposed bipartite graph model with K over-segmentations of an image. A black dot denotes a pixel while a red square denotes a superpixel [START_REF] Li | Segmentation using superpixels: A bipartite graph partitioning approach[END_REF].

w ij =    e -θg g i -g j if i, j ∈ V e -θg ḡi -ḡ j if i, j ∈ V (l) γ if i ∈ V, j ∈ V (l) (2.18)
where θ g is a constant that controls the strength of the weight. g i denotes the mean color of inner pixels of the region i. V ( l) denotes oversegmentaiton in scale l, and the V denotes the set of pixels in original image domain as shown in Figure 2.7

Another framework is proposed in [START_REF] Li | Segmentation using superpixels: A bipartite graph partitioning approach[END_REF], which constructs the affinity graph and concatenates 5 to 6 scale of superpixels generated by MS and Felzenszwalb-Huttenlocher (FH) into an unified matrix diagonally, Figure 2.7 shows the overview of the method.

Arose from the application of superpixels, deriving good-quality superpixel has become an increasing attractive topic. Principally, any kind of segmentation method which can generate regions, can be candidate of the method for superpixels. We list the methods frequently used for generating superpixels in Table 2. 1, and Neubert and Protzel [Neubert and Protzel, 2012] present a survey for comparing different methods quantitatively. the affinity of node i and j as the product of a feature similarity term and spatial proximity term:

w ij = e -F(i)-F(j) 2 2 σ I * e -X(i)-X(j) 2 2 σ X if X(i) -X(j) 2 < r 0 otherwise. (2.19)
where F (i) can be any features like intensity, color and X(i) is the position of node i. σ I and σ X are the parameters to control the speed of decay. Note that the weight w ij = 0 for any pair of nodes that are more than r pixels apart.

Malik et al. [START_REF] Malik | Contour and texture analysis for image segmentation[END_REF] incorporated the intervening contour cue W IC ij and texture cue W T X ij using the idea which is if either of the cues suggests that i and j should be separated, the composite weight, W ij , should be small, formally defined as:

W ij = W IC ij × W T X ij .
(2.20)

Cour et al. [START_REF] Cour | Spectral segmentation with multiscale graph decomposition[END_REF] combined the intervening contour cue and intensity cue W I ij with:

W ij = W I ij × W IC ij + α × W I ij . (2.21)
Cheng et al. [Cheng et al., 2011a] proposed a new solution to fuse multiple types of image features by seeking the sparsity-consistent low-rank affinities from the joint decompositions of multiple feature matrices into pairs of sparse and lowrank matrices. Formally, given a collection of affinity matrices Z 1 , Z 2 , . . . , Z K , in order to take account both the advantages of LRR and use of cross-feature information, the unified affinity matrix is obtained by solving the following convex optimization problem:

min Z 1 ,...,Z K E 1 ,...,E K K i=1 ( Z i * + λ E i 2,1 ) + α Z i 2,1 s.t. X i = X i Z i + E i , i = 1, . . . , K (2.22)
where α > 0 is a parameter. Note that minimizing the term

Z i * + λ E i 2,1
is LRR problem, and Z i 2,1 is a regularization term to ensure the sparsity of resulting matrix. The deriving optimal solution (Z * 1 , Z * 2 , . . . , Z * K ), final unified affinity matrix is defined:

W ij = 1 2 ( K l=1 (Z l ) 2 ij + K l=1 (Z l ) 2 ji ) (2.23)
5. Summary. We list popular features used in graph-oriented algorithm shown in Table 2.2. It can be seen that region based graph construction is more generic and flexible compared with pixel and patch. The disadvantages of using pixel [START_REF] Fowlkes | Learning affinity functions for image segmentation: Combining patch-based and gradient-based approaches[END_REF] is: (1) not "scale invariant"; (2) no explicit control over connectedness; [START_REF] Wang | Graph-based image segmentation using weighted color patch[END_REF] hard to incorporate mid/high-level shape information Chapter 2. Graph based Methods such as continuity. and ( 4) high computational cost to derive solution to the affinity graph.

Concerning the color, each color space has an interesting property, which can efficiently be taken into account in order to make more reliable result. For example, RGB is an additive color system based on trichromatic theory and nonlinear with visual perception. This space color seems to be the optimal one for tracking applications. The HSV is interesting in order to decouple chromatic information from shading effect. The Lab color system approximates human vision, and its component closely matches human perception of lightness. The Luv components provide an Euclidean color space yielding a perceptually uniform spacing of color approximating a Riemannian space. Busin et al. [START_REF] Busin | Color space selection for color image segmentation by spectral clustering[END_REF] proposed a method which automatically selects a specific color space among a set of color spaces in order to preserve their own specific properties.

Concerning the local features, an additional step, called "coding and pooling", to construct a feature vector descriptor. One example is illustrated in the generation of textons with K-means in Fig. 2.5. More detail can be found in [START_REF] Boureau | A theoretical analysis of feature pooling in visual recognition[END_REF].

Weighted Function

We now discuss distance metrics for computing the w ij . Deciding a good function usually depend on the task at hand. For computing the affinity or similarity, frequently used approaches in the literature, include Euclidean distance and the χ 2 distance (see examples in section 2.2.2). We list several frequent distance metric in Table 2.3. More details can be found in [START_REF] Satu | Graph clustering[END_REF][START_REF] Jrr Uijlings | Selective search for object recognition[END_REF]

Graph Cut Cost Function

Image segmentation can be deemed as cutting edges of a suitable graph to divide data samples into disjoint groups. At the beginning, the graph is partitioned according to a fixed threshold and local properties defined by the Gestalt laws, therefore, global properties of segmentation are hard to guarantee. Then, Wu and Leahy [START_REF] Wu | Tissue classification in mr images using hierarchical segmentation[END_REF] proposed the first graph cut with global cost function. From then on, the graph cut based methods have attracted increasing interest on designing different cost functions for image segmentation. In particular, graph cut based methods are extensively applied for image segmentation since the Normalized cut (Ncut) [START_REF] Shi | Normalized cuts and image segmentation[END_REF] was proposed, which provides a significant progress over the previous graph cuts methods, both from a theoretical and practical perspective. The normalized cut criterion is further adopted to multi-way partitioning algorithm [Ng et al., 2001, Yu and[START_REF] Stella | Multiclass spectral clustering[END_REF].

Give a graph G = (V, E), where V = {v 1 , • • • , v n }
is a set of vertices corresponding to image elements such as pixels or regions in the Euclidean space. E is a set of edges connecting a pair of vertices. Each edge (u i , u j ) ∈ E has a corresponding weight w(u i , u j ) which measures certain similarity based on the property between Chapter 2. Graph based Methods the two vertices connected by that edge. The goal of graph cut is to cut or break the edges in E, so as to divide the vertices in V into disjointed groups

V i ∪ V j = V and V i ∩ V j = φ, (i, j ∈ {1, • • • , k}, i = j).

Minimal Cut

What is a graph cut? It is related to a set of edges by which the graph G will be partitioned into two disjoint sets A and B. The degree of dissimilarity between these

Chapter 2. Graph based Methods

Table 2.3: List of frequent distance metrics for weight calculation.

d i = (d i (1), d i (2), . . . , d i (K)
) is an K-dimensional vector in Euclidean space, A and B are two sets of data samples.

Distance Definition

Eulidean distance

K k=1 (d i (k) -d j (k)) 2 Manhattan distance K k=1 |(d i (k) -d j (k))| Cosine distance arccos d i • d j √ K k=1 (d i (k) 2 ) √ K k=1 (d j (k) 2 ) χ 2 distance 1 2 K k=1 [d i (k)-d j (k)] 2 d i (k)+d j (k) Histogram intersection K k=1 min(d i (k), d j (k)) Jaccard index |A∩B| |A∪B|
two sets can be computed as the total weight of the edges that have been removed. As a consequence, the segmentation of an image can be interpreted as a graph cut and associated with the following cut criterion:

cut(A, B) = u∈A, v∈B w(u, v) (2.24)
Wu and Leahy [START_REF] Wu | Tissue classification in mr images using hierarchical segmentation[END_REF] proposed a clustering method based on the minimum cut criterion in Eq. (2.24), namely minimal cut. Solving this minimal cut is well studied problem, for example [START_REF] Ralph | Multi-terminal network flows[END_REF] in polynomial time. In particular, the author also seek to more general case, that is partitioning a graph into k-subgraphs, such that the maximum cut can be efficiently solved by recursively finding the minimum cuts that bisect the existing segments.

As noticed by Wu and Leahy, the minimum cut criteria has bias on small sets of isolated nodes in the graph, i.e. short boundaries, since the cut increases with the number of edges going across the two partitioned parts.

Ratio Regions

Cox et al. [START_REF] Cox | ratio regions": A technique for image segmentation[END_REF] proposed a cost function called ratio regions to alleviate Chapter 2. Graph based Methods minimum cut bias by incorporating both interior region and boundary information. The ratio region criteria minimizes a new cost function based on the ratio of the cost of the perimeter of the segmented region to the benefit assigned to its enclosed interior. Formally, let P be a directed path in graph G that starts and finishes at the same vertices v, denoted by cost(P ) representing the length of the boundary. Segment-area cost is denoted by weight(P ), the ratio region is defined as:

Regioncut(A, B) = cost(P ) weight(P ) (2.25)
Notice that the cost function favors large regions in the image and the region characteristic of smoothness is measured using the area and perimeters. In particular, the limitation of this criteria is that it can only segment enclosed objects due to its definition. Rao (personal communication) gives a polynomial-time algorithm for finding a cut that minimizes this function with binary search through a space of max-flow problems.

Normalized Cut

Shi and Malik [START_REF] Shi | Normalized cuts and image segmentation[END_REF] proposed a new disassociation measure called as Normalized cut (Ncut), to avoid the minimal cut bias, i.e. segmenting small sets of points. Ncut computes the cut cost as a fraction of the total edge connections to all the nodes in the graph, rather than only taking account the value of total edge weight connections between two partitions. Formally, Ncut is defined as:

N cut(A, B) = cut(A, B) vol(A) + cut(A, B) vol(B) (2.26)
where vol( • ) is the total connection from vertices in a set (e.g. A) to all vertices in the graph G. Formally, vol(A) = u∈Av∈V w(u, v), where w(u, v) is weight on edge (u, v) and can be computed with certain affinity function (see section 2.2.2). cut(A, B) is defined in Eq. (2.24). Finding a cut that minimizes this cost function is NP-complete. Shi and Malik also present a method to compute the optimal partition using spectral graph theory [START_REF] Ulrike | A tutorial on spectral clustering[END_REF]. However, Ncut based method (e.g. [Cour et al., 2005] [Yu and[START_REF] Stella | Multiclass spectral clustering[END_REF]) tend to break large uniform regions because of the normalization prior. More precisely, the cost criteria favors balanced partitions, at the risk of breaking object boundaries or large uniform region (e.g. sky and grass) into chunks.

Mean Cut

Wang and Siskind [START_REF] Wang | Image segmentation with minimum mean cut[END_REF] proposed a cost function called as mean cut with no bias, such as short boundary, large regions, or similar weighted regions. The cost criteria finds cuts which minimize the average edge weight in the cut boundary. Formally, it is defined as:

meancut(A, B) = cut(A, B|w(u, v)) cut(A, B|1) (2.27)
where cut(A, B|W (u, v)) means the cut cost between region A and B given the edge weight w(u, v), and cut(A, B|1) is defined similarly with all edge weights to be 1, i.e. boundary length.

The mean cut criteria can generate both open and closed boundaries and guarantees that partitions are connected as well as does not impose any bias. The author also present polynomial-time global optimization algorithm for this cost function, yet only can be applied in connected planar graphs. To solve the Eq.2.27, there are three reductions: 1) from minimum mean cut to minimum mean simple cycle; 2) from minimum mean simple cycle to negative simple cycle and 3) from negative simple cycle to minimum-weight perfect matching.

Ratio Cut

Wang and Siskind [START_REF] Wang | Image segmentation with ratio cut[END_REF] generalized the mean cut cost function by removing the restriction that edge weights are 1 and call this new cost function as ration cut. It normalizes the first boundary cost by the second boundary cost, and is formally defined as:

Ratiocut(A, B) = cut1(A, B) cut2(A, B) (2.28)
where cut1(A, B) and cut2(A, B) are defined on the graphs of different iterations.

The author adopts the same reduction process as mean cut to solve this NP-hard problem.

Graph Partitioning

Solving most graph cut cost functions yields NP-complete problem. To approximate the optimal solution, there are two broad categories of methods, i.e. local (e.g. the Kernighan-Lin [START_REF] Kernighan | An efficient heuristic procedure for partitioning graphs[END_REF]] algorithm) and global (e.g. Spectral partitioning). The local method's major drawback is the arbitrary initial partitioning of the vertex set, which can affect the final solution quality. Global methods rely on properties of the entire graph and do not rely on an arbitrary initial partition. More in detail, they can be of three different types, as suggested in [START_REF] Karypis | A fast and high quality multilevel scheme for partitioning irregular graphs[END_REF]], listed in following:

• Spectral methods. Many algorithms have been developed that find a reasonably good partition with spectral partitioning, where a partition is derived from the spectrum of the adjacency matrix. Shi and Malik approximate computing the minimum normalized cut criterion with eigen-problem, later, Weiss has shown how the eigenvector problem relate to more standard spectral partitioning methods on graphs. The core idea is to use matrix theory and linear algebra to study properties of the incidence matrix, W , and the Laplacian matrix, L = D -W , which provide a great deal of information about graph G. Using the spectrum of graph Laplacian, which is symmetric positive semidefinite matrix, can capture essential cluster structure of a graph, i.e. the eigenvectors of the graph Laplacian or its variants. This can be graphically illustrated in Fig. 2.8. This is a rich area of mathematics and using eigenvectors of the Laplacian for finding partitions of graphs can be traced back to [Cheeger], [START_REF] William | Lower bounds for the partitioning of graphs[END_REF], and [START_REF] Fiedler | A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory[END_REF]. For a tutorial introduction to spectral graph theory, Chung [START_REF] Chung | Spectral Graph Theory[END_REF] presented a good survey on spectral clustering. In mathematics, the spectrum of a symmetric positive semi-definite matrix is the complete real positive eigenvalues 0 ≤ λ 1 ≤ . . . ≤ λ n , by solving following generalized eigen-problem: However, these methods are very expensive since they require the computation of the eigenvector corresponding to the second smallest eigenvalue (Fiedler vector). Execution time of the spectral methods can be reduced if computation of the Fiedler vector is done by using a multilevel algorithm.

Lf = λDf (2.
• Geometric partitioning algorithm. These methods use the geometric information of the graph to find a good partition. This algorithm produces partitions that are provably within the bounds that exist for some special classes of graphs (see an example shown in Fig. 2.9). Although these methods tend to be fast yet obtain worse partitions than those obtained by spectral methods [START_REF] Karypis | A fast and high quality multilevel scheme for partitioning irregular graphs[END_REF]]. Moreover, they are applicable only if coordinates are available for the vertices of the graph.

• Multilevel graph partitioning. These methods reduce the size of the graph (i.e., coarsen the graph) by collapsing vertices and edges, partitions the smaller graph, and then uncoarsens it to construct a partition for the original graph. This process is graphically illustrated in Fig. 2.10. At beginning, researchers designed the multilevel graph partitioning to reduce the computational time at cost of worse partition quality. Later, many methods have been proposed to give both fast execution times and very high quality results. [START_REF] Hendrickson | A multi-level algorithm for partitioning graphs[END_REF] construct a sequence of increasingly coarse approximations to a graph, then the smallest graph is partitioned by spectral method, finally the sequence of graphs are projected back to the original graph, periodically improving it with a local refinement algorithm, such as Kernighan-Lin algorithm [START_REF] Kernighan | An efficient heuristic procedure for partitioning graphs[END_REF]. In particular, this work showed that multilevel schemes can provide better partitions than spectral methods at lower cost for a variety of finite element problems.

Chapter 2. Graph based Methods

Summary

Graph cut methods are clearly adapted to the objective of segmentation, i.e. minimizing certain cut cost function makes vertices in different sets (dissimilar vertices) or groups vertices in the same sets (similar vertices). Many different cut criteria have been proposed. In practice, to implement each cost function, finding the solution is a NP-hard problem. Therefore, efficient approximations of the solution need to be studied. Since these methods form different basis for general image segmentation problem, they can be combined with other segmentation techniques for further extension.

Table 1 summarizes different graph cut methods introduced above, including the cost functions, optimization methods, complexity and their properties.

Table 2.4: Comparisons between different graph cut cost functions

Graph cut methods

Objective function

Optimization method

Computational complexity Bias

Minimal cut [START_REF] Wu | Tissue classification in mr images using hierarchical segmentation[END_REF]]

M incut(A, B)= u∈A,v∈B w(u, v)
Gomory-Hu's K-way maxflow algorithm Polynomial time

Short boundaries

Ratio regions [START_REF] Cox | ratio regions": A technique for image segmentation[END_REF] Regioncut(A, B)= cost(P ) weight(P )

Local rearching for the solution O(n log(n))

Smooth boundaries

Ncut [START_REF] Shi | Normalized cuts and image segmentation[END_REF]]

N cut(A, B)= cut(A,B) vol(A) + cut(A,B) vol(B) Generalized eignsystem O(mn)

Similar weight partition

Mean Cut [START_REF] Wang | Image segmentation with minimum mean cut[END_REF]]

M eancut(A, B)= cut(A,B|w(u,v)) cut(A,B|1)

minimum-weight perfect matching polynomial time No bias

Ratio cut [START_REF] Wang | Image segmentation with ratio cut[END_REF]]

Ratiocut(A, B)= cut1(A,B) cut2(A,B) Baseline method O(n

Introduction

Image segmentation is a fundamental problem in computer vision. The objective of image segmentation is to segment an image into several non-overlapping regions that are deemed meaningful according to some objective criterion, homogeneity in some feature space or separability in some other one for example. Image segmentation have been a long studied problem. Since the first image segmentation approaches published more than 40 years ago, see for instance [START_REF] Muerle | Experimental evaluation of techniques for automatic segmentation of objects in a complex scene[END_REF], thousands of algorithms have been proposed, and they can be very different using different mathematical models or according to different application goals. Typically, in many literature surveys [START_REF] Fu | A survey on image segmentation[END_REF][START_REF] Luccheseyz | Color image segmentation: A state-of-the-art survey[END_REF][START_REF] Peng | A survey of graph theoretical approaches to image segmentation[END_REF], existing image segmentation methods can be categorized as unsupervised or supervised. Unsupervised methods are also called as low-level or bottom-up methods in the literature. In this thesis, we consider those methods that are without any human interactions nor prior knowledge involving training process or objectclass specific information beforehand. In many instances of supervised setting, also called as top-down segmentation or high-level segmentation, there are two versions, namely weakly supervised and fully supervised methods. The former tries to only use the image annotation which describes the visual concepts depicted in the image, instead of manually segmented result for each pixel. Section 3.3 relates to supervised methods in the sense that there is human interaction, e.g. drawing a bounding box Chapter 3. Literature Review: Image Segmentation containing objects in the interactive segmentation, and the co-segmentation or object discovery models the segmentation processing provided at least multiple images share a common object. Fully supervised methods involve tasks such as semantic segmentation, image parsing and scene understanding, which need to recognize and label each pixel as a semantic object or event within the image, more detail can be found in Section 3.4. Note that the literature review is performed from the view-point of general natural image segmentation, specific domain such as medical image processing is not included in the survey.

Unsupervised Image Segmentation

Unsupervised image segmentation remains a daunting challenge and a hot research topic for computer vision. It is mostly defined as a bottom-up process, employing no high-level knowledge. Low-level knowledge such as coherence of brightness, color, texture, gradient or motion is exploited to design various approaches. Unsupervised image segmentation techniques can be classified into two broad families: (1) region-based, and (2) edge-based approaches. Region-based approaches try to find partitions of the image pixels into sets corresponding to coherent image properties such as brightness, color and texture. Edge-based approaches usually start with a first stage of edge detection, followed by a linking process that seeks to exploit curvilinear continuity.

I am not going to survey the review from the above point of view, instead, I would roughly summarize the literature under the whole domain development. As we know, there are countless papers published around the topic of image segmentation. In following review, those segmentation methods or features, which pursue optimal performance on single or a few images, will be classified to the early stage of image segmentation. While those approaches, which combine different algorithms or different parameters of the same algorithm and validated on large image annotated benchmarks with segmentation metrics, will be deemed as modern stage of image segmentation. A broad family of approaches to segmentation make use of low-level features such as brightness, color, or texture, they are rough be introduced as follows.

• Histogram Thresholding. Histogram thresholding is one of the widely used techniques for gray-level image segmentation. It assumes that images are composed of regions with different gray level ranges, the histogram of an image can be separated into a number of peaks (modes), each corresponding to one region, and there exists a threshold value corresponding to valley between the two adjacent peaks. Color images can also be thresholded. One approach is to perform threshold for each of the RGB components of the image and then combine them with an AND operation, see more information in [START_REF] Cheng | Color image segmentation: advances and prospects[END_REF]. Automatic thresholding techniques can be roughly categorized as global thresholding and local thresholding. The Otsu's method [START_REF] Otsu | A threshold selection method from gray-level histograms[END_REF] and Kittler and Illingworth's method [START_REF] Kittler | Minimum error thresholding[END_REF] are the most popular methods for image thresholding. Other interesting methods are, as summarized in [START_REF] Sezgin | Survey over image thresholding techniques and quantitative performance evaluation[END_REF] [START_REF] Otsu | A threshold selection method from gray-level histograms[END_REF].

• Contour detector. The problems of contour detection and segmentation are related, but not identical. In general, contour detectors offer no guarantee that they will produce closed contours and hence do not necessarily provide a partition of the image into regions. But, one can always recover closed contours from regions in the form of their boundaries. Early edge detection methods, such as the Robert edge detector [START_REF] Gilman | MACHINE PERCEPTION OF THREE-DIMENSIONAL soups[END_REF], the Canny edge detector [START_REF] Canny | A computational approach to edge detection[END_REF] are based on the abrupt changes in image intensity. Later, more complex techniques are obtained by considering the response of the image to a family of filters of different scales and orientations, such as Gaussian smoothing at multiple scales [START_REF] Andrew P Witkin | Scale-space filtering[END_REF], and the Oriented Energy approach [START_REF] Freeman | The design and use of steerable filters[END_REF]. In modern local methods, one develops a powerful contour detector by taking into account color and texture information and make use of cue combination [START_REF] Malik | Contour and texture analysis for image segmentation[END_REF]. Many researcher still concern the issue, that is objects may appear at large scales of the image. Ren [START_REF] Ren | Multi-scale improves boundary detection in natural images[END_REF] combines strengths from both large-scale detection (robust but poor localization) and small-scale detection (detail-preserving but sensitive to clutter) multiple scales of the local operators developed by [Ar-belaez et al., 2011]. As pointed in [START_REF] Ren | Discriminatively trained sparse code gradients for contour detection[END_REF], there are something in common among modern contour detection methods: they are built on top of a set of gradient features measuring local contrast of oriented discs, using chisquare distances of histograms of color and textons. For example, the stateof-the-art contour detector, global probability boundary (gPb) [START_REF] Arbelaez | Contour detection and hierarchical image segmentation[END_REF], whose output E(x, y, e) predicts the probability of an image boundary at location (x, y) and orientation. They also present the method to build hierarchical regions by exploiting the information from this contour signal using a sequence of two transformations, the Oriented Watershed Transform (OWT) [START_REF] Arbelaez | Boundary extraction in natural images using ultrametric contour maps[END_REF] and Ultrametric Contour Map (UCM) [START_REF] Arbelaez | Boundary extraction in natural images using ultrametric contour maps[END_REF]. • Clustering. Cluster analysis is one of the most fundamental modes of understanding and learning. Clustering is the unsupervised classification of patterns (observations, data items, or feature vectors) into groups (clusters). It has broad application in many contexts and appealed by researchers in many disciplines. Thousands of clustering algorithms have been proposed, which makes it extremely difficult to review all the published approaches. We refer readers to the review by Jain and Dubes [START_REF] Anil | Algorithms for clustering data[END_REF], Jain et al.

[ [START_REF] Anil K Jain | Data clustering: a review[END_REF] and Jain[Jain, 2010] for more information.

Clustering broadly divided into two groups: hierarchical and partitional (hierarchical methods produce a nested series of partitions, while partitional methods produce only one). Most hierarchical clustering algorithms are variants of the single-link [START_REF] Peter | Numerical taxonomy. The principles and practice of numerical classification[END_REF], complete-link [START_REF] King | Step-wise clustering procedures[END_REF]. The difference between the single-link and complete-link algorithm is the distance between two clusters, which are measured by the minimum and maximum of the distances between all pairs of patterns drawn from the two clusters, respectively. In either case, two clusters are merged to form a larger cluster based on minimum distance criteria. Compared to hierarchical clustering algorithms, partitional clustering algorithms find all the clusters simultaneously as a partition of the data and do not impose a hierarchical structure.

The most popular and the simplest clustering algorithm is K-means. The basic idea of the K-means method is to cluster a set of points in some metric space into K clusters by iteratively improving K cluster centres and grouping each point to the cluster with the closest centre (called hard assignment); the centres are chosen to minimize the sum-of-squares of the intra-cluster distances. Such iterative algorithms for clustering provide a partial clustering for the data already seen from an unknown data stream to be clustered. In order to cluster a large database, incremental clustering is useful for clustering data sets that undergo frequent modification, such as addition, removal or editing of the data elements. It is noteworthy that in iterative clustering, the order in which the data are processed may significantly affect the resulting clusters. To avoid these problems, commonly the existing partial clustering is constantly optimized with respect to some carefully selected global measure as new data are processed, reassigning also the old data as necessary. For instance, fuzzy c-means [START_REF] James | Pattern recognition with fuzzy objective function algorithms[END_REF], is an extension of K-means where Chapter 3. Literature Review: Image Segmentation each data point can be a member of multiple clusters with a membership value (soft assignment).

Compared to the traditional algorithm such as K-means or single linkage, spectral clustering has many fundamental advantages. Results obtained by spectral clustering often outperform the traditional approaches, spectral clustering is very simple to implement and can be solved efficiently by standard linear algebra methods. Spectral clustering is typically based on computing the eigenvectors corresponding to the second-smallest eigenvalue of the normalized Laplacian or some eigenvector of some other matrix representing the graph structure.

As a single cluster can be well modeled by a Gaussian distribution, it is straightforward to assume that each probabilistic distribution is Gaussian, so known as the mixture of Gaussian model (GMM). Then the problem of segmenting the data is converted to a model estimation problem. The EM algorithm [START_REF] Arthur P Dempster | Maximum likelihood from incomplete data via the em algorithm[END_REF] is used to infer the parameters in mixture models. Recently established minimum description length (MDL) [START_REF] Ma | Segmentation of multivariate mixed data via lossy data coding and compression[END_REF], explicitly cast segmentation problem as density estimation, which entails estimating the mixture of all the models and then assigning each data point to the model with the highest likelihood. But when the data is highdimensional, the feature space is usually sparse, making it difficult to distinguish high-density regions from low-density regions. Subspace space clustering (SSC) [START_REF] Elhamifar | Sparse subspace clustering[END_REF] overcome this limitation by finding clusters embedded in low-dimensional subspaces of the given high-dimensional data. SSC uses the sparsest representation produced by 1 -minimization to define the affinity matrix of an undirected graph. Then subspace segmentation is performed by spectral clustering algorithms such as the Normalized cuts [START_REF] Shi | Normalized cuts and image segmentation[END_REF]].

• Mode-seeking. Mode seeking provides a versatile tool for feature space analysis by finding local density maxima (or modes) in the feature space. In mode seeking clustering, data belonging to the same cluster fall within the same density attraction basin where the attraction force points to the direction that mostly increases the estimated density. Mean shift (MS) [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF] is regarded as one of the most canonical mode seeking algorithms with numerous real applications in computer vision. Given a collection of data samples distributed according to an unknown distribution on a Euclidean space, the mean shift is designed to iteratively locate the underlying modes together with the points that belong to the cluster associated with each mode. The success of the mean shift algorithm inspired many researchers to develop different variants of the standard version. For instance, there is a great deal of works that focus on improving the mean shift in: 1) speed [START_REF] Paris | A topological approach to hierarchical segmentation using mean shift[END_REF];

2) accuracy via adaptive bandwidths [START_REF] Georgescu | Mean shift based clustering in high dimensions: A texture classification example[END_REF] and asymmetric kernels [START_REF] Yilmaz | Object tracking by asymmetric kernel mean shift with automatic scale and orientation selection[END_REF]; 3) manifold. Subbarao and Meer [START_REF] Subbarao | Nonlinear mean shift for clustering over analytic manifolds[END_REF] extend the Euclidean MS formulation to two particular analytic manifolds, Grassmann manifolds and Lie groups, which is actually the nonlinear MS. Inspired by the nonlinear MS, Medoid shift [START_REF] Yaser | Mode-seeking by medoidshifts[END_REF] and the quick shift [START_REF] Vedaldi | Quick shift and kernel methods for mode seeking[END_REF] algorithms are designed to cluster data on non-Euclidean spaces and employed for image segmentation and categorization. [START_REF] Ertan | Intrinsic mean shift for clustering on stiefel and grassmann manifolds[END_REF] generalize mean shift to non-linear manifolds and intrinsically model curved mean shift space. Yu et al. [START_REF] Yu | Bag of textons for image segmentation via soft clustering and convex shift[END_REF] modify mode seeking method called as convex shift to group superpixels using bag of features. Segmentation generated by mean shift [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF], quick shift [START_REF] Vedaldi | Quick shift and kernel methods for mode seeking[END_REF] and convex shift [START_REF] Yu | Bag of textons for image segmentation via soft clustering and convex shift[END_REF].

• Graph based methods. In Chapter 2, we focused on reviewing unsupervised graph based methods with cost functions, which are designed to minimize the similarity between pixels that are then split with graph partitioning method.

In this Chapter, we briefly review other graph based methods in unsupervised manner. More specifically, we will introduce the minimal spanning tree based methods, since other graph based methods such as graph cut on Markov random field models and the shortest path based methods incorporate high-level knowledge or user's guidance to segment semantic objects in images. We will discuss them in the supervised segmentation setting.

The minimal spanning tree (MST) is a spanning tree with the smallest weights among all spanning trees. The MST is essentially related to graph clustering, where the MST can be used to compute the weights between two vertices. A typical MST method, such as the Prim's algorithm [START_REF] Clay | Shortest connection networks and some generalizations[END_REF], is constructed by iteratively adding the frontier edge of the smallest edge-weight. For instance, Felzenszwalb and Huttenlocher' s (FH) graph-based method [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF]] is a very efficient algorithm and recently it has Chapter 3. Literature Review: Image Segmentation been frequently applied in generating superpixels [START_REF] Li | Segmentation using superpixels: A bipartite graph partitioning approach[END_REF][START_REF] Wang | A graph-cut approach to image segmentation using an affinity graph based on l0-sparse representation of features[END_REF] or as starting step in other high-level machine learning tasks [van de [START_REF] Koen | Segmentation as selective search for object recognition[END_REF]. The algorithm considers both the difference across two regions and the difference inside a region. It merges regions greedily according to these differences and returns a gross segmentation. Fig. 3.5 illustrates the segmentation results obtained with this algorithm. [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF].

• Partial differential equation-based methods. Those methods are more recent, can be very efficient and have broad applications in image processing, such as image interpolation, denoising and segmentation, etc. In this review, we briefly introduce classical PDE methods for segmentation. The basic idea is to evolve a curve, subject to constraints from a given image, in order to detect objects in that image. For instance, starting with a curve around the object to be detected, the curve moves toward its interior normal and has to stop on the boundary of the object. The early methods in segmentation are parametric methods, such as the famous snake [START_REF] Kass | Snakes: Active contour models[END_REF] and its variants. Later, the level set method for capturing dynamic interfaces and shapes was introduced in Osher and Sethian [START_REF] Osher | Fronts propagating with curvature-dependent speed: algorithms based on hamilton-jacobi formulations[END_REF] and adapted for segmentation in Caselles [START_REF] Caselles | Geometric models for active contours[END_REF] and Malladi et al. [START_REF] Malladi | Shape modeling with front propagation: A level set approach[END_REF]. The basic idea of the level set method is to represent a contour as the zero level set of a higher dimensional function and formulate the motion of the contour as the evolution of the level set function. The active contour models in level set can also be classified as edge-based methods, e.g. geodesic active contour (GAC) [START_REF] Caselles | Geodesic active contours[END_REF] and region-based method, e.g. the Mumford-Shah model [START_REF] Mumford | Optimal approximations by piecewise smooth functions and associated variational problems[END_REF]] and its piecewise constant version addressed numerically with the Chan-Vese (CV) model [START_REF] Tony | Active contours without edges. Image processing[END_REF]. In particular, the CV model has gained great success due to its simplicity and efficiency. Based on CV model, many works have been devised to generalize it, e.g. extending the CV model to multi-channel images [START_REF] Tony F Chan | Active contours without edges for vector-valued images[END_REF] and multiphase model [Vese and [START_REF] Luminita | A multiphase level set framework for image segmentation using the mumford and shah model[END_REF]. More recently, some works improved the active contour model to segment images with intensity inhomogeneities [START_REF] Zhang | Global data association for multiobject tracking using network flows[END_REF][START_REF] Yu Qian Zhao | A level-set method based on global and local regions for image segmentation[END_REF]. Another direction is incorporating prior shape [Cootes et al., 1995] [Chan and[START_REF] Chan | Level set based shape prior segmentation[END_REF] into the energy function to make it robust to occlusion, severe pollution etc.

As discussed in many works, edge-based, region-based or prior shape based methods have advantages and weaknesses. State-of-the-art models, e.g. [START_REF] Ali | An integrated region-, boundary-, shapebased active contour for multiple object overlap resolution in histological imagery[END_REF], try to combine all their merits in a unified energy function to obtain more reasonable segmentations.

Foregound/Background Segmentation

Foreground/background segmentation has been seen as an important and even necessary precursor for object recognition when supervisory information is available in the form of labeled training data (full image or, in interactive settings, smaller groups of pixels).

Interactive Segmentation

Interactive segmentation is an important problem in computer vision where discrete optimization techniques have had a significant impact. Generally the user assigns some pixels to the foreground and background regions manually and these constrain an energy function, which is optimized using a global minimization algorithm. The goal is to allow the user to quickly segment foreground objects from the rest of the image. This is done via iterative process, where the user has the opportunity to correct or improve the current segmentation as the algorithm progresses.

There have been proposed a wealthy literature on this topic. One of them is the shortest path based methods. They are to finding the shortest path between two vertices in a weighted graph, i.e. it will connect the two nodes with the minimized sum of edge weights. In image segmentation context, the problem of finding the minimum cost path between the two vertices corresponds to finding the best boundary segment. Several algorithms can be used to solve it, one of which is Dijkstra's algorithm. For instance, Intelligent scissors [Mortensen and [START_REF] Eric | Intelligent scissors for image composition[END_REF] find the object contour via shortest paths in a graph near the boundary of the target clicked by user. Given an initial pixel s by user, the shortest paths can derive an optimal curve from s to any pixel within the image. So with user clicking the mouse around the target, the contour of the target can be computed with a shortest paths in a graph.

In these approaches, graph-cuts (also known as s/t cut) methods have been quite popular for foreground/background segmentation [Boykov and[START_REF] Boykov | Graph cuts and efficient nd image segmentation[END_REF]Kolmogorov, 2004], for that they can obtain optimal solution for defined energy minimization problems that involve region and boundary properties. These methods employ appearance models for the foreground and background which are estimated through user interactions. Graph-cut method demands user input seeds in the foreground region and background region. For example, the lazy snapping [START_REF] Li | Lazy snapping[END_REF] require loosely foreground position seed points and editing the boundary to modify results. [START_REF] Bagon | What is a good image segment? a unified approach to segment extraction[END_REF] require a user click a point inside the object of interest, and use EM to estimate a sophisticated self-similarity energy. GrabCut [START_REF] Rother | Grabcut: Interactive foreground extraction using iterated graph cuts[END_REF] demands less human interaction, where a simple rectangular seed around the object of interest is initialized. It iteratively uses graph-cuts in the model of foreground/background. Chen et al. [START_REF] Chen | Adaptive figure-ground classification[END_REF] proposed adaptive figure-ground classification algorithm with a prior bounding box defined by user. The image is oversegmented with mean shift [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF], then the background and foreground regions are gradually refined and multiple segmentations according to several evaluation scores are selected. The final segmentation is determined with a voting or weighted combination scheme. Liu et al. [START_REF] Liu | Paint selection[END_REF] propose "Paint Selection" which gives user instant feedback when they drag the mouse. Figure 3.7: Illustration of comparison of interactive segmentation method. The top row shows the user interaction required to complete the segmentation or matting process: white brush/lasso (foreground), red brush/lasso (background), yellow crosses (boundary). The bottom row illustrates the resulting segmentation.

Class Segmentation

Given a set of training examples from an object class, class segmentation pursue to be able to automatically learn a class specific prior knowledge to categorize and segment images which contains the specific object class. The class segmentation differs from unsupervised image segmentations and interactive segmentation in that it not only divides the image into a set of coherent regions, but also assigns a class labels to each region.

Many methods have been proposed on such topic to use top-down knowledge to leverage the segmentation performance. Learning a prior class-specific shape model have been intensively studied for the task of object recognition. Borenstein and Ullman 2002 used prior shape characteristics of objects within a given class to guide the segmentation process, where the segmentation result is obtained by fitting the fragments to the image, which is analog to jigsaw-puzzle. Leibe and Schiele 2006 defined a implicit shape model using codebook which groups and encodes specific object class's local appearance represented with patches centered around interest points over all training images. Alexe et al. 2010 learned the object class's shape structure with a reference coordinate frame common across images. Such reference frame is determined in every image with a salient object detector.

Cosegmentation/Object Discovery

The term "cosegmentation" (also known as object discovery) is first coined in [START_REF] Rother | Cosegmentation of image pairs by histogram matching-incorporating a global constraint into mrfs[END_REF], and have attracted increasing interest in computer vision. The early aim of cosegmentation is to simultaneously segment the common parts within a pair of images by proposing a generative model, which encodes constraints (such as spatial coherency) in the formulation of MRF. As shown in Figure 3.8, cosegmentation is superior to classical foreground/background methods (GrabCut [START_REF] Rother | Grabcut: Interactive foreground extraction using iterated graph cuts[END_REF]) which do not model joint foreground. However, numerous methods have been proposed, they can only handle a pair of images with the same object at a time [START_REF] Rother | Cosegmentation of image pairs by histogram matching-incorporating a global constraint into mrfs[END_REF], and/or need user interaction [START_REF] Batra | icoseg: Interactive co-segmentation with intelligent scribble guidance[END_REF]. [START_REF] Rother | Cosegmentation of image pairs by histogram matching-incorporating a global constraint into mrfs[END_REF]: given a pair of images, the task is to segment the common part in both images. Compared to GrabCut [START_REF] Rother | Grabcut: Interactive foreground extraction using iterated graph cuts[END_REF], which segment the foreground individually, cosegmentation outperforms traditional foreground/background method.

There has been increasing interest on the developing cosegmentation by taking into account: (1) multiple object classes and 2) more images. Their target is to jointly segment K different objects classes from multiple images, each of which contains unknown subset of K object classes. [START_REF] Vicente | Object cosegmentation[END_REF] introduced objectlike into cosegmentation by generating a pool of region proposals [START_REF] Carreira | Constrained parametric min-cuts for automatic object segmentation[END_REF] followed by learning similarity measure using Random Forest regressor, which evidently boost the performance on standard benchmark.

It is worth to mention that although many cosegmentation and object discovery methods claim as unsupervised, to clarify the ambiguities, we categorize them as weakly/fully supervised, in the sense that the assumption of multiple images supposed to have recurring visual categories provides a weak form of supervision. But the strong assumption that the object is present in all of the images is relaxed. Further improvements are made to handle images which might not contain the common object shown in Figure 3. [START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF] applied in images obtained from Internet search. Note that no objects are discovered for noisy images.

Semantic Segmentation

Semantic segmentation (also known as object segmentation and image parsing), has attracted wide and intensive interest in computer vision. The task of semantic segmentation involves recognition and localization, that is to assign a class label to each pixel. This has high practical value in many applications, such as image editing, object retrieval and intelligent image coding.

In recent years, numerous semantic segmentation methods have been proposed. They can be generally categorized as bottom-up and top-down. Increasing studies ( see [START_REF] Fei | Rapid natural scene categorization in the near absence of attention[END_REF]) suggest that humans can perform high level scene and object categorization tasks as fast as low level texture discrimination and other so-called pre-attentive vision tasks, i.e. humans can detect both low and high level visual patterns at early stages in visual processing. This evidence makes two paradigms to pursue to semantic segmentation.

The bottom-up methods generally consist of four steps: (1) extract low level image features (e.g., SIFT) over pixel or regions, 2) perform feature coding (e.g., K-means and sparse coding) and pooling (e.g., max-pooling) to construct midlevel feature vector descriptor (e.g., bag-of-words), and 4) train a discriminative classifier (e.g., SVM). For example, Carreira et al. 2012b proposed a method where figure-ground (regions) are generated by solving constrained parametric min-cut (CPMC) [START_REF] Carreira | Constrained parametric min-cuts for automatic object segmentation[END_REF] problems with various choices of the parameter. The semantic hypotheses are then ranked and classified by making use of support vector regression (SVR) based on their "objectness". Another typical example using this paradigm (shown in Fig. 3.10), Zou et al. [START_REF] Zou | Semantic image segmentation using region bank[END_REF] first generate multilevel regions for an input image with globalP b-UCM [START_REF] Arbelaez | Contour detection and hierarchical image segmentation[END_REF], extract color-SIFT [van de [START_REF] Van De Sande | Evaluating color descriptors for object and scene recognition[END_REF] and derivatives of Gaussians on the regions, generate bag-of-words with K-means, then train a region based classifiers with support vector machine with multiple kernel learning [START_REF] Varma | Learning the discriminative power-invariance trade-off[END_REF]. The semantic labeling is derived by considering SVM scores, region sizes and common sense. Many works in literature focus on proposing discriminative Figure 3.10: Illustration of bottom-up semantic segmentation framework in paper [START_REF] Zou | Semantic image segmentation using region bank[END_REF] feature descriptors for semantic segmentation. Shotton et al. [START_REF] Shotton | TextonBoost: Joint appearance, shape and context modeling for multi-class object recognition and segmentation[END_REF] proposed bag of semantic texton forest, which is computed over local rectangular regions for semantic segmentation. Carreira et al. [Carreira et al., 2012a] proposed second order pooling to encode the second order statistics of local descriptors inside a region. Combining this pooling technique with CPMC, leading to be the winner of segmentation competition on PASCAL VOC [Everingham et al.].

Top-down approaches generally exploit the acquired class-specific prior knowledge with low-level grouping cues. Most of these approaches use Conditional Random Fields (CRFs) over regions which in standard form have two terms: data term which considers appearance information of each region and a smoothness term which encourages similar neighboring regions to have the same labels. [START_REF] Ladicky | Associative hierarchical crfs for object class image segmentation[END_REF] proposed a multilevel hierarchical conditional random field (CRF) model to incorporate information from different scales, which is combined with top-down detectors and global occurrence information. [START_REF] Bibliography | Semantic segmentation using regions and parts[END_REF] proposed region based object detectors which combine top-down poselet detector and global appearance cues.

It is worth to mention that semantic segmentation can also be categorized as three different types, ones that estimate labels pixel by pixel ( [START_REF] Ladicky | Associative hierarchical crfs for object class image segmentation[END_REF][START_REF] Shotton | TextonBoost: Joint appearance, shape and context modeling for multi-class object recognition and segmentation[END_REF]), ones that combine features over regions( [Carreira et al., 2012b[START_REF] Zou | Semantic image segmentation using region bank[END_REF]), and ones that exploit the information of the whole image [START_REF] Josep M Gonfaus | Harmony potentials for joint classification and segmentation[END_REF]).

Image Segmentation: Dataset

Berkeley Segmentation Dataset (BSD). The public benchmark [START_REF] Arbelaez | Contour detection and hierarchical image segmentation[END_REF] has two versions. One of them called as BSD300, which includes 300 images and its corresponding ground truth data (each image has at least 4 human annotations), is divided into train set which contains 200 images and test set including 100 images. The other is the BSDS500, an extended version of the BSDS300 that includes 200 fresh test images. Each image size is 481 × 321. [START_REF] Shotton | TextonBoost: Joint appearance, shape and context modeling for multi-class object recognition and segmentation[END_REF]] was first introduced in the context of supervised class segmentation. Soon, this dataset has been widely used to evaluate scene labeling including both image segmentation and multi-class object recognition. The MSRC dataset contains two versions. The MSRC-v0 has 21-classes (3,457 images), and the MSRC-v2 has 21classes (591 images). The MSRC-v2 has been used as the standard benchmark for evaluating image segmentation [Wang et al., 2013b] as well as co-segmentation and object discovery [START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF], since it has the largest number of categories, and provides clean ground-truth labeling for all objects. Table .3.2 presents some examples from the MSRC-v2, where each color corresponds to a class.

Image Segmentation: Evaluation

Since tens of thousands of image segmentation algorithms have been proposed, it is essential to compare them using different parameters, in order to understand them on a solid experimental ground. This domain has attracted great interest, and many different evaluation metrics have been developed. Zhang et al. [Zhang et al., 2008a] presented a good survey on this topic. Typically, an evaluation metric allows to compare the results between a machine algorithm and human observer. The degree of similarity between the human and machine segmented images determines the quality of the segmented image.

From a different perspective, many evaluation algorithms have been proposed. Generally, researchers tend to evaluate the proposed algorithm with multiple different evaluation metrics to fully present its performance. For example, many methods [START_REF] Rao | Natural image segmentation with adaptive texture and boundary encoding[END_REF][START_REF] Yining | Unsupervised segmentation of color-texture regions in images and video[END_REF]] [Li et al., 2012] [Wang et al., 2013b] [ [START_REF] Wang | A graph-cut approach to image segmentation using an affinity graph based on l0-sparse representation of features[END_REF] use the PRI, VoI, GCE and BDE as standard combination to Chapter 3. Literature Review: Image Segmentation compare with other standard benchmark algorithms. According to them, a segmentation result is good, at least quantitatively, whenever the comparison with ground truth yields a high value for PRI and small values for the other three indicators. We list several popular evaluation metrics used in image segmentation.

1. The Probabilistic Rand Index (PRI) measures the fraction of pixel pairs whose labels are consistent between the segmentation result and the ground truth. In practice, PRI can be computed in a simple form. Let S ground and S test be two clusterings of the same image with different number of clusters, and let n ij be the number of points in the ith cluster of S ground and the jth cluster of S test . N is the total number of pixels of the image. The similarity between the two clusterings is:

P R(S ground , S test ) = N 2 -1/2{ i ( j n ij ) 2 (3.1) + j ( i n ij ) 2 - n 2 ij } N 2
From (3.2), the value of PRI, which measures the similarity of two clusters, ranges from 0 (when there is no intersection at all between S ground and S test ) to 1 when the two clusterings are actually the same.

2. The Volume of Information (VoI) [START_REF] Meila | Comparing clusterings: an axiomatic view[END_REF] computes the amount of information loss/gain between the compared images, and can therefore measure the extent to which one image can explain the other, with lower values representing greater similarity. Formally, it is defined as:

V I(S ground , S test ) = H(S ground ) + H(S test ) -2I(S ground , S test ) (3.2)
where H and I represent respectively the entropies of and the mutual information between the two clusterings, see [START_REF] Meila | Comparing clusterings: an axiomatic view[END_REF] for more details.

3. The Global Consistency Error (GCE) [START_REF] Martin | A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[END_REF]

BDE(B 1 , B 2 ) = N 1 i d(p i , B 2 )/N 1 + N 2 i d(p i , B 1 )/N 2 2 (3.6)
A value of BDE close to zero is a good indication that both segmentations are similar.

5. The Segmentation Covering [START_REF] Arbelaez | From contours to regions: An empirical evaluation[END_REF] has been used for the evaluation of the pixel-wise classification task in recognition. The overlap between two regions R and R is defined as:

O(R, R ) = |R ∩ R | |R ∪ R | (3.7)
It measures the region-wise covering of the ground truths by a machine segmentation.

6. The Precision and Recall criteria [START_REF] Arbelaez | From contours to regions: An empirical evaluation[END_REF] and their weighted harmonic mean F-measure evaluate the accuracy of the segmentation algorithms by computing the percentage of matched boundary pixels between the segmented result and the ground-truth image.

Introduction

Image segmentation aims to partition an image into meaningful regions and is a fundamental step for many computer vision tasks, e.g., object recognition [START_REF] Lee | Object-graphs for context-aware category discovery[END_REF], scene interpretation [START_REF] Kumar | Efficiently selecting regions for scene understanding[END_REF], or content-based image retrieval [START_REF] Belongie | Color-and texture-based image segmentation using em and its application to content-based image retrieval[END_REF]. It proves to be extremely challenging due to the huge diversity and ambiguity of visual grouping patterns in natural scene images, in particular in presence of faint object boundaries and cluttered background (see Fig. 4.1(a)). When no restrictive prior is imposed, segmenting an image is an inherently ill-posed task which requires incorporating prior knowledge into the algorithm and keeps attracting many researcher's attention. . In this work, we are interested in graph-oriented methods which turn the problem of segmenting an image into a problem of partitioning a graph. They prove to be very versatile while providing the ability to encode perceptual grouping laws which play a major role in human visual perception [Felzenszwalb and Huttenlocher, 2004, Chapter 4. A Global/Local Affinity Graph for Image Segmentation Shi andMalik, 2000, Wertheimer, 1938]. However, it is also well known that the quality of the final segmentation result strongly depends on the way the initial graph is built from the input image. Building a graph requires defining its nodes and the relationships between them, i.e., the edges and their weights. However, for graphbased image segmentation, constructing a reliable graph with such requirements faces the following challenges:

1. Numerous feature descriptors have been proposed to differentiate data points.

It is actually uneasy to choose the most appropriate descriptor since the relative performances of the various features vary depending on the type of data and are not well known in general;

2. Both local geometrical adjacency and global grouping cues are critical to obtain reliable segmentation results, while their adaptive combination still has to be understood in graph-construction algorithms.

Motivation and contribution

In this work, we propose to construct a sparse and discriminative graph over superpixels to implement not only some obvious perceptual grouping laws, e.g., proximity, similarity, but also enable some others, less straightforward, e.g., continuity, to enter into action for the purpose of perceptual image segmentation. Based on empirical observations, we first postulate a gravitation law over superpixels for their perceptual grouping. Specifically, as can be seen in Fig. 4.1 (b)-(f), in dividing broadly superpixels into small, medium and large sized sets, colored in yellow, green and blue in Fig. 4.1, respectively, the postulated gravitation law states that: 1. Small sized superpixels are tiny regions which tend to be perceptually attracted by nearby medium or large sized superpixels while large sized superpixels are wide regions, e.g., ground regions in blue in Fig. 4.1(b), which could span as large as more than half of an image. They are structuring visual patterns that already convey long range information and tend to strongly attract their direct medium and small sized superpixels in perceptual grouping;

(a) (b) (c) (d) (e) (f) (g) (h)
2. Medium sized superpixels express long range visual grouping patterns, e.g., skin spots of the leopard in green in Fig. 4.1.(b), which need to be captured to further enable propagation of local grouping cues across long range connections;

As a result, we propose to construct an adjacent-graph over small and large sized superpixels to encode the proximity, and adopt our previously proposed sparse 0 graph over medium sized ones to capture continuity and promote sparsity. As the proposed graph can capture both local and global relationships among data points, we call it a Global/Local Graph, or GL-graph in short. Furthermore, to enable propagation of grouping cues among superpixels of different scales, we also introduce a bipartite graph which expresses relationships between pixels and superpixels.

Another important perceptual grouping law is similarity of data points within an object which can be characterized by three major perceptual visual features, namely color, texture and shape. According to a few works in psychophysics of human vision [Toni P.Saarela, 2012][M. Peterson and B.Gibson., 1993], these features jointly contribute to perceptual grouping but with different emphases. However, human vision of a scene is perceptual, making use of perceptual laws [START_REF] Wertheimer | Laws of organization in perceptual forms (partial translation)[END_REF], e.g., similarity, proximity, continuity, etc. Given the unsupervised context while dealing with a huge diversity of natural scene images, e.g., indoor and outdoor scenes, landscapes, cityscapes, plants, animals, people, objects, etc., the challenge here is thus to construct a reliable graph fulfilling the aforementioned requirements while encoding some prior knowledge, e.g., perceptual laws. In this work, we implement this paradigm and evaluate the aforementioned three visual features in our GL graphs, through mlab and color histogram, Color LBP and SIFT-based codebooks for color, texture and shape, respectively, both individually and their weighted combinations for their effectiveness in unsupervised image segmentation.

The contributions of the proposed approach are threefold:

1. A sparse global/local graph over superpixels of different scales is proposed to capture both short and long range grouping cues of an image, thereby enabling perceptual grouping laws, e.g., proximity, similarity, continuity, to enter into action through a suitable graph cut algorithm. This is achieved in over-segmenting the input image into superpixels at different scales, postulating and implementing a gravitation law which makes use of small and large sized superpixels to encode local smoothness, e.g., proximity, while medium sized superpixels to capture sparse long range grouping cues, e.g., continuity, through 0 sparsity. A bipartite graph is also introduced to further enable propagation of grouping cues across superpixels of different scales.

2. Using GL-graph, we also evaluate three major visual grouping features, namely color, texture and shape, for their discriminating power in perceptual image segmentation, as well as simple weighted fusion schemes which implement findings from psychophysics which suggest combining color, texture and shape cues with different emphases for perceptual grouping. These evaluations are not only conducted on the proposed GL-graph but also on a number of state of the art graph construction methods to shed light on how constructing discriminative graphs with suitable features and their combinations.

3.

Extensive experiments are carried out on the Berkeley Segmentation Database (BSD) using 4 different criteria, namely PRI, VoI, GCE and BDE. The experimental results show the effectiveness of the proposed approach, which generate perceptually meaningful partitions and display very competitive objective results in comparison with a number of state of the art algorithms.

Paper Organization. The rest of this paper is organized as follows: in Section II we discuss the basic principles underlying standard graph construction methods in the literature. Section III presents the proposed GL-graph in detail and introduces the graph cut method for general image segmentation tasks. In Section IV we carry out extensive experiments on different graphs with different features, and compare the proposed graph with existing graphs as well as other state-of-the-art segmentation methods both visually and quantitatively. Finally, the conclusion is drawn in Section V.

Proposed Global Local Affinity Graph based on Superpixel and Sparse Representation

In this chapter, we propose a new efficient affinity graph and an unsupervised image segmentation method. An overview of the scheme is shown in Fig. 4.2. We start by affinity graph is the combination of these graphs. We repeat this graph construction scheme several times for different scales of over-segmentations and concatenate the resulting multi-feature affinity graph into a new multi-feature multi-level affinity graph. Finally, unlike usual unsupervised approaches like normalized cut (Ncut) [START_REF] Shi | Normalized cuts and image segmentation[END_REF], the image segmentation problem is solved by computing the partition of the bipartite graph obtained with the unified affinity graph and the association between pixels and superpixels.

Multi-scale Superpixels Generation and Representation

As pointed in [START_REF] Li | Segmentation using superpixels: A bipartite graph partitioning approach[END_REF], superpixels generated by different methods with varying parameters can capture various and multiscale visual patterns of a natural scene image. By superpixel, we mean here a connected maximal region in a segmented image. As shown in Fig. 4.3, an input image is oversegmented into superpixels of different scales, e.g., 5 scales in the figure, using one or several state of the art segmentation methods, e.g. the Mean Shift algorithm (MS) [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF] and the Felzenszwalb-Huttenlocher (FH) graph-based method [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF]] in this work. Fig. 4.3 shows 5 oversegmentations at 5 different scales using the same parameters as the method referred to as Segmentation by Aggregating Superpixels (SAS) [START_REF] Li | Segmentation using superpixels: A bipartite graph partitioning approach[END_REF]

Global/local Affinity Graph Construction

We postulate the gravitation law from empirical observations on superpixels and broadly divide them into small, medium and large sized sets for their perceptual grouping. Adjacency-graph is used for both small and large sized superpixels with respect to their spatial neighbors to capture local smoothness while 0 -graph is applied to medium sized pixels. The final result is a sparse Global/Local graph, namely GL-graph, as illustrated in Fig. (4.5), which implement proximity, long-range continuity and similarity in the same framework.

Specifically, given an input image I, and a collection of superpixels S l = {s 1 , s 2 , ..., s N } at a given scale l, a GL-graph is built in a given feature space, e.g., mLab, using the superpixels as graph nodes. Superpixels are divided adaptively into three disjoints sets: small, medium and large sized ones. The small sized superpixels can be directly defined using the minimum area parameter involved in the oversegmentation algorithms used for the computation of the superpixels. To decide the large sized superpixels, we first sort all the superpixels areas in an ascending order, then we compute the cumulative sum C(s l ) of the reordered areas. Fig. 4.4 illustrates the graph of this cumulative sum for superpixels of 5 different scales. Calculating the second derivative of each curve, we identify its maximal value, and the corresponding area is chosen as threshold value (see the corresponding blue mark on the cumulative graphs in Fig. 4.4). This simple procedure seems rather robust in our experiments. Indeed, they depict almost the same performance when the threshold for deciding the large sized superpixels varies in a range close to the inflection identified by the aforementioned procedure through second derivative.

Building a 0 -graph for medium-sized superpixels. Our previously proposed 0 -graph in [START_REF] Wang | A graph-cut approach to image segmentation using an affinity graph based on l0-sparse representation of features[END_REF]] is applied to medium-sized superpixels in order to capture long range grouping cues. More precisely, in context of image segmentation problem, the basic principle is to approximate every data point, i.e., superpixel in a given feature space, as a linear combination of other superpixels of the same image, which are considered as neighbors, and their pairwise similarities or affinities are computed from the corresponding representation error. Formally, such an approximation can be written as:

y i = Yc i , c ii = 0 (4.1)
where c i ∈ R n is the sparse representation of the data point y i ∈ R m over the dictionary Y which is a matrix representation of data points. The constraint c ii = 0 prevents the self-representation of y i .using Eq.( 4.1) to approximate every mediumsized superpixel from other medium-sized ones in a given feature space, e.g., mLab.

However, Eq.(4.1) is generally underdetermined and can have an infinite number of solutions whereas we seek to build a sparse image graph in line with the requirements. It turns out that the sparsest solution of Eq.(4.1) measured in the sense of problem:

min ||c i || 0 s.t. y i = Yc i , c ii = 0 (4.2)
where • 0 denotes the 0 norm, which counts the number of nonzero values in a vector. c ii denotes the ith elements in the coefficient vector c i . However, the problem of finding the sparsest solution of linear equations is NPhard. Nevertheless, there are many sparse approximation methods, the most two common ones being the 1 -norm approximation and the orthogonal matching pursuit (OMP).

The 1 -norm can be used to approximate the 0 -norm:

min ||c i || 1 s.t. y i = Yc i , c ii = 0 (4.3)
under the condition if the solution sought is sparse enough [START_REF] Bibliography | Algorithms for sparse approximation[END_REF][START_REF] Wright | Robust face recognition via sparse representation[END_REF]. However, within our context of image segmentation using superpixels, such a condition is not necessarily satisfied, given the fact that the number of superpixels given by an oversegmentation is quite limited, e.g., a few hundreds, and even less for medium sized superpixels. Furthermore, because of the huge diversity of natural scene images, the dictionary,i.e.,the data point representation matrix Y = [y i , ..., y N ] ∈ R d×N in Eq.( 4.1), could be very unbalanced, for instance with far much more sky superpixels than others, thus missing to be overcomplete for some visual patterns. As a result, we keep to solve Eq.( 4.2) using the 0 -norm but make use of orthogonal matching pursuit (OMP) to seek an approximation of the sparsest solution. Experimental results discussed later on in section 4.3 are in line with our analysis and provide further support in favor of our choice of the 0 -sparsity. OMP is a simple and fast greedy method for approximately solving the 0 -norm sparse formulation through the following optimization problem:

ci = argmin c i y i -Yc i 2 2 , c i 0 ≤ L, c ii = 0 (4.4)
where the parameter L controls the sparsity of the representation. The OMP takes linear time O(N L) with the N representing total number of entries in the dictionary Y, and the L be the maximal number of coefficients for each input data atom y i . Once achieved a sparse representation for each data point whose nonzero elements are expected to indicate superpixels from a same object, these superpixels will be considered as graph neighbors of the given data point. The next step of the algorithm is to define the similarity matrix W using the sparse reconstruction error:

r ij = y i -c ij y j 2 2 .
(4.5) c ij denotes the jth elements in the coefficient vector c i .

The similarity coefficient w ij between superpixels s i , s j is defined as

w ij = 1 if i = j 1 -(r ij + r ji )/2 if i = j. (4.6)
Building an adjacency-graph for small and large sized superpixels with respect to their neighbors. As for the superpixels in the small-and largesized sets, every superpixel is connected to all its adjacent superpixels, denoted as adjacency-graph. Traditionally, the pairwise similarities are computed with the Gaussian kernel function which is influenced greatly by the choice of the standard deviation σ [Li et al., 2012, Shi and[START_REF] Shi | Normalized cuts and image segmentation[END_REF]]. In our combining scheme, it is hard to decide adaptively the value of σ in order to maintain the same order of magnitude with 0 -graph. Therefore, we adopt the same principle as for 0 -graph to compute the similarities: given a superpixel s i associated with its corresponding feature vector x i and the matrix-representation D of all its adjacent neighbors, we try to represent x i as a linear combination of elements in D. In practice, we solve the following optimization problem:

ci = argmin c i ||x i -Dc i || 2 (4.7)
Once a minimizer ci has been computed, the similarities between a superpixel and its graph neighbors are computed as in Eq. ( 4.5) and (4.6).

Fusing GL-graphs of different visual features and different scales

In summary, for each scale of oversegmented superpixels S l = {s 1 , ..., s N }, and its associated feature matrix [x 1 , ..., x N ], we construct a GL-graph G l . In this work, as explained in subsection 4.2.1, we aim to evaluate the effectiveness of three major perceptual visual features, namely color, texture and shape, for their discriminating power, and therefore generate for each of them f k a similarity matrix W f k . Furthermore, following [M. Peterson andB.Gibson., 1993, Toni P.Saarela, 2012] which suggest combining color, texture and shape cues with different emphases. Given with m different types of features, we implement a simple weighted sum as in Eq.(4.8) to Figure 4.5: Illustration of the GL-graph's structure: for each over-segmentations, all the superpixels are divided into three sets: small (the green dots), medium (the blue dots) and large (the ink blue dots) according to their area. Over small and large sets, all data points will connect to their adjacent neighbors, while over medium set, each data point will search its neighbors all over the set. Note that bold red lines represent undirected edges connecting data points within sets, while the dashed red lines describe the edges connecting data points between two different sets.

fuse these similarities into a single affinity matrix.

w ij = m k=1 (β f k w f k ij ) (4.8)
where β f k is a weight assigned to feature f k , which controls this feature's importance, and w f k ij denotes the similarity of superpixels s i and s j with feature f k . For comparison, a baseline fusion scheme as defined in Eq.(4.9) is also used.

w ij = m k=1 (w f k ij ) 2 (4.9)
To fuse all scales of superpixels, we plug each scale affinity matrix W l corresponding to its GL-graph G l into a block diagonal multiscale affinity matrix W ss like [START_REF] Cour | Spectral segmentation with multiscale graph decomposition[END_REF] as follows:

W ss =    W 1 0 . . . 0 W l    (4.10)
Note that this multiscale affinity matrix of superpixels gathers all the informative intra-scale similarities for grouping. Furthermore, in packing them diagonally, we are ready also to enable propagation of long-range grouping cues across scales, which is achieved by constructing and diagonalizing a pixel-superpixel graph, or bipartite graph, as introduced in the next subsection.

Bipartite Graph Construction and Partition

To map the relationships between pixels and superpixels and enable propagation of grouping cues across superpixels of different scales, we build a bipartite graph which consists of two parts describing the pixel-superpixel and superpixel-superpixel relationships, respectively. Fig. 4.6 illustrates the structure of such a bipartite graph which encodes the information between pixels and superpixels in blue lines, and the information between superpixels in yellow ones. In particular, taking into account the demand of sparsity for a good-quality graph, pixels are only connected to the superpixels to which they belong. More precisely, let G B = {U, V, B} denote the bipartite graph, where U = I ∪ S, V = S, I is the set of pixels and S the set of

superpixels. B = W IS W SS , with W IS = (b ij ) |I|×|V |
, and b ij = γ, if pixel i belongs to superpixel j (in our experiments, we set γ = 10 -3 ), b ij = 0 otherwise. W SS is the affinity graph between superpixels computed in section 3.2. Note that the resultant bipartite graph is highly sparse 1 because of its unbalanced nature. Furthermore, superpixels sharing a large number of pixels are likely to be grouped together, thanks to connections between pixels and their superpixels containing them, thus enabling propagation of grouping cues across scales.

Given an undirected graph G = (V, E) with a similarity matrix W and a number of segments k, various techniques can be applied to group the data points into k different clusters, as cuts [START_REF] Shi | Normalized cuts and image segmentation[END_REF], maximum-flow techniques [START_REF] Goldberg | A new approach to the maximum flow problem[END_REF] and spectral clustering algorithms [START_REF] Chung | Spectral Graph Theory[END_REF][START_REF] Ulrike | A tutorial on spectral clustering[END_REF]. Among these methods, spectral clustering algorithms have been proven successful in many applications, and in particular image segmentation [START_REF] Shi | Normalized cuts and image segmentation[END_REF]. They have been in recent years a major trend to achieve clusters from a sparse graph, mainly using representations as linear combinations of eigenvectors of the Laplacian matrix. Basically, spectral clustering consists of partitioning the graph using eigenspaces associated with the following generalized eigen problem [START_REF] Shi | Normalized cuts and image segmentation[END_REF]: (4.11) where L = D -W denotes the graph Laplacian, and D = diag(W 1) with 1 a vector with all components equal to 1. The Lanczos method [START_REF] Golub | Matrix computations[END_REF] and the partial SVD [START_REF] Zha | Bipartite graph partitioning and data clustering[END_REF] can be applied to solve the above 1 In the bipartite graph, a pixel is connected to only l superpixels for l over-segmentations of an image, we used l = 5 or 6 for our experiments . For instance, an image named 2092, it is oversegmented into 5 scales with 123, 121, 105, 209 and 53 superpixels, respectively, thus resulting in 611 superpixels in total. The pixel-superpixel graph's size is 154401 × 611. The total number of nonzero elements in this graph is 154401 × 5. The percentage of nonzero elements can be viewed as a measurement of sparsity, i.e., eigen problem.

Lf = λDf ,
However finding eigenvalues of large matrices is in general computationally demanding, for example, given the bipartite graph G B , it takes O(k(|U| + |V|) 3/2 ) [START_REF] Li | Segmentation using superpixels: A bipartite graph partitioning approach[END_REF] for the Lanczos method and the partial SVD. Note that the bipartite graph in our case is unbalanced, i.e. |U| = |V|+|I| , and |I| >> |V| in general, which gives |U| >> |V|. We use the Transfer Cuts method [START_REF] Li | Segmentation using superpixels: A bipartite graph partitioning approach[END_REF] which has been proposed to solve efficiently the unbalanced bipartite graph partitioning problem. Interestingly, Transfer Cuts solve a problem which has similar form as (4.11), but holds on a much smaller graph over superpixels only

L V f = λD V f , (4.12)
where

L V = D V -W V , D V = diag(B 1), and W V = B D -1 U B, D U = diag(B1
). Note that solving (14) takes linear time O(k|V| 2/3 ) with a small constant.

Experiment and Analysis

image's size is 481 × 321. Four standard measurements are used for quantitative evaluation: the Probabilistic Rand Index (PRI) [START_REF] Unnikrishnan | Toward objective evaluation of image segmentation algorithms[END_REF], the Variation of Information (VoI) [START_REF] Meila | Comparing clusterings: an axiomatic view[END_REF], the Global Consistency Error (GCE) [START_REF] Martin | A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[END_REF], and the Boundary Displacement Error (BDE) [START_REF] Freixenet | Yet another survey on image segmentation: Region and boundary information integration[END_REF].

Experiments Setup

Using the framework depicted in Fig. 4.2, the proposed GL-graph is first evaluated through a single visual feature in comparison with several state of the art graphs. It is then further evaluated when fusing visual features as proposed by psychophysicists and several global graphs to capture different grouping cues. This means that only the GL-graph construction is evaluated and compared while keeping the same all the other steps, e.g., over-segmentation, feature extraction, bipartite graph construction and graph partition using spectral clustering. Please refer to section 4.2 for further details.

The state of the art graphs studied are the adjacent-graph as in SAS2 [START_REF] Li | Segmentation using superpixels: A bipartite graph partitioning approach[END_REF] and four popular global graphs, namely KN N -graph 3 [Grady, 2004], 1graph4 [START_REF] Elhamifar | Sparse subspace clustering: Algorithm, theory, and applications[END_REF], LRR-graph (Low Rank Representation)5 [START_REF] Liu | Robust recovery of subspace structures by low-rank representation[END_REF], and 0 -graph [START_REF] Wang | A graph-cut approach to image segmentation using an affinity graph based on l0-sparse representation of features[END_REF].

For each method, we tuned the parameters to achieve the best performance:

1. adjacent-graph: the standard deviation of the Gaussian kernel function is defined as σ = 20;

2. KN N -graph: we adopt Euclidean distance as the similarity metric, and use Gaussian kernel function to compute the weights of edges, with σ = 20 as [START_REF] Li | Segmentation using superpixels: A bipartite graph partitioning approach[END_REF]. Various numbers of neighbors are tested;

3. 1 -graph: we construct the graph following the method in [START_REF] Elhamifar | Sparse subspace clustering: Algorithm, theory, and applications[END_REF]. Since the affinity matrix is asymmetric, we replace it with W = (|W | + |W | T )/2;

4. 0 -graph: we derive the graph and symmetrize it following [START_REF] Wang | A graph-cut approach to image segmentation using an affinity graph based on l0-sparse representation of features[END_REF]. Parameters are also the same;

5. LRR-graph: we construct the LRR-graph and symmetrize it as for the 1graph following [START_REF] Liu | Robust recovery of subspace structures by low-rank representation[END_REF]. We set the balance parameter λ = 0.18;

6. GL-graph: For our GL-graph, the threshold value for defining small regions is empirically set to 300 pixels and the threshold for large regions is decided adaptively following the discussion in Section 3.2. Performances with various L are presented.

As explained in subsection 4.2.1, following the findings of psychophysicists, we evaluate three major perceptual visual features, namely color using the mean value of a superpixel in L*a*b denoted as mLab ∈ R 3 or RGB color histogram denoted as CH ∈ R 256 , texture through Uniform Color Local Binary Pattern6 [START_REF] Zhu | Multi-scale color local binary patterns for visual object classes recognition[END_REF] denoted as CLBP u2 ∈ R 177 , and shape cues using the Bag-of-Visual-Words (BoW ).

In the experiments, we compute the scale invariant feature transform (SIFT)7 [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF] at each pixel and then perform the vector quantization by fast K-means8 to construct the visual vocabulary. The number of clustering centers is 100, 150, 200 and 300, denoted as BoW 100, BoW 150, BoW 200, BoW 300, respectively.

Experimental results using single visual feature

Graph's performances are closely related to neighborhood's topology and to features' choice. This experiment aims to compare the quality of the proposed GL-graph with 5 other state of art graph constructions and highlights the discriminating power of each visual feature. Table 4.1 tabulates the performance of the 6 tested graph construction methods over each visual feature. First we present the average score on each number of segments over the BSD test set I and II (Fig. 4.7 and 4.8). In detail, for each feature, we use the four evaluation metrics (PRI, VoI, GCE, and BDE) to compare different graphs: adjacent-graph, KN N -graph, 1 -graph, LRRgraph, 0 -graph, and GL-graph. Together with the feature performance, we can make the following observations:

1. The adjacent graph is more sensitive than global graphs to the number of segments k and to feature selection. In particular, its performance varies greatly with the feature mLab. However, the additional use of BoW makes it less sensitive to k. In addition, on average, mLab performs better as k increases. 1. color is a faithful cue for almost all graphs except the LRR-graph and GLgraph on which LBP has equivalent performance with color. More specially, choosing appropriate color space can boost the performance, such as mLab for KN N -graph and 1 -graph;

2. CH and LBP perform almost the same for all kinds of graph;

3. BoW 's performance does not vary greatly with respect to the number of centers. Note that LRR-graph's performance is invariant to the feature selection according to Table 4.1.

Remark that these findings are in perfect accordance with those of psychophysicists on human vision-based segmentation which suggest that appearance grouping cues, i.e., color and texture, outweight shape-based ones [M. Peterson and B.Gibson., 1993] while human vision makes joint use of color and texture for image segmentation but with asymmetric role in favor of color [START_REF] Michael | Combination of texture and color cues in visual segmentation[END_REF]. These findings will be fully explored in the fusion scheme as explained in subsections 4.3.3. Obtaining visually meaningful results requires inevitably the careful tuning of the number of segments k. We show in Fig. 4.9 the different performances of the graphs for various values of k and the following observations can be made: 1) the 4.9), due to its high sensitivity to noise and outliers, which is a convenient skill for face recognition [START_REF] Wright | Robust face recognition via sparse representation[END_REF], but not for image segmentation; 3) unlike the graph based on sparse minimization, which finds the sparse representation of every point, the LRR-graph finds a global lowest rank representation, therefore further enforces the global structure over the data points. However, as pointed in [START_REF] Zhuang | Non-negative low rank and sparse graph for semi-supervised learning[END_REF], LRR-graph often produces a dense graph which fails to meet the demand of sparsity for a desirable graph.

Results on fusing different graphs and visual features

The experimental results shown in subsection 4.3.2 in perfect accordance with the findings of psychophysicists on human vision-based segmentation [M. Peterson and B.Gibson., 1993] strengthen the simple weighted sum fusion scheme as defined in Eq.(4.8) in subsection 4.2.3 [Toni P.Saarela, 2012] which enables combining color, texture and shape cues with different emphases. Specifically, following both the findings of psychophysics and the experimental results shown in subsection 4.3.2, we empirically implement several fusion schemes, namely fusion schemes combining color and texture features as well as those combining color, texture and shape at the same time. When color and texture cues are jointly used, more weight is given to color-based affinities than those of texture-based one; When all the three visual features are used at the same time, shape receives less weight in comparison with color and texture. As a baseline, we also implement the baseline fusion scheme as defined in Eq.(4.9) which gives an equal weight to each kind of visual grouping cues.

As can be seen from the Table 4.3, very competitive results are achieved by the proposed GL-graph when fusing color, texture and shape with different emphases. We showed in the previous section that that different graphs capture different affinities between superpixels. Given a visual feature, e.g., color mLab, fusion can also be carried out at the graph level in combining the proposed GL-graph with other ones, e.g., 1 , KN N , LRR, and in averaging their affinities. Specifically, the segmentation framework as defined in section 4.2 is kept the same, the fusion only takes place at the graph level of medium sized superpixels. Table 4.4 reports the experimental results of such graph level fusion schemes. As can be seen from Table 4.4, when the input image is simply segmented into two clusters (k = 2), the baseline, i.e., the proposed GL-graph, outperforms all three combinations. However, when the number of clusters is increased, i.e., k = 10, 30, 40, all three combinations outperform the baseline GL-graph. These results suggest that, when the number of clusters is increased, new connections are brought in by other global graphs, i.e., 1 , KN N , LRR, definitively contribute to improve the segmentation result. Furthermore, both KN N and LRR graphs prove to bring more complementary information with respect to the GL-graph than the 1 graph.

Comparison with state-of-the-art algorithms

Our work follows a similar, yet not identical, strategy as the SAS algorithm [START_REF] Li | Segmentation using superpixels: A bipartite graph partitioning approach[END_REF], i.e., building a bipartite graph over multiple superpixels and pixels, then using Tcuts for image segmentation. The main difference between both methods is the affinity graph construction. In SAS, adjacent neighborhoods of superpixels are used, and the pairwise superpixel similarity is computed by the Gaussian weighted Euclidean distance in the color feature space. In our method, we build a GL-graph combining classical spatial homogeneity of objects and long range clustering based on sparse representation over multiple types of features and multi-scale superpixels, making the constructed graph having the characteristics of a long range neighborhood topology, yet with sparsity and high discriminative power. Fig. 4.10 shows various segmentation results obtained with either the SAS method (second image of each experiment), or with our algorithm (third image). Notice that the results of SAS are the best results reported by the authors, and require a careful tuning of the number of segments k (e.g. for starfish, owl and leopard, k = 11, 4, 5 respectively).

For our method that takes into account the global information, a desirable result can be usually achieved with either k=2, 3, or 4 (e.g. for starfish, owl and leopard, k = 2). Especially, compared with SAS, our method achieves a correct segmentation even in the difficult cases where: 1) The detected object is highly textured (this is for instance the case of starfish, moray eel, leopard, and owl), and the background may be highly unstructured. In the particularly difficult case of the owl image, [START_REF] Shi | Normalized cuts and image segmentation[END_REF] 0.7242 2.9061 0.2232 17.15 JSEG [START_REF] Yining | Unsupervised segmentation of color-texture regions in images and video[END_REF] 0.7756 2.3217 0.1989 14.40 MNCut [START_REF] Cour | Spectral segmentation with multiscale graph decomposition[END_REF] 0.7559 2.4701 0.1925 15.10 NTP [Wang et al., 2008a] 0.7521 2.4954 0.2373 16.30 TBES [START_REF] Rao | Natural image segmentation with adaptive texture and boundary encoding[END_REF] 0.8000 1.7600 N/A N/A UCM [START_REF] Arbelaez | Contour detection and hierarchical image segmentation[END_REF] 0.8100 1.6800 N/A N/A SDTV [START_REF] Donoser | Saliency driven total variation segmentation[END_REF] 0.7758 1.8165 0.1768 16.24 LFPA [Kim et al., 2010a] 0.8146 1.8545 0.1809 12.21 Context-sensitive (mlab) [START_REF] Bai | Learning context-sensitive shape similarity by graph transduction[END_REF] [Kim et al., 2010a] and [START_REF] Yang | Affinity learning with diffusion on tensor product graph[END_REF], with exception of [START_REF] Bai | Learning context-sensitive shape similarity by graph transduction[END_REF], 2012[START_REF] Zhou | Fusion with diffusion for robust visual tracking[END_REF], the graphs proposed in which are for task of shape retrieval and visual tracking. Nevertheless, we compare with their graph construction methods, by only replacing the GL-graph in our segmentation framework, while keeping other settings such as multi-scale superpixels and bipartite graph structure the same, for the sake of fairness. From Table 4.5, we can observe that only with one feature mlab, the context-sensitive graph [START_REF] Bai | Learning context-sensitive shape similarity by graph transduction[END_REF] has very promising performance. It is worth to mention that the graph construction techniques proposed in [START_REF] Bai | Learning context-sensitive shape similarity by graph transduction[END_REF], 2012, Yang et al., 2013[START_REF] Zhou | Fusion with diffusion for robust visual tracking[END_REF], are with very high computational cost and even hardly acceptable for the bottom-up segmentation, which is usually pre-process for high-level computer vision task, e.g. object recognition and detection. We can see that our method ranks first for PRI, VoI, GCE, and BDE, in particular the gain is significant for PRI and BDE.

Additionally, to demonstrate the advantage of our algorithm in practical applications, we present visual segmentation results of our method with k =2. As can be seen in Fig. 4.11, our method tends to first segment the most salient objects in the image even in the following cases where: 1) the detected object is tiny (see the aeroplane, the boat); 2) multiple objects are needed to segment in the same image (as in both middle rows); 3) the color of background and object are quite similar (see the last row).

Algorithm time complexity

Conclusion

In this chapter, we introduced a sparse global/local graph which encodes in a sparse way the perceptual grouping laws, e.g., proximity, similarity, and continuity. Unlike classical methods, our GL-graph is able to encode adaptively both local and global homogeneity of an object via fusing two types of graphs: the adjacent-graph and the sparse 0 -minimization based graph built separately on three different classes of superpixels, i.e. enforcing proximity and similarity over small and large sized superpixels and encoding long range similarity on medium sized ones. Moreover, the discriminative power of the GL-graph is further enhanced by fusing several different features over multi-scale superpixels. The derived GL-graph is plugged into an efficient graph-cut method for unsupervised image segmentation. Extensive validations on the BSD data set show that our method yields very competitive qualitative and quantitative segmentation results compared to state-of-the-art methods.

As future extension of our work, it could be interesting to be able to learn an optimal fusion scheme that combines color, texture and shape cues using training data. That would be an interesting step toward semi-supervised image segmentation. 4.11: Visual segmentation examples by the proposed method: all images are segmented into 2 regions (k=2). Note that the salient objects or parts can be segmented accurately, such as the plane, boat, flower with insects, elephants, hill. Even multiple objects with large inner color variation can be segmented correctly, as the cactus flowers or the men in water.

Chapter 5

Graph-based Image Segmentation

Using Weighted Color Patch

Introduction

In recent years, the graph-based methods have been proven successful and widely applied to image segmentation, mainly because they have an efficient tool to solve the optimization problem of segmentation [P. [START_REF] Peng | A survey of graph theoretical approaches to image segmentation[END_REF] and can naturally incorporate different type of features in the affinity graph. In particular, the graph-based methods first construct an affinity graph from a given image, and then partition the resulting graph into different clusters with certain cut criteria [START_REF] Hagen | New spectral methods for ratio cut partitioning and clustering[END_REF]Kahng, 1992] [Shi and[START_REF] Shi | Normalized cuts and image segmentation[END_REF]. Thus, constructing a discriminative affinity graph plays an essential role in such methods. For a desirable partition result, the pixels should be similar to each other in intra-clusters while different from each other in interclusters. The similarity between two pixels can be measured by the distance of different features such as color, boundary, texture, etc. Feature is an important factor since its properties directly influence the discriminative power of the resulting affinity graph.

Chapter 5. Graph-based Image Segmentation Using Weighted Color Patch

Motivation and our proposed method

In this chapter, we propose a new feature descriptor based on the weighted color patch to construct a more discriminative affinity graph. The idea of representing a pixel with a patch has been proven successful in non-local image denoising [START_REF] Buades | A non-local algorithm for image denoising[END_REF]. However, it produces the over-smooth effect due to considering each member equally in the patch. Therefore, it is necessary to assign different weight to each pixel in the patch. J. Zexuan et al. [START_REF] Ji | Fuzzy c-means clustering with weighted image patch for image segmentation[END_REF] investigated this idea in their work on fuzzy c-means clustering, but they only considered gray intensities to compute the similarity of two pixels. For image segmentation, it is insufficient to use only gray intensities, while color is also a very discriminative and efficient feature for identifying different objects, especially in natural images. Therefore, our proposed method intends to incorporate both color and neighborhood information. There are two main advantages: i) it can smooth local regions by averaging color information and ii) it can capture texture information by considering context neighboring cue. Furthermore, in order to incorporate spatial information, we also propose to assign a global weight to each pixel in an image according to different proportion of the object and background, so that the contrast between them is enhanced and a more discriminative affinity graph is constructed. The rest of the chapter is organized as follows: we introduce the proposed weighted color patch (WCP) method elaborately in section 2, where local and global weights are presented in section 2.1 and 2.2 respectively, and we introduce the affinity graph construction based on WCP in section 2.3; in section 3, we present extensive experiments on the Prague texture image benchmark [START_REF] Haindl | Texture segmentation benchmark[END_REF] and the Berkeley image segmentation database [START_REF] Arbelaez | Contour detection and hierarchical image segmentation[END_REF], and report the quantitative results with associated multiple evaluation metrics; the conclusions are drawn in section 4.

Related work

In the literature, numerous works have been proposed to design powerful features for image segmentation. Color has been proven powerful in many works for image segmentation. Early works [Shi andMalik, 2000][Felzenszwalb and[START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF] on graph cut based technique only consider the color information with one pixel. Recent results in [START_REF] Fowlkes | Learning affinity functions for image segmentation: Combining patch-based and gradient-based approaches[END_REF] suggest that the color cue is best captured using patches to task of image segmentation, for it is well known that color patches are a stable cue. Furthermore, using sliding window (patch) for object detection has proven a huge success, e.g., Deformable Part-based Models (DPM) [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] and its variants [Girshick et al., 2011] [Azizpour and[START_REF] Azizpour | Object detection using strongly-supervised deformable part models[END_REF]. Developing new feature descriptor based on patch attracts intensive interest of researchers. One evident advantage of patch is that a set of intensity, texture and shape features can be extracted and computed for each patch. For instance, Malik et al. [START_REF] Malik | Contour and texture analysis for image segmentation[END_REF] constructed textons based on clustering of filter response over patches. [START_REF] Brunner12 | Patch-cuts: A graph-based image segmentation method using patch features and spatial relations[END_REF], they extract intensity, texture and shape descriptors from patches and combine them linearly in the graph-cut formulation. Another advantage is that using patch makes derived descriptor robust against noise. More importantly, the use of a patch can also incorporate the context Patch information, which has been treated as a key factor. [START_REF] Torralba | How many pixels make an image[END_REF] pointed out that human performance in scene categorization remains high no matter whether low or multi-mega pixel images are used. Moreover, they demonstrated that very smallsize patch 32 × 32 color pixels provides sufficient information to recognize the object category. Later, in [START_REF] Yong | Object-graphs for context-aware visual category discovery[END_REF], the authors proposed that context information of known object is a helpful hint for discovering unknown objects in an image. In [START_REF] Bai | Learning context-sensitive shape similarity by graph transduction[END_REF], the computation of graph similarities for shape retrieval is context-sensitive by considering neighbors' influence.

Proposed method

Local weights computation

As introduced in the introduction, using patches directly will cause the over-smooth effect mainly due to considering each member in the patch equally. Therefore, it is necessary to assign different weights to different pixels. In this paper, we adopt the method described in [START_REF] Ji | Fuzzy c-means clustering with weighted image patch for image segmentation[END_REF] to compute the local weights adaptively.

Let an image represented by I = {g 1 , ..., g x } with g x as pixel intensity, and a patch vector denoted as P k = (g k , N k ), where N k is the neighborhood around the central pixel g k with the size w × w. For each pixel g r in the patch, its mean-square deviation σ r is defined as follows:

σ r = n∈N k \{r} (g r -g n ) 2 n k -1 1/2
(5.1)

The computed mean-square deviation σ r is then applied in the following exponential kernel function:

ξ r = exp -σ r - r∈N k σ r n k (5.2)
Finally, the local weight of pixel g r is obtained by normalizing the value of ξ r :

ω r = ξ r r∈N k ξ r (5.3)
Since the applied kernel function decays very fast, those pixels whose meansquare deviation is far away from the average value will have a relatively small weights. An illustration of how to calculate the local weights is shown in Fig. 5.1, and we take a patch from a natural image to depict the effectiveness of the local weights. We can observe that the patch is extracted from an inhomogeneous boundary region, thus relative to the central pixel, those pixels lying on the other side of the boundary are assigned with smaller weights in order to decrease their impact to the patch.

Global weights assignment

In 2 presents an example to show the effectiveness of using the global weights. Suppose that the intensities of the background, the triangle object and the rectangle object are 255, 200, 100 respectively, then their calculated global weights will be 0.7, 0.1 and 0.2 respectively. Without the global weights, the distances between the background and the objects are 55 and 155 respectively, while both distances become 158.5 when considering the global weights. Thus we can see that i) the distances between the background and the objects are increased; ii) both objects have the same distance to the background, which makes them easier to be segmented simultaneously.

Affinity graph construction

Given an image I, it can be represented as a graph G = (V, E), with V being the set of vertices and E being the set of edges connecting two vertices. We apply the Patch proposed WCP method to compute the weight of edges in the graph. In order to incorporate color information, the affinity graph is first computed in each channel of the RGB color space, formally defined as follows:

W (x i , x j ) = e -( N i=1 P c wi -N j=1 P c wj 2 /σ) , ||x i -x j || 2 < r (5.4)
where W is the affinity graph, and W (i, j) defines the edge weight of two vertices i and j in the graph. According to the derived weights, we discard those pixels in the patch whose weights are smaller than a threshold value which is set to 1/(n k ) × 1/N with n k the size of the local patch, and N the total number of pixels in the image.

x i represents the spatial coordinates of pixel i, and r is the graph radius.

P wi = (g r , r ∈ N k , if ω r × ξ r >= (1/(n k ) × 1/N )) (5.5)
with ξ r represents the global weight assigned to pixel g r . σ in Eq.( 4) is a positive constants to control the decaying speed of gaussian kernel function. c represents each channel of the RGB color space.

The final affinity graph is obtained by averaging the results from all the channels.

Graph partitioning

Given the affinity graph W , we apply the normalized cut (NCut) algorithm to partition the graph into k groups by solving the following generalized eigen-vector problem:

Ly = λDy (5.6)
where L = D -W is the Laplacian matrix, D = diag(W 1) is the diagonal degree matrix. The bottom k eigenvectors are computed either by k-means [START_REF] Ulrike | A tutorial on spectral clustering[END_REF] or discretization method [START_REF] Shi | Normalized cuts and image segmentation[END_REF].

Experimental Evaluation

In this section, we evaluate the proposed WCP method for image segmentation on two popular databases: the Prague color texture benchmark [START_REF] Haindl | Texture segmentation benchmark[END_REF] and the Berkeley image segmentation database (BSD) [START_REF] Arbelaez | Contour detection and hierarchical image segmentation[END_REF]. For simplicity, we fix the parameters for all the following experiments as: σ = 10, r = 10 in Eq.( 4) and the patch size is 7 × 7.

Results on Prague texture benchmark

The Prague texture benchmark datasets are computer generated 512 × 512 random mosaics filled with randomly selected textures. This benchmark provides a bunch Chapter 5. Graph-based Image Segmentation Using Weighted Color Patch of criteria for evaluation (see Table 1), and we list them in Appendix B which describes them in detailed manner. The proposed method is compared with the other unsupervised benchmark algorithms, including: EDISON [START_REF] Christoudias | Synergism in low level vision[END_REF], JSEG [Yining and Manjunath, 2001a], SWA [START_REF] Sharon | Segmentation and boundary detection using multiscale intensity measurements[END_REF], and GL-graph in Chapter 4. Fig. 5.3 presents seven selected 512 × 512 experimental benchmark mosaics and Table 1 gives their corresponding numerical scores w.r.t. different indicators. It can be observed that EDISON and JSEG tend to oversegment images while SWA and our method have better trade-off between over-/under-segmentation.

From the results presented in Table 1, we can see that no single algorithm can outperform all the others on all the measurements. Note that our method GL-graph presented in Chapter 4 ranks the first place on 10 indicators (highlighted in bold), the proposed method WCP and JSED has two and SWA has four best results. In particular, although EDISON also has 8 best performances, its other performances such as OS, O and C lagged far behind ours, which makes our method the best overall algorithm except GL-graph regarding to all associated indicators.

Results on Berkeley image database

The Berkeley image database contains 300 images and their corresponding ground truth (each image has at least 4 human annotations). In our experiments, we test the proposed method on all the 300 images, since the algorithm has no parameter to be trained. The number of segments k is set from [START_REF] Wang | Graph-based image segmentation using weighted color patch[END_REF]5,[START_REF] Karypis | A fast and high quality multilevel scheme for partitioning irregular graphs[END_REF]10,12,15,[START_REF] Goldberg | A new approach to the maximum flow problem[END_REF]20,23,25,28,30,31,[START_REF] Josep M Gonfaus | Harmony potentials for joint classification and segmentation[END_REF]35,[START_REF] Knutsson | Texture analysis using two-dimensional quadrature filters[END_REF]. The final results are evaluated according to 4 associated measurements, including: Probabilistic Rand Index (PRI) [START_REF] Unnikrishnan | Toward objective evaluation of image segmentation algorithms[END_REF], Variation of Information (VoI) [START_REF] Meila | Comparing clusterings: an axiomatic view[END_REF], Global Consistency Error (GCE) [START_REF] Martin | A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[END_REF], and Boundary Displacement Error (BDE) [START_REF] Freixenet | Yet another survey on image segmentation: Region and boundary information integration[END_REF]. The popular NCut, GBIS [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF] and Normalized Tree Partitioning (NTP) [Wang et al., 2008b] are applied for the purpose of comparison, and their parameters are the same as [Kim et al., 2010a], which manually tuned the number of segments for each image.

The quantitative results are presented in Table 2, with the best results highlighted in bold for each measurement. It is obvious to see that the proposed WCP method ranks the first place with respect to VoI and BDE compared with the other methods. Fig. 5.4 presents some visual comparisons of our results with the other methods, and we can see that NCut tends to split homogenous large region into separate regions and GBIS has thick edges, while our proposed method can obtain more meaningful region with accurate boundary. We also present some examples segmented by our proposed method in Fig. 5.5. It can be observed that our method can well segment the texture images (the penguin, the leopard, web girl), and it has high discriminative power to detect objects from different backgrounds.

Conclusion

In this paper, we propose a new method based on the weighted color patch to construct the affinity graph for image segmentation. The proposed method is invariant to uneven light conditions and noise benefitting from the usage of image patches. Patch Furthermore, we assign a local weight to each member in the patch to overcome the over-smooth effect, and also calculate a global weight for each pixel in the image to enhance the contrast between the background and the objects. The proposed method is evaluated by extensive experiments on two popular segmentation databases, and is quantitatively compared with some other standard algorithms. The results show that our method is powerful and competitive, and can be further applied on other clustering problems.

Introduction

Most unsupervised image segmentation methods, which are frequently used for highlevel vision tasks like object recognition and image annotation, involve essentially low level features such as color, boundary or texture. In particular, various method using graphs and spectral clustering have been proposed in recent years, however it remains challenging for those methods to provide desirable visually semantic partitions.

Generally, for those methods, building a faithful graph is critical to the final quality. The graph nodes can be pixels or regions, and the graph affinity matrix encodes the similarity between either low level features or top down features associated with the nodes. Low level features capture object basic properties and they can be obtained with various descriptors or operators, such as color histograms, histogram of oriented gradients (HOG), scale invariant feature transform (SIFT), local binary patterns (LBP), etc. Despite progresses in the design of more informative low-level Chapter 6. Sparse Coding and Mid-Level Superpixel-Feature for 0 -Graph Based Unsupervised Image Segmentation features, performances remain limited. Top down features usually convey semantic or prior knowledge about the segmented regions or objects. Many works treat the output of trained classifiers and object detectors [START_REF] Li | Object bank: A high-level image representation for scene classification and semantic feature sparsification[END_REF], or semantic segmentation algorithm [START_REF] Fu | Integrating low-level and semantic features for object consistent segmentation[END_REF] as top down information to guide the low level unsupervised segmentation. However, all these top-down semantic methods require non-trivial amounts of human-labeled training data, which is unrealistic in practical situation.

Motivation and the proposed method

In this chapter, we focus on mid-level features based on sparse coding, as in [START_REF] Zou | Semantic image segmentation using region bank[END_REF] where first a dictionary is built by learning or human labeling, then the coefficients of the sparse representation in this dictionary are used to define mid-level features for classification or grouping. In contrast to [START_REF] Zou | Semantic image segmentation using region bank[END_REF], we build the dictionary from informative patches centered at interest points detected without any supervision, and each mid-level feature is the sparse coding in the dictionary of the low level feature associated with a superpixel. This way, the contextual information, which has been proved an efficient cue to discriminate two objects or images [START_REF] Yong | Object-graphs for context-aware visual category discovery[END_REF], is added to the original low-level features to improve the robustness of the similarity coefficient between two superpixels in the graph construction, whose quality plays a critical role to the segmentation result.

More precisely, the whole segmentation model starts by extracting interest points from the image, associating with them a set of low-level features whose collection forms a dictionary, and over-segmenting the input image into multi-layer superpixels. Then, each superpixel is associated with a sparse representation of its low level feature in the previously built dictionary. This proposed feature inherits of the original descriptors' property and covers also adaptive contextual information. Compared with related works and other benchmark algorithms on the MSRC dataset [START_REF] Shotton | TextonBoost: Joint appearance, shape and context modeling for multi-class object recognition and segmentation[END_REF], the key contribution of this paper is that our new mid-level feature is able to describe better the superpixels. The similarities between superpixels are then computed based on 0 graph construction in the spirit of [START_REF] Wang | A graph-cut approach to image segmentation using an affinity graph based on l0-sparse representation of features[END_REF] (where only low-level features were used). Finally, the constructed graph is plugged into a robust unsupervised segmentation framework introduced in [START_REF] Li | Segmentation using superpixels: A bipartite graph partitioning approach[END_REF]. The proposed method can segment visually semantic regions, and can be used in many high-level computer vision tasks.

The organization of the chapter is as follows: in Section 2 we introduce the proposed mid-level features based on the sparse coding and the segmentation framework, and in Section 3 we present and comment a few segmentation results on the MSRC dataset. We conclude in Section 4.

Related work

In recent years, features popularized in other domains, e.g. image classification and sliding-window detection, has been renewed interest in segmentation together with recognition based on bottom-up segments. In this problem, the typical processing pipeline is: 1) extracting local feature (e.g., SIFT and HOG), 2) encoding the local features in an image descriptor (e.g., histogram of the quantized local feature), and 3) representing resultant descriptor to a classifier (e.g, support vector machine). The role of feature encoding is the core component, which produces a global description of an image or a region to summarize the local features inside the region [Carreira et al., 2012a[START_REF] Huang | Feature coding in image classification: A comprehensive study[END_REF]. Note that in the thesis, we denote the feature descriptor derived from 1) and 3) as mid-level feature, also known as bag-of-visual features in other literatures. Successful applications of discriminative power of local features also have motivated their introduction for bottom-up image segmentation directly. For instance, [START_REF] Yu | Bag of textons for image segmentation via soft clustering and convex shift[END_REF] proposed bag of textons, namely, filter responses encoded by soft clustering technique for image segmentation.

There are bunch of feature coding methods proposed in literature. As suggest by the survey [START_REF] Huang | Feature coding in image classification: A comprehensive study[END_REF], we can group the existing techniques into two major categories, global and local coding according to the motivations presented in their original papers. Global coding focuses on the global description of all features rather than each individual feature. More specifically, there are two major methods:

• Voting-based methods describe the distribution of features with a histogram, also referred as codebook in literature, which carries the occurrence information of codewords. Such a histogram can be constructed by hard quantization or soft quantization. For instance, in [START_REF] Csurka | Visual categorization with bags of keypoints[END_REF], a bag of key points called as the bag-of words for word-document or bag of features for image classification, was proposed as mid-level feature, which corresponds to a histogram of the number of occurrences of particular image patterns in a given image. To avoid drawbacks of the codebook produced by K-means or radius based clustering, [START_REF] Van Gemert | Kernel codebooks for scene categorization[END_REF] proposed an uncertainty modeling method to form the codebook.

• Fisher coding-based methods estimate the distribution of features or codebook with the Gaussian mixture models (GMM), consisting of the weights, the means, and the covariance matrix of multiple Gaussian distributions, each of which reflects one pattern of features. Fisher Kernel introduced by Jaakkola et al. [START_REF] Jaakkola | Exploiting generative models in discriminative classifiers[END_REF] and applied by Perronnin and Dance [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF] to image classification.

Yet local coding is proposed to describe each individual feature. More precisely,

• Reconstruction-based methods use a small part of codewords to describe each feature via solving a least-square-based optimization problem with constraints on codewords, i.e., a feature can be represented with a small error. There is a huge body of literature existing on this topic. Their difference mainly lies on constraint term. For instance, sparse coding is with a constraint term: [START_REF] Yang | Linear spatial pyramid matching using sparse coding for image classification[END_REF]with constraint term M i=1 |v(i)|; LLC [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF] is subject to constraint: M i=1 (v(i)exp(||x -b i || 2 /σ)). Besides this, there are many other reconstruction-based coding methods, e.g., Laplacian sparse coding [START_REF] Gao | Local features are not lonely-laplacian sparse coding for image classification[END_REF], mixture sparse coding [START_REF] Yang | Efficient highly over-complete sparse coding using a mixture model[END_REF], nonnegative sparse coding [START_REF] Zhang | Image classification by non-negative sparse coding, low-rank and sparse decomposition[END_REF], hierarchical sparse coding [START_REF] Yu | Learning image representations from the pixel level via hierarchical sparse coding[END_REF]. All of them extend sparse coding by substituting the constraint term.

• Local tangent-based methods, e.g., [START_REF] Yu | Improved local coordinate coding using local tangents[END_REF] assume that all features constitute a smooth manifold where codewords are located. They derive an exact description for each feature through approximating the Lipschitz smooth manifold. In this way, features are not independent but closely related, expressed by a Lipschitz smooth function.

• Saliency-based methods e.g., [START_REF] Huang | Salient coding for image classification[END_REF] encode each feature by the saliency degree, which is calculated using the ratio or the difference of the distances from a feature to its nearby codewords. The core idea is that a strong response on a codeword indicates relative proximity, which means that this codeword, compared with all other codewords, is much closer to a feature belonging to this codeword.

Finally, we summarize the characteristics of the different methods mentioned above.

Global coding pursues to model the probability density distribution of features, and therefore, it is not easy to be influenced by a small number of unusual features.

In particular, Fisher coding uses GMM for probability density estimation, which is more robust than the histogram-based manner. Local coding aims to describe each individual feature and, thus, is sensitive to unusual features, however, as the codebook size increases, it can describe more patterns of features. Thus, it has better adaptiveness compared with global coding.

Superpixels, mid-level features, and sparse representation

Our approach consists of three steps: 1) interest points extraction, low-level features computation, and dictionary building; 2) over-segmentation of the original image, extraction of superpixels (defined as the over-segmented regions), computation of a low-level feature for each superpixel, and sparse representation in the dictionary of step 1; 3) graph construction and partitioning.

Low-Level Features Detection and Extraction

We use low-level features extraction to build a meaningful dictionary to represent a given image. First, we extract a set of key points from the image. The meaningfulness of the low-level dictionary is highly dependent on the choice of the key points. If they capture the main structural information of the input image, then the derived dictionary will be highly meaningful. In practice, we have tested various approaches, see Fig. 6.1: either the interest points are randomly or densely sampled, or they are obtained using a feature descriptor, e.g., the Harris detector, the Difference of Gaussians (DoG), or the Hessian detector. The respective performances are discussed in Section 3. Once interest points have been extracted, we consider the local image patches around them, from which low-level features can be computed (we use in this paper RGB color histograms for its strong discriminative skill, but other features as LBP histogram or SIFT may be used). Finally, our low-level dictionary is defined as the collection of all these low-level features, see Fig. 6.2.

Mid-Level Features Extraction over Superpixels

We call superpixel a region of an over-segmentation of the original image. In practice, we compute several over-segmentations, and we associate with each superpixel a low-level feature (in our experiments, we used RGB color histograms for its strong discriminative skill). Then we define the mid-level feature associated with a superpixel as the sparse representation of its low-level feature in the dictionary built previously, see Fig. where α ∈ R n , and α 0 := α 0 is the number of its non-zero coefficients. Suppose α is a solution of the problem and Λ α = {j|α(j) = 0} is the index set of non-zero ent subsets of MSRC database and compare it with several state-of-the-art methods; finally, we show some visual examples of our method. [START_REF] Wang | A graph-cut approach to image segmentation using an affinity graph based on l0-sparse representation of features[END_REF] 0.8190 1.2930 0.1508 9.3644 NCut [START_REF] Shi | Normalized cuts and image segmentation[END_REF] 0.8052 1.2516 --LRR(CH) [START_REF] Liu | Robust recovery of subspace structures by low-rank representation[END_REF] 0.7912 1.3002 --MS [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF] 0.7307 1.7472 --

Experimental Results

As mentioned in section 6.2.1, the property of the low-level dictionary is highly dependent on the selection of the key points. Therefore, we compared the Harris detector, Difference of Gaussian (DoG), Hessian detector, random sampling, and the dense sampling (see Fig. 6.1). The results are shown in Tab. 6.1, from which we can deduce that dense sampling is the most efficient way to extract interest points.

The main reason is that dense sampling can capture almost all information of the image and is well-suited for sparse coding that requires an over-complete dictionary. We compare in Table 6.2 the performances of our method on the MSRC database and the performances of the method we proposed in [START_REF] Wang | A graph-cut approach to image segmentation using an affinity graph based on l0-sparse representation of features[END_REF] (limiting to RGB histogram as superpixel feature, and calling baseline this reference algorithm). Obviously, our new method can achieve excellent performances on segmenting object classes such as cow, building, sheep, flower, sign, bird, road, and boat, but is less efficient for tree, face, cat, dog, bike, etc. The visual results are also shown in Fig. 6.4. Chapter 6. Sparse Coding and Mid-Level Superpixel-Feature for 0 -Graph Based Unsupervised Image Segmentation

The reasons for the difference performances are various: 1) objects like face, cat, and dog usually have complex backgrounds mainly associated with indoor scene which makes the evaluation unfair for the machine algorithms since the groundtruth does not label the indoor objects. On the other side, in the case of objects without complex backgrounds, our method can segment them correctly even if the object itself presents obvious color variations like on cow, building and flower; 2) objects like face or bike can be subject to strong illumination changes which prevent the machine algorithms from grouping object correctly if only color is used as low level descriptor. Results should be improved if other descriptors as LBP were used, and this is the purpose of future work. 3) the quality of segmentation can also be influenced greatly by the way superpixels are extracted.

We compare the performances of our approach with other state-of-the-arts algorithms in Tab. 6.2. We used the scores given in [START_REF] Liu | Robust recovery of subspace structures by low-rank representation[END_REF], observing that GCE and BDE were not reported. Our method ranks first according to PRI and BDE, which makes it one of the most competitive algorithms.

Conclusion

We introduced a new unsupervised image segmentation method based on 0 -graph, superpixels, mid-level features, and sparse coding. An nice property of the mid-level feature we propose is that it can capture adaptive contextual information and carries as well the original low level feature information. Quantitative comparison with the state-of-art methods, as well as visual results, indicate that our new algorithm is a competitive image segmentation method.

Introduction

Designing an efficient and robust tracking algorithm has been an active research topic in computer vision community over the past decades. The basic task of video tracking is to detect the position or shape of objects and to link correctly trajectories of moving single/multiple targets in consecutive frames. In practice, multiple objects tracking (MOT) is a canonical method for wider range of applications ranging from human surveillance [START_REF] Bibliography | Stable multi-target tracking in real-time surveillance video[END_REF], Butt and Collins, 2013b[START_REF] Milan | Detection-and trajectory-level exclusion in multiple object tracking[END_REF], vehicles tracking [START_REF] Betke | Real-time multiple vehicle detection and tracking from a moving vehicle[END_REF], Rubio et al., 2012], to biological analysis (e.g. cell tracking [START_REF] Chenouard | Multiple hypothesis tracking for cluttered biological image sequences[END_REF]), or behavior pattern study [START_REF] Veeraraghavan | Shape-andbehavior encoded tracking of bee dances[END_REF].

Chapter 7. Active Colloids Segmentation and Tracking

Context

In this thesis, we aim to develop a reliable system to track tens of thousands of active colloids in certain environment. Here, active colloids are tiny-scaled particles which can propel themselves by consuming energy at individual level. These spherical colloidal particles (see Fig. 7.1) can be sedimenting, platinum-coated gold particles [START_REF] Buttinoni | Dynamical clustering and phase separation in suspensions of self-propelled colloidal particles[END_REF] or an embedded hematite cube [START_REF] Palacci | Living crystals of light-activated colloidal surfers[END_REF]. The modeling of dense active suspensions of artificial self-propelled colloids has aroused recently the interest of physicists [START_REF] Buttinoni | Dynamical clustering and phase separation in suspensions of self-propelled colloidal particles[END_REF][START_REF] Theurkauff | Dynamic clustering in active colloidal suspensions with chemical signaling[END_REF], with the general purpose of understanding the mechanisms of self-aggregation and the formation of clusters. Very recent studies found that active systems exhibit a wide variety of collective behaviors, structures and patterns as illustrated in Fig. 7.1 where typical situations at low and high density are presented. Fig. 7. 1 (a) shows the stage of temporal evolution of a small cluster. During the period, the aggregation is dynamical, i.e., particles join and leave the cluster frequently. et al.. Fig.7.1 (d) illustrates that at higher densities, clusters grow until the system consists of a few big clusters according to the observations of Buttinoni et al.. Moreover, such mechanisms can be observed in many living systems, such as cells, sheep flocks, birds, fishes swarms, etc. However, the collective patterns hide many different mechanisms in the individual motion, e.g. move and interaction. Therefore, there is a need for identifying the underlying models in order "to disentangle the universal from the specific behavior of those complex phases" [START_REF] Theurkauff | Dynamic clustering in active colloidal suspensions with chemical signaling[END_REF]. A natural approach is to derive the models from the experimental observation of colloidal suspensions, and more precisely from the identification of the individual trajectories of colloids. However, labeling manually massive colloidal suspensions in long video sequences to obtain accurate trajectories leads to a tremendous amount of work. It is therefore necessary to design a reliable, automatic, and systematic algorithm, which can process long video sequences with good resolution.

Although several publications on colloidal suspensions [START_REF] John | Methods of digital video microscopy for colloidal studies[END_REF]Grier, 1996, Royall et al., 2003] have provided standard procedures to identify independent paths, they still differ from our problem in the context of active systems in some respects, for example, irregular motion and frequent interactions among the colloids. Nevertheless, the task of tracking active colloids shares several common difficulties with the particle tracking in biological study [START_REF] Chenouard | Multiple hypothesis tracking for cluttered biological image sequences[END_REF], 2014[START_REF] Padfield | Coupled minimum-cost flow cell tracking for high-throughput quantitative analysis[END_REF], where a "particle" may be anything, such as a single molecule, or cells, genes etc. Difficulties include similar appearance, large number of objects, frequent events like entering, exiting, splitting, merging etc.. Yet in the context of active systems, we face with new challenges which are still open issues. First, due to that colloids are all similar, the only useful information is spatial location. Second, colloids can have very complicated motion [START_REF] Buttinoni | Dynamical clustering and phase separation in suspensions of self-propelled colloidal particles[END_REF]. For example, a colloid may follow ballistic motion at short times, while at longer times, it transits to a diffusive regime. Moreover, unlike the application in human or cell tracking, the motion of a colloid can change frequently because of collisions with other colloids. Thus, it is difficult to infer an accurate pre-defined model to predict colloid's location, especially in a long video sequence. Furthermore, as will be explained below, in the experiments that we use, colloids essentially move in a 2-dimensional plane, yet some 3d behavior may rarely occur which results in that some colloids may exhibit low intensity or disappear, and then appear again in a short period of time. Consequently, only trajectories fragments may be observed for some colloids.

In addition, in contrast with living cells tracking where merging usually happens among few cells and small clutter moves at small speed, in our case, as pointed in [START_REF] Buttinoni | Dynamical clustering and phase separation in suspensions of self-propelled colloidal particles[END_REF], large clusters can form and move. It is therefore essential, in order to identify accurately the motion law, to be able to distinguish colloids individually.

Motivation and contribution

Our goal is to design a faithful detection and tracking algorithm to answer physicist's needs, i.e. detecting precisely the positions and the independent trajectories of many self-propelled colloids. Our work is based on video captures of a two-dimensional dense active suspension of artificial self-propelled colloids [START_REF] Buttinoni | Dynamical clustering and phase separation in suspensions of self-propelled colloidal particles[END_REF], see the experimental details in Section 7.4. By two-dimensional, it is meant that the colloids being heavy, they settle at the bottom of the observation cell and only 2D motions are observed. In particular, the colloids being observed from below, there is essentially no occlusion phenomenon. We propose a framework to jointly segment, localize and track each colloid. The difficulty of the detection task follows from the severe intensity inhomogeneities in each frame, the high number of colloids, and the poor temporal resolution. In other experiments where the intensity is more homogeneous and the temporal resolution is high, a much simpler algorithm can be used (for instance adaptive threshold technique [START_REF] Otsu | A threshold selection method from gray-level histograms[END_REF], morphological top hat [START_REF] Serra | Image analysis and mathematical morphology[END_REF]). The method that we propose in this paper can handle much more complicated situations, e.g. it is also applicable to dense assemblies of passive colloids, such as colloidal glasses and gels.

To sum up, our contribution is as follows:

• To obtain high-quality segmentation, we propose to combine the level set method and circular Hough transform in the same framework, to handle the severe intensity inhomogeneities and highly cluttered colloids.

• We build a graph over all frames instead of over a very few, and further refine by three additional configurations. We insist on the fact that no assumption is made on colloids motion, except that the positions of a colloid in two consecutive frames are close. In particular, we do not assume any smoothness of the trajectories and we do not favor a priori linear motions.

• We propose to recover all trajectories from the trellis graph simultaneously.

More precisely, we model the problem by finding the maximum flow with minimum cost over the whole graph. We propose an additional procedure called tag-then-delete together with the successive shortest path (SSP) algorithm to efficiently solve the min-cost/max flow optimization.

• Unlike other methods, validated on simulated image data, we choose to evaluate quantitatively on a real benchmark, the active colloids suspension, provided to us by physicists. These videos have been annotated by different graduate students majored in computer vision. As far as we know, there is very limited previous work using real dataset with human observations labeling the ground truth, for the obvious reasons that it is a tedious task to track all the particles in long video sequences. Instead, most methods first evaluate on a synthetic benchmark [START_REF] Chenouard | Objective comparison of particle tracking methods[END_REF][START_REF] Ruusuvuori | Benchmark set of synthetic images for validating cell image analysis algorithms[END_REF], Smal et al., 2010a] with other standard algorithms, then provide performances on real data, e.g. cells in fluorescence image sequences.

Organization. The remainder of this paper is organized as follows. In Section 2, we present a survey on previous literature on multiple object tracking. In Section 3, we introduce our proposed detection algorithm and trellis graph construction for modeling the generic dynamics in the active systems, and present in detail the Mincost/Max flow algorithm and our optimized solution to this optimization problem as well. In Section 4, our real-data benchmark is introduced and extensive experiments are presented to validate our method. Finally, we conclude in Section 5.

Related Work

Advances in imaging techniques and applications in some specific domains have encouraged greatly the research on automatic tracking methods capable of establishing accurate trajectories. In this paper, we concentrate on the tracking-by-detection paradigm to solve the task of multiple object tracking. Existing proposed methods in literature can generally be divided into two components: (i) particles detection, where targets are detected from each video frame, and (ii) multiple objects tracking, where detected objects or particles are connected across frames by a suitable tracker algorithm. For each of the above two steps, there are a huge body of literature over the years. Nevertheless, several good-quality surveys with relevant to the object tracking [START_REF] Chenouard | Objective comparison of particle tracking methods[END_REF][START_REF] Meijering | Methods for cell and particle tracking[END_REF][START_REF] Bibliography | Object tracking: A survey[END_REF] are available to provide practical yet insightful summarization these developments. We briefly review these techniques concerning multiple particles detection and tracking.

Particles Detection

Generally, most proposed particle detection frameworks can be split into three steps and some of them can be optional or implement in a different way, according to [START_REF] Chenouard | Objective comparison of particle tracking methods[END_REF], Smal et al., 2010a,b]: (i) noise reduction, e.g. Guassian smoothing (ii) signal enhancement, e.g. wavelet multiscale product [START_REF] Olivo-Marin | Extraction of spots in biological images using multiscale products[END_REF], and (iii) signal thresholding. For example, in [START_REF] Basset | Slt-log: A vesicle segmentation method with automatic scale selection and local thresholding applied to tirf microscopy[END_REF], they exploited Laplacian of Gaussian at several scales to detect the minima of LoG values, which is then thresholded to derive segmentation result. (LoG) of the images at several scale In [START_REF] Chenouard | Objective comparison of particle tracking methods[END_REF], they performed an objective comparison of different methods with an open competition, and found that approaches to particles detection algorithm varied greatly, ranging from simple threshold [START_REF] Winter | Vertebrate neural stem cell segmentation, tracking and lineaging with validation and editing[END_REF], or local-maxima finding [START_REF] Coraluppi | Multi-stage multiple-hypothesis tracking[END_REF] and morphological processing [START_REF] Anoraganingrum | Cell segmentation with median filter and mathematical morphology operation[END_REF], to linear and nonlinear model fitting [START_REF] Liang | Tracking clathrin coated pits with a multiple hypothesis based method[END_REF], and centroid estimation [START_REF] Ivo | Feature point tracking and trajectory analysis for video imaging in cell biology[END_REF]. Most of detection algorithms have incorporated two or more of these mentioned techniques, and inevitably they shared many techniques in common.

Multiple Object Tracking

Multiple object tracking has been intensively studied by researchers, and can be divided into two basic classes [START_REF] Aubrey | Some assignment problems arising from multiple target tracking[END_REF]]: (i) the probabilistic based methods. (e.g. Kalman filters [START_REF] Samuel S Blackman | Multiple-target tracking with radar applications[END_REF], particle filters [START_REF] Kitagawa | Non-gaussian state-space modeling of nonstationary time series[END_REF], multiple hypothesis tracking [START_REF] Blackman | Multiple hypothesis tracking for multiple target tracking[END_REF], probabilistic multiple hypothesis tracking [START_REF] Gelgon | Recovery of the trajectories of multiple moving objects in an image sequence with a pmht approach[END_REF], inference on Bayesian network [START_REF] Nillius | Multi-target tracking -linking identities using bayesian network inference[END_REF], joint probabilistic density association filters [START_REF] Fortmann | Sonar tracking of multiple targets using joint probabilistic data association[END_REF]), Monte Carlo Markov Chains methods [START_REF] Songhwai Oh | Markov chain monte carlo data association for general multiple-target tracking problems[END_REF]; (ii) non-probabilistic methods (e.g. nearest neighborhood, minimum-cost [Butt and Collins, 2013a[START_REF] Wu | Efficient track linking methods for track graphs using network-flow and set-cover techniques[END_REF][START_REF] Padfield | Coupled minimum-cost flow cell tracking for high-throughput quantitative analysis[END_REF], shortest path [START_REF] Berclaz | Multiple object tracking using k-shortest paths optimization[END_REF][START_REF] Jiang | Accurate 3d multi-marker tracking in x-ray cardiac sequences using a two-stage graph modeling approach[END_REF], minimal paths [START_REF] Bonneau | Single quantum dot tracking based on perceptual grouping using minimal paths in a spatiotemporal volume[END_REF], Hungarian algorithm [START_REF] Harold W Kuhn | The hungarian method for the assignment problem[END_REF]).

Most proposed algorithms are locally greedy, that is run a low-level tracker in a small window (two frames or three) to obtain tracklets, and then link the par-tial track fragments with method like network-flow [Zhang et al., 2008b], linearprogramming [START_REF] Hao Jiang | A linear programming approach for multiple object tracking[END_REF], matching algorithm [START_REF] Harold W Kuhn | The hungarian method for the assignment problem[END_REF], Bayesian network [START_REF] Nillius | Multi-target tracking -linking identities using bayesian network inference[END_REF], or solving a set cover problem [START_REF] Wu | Efficient track linking methods for track graphs using network-flow and set-cover techniques[END_REF]. These locally greedy trackers are applied widely for the sake of low computational cost, nonetheless such trackers tend to have identity swap errors, which are hard to be corrected when future information is included. Another drawback is that such strategy can easily miss the global optimal solution. It is also fair to mention that Multiple Hypothesis Tracking and Monte Carlo Markov Chains methods search the largest nonconflicting trajectories of all objects satisfying the expected motion behavior, but cannot guarantee a globally optimal solution in sub-exponential time.

Proposed Framework for Colloids Detection and Tracking

Accurate Active Colloids Detection

In the paradigm of track-before-detect, accurate detection method is essential for the quality of tracking. In general, the difficulty of detecting particles yields corrupted sets of detections: some particles are missed by the detection procedure and some artifacts are wrongly considered as being some spots of interest. In our context of the active colloids detection, due to low dose concentration, all images have low contrast-to-noise. Moreover, the images are subject to uneven illumination, i.e. the flat-field from the lamp causes the interior to look brighter than the edges of the image (e.g. see Fig. 7.2(a)). In addition, objects can be highly cluttered, which can cause severe ambiguities in the tracking stage.

Chapter 7. Active Colloids Segmentation and Tracking

We propose an accurate method to detect meaningful objects based on the modified Circular Hough Transform (CHT) [START_REF] Tim | Size invariant circle detection[END_REF] and the level set method proposed in [START_REF] Zhang | Global data association for multiobject tracking using network flows[END_REF]. It is known that all objects in the image are round-shape spots, although some colloids may have deformations due to twinkle or uneven illumination. The Circular Hough Transform has been proved efficient in detecting circle targets thanks to its nice properties such as the robustness to noise, invariance to slight occlusion and illumination.

However, when dealing with real-world images, the circular Hough transform can miss potentially targets altered by intensity inhomogeneities. In this paper, we adopt an efficient level set variational model [START_REF] Zhang | Global data association for multiobject tracking using network flows[END_REF] to overcome the difficulties arisen from such inhomogeneities, thanks to the region-scalable fitting (RSF) energy which quantifies how well, given a contour C in the image domain Ω, the image intensities in the outer and inner domains with respect to C are well approximated locally by two functions f 1 and f 2 :

ε RSF (C, f 1 , f 2 ) = Ω (λ 1 inside(C) K σ (x -y)|I(y) -f 1 (x)| 2 dy +λ 2 outside(C) K σ (x -y)|I(y) -f 2 (x)| 2 dy)dx + ν|C| (7.1)
where Ω is the image domain, λ 1 , λ 2 , ν are positive constants, K σ is a Gaussian kernel whose standard deviation σ tunes the locality of the approximation, and the length |C| of C is a regularization parameter that avoids spurious contours when the energy is minimized. The fitting energy ε RSF is able to segment objects even in severe illumination condition, due to that, in contrast to global threshold in classical level set based active contour models (e.g. the Chan-Vese model [START_REF] Chan | An active contour model without edges[END_REF]), the approximating functions f 1 and f 2 are not necessarily constant within the outer and the inner domains denoted as outside(C) and inside(C) respectively. This allows a good robustness to light changes.

As shown in [START_REF] Zhang | Global data association for multiobject tracking using network flows[END_REF], the energy admits a level-set formulation, so that the associated minimizing flow can better handle the topological changes. More precisely, a contour C ⊂ Ω is represented as the zero level set of a function φ : Ω → R, which is called level set function (a classical example of such function is the signed distance function to C). We solve the level set minimization problem with standard gradient descent method in Algorithm 1, and we refer the reader to [START_REF] Zhang | Global data association for multiobject tracking using network flows[END_REF] for more details. Convex formulations of ε RSF (C, f 1 , f 2 ) in the spirit of [START_REF] Chan | Algorithms for finding global minimizers of image segmentation and denoising models[END_REF][START_REF] Pock | A convex formulation of continuous multi-label problems[END_REF]] could be used, and would decrease the computational time, but they would not be equivalent to Algorithm 1 which involves an additional regularization term that is well suited for the recovery of objects with smooth boundaries.

The proposed detection method can segment individual tiny objects in dense populations in the presence of noise and intensity inhomogeneities. Input frame I i 3:

Segment frame I i with the RSF level set method, i.e.:

4:

Initialize the level set φ (using for instance the signed distance function to the discontinuity set of the segmentation), the number of iterations numIter, and the parameters λ 1 , λ 2 , ν, µ, σ;

5:

for k = 1 : numIter do 6:

Compute the approximate Heaviside function and its derivative:

H ε (φ) = 1 2 [1 + 2 π atan( φ ε )], (7.2)
δ(φ) = 1 π ε ε 2 + φ 2 ;
(7.3)

7:

Compute the fitting intensities:

f 1 = K σ * [H ε (φ)I i ] K σ * [H ε (φ)] , (7.4
)

f 2 = K σ * I i -K σ * [H ε (φ)I i ] K σ * 1 -K σ * [H ε (φ)] (7.5) 8:
Update φ:

∂φ ∂t = -δ ε (φ)(λ 1 e 1 -λ 2 e 2 ) + νδ ε (φ) div( ∇φ |∇φ| )
+µ ∆φ -div ∇φ |∇φ| (7.6) where, e k

(x) = Ω K σ (y -x)|I i (x) -f k (y)| 2 dy, k = 1, 2.

9:

Threshold the level set φ with Otsu's method [START_REF] Otsu | A threshold selection method from gray-level histograms[END_REF], get coarse object interest regions I roi .

10:

Find circles with CHT on I roi : [centers radii] = CHT (I roi , [minR maxR]), where [minR maxR] is the range of possible radii;

11:

Generate binary image by creating round regions centered at centers and get each colloid's center.

reason lies in that the RSF model is unable to separate clustered colloids and the CHT misses some ambiguous targets. Fig. 7.2 (d) demonstrates that combining both methods is much more efficient.

Active Colloids Tracking

Given detected colloids, the next task is to infer meaningful trajectories throughout the video. Unlike common methods, which first implement partial matching between two or three frames, then link all fragments to form meaningful paths, we build the graph using all colloids within all frames, and then solve the multi-frame data association problem.First, the output of the detection step consists in all colloids' centers associated with frame indexes, and this information is used to construct an initial graph. Second, we refine the initial graph in order to correct local "errors" (see Fig. 7.3), which may cause ambiguity during later data association. Finally, the min-cost/max flow algorithm is adopted to solve the problem of finding meaningful paths over the trellis graph, and the solution is guaranteed to be a global optimum with respect to the current graph.

Directed Acyclic Graph Construction

A directed graph G = (V, E) is constructed to model the image frames over the time, where V is the nodes set representing all colloids centers, and E is the edge set of pairwise nodes representing the relationship of these nodes. The quality of the constructed graph is very important to the final tracking result. We have two stages for the graph construction: 1) initial graph construction; 2) initial graph refinement. Initial Graph Construction: In collision-free situations, a single colloid exhibits Brownian-like motion. In practice however, the population density yields frequent collisions, which induce abrupt changes of colloids' motion velocity and direction. It implies that we cannot impose any motion smoothness, in particular because the purpose of the study is to identify the underlying motion model, not to impose it a priori. Therefore, we construct the initial graph using only a simple spatial rule, i.e. each node links to its neighbors within a search range d max , and the edge weight coincides with the normalized distance between both neighbors.

Mathematically, for a node v = (x , y ) at frame f k-1 finds its neighbor u = (x, y) in the next frame f k , the cost ω uv of linking them is defined as:

ω uv = u -v 2 d max (7.7)
where d max is a parameter which controls the search range. Initial graph refinement: Given the initial weighted graph, we now want to recover meaningful paths in it. However, the graph's construction rules being uniform, a colloid in a given frame may be connected with none, one or several colloids in the previous and next frames. Heuristically, we identified three configurations that may require a modification of the graph which, in practice, improves the final result. These configurations are illustrated in Fig. 7 The graph refinement corresponding to fixing these configurations is synthesized in Algorithm 2. It is worth mentioning that the refinement removes at most one connection at each node, and that of course there remain afterward, in particular in zones with clusters, nodes with more than two neighbors. Experimentally, we observed that there is no need to iterate the refinement until convergence to a stable graph. There is actually no significant improvement of the final optimal flow after two iterations of this intermediate refinement step.

Full Trajectories via Min-cost/max Flow

In the context of tracking, our goal is converted to finding the largest set of independent trajectories, which can be expressed as a maximum flow problem. While there are many maximal solutions to the same flow network, the fact that colloid's motion shows natural spatial continuity between consecutive frames yields naturally to defining the optimal tracking result as the solution of a minimum cost / maximum flow problem (min-cost/max flow).

Mathematical formulation: we consider a directed graph G = (V, E) with source s ∈ V and sink t ∈ V , where each edge e uv ∈ E has unit capacity. We will denote as f uv a volume of flow passing from node u to node v along e uv . If e uv is positively oriented then 0 ≤ f uv ≤ 1, otherwise -1 ≤ f uv ≤ 0. The cost per unit flow on e uv is denoted as ω uv -we already assumed that ω uv = u -v 2 /d max whenever u, v = s, t, and of course edges from s or to t have no cost. We shall work only with circulation flows, i.e. the inflow and outflow volumes are equal at each node except s and t.

Sending a volume m of a circulation flow from s to t, and looking for the flow repartition along the graph with minimal cost is equivalent to solving the following problem [START_REF] Ravindra | Network Flows: Theory, Algorithms, and Applications[END_REF]: 7.8) subject to the following properties Thus many potential trajectories are actually hidden in the initial graph. Instead of performing SSP once, we apply the method iteratively followed by a tag-then-delete procedure. In each iteration, the SSP first finds a set of optimal trajectories (shown in blue lines in Fig. 7.4(a)) in the current graph. The tag-then-delete procedure then tags and deletes the nodes as well as their corresponding edges within the flow (dots in gray color and dash lines in Fig. 7.4(b)). The rest of nodes with 0 in-degree will be connected to the source and the ones with 0 out-degree will be linked to the sink, which is shown in Fig. 7.4(b), where bold edges in orange are the new edges connected with the dummy nodes, i.e. source and sink in red and green respectively. The newly constructed graph is fed into the next iteration. As the number of tracks is unknown, the iterative algorithm will stop when all nodes in the initial graph have been deleted, which means every potential colloids' path has been found. Step I: initialize graph G, and compute its residual graph G * ; 4:

argmin f (u,v)∈E ω uv f uv (
(i) |f uv | ≤ 1; (ii) f uv = -f vu ; (iii) w∈V f uw = 0 ∀u = s, t; ⋯ 𝒇 𝒌-𝟏 𝒇 𝒌 (
Step II: find min-cost paths (ii) update each edge cost ω

(K+1) uv , ∀e uv ∈ E by ω (K+1) uv = ω (K) uv + d(u) -d(v) (7.9) 8:
(iii) if ∃p K (p K is a min-cost path) then push flow from s to t; Step III: do depth-first-search to find every path from s to t; 15:

Step IV: tag nodes V l in path set P = {p K } and delete the nodes and their corresponding edges E l ; 16:

Step V: construct a new graph G with nodes V = V \ V l and E = E \ E l ; 17: end 18: Output:All tracks P

Experiments and Discussion

Benchmark

Data acquisition: the active particles in all videos are homemade spherical gold colloids of radius α 1.1 ± 0.1 µm, half covered with platinum. In the presence of hydrogen peroxide, the particles self-propel consuming H 2 O 2 under a self-phoretic motion (a combination of diffusiophoresis and self-electrophoresis) [START_REF] Palacci | Sedimentation and effective temperature of active colloidal suspensions[END_REF]]. The active system is observed with an inverted optical microscope and a Hammatsu Orca-ER camera. Each video contains 500 frames (taken at 1 fps), and each frame's size is 1024 × 1344 pixels. We already mentioned in the introduction that a better acquisition system can provide a better temporal resolution and images with less noise and less intensity inhomogeneities. The purpose of this paper is to propose a general algorithm which works also in more difficult situations. Ground-truth generation: the ground-truth is obtained from the manual tracking of particles in subvideos. More precisely, we divide the first large-scale video into 16 small subvideos of size 256 × 336 pixels per frame. The ground-truth is generated as follows:

• each subvideo is labeled by various observers in order to take into account that tracking results may differ between various observers.

• each time, only one colloid is tracked across all 500 frames, as the ability of human vision system to track multiple objects is limited [START_REF] Zenon | Tracking multiple independent targets: Evidence for a parallel tracking mechanism*[END_REF].

• each observer (graduate-level student majored in computer science) is not instructed nor has prior knowledge by watching the video before tracking.

We illustrate the process in Fig. 7.5, which presents the ground-truth generation and the sub-videos' annotation result in 3D. More precisely, 9 subvideos are randomly chosen out of 16 extracted from the original sequence. The parameters of each subvideo are provided in Table 1. In average, each subvideo has a cumulative number of 9587 colloids (adding all colloids in all frames, i.e. without any identification of identical colloids across frames) and 268 trajectories. In total, we have labeled 2408 meaningful trajectories extracted from a cumulative number of 86287 colloids recovered from 9 different videos by 9 different observers.

Evaluation Metrics

In this paper, following common practice (e.g. [START_REF] Bibliography | Stable multi-target tracking in real-time surveillance video[END_REF]Reid, 2011][Berclaz et al., 2011]), our results are evaluated using the standard CLEAR MOT metrics [START_REF] Keni | Evaluating multiple object tracking performance: the clear mot metrics[END_REF], listed as follows:

• The multiple object tracking Precision (MOTP): the ratio of the number of track switches over the number of objects present in all frames,

M OT P = i,t d i t t c t (7.10)
where c t is the number of matches found for time t. For each of theses matches, d i t is the distance between the object o i and its corresponding hypothesis.

• The Mismatch ratio (MM): the ratio of the number of track switches over the number of objects present in all frames, mme = t mme t t g t (7.11) The quantitative results of detection are presented in Table 7.2, which shows that our method gain more accuracy in terms of MOTP criterion compared with other standard baselines. The visual comparison results are shown in the Fig. 7.6 and Fig.7.7. The adaptive threshold technique and wavelet based method [START_REF] Padfield | Coupled minimum-cost flow cell tracking for high-throughput quantitative analysis[END_REF] can obtain reasonable good segmentation (see in Fig.7.6 (d)) where there aren't cluttered colloids, otherwise they fail to successfully separate the colloids individually (shown in Fig. 7.6 (c) and (g)). The local minimum/maximum finding technique, is prone to be sensitive to noise of the image. Therefore, we set up a threshold in order to cut off non-particle detection (shown in Fig. 7.6 (e) and (f)). The detection generated by method in [START_REF] Ivo | Feature point tracking and trajectory analysis for video imaging in cell biology[END_REF] shows its weakness in detecting objects in low-resolution background, which leads to miss the detections shown in the Fig. 7.7(c) and (d). First we evaluate the influence of the three refinement operations separately as well as their different combinations. In Table 7.3, each type of proposed refinement is proved useful quantitatively, compared to the case without any refinement operation, the performance goes from 94.03% to 94.13%, 94.17%, and 94.23% respectively. Moreover, combining two or all of them further leverages accuracy to 94.45%, which means that the three types of refinements are complementary. We also investigate in Table 7.4 the influence of different orders of refinement operations, and it follows from the results that the order does not affect significantly the final performance. The reason lies in the fact that we perform the three configurations iteratively.

Comparison with standard baselines

To compare systematically, we report results on nine annotated video sequences with five standard baselines: the Kalman's filter [START_REF] Samuel S Blackman | Multiple-target tracking with radar applications[END_REF], Dijkstra's short- Dijkstra, 1959a[START_REF] Jiang | Accurate 3d multi-marker tracking in x-ray cardiac sequences using a two-stage graph modeling approach[END_REF], the Nearest neighbor, the Hungarian [START_REF] Harold W Kuhn | The hungarian method for the assignment problem[END_REF] and the [START_REF] Ivo | Feature point tracking and trajectory analysis for video imaging in cell biology[END_REF]. The first baseline algorithm is the Kalman's filter [START_REF] Samuel S Blackman | Multiple-target tracking with radar applications[END_REF], which recursively estimates the state of a process by minimizing the mean of the squared error. The Kalman filter model assumes the true state at time t is evolved from the state at (t -1) according to:

x t = A t x t-1 + B t u t + w t (7.13) and at time t an observation (or measurement) z t of the true state x t is made according to: 7.14) where, A t is the state transition model, B t is the control-input model and w t is the process noise, which is assumed to be drawn from a zero mean multivariate normal distribution with covariance Q, w t ∼ N (0, Q), and H t is the observation model, v t is the observation noise, v t ∼ N (0, R). In the experiment, we

z t = H t x t + v t (
set A t =    
1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 in the purple-colored path). A relatively high number of fragments and identity switches can be observed from the method proposed by [START_REF] Jiang | Accurate 3d multi-marker tracking in x-ray cardiac sequences using a two-stage graph modeling approach[END_REF] shown in Fig. 7.10 at the same time, leaving colloids tend to link with entering colloids, which leads to very long-range paths (e.g. the red, blue and green ones). These one-pass greedy algorithms do not work well when there is target interaction in a scene. In contrast, the nearest neighbor, the Hungarian algorithm [START_REF] Harold W Kuhn | The hungarian method for the assignment problem[END_REF], and our modified min-cost/max flow algorithm can recover the correct trajectories even in a dense scene as shown in Fig. 7.11, Fig. 7.12 and Fig. 7.14 respectively. One reason for our tracking method is the use of unit capacity constraint for each edge and the global optimization algorithm solved by the modified SSP. Finally, we present visual results of colloids in highly dense context shown in Fig. 7.15. We can observe that our proposed method can detect colloids individually correctly and track them without identity switch even in such highly dense and cluttered video.

Note that the ground-truth videos used in the experiments, as well as the tracking results obtained with either our algorithm or the methods presented in [START_REF] Samuel S Blackman | Multiple-target tracking with radar applications[END_REF][START_REF] Jiang | Accurate 3d multi-marker tracking in x-ray cardiac sequences using a two-stage graph modeling approach[END_REF], are available in a frame-by-frame format at http://math.univ-lyon1.fr/~masnou/colloids.Together with these ground truth videos, we provide the segmentation and tracking result for a video with a middle dense population of colloids.

Code and computational time

In the previous part, extensive experiments were presented to evaluate the efficiency of our method. The segmentation step is implemented as a Matlab routine, and the tracking step combines C++ and matlab implementations. The code is ran on a standard computer (Intel Xeon 3.3GHz CPU with 16G memory). For each subvideo (frame size 256 × 336, 500 frames), the computational time was approximately 28mins for the segmentation, 2s for the graph construction, and 0.5s for the iterated min-cost/max-flow algorithm. Improving the computational burden for segmentation is the purpose of future research.

Conclusion

In this chapter, an efficient and reliable framework has been proposed to detect and track individual colloids in a long-term video sequence. First, all colloids are detected individually by combining a region-based level set method with the circular Hough transform. Then, all meaningful trajectories are recovered from a trellis graph (which iterative refinements) using an iterative optimization algorithm. The min-cost/max flow algorithm guarantees the global optimum at each iteration. The combination of a tag-then-delete method and the successive shortest paths algorithm enables to find all colloids' paths simultaneously with higher accuracy, compared with five state-of-the-art methods, according to MOTA and MM criteria on annotated real videos. [START_REF] Otsu | A threshold selection method from gray-level histograms[END_REF], local maximum detection method, and wavelet based method [START_REF] Padfield | Coupled minimum-cost flow cell tracking for high-throughput quantitative analysis[END_REF] respectively. Chapter 8

Conclusions and Future Work This thesis mainly concentrates on the application of graph theory and develops algorithms based on it to solve two classical computer vision problems: image segmentation and multi-target tracking. In chapter 1, we give a general introduction of the contexts, motivations, objectives, and contributions. In chapter 2, we introduce the basic definitions in graph-theoretical methods and review graph construction algorithms and the graph partitioning methods. In chapter 3, we review the previous work on image segmentation, since the algorithms presented in this dissertation are mainly on this subject. Our main research works presented in the thesis can be divided into three parts. Part 1 (Chapter 4) deals with the graph construction. To combine adaptively the local and global image structure information, we propose a novel graph construction algorithm taking account of nice properties, e.g. spatial consistency, sparsity, long-range grouping cues. Part II (Chapter 5 and 6) focus on the topic of developing powerful and discriminative grouping cues. In chapter 5, to include color and neighborhood structure as well as avoid the over-smooth effect, we propose a new feature descriptor weighted color patch, which is further used to compute the weight of edges in graph construction. In chapter 6, we propose a graph-based unsupervised segmentation approach that combines superpixels, sparse representation, and a new mid-level feature to describe superpixels. Part III (Chapter 7) deals with the multi-target tracking problems in active colloids systems. We propose an efficient and robust framework to jointly detect and track each colloid in a long-term video sequences. We propose a graph-based unsupervised segmentation approach that combines superpixels, sparse representation, and a new mid-level feature to describe superpixels. We first extract a set of interest points either by sampling or using a local feature detector, and we compute a set of low-level features associated with the patches centered at the interest points. A low-level dictionary is defined as the collection of all these low-level features. We call superpixel a region of an oversegmented image obtained from the input image, and we compute the low-level features associated with it. Then we compute for each superpixel a mid-level feature defined as the sparse coding of its low-level features in the aforementioned dictionary. These mid-level features not only carry the same information as the initial low-level features, but also carry additional contextual cue. We use the superpixels at several segmentation scales, their associated mid-level features, and the sparse representation coefficients to build graphs at several scales. Merging these graphs leads to a bipartite graph that can be partitioned using the Transfer Cut algorithm. 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.

Active Colloids Tracking: Recover Trajectories Globally via Min-cost/max Flow

To track massive colloids' trajectories independently for the study of the active suspension system, we propose a new detect-then-track method. First, a region based level set method is adopted to segment all colloids from long-term video sequences. Moreover, the circular hough transform further refines the segmentation to obtain colloid individually. Second, we propose to recover all the colloids' trajectories simultaneously, which is a global optimal problem and can be solved efficiently with the min-cost/max flow. A high-quality graph construction strategy guarantees the final tracking result. We first construct an initial graph using simple yet effective measurement such as colloid displacement, and further resolve local conflicts introduced by the unambiguity of initial graph with additional constraints. A modification of min-cost/max flow algorithm combined with iterative tag-then-delete is proposed to recover all colloids' trajectories simultaneously. Finally, we evaluate the proposed framework on a real benchmark with annotations. Extensive experiments demonstrate that the proposed framework outperforms standard state-of-the-art methods with large margin measured by CLEAR MOT.

8.2 Perspectives for Future Work

Image Segmentation

Image segmentation has been a fundamentally studied topic and continues to attract intensive interest in computer vision. After a short period time, when part of the recognition community lost confidence in bottom-up segmentation for its ill-posed property, it becomes a major trend to apply the results of bottom-up segmentation as a first step in many high-level vision tasks. These methods provide high-quality and category-independent object candidates, which can then be described with richer representations and used as input to more sophisticated learning methods. Recently, this paradigm has dominated the PASCAL segmentation challenge [START_REF] Carreira | Constrained parametric min-cuts for automatic object segmentation[END_REF]] [Carreira et al., 2012a[START_REF] Bibliography | Semantic segmentation using regions and parts[END_REF], leveraged object detection [START_REF] Alexe | Classcut for unsupervised class segmentation[END_REF][START_REF] Jrr Uijlings | Selective search for object recognition[END_REF]] [Girshick et al., 2013[START_REF] Wang | Regionlets for generic object detection[END_REF][START_REF] Manen | Prime object proposals with randomized prim's algorithm[END_REF] and demonstrated competitive in large-scale classification [START_REF] Jrr Uijlings | Selective search for object recognition[END_REF].

Graph based methods build the basis of many state-of-the-art methods in image and video segmentation. These methods gain popularity for well-sound mathematical structure and efficient discrete optimization techniques as well as the flexible data representation ability. As consequence, methods using graph have been a dominant paradigm to generate state-of-the-art performance on popular benchmark dataset. We present possible extensions and future directions.

Multiple Cues Combination

For general-purpose segmentation, it is insufficient to use a single feature to describe all type of image perceptual properties. At the same time, various feature descriptors are proposed in literature possessing different advantages in color, gradient or texture etc. Consequently, optimizing multiple grouping cues in the same framework is an essentially interesting area in bottom-up segmentation. For graph oriented methods, the affinity graph plays essentially important role for the quality of result by graph partitioning technique. A good combination of different features can improve the accuracy due to its ability of capturing key perceptual grouping property.

It will be a very valuable research if one can design a general and fair comparison framework to comprehensively understand the performance of various feature descriptors based on graph weight computation. As a preliminary extension, based on the idea presented in [START_REF] Wang | A graph-cut approach to image segmentation using an affinity graph based on l0-sparse representation of features[END_REF], we investigate various feature descriptors including color, texture, and other appearance cues. Several works have been proposed toward this direction also. For instance, in the global probability boundary (gPb) [START_REF] Arbelaez | Contour detection and hierarchical image segmentation[END_REF] algorithm, brightness, color and texture gradients at three fixed disk sizes are first computed. These local contour cues are globalized using spectral graph-partitioning, resulting in the gPb contour detector as state-ofthe-art in BSDS. Cheng et al.[Cheng et al., 2011a] proposed a new solution to fuse multiple types of image features by seeking the sparsity-consistent low-rank affinities from the joint decompositions of multiple feature matrices into pairs of sparse and low-rank matrices.

Multi-scale Segmentations Combination

Multi-scale Segmentation have been frequently considered in order to design a robust and general framework. Combining scales from coarse to fine is a powerful processing strategy in computer vision, as a single hierarchy is not enough to get a sufficiently diverse set of regions but by using several ones can capture different meaningful object candidates. One example is the winner [START_REF] Jrr Uijlings | Selective search for object recognition[END_REF] in the localization task of the ImageNet Large-Scale Visual Recognition Challenge 2011, it use several over-segmentations computed in several color spaces and obtain high recall which is a critical index for the object detection task. [START_REF] Bibliography | Semantic segmentation using regions and parts[END_REF] considered hierarchical segmentations at three different scales and combining pairs and triplets of adjacent regions from the two coarser scales to produce object region. [START_REF] Arbeláez | Multiscale combinatorial grouping[END_REF] proposed a hierarchical segmenter that leverages multiscale information and produces accurate object candidates by efficiently exploring the combinatorial space of our multiscale regions. For graph oriented methods, graph partitioning technique provides a natural globalization of the combination of multi-scale affinity graph, e.g. [START_REF] Cour | Spectral segmentation with multiscale graph decomposition[END_REF]] [Kim et al., 2010b]. It is worth to mention that varying parameters of candidate oversegmentation methods can also obtain multi-scale superpixels, which are further used as mid-level grouping unites either in graph cut framework [START_REF] Li | Segmentation using superpixels: A bipartite graph partitioning approach[END_REF] or conditional random field framework [Liu et al., 2013b], both being mathematical model to integrate the spatial coherency and across-scale consistency of multi-scale superpixels.

Multiple Algorithms Combination

Recently, the paradigm which treats bottom-up segmentation as input to more sophisticated task, e.g. object detection, has dominated the PASCAL challenges on segmentation and object detection [Carreira et al., 2012a][Carreira and Sminchisescu, 2012[START_REF] Fidler | Bottom-up segmentation for top-down detection[END_REF] and it has been also proved very competitive in largescale classification [START_REF] Jrr Uijlings | Selective search for object recognition[END_REF]. Motivated by potential fail of only one segmentation method, which may often lead to degrade performance substantially, several works have pointed out "some segments in some of the segmentations appear to provide good spatial support objects" [START_REF] Malisiewicz | Improving spatial support for objects via multiple segmentations[END_REF]. For example, [START_REF] Hoiem | Geometric context from a single image[END_REF][START_REF] Bryan C Russell | Using multiple segmentations to discover objects and their extent in image collections[END_REF] used multiple segmentations from an image, and treated them as hypotheses for object support rather than a single partitioning of the image for recognition and detection. [START_REF] Malisiewicz | Improving spatial support for objects via multiple segmentations[END_REF] took one of the first steps towards combinatorial grouping, by running multiple segmenters with different parameters and merging up to three adjacent regions. As a preliminary extension, we proposed in [Wang et al., 2013b[START_REF] Wang | A graph-cut approach to image segmentation using an affinity graph based on l0-sparse representation of features[END_REF] to construct an unified affinity graph by concatenating 5 to 6 scale of superpixels generated by MS [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF] and FH [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF]] into an unified matrix diagonally.

Multi-target Tracking

Multi-target tracking is one of the most challenging problems in computer vision. Although much progress has been made in the last several years, it is still far from solved. Tracking-by-detection paradigm is frequently used to this task, these methods tend to be more robust as they can access all observations simultaneously. Many algorithms are proposed to solve the tracking problem in specific domain, and therefore algorithms can be very varied according to the track target. Nevertheless, we can point out some further improvement based on our observation in our preliminary work in Chapter 7. First of all, as its name tells, the tracking result surely benefits from further advances in object detection which is largely an independent research area and is really ad-hoc. Some assumption can be learned from colloid' s properties and motion mechanism throughout the whole video sequences. For example, the prior knowledge round-shaped target can be further considered in the stage of segmenting (e.g. imposing as shape prior in the active contour model's energy function [START_REF] Chan | Level set based shape prior segmentation[END_REF]), and the smooth change in terms of mean gray level of colloids can indicate the motion towards the third direction, which can be a useful hint to detect the target even in severe inhomogeneous condition. Another improvement can be made in the efficiency of level set formation. For example, the convex formulations of ε RSF (C, f 1 , f 2 ) in Chapter 7, in the spirit of [START_REF] Chan | Algorithms for finding global minimizers of image segmentation and denoising models[END_REF][START_REF] Pock | A convex formulation of continuous multi-label problems[END_REF] could be used, and would decrease the computational time. Second, recovering trajectories from video sequences is in fact a combinatorial optimization problem of significant complexity. There exists many proposals to solve this problem, e.g. Hungarian algorithm [START_REF] Harold W Kuhn | The hungarian method for the assignment problem[END_REF] and k-shortest paths [START_REF] Berclaz | Multiple object tracking using k-shortest paths optimization[END_REF]. More recent methods [Zhang et al., 2008b[START_REF] Berclaz | Multiple object tracking using k-shortest paths optimization[END_REF] have attempted to find globally optimal solutions across the entire sequence by creating network flow graphs, which can be solved optimally and efficiently by min-cost/max flow algorithms. In Chapter7, we also treat the tracking task as the min-cost/max flow problem. A further improvement can be made by considering integrating higher-order track smoothness constraints such as constant velocity. Although additional constrain to the original binary flow variables in the network graph leads to a problem, which cannot be solved by min-cost flow any more, [Butt and Collins, 2013b] proposed an iterative solution method that relaxes these extra constraints using Lagrangian relaxation, resulting in a series of problems that are solvable by min-cost flow.

Table A.2: Class-level localization accuracy (in %) for the VOC07-6×2 dataset for our method vs. [START_REF] Deselaers | Localizing objects while learning their appearance[END_REF][START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF][START_REF] Siva | In defence of negative mining for annotating weakly labelled data[END_REF].

Initialization ours [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF] [ [START_REF] Siva | In defence of negative mining for annotating weakly labelled data[END_REF]

  Comparison of segmentation result: (a) The original image. (b)-(c)

  applied in images obtained from Internet search. Note that no objects are discovered for noisy images. . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.10 Illustration of bottom-up semantic segmentation framework in paper Zou et al. [2012] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.11 Illustration of semantic segmentation on PASCAL VOC 2012 test dateset by the method in [Xia et al.]. Different colors correspond to different object classes and the boundaries are colored in white. . . . 52 xiv List of Figures 4.1 Illustration of the gravitation law in perceptual grouping: (a) leopard running on the ground, (b)-(d) are superpixels of 3 different scales by Mean Shift (MS) by oversegmenting (a) using 3 parameter settings, and (e)-(f) superpixels of 2 other different scales by Felzenszwalb-Huttenlocher (FH). Superpixels are divided into small, medium and large sized sets colored in yellow, green and blue, respectively. (g) and (h) are segmented result by SAS and the proposed GL-graph with a number of segments k = 4 and k = 2 respectively. . . . . . . . 4.2 The framework of our proposed graph-cut approach for image segmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Multi-scale superpixels generation and representation with multiple features: each superpixel can be described by feature vectors, as color (mean value in L*a*b, mlab, color histogram in RGB (CH), texture (Local Binary Pattern, LBP), and gradient appearance cue (Bag-of-Words) with SIFT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Illustration of the adaptive threshold selection of large regions. . . .

4. 7

 7 The performance comparison of the GL-graph with other graphs on different features (mlab, CH and LBP ) on Berkeley Segmentation Database I: for each feature, graphs are compared by the average score over each number of segments from 2 to 40 by the four metrics PRI, VoI, GCE and BDE simultaneously. . . . . . . . . . . . . . . . 4.8 The performance comparison of the GL-graph with other graphs on different features on Berkeley Segmentation Database II: for each feature, graphs are compared by the average score over each number of segments from 2 to 40 by the four metrics PRI, VoI, GCE and BDE simultaneously. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv List of Figures

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5.1 An illustration of the local weights calculation of a patch extracted from the boundary region in a natural image (the first column shows the gray values, the second column is the mean-square deviation of each pixel, and the last column shows the weights assigned to each pixel). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 5.2 An illustration of the effectiveness of the global weights in a synthetic image. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 5.3 Visual comparison of our results with other methods on the Prague benchmark (examples presented in row-wise, from up to down, are respectively the original images, ground truth maps, EDISON, JSEG, SWA, GL-graph presented in Chapter 4 and our results WCP). . . . 86 5.4 Visual comparison of our results with other methods on the Berkeley database (examples presented in column-wise, from left to right, are respectively the original images, NCut, GBIS and our results). . . . . 88 5.5 Some examples segmented by our method on the Berkeley database. 89 6.1 Illustration of different types of interest points. . . . . . . . . . . . . 95 6.2 Illustration of low-level features computation. . . . . . . . . . . . . . 95 6.3 Illustration of mid-level features computation. . . . . . . . . . . . . . 96 6.4 Examples of segmented results on the MRSC dataset (for each experiment, we show the segmentation result, and the segmentation superimposed with the original image). . . . . . . . . . . . . . . . . . 100 7.1 Illustration of dynamical-clustering of self-propelled colloidal particles at different stages: (a) illustrates temporal evolution at low densities; (b) and (c) show the cluster grow stably, and (d) presents the final stage of the system. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 xvi List of Figures 7.2 Illustration of active colloid detection. In light-blue block: (a) a video frame with highly dense colloids; (b) result segmented only by level set [Li et al., 2008]; (c) result detected with Gaussian smoothing and circular Hough transform; and (d) result obtained by the combination of level set and circular Hough transform. In light-purple block: (e) zoom in version of the yellow rectangle shown in (a); and (f-h) are the zoom-in results corresponding to (b-d) respectively. . . . . . . . 7.3 Illustration of local confliction in the initial graph. Left: temporal trajectories in different color among three consecutive frames recovered from the initial graph with min-cut/max flow algorithm. Right: the graph connection between two frames f k-1 and f k . Note that dot in black represent the current node and its corresponding neighbors in next frame is dot in white. The dash line means the nodes should be considered connected and the × in red means the connection should be removed. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4 Illustration of our tracking scheme by iteratively finding the min-cost

7 . 5

 75 Illustration of ground-truth. (a) 9 subvideos (out of 16) extracted from the original large scale video; (b) Stack of frames in subvideo #1 annotated by human observers; (c) 3D visualization of a few trajectories tracked by observers in subvideo #1. . . . . . . . . . . . . . . 7.6 Visual comparison of different particle detection methods. (a, b)

1 IntroductionContents 1 . 1

 111 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.10 Illustration of cluttered colloid's tracking: Dijkstra shortest path used in [Jiang et al., 2013]. . . . . . . . . . . . . . . . . . . . . . . . . . . 7.11 Illustration of cluttered colloid's tracking: Nearest neighbor linking. 7.12 Illustration of cluttered colloid's tracking: Hungarian algorithm [Kuhn, 1955]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.13 Illustration of cluttered colloid's tracking: track algorithm proposed in [Sbalzarini and Koumoutsakos, 2005] . . . . . . . . . . . . . . . . 7.14 Illustration of cluttered colloid's tracking: our proposed method. . . 7.15 Illustration of results of colloids detection and tracking in highly dense video. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii List of Figures A.1 Illustration of our proposed method to extract the initial object estimation: for an input image (a), 1000 object proposals (b) are sampled with corresponding scores to their probability to have object inside via the objectness measurement. (c) is the saliency map derived from (b), and (d) is the reference region obtained by thresholding (c). A finer set of candidate windows (f) are selected on the sorted proposals (e) by NMS. The blue window in (g) is our initial object estimation obtained by optimizing the overlap between (d) and (f). . . . . . . . 138 A.2 Examples of bounding box enlarging and shrinking. Boxes before and Chapter Computer Vision . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.

Figure 1 . 1 :

 11 Figure 1.1: Illustration of components consist of a computer vision system.

Figure 1 . 2 :

 12 Figure 1.2: Illustration of various image segmentation applications.

Figure 1 . 3 :

 13 Figure 1.3: Illustration of successful segmentations using low-level perceptual grouping criteria.

Figure 1 . 4 :

 14 Figure 1.4: Illustration of the difficulty of low-level segmentation. SAS is the method presented in[START_REF] Li | Segmentation using superpixels: A bipartite graph partitioning approach[END_REF]

Figure 1 . 5 :

 15 Figure 1.5: Illustration of application examples for multi-target tracking.

Chapter 2 .

 2 Graph based Methods(a) ε-graph (b) kNN graph

Figure 2 . 1 :

 21 Figure 2.1: Illustration of two classical pairwise graphs. The dark point is current data, and data in different color form different clusters.

Figure 2 . 2 :

 22 Figure 2.2: What kind of feature descriptor should we use for constructing the affinities.

Fig. 2 .

 2 2(a) prefers the texture feature descriptor, whilst Fig.2.2(b) can use color or contour information.

Figure 2 . 3 :

 23 Figure 2.3: Left: the original image. Middle: part of the image marked by the box.The intensity values at pixels p 1 , p 2 and p 3 are similar. However, there is a contour in the middle, which suggests that p 1 and p 2 belong to one group while p 3 belongs to another. Just comparing intensity values at these three locations will mistakenly suggest that they belong to the same group. Right: orientation energy. Somewhere along l 2 , the orientation energy is strong which correctly proposes that p 1 and p 3 belong to two different partitions, while orientation energy along l 1 is weak throughout, which will support the hypothesis that p 1 and p 2 belong to the same group[START_REF] Malik | Contour and texture analysis for image segmentation[END_REF]

Figure 2 . 4 :

 24 Figure 2.4: Multiscale graph compression

Fig. 2 .

 2 Figure 2.5: (a) Polka-dot image is convolved with a bank of filters. (b) Textons found via K-means with K = 25, sorted in decreasing order by norm. (c) Mapping of pixels to the texton channels. The dominant structures captured by the textons are translated versions of the dark spots. [Malik et al., 2001].

Figure 2 . 6 :

 26 Figure 2.6: Multi-layer graph model[Kim et al., 2010b]. In (a), the graph nodes V * consist of pixels V and regions V (l) l=1,...,L , generated by varying the parameters of the mean shift algorithm[START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF]]. An undirected edge E * represents the relation between a pair of nodes. (b) and (c) show the examples of edges (violet lines) connected to one region and to one pixel, respectively.

Chapter 2 .

 2 Figure 2.7: The proposed bipartite graph model with K over-segmentations of an image. A black dot denotes a pixel while a red square denotes a superpixel[START_REF] Li | Segmentation using superpixels: A bipartite graph partitioning approach[END_REF].

Figure 2 . 8 :

 28 Figure 2.8: Illustration of spectral methods for image segmentation.

  (a) Input mesh (b) Partition of the mesh with 42 cut edges

Figure 2 . 9 :

 29 Figure 2.9: Illustration of the geometric partitioning method [Gilbert et al., 1998].

Figure 2 .

 2 Figure 2.10: The various phases of the multilevel graph bisection. During the coarsening phase, the size of the graph is successively decreased; during the initial partitioning phase, a bisection of the smaller graph is computed; and during the uncoarsening phase, the bisection is successively refined as it is projected to the larger graphs. During the uncoarsening phase the light lines indicate projected partitions, and dark lines indicate partitions that were produced after refinement.

  : histogram shaped-based method, clustering-based method[START_REF] Hamid R Tizhoosh | Image thresholding using type ii fuzzy sets[END_REF], entropy-based methods[START_REF] As Abutaleb | Automatic thresholding of gray-level pictures using 2-d entropy[END_REF], spatial methods[Wang et al., 2008c] and local methods. It is worth to mention that early methods for image thresholding were basically devised to separate classes that are unimodal and lies in the assumption that class data are Gaussian. Recently, researchers have used other distribution types to provide better image thresholding methods by modeling histogram classes using, for instance, Poisson, generalized Gaussian, skew-normal and Rayleigh distributions. Another parallel trend is using mixture methods for segmentation, where data are clustered to classes determined by the components of a learned mixture model. For instance,[START_REF] Boulmerka | A generalized multiclass histogram thresholding approach based on mixture modelling[END_REF] propose a thresholding method by modeling non-Gaussian and multi-modal class-conditional distributions using mixtures of generalized Gaussian distributions.

Figure 3 . 1 :

 31 Figure 3.1: Illustration of thresholding result with the Otsu method[START_REF] Otsu | A threshold selection method from gray-level histograms[END_REF].

Figure 3 . 2 :

 32 Figure 3.2: Hierarchical segmentation from contours [Arbelaez et al., 2011] . Top Left:Original image. Top Middle: Maximal response of contour detector gPb over orientations.Top Right: Weighted contours resulting from the Oriented Watershed Transform -Ultrametric Contour Map algorithm using gPb as input. Bottom: Contours and corresponding segmentations obtained by thresholding the UCM at levels 0.1(left), and 0.5 (right), with segments represented by their mean color.

Figure 3 . 3 :

 33 Figure 3.3: A taxonomy of clustering algorithm [[START_REF] Anil K Jain | Data clustering: a review[END_REF]

Fig. 3 .

 3 4 present the perceptual comparison of several popular mode seeking methods, i.e. mean shift, quick shift as well as the convex shift.

Figure 3 . 4 :

 34 Figure 3.4: Comparison of segmentation result: (a) The original image. (b)-(c) Segmentation generated by mean shift[START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF], quick shift[START_REF] Vedaldi | Quick shift and kernel methods for mode seeking[END_REF] and convex shift[START_REF] Yu | Bag of textons for image segmentation via soft clustering and convex shift[END_REF].

Figure 3 . 5 :

 35 Figure 3.5: Illustration of the segmentation result by MST based algorithm, FH[START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF].

Figure 3 . 6 :

 36 Figure 3.6: (a), (f), (k) Watershed initialization of nuclei and lymphocytes on prostate and breast cancer histopathology with corresponding segmentation results obtained via GAC [Caselles et al., 1997] (b), (g), (l); Method in [Ali and Madabhushi, 2012] (c), (h), (m); magnified region (d), (i), (n) from (b), (g), (l); magnified region (e), (j), (o) from (c), (h) and (m)

Figure 3 . 8 :

 38 Figure 3.8: Illustration of cosegmentation[START_REF] Rother | Cosegmentation of image pairs by histogram matching-incorporating a global constraint into mrfs[END_REF]: given a pair of images, the task is to segment the common part in both images. Compared to GrabCut[START_REF] Rother | Grabcut: Interactive foreground extraction using iterated graph cuts[END_REF], which segment the foreground individually, cosegmentation outperforms traditional foreground/background method.

9 .

 9 These methods aim to handle multiple object classes. In particular, Kim and Xing 2012 explicitly handled this challenge by foreground segmentation(with/without user input label) and region assignment. Joulin et al. 2012 implicitly handled multiple object classes with non-convex energy function which combines spectral-and discriminative-clustering. Ma and Latecki 2013 solved this problem based on graph transduction semi-supervised learning. Rubinstein et al. 2013 further extended the cosegmentation to discover object in internet images, and can handle noisy images which do not contain common object of interest, with constructing a large-scale graphical model.

Figure 3 . 9 :

 39 Figure3.9: Illustration of cosegmentation[START_REF] Rubinstein | Unsupervised joint object discovery and segmentation in internet images[END_REF] applied in images obtained from Internet search. Note that no objects are discovered for noisy images.

Figure 3 . 11 :

 311 Figure 3.11: Illustration of semantic segmentation on PASCAL VOC 2012 test dateset by the method in [Xia et al.]. Different colors correspond to different object classes and the boundaries are colored in white.

Figure 4 . 1 :

 41 Figure 4.1: Illustration of the gravitation law in perceptual grouping: (a) leopard running on the ground, (b)-(d) are superpixels of 3 different scales by Mean Shift (MS) by oversegmenting (a) using 3 parameter settings, and (e)-(f) superpixels of 2 other different scales by Felzenszwalb-Huttenlocher (FH). Superpixels are divided into small, medium and large sized sets colored in yellow, green and blue, respectively. (g) and (h) are segmented result by SAS and the proposed GL-graph with a number of segments k = 4 and k = 2 respectively.

Figure 4 . 2 :

 42 Figure 4.2: The framework of our proposed graph-cut approach for image segmentation

  in the sequel. Then, to obtain a discriminative affinity graph, we compute for each superpixel various visual features. While any kind of region-based feature could be used, we evaluate the discriminating power of three perceptual visual features, namely color, texture and shape, which play a major role in human vision-based segmentation [Toni P.Saarela, 2012][M.Peterson and B.Gibson., 1993]. Specifically, in this work, color feature is characterized using mean value in the L*a*b space (mLab) and Color Histogram (CH) in the RGB space, texture through Local Binary Pattern (LBP ) while shape cues using SIFT based bag-of-visual-words (BoW )[START_REF] Lowe | Object recognition from local scale-invariant features[END_REF]][Cheng et al., 2011a] as shown in Fig.4.3. Unlike RGB, Lab color space is designed to approximate human vision and its L component closely matches human perception of lightness. Local Binary Patterns (LBP ) are reputed to encode micro-texture and robust to monotone light changes.

Figure 4 . 3 :

 43 Figure 4.3: Multi-scale superpixels generation and representation with multiple features: each superpixel can be described by feature vectors, as color (mean value in L*a*b, mlab, color histogram in RGB (CH), texture (Local Binary Pattern, LBP), and gradient appearance cue (Bag-of-Words) with SIFT.

Figure 4 . 4 :

 44 Figure 4.4: Illustration of the adaptive threshold selection of large regions.

  5 611 = 0.0081 Additionally, the unbalanced structure of the constructed bipartite graph GB = {U, V, B} makes the graph further sparser. The final bipartite graph has the size |U| = |V| + |I| = (154401 + 611) > |I| = 481 × 321 = 154401 .

Figure 4 . 6 :

 46 Figure 4.6: Illustration of the construction of an unbalanced bipartite graph over multi-scale over-segmentations: a yellow dot denotes a pixel, and a white dot denotes a superpixel. The blue lines show that each pixel is only connected to its corresponding superpixel in each scale of over-segmentations which is represented as a pixel-superpixel affinity matrix (upper block matrix), while the yellow lines show undirected edges representing the relationships between two superpixels, represented by a superpixel-superpixel affinity matrix (lower block matrix).

Figure 4 . 7 :

 47 Figure 4.7: The performance comparison of the GL-graph with other graphs on different features (mlab, CH and LBP ) on Berkeley Segmentation Database I: for each feature, graphs are compared by the average score over each number of segments from 2 to 40 by the four metrics PRI, VoI, GCE and BDE simultaneously.

Figure 4 . 8 :

 48 Figure 4.8: The performance comparison of the GL-graph with other graphs on different features on Berkeley Segmentation Database II: for each feature, graphs are compared by the average score over each number of segments from 2 to 40 by the four metrics PRI, VoI, GCE and BDE simultaneously.

Figure 4 . 9 :

 49 Figure 4.9: Visual comparison of the results obtained with the GL-graph and with other graphs. Each line from top to bottom corresponds to the segmentation result obtained with the following graphs: adjacency, kN N , 1 , LRR, and the proposed GL-graph. From left to right, the results for various choices of k = 2, 3, 4, 5. . Note that the result is segmented using the most appropriate feature for each kind of graph according to Table I, e.g. we use the feature mlab for the adjacency-graph and the KN N -graph. 78

Figure 4 .

 4 Figure 4.10: Visual comparison with SAS. For each experiment, the second image shows the results of SAS, and the third image is obtained with our method. Our results require significantly less tuning for k and are visually better in general, in particular often more accurate.

Figure

  Figure 4.11: Visual segmentation examples by the proposed method: all images are segmented into 2 regions (k=2). Note that the salient objects or parts can be segmented accurately, such as the plane, boat, flower with insects, elephants, hill. Even multiple objects with large inner color variation can be segmented correctly, as the cactus flowers or the men in water.

Figure 5 . 1 :

 51 Figure 5.1: An illustration of the local weights calculation of a patch extracted from the boundary region in a natural image (the first column shows the gray values, the second column is the mean-square deviation of each pixel, and the last column shows the weights assigned to each pixel).

Figure 5 . 2 :

 52 Figure 5.2: An illustration of the effectiveness of the global weights in a synthetic image.

Figure 5 . 3 :

 53 Figure 5.3: Visual comparison of our results with other methods on the Prague benchmark (examples presented in row-wise, from up to down, are respectively the original images, ground truth maps, EDISON, JSEG, SWA, GL-graph presented in Chapter 4 and our results WCP).

Figure 5 . 4 :

 54 Figure 5.4: Visual comparison of our results with other methods on the Berkeley database (examples presented in column-wise, from left to right, are respectively the original images, NCut, GBIS and our results).

0

  Figure 6.1: Illustration of different types of interest points.

Figure 6 . 2 :

 62 Figure 6.2: Illustration of low-level features computation.

  6.3 for an illustration of the whole process. More precisely, given a superpixel, suppose x ∈ R m is the low-level feature associated with it, and let D = [d 1 • • • d n ] ∈ R m×n be the low-level dictionary built in section 6.2.1. The sparse representation of x in D is obtained by solving the following optimization problem: min α ||x -Dα|| 2 2 s.t. ||α|| 0 ≤ L, (6.1)

Figure 7 . 1 :

 71 Figure 7.1: Illustration of dynamical-clustering of self-propelled colloidal particles at different stages: (a) illustrates temporal evolution at low densities; (b) and (c) show the cluster grow stably, and (d) presents the final stage of the system.

  Fig.7.1(b) and (c) show that the cluster size increases approximately linearly, as observed by Buttinoni

Figure 7 . 2 :

 72 Figure 7.2: Illustration of active colloid detection. In light-blue block: (a) a video frame with highly dense colloids; (b) result segmented only by level set [Li et al., 2008]; (c) result detected with Gaussian smoothing and circular Hough transform; and (d) result obtained by the combination of level set and circular Hough transform. In light-purple block: (e) zoom in version of the yellow rectangle shown in (a); and (f-h) are the zoom-in results corresponding to (b-d) respectively.

4 :

 4 Fig.7.2 shows our motivation and the result of active colloids detection. It is obvious to observe that Fig.7.2 (a) is a difficult image for the task of segmenting individual tiny colloids from poor illumination condition and large clusters. As we can see, Fig.7.2 (b) (c) illustrate that RSF and CHT fail to detect objects when used individually. The 107 Chapter 7. Active Colloids Segmentation and Tracking Algorithm Active colloids detection 1: for i = 1 : N do 2:

Figure 7 . 3 :

 73 Figure 7.3: Illustration of local confliction in the initial graph. Left: temporal trajectories in different color among three consecutive frames recovered from the initial graph with min-cut/max flow algorithm. Right: the graph connection between two frames f k-1 and f k . Note that dot in black represent the current node and its corresponding neighbors in next frame is dot in white. The dash line means the nodes should be considered connected and the × in red means the connection should be removed.

Figure 7 . 4 : 6 :

 746 Figure 7.4: Illustration of our tracking scheme by iteratively finding the min-cost path with SSP and tag-then-delete procedure. In (a), the bold blue edges are part of an optimal path found by the SSP among all edges (edges in blue and yellow); in (b), the dash edges in blue and some edges in yellow are tagged and deleted, some new edges in orange are added to connect the node directly with dummy nodes

  ∀u ∈ V , computer the shortest distance d(u) from s, by Dijkstra s algorithm with cost ω

Figure 7 . 5 :

 75 Figure 7.5: Illustration of ground-truth. (a) 9 subvideos (out of 16) extracted from the original large scale video; (b) Stack of frames in subvideo #1 annotated by human observers; (c) 3D visualization of a few trajectories tracked by observers in subvideo #1.

Figure 7 . 6 :

 76 Figure 7.6: Visual comparison of different particle detection methods. (a, b) show two original video frames. (c, d), (e, f), (g, h) are the result obtained by the Otsu's threshold[START_REF] Otsu | A threshold selection method from gray-level histograms[END_REF], local maximum detection method, and wavelet based method[START_REF] Padfield | Coupled minimum-cost flow cell tracking for high-throughput quantitative analysis[END_REF] respectively. 124

Figure 7 . 7 :

 77 Figure 7.7: Visual comparison of different particle detection methods. (a, b) show two original video frames. (c, d), (e, f) are the result obtained by the method proposed in [Sbalzarini and Koumoutsakos, 2005] and our method respectively.

Figure 7 . 8 :

 78 Figure 7.8: Illustration of cluttered colloid's tracking: ground truth.

Figure 7 . 9 :

 79 Figure 7.9: Illustration of cluttered colloid's tracking: Kalman filter[START_REF] Samuel S Blackman | Multiple-target tracking with radar applications[END_REF].

Figure 7 .

 7 Figure 7.10: Illustration of cluttered colloid's tracking: Dijkstra shortest path used in [Jiang et al., 2013].

Figure 7 . 11 :

 711 Figure 7.11: Illustration of cluttered colloid's tracking: Nearest neighbor linking.

Figure 7 .

 7 Figure 7.12: Illustration of cluttered colloid's tracking: Hungarian algorithm [Kuhn, 1955].

F=1F=20Figure 7 . 13 :Figure 7 .

 7137 Figure 7.13: Illustration of cluttered colloid's tracking: track algorithm proposed in [Sbalzarini and[START_REF] Ivo | Feature point tracking and trajectory analysis for video imaging in cell biology[END_REF]

Figure 7 .

 7 Figure 7.15: Illustration of results of colloids detection and tracking in highly dense video.

8. 1 . 3

 13 Sparse Coding and Mid-Level Superpixel-Feature for 0 -Graph Based Unsupervised Image Segmentation

  1.1 Illustration of components consist of a computer vision system. . . . 2 1.2 Illustration of various image segmentation applications. . . . . . . . 3 1.3 Illustration of successful segmentations using low-level perceptual grouping criteria. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Illustration of the difficulty of low-level segmentation. SAS is the method presented in Li et al. [2012] . . . . . . . . . . . . . . . . . . . 4 1.5 Illustration of application examples for multi-target tracking. . . . . 7 2.1 Illustration of two classical pairwise graphs. The dark point is current data, and data in different color form different clusters. . . . . . . . . 19 2.2 What kind of feature descriptor should we use for constructing the affinities. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3 Left: the original image. Middle: part of the image marked by the box.

  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

Table 1 .

 1

		1: Graph applications
	Context	Graph vertices	Graph edges
	communication network telephones, computers	fiber optic cables
	transportation network street intersections, airports highways, airway routes
	hydraulic network	reservoirs, pumping stations piperline
	internet	web pages	hyperlinks
	social relationships	people, actors	friendships, movie casts
	neural network	neurons	synapses
	protein networs	proteins	protein-protein interactions
	image	pixels, regions	pairwise relationship
	1.3 Image Segmentation
	1.3.1 Definition

Image segmentation is a fundamental problem in computer vision. A general definition of image segmentation is to divide an image into meaningful non-overlapping regions, according to some objective criterion, homogeneity in some feature space or separability in some other one for example. Image segmentation is a core research topic since it is a key element in many computer vision tasks, such as medical imaging for computer-aided diagnosis, cell tracking for biological analysis, motion analysis, see various examples in Fig.

1.2.

  Chapter 1. Introduction under certain assumptions, e.g. linear dependency. To relax the linearity constraint, extensions such as the extended Kalman filter or the unscented Kalman filter [Julier and Uhlmann

Table 2 .

 2

1: Superpixel generation methods Method Chapter 2. Graph based Methods

Table 2 .

 2 2: List of popular features used in graph-oriented algorithms. A +/means that the feature is partially recommended, + (-) means that the feature can (cannot) be used in the case of pixel, patch or region.

	Category Feature descriptor Variants		Usage
				Pixel Patch Region
			RGB	+	+	+
		Color	Luv Lab	+ +	+ +	+ +
			HSV	+	+	+
		LBP		-	-	+
			Area	-	-	+
			Perimeter	-	-	+
			Centroid	-	+	+
			Roundness	-	+	+
	Global	Shape	Compactness Eccentricity	--	+ -	+ +
			Orientation	-	-	+
			Convex area	-	-	+
			Minor axes length	-	-	+
			Major axes length	-	-	+
			Inter-region texton similarity	-	+/-	+
			Intra-region texton similarity	-	+/-	+
		Gestalt properties	Inter-region brightness similarity Intra-region brightness similarity	--	+/-+/-	+ +
			Inter-region contour energy	-	+/-	+
			Intra-region contour energy	-	+/-	+
			Harris	-	+/-	+
		Interest point	DoG LoG	--	+/-+/-	+ +
	Local	SIFT	Hessian Gray-SIFT Color-SIFT	---	+/-+ +	+ + +
		HOG		-	+	+
		Bank of filters		-	+	+

  Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

	Chapter 3
	Literature Review: Image
	Segmentation
	Contents
	3.1
	7/4 )	No bias

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

  Table.3.1 presents some examples from the BSD. Note that each image has multiple ground truths annotated by different human observers. The Microsoft Research Cambridge (MSRC) dataset

Table 3 . 1 :

 31 Berkeley Segmentation Dataset

	Image	#1	#2	Human Subjects #3	#4	#5	Boundary

Table 3 . 2

 32

: MSRC-v2 object category image database grass, tree, sky, flower, water, mount building, road, sign, aeroplane, sky cow, sheep,bird, dog, grass, sky... chair, book, bike, cat

  computes the degree to which two segmentations are mutually consistent. Let R(S ground , p i ) ∆ R(S test , p i ) denote the symmetric difference between R(S ground , p i ) (the subregion of S ground containing the pixel p i ) and R(S test , p i ) (the subregion of S test containing the pixel p i ). Let | • | denote set cardinality. The non symmetric local consistency error is defined as: GCE is valued in [0, 1], where the null value indicates of course that both segmentations are equivalent.4. The Boundary Displacement Error (BDE)[START_REF] Freixenet | Yet another survey on image segmentation: Region and boundary information integration[END_REF] measures the average displacement error of boundary pixels between two segmentation results. More precisely, it defines the error of one boundary pixel as the distance between the pixel and its closest boundary pixel in the other image. Denoting d(p i , B 2 ) = min

	and the global consistency error is obtained by symmetrization and averaging:
	GCE(S ground , S test ) =	1 N	min{	i	E(S ground , S test , p i ),	(3.4)
			p∈B 2	p i -p	(3.5)
						(3.3)

E(S ground , S test , p i ) = |R(S ground , p i )∆R(S test , p i )| |R(S ground , p i )| i E(S test , S ground , p i )} the distance of a boundary point p i ∈ B 1 to the boundary set B 2 , and N 1 , N 2 the total number of points in the boundary sets B 1 and B 2 , BDE is defined as:

  Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

			Chapter 4
	A Global/Local Affinity Graph for
	Image Segmentation
	Contents
	4.1
	P =	T P T P + F P	(3.8)
	R =	T P T P + F N	(3.9)

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

  The performances of global graphs are essentially stable with respect to k and such stability is invariant to feature selection. This property is mainly due to the fact that global graphs choose each node's neighbors by searching globally, which enables the constructed graph to capture long-range grouping cue. It is worth mentioning that such property of global graph makes it promising for practical applications in object recognition, image annotation, etc. Note that the family of sparsity-based graphs (e.g. 0 -graph ) has better performance than rank minimization graph (LRR-graph) or 1 -graph. The reason is that in a 0 -graph, each node has very few neighbors, which makes the graph much

	As a
	quantitative example, when k=2, the evaluation scores on the BSD test set for
	mLab are: PRI=0.6097, VoI=2.0647, GCE=0.1211, BDE=41.2471; and using
	BoW 100 one gets PRI=0.7705, VoI=2.3657, GCE= 0.2047, BDE=16.0532.

The reason may lie on the feature's dimension and on the use of global information. Indeed, BoW 100 is encoded from SIFT with K-means into a 100-dimensional histogram. Generally the sensitivity to k decreases as the dimension increases; 2.

Table 4 .

 4 1 where scores with various values of the parameter L are reported; 3. The proposed GL-graph combines local graph and 0 -graph's nice properties. It achieves the best performances in Table 4.1 in comparison with the adjacency-graph and the 0 -graph. As shown in Table 4.2, it is however somewhat sensitive to the parameter L. As for the evaluation of the respective performances of features, it is essentially an open problem. In what follows, we shed light on the performance of seven features on different graphs by comparing the best results according to the maximization of the evaluation measurement PRI shown in Table 4.1, from which we can deduce that: Chapter 4. A Global/Local Affinity Graph for Image Segmentation

Table 4 .

 4 1: Performance validation for the proposed GL-graph and other types of graphs, using various features, on the Berkeley Segmentation Database test set. Four metrics are used: PRI, VoI, GCE and BDE. For each graph, the best performance over features is highlighted. Note that the best performance result is computed by maximizing PRI of each image over all its evaluation results ranging from 2 to 40.

	adjacent-graph	PRI↑	VoI↓	GCE↓	BDE↓	KN N -graph	PRI↑	VoI↓	GCE↓	BDE↓
	mlab	0.8264 1.7537 0.1935 12.7985 mlab	0.8290	2.0732	0.2316	12.1872
	CH	0.8133	1.9811	0.2204	13.9598 CH	0.8016	2.7882	0.3229	14.4206
	CLBP u2	0.8133	1.9811	0.2204	13.9598 CLBP u2	0.8016	2.7882	0.3229	14.4206
	BoW100	0.8106	1.9983	0.2301	14.7859 BoW100	0.7862	3.2387	0.3440	16.1826
	BoW150	0.8112	2.0210	0.2302	14.9699 BoW150	0.7891	3.1858	0.3385	16.2013
	BoW200	0.8104	2.0179	0.2286	14.7858 BoW200	0.7899	3.2239	0.3402	15.3621
	BoW300	0.8113	1.9954	0.2285	14.9503 BoW300	0.7871	3.2063	0.3383	16.1223
	1 -graph	PRI↑	VoI↓	GCE↓	BDE↓	LRR-graph	PRI↑	VoI↓	GCE↓	BDE↓
	mlab	0.8036 2.9053 0.3079 12.7745 mlab	0.8155	1.8788	0.2071	13.7015
	CH	0.7710	2.8919	0.3012	13.5910 CH	0.8153	1.8794	0.2068	13.6949
	CLBP u2	0.7710	2.8919	0.3012	13.5910 CLBP u2	0.8153	1.8794 0.2068	13.6949
	BoW100	0.6963	2.9473	0.3691	19.1577 BoW100	0.8148	1.8809	0.2072	13.6680
	BoW150	0.7009	2.9678	0.3695	19.6824 BoW150	0.8146	1.8864	0.2084	13.7504
	BoW200	0.7046	2.9428	0.3702	24.5510 BoW200	0.8140	1.8838	0.2083	13.7732
	BoW300	0.7096	2.8871	0.3495	23.2067 BoW300	0.8147	1.8901	0.2078	13.6894
	0 -graph	PRI↑	VoI↓	GCE↓	BDE↓	GL-graph	PRI↑	VoI↓	GCE↓	BDE↓
	mlab	0.8141	2.2969	0.2470	12.2632 mlab	0.8230	2.0848	0.2260	11.7124
	CH	0.8185 2.2426 0.2622 12.8445 CH	0.8266	1.9585	0.2204	12.0042
	CLBP u2	0.8152	1.8793	0.2068	13.6948 CLBP u2	0.8266	1.9584	0.2204	12.0043
	BoW100	0.7896	2.7465	0.3057	15.7107 BoW100	0.7970	2.4072	0.2545	15.2672
	BoW150	0.7878	2.7624	0.2994	15.5692 BoW150	0.7959	2.4067	0.2542	14.7353
	BoW200	0.7859	2.7847	0.3050	15.2595 BoW200	0.7991	2.3744	0.2521	15.1711
	BoW300	0.7872	2.7346	0.2968	15.1443 BoW300	0.7997	2.3612	0.2502	15.4163

Table 4 .

 4 2: Quantitative scores for different values of the parameter L for the GLgraph over the Berkeley Segmentation Database test set. considers only the local structure of image, which leads to wrong segmentations (see the results segmented in first row for each image) when the objects cover a large part of the image. 2) the 1 -graph tends to oversegment the image (see third rows for every example in Fig.

	Sparsity (CH) PRI↑	VoI↓	GCE↓ BDE↓
	L=2	0.8213 2.1111 0.2453 13.2554
	L=3	0.8185 2.2426 0.2622 12.8445
	L=4	0.8195 2.2958 0.2645 12.4510
	L=5	0.8177 2.3079 0.2622 12.2648
	L=6	0.8185 2.3086 0.2631 12.8950
	L=7	0.8190 2.2913 0.2624 12.8970
	L=8	0.8185 2.3253 0.2667 12.1963
	adjacent-graph

Table 4 .

 4 3: Quantitative performance of the proposed method (GL-graph) with simple weighted sum fusion scheme.

	Methods	PRI↑	VoI↓	GCE↓	BDE↓
	(LBP 2 + mlab 2 + SIF T 2 ) 0.8332	1.8890	0.1998	10.7904
	(LBP 2 + CH 2 + SIF T 2 )	0.8355	1.8716	0.2048	10.9985
	(0.4LBP+0.6mlab)	0.8355	1.8965	0.1765	10.9157
	(0.4LBP+0.6CH)	0.8363	1.6776 0.1727 11.0456
	(0.4LBP+0.4mlab+0.2SIFT) 0.8368	1.8347	0.1706 10.8552
	(0.4LBP+0.4CH+0.2SIFT)	0.8381	1.8753	0.1741 10.6787
	(0.3LBP+0.5mlab+0.2SIFT) 0.8384	1.8012	0.1934 10.6633
	(0.3LBP+0.5CH+0.2SIFT)	0.8383	1.7927 0.1958	11.4088

Table 4 .

 4 5: Quantitative comparison of the proposed method (GL-graph) with stateof-the-art methods over the Berkeley Segmentation Database.

	Methods	PRI↑	VoI↓	GCE↓	BDE↓
	NCut

  Contents 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

Table 5 .

 5 1: Quantitative comparison of our results with other methods on the Prague benchmark with multiple measurements.

	Metrics		region-based		consistency measure		clustering		-
	Methods	CS↑	OS↓	US↓	ME↓	NE↓ GCE↓	LCE↓	dM↓	dD↓	dVI↓	-
	EDSION	12.68	86.91	0.00	2.48	4.68	3.55	3.44	35.37	16.84	25.65	-
	JSEG	27.47	38.62	5.04	35.00 35.50	18.45	11.64	23.38	15.19	17.37	-
	SWA	27.06	50.21	4.53	25.76 27.50	17.27	11.49	24.20 13.68 17.16	-
	GL-graph 41.42 15.04	12.48 27.64 26.92	20.48	11.25	11.22 17.13	14.40	-
	WCP	30.92	4.12	26.67 37.40 35.72	20.28	14.82	22.27	16.83 13.25	-
	Metrics						pixel-wise
	Methods	O ↓	C↓	CA↑	CO↑	CC↑	I.↓	II.↓	EA↑	MS↑	RM↓	CI↑
	EDSION	73.17 100.00 31.19 31.55 98.09 68.45	0.24	41.29	31.13	3.21	50.29
	JSEG	37.94	92.77	55.29 61.81 87.70	38.19	3.66	66.74	55.14	4.96	70.27
	SWA	33.01	85.19	54.84 60.67 88.17	39.33	2.11	66.94	53.71	6.11	70.32
	GL-graph 17.80 15.13 66.53 75.75 82.19 24.25	4.17	76.10	63.63	6.72	77.48
	WCP	41.32	28.70	53.55 67.49 63.39	32.51	6.60	62.69	51.23	9.34	64.00

Table 5 .

 5 2: Quantitative comparison of our results with other methods on the Berkeley database with multiple measurements: the results of our method are obtained over the best tuned parameter for each image.

	Methods	PRI↑	VoI↓	GCE↓	BDE↓
	NCut	0.7242	2.9061	0.2232	17.15
	GBIS	0.7139	3.3949 0.1746	16.67
	NTP	0.7521 2.4954	0.2373	16.30
	WCP	0.7496 2.4399 0.2392 15.7416

Table 6 .

 6 2: Performances of our method on MSRC and comparison with state-ofthe-art methods.

	Metric	PRI↑	VoI↓	GCE↓	BDE↓
	Object class	baseline	new	baseline	new	baseline	new	baseline	new
	1. grass, cow	0.8889	0.8978	0.7927	0.8417	0.1006	0.1059	4.8316	4.9181
	2. tree, grass, sky	0.7865	0.7963	1.2569	1.3664	0.1727	0.1990 18.6141 13.6065
	3. building, sky	0.8429	0.8697	1.2660	1.3768	0.1670	0.1755	8.0268	8.3904
	4. aeroplane, grass, sky	0.9083	0.9202	1.3133	1.2662	0.1463	0.1649	4.1802	4.3369
	5. cow, grass, mount	0.9038	0.8647	0.5641	0.7804	0.0752	0.0889	4.2286	4.8817
	6. face, body	0.7176	0.7277	2.2429	2.3892	0.2601	0.2669 16.1357 15.2383
	7. car, building	0.7423	0.7624	2.2676	2.1879	0.2044	0.2546 12.3907 12.3268
	8. bike, building	0.7037	0.7196	2.0662	2.1575	0.2729	0.2854 10.7725 10.9580
	9. sheep, grass	0.8837	0.8867	0.7287	0.7166	0.0853	0.0874	4.7323	4.9983
	10. flower	0.8712	0.8766	0.6368	0.7172	0.0836	0.0927	6.8501	5.7331
	11. sign	0.8581	0.8839	0.7668	0.7591	0.0929	0.0940	6.4911	6.3972
	12. bird, sky, grass, water	0.8820	0.8932	0.6977	0.7215	0.0963	0.0831	5.6918	5.9985
	13. book	0.6714	0.6613	1.7574	1.9669	0.1596	0.1633 18.9275 17.7393
	14. chair	0.7395	0.7806	1.3144	1.6839	0.1862	0.1807 11.7096	7.7027
	15. cat	0.7532	0.7483	1.3479	1.2819	0.1272	0.1240 12.0134 11.8589
	16. dog	0.8030	0.8029	1.2856	1.2436	0.1394	0.1613	9.7475	9.5381
	17. road, building	0.8439	0.8610	1.6346	1.7412	0.2002	0.2025	9.0031	8.4299
	18. water, boat	0.8548	0.8424	1.0310	1.0947	0.0935	0.1088	9.1329	12.4533
	19. body, face	0.8376	0.8275	1.6961	1.9347	0.1931	0.2124	7.4399	8.8790
	20. water, boat, sky, mount	0.8884	0.9154	1.1942	1.0002	0.1602	0.1279	6.3682	5.6792
			Average performance
	Method	PRI↑	VoI↓	GCE↓	BDE↓
	Our new method	0.8269	1.3614	0.1590	9.0032
	Baseline

  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

	Chapter 7
	Active Colloids Segmentation and
	Tracking
	Contents
	7.1

. 3 :

 3 Configuration I (PI) Fig.7.3 (a) shows a case of missing connection. The track numbered 80 in pink is terminated at frame f k , due to that its corresponding node at time t = k -1 has no connected node at time t = k. This can be easily fixed by simply increasing the search range until a neighborhood is found (shown in dash line). We observed that the global result is improved if the link with the most distant node is removed from the graph. Let us emphasize that in case a node has more than three neighbors, only the most distant one is removed. ) are connected to the same neighbor in f k (labeled as 88 in the figure). If only one of the node has more than two neighbors then its connection with the common neighbor is removed. If both nodes have more than two neighbors, the longest connection with the common neighbor is removed.

	Configuration III (PIII)
	Fig.7.3 (c) presents another conflicting situation where two nodes (numbered
	88 and 344 in frame f k-1
	Configuration II (PII)

Fig.7.3 (b)

illustrates the case where one node (numbered 154 in the frame f k-1 ) connects to two neighbors (numbered 154 and 361 in frame f k ), which are far from each other.

Table 7 .

 7

		1: Parameters of ground-truth
			Mean colloids		Mean/min/max
	Labeled videos Total colloids	per frame	Total trajectories	trajectory length
	# 1	12443	25	352	35/1/283
	# 2	14479	29	358	40/1/361
	# 3	11571	23	318	36/1/212
	# 4	7974	16	236	34/1/145
	# 5	9802	20	248	40/1/500
	# 6	8420	17	253	33/1/173
	# 7	8561	17	258	33/1/159
	# 8	6437	13	198	32/1/105
	# 9	6600	13	187	35/1/146
	Av.	9587	19	268	36/1/232
	Total	86287	-	2408	-

Table 7 .

 7 2: Quantitative evaluation of different detection methods measured by MOTP.

	Method	Otsu	local maximum Padfield et al. Sbalzarini and Koumoutsakos	ours
	# 1	0.8975	0.8950	0.8793	0.8929	0.8969
	# 2	0.8920	0.8977	0.8741	0.89	0.8996
	# 3	0.9032	0.9006	0.8829	0.8871	0.9058
	# 4	0.8661	0.8635	0.8542	0.8506	0.8646
	# 5	0.8627	0.8637	0.8356	0.8545	0.8661
	# 6	0.8434	0.8444	0.8315	0.8327	0.8427
	# 7	0.9064	0.9031	0.8886	0.8907	0.9085
	# 8	0.8654	0.8642	0.8526	0.8563	0.8645
	# 9	0.8218	0.8248	0.8135	0.8153	0.8254
	AV	0.8731	0.8730	0.8569	0.8633	0.8749
	7.4.4 Tracking and Analysis
	7.4.4.1 Graph Refinement Validation

Table 7 .

 7 3: Quantitative evaluation of the efficiency of the three types of refinement, PI, PII and PIII. ⊕ and mean with/without operator.

		Refinement	Metric
	PI PII PIII MOTA% ↑
				94.03%
	⊕			94.13%
		⊕		94.17%
			⊕	94.23%
	⊕	⊕	⊕	94.45%

Table 7 .

 7 4: Quantitative evaluation of different combinations of the three types of refinement, PI, PII and PIII. Numbers 1,2 3 mean 1st, 2nd,3th order.

		Refinement	Metric
	PI PII PIII MOTA%↑
	1	2	3	94.45%
	1	3	2	94.45%
	2	1	3	94.45%
	2	3	1	94.45%
	3	1	2	94.45%
	3	2	1	94.45%
	est path algorithm [

Table 7 .

 7 5: Quantitative comparison between five standard tracking methods and our algorithm on 9 small video samples.

			dt 2 /2		 dt 4 /4	0	dt 3 /2	0	
	   , B t =	   (dt 2 /2) dt    , Q =	   dt 3 /2 0	dt 4 /4 0	0 dt 2	dt 3 /2 0	   ,
			dt		0	dt 3 /2	0	dt 2

  Contents 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

Patch. In this case, a patch centered at a pixel is extracted and is treated as a

Superpixels. In recent years, for both low-level and high-level tasks in computer vision, it has been a major trend to use the superpixel, which is a set of homogeneous pixels in certain feature space, as a basic data sample. For example, low-level segmentation[Wang et al., 2008b[START_REF] Yang | Unsupervised segmentation of natural images via lossy data compression[END_REF],objectness measurement[START_REF] Alexe | Measuring the objectness of image windows[END_REF][START_REF] Jrr Uijlings | Selective search for object recognition[END_REF], object detection[Shu

http://www.cs.toronto.edu/~babalex/research.html ERS[START_REF] Liu | Entropy rate superpixel segmentation[END_REF] https://sites.google.com/site/seanmingyuliu/home/research_segmentation SLIC[START_REF] Achanta | Slic superpixels compared to state-of-the-art superpixel methods[END_REF] http://www.vlfeat.org/ 4. Combined features. Up to now, there is no single feature that can describe all types of object properties. Thus it is essential to understand the advantages and disadvantages of different feature descriptors, and extend them or combine them for specific application. Shi and Malik[Shi and Malik, 2000] computed

-norm is unique and conveys the most meaningful information of a signal[START_REF] Elad | Sparse and Redundant Representations -From Theory to Applications in Signal and Image Processing[END_REF].Formally, this sparsest solution can be written as the following minimization

All experiments are carried out on the Berkeley Segmentation Database (BSD)[START_REF] Arbelaez | Contour detection and hierarchical image segmentation[END_REF], which includes 300 images and the corresponding ground truth data (each image has at least 4 human annotations). It is divided into a training set which contains 200 images and a test set including 100 images. Each

http://www.ee.columbia.edu/ln/dvmm/SuperPixelSeg/

http://cns.bu.edu/ lgrady/software.html

http://www.cis.jhu.edu/ ehsan/

https://sites.google.com/site/guangcanliu/

http://www.cse.oulu.fi/CMV/Downloads/LBPMatlab

http://www.vlfeat.org/

https://gforge.inria.fr/frs/?group_id=2151

Acknowledgments Acknowledgment

The authors would like to thank Bingxue Zhang, Doming Chen, Huaxiong Ding, Huiliang Jin, Ying Lv, Yuxing Tang, Yinghang Tang, Cheng Wang, and Wuming Zhang for contributing their precious time to annotate each colloid in the video sequences presented in the paper. In particular, many thanks to Xiaoyan Jiang, for her fruitful suggestions on our work, and for having provided the results for 9 video sequences using the algorithm proposed in [Jiang et al., 2013].

Romain Le Goc. He gives me warm support and love.

During my thesis work, I am fully funded by a PhD scholarship from the Chinese Government and the China Scholarship Council. My research in this PhD thesis is also supported by the Freanch research agency, Agence National de Recherche (ANR), through the Visen project within the ERA-NET CHIST-ERA program, under the grant ANR-12-CHIRI-0002-04, and VideoSense project under the grant 2009 CORD 026 02.

Code

Mean Shift [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF] http://www.vlfeat.org/ FH [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF] http://cs.brown.edu/~pff/segment/ Superpixel with normalized cut [START_REF] Ren | Learning a classification model for segmentation[END_REF] http://www.cs.sfu.ca/~mori/research/superpixels/ Quick Shift [START_REF] Vedaldi | Quick shift and kernel methods for mode seeking[END_REF] http://www.vlfeat.org/ Watersheds [START_REF] Couprie | Power watersheds: A new image segmentation framework extending graph cuts, random walker and optimal spanning forest[END_REF] http://www.esiee.fr/~coupriec/code.html Turbopixels [START_REF] Levinshtein | Turbopixels: Fast superpixels using geometric flows[END_REF]

our method segments it correctly while the segmentation provided by SAS is not meaningful; 2) The object and its surrounding are quite similar in color or texture (river otter, leopard and bird). For example, the SAS algorithm oversegments the river otter and the leopard into several parts, while our method yields a correct segmentation. 3) Objects of the same type appear in a large, possibly disconnected, region of the image, as for instance the bottles or the mountain. SAS is not competitive with our method for long-range grouping, hence it tends to split the object into different parts (e.g. the bottles into 4 parts and the mountain into 4 parts).

On the contrary, our proposed method can derive the right partition.

We also report quantitative comparison with SAS and other standard benchmarks: Ncut [START_REF] Shi | Normalized cuts and image segmentation[END_REF], JSEG [START_REF] Yining | Unsupervised segmentation of color-texture regions in images and video[END_REF], Multiscale Ncut (MNcut) [START_REF] Cour | Spectral segmentation with multiscale graph decomposition[END_REF], Normalized Tree Partitioning (NTP) [Wang et al., 2008a], Saliency Driven Total Variation (SDTV) [START_REF] Donoser | Saliency driven total variation segmentation[END_REF], Texture and Boundary Encoding-based Segmentation (TBES) [START_REF] Rao | Natural image segmentation with adaptive texture and boundary encoding[END_REF], Ultrasound Contour Map (UCM) [START_REF] Arbelaez | Contour detection and hierarchical image segmentation[END_REF], Learning Full Pairwise Affinity (LFPA) [Kim et al., 2010a], SAS [START_REF] Li | Segmentation using superpixels: A bipartite graph partitioning approach[END_REF], Context-sensitive [START_REF] Bai | Learning context-sensitive shape similarity by graph transduction[END_REF], Co-transduction [START_REF] Bai | Co-transduction for shape retrieval[END_REF], Tensor Product Graph (TPG) [START_REF] Yang | Affinity learning with diffusion on tensor product graph[END_REF], and Fusion with TPG [START_REF] Zhou | Fusion with diffusion for robust visual tracking[END_REF]. The results are shown in Table 4. 5, where we highlight in bold the best two results for each qualitative criterion.

Most of the average scores of the benchmark methods are collected from [Li Chapter 5. Graph-based Image Segmentation Using Weighted Color Patch Therefore, the mid-level feature x is a linear combination of several low-level features, thus not only carries the same information as the original low-level features, but also carries additional contextual cue.

Graph Construction and Partitioning

Once mid-level features have been computed, we build the graph that will be plugged into a spectral clustering algorithm to perform image segmentation. This is done as follows: For each scale of over-segmentation (i.e. for each instance of over-segmentation), we construct a graph whose nodes are the superpixels at that scale, and whose graph edges and weights are computed using 0 -sparse representation. More precisely, we consider as dictionary the mid-level features associated with the superpixels. Then, as in Equation ( 6.2), each mid-level feature xi can be represented as a sparse linear combination xi = j α i j xj of the other mid-level features. The similarity coefficient of any pair xi , xj of superpixels is defined as

where r ij is the sparse representation error of xi and xj , i.e.

. We collect all 0 affinity matrices obtained from all over-segmented images, and we concatenate them diagonally into a unique matrix denoted as W SS , together with the pixel-superpixels affinity matrix W IS . Then we consider the bipartite graph associated with the matrix B = W IS W SS and the Transfer Cut algorithm [START_REF] Li | Segmentation using superpixels: A bipartite graph partitioning approach[END_REF] is applied to partition the bipartite graph into K clusters by solving the Chapter 6. Sparse Coding and Mid-Level Superpixel-Feature for 0 -Graph Based Unsupervised Image Segmentation following generalized eigenvalue problem over superpixels only [START_REF] Li | Segmentation using superpixels: A bipartite graph partitioning approach[END_REF] for more details.

Experimental Results

Database and Parameter Settings

We evaluate our approach on the Microsoft Research Cambridge (MSRC) database, which contains 591 images from 23 object classes, and we use for the evaluation the accurate ground-truth segmentations of [START_REF] Malisiewicz | Improving spatial support for objects via multiple segmentations[END_REF]. To quantitatively evaluate the performance, we apply four popular measurements : 1) Probabilistic Rand Index (PRI) [PRI]; 2) Variation of Information (VOI) [START_REF] Meila | Comparing clusterings: an axiomatic view[END_REF]; 3) Global Consistency Error (GCE) [START_REF] Martin | A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[END_REF]; and 4) Boundary Displacement Error (BDE) [START_REF] Freixenet | Yet another survey on image segmentation: Region and boundary information integration[END_REF]. A segmentation result is better if PRI is higher and the other three ones are lower. For low-level features extraction, we only use the color feature in RGB space, and the feature dimension is reduced from 256 × 3 to 64 by PCA. For mid-level dictionary building via sparse coding, we use the Orthogonal Matching Pursuit (OMP) algorithm [OMP] to solve Eqn. 6.1 and set the sparsity number L = 4 according to the experimental results.

On the step of graph construction and partitioning, we proceed as in our previous work [START_REF] Wang | A graph-cut approach to image segmentation using an affinity graph based on l0-sparse representation of features[END_REF], i.e. we derive from the original image 5 or 6 oversegmented images (this number of scales being experimentally satisfactory) obtained by the Mean Shift (MS) method [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF] and by the FH method [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF]. More precisely, we derive three images by the MS method using the sets of parameters (hs, hr, M )= { [START_REF] Karypis | A fast and high quality multilevel scheme for partitioning irregular graphs[END_REF][START_REF] Karypis | A fast and high quality multilevel scheme for partitioning irregular graphs[END_REF]100), [START_REF] Karypis | A fast and high quality multilevel scheme for partitioning irregular graphs[END_REF]9,100), and (7, 11, 100)}, respectively, where hs and hr are bandwidth parameters in the spatial and range domains, and M is the minimum size of each segment. Either two of three oversegmented images are provided by the FH method using as parameters (σ, c, M ) either {(0.5, 100, 50), (0.8, 200, 100)}, or {(0.8, 150, 50), (0.8, 200, 100), (0.8, 300, 100)}. To build the 0 graph, the sparsity number L = 3 is used for all the experiments, see [START_REF] Wang | A graph-cut approach to image segmentation using an affinity graph based on l0-sparse representation of features[END_REF] for more details. We organize our experimental results as follows: first, we compare the Ensuring that no two trajectories share an object, each colloid can just only link with one colloid between consecutive frames respectively. Thus, we assume that each edge contains unit capacity c(u, v) = 1 and there are no negative cost edges ω(u, v) 0. Many algorithms exist to find the solution based on such optimality criteria, such as cycle canceling, linear programming, push-relabel method [Zhang et al., 2008b], We refer the reader to [START_REF] Ravindra | Network Flows: Theory, Algorithms, and Applications[END_REF] for a proof of the optimality criteria and more details of these algorithms.

Global optimal solution: Many algorithms exist to find the solution of this minimum cost maximal flow problem, such as cycle canceling, linear programming, or the push-relabel method [Zhang et al., 2008b]. We refer the reader to [START_REF] Ravindra | Network Flows: Theory, Algorithms, and Applications[END_REF] for a proof of the optimality criteria and more details on these algorithms.

A popular method is the successive shortest path (SSP) algorithm [pir, Ahuja et al., 1993]. However, one pass of SSP is insufficient to find all tracks, because graph construction from frames cannot guarantee to connect every head node of potential track to the source, with the same situation for rear node to the sink. where mme t is the number of mismatch errors for time t. g t be the number of objects present at time t.

• Multiple Object Tracking Accuracy (MOTA): the final score to summarize tracking,

.12) m t , f p t , mme t represent respectively the number of misses, of false positives, and of mismatches respectively for time t.

MOTP evaluates the alignment of tracks with the ground truth, and MOTA produces a score based on the amount of false positives, missed detections and identity switches. Note that during constructing object-hypothesis, the distance between object o i and hypothesis h j should not exceed the threshold, 15 pixels. In other words, the maximal observed difference between computed and hand-marked cell positions was 15 pixels, i.e. less than the search range.

Detection and Analysis

In this part, we compare the proposed method, i.e. the combination of a level set method with the circular Hough transform, with four other standard baselines which are frequently used techniques for particle detection. As summarized in [START_REF] Chenouard | Objective comparison of particle tracking methods[END_REF], Smal et al., 2010b], we choose to use the adaptive threshold method [START_REF] Otsu | A threshold selection method from gray-level histograms[END_REF], the local minimum/maximum detection, and the wavelet based method used in [START_REF] Padfield | Coupled minimum-cost flow cell tracking for high-throughput quantitative analysis[END_REF] as well as the particle detection method proposed in [START_REF] Ivo | Feature point tracking and trajectory analysis for video imaging in cell biology[END_REF]. Let us briefly introduce them.

In the experiments, we use the Otsu's method to decide the optimal threshold for the image after performing the background subtraction. We model the background by simply averaging over all video frames. Before we perform the local minimum/maximum algorithm, we also subtract background and denoise the result with Gaussian kernel. In [START_REF] Padfield | Coupled minimum-cost flow cell tracking for high-throughput quantitative analysis[END_REF], they choose to use wavelets based method to decompose the image into both the spatial and frequency domain. Such decomposition enables the images to be directly denoised in the wavelet coefficient space and the final segmentation can be obtained from the correlation stack for coefficients greater than zero and needs no post-processing. The segmentation parameters for the lower scales and upper scales are tuned according to the rules introduced in [START_REF] Padfield | Coupled minimum-cost flow cell tracking for high-throughput quantitative analysis[END_REF]. Note that the code can be found online at http://www.dirkpadfield.com/papers. In [START_REF] Ivo | Feature point tracking and trajectory analysis for video imaging in cell biology[END_REF], their proposed particle detection algorithm mainly consists of four steps: image restoration, estimation and refinement of the particle position and non-particle discrimination. The parameters relevant for detection are: (1) radius: approximate radius of the particles, radius = 4 pixels; (2) cutoff: the score cut-off for the non-particle discrimination, cutof f = 0; and (3) percentile: the percentile which determines which bright pixels are considered as particles, percentile = 0.7. Note that we turn the parameter to get reasonable performance with the software online available at http://mosaic.mpi-cbg.de/?q=downloads/imageJ.

The second baseline algorithm is the algorithm proposed in [START_REF] Jiang | Accurate 3d multi-marker tracking in x-ray cardiac sequences using a two-stage graph modeling approach[END_REF], which first constructs a directed graph associating all frames and then iteratively uses Dijkstra's shortest path algorithm until a specified number of iterations is reached or no more optimal paths can be extracted from the graph. In the experiments, to conduct fair comparison, the maximum displacement of a colloid moving between consecutive frames is fixed with the same of ours, naming d max = 25 pixels. All the nine videos use the same detection results proposed in this paper, the only difference is the tracking algorithm.

The third and fourth algorithms are the nearest neighbor algorithm and the Hungarian algorithm [START_REF] Harold W Kuhn | The hungarian method for the assignment problem[END_REF]. Both of them recover the trajectories of colloids by first doing a frame-to-frame linking by virtue of either nearest neighbor or the Hungarian algorithm, and then do a second iteration which is to link the partial trajectory with its subsequent trajectory. Their code is available online at http: //fr.mathworks.com/matlabcentral/fileexchange/34040-simple-tracker. In addition, during the second iteration, they also consider gap-closing, which is a link spanning between multiple frames to restore the track. Note that, the Hungarian algorithm provides guarantee that the sum of the pair distance (measured by Euclidean distance) is minimized over all colloids between two frames. The complexity of this algorithm is in O(n 3 ), which can be prohibitive for problems with a huge number of objects in each frame. In this case, it is prone to use the nearest neighbor, which runs in O(n 2 ), although it only achieves a local optimum for a pair of colloids.

The fifth baseline proposed in [START_REF] Ivo | Feature point tracking and trajectory analysis for video imaging in cell biology[END_REF] find the trajectories also within two or more frames, where the optimal set of associations is solved by minimizing a cost functional. In practice, their implementation is based on a particle matching algorithm [START_REF] Stuart | Decay of rotating turbulence: some particle tracking experiments[END_REF] using a graph theory technique. In experiments, the maximum displacement is set 25 pixels also, the number of subsequent frames that are considered to find the optimal association is two frames.

The quantitative comparison results are reported in the Table 7.5. Our proposed tracking scheme has the best performance over all videos with respect to the MOTA score, and at the same time, has the smallest mismatch measured by MM, compared with the other standard baselines. In average, our method gains large margins compared with the Kalman, the Dijkastra shortest path used in the [START_REF] Jiang | Accurate 3d multi-marker tracking in x-ray cardiac sequences using a two-stage graph modeling approach[END_REF], and the [START_REF] Ivo | Feature point tracking and trajectory analysis for video imaging in cell biology[END_REF]] by both measurements of MM and MOTA. The performances of the nearest neighbor and the Hungarian are quite close to ours, their average accuracies measured by the MOTA are 92.93% and 92.99% respectively, which is close to our average accuracy 93.19%.

In addition, we also compare visually the results obtained by different algorithms to show the performance in a particular context where a small cluster is moving slowly and meanwhile encounters with other individual colloids. As shown from Fig. 7.8 to Fig. 7.14, we show only a few trajectories, but each illustration is finished at the end frame of trajectories, for example, in Fig. 7.8, all trajectories are finished at the 126th-frame. Besides, we also show all the trajectories in the three-dimensional illustration located at the last of each figure. As observed in Fig. 7.9, the Kalman's filter yields identity switches errors with long-distance colloids (note the large gap

Contributions

The contributions in this thesis are as follows.

A Global/Local Affinity Graph for Image Segmentation

To construct a high-quality graph in the graph-cut based image segmentation methods, we propose a novel sparse global/local affinity graph over superpixels of an input image to capture both short and long range grouping cues, thereby enabling perceptual grouping laws, e.g., proximity, similarity, continuity, to enter in action through a suitable graph cut algorithm. Moreover, we also evaluate three major visual features, namely color, texture and shape,for their effectiveness in perceptual segmentation and propose a simple graph fusion scheme to implement some recent findings from psychophysics which suggest combining these visual features with different emphases for perceptual grouping. Specifically, an input image is first oversegmented into superpixels at different scales. We postulate a gravitation law based on empirical observations and divide superpixels adaptively into small, medium and large sized sets. Global grouping is achieved using medium sized superpixels through a sparse representation of superpixels' features by solving a 0 -minimization problem, thereby enabling continuity or propagation of local smoothness over long range connections. Small and large sized superpixels are then used to achieve local smoothness through an adjacent graph in a given feature space, thus implementing perceptual laws, e.g., similarity and proximity. Finally, a bipartite graph is also introduced to enable propagation of grouping cues between superpixels of different scales. Extensive experiments are carried out on the Berkeley Segmentation Database in comparison with several state of the art graph constructions. The results show the effectiveness of the proposed approach which outperforms state of the art graphs using 4 different objective criteria, namely PRI, VoI, GCE and BDE.

Graph-based Image Segmentation Using Weighted Color Patch

To construct a discriminative affinity graph in graph-based image segmentation, we propose a new method based on the weighted color patch to compute the weight of edges in an affinity graph. The proposed method intends 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 normalized cut algorithm is then applied on the resulting affinity graph to find partitions. We evaluate the proposed method on the Prague color texture image benchmark and the Berkeley image segmentation database. The extensive experiments show that our method is competitive compared to the other standard methods using multiple evaluation metrics.

Appendix A

Fusing Generic Objectness and Deformable Part-based Models for Weakly Supervised Object Detection

A.1 Introduction

Object detection/localization in images is one of the most widely studied problems in computer vision. For most of the existing methods, a fully supervised learning (FSL) approach is adopted [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]Triggs, 2005, Felzenszwalb et al., 2010],

where positive training images are manually annotated with bounding boxes encompassing the objects of interest. However, manual annotation for large-scale image database is extremely laborious and unreliable [Siva and Xiang, 2011b]. As a result, in contrast to the traditional FSL, there has been a great interest in weakly supervised learning (WSL) for object detection [START_REF] Deselaers | Localizing objects while learning their appearance[END_REF] Deformable Part-based Models (DPM) [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] and its variants [START_REF] Azizpour | Object detection using strongly-supervised deformable part models[END_REF]Laptev, 2012, Girshick et al., 2011], are the leading techniques to object detection with full supervision on the challenging PASCAL VOC datasets [START_REF] Everingham | The pascal visual object classes (voc) challenge[END_REF]. The DPM represent an object with a coarse root filter that approximately covers an entire object and several higher resolution part filters that cover smaller parts of the object. In the standard (fully supervised) DPM framework, the positive ground-truth object bounding boxes are treated as the initial root filters, and it is allowed to move around in its small neighborhood to maximize the filter score. The locations of parts are treated as latent information as the annotations for parts are not available. Megha et al. [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF] modify the fully supervised DPM to a weakly supervised one, without object-level annotations, by treating the location of root filter and part filters full latent, and learning structural object detectors based on the entire image (root filter location is initialized randomly based on a window which has at least 40% overlap with the positive training image, and its aspect ratio is initialized roughly to the average of the aspect ratios of positive training examples). However, the specific size and location of the initial root filter, as well as their aspect ratio are indicated to have a significant impact on the final localization result [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF], Models for Weakly Supervised Object Detection Felzenszwalb et al., 2010, Pandey and[START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF]. And to our best knowledge, methods for initializing the root filter as well as the definition of the aspect ratio of the objects in weakly supervised DPM, have not been well studied in [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF]. To take advantage of the outstanding object detection performance of fully supervised DPM, in this paper, we propose a model enhancing the weakly supervised DPM by emphasizing the importance of location and size of the initial class-specific root filter. To be precise, we explore the objectness approach [START_REF] Alexe | Measuring the objectness of image windows[END_REF], which generates class-independent object proposals with corresponding scores to their probabilities of being object windows, and adaptively extract a reliable window from the derived object proposals for each image as the initial root filter estimate for training DPM detector. Finally, a flexible enlarging-and-shrinking postprocessing procedure is proposed to modify the predicted output of DPM detector, which can effectively generate more accurate bounding boxes by better conserving foreground and cropping out plain background regions. Experimental results on the challenging PASCAL VOC 2007 database demonstrate that our proposed framework is effective for initialization of root filter, and shows competitive final localization performance with the other weakly supervised object detection methods [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF]Lazebnik, 2011, Siva et al., 2012]. The rest of the chapter is organized as follows: we present our method to extract reliable initial root filter for weakly supervised DPM and our technique to post-process the bounding box in Section A.2, and in Section A.3 we present our experimental results and the comparison with other methods on PASCAL VOC 2007 datasets. In Section A.4, we conclude our work. Models for Weakly Supervised Object Detection

A.2 Our Approach

In this section, we present our approach for improving the performance of DPM for weakly supervised object detection. In particular, we explore objectness measurement [START_REF] Alexe | Measuring the objectness of image windows[END_REF], which has been widely applied for various purposes in computer vision, to generates category-independent object proposals with corresponding scores to their likelihood of being object bounding boxes, and adaptively extract a faithful window from the derived object proposals for each image as the initial root filter size and position for DPM detector. We then briefly describe the training and detecting procedures with DPM. Finally we propose our new postprocessing method to further modify the predicted object bounding box obtained by DPM detector, so as to cover the object more precisely. [START_REF] Ali | An integrated region-, boundary-, shapebased active contour for multiple object overlap resolution in histological imagery[END_REF]. We set N = 1000, which ensures covering most objects even in very difficult images [START_REF] Ali | An integrated region-, boundary-, shapebased active contour for multiple object overlap resolution in histological imagery[END_REF]. Based on the fact that the objectness is designed to capture all possible objects within an image, we assume it has the reliability for providing at least one good candidate window w * which covers the object of interest. However, the window with the highest objectness score max(S) is not always an effective choice [START_REF] Shi | Transfer learning by ranking for weakly supervised object annotation[END_REF], which usually encompasses other noisy objects, or locates poorly on object target.

A.2.1 Initialization of object bounding box estimation

To extract a reliable window from the pool of 1000 windows, we design a recursive selective scheme shown in

where,

and their corresponding score denoted as

Given the reference region T which implies the most salient region within an image, and confident candidate windows, the overlap between them provides valuable information to find the location of target object. The final estimate of the initial object bounding box w * (Fig. A.1(g)) is determined by optimizing the following function:

where γ is a parameter used to control the influence of the objectness score s i . In practice, we set γ = 0.2.

A.2.2 Detection with deformable part-based models

We start training the DPM detectors with the derived bounding boxes from Section A.2.1, which are treated as our positive training windows. Similarly to [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF], each root filter hypothesis in a positive training image is initialized with the corresponding derived bounding box (ground-truth bounding box is used in [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]), and it is allowed to move around in a small neighborhood to maximize the filter score to compensate for imprecise bounding box estimation from Section A.2.1. We refer the reader to [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF] for more details concerning the DPM training and detection procedures. As in [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF], we represent an image by a multiscale HOG feature pyramid [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF] of 16 levels. For our DPM model, we use only a single component, since the multiple components are used for detecting objects with different views.

We set the number of parts in DPM as 8 in all our experiments. And for negative training examples, we use random negatives from other object classes.

A.2.3 Bounding box post-processing

In many cases, the bounding boxes generated by DPM detectors are too large (resp. small) when detecting very small (resp. large) objects due to the restrictions of the size of the root filter and the scale of the feature pyramid. To improve the localization and to obtain a more precise estimate of the bounding box aspect ratio, we post-process each bounding box by enlarging or shrinking it to cover the object as much as possible. This is done using an improved version of the method proposed in [Y. [START_REF] Tang | The design of high-level features for photo quality assessment[END_REF] which measures the amount of area that the edge energy occupies. In brief, we first augment the original bounding box to 120% of the original width and height (i.e. 144% in total area), and calculate the absolute values of the Models for Weakly Supervised Object Detection gradients over the augmented bounding box and set the values which are less than 10% of the maximum to 0. To easily calculate the edge spatial distribution, then we resize the gradient magnitude image size to 100 × 100 and normalize the image sum to 1. Finally, we expand the bounding box in 4 directions from the centroid and stop until it contains 98% of the total gradient magnitude (edge energy) in the augmented box. This post-processing technique is not only able to crop out plain background regions, but also can expand to cover the foreground regions which are not encompassed by the original box. However, the cropping method in [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF] is probably to fail with the latter. Dataset: Following the protocol of previous works [START_REF] Deselaers | Localizing objects while learning their appearance[END_REF][START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF][START_REF] Siva | In defence of negative mining for annotating weakly labelled data[END_REF], we evaluate the performance of our proposed weak supervision framework on two subsets from the training and validation set (trainval ) of the PASCAL VOC 2007 dataset (VOC07 ) [START_REF] Everingham | The pascal visual object classes (voc) challenge[END_REF]: VOC07-6×2 and VOC07-14. The VOC07-6×2 subset contains 6 classes with Left and Right views (aspects) of each class, resulting in a total of 12 separating classes. The VOC07-14 subset (same with PASCAL07-all defined in [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF]) consists of 42 class/view combinations covering 14 classes and 5 views. Similar to [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF], we remove all the images annotated as difficult or truncated in both training and evaluation steps. Models for Weakly Supervised Object Detection Evaluation criteria: To make fair comparisons, we only choose the detection window with highest score per image, although our method can detect multiple instances appeared in the image using sliding window approach. We also report both results for initial and refined localization as [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF]Lazebnik, 2011, Siva et al., 2012]. A refined localization is obtained by an iteratively trained DPM detector for one/several iteration(s) to refine the initial detection using the previous annotations as ground truth. Performance is evaluated with the percentage of training images in which an object is correctly covered by the window, if the strict PASCAL-overlap criterion is satisfied (intersection-over-union > 0.5).

A.3 Experimental Evaluation

Experimental evaluation: As Table A.1 shows, our method outperforms [START_REF] Deselaers | Localizing objects while learning their appearance[END_REF] and our baseline approach [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF]] on both datasets. Our average performance of initial detection before cropping boxes on the VOC07-6×2 and VOC07-14 subsets is 38.74% and 21.73% respectively, versus 37.22% and 19.98% for [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF]. These improvements are due to the initial object estimate of our method described in Section A.2.1, which gives a better initialisation of the root filter of DPM detectors. We can also observe that both the cropping post-processing method from [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF] (i.e. ours- [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF] in Table A.1) and our enlarging-or-shrinking (i.e. ours-ES) post-processing method steadily improve the average localization accuracy. In particular, our ES cropping method is superior to that of [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF], as our cropped bounding box is not only able to shrink to crop out the background regions, but also capable of enlarging to cover the whole foreground object resulted by incomplete coverage of the original window. An example is shown in the last row of Fig. A.3, where the target object (motorbike) is only partially localized by the initial detector (shown in red rectangles in the middle and right images) for both [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF] and our method. However, in the final detection (shown in yellow), our method is able to enlarge the bounding box to nearly include the whole object, while [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF] tends to crop out both foreground and background regions. The middle rows in Table A.1 indicate that localization accuracy can benefit from the refinement process. It is worth mentioning that with a better initialisation, our models converge to a steady level of performance after one less round of costly re-training (i.e. 2 iterations) than [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF], and achieve slightly better results in the mean time. The detailed comparisons of our method with state-of-the-art methods on the VOC07-6×2 dataset are listed in Table A.2. The results show that our method outperforms [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF] for most of the categories. Especially, our method achieves the state-of-the-art results in some classes where the target object possesses the most salient regions in that category (e.g. aeroplane, bus, horse). Interestingly, even without refinement process, the accuracy for our method with certain category (e.g. aeroplane left) is superior to the competitors with the timeconsuming refinement procedure. Fig. A.3 visually compares some of our results with those of [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF]. Models for Weakly Supervised Object Detection

Ground Truth [5] Ours

A.4 Conclusion

In this paper, we proposed a model enhancing the weakly supervised learning by emphasizing the importance of location and size of the initial class-specific root filter of deformable part model (DPM). We follow the general setup of [START_REF] Pandey | Scene recognition and weakly supervised object localization with deformable part-based models[END_REF] and introduce several substantial improvements to the weakly supervised DPM. The main contributions included new approaches based on objectness approach in generating the initial candidate window estimates. Furthermore we designed a flexible enlarging-and-shrinking post-processing procedure to modify the output bounding boxes of DPM, which can effectively further improve the final accuracy. Experimental results on the challenging PASCAL VOC 2007 database demonstrate that our proposed framework is efficient and competitive with stateof-the-art methods.

Appendix B

The Criteria Set on Prague Texture Benchmark

The segmentation benchmark criteria is divided into four subsets:

• Region-Based Criteria [START_REF] Hoover | An experimental comparison of range image segmentation algorithms[END_REF].

• Pixel-Wise Weighted Average Criteria.

• Consistency Error Criteria [START_REF] Martin | A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[END_REF] • Clustering Comparison Criteria [START_REF] Meila | Comparing clusterings: an axiomatic view[END_REF] Note that we have introduced the GCE in Chapter 2. Symbols ↑ and ↓ denote required increase / decrease of the corresponding criterion.

B.1 Region-Based Criteria

The region-based criteria mutually compare the machine segmented regions R i i = 1, ..., M with the correct ground truth regions Rj j = 1, ..., N where |R| is the corresponding set cardinality. The regions overlap acceptance is controlled by the threshold 0.5 < T ≤ 1]) k = 0.75. Single region-based criteria are defined as follows:

↑ where N , M are the correct number of classes and the interpreted number of classes (or regions), respectively. K = arg max{M ; N }, n is the number of pixels in the test set, n i,j is the number of pixels interpreted as the i-th class but belonging into the j-th class. The error matrix ({n i,j }) extended into K × K is obtained by padding missing entries with zeros. î is either i for supervised tests or mapping of the i-th class ground truth into an interpretation segment based on the Munkres algorithm (for unsupervised test). The following pixel-wise criteria were implemented: ↓ O (omission error -the overall ratio of wrongly interpreted pixels):

where O i is the i -th class omission error. ↓ C (commission error -the overall ratio of wrongly assigned pixels):

where C i is the i-th class commission error. ↑ CA (the weighted average class accuracy):

↑ CO (recall, the weighted average correct assignment):

↑ CC (precision, object accuracy, overall accuracy):

↓ I (type I error, the weighted probability of wrong assignment of classes pixels):

↓ II (type II error, the weighted probability of commission error): ↓ RM (root mean square proportion estimation error): .12) indicates unbalance between the omission O i and commission C i errors, respectively. ↑ CI (comparison index -includes both these types of errors): [START_REF] Gao | Local features are not lonely-laplacian sparse coding for image classification[END_REF] where CC i , CO i are the object precision and recall. CI reaches its maximum either for the ideal segmentation or for equal commission and omission errors for every region (class).

The F measure curve (see Region-Based Criteria) Appendix C

Publications

During my PhD studies, I have published one journal paper and five papers in international conferences. A second journal paper is under review.

Published International Conference Papers: