Color Constancy and Image Segmentation Techniques for Applications to Mobile Robotics

Chapter 6 A Color Image Segmentation Algorithm 6.1 Introduction Image segmentation is a essential but critical component in low–level vision, image analysis, pattern recognition, and now in robotic systems. Besides, it is one of the most difficult and challenging tasks in image processing, and determines the quality of the final results of the image analysis. Intuitively, image segmentation is the process of dividing an image into different regions such that each region is homogeneous while not the union of any two adjacent regions. An additional requirement would be that these regions had a correspondence to real homogeneous regions belonging to objects in the scene. The classical broadly–accepted formal definition of image segmentation is as follows [PP93]. If P(◦) is a homogeneity predicate defined on groups of connected pixels, then the segmentation is a partition of the set Iinto connected components or regions {C1,...,Cn}such that n [ i=1 Ciwith Ci∩Cj=∅,∀i6=j(6.1) The uniformity predicate P(Ci) is true for all regions Ciand P(Ci∪ Cj) is false when i6=jand sets Ciand Cjare neighbors. Additionally, it is important to remember here that the image segmentation problem is basically one of psychophysical perception, and therefore not susceptible to a purely analytical solution, according to [FM81]. Maybe that is why, literally, there are hundreds of segmentation techniques in literature. Nevertheless, to our knowledge, yet no single method can be considered good for all sort of images and conditions, being most of them created pretty ad hoc for a particular task. Despite the importance of the subject, there are only several surveys specific on the image segmentation issue, principally versed on monochrome segmentation [FM81, HS85], giving little space to color segmentation [PP93, LM99]. For more details, Chapter 3 is completely devoted to review the state of the art on the segmentation of color images. Not until recently has color image segmentation attracted more and more attention mainly due to reasons such as the ones below 118 CHAPTER 6. A COLOR SEGMENTATION ALGORITHM •Color images provide far more information than gray–scale images and segmentations are more reliable. •Computational power of available computers has rapidly increased in recent years, being able even for PCs to process color images. •Handling of huge image databases, which are mainly formed by color images, as the Internet. •Outbreak of digital cameras, 3G mobile phones, and video sets in everyday life. •Improvement in the sensing capabilities of intelligent systems and machines. Most of the segmentation techniques for monochrome images – histogram thresholding, feature clustering, edge detection, region–based methods, fuzzy techniques, and neural networks – have been extended to segment color images by using RGB color coordinates or some of their transformations, either linear or nonlinear. However, comprehensive surveys on color image segmentation are still scarce in number [SK94, CJSW01]. Work in [SK94] discussed the properties of several color representations and a pretty extensive list of segmentation methods were summarized and analyzed, splitting them into several categories analogous to those already mentioned for gray–scale images. The list of conclusions in that review are worth to be taken into account, specially those saying that •General purpose algorithms are not robust nor always algorithmically efficient. •No general advantage in using one specific color space with regard to others has been found. •Color constancy is needed to improve effectiveness when combining region segmentation with color object recognition. More recently, the review in [CJSW01] provides an up–to–date summary of color image segmentation techniques available at present, and describes the properties of different kinds of color representation methods and some of the problems encountered when applying those models to segment color images. Some novel approaches such as fuzzy and physics–based methods are discussed as well in that work. There is an interesting taxonomy of methods and color spaces with their description, advantages and disadvantages. For more information about the issue, the reader should refer to Chapter 3. In order to propose a useful segmentation algorithm that fits our needs, we must say that our choice was among the family of graph–theoretical approaches because of its good mathematical basements and the fact that the segmentation problem is straightforwardly translated into a graph–partitioning problem existing lots of different methods to solve it. Nonetheless, the worst disadvantage of this type of framework is, as can be seen in [WL93, VC93, XU97], that these algorithms are heavy time–consuming, which should prevent us from their application in (nearly) real–time applications. For this last reason, we chose Jaume Verg´es–Llah´ı MMV 6.2 Outline of the Chapter 119 among the sort of greedy graph–partitioning algorithms, faster than any other one method in that family, as observed in [FH98a]. In this Chapter we present our color image segmentation algorithm that is capable of working on diverse color spaces and metrics. This approach has a nearly linear computational complexity and is based on that in [FH98a] along with a set of improvements, both theoretical and practical, which amend the lacks detected in former results. This algorithm has been successfully applied to segmenting both static images and sequences, where some further enhancements were introduced to achieve more coherent and stabler segmentations of sequences. Finally, in this Chapter some results are provided whose aim is to test the performance of our segmentation in comparison not only with the results attained by the original algorithm in [FH98a], which has been improved, but also with those obtained by the unsupervised clustering Expectation–Maximization (EM) algorithm by Figueiredo [FJ02]. EM is one of the most successful clustering methods in recent years1, and Figueiredo’s version is completely unsupervised, which avoids the problem of selecting the number of components and does not require a careful initialization. Besides, it overcomes the possibility of convergence toward a singular estimate, a serious problem in other EM–like algorithms. We show that our segmentations are fully comparable to those of the Figueiredo’s EM algorithm, but at the same time and more importantly, our algorithm is far faster. 6.2 Outline of the Chapter Next, we summarize the main aspects discussed in each Section of the Chapter. In Section 6.3 we condense the most related former works dealing with the image segmentation problem using a graph–theoretical approach. Section 6.4 is devoted to extensively analyzing our color segmentation algorithm. Our approach has been enlarged to cope with sequences in Section 6.5. Thereafter, in Section 6.6, we reinforce our previous statements with numerous example of image segmentations of static images and sequences, comparing them with those obtained employing other image segmentation algorithms. Finally, Section 6.7 encompasses our conclusions about the work carried out in this Chapter. 6.3 Related Previous Work An important set of techniques to segment images are those based on graph theory. The main idea consists in building an image representation employing a graph and then applying some graph–theoretical techniques to obtain homogeneous connected components which represent regions in the segmented image. An additional advantage of using graphs is that region–based and edge–based segmentation are dual problems, being able to achieve close contours from the segmentation of regions without any further treatment on the image. 1Another extremely interesting clustering algorithm usually applied to the image segmentation problem is the one based on the mean–shift transformation [CM97, CM99, CM02]. While this one is nonparametric, EM is a parametric method that provides, as a result, a finite mixture of Gaussian distributions. Jaume Verg´es–Llah´ı MMV 120 CHAPTER 6. A COLOR SEGMENTATION ALGORITHM Two different groups of methods can be considered depending on the technique employed. On the one hand, there exist all those methods that partition a graph describing the whole image into a set of subgraphs, where there is one component for each image region. Algorithms differ in the particular way of removing superfluous edges. Next, some graph–partitioning approaches are briefly described. The most efficient graph–based algorithms use fixed thresholds and purely local measures to find regions. For instance, the approach in [Zah71] is based on breaking larger edges in a minimum spanning tree of the graph. The inadequacy of removing larger edges is apparent because edge weights within high variability region tend to be larger than in any other region. This work also developed several heuristics to address such issues by using models of the distributions of weights. A more recent method is that in [WL93] based on the computation of the minimum cut in the graph representing an image. Originally, this kind of algorithms were used to solve problems of maximum flow between two points – the source and the drain – connected by paths with a constrained flow capacity, e.g., water or electric networks. In the case of images, capacities account for the similarity between components and node connectivity represents pixel neighborhoods. Therefore, the cut criterion is designed to minimize the similarity between regions that are being split. This kind of segmentation captures nonlocal properties of the image but requires more than nearly linear time, in contrast with more efficient methods described bellow that just employ local information. Other refinements based on spectral partitioning techniques can be found in [SM97, SBLM98], where a normalized version of the minimum cut is computed. For a wider review on these sort of approaches, we refer the reader to [Els97, Fja98]. Another algorithm proposed in [Urq97] uses a measure of local variability to decide which edge to remove from the graph. This measure is based only on the nearest neighbors for each point. When this criterion is applied to segmentation problems, it is claimed that the nearest neighbors alone are not enough to get a reasonable measure of the whole image variability since they only capture local properties of the image. This issue is tackled in [FH98a], as will be seen later. The interesting graph–theoretical work in [Wan98] presents a method to segment images into partitions with connected components by using computationally inexpensive algorithms for probability simulation and simulated annealing, such as that of Hastings’s and the generalized Metropolis algorithm. In order to reduce the computational burden, a hierarchical approximation is proposed, minimizing at each step a cost function on the space of all possible partitions into connected components of a graph. Finally, there are a number of methods that employ more sophisticated models, such as those based on Markov Random Fields (e.g., [GG84]). However, these methods tend to be quite inefficient in terms of time. In our opinion, the two main goals for an image segmentation algorithm are to capture nonlocal properties of the image and to be efficient to compute, and those algorithms are far too time–consuming for our purposes. On the other hand, there is another set of graph–based algorithms that takes advantage of region–growing methods, being the growing process driven by the attributes of nodes and edges. Thus, edges are aggregated forming a list of connected nodes, which likewise form an image component. Edges are selected in Jaume Verg´es–Llah´ı MMV 6.4 Segmentation of Color Images 121 such a manner they provide homogeneous components. The particular strategy applied to select edges is what differentiate algorithm one another. It is important to state that in both kinds of methods numerous works are found taking advantage of the Minimum Spanning Tree (MST) as a mean to reduce the inherent algorithmic complexity of the graph–partitioning problem as well as the one that may appear in region–growing if all node connections are taken into account. MST captures the minim structure of an image and helps by its partition or growing to obtain efficient segmentation algorithms in terms of time and memory. In [VC93] vertexes which are connected by the smallest edge weight are afterwards melted by an iterative process. At the end of that process, the list encompassing the smallest edges at each step forms a spanning tree which is further split by way of removing the edges with the greatest weights, while generating a hierarchy of image partitions. In [XU97] a MST is build up using the Kruskal’s algorithm to find a partition that minimizes a cost function afterwards. This task is accomplished by a dynamic approach and diverse heuristics to further reduce the algorithm complexity. The approach in [FH98a] is even more drastic in the use of MSTs since it combines both region–growing and Kruskal’s routine. Edge aggregation is driven by a local measure of image variation over arbitrarily large regions in the image. Moreover, this approach addresses a major shortcoming of previous graph– based methods, i.e., the dichotomy between either using efficient (nearly linear time) algorithms, but avoiding global properties of the image, or capturing global image properties, but being less efficient. Despite in [SM97] it is argued that in order to capture nonlocal properties of an image any segmentation algorithm should start with larger regions in the image and then splitting them progressively, rather than starting with smaller regions and merging them, work in [FH98a] suggests arguments to the contrary, i.e., a region merging algorithm based on nonlocal image properties is as well capable of producing segmentations. They do so by introducing global definitions of what it means for an image to be subsegmented or oversegmented based on the aggregation of local intensity differences. An image is defined to be oversegmented when there is some pair of regions for which the variation between regions is small relative to the variation within each region. Besides, an image is subsegmented when there is a way to split some regions into subregions such that the resulting segmentation is not an oversegmentation. These definitions could be used along with other measures of similarity between regions. The algorithm in [FH98a] satisfies at the same time the two global properties of neither subsegmenting nor oversegmenting an image accordingly to their previous definitions. The algorithm runs in nearly linear time of the number of pixels, and it is really fast in practice. This efficiency is achieved by a bottom–up process that successively merges smaller components into larger ones. 6.4 Segmentation of Color Images Due to the speed of the algorithm in [FH98a], it is a good starting point to develop a fast algorithm for color segmentation that fits the time constraints Jaume Verg´es–Llah´ı MMV 122 CHAPTER 6. A COLOR SEGMENTATION ALGORITHM of mobile robotics. Hence, many novelties have been introduced in our new approach in order to improve the final results attained by the original algorithm. The first change we have introduced is the use color differences instead of independently running an intensity version of the algorithm as many times as the number of color channels and trying to mix the obtained regions afterwards. Secondly, we have developed an energy–based approach to control the component merging process so as to relax the oversegmentation condition to obtain, as a consequence, resultant segmentations with fewer regions. In addition, we have introduced an index to identify all the spurious regions that appear in segmentation as a result of highly variant regions not corresponding to any actual area in the image. These regions are removed from segmentation and joined to their closest neighboring component. The overall coherence at the ending segmentation is improved because the remaining regions correlate better with their counterparts in the real scene. Finally, the algorithm has also been extended to cope with images coming from video sequences in order to maintain their segmentations as stable as possible through time. Part of the results described in this Chapter have already been reported in the papers [VLCS00] and [SAA+02]. 6.4.1 Some Definitions First of all, we give some basic definitions will help us along this Section. In our graph–based approach to image segmentation, Undirected Weighted Graphs (UWG) are used to represent color images. Being Va set of vertexes and Ea set of edges connecting them, an UWG is a graph G = (V,E) defined from the set of image pixels P={pi}and the set of their colors I={cp:∀p∈ P} as follows. Each pixel p∈ P corresponds to a vertex v∈ V to which a neighborhood Nρ(p) = {q∈ P | 0< DP(p, q)≤ρ}can be assigned, being DP:P ×P → R+ 0 a distance between pixels, usually Euclidean, in image coordinates. Therefore, the set of edges is defined as E={epq = (p, q) : ∀q∈Nρ(p)}.ρis the radius of the neighborhood, in number of pixels. Commonly, ρ= 1. Therefore, the weight function ωamong edges gives a measure of similarity between two vertexes (pixels) as follows ω:E−→ R+ 0 epq 7−→ ω(epq) = DI(cp, cq) = ωpq (6.2) where DIis some distance in a color space. We refer to [WS82, SK94, Fai97] for a wider review on color coordinates and distances, which will be partially reviewed later in this Section. Finally, Ω = {ω(e): ∀e∈ E} is the set of all weights of the edge set in G. The following algorithm works on a fixed ordering ˜ E= (e1,...,en) such that ω(ei)≤ω(ej),∀i≤j, where n=|E|. Asegmentation of G is defined as a subgraph S = (C,FC) where C={Ci}is the set of components forming a partition2of Vand FC={FCi}is a canonical forest. A component Ciis a set of vertexes that are connected one another by a path of edges of Eminimizing the sum of their edge weights. Cpis the component to where the vertex pbelongs. 2A partition of Xis a group of subsets {Xi⊂ X } | X =∪iXiand Xi∩ Xj=∅,∀i6=j. Jaume Verg´es–Llah´ı MMV 6.4 Segmentation of Color Images 123 A canonical forest FCis a set of trees where each FCi∈ FCis a Minimum Spanning Tree (MST) of Ci∈ C. The ordering ˜ Eprovides a way of selecting a unique MST from the possible minimum weight spanning trees of Ci. We can now define the set Σ of all the segmentations S of a graph G and an equivalence relation, ≤, of pairs of elements that is reflexive,anti–symmetrical, and transitive T≤S⇐⇒ T∈R(S) (6.3) where R(S) = {Q∈Σ: ∀C∈Q,∃C0∈S|C⊆C0}is a refinement of a segmentation S ∈Σ. Put in words, a refinement of a segmentation S is the set of all other segmentations which have smaller components in a way that once these components get merged, they generate the same components as in S. Moreover, the strict inequality can be defined as T <S if and only if T ≤S and T 6= S. The set (S, ≤) is a partially ordered set because the fact that T,T0≤S does not imply that T ≤T0nor T0≤T. Nevertheless, for any two segmentations T = (C,FC) and T0= (C0,FC0) it is true that T∩T0≤T,T0and T,T0≤T∪T0. Schematically T∪T0 % - T T0 - % T∩T0 (6.4) where T ∩T0= (C ∩C0,FC∩C0) and T ∪T0= (C ∪C0,FC∪C0). The maximum element of (S,≤) is G = (V,E) and the minimum is Gmin = (V,∅), where all components have only one vertex and trees have no edge. If we follow an algorithm that put together two components Cand C0at each step in respect to an edge in ˜ E, the resultant set of graphs at each step will be in ascendant order in (S, ≤), i.e., from minimum to maximum, forming a chain Π: Gmin = S1≤...≤Sn= G (6.5) This is the case of greedy algorithms such as the Kruskal’s minimum spanning tree algorithm and also that in [FH98a]. 6.4.2 Algorithm Analysis Now in this Section we translate the segmentation of an image Iinto the problem of finding a proper segmentation S from a graph G among the set of all possible segmentations in Σ. As a starting point, we follow the approach in [FH98a], where a segmentation is sought that fulfills a global property by only carrying out a local search. As mentioned, this approach takes advantage of a greedy algorithm that obeys the previous definitions of what is considered to be an oversegmented and a subsegmented image. The process keeps merging regions until segmentations which are neither oversegmented nor subsegmented are attained. Ideally, this should occur in an intermediate case corresponding to the notion of having neither too many nor too few components in a segmentation. Intuitively, an image is oversegmented when there are still too many components that could be further merged into bigger regions. Consequently, the algorithm should grow components until the image failed to be oversegmented, Jaume Verg´es–Llah´ı MMV 124 CHAPTER 6. A COLOR SEGMENTATION ALGORITHM that is, whenever merging more components were a likely error. Hence, an image is no more oversegmented if the differences between any two adjacent components are greater than their differences within S∈Σis NOT oversegmented if ∀Ci, Cj∈S adjacent Ci6=Cj   =⇒Dif (Ci, Cj)> Hom (Ci, Cj) (6.6) where Dif(◦,◦) is a function measuring the difference between two adjacent components and Hom(◦,◦) accounts for the internal homogeneity of both components. Be Σc OS ⊂Σ the set of all graphs observing Eq. (6.6)3. If T0∈Σ is the greatest segmentation in the chain Π being oversegmented, then we can rewrite Σc OS in an intervalwise manner as Σc OS = (T0,G) = {T∈Σ: T0<T<G}. In a similar way, an image is subsegmented whenever region–growing has gone too far and there are too few components left. This implies that too different components have been erroneously joined. Therefore, an image will not be subsegmented if there exists a proper refinement which is neither oversegmented, meaning that a smaller segmentation can be still found fulfilling Eq. (6.6). Hence, we can take as an interval the set (Gmin,S) = {T∈Σ: Gmin < T < S} of all proper segmentations smaller than S. So, we get that S∈Σis NOT subsegmented if (Gmin,S) ∩Σc OS 6=∅(6.7) The algorithm proposed by Felzenszwalb&Huttenlocher in [FH98a] – F&H’s algorithm, from now on –, which is a modification of the Kruskal’s algorithm to compute minimum spanning trees, used the two criteria above to control the segmentation process. Moreover, it was proved that the resulting segmentations were unique, that is, for a particular image the process always ends at the same segmentation and follows the same chain of segmentations Π. Nevertheless, what is important in this algorithm is the fact that the segmentation process takes decisions based on local properties of the image, such as pixel differences, and, yet, the resulting segmentation reflects global properties of the image since both oversegmentation and subsegmentation are global image features. However, we are convinced that these constraints are still too restrictive, which causes aggregation to stop prematurely, giving as a result a class of segmentations with too many components for our purposes. Our approach on the forthcoming Sections touches upon these defects both in a theoretical and a practical manner, as explained straight away. 6.4.3 Theoretical Approach Stating the fact that the F&H’s algorithm causes a resultant segmentation S as soon as both previous constraints are fulfilled and that any two successive 3ΣOS is the set of all oversegmented graphs and Σc OS is its complement. Jaume Verg´es–Llah´ı MMV 6.4 Segmentation of Color Images 125 segmentations Siand Si+1 accomplish that Si≤Si+1, we deduce that the algorithm will stop whenever (Gmin,S) ∩(T0,G) 6=∅ ⇐⇒ T0<S (6.8) This means that the F&H’s algorithm stops at the first segmentation S that is not oversegmented, which is in some way quite arbitrary and restrictive since the segmentation S usually has too many components in practice, i.e., it is still oversegmented for our proposes. If the nonoversegmented criterion were relaxed, it would be possible to attain segmentations S0with fewer components, i.e., S ≤S0. In case S0were still oversegmented, again the algorithm would follow the aggregation until another nonoversegmented S00 appeared, i.e., S0≤S00. Otherwise, we could deter the constraint again or just stop at that segmentation, which would be effectively greater than S and nonoversegmented, as expected. Nevertheless, oversegmentation can not be pushed too far since as regions grow, so do their internal dissimilarities, which are more than likely to surpass their mutual differences. This would cause the nonoversegmented condition not to be satisfied once a point of no return were crossed, in view of the fact that aggregation would keep on until only one region remained. So, in practice, the interval Σc OS would be (T0,T1) and a resulting segmentation should be obtained before T1were dangerously too close to G. In order to manage this leap over the constraints while avoiding the problem of going too far, we first reformulated the nonoversegmented criterion as a problem controlled by an energy function Uin the following way S∈Σis NOT oversegmented if ∀Ci, Cj∈S, adjacent, and Ci6=Cj=⇒∆US→S0>0 (6.9) where S ≤S0. ∆US→S0stands for the energy of the system involved in the transition between two consecutive segmentations S and S0. If the transition is done by joining components Ciand Cjtogether, we note this as ∆US→S0= ∆U(Ci∪Cj). In the case of F&H’s, we get that ∆U(Ci∪Cj) = Dif (Ci, Cj)−Hom (Ci, Cj) (6.10) where Dif(◦,◦) increases as regions grow while Hom(◦,◦) tends to fall along the segmentation because components differentiate each other more and more as they propagate. Those functions are based on local information provided by edges in ˜ E, which is not modified once computed at the starting point because of the greediness of that approach. The merging step of the algorithm employs the following aggregation condition. At any step k, two components merge if the edge ek=eij ∈˜ Econnecting them fulfills that Ck−1 i6=Ck−1 jand ∆UCk−1 i∪Ck−1 j≤0 (6.11) then, at step k, segmentation Skhas a new component formed by Ck−1 i∪Ck−1 jand FCk−1 i∪FCk−1 j∪ek(6.12) Jaume Verg´es–Llah´ı MMV 132 CHAPTER 6. A COLOR SEGMENTATION ALGORITHM 6.5 Segmentation of Sequences We must now face the problem of segmenting a sequence of images keeping in mind that those segmentations should satisfy at least two general properties, namely, components should correspond to actual regions in the image of homogenous color (coherence) and remain as stable as possible through the sequence. In other words, we do not want either segmentations with too many small regions or components which fluctuate too much through time. However, the process of reducing the number of components by aggregating similar adjacent regions may cause unstable segmentations because some of them may be joined differently in contiguous frames. From some preliminary results it seems that a more coherent segmentation would be necessary to prevent this shortcoming. We suggest an approach which takes advantage of the segmentation of the immediately previous frame in order to obtain that of the next one. The idea is pretty simple and, for each new frame, consists in grouping similar regions into bigger ones in the same way as it was done in the preceding frame. Thus, we kill two birds with one stone, i.e., we get greater coherence and stability. Obviously, an intermediate step dedicated to matching regions which seem equal in two consecutive images is needed. In general, using a correspondence stage in a segmentation process would be seen as a drawback because of being a time consuming and a usually prone–to– error process. Nevertheless, we propose to use the ideas laying behind the IRM distance between regions [WLW01], which provides both robustness to poor segmentations and effortlessly integrates features from many regions. Next, we consider the two steps that are needed in our segmentation of sequences, namely, the computations of correspondences among components and the propagation of previous segmentations into the new ones for each frame in the sequence. 6.5.1 Computation of Component Correspondences The correspondence between two components, Ck−1 i∼Ck i0, in two correlative frames Ik−1and Ikis defined as Ck−1 i∼Ck i0⇐⇒ Ck−1 i= argmin ∀Ck−1 l∈Ik−1DCk−1 l, Ck i0,∀Ck i0∈ Ik(6.31) where D(◦,◦) is a measure of distance between components in Ik−1and Ik. As said, we follow the ideas of the IRM similarity measure7in [WLW01] to compute a content–based distance between two components from different images. Our approach combines, at the same time, features of appearance and position. We use the mean color as the appearance feature, while the component center of mass is the position feature. Then, the difference D(Ck−1 l, Ck i0) between two components in two successive frames is computed using the simple Euclidean distance over the features above. In order to compare side by side two features that apparently are rather heterogeneous, such as color and position, we normalize the coordinates to fit the interval [0,1] dividing each component by the maximum range of each feature. 7In Chapter 7 there is a wider explanation about this measure. Jaume Verg´es–Llah´ı MMV 6.5 Segmentation of Sequences 133 This way, things which are a priori different and have dissimilar units can be compared as if they were basically the same. Theoretically, computations should be done for all Ck−1 i∈ Ik−1and Ck i0∈ Ikso that we finally got all the correspondences between components in two correlative frames. Nonetheless, to speed up computations it is interesting to focus comparisons only to a certain area surrounding the likeliest position where to find those component. 6.5.2 Propagation of Component Correspondences For each new frame, once the image has been individually segmented into components, we would like to use the previous regrouping of components to reduce the number of existing regions in the present image while preserving the regions which have already come up, maintaining the degree of coherence along the sequence as a consequence of it. Formally, let us suppose that two consecutive frames Ik−1and Ikprovide us with two segmentations Ik−1={Ck−1 i}i=1,...,nk−1and Ik={Ck i0}i0=1,...,nk, respectively. Let us also assume we know that the segmentation Ik−1has been reduced to a new segmentation with bigger components ˜ Ik−1={˜ Ck−1 j}j=1,...,mk−1, where mk−1≤nk−1and for each component Ck−1 i∈ Ik−1there exists a bigger component ˜ Ck−1 j∈˜ Ik−1so that Ck−1 i⊆˜ Ck−1 j. We define the set of indexes Indjof all components in Ik−1that have been put together forming one single region ˜ Ck−1 j∈˜ Ik−1. There hence exist as many index sets as components in ˜ Ik−1. The problem then is to propagate the segmentation in ˜ Ik−1into the one in Ikforming, as a consequence, a new segmentation ˜ Ik={˜ Ck j0}j0=1,...,mk. This is carried out by grouping the regions in Ikin such a way that if any component Ck i0∈ Ikcorresponds to a component Ck−1 i∈ Ik−1in the previous frame that was joined forming a bigger region ˜ Ck−1 j∈˜ Ik−1, then the component Ck i0will be grouped with the others satisfying the same property and creating the bigger component ˜ Ck j0, which is the propagation of the component ˜ Ck−1 jin the (k−1)th frame into the kth frame, that is, ˜ Ck−1 j∼˜ Ck j0. Formally, the component ˜ Ck j0is build as follows ˜ Ck j0=[ i0∈Indj0 Ck i0,∀Ck i0∈ Ik|Ck−1 i∼Ck i0∧Ck−1 i⊆˜ Ck−1 j(6.32) In other words, components in a given frame will be joined together as their corresponding components were joined in the anterior frame. Finally, a new segmentation ˜ Ikis achieved at kth frame, which is in general less oversegmented than the original one, Ik, while maintaining the stability of regions in respect to the previous frame. This scheme does not need to treat in any particular manner the components that appear or disappear in every new frame. Since component correspondence is done backwards, disappearing regions simply have no matching in the new frame. On the other hand, new regions will look for the closest region in the previous frame in terms of color and position. If the resulting distance is too great, then it is not adjoined to any component in ˜ Ik−1and is considered as a new region in the segmentation ˜ Ik. Jaume Verg´es–Llah´ı MMV 134 CHAPTER 6. A COLOR SEGMENTATION ALGORITHM 6.6 Experiments and Results The main concern in this Chapter resides in the segmentation of color images considered both as static images as well as belonging to a sequence that may have been obtained, e.g., from an autonomous robot. In order to achieve this goal, we display in this Section the set of experiments that have been carried out and the results obtained. Principally, these experiments consist in the segmentation of such images by the algorithm we suggest in this Chapter and the comparison of the resulting outcomes with those attained by means of the two other approaches already mentioned in previous paragraphs, namely, the original F&H’s algorithm in [FH98a] and the Figueiredo’s EM clustering method in [FJ02]. The goal of doing so is, first of all, to illustrate the improvements that have been attained in relation to the results by the original F&H’s algorithm, while maintaining its speed at a similar level. Likewise, our algorithm has been put side by side to that of Figueiredo, which is known to perform fairly well, to comparatively study the quality of our segmentations. Since our segmentations are definitively far faster than those of Figueiredo’s unsupervised EM, it is important for us to show that the same range of quality is kept. 6.6.1 Segmentation of Static Images The images shown in Fig. 6.1 correspond to different stages in the segmentation of the picture exhibited in Fig. 6.1 (a). First, we display the results obtained using the original F&H’s algorithm in Fig. 6.1 (b). It can be appreciated how this segmentation is not completely satisfactory since big homogeneous regions are split into several components, specially in the background. This is partially solved in Fig. 6.1 (c), where now homogeneous regions are completely merged in a coherent way into bigger components. Nevertheless, the total number of regions is still high in respect of the relatively small number of potential real regions in the image. This is because of the spurious regions generated in highly variable areas such as borders. These regions are detected using the index defined in Eq. (6.19) and can be observed in Fig. 6.1 (d). Finally, the resulting segmentation can be appreciated in Fig. 6.1 (e) after removing spurious regions, closely fitting actual homogeneous areas in the scene. An analogous situation is the one shown in Fig. 6.2, where the well–known picture of peppers is segmented. Again, the original image is portrayed in Fig. 6.2 (a). Fig. 6.2 (b) is the segmentation before removing the spurious regions that are pictured in Fig. 6.2 (c). The final result is exhibited in Fig. 6.2 (d). It must be noted that spurious pixels are eliminated by layers, starting at outer layers and ending with inner pixels. In this manner, regions tend to phagocytize any small spurious region within and to grow outwards until another region is found. This is not a genuine dilatation since pixels prefer regions with the highest number of neighbors in common. In order this segmentation to be useful in an object recognition system, it is important that images of a given object, which have been taken from different angles, be segmented in a similar way. We verify that behaviour in Fig. 6.3 and Fig. 6.4 where two series of images are shown. Fig. 6.3 displays a toy bear under six views. The upper row shows the original pictures while the lower row offers Jaume Verg´es–Llah´ı MMV 6.6 Experiments and Results 135 (a) (b) (c) (d) (e) Figure 6.1: Comparing our algorithm to that of F&H: (a) Original Image. (b) F&H’s segmentation. (c) Our segmentation before spurious regions elimination. (d) Spurious regions. (e) Final result after spurious regions elimination. (a) (b) (c) (d) Figure 6.2: Example of our segmentation: (a) Original Image. (b) Our segmentation before spurious regions elimination. (c) Spurious regions. (e) Final result after spurious regions elimination. Jaume Verg´es–Llah´ı MMV 136 CHAPTER 6. A COLOR SEGMENTATION ALGORITHM Figure 6.3: Example of our segmentation. Upper row: Original image. Lower row: Segmented image. Figure 6.4: Example of our segmentation. Upper row: Original image. Lower row: Segmented image. Jaume Verg´es–Llah´ı MMV 6.6 Experiments and Results 137 (a) (b) (c) (d) (e) Figure 6.5: Comparing our algorithm to that of Figueiredo. Upper row: Figueiredo’s segmentation. Lower row: Our segmentation. Jaume Verg´es–Llah´ı MMV 138 CHAPTER 6. A COLOR SEGMENTATION ALGORITHM the segmented images. A similar series is exhibited in Fig. 6.4, where a set of ten different views is supplied. In both series, regions formed in neighboring views are similarly segmented. Shades and highlights are collected into separate regions, which is quite natural since we, as humans, can also perceive them as separate areas. In our opinion, it is not a segmentation concern the issue of identifying such regions and discerning to which component they belong, a question that should be implemented in a different level task. Finally, in Fig. 6.5 we check up on whether our segmentation algorithm is capable of attaining results comparable to those obtained by the Figueiredo’s unsupervised clustering algorithm [FJ02]. This is an excellent version of the EM technique, very useful to segment images of unknown content since there is no need to know the exact number of clusters to run the routine. Moreover, this algorithm provides us with a family of Gaussian distributions as a result. Nevertheless, it takes quite a lot of time to complete an image. For example, a 360 ×288 image takes about 25 sec. to get segmented in a 800 MHz PC. Our algorithm only takes about 0.10 ÷0.20 sec. in the same computer, which is almost less than two orders of magnitude. In these series, the upper rows of each object are formed by the results corresponding to the Figueiredo’s segmentation, whereas the lower rows belong to the ones obtained by our algorithm. The aim in placing these images this way is to illustrate mainly two important questions, i.e., how different views of the same object are comparatively segmented and whether these segmentations differ too much depending on the kind of algorithm used. At first sight, it seems that both algorithms supply very similar segmentations, despite the elimination of spurious regions in our approach can produce slightly differing results wherever textured areas appear in images, as it is the case of fruity drawings and letters in Fig. 6.5(b) and Fig. 6.5(c), respectively. 6.6.2 Segmentation of Sequences We now move on to the description of some of the results that have been obtained after segmenting a video sequence captured from a mobile robot in an indoor environment. Yet, our aim is to illustrate the performance of our algorithm in such a task if compared to Figueiredo’s approach. At this point, we must state the difficulty we found to put these results in paper. Although the sense of all that is at once grasped once the videos are viewed8, we try to provide the same information in the following pages by only showing a set of images from a short interval out of the whole sequence. This piece of sequence is in Fig 6.6 and consists of a reduced set of 16 images from a longer sequence (≈1 min.) of 1001 images at a rate of 15 images/sec. This small set span for about 10 sec. and represent only one every 10 images. Images are filtered using the median filter with a neighborhood of 3 ×3 pixels to remove noise and to get smooth images without enlarging region contours. Color information is stabilized using the color constancy algorithm in Chapter 5 together with the Mean heuristic. The first image in the sequence is employed as the canonic one. The first step is to examine how the Figueiredo’s algorithm performs in segmenting sequences in order to later compare them with those achieved by our 8These videos will be provided in a CD–ROM for a better appreciation along with the rest of the graphics and images used in the conformation of this document. Jaume Verg´es–Llah´ı MMV 6.6 Experiments and Results 139 Figure 6.6: Set of images from the video sequence of a mobile robot moving about in an indoor environment. approach. Two set of images are presented in Fig. 6.7 in groups of two rows. The upper row are the same images in Fig 6.6 that have been independently segmented, meaning that each image is segmented using a randomly initialized Gaussian mixture. As can be seen, this method presents a number of problems since clustered colors are not exactly the same in consecutive frames. To minimize this lack of stability, the initialization routine is changed so that it could take advantage of previous segmentations. This is very easily attained using at each new frame the finite mixture of Gaussian distributions from the previous EM execution. When a certain color disappears, its corresponding Gaussian simply gets a zero weight and dies out. Letting spare Gaussian distributions initialize at random allows the algorithm to incorporate new clusters into the next segmentation step. Results obtained in that manner are displayed at the lower row in Fig. 6.7. The improvement is obvious in both segmentation and computation time, since convergence of the EM routine is faster due to the minor number of distributions and their closeness to the quiescent point. Afterwards, in order to complete the series of segmentations we carry out the same experiment as before, but using this time our algorithm in the next two cases, namely, without and with the enforcement of stability based on the computation and propagation of correspondences between components explained in Section 6.5. To perform these experiments, we use two color spaces, i.e., RGB along with the Euclidean distance, and Lab with the ∆Eab metric, both oh them reviewed in Section 6.4.6. Results obtained this way are exhibited in Fig. 6.8 for case of Lab space, and in Fig. 6.9 for RGB coordinates. As explained for Fig. 6.7, segmentations produced as if images were indeJaume Verg´es–Llah´ı MMV 140 CHAPTER 6. A COLOR SEGMENTATION ALGORITHM Figure 6.7: Images from the video sequence segmented using Figueiredo’s algorithm. Upper row: independent images. Lower row: using previous segmentation. Jaume Verg´es–Llah´ı MMV 6.6 Experiments and Results 141 Figure 6.8: Images from the video sequence segmented using our algorithm and Lab color space. Upper row: independent images. Lower row: component correspondence. Jaume Verg´es–Llah´ı MMV