New HSL Distance Based Colour Clustering Algorithm Vasile Patrascu Departement of Informatics Technology, Tarom Company Calea Bucurestilor 224F, Bucharest, Romania, e-mail: patrascu.v@gmail.com Abstract when the luminosity is taken into account in the distance In this paper, we define a distance for the HSL colour system. Next, formula, there are arising situations when two colours are the proposed distance is used for a fuzzy colour clustering placed in different clusters because of the difference between algorithm construction. The presented algorithm is related to the their luminosities despite of their strong similarity in the well-known fuzzy c-means algorithm. Finally, the clustering chromatic space HS . algorithm is used as colour reduction method. The obtained experimental results are presented to demonstrate the effectiveness In this paper, we propose a distance that minimizes the two of our approach. disadvantages mentioned above. This distance is constructed as a quasi-linear combination of the three standard distances of H , S , L scalar components. Next, this distance is used for Introduction a fuzzy colour clustering construction. In the following sections, the paper is thus organized: section A colour image generally contains tens of thousands of 2 presents the particular form of the system HSL used in this colours. Therefore, most colour image processing paper; section 3 presents the new colour distance; section 4 applications first need to apply a colour reduction method presents the colour clustering algorithm based on the before performing further sophisticated analysis operations proposed distance and related to the fuzzy c-means such as segmentation. The using of colour clustering algorithm; section 5 presents some experimental results algorithm could be a good alternative for colour reduction while section 6 outlines the conclusions. method construction. In the framework of colour clustering procedure, we are faced with two colour comparison subject. The Perceptual Colour System HSL We want to know how similar or how different two colours are. In order to do this comparison, we need to have a good The most part of the colour images are represented by the coordinate system for colour representation and also, we RGB colour system. However, this space presents the need to define an efficient inter-colour distance measure in following two important limitations: the difficulty to the considered system. determine colour features like the presence or the absence of In this paper we will consider the particular case of colour a given colour, and the inability of the Euclidean distance to representation by the perceptual system HSL (hue, correctly capture colour differences in the RGB space. saturation and luminosity) (Smith 1978). The obtained Starting from the RGB system, there were defined other degree of similarity or dissimilarity is dependent on the used systems for colour representation. One of them is the HSL inter-colour distance (Carron 1995), (Lim et al. 1990), system where H is the hue, S is the saturation and L is (Sarifuddin et al. 2005), (Trivedi et al. 1986). In the HSL the luminosity. Colour space HSL is also commonly used in colour comparison procedure, the three colour components image processing. As opposed to RGB system, HSL is have not the same importance. Thus, the most important is considered as natural representation colour system. The the hue, the saturation is the next and finally, the luminosity HSL system belongs to the perceptual system category is less important. Because of this reason, we can define some because it is very close to the human colour perception. In colour clustering methods that use the bi-dimensional space the HSL system, colour is decomposed according to HS . On this way, it is neglected the third component, the physiological criteria like hue, saturation and luminosity. luminosity. This method is very good for those images that Hue refers to the pure spectrum colours and corresponds to are quite saturated. In the same time, this method has the dominant colour as perceived by human. Saturation disadvantage of supplying erroneous clusters for the less corresponds to the relative purity or the quantity of white saturated colours because it does not take into account the light that is mixed with hue while luminosity refers to the achromatic component, the luminosity. On the other side, amount of light in a colour (Gonzales et al. 2007). A great advantage of HSL system over the RGB lies in its capacity    2  to recognize the presence of colours in a given image. d 2 (1,2 )  sin 2  1   2  There exist many formulae for H , S , L components d 2 ( 1,  2 )  ( 1   2 ) 2 calculation. For the hue H , the most part of the definitions are closed to the following formula that uses the atan2 function (ECMA-262 2011): d 2 (l1, l2 )  (l1  l2 ) 2  B  G 2R  B  G  The coordinate system HSL is a cylindrical one and for two H  atan2 ,   (1) colours Q1  ( H1 , S1 , L1 ) and Q2  (H 2 , S 2 , L2 ) , the  2 6  Euclidean distance becomes (Gonzales et al. 2007): and H  ( ,  ] . For the luminosity calculation, in this paper, the following DE2 (Q1, Q2 )  4S1S2  d 2 ( H1, H 2 )  d 2 ( S1, S2 )  (4) formula will be used (Patrascu 2012):  d 2 ( L1, L2 ) M L (2) The colour Euclidean distance DE has three terms: the 1 M  m where distance between hues, the distance between saturations and M  max(R, G, B) the distance between luminosities. The distance between hues is multiplied by a factor that depends on the colour and saturations. This factor has a multiplicative structure. Thus, m  min(R, G, B) . when the saturation values increase, the hues distance Regarding to the saturation calculation, many variants are influence increases in framework of distance DE . When the defined by the distance between max(R, G, B) and saturation values decrease, the hue distance influence min(R, G,.B) . In this paper, we will use for saturation decreases. calculation, the following formula (Patrascu 2009): From here, the idea to multiply the luminosity distance with a similar factor comes up. This factor will have the following 2(M  m) behaviour: when the saturation values increase, the S (3) 1 | M  0.5 |  | m  0.5 | luminosity distance influence decreases and when the saturation values decrease, the luminosity distance influence We suppose R, G, B [0,1] and it results that increases. We can generalize (4) using two real and positive M , m, S , L [0,1] . parameters  and  , by the following: The New HSL Colour Distance DP2 (Q1 , Q2 )    d 2 ( H1 , H 2 )    d 2 ( L1 , L2 )  (5) In the Cartesian coordinate system ( x, y, z )  R 3 , for two  d 2 ( S1 , S 2 ) vectors v1  ( x1 , y1 , z1 ) , v2  ( x2 , y2 , z 2 ) one defines the The parameter  will be related to the colour chromaticity Euclidean distance by: while the parameter  will be related to the colour achromaticity. Before the construction of parameters  and D E2 (v1 , v 2 )  ( x1  x 2 ) 2  ( y1  y 2 ) 2  ( z1  z 2 ) 2  , we define the index of chromaticity c and the index of achromaticity a , having the following properties: In order to obtain the variant of Euclidean distance for the cylindrical coordinate system, we use the following  index of chromaticity substitution: c : [0,1]  [0,1] , (i) c(0)  0 x   cos( ) , y   sin( ) , z  l . It results: (ii) c(1)  1 (iii) S1 , S 2  [0,1] , D E2 (v1 , v 2 )  4 1  2  d 2 (1 ,  2 )  d 2 ( 1 ,  2 )  d 2 (l1 , l 2 ) if S1  S 2 then c( S1 )  c( S 2 ) . were: We will use for the chromaticity index the following particular function: The membership function wij is calculated using formula c( S )  S (6) (13), where the distance DP is calculated with formula (12).  index of achromaticity i  [1, n]  , a : [0,1]  [0,1] , j  [1, k ] (i) a(0)  1 , (ii) a(1)  0 . wij  1 (13)   2 (iii) S1 , S 2  [0,1] , k  D Q , q   1 1     P i j if S1  S 2 then a(S1 )  a(S 2 ) . m 1  D P Qi , q m    m j We will use for the achromaticity index the following particular function: The functions wij verify the condition of the partition of unity, namely: a( S )  1  S (7) i [1, n] , wi1  wi 2  ...  wik  1 The two parameters  and  will have a multiplicative structure. Thus,  will be a product of chromaticity indexes, The cluster center components h j , s j , l j  are calculated while  will be a product of achromaticity indexes. It with formulae (14), (15) and (16). results: j  [1, k ] ,   c(S1 )  c(S 2 ) (8)  n  n    a(S1 )  a(S 2 ) (9)   wij C i  sin H i   wij C i  cosH i     h j  atan2 i 1 , i 1  (14) Using (6), (7), (8) and (9) for the two multipliers  and  ,  n  n     wij Ci  wij Ci  it results the following particular forms:  i 1 i 1    S1  S 2 (10) with Ci  S i .   1  S1  1  S 2 (11) j [1, k ] , The distance (5) becomes: n  H  H2  D P2 (Q1 , Q2 )  S1  S 2 sin 2  1    wij Ai  Li  2  (12) l j  i 1 (15) n   (1  S1 )  (1  S 2 )  ( L1  L2 )  ( S1  S 2 ) 2 2  wij Ai i 1 The Colour Clustering Algorithm with Ai  1  S i . Let there be n colours Q1 , Q2 ,...,Qn that must be clustered n into k sets. Each cluster j is characterized by the  wij  S i membership coefficients w j1 , w j 2 ,..., w jn for the considered j  [1, k ] , s j  i 1 (16) n  n colours and the cluster center defined by the colour  wij   q j  h j , s j , l j . For colour clustering, we will construct an i 1 algorithm that is similar to the fuzzy c-means algorithm (Bezdek 1981). where  is a fuzzification-defuzzification parameter and also,   (1,1.5). Experimental Results We have applied this method to images: “red-green” (figure 1a), “flower” (figure 2a), “house” (figure 3a), “parrots” (figure 4a) and “bird” (figure 5a). The clustered images obtained using the new distance can be seen in figures 1b, 2b, 3b, 4b, 5b and those obtained using the Euclidean distance can be seen in figures 1c, 2c, 3c, 4c, 5c. Figure 1a shows a synthetic image. Using the proposed distance, it was obtain the 3-colour representation shown in figure 1b while figure 1c shows the image obtained using the Euclidean distance. In the first case, the black region has a small area, while in the second case, it has a large one. This fact proves the influence of achromatic parameter that was used in the proposed distance. In the case of image “flower”, using the Euclidean distance it was obtained two clusters for background. These two clusters have the same hue but the luminosities are different (a) (figure 2c). Using the proposed distance, one obtained only one cluster for the entire background (figure 2b). For image “house”, using the Euclidean distance, the white and bright blue colours were not separated (figure 3c). In the case of image “parrots”, the yellow and red colours were not separated (figure 4c) and the clustering is different from that obtained using the proposed distance (figure 4b). For the image “bird”, using the Euclidean distance, the orange and grey colours were not separated (figure 5c). The experimental results illustrate that our distance performs well compared to Euclidean distance. In the same time, the obtained results show the helpfulness of using this novel inter-colour distance measure in colour clustering algorithms. (b) Conclusions In this paper one presents an enhancement of fuzzy c-means algorithm for the particular case of colour clustering. It was used the perceptual colour system HSL for colour representation. The main step is represented by definition of a new distance in the HSL colour space. In this construction, there were used two multipliers that make the balance between the hue weight and luminosity weight in the framework of this three-term colour distance. We can conclude that the new inter-colour distance “ DP ” defined by (12), the two multipliers “  ” defined by (8) and “  ” defined by (9), the particular form of index of chromaticity “ c ” defined by (6) and achromaticity “ a ” defined by (7) construct a new and useful framework for colour clustering (c) procedures. The obtained experimental results were compared with those obtained by using the Euclidean Figure 1: The image „red-green” (a) and its 3-colour distance. This comparison shows the efficiency of the representation based on proposed HSL distance (b) and proposed clustering algorithm using for the colour reduction based on HSL Euclidean distance (c). method. (a) (a) (b) (b) (c) (c) Figure 2: The image „flower” (a) and its 3-colour Figure 3: The image „house” (a) and its 6-colour representation based on proposed HSL distance (b) and representation based on proposed HSL distance (b) and based on HSL Euclidean distance (c). based on HSL Euclidean distance (c). (a) (a) (b) (b) (c) (c) Figure 4: The image „parrots” (a) and its 6-colour Figure 5: The image „bird” (a) and its 4-colour representation based on proposed HSL distance (b) and representation based on proposed HSL distance (b) and based on HSL Euclidean distance (c). based on HSL Euclidean distance (c). References Bezdek, J. C. 1981. Pattern Recognition with Fuzzy Objective Functions, New York: Plenum Press. Carron, A. T. 1995. Segmentation d'images couleur dans la base Teinte Luminance Saturation: approche numérique et symbolique, PhD Thesis, Université de Savoie. ECMA-262, 2011. ECMAScript® Language Specification, www.ecma-international.org/publications/standards/Ecma- 262.htm. Gonzalez, R. C.; Woods, R. E. 2007. Digital Image Processing. Prentice Hall. Lim, Y. W. S.; Lee, U. 1990. On the colour image segmentation algorithm based on the thresholding and the fuzzy c-means techniques, Pattern Recognition, volume 23, no.9, 935-952. Patrascu, V. 2009. New fuzzy color clustering algorithm based on hsl similarity. In Proceedings of the Joint 2009 International Fuzzy Systems Association World Congress (IFSA 2009), Lisbon, Portugal. Patrascu, V. 2012. Fuzzy Membership Function Construction Based on Multi-Valued Evaluation, in vol. Uncertainty Modeling in Knowledge Engineering and Decision Making, Proceedings of the 10th International FLINS Conference (FLINS 2012), Istanbul, Turkey, World Scientific Press, 756-761. Smith, A. R. 1978. Colour Gamut Transform Pairs, Computer Graphics 12 (2). Sarifuddin, A. M.; Missaoui, R. 2005. A new perceptually uniform colour space with associated colour similarity measure for content based image and video retrieval, In Proceedings of Multimedia Information Retrieval Workshop, 3-7. Trivedi, A. M.; Bezdek, J. C. 1986. Low-level segmentation of aerial images with fuzzy clustering, IEEE Trans. On Systems, Man, and Cybernetics, volume. 16, no. 4, 589-598.