Segmenting colour images on the basis of a fuzzy hierarchical approach

Mathware & Soft Computing 10 (2003) 101-115 Segmenting Colour Images on the Basis of a Fuzzy Hierarchical Approach J. Chamorro-Mart´ınez, D. S´anchez, B. Prados-Su´arez, E.Gal´an-Perales and M.A. Vila Department of Computer Science and Artificial Intelligence. University of Granada, Spain. e-mail: {jesus,daniel,belenps,egalan,vila}@decsai.ugr.es Abstract In this paper we deal with two problems related to imprecision in colour image segmentation processes: to decide whether a set of pixels verify the property ”to be homogeneously coloured”, and to represent the set of possible segmentations of an image at different precision levels. In order to solve the first problem we introduce a measure of distance between colours in the CIE L∗a∗b∗space, that allows us to measure the degree of homogeneity of two pixels pand qon the basis of the maximum distance between the colours of consecutive pairs of pixels in any path linking pand q. Since homogeneity is a matter of degree, we define a (fuzzy) segmentation of an image as a set of fuzzy regions, each of them being a fuzzy subset of pixels, that we obtain by using a region growing technique. The membership degree of each pixel to each region is calculated on the basis of our homogeneity measure. The second problem is solved by introducing a fuzzy similarity relation between the fuzzy regions in this initial segmentation. The different α-cuts of the similarity relation define the set of precision levels, from which a nested hierarchy of fuzzy segmentations is finally obtained. Keyword: Colour image segmentation, fuzzy segmentation, hierarchical segmentation, colour distance. 1 Introduction As it is well known, many image analysis techniques take as starting point a segmentation of the image, that is, a partition of the set of pixels in the image into connected subsets (called regions) on the basis of a certain criterion, that in most cases is color homogeneity of the pixels in regions. Many types of segmentation techniques have been proposed in the literature, each of them based on a certain methodology to calculate the regions. A first group of segmentation methods, pixel based methods, consider a region as a set of pixels satisfying a class membership function. Among them, histogram based 101 102 J. Chamorro-Mart´ınez et al. techniques [6] and clustering algorithms are significative examples [17]. A second kind of segmentation methods, area based techniques, defines regions as a set of pixels verifying an uniformity condition, as occurs in regions growing techniques [10] and split and merge algorithms [1]. A different point of view about regions consists on describing them as a set of pixels bounded by a colour contour, as edge based algorithms do. Most of the proposals falling in the aforementioned categories provide a crisp segmentation of images, where each pixel has to belong to an unique region. However, separation between regions is usually imprecise in natural images, as can be noticed in shadows, brights and color gradients, so crisp techniques are not often appropriate. To solve this problem, some approaches propose the definition of region as a fuzzy subset of pixels, in such a way that every pixel of the image has a membership degree to that region [2]. The majority of these fuzzy techniques are based on fuzzy clustering [4], like C-means algorithms, which defines a set of centroids and compute the membership value for all the pixels in the image to each centroid [14] [16]. Another example of fuzzy techniques are those based on the definition of fuzzy color histograms, where every pixel in the image belongs to every histogram’s bin in a certain degree [8], or fuzzy homogeneity histograms [5]. Less extended ideas for fuzzy segmentation are the ones based on different fuzzy resources, like using If-Then rules to detect borders [5] [7]. A drawback of most of these approaches is that they don’t take into account one of the characteristics of regions, i.e., they must be topologicaly connected. As a consequence, pixels belonging to separate and different regions, could be assigned to the same cluster. Hence, we consider that spatial information related to adjacency between regions should be introduced in order to overcome this situation. For this purpose, an interesting approach is to incorporate information about the topology of the image [10]. Another important problem related to image segmentation is that of granularity of the resulting fuzzy partition. Granularity issues are inherently present in image segmentation since number, size, and homogeneity of regions depend on the precision level we consider. Let’s illustrate this idea with the image in figure 1. At a high precision level we could consider several regions into the turtle’s shell, corresponding to areas with different brown colours. However, at lower granularity levels we could consider an unique region corresponding to the whole turtle. In general, when high precision is employed we obtain ”many”, small, and homogeneous regions. As the precision level is diminished, less, bigger, more heterogeneous regions are obtained by joining together several regions of previous levels. At the bottom, we have one single region that covers the whole image. Indirectly, some of these techniques [9] supply results that may be considered a solution to take into account these different levels of detail, since in every step of the algorithm the two most similar regions are joint into a single one. Nevertheless they only use information about the center of the regions like their average colour, so they don’t consider how soft or abrupt the transition between adjacent regions is. To face the problems described above, a hierarchical approach to fuzzy segmen- Segmenting Colour Images on the Basis of a Fuzzy Hierarchical Approach 103 Figure 1: A real image example that can be viewed with different detail levels. tation of colour images is proposed in this paper. The methodology works in two steps: •In the first one, introduced in [3], a collection of fuzzy regions is calculated by using the region growing approach. In this stage, a region is defined as a fuzzy subset of connected pixels and it is constructed using topographic and colour information, i.e., two pixels will be assigned to the same region if they are connected through a path of similar colours. A distance defined in the CIE(L∗a∗b∗) colour space is used in the growth of a region both (i) to select the pixels which will be linked in each step of the algorithm, and (ii) to calculate the membership degree of each point to each region. •In the second step, a nested hierarchy of fuzzy partitions is calculated on the basis of a max-min transitive similarity relation between regions. The set of levels of the hierarchy corresponds to the different significant α-cuts of the relation. The similarity relation is calculated on the basis of a resemblance one (degree of compatibility of regions) and using the idea of path between regions. This technique, that incorporates information about the aforementioned characteristics of the transition between regions, is coherent with the one employed between pixels in the previous stage. The rest of the paper is organized as follows: in section 2 the colour information processing used in our approach is described. Section 3 summarizes the proposed methodology to extract the collection of fuzzy regions (first stage). Section 4 describes in detail the proposed hierarchical union of regions (second stage). Finally, some results and the main conclusions are showed in sections 5 and 6 respectively. 2 Colour processing An important aspect to take into account in image segmentation is the colour information processing. The most common solutions in the literature are (i) combining the information of each band into a single value before processing (for example, the gradient), or (ii) analyzing each band separately and then combining the results (for example, histogram analysis of each band and subsequent combination). Apart from the difficulty to choose an adequate criterion to pool the data, also appears the problem of the fuzziness associated with the own definition of the color spaces, 104 J. Chamorro-Mart´ınez et al. which some techniques like [11] try to solve by modeling the human perceptual system. However there is still a problem to work out in above mentioned solutions: they apply the same combination rule to the whole image, without considering the particularities that appear in the comparison of two colours. That problem is more significant in methods, like those based on region growing, where the decision in each step depends on the difference between pixels. To process the colour information, we propose a methodology based on a distance between colours defined within a perceptual color space. Although the RGB is the most used model to acquire digital images, it is well known that it is not adequate for colour image segmentation. Instead, other colour spaces based on human perception (HSI, HSV, CIE(L∗a∗b∗), etc. ) seem to be a better choice for this purpose [12]. In this paper, the CIE(L∗a∗b∗) colour space is used. This colour model has been developed on the basis of observer’s judgements and it provides a measure of the perceived difference between colours. Specifically, it is based on Munsell’s uniform space [13] and it is given by the quantities L∗,a∗and b∗defined as: L∗= 116fY Yn−16 a∗= 500 hfX Xn−fY Yni b∗= 200 hfY Yn−fZ Zni (1) where f(x) = x1 3if x > 0.008856 7.787x+16 116 otherwise (2) with X,Yand Zbeing the tristimulus coordinates of the represented colour, and Xn,Ynand Znthe tristimulus values of the white colour [13]. In this space, the L∗value is a measure of the lightness, while a∗and b∗define together the hue and saturation of the color. Specifically, the a∗axis runs from red to green, and the b∗ axis from yellow to blue. Distance between colours In order to determine how different are two given colours we propose the following measure: Definition 2.1 The difference between two colour stimuli pand q, each given in terms of L∗,a∗,b∗, is: 4C∗(p, q) = q(4L∗)2+ (4a∗)2+ (4b∗)2(3) For the sake of simplicity, we have left out the spatial parameters (x, y) in the notation p(x, y). This Euclidean distance within the CIE(L∗a∗b∗) colour space is related to the perceptual difference measured by human observers [13]. Segmenting Colour Images on the Basis of a Fuzzy Hierarchical Approach 105 3 Extracting initial fuzzy regions In this section, a method to obtain an initial set of fuzzy regions, noted as e Θ = ne R1,e R2,..., e Rmo, is proposed. Firstly, a technique to calculate a collection of seed points, noted as Θ = {r1, r2,...,rm}, is outlined in section 3.1. Secondly, a method to fuzzify that set of seed points is proposed. For this purpose, a membership function for fuzzy regions is defined (section 3.3) based on a distance between pixels (section 3.2). 3.1 Seed points In order to select areas that hopefully may correspond to structural units, seed regions will be located in the local minima of the image defined by the equation 4I(p) = min {4C∗(p, q), q ∈Wr(p)} where Wr(p) represents the neighborhood of pdefined as the set of pixels contained in a window of size r×rcentered at p. Let us remark that 4I, and consequently the seed point selection method, is defined on the basis of the colour-difference formula 4C∗(equation 3) within the CIE(L∗a∗b∗) colour space. In this paper, r has been fixed to 3 and the local minima have been calculated over a window of size 7 ×7. It would be desirable for each object in the image to contain a single seed, but this is not often the case. Indeed, it is usual to find several seeds into the same object (which implies an overload of regions). To solve this problem, some authors propose to discard seeds during the segmentation process on the basis of some criterion. Apart from the difficulty to choose that criterion, this solution could eliminate seeds corresponding to zones of interest. In general, the main problem is that the number and size of regions depend on the precision level we consider when looking at images. As we shall show in section 4, we face this problem on the basis of a hierarchical union of regions. 3.2 Distance between pixels Our target now is to define a measure of how different are two pixels, taking into account not only their colour, but also including information about the topology of the area separating them. For this purpose we use information about the path joining them, having a path defined as follows: Definition 3.1 A path between two pixels pand qis a sequence πpq = (r0, r1,...,rk) where k≥1such that r0=pand rk=qand riis connected to ri+1 ∀i∈ {0,...,k−1}. We will note Qpq to the set of possibles paths linking the pixels pand qthrough pixels of the image Ias Qpq . 106 J. Chamorro-Mart´ınez et al. Definition 3.2 The cost of a given a path πpq ∈Qpq, is defined as the greatest distance between two consecutive points on the path: cost(πpq ) = max {4C∗(ri, ri+1)/ ri, ri+1 ∈πpq}(4) where riand ri+1 are two consecutive points of πpq, and 4C∗is defined in equation (3). Taking it into account, we can define the optimum path between pand qas the path that links both points with minimum cost, in the following way: Definition 3.3 The optimum path between pand qis: π∗ pq =argmin πpq ∈Πpq {cost(πpq )}(5) Based on this optimum path, we can get the measure of the distance between two pixels as shown in this definition: Definition 3.4 The distance between two pixels pand qas the cost of the optimum path from pto q: d(p, q) = cost(π∗ pq) (6) Let us remark that the distance defined in (6) uses topographic information (paths linking the pixels) and distances between colours. In addition, it is sensitive to the presence of edges in the following sense: if the optimum path linking two points p and qpass through an edge (that is, a point which separates two regions), its cost, and consequently the distance between pand q, will be increased. That is because of the fact that there are consecutive points, in the portion of the path that cross over the edge, with a high distance between them. 3.3 Membership function for fuzzy regions Since we have fuzzy regions, it is necessary to define a measure that indicates the degree in which each pixel in the image belongs to each region. For this purpose, we introduce a membership function associated to each region, which definition is the following: Definition 3.5 The membership degree µf Rs(p)of a pixel pto a fuzzy region f Rs is: µf Rs(p) = 1 −d(p, rs) M(7) where rs∈Θ is the seed point of f Rs, and Mis a normalization factor given by M= max {d(q, rs), q ∈I}(8) Using equation (7) we can calculate the membership degree of every point p∈ Ito each region f Rs. This allows us to obtain the set of fuzzy regions e Θ = ne R1,e R2,..., e Rmofrom the set of seed points Θ = {r1, r2,...,rm}. An algorithm to calculate e Θ is proposed in [3] with a computational complexity of O(mn), where nis the number of pixels of the image Iand mis the number of seeds. Segmenting Colour Images on the Basis of a Fuzzy Hierarchical Approach 107 4 Hierarchical union of fuzzy regions In the previous section we have described a methodology to get an initial fuzzy segmentation. In this section we are going to use a similar approach to provide a methodology to perform a hierarchical union of regions on the basis of their resemblance and a given precision degree. 4.1 Resemblance relation Since our target is to join regions, it is necessary to introduce a measure to determine how similar they are, and therefore whether they can be joint or not. To obtain this measure, we introduce the following resemblance relation: Definition 4.1 The fuzzy resemblance relation Rese Θbetween fuzzy regions in e Θ, Rese Θ:e Θ×e Θ→[0,1] is Rese Θ(f Rs,f Rt) = max p∈I{min[µf Rs(p), µf Rt(p)]}(9) Definition 4.2 Connected regions: We say that two regions are connected iff Rese Θ(f Rs,f Rt)>0. This means that two regions are so similar as the highest membership value of the pixels belonging to both regions. Since the value Rese Θ(f Rs,f Rt) is a measure of the compatibility degree between f Rsand f Rt, the resemblance between regions plays the same role as the distance between pixels, i.e., they give us information to make a decision about when to join them together into a single region. It is easy to show that Rese Θis reflexive (since the membership function of every fuzzy region is normalized), and symmetric. A limitation of this fuzzy relation is that it considers only those pixels that are in the intersection of the support of both fuzzy regions. However, as in the case of individual pixels, we should take into account the idea of continuity, in the sense that given two regions f Rsand f Rt, we could find a chain of connected regions from f Rsto f Rtsuch that the minimum similarity between consecutive regions is greater than Rese Θ(f Rs,f Rt). An example is a gradation like that in figure 2. In such a case, assuming that the resemblance between connected regions is the same, it seems that there are only two possibilities to build a nested hierarchy: to join all the regions or to keep them all separate. Seeming natural, these decisions cannot be adopted if we use Rese Θ. As a conclusion we think that, in general, we should take into account topographic information when determining the relation between regions. 4.2 Similarity relation To comply with the notion of continuity, we have defined a similarity relation following the same idea used for distance between individual pixels, i.e., to find 108 J. Chamorro-Mart´ınez et al. paths of regions and to calculate the similarity between a given pair of regions as the minimum similarity of consecutive pairs of regions in any path linking them. So we first need to precise what a path between regions is: Definition 4.3 A path between regions f Rsand f Rtis a sequence ω=g Rr1,g Rr2,...,g Rro with o≥2such that g Rr1=f Rsand g Rro=f Rt, and g Rrkis connected to ^ Rrk+1 ∀k∈ {1,...,o−1}. Having a path between regions defined as a chain of consecutive and non repeated regions, we can get the set of all the possible path joining regions in the image, that we will note as Ω e Θ, where e Θ is the set of all regions in the image. Following this notation Ω e Θ st ⊆Ω e Θwill be the set of paths between regions f Rsand f Rt. Since the definition of the similarity relation needs to select just one of all the paths joining two regions, we introduce a measure to compare all of them and find the optimum path: path’s benefit, defined as follows: Definition 4.4 The benefit of a path ω∈Ω e Θis ben(ω) = min k∈{1,...,o−1}Rese Θ(g Rrk, ^ Rrk+1 ) (10) This measure has a similar meaning to the cost defined for pixels, with the difference that benefit represents similarity, while cost indicates dissimilarity. The benefit of a path is the similarity degree between the first and the last region of the path, as given by the sequence of similarities of connected regions. If the path is cyclic (i.e. ∃k < l such that g Rrk=g Rrl) it is always possible to find a path with better (or equal in the worst case) benefit by deleting the regions from kto l−1 from the path. Taking it into account we define the similarity degree between two regions as the benefit of the optimum path joining them. Definition 4.5 We introduce the fuzzy similarity relation Sime Θbetween fuzzy regions in e Θto be Sime Θ(f Rs,f Rt) = max ωst∈Ω e Θ st {ben(ωst)}(11) if Ω e Θ st 6=∅, and 0 otherwise. Some of the properties verified by this fuzzy similarity relation are the following: Proposition 4.1 Sime Θis reflexive. Proof 4.1 Rese Θis reflexive, so for every f Rk∈e Θthere is a path f Rk,f Rkwhose benefit is 1. Hence, Sime Θ(f Rk,f Rk) = 1. Segmenting Colour Images on the Basis of a Fuzzy Hierarchical Approach 109 Proposition 4.2 Sime Θis symmetric. Proof 4.2 Rese Θis symmetric, and the calculation of Sime Θfrom Rese Θinvolves symmetric functions only (maximum and minimum, see equations 10 and 11) so Sime Θis symmetric. Proposition 4.3 Sime Θis max-min transitive, i.e. Sime Θ(f Rs,f Rt)≥max f Ru∈ e Θ min{Sime Θ(f Rs,f Ru), Sime Θ(f Ru,f Rt)}(12) Proof 4.3 Let f Ru∈Θ, we shall show that Sime Θ(f Rs,f Rt)≥min{Sime Θ(f Rs,f Ru), Sime Θ(f Ru,f Rt)} Let ωsu be the maximum benefit path between f Rsand f Ru, and let ωut be the maximum benefit path between f Ruand f Rt. Let ωst be the concatenation of paths ωsu and ωut. Then ben(ωst) = min{Sime Θ(f Rs,f Ru), Sime Θ(f Ru,f Rt)} Also it is obvious that ωst ∈Ω e Θ st, and by equation (11) Sime Θ(f Rs,f Rt) = max ω∈Ω e Θ st {ben(ω)} ≥ ≥ben(ωst) = min{Sime Θ(f Rs,f Ru), Sime Θ(f Ru,f Rt)} It is well known that any α-cut of a max-min transitive similarity relation is a crisp equivalence relation. In particular, any α-cut of Sime Θ, noted Sime Θα, is a crisp equivalence relation in e Θ. In the following section, we shall use this property to obtain a hierarchy of nested fuzzy segmentations. 4.3 Hierarchical segmentation From Sime Θwe shall obtain a hierarchy of nested fuzzy segmentations He Θ= {e Θ1,...,e Θm}, where the segmentation asociated to each level of granularity is given by the set e Θi={f Ri 1,...,g Ri ni}with f Ri k∈e℘(I) a fuzzy region. The number of granularity levels, m, will be equal to the number of significant αlevels of Sime Θ, i.e., the number of different similarity degrees between regions in e Θ [15]. The set with all the possible values of the parameter αis: ΛSime Θ={α1,...,αm} where α1=1,αm= min nSime Θf Rs,f Rt|f Rs,f Rt∈e Θo, and αi> αi+1 ∀i∈ {1,...,m}.