Color Learning and Illumination Invariance on Mobile Robots: A Survey <s> Static Color Segmentation <s> We propose a novel approach for solving the perceptual grouping problem in vision. Rather than focusing on local features and their consistencies in the image data, our approach aims at extracting the global impression of an image. We treat image segmentation as a graph partitioning problem and propose a novel global criterion, the normalized cut, for segmenting the graph. The normalized cut criterion measures both the total dissimilarity between the different groups as well as the total similarity within the groups. We show that an efficient computational technique based on a generalized eigenvalue problem can be used to optimize this criterion. We have applied this approach to segmenting static images and found results very encouraging. <s> BIB001 </s> Color Learning and Illumination Invariance on Mobile Robots: A Survey <s> Static Color Segmentation <s> We propose a motion segmentation algorithm that aims to break a scene into its most prominent moving groups. A weighted graph is constructed on the image sequence by connecting pixels that are in the spatiotemporal neighborhood of each other. At each pixel, we define motion profile vectors which capture the probability distribution of the image velocity. The distance between motion profiles is used to assign a weight on the graph edges. Using normalised cuts we find the most salient partitions of the spatiotemporal graph formed by the image sequence. For segmenting long image sequences, we have developed a recursive update procedure that incorporates knowledge of segmentation in previous frames for efficiently finding the group correspondence in the new frame. <s> BIB002 </s> Color Learning and Illumination Invariance on Mobile Robots: A Survey <s> Static Color Segmentation <s> The paper presents a novel variational method for supervised texture segmentation. The textured feature space is generated by filtering the given textured images using isotropic and anisotropic filters, and analyzing their responses as multi-component conditional probability density functions. The texture segmentation is obtained by unifying region and boundary based information as an improved Geodesic Active Contour Model. The defined objective function is minimized using a gradient-descent method where a level set approach is used to implement the obtained PDE. According to this PDE, the curve propagation towards the final solution is guided by boundary and region based segmentation forces, and is constrained by a regularity force. The level set implementation is performed using a fast front propagation algorithm where topological changes are naturally handled. The performance of our method is demonstrated on a variety of synthetic and real textured frames. <s> BIB003 </s> Color Learning and Illumination Invariance on Mobile Robots: A Survey <s> Static Color Segmentation <s> We propose a new model for active contours to detect objects in a given image, based on techniques of curve evolution, Mumford-Shah (1989) functional for segmentation and level sets. Our model can detect objects whose boundaries are not necessarily defined by the gradient. We minimize an energy which can be seen as a particular case of the minimal partition problem. In the level set formulation, the problem becomes a "mean-curvature flow"-like evolving the active contour, which will stop on the desired boundary. However, the stopping term does not depend on the gradient of the image, as in the classical active contour models, but is instead related to a particular segmentation of the image. We give a numerical algorithm using finite differences. Finally, we present various experimental results and in particular some examples for which the classical snakes methods based on the gradient are not applicable. Also, the initial curve can be anywhere in the image, and interior contours are automatically detected. <s> BIB004 </s> Color Learning and Illumination Invariance on Mobile Robots: A Survey <s> Static Color Segmentation <s> CM-Pack'01 came in second place at RoboCup-2001 in the Sony Legged League. This is our fourth year competiting in this league. We used a simplified architecture this year. Our vision, localization, and behaviors ran synchronously with the camera input while our motions remained an asynchronous process. We focused on reducing latency and increasing timeliness and completeness of environment modelling for this year. We used more structured software engineering this year than in previous years and found this very useful[4]. <s> BIB005 </s> Color Learning and Illumination Invariance on Mobile Robots: A Survey <s> Static Color Segmentation <s> A novel scheme for image segmentation is presented. An image segmentation criterion is proposed that groups similar pixels together to form regions. This criterion is formulated as a cost function. Using gradient-descent methods, which lead to a curve evolution equation that segments the image into multiple homogenous regions, minimizes this cost function. Homogeneity is specified through a pixel-to-pixel similarity measure, which is defined by the user and can be adaptive based on the current application. To improve the performance of the system, an edge function is also used to adjust the speed of the competing curves. The proposed method can be easily applied to vector valued images such as texture and color images without a significant addition to computational complexity. <s> BIB006 </s> Color Learning and Illumination Invariance on Mobile Robots: A Survey <s> Static Color Segmentation <s> A novel scheme for the detection of object boundaries is presented. The technique is based on active contours deforming according to intrinsic geometric measures of the image. The evolving contours naturally split and merge, allowing the simultaneous detection of several objects and both interior and exterior boundaries. The proposed approach is based on the relation between active contours and the computation of geodesics or minimal distance curves. The minimal distance curve lays in a Riemannian space whose metric as defined by the image content. This geodesic approach for object segmentation allows to connect classical "snakes" based on energy minimization and geometric active contours based on the theory of curve evolution. Previous models of geometric active contours are improved as showed by a number of examples. Formal results concerning existence, uniqueness, stability, and correctness of the evolution are presented as well. > <s> BIB007 </s> Color Learning and Illumination Invariance on Mobile Robots: A Survey <s> Static Color Segmentation <s> This paper addresses the problem of segmenting an image into regions. We define a predicate for measuring the evidence for a boundary between two regions using a graph-based representation of the image. We then develop an efficient segmentation algorithm based on this predicate, and show that although this algorithm makes greedy decisions it produces segmentations that satisfy global properties. We apply the algorithm to image segmentation using two different kinds of local neighborhoods in constructing the graph, and illustrate the results with both real and synthetic images. The algorithm runs in time nearly linear in the number of graph edges and is also fast in practice. An important characteristic of the method is its ability to preserve detail in low-variability image regions while ignoring detail in high-variability regions. <s> BIB008 </s> Color Learning and Illumination Invariance on Mobile Robots: A Survey <s> Static Color Segmentation <s> Unsupervised image segmentation algorithms have matured to the point where they generate reasonable segmentations, and thus can begin to be incorporated into larger systems. A system designer now has an array of available algorithm choices, however, few objective numerical evaluations exist of these segmentation algorithms. As a first step towards filling this gap, this paper presents an evaluation of two popular segmentation algorithms, the mean shift-based segmentation algorithm and a graph-based segmentation scheme. We also consider a hybrid method which combines the other two methods. This quantitative evaluation is made possible by the recently proposed measure of segmentation correctness, the Normalized Probabilistic Rand (NPR) index, which allows a principled comparison between segmentations created by different algorithms, as well as segmentations on different images. For each algorithm, we consider its correctness as measured by the NPR index, as well as its stability with respect to changes in parameter settings and with respect to different images. An algorithm which produces correct segmentation results with a wide array of parameters on any one image, as well as correct segmentation results on multiple images with the same parameters, will be a useful, predictable and easily adjustable preprocessing step in a larger system. Our results are presented on the Berkeley image segmentation database, which contains 300 natural images along with several ground truth hand segmentations for each image. As opposed to previous results presented on this database, the algorithms we compare all use the same image features (position and colour) for segmentation, thereby making their outputs directly comparable. <s> BIB009 </s> Color Learning and Illumination Invariance on Mobile Robots: A Survey <s> Static Color Segmentation <s> We present a multiscale spectral image segmentation algorithm. In contrast to most multiscale image processing, this algorithm works on multiple scales of the image in parallel, without iteration, to capture both coarse and fine level details. The algorithm is computationally efficient, allowing to segment large images. We use the normalized cut graph partitioning framework of image segmentation. We construct a graph encoding pairwise pixel affinity, and partition the graph for image segmentation. We demonstrate that large image graphs can be compressed into multiple scales capturing image structure at increasingly large neighborhood. We show that the decomposition of the image segmentation graph into different scales can be determined by ecological statistics on the image grouping cues. Our segmentation algorithm works simultaneously across the graph scales, with an inter-scale constraint to ensure communication and consistency between the segmentations at each scale. As the results show, we incorporate long-range connections with linear-time complexity, providing high-quality segmentations efficiently. Images that previously could not be processed because of their size have been accurately segmented thanks to this method. <s> BIB010 </s> Color Learning and Illumination Invariance on Mobile Robots: A Survey <s> Static Color Segmentation <s> Humans have an amazing ability to instantly grasp the overall 3D structure of a scene--ground orientation, relative positions of major landmarks, etc.--even from a single image. This ability is completely missing in most popular recognition algorithms, which pretend that the world is flat and/or view it through a patch-sized peephole. Yet it seems very likely that having a grasp of this "surface layout" of a scene should be of great assistance for many tasks, including recognition, navigation, and novel view synthesis. ::: ::: In this paper, we take the first step towards constructing the surface layout, a labeling of the image intogeometric classes. Our main insight is to learn appearance-based models of these geometric classes, which coarsely describe the 3D scene orientation of each image region. Our multiple segmentation framework provides robust spatial support, allowing a wide variety of cues (e.g., color, texture, and perspective) to contribute to the confidence in each geometric label. In experiments on a large set of outdoor images, we evaluate the impact of the individual cues and design choices in our algorithm. We further demonstrate the applicability of our method to indoor images, describe potential applications, and discuss extensions to a more complete notion of surface layout. <s> BIB011
Color segmentation is typically the first step in a robot vision system that uses a color camera. The goal here is to either cluster image regions into similar groups and/or to create a mapping from each possible pixel value to a discrete color label, i.e. to create a color map: where m 1 , m 2 , m 3 are the values along the color channels (e.g. R, G, B), E represents the dependence on illumination, and l refers to the numerical indices of the color labels (e.g. blue = 1, orange = 2). Color segmentation of individual images is a heavily researched field in computer vision, with several good algorithms  BIB001 BIB006 . We first discuss a few of these approaches. The mean-shift algorithm  is a very general non-parametric technique for the analysis of complex multi-modal feature spaces (e.g. texture) and the detection of arbitrarily shaped clusters in such spaces. The feature space is modeled as an empirical probability density function (pdf). Dense regions in the feature space correspond to local maxima, i.e. the modes of the unknown pdf, which are located at the zeros of the gradient of the density function. Unlike the classical approaches for kernel density estimation  , the meanshift procedure locates the local maxima i.e. zeros without estimating the density function. Iterative computation of the mean-shift vector that always points in the direction of maximum increase in density, and translation of the kernel in the direction of the mean-shift vector, is guaranteed to converge to a local mode. Mean-shift vectors therefore define a path to the desired modes. Once the modes are found, the associated clusters can be separated based on the local structure of the feature space. Though the technique performs well on several vision tasks such as segmentation and tracking, its quadratic computational complexity makes it expensive to perform on mobile robots with computational constraints. Figure 3 shows image results obtained using Mean shift code  . An entirely different approach to image segmentation is the use of "active contours" (curve evolution), where initial contours are defined and deformed towards the object boundaries using partial differential equations. The active contour methods typically follow one of two representation schemes: parametric active contours (PAC) and geometric active contours (GAC). PAC use a parametric representation for the curves while GAC use level sets. Level sets and and hence the GAC methods readily handle changes in topology as the curve evolves, for example merging and splitting. Active contour methods are typically classified into three groups: edge-based BIB007 , region-based BIB004 BIB006 and hybrid BIB003 based on whether they primarily operate on image edges, regions or a combination of both. Sumengen et al. BIB006 describe a region-based GAC method that segments images into multiple regions. Their approach uses edgeflow image segmentation, where a vector field is defined on pixels in the image grid and the vector's direction at each pixel is towards the closest image discontinuity at a predefined scale. An edge function based on this vector field is used to segment precise region boundaries. Their method allows the user to specify the similarity measure for region-merging and splitting based on different image characteristics such as color or texture. The algorithm is reasonably robust to the initial curve estimates and provides good segmentation results on a variety of images. However, it involves an iterative computation for finding the final contours and takes seconds of off-board processing per image. These algorithms are hence unsuitable for real-time operation on mobile robots with constrained resources. Image segmentation can also be posed as a graph-partitioning problem, and more specifically as a weighted undirected graph G = (V, E), where each node v i ∈ V represents a pixel in the image, and the edges E connect certain pairs of neighboring pixels. Each edge is assigned a weight based on some property of the pixels that it connects. In recent times, graph-based methods BIB008 BIB001 have proven to be powerful segmentation algorithms. One popular class of graph-based segmentation methods find minimum cuts in the graph, where a cut measures the degree of dissimilarity between point sets by computing the weights of the graph edges that have to be removed to separate the two sets (say A, B): and the goal is to minimize this cost. Since the minimum cut favors cutting small sets of isolated nodes in the graph  , Shi and Malik BIB001 proposed the idea of considering pixel clusters instead of looking at pixels in isolation. Their normalized cut is a robust global criterion that simultaneously maximizes the similarity within a cluster and the dissimilarity between clusters. Since the normalized cut for a graph with regular grids is NP-complete, it is approximated and solved using principles drawn from the generalized eigenvalue problem BIB001 . In addition to providing good segmentation and object recognition, normalized cuts have also been used for other computer vision tasks such as motion tracking BIB002 and 3D view reconstruction BIB011 . However, the graph-optimization process is time-consuming. Even with the current linear approximations to the original quadratic-time implementation it involves an iterative optimization phase that takes seconds of off-board processing per image. Graph-based algorithms are hence computationally expensive to perform in real-time (20-30Hz) on mobile robot platforms. Other recent graphbased image segmentation techniques (e.g. Felzenswalb and Huttenlocher BIB008 ) provide improved measures for graph-partitioning but still have similar computational limitations, even after incorporating simplifying assumptions that increase processing speed. Pantofaru and Hebert BIB009 compare the Mean-shift and graph-based image segmentation algorithms. Figure 4 shows sample results obtained with the NCuts code BIB010 . Many mobile robot applications require real-time operation (20-30Hz) and a robust mapping from pixels to color labels (the color map in Equation 1 ). In addition to being clustered, similar image regions may hence need specific color labels and may need to be tracked across several images even when environmental conditions change. This color map is typically created through an elaborate offline training phase -images are manually labeled over a period of hours to obtain the initial training samples BIB005 . Since the extensive labeling only labels 5 − 10% of the color space, the color map is produced by generalizing from these training samples using machine learning techniques such as neural networks  , decision trees  , axis-parallel rectangle creation  and nearest neighbors [92] . Figure 5 provides segmentation results on some sample images captured on-board a legged robot. The main disadvantage of the hand-labeled color map is that this entire training process has to be repeated when the environmental conditions such as the illumination change. Even methods that provide some robustness to illumination changes by using a different color space  do not eliminate the need for extensive manual calibration, or the sensitivity to illumination. Table 1 uses the criteria mentioned in Section 2 to evaluate the segmentation algorithms discussed above. The "adaptation" column represents the ability to detect environmental changes, and to consistently hold the appropriate belief over various colored regions when such changes occur -red regions for instance should be clustered appropriately and labeled red even when the illumination changes. In summary, classical approaches to color segmentation are either computationally expensive to implement on mobile robots and/or require extensive manual calibration that is sensitive to environmental changes.