=Paper=
{{Paper
|id=Vol-1348/maics2013_paper_13
|storemode=property
|title=New HSL Distance Based Colour Clustering Algorithm
|pdfUrl=https://ceur-ws.org/Vol-1348/maics2013_paper_13.pdf
|volume=Vol-1348
|dblpUrl=https://dblp.org/rec/conf/maics/Patrascu13
}}
==New HSL Distance Based Colour Clustering Algorithm==
https://ceur-ws.org/Vol-1348/maics2013_paper_13.pdf
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 cosH 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.