Image Quantisation using KM and KHM Clustering Techniques with Outlier-Based Initialisation

) colour spaces and additionally by the loss of colourfulness ( $\Delta M$ ).

1 Introduction

True colour images acquired by a camera contain only a small subset of all possible 16.7 million colours. Therefore, it makes sense to further reduce the number of colours in the image. Nowadays, the colour image quantisation (CIQ) is an important auxiliary operation in the field of colour image processing and is very useful in image compression, image pre-segmentation, image watermarking and content-based image retrieval (CBIR). These algorithms are also still used to present the true colour images on devices with limited number of colours. CIQ reduces significantly the number of colours in the image to the specially selected set of representative colours (colour palette). Colour palette generation is the most important step in any CIQ method. Proper choice of the colour palette helps minimize the colour difference between the original image and the quantised image.

There exist two main classes of CIQ techniques: splitting techniques and clustering techniques [1]. The splitting techniques divide the colour space into smaller disjoined subspaces and then a colour palette is built by choosing representative colours from these subspaces. Good examples of such techniques are the Median Cut [8], Octree [5] and Wu’s [16] algorithms. For example, the Median Cut method first locates a tightest box in RGB colour space, that encloses all image colours. Then, the box is cut on the longest side and two subboxes are formed. As a result of a such cut both subboxes should contain the same number of colours and from here comes the name of the method. Next, a subbox with longest side is cut. This process continues until the total number of subboxes is smaller than the number of colours in the palette chosen for the quantised image. All colours in one subbox are represented by their mean value.

On the other hand, the clustering techniques are the optimization tasks that minimize the quantisation errors by minimization the sums of distances between the cluster centres and cluster points. One of the most popular clustering techniques is the K-means (KM) technique [10] and its existing modifications e.g. K-harmonic means (KHM) technique [19]. The clustering has a long tradition of use to quantize colour images [18]. It can be easily to see that each of the dominant colours in natural image corresponds to a separate fragment of pixels cloud in the colour space, which can be called a cluster (Fig. 1). As a generally statement, it may be found that the splitting techniques are faster than the clustering techniques but they have larger quantisation errors.

Fig. 1

Simple colour image and its clusters in RGB colour space

The results of many clustering techniques depend on method of determination of initial cluster centres, used colour space, applied colour metric etc. Such sensitivity to initialisation is an important disadvantage of these clustering techniques. A random selection of the initial centres, used in classical KM version, is not able to achieve repeatable results in colour image quantisation. Therefore, in our previous paper [3] we attempted to use two new heuristic methods of initialisation. The first method, which is an arbitrary one, is based on uniform partitioning of diagonal of RGB cube (DC) into k segments. Gray levels in the middle of segments are used as initial centres. If an image is clustered into k clusters, k initial cluster centres are located on the gray level axis. The second method, which is an adaptive one, uses a size of pixel cloud of a colour image and the method has been marked as SD. First, the mean value and standard deviation (SD) for each RGB component of all image pixels are calculated. Then, around the point of mean colour (a pixel cloud centre) a rectangular cuboid with sides equal $2\sigma _R$ , $2\sigma _G$ and $2\sigma _B$ is constructed. We assume that it lies within the RGB cube. Next, the main diagonal of the cuboid is divided into k equal segments. The centres of these segments are used as initial cluster centres. Initial cluster centres in KM can also come directly from splitting algorithms e.g. from MC or Wu’s algorithms and such combined approach (MC+KM, Wu+KM) was proposed few years ago [14]. Experiments have shown that Wu+KM technique offers a slightly better performance than MC+KM and KM initialised by SD approach.

Appropriate initialisation provides the high quality clustering achieved by running small number of iterations and avoids the formation of empty clusters, which sometimes occurs in the case of DC initialisation. The result of empty clusters is a reduction in the number of colours in quantised image. Removing empty clusters needs changing the cluster centres or splitting a newly created cluster. Good initialisation for the KM technique, used in colour quantisation, is still looked for by many researchers [2].

The KHM is based on harmonic means, instead of arithmetic means and additionally uses fuzzy membership of pixels to clusters and dynamic weight functions, what means different influence an individual pixel on calculating new values of centres in each iteration. KHM is robust to initialisation and creates non-empty clusters. A disadvantage of KHM in relation to KM is greater computational complexity, resulting in a longer computation time.

The clustering process can be conducted not only in the RGB colour space, but also in other colour spaces. Here a special role is played by recommended in 1976 the CIELAB colour space [17]. It is a perceptually uniform colour space which approximately expresses a way of human colour perception. The Euclidean distance in this space is approximately equal to the perceptual colour difference. This should be of great importance in the process of clustering. Unfortunately, the transform from RGB to CIELAB is complicated and nonlinear.

The YCbCr colour space is applied in CIQ task among other used colour spaces. Its advantage, in comparison to CIELAB colour space, is a linearity of transformation from RGB space, which results in faster calculation of the YCbCr components. Although the colour difference in the YCbCr space less corresponds to the human colour perception than the colour difference calculated in CIELAB, however makes it better than the Euclidean distance calculated in RGB space. The YCbCr components can be received from the following transformation [9]:

(1)

$$Cb = -0.148R - 0.291G + 0.439B + 128$$

(2)

(3)

Therefore, later in this chapter, are tested the CIQ methods in the following colour spaces: basic RGB, YCbCr and perceptually uniform CIELAB.

This chapter is organized as follows. In Sect. 2, we present two typical and one untypical quality measures used for CIQ quality evaluation. The results of experimental tests for determination of factors influencing the quantisation errors are described in Sect. 3. The idea of the new proposed initialisation method (modified Mirkin’s algorithm) is illustrated on several images in Sect. 4. Section 5 shows on a larger set of images a usefulness of a new MM initialisation in quantisation process, which is oriented toward image segmentation. Finally we conclude the chapter in Sect. 6.

2 CIQ Quality Measures

The colour quantisation error depends on the number of colours in palette (e.g. 256, 64, 16, 8, 4 colours): the smaller number of colours in palette, then larger is the quantisation error. Objective CIQ quality measures (Fig. 2) are very important in the evaluation process of different colour quantizers.

Fig. 2

The general idea of CIQ quality measure

Commonly used most popular measure is the Mean Squared Error (MSE) defined by:

$\mathit{MSE} = \frac{1}{\textit{3MN}}\sum\limits_{i = 1}^M {\sum\limits_{j = 1}^N {\left[ {{{({R_{ij}} - R_{ij}^*)}^2} + {{({G_{ij}} - G_{ij}^*)}^2} + {{({B_{ij}} - B_{ij}^*)}^2}} \right]} }$

(4)

where M and N are the image dimensions in pixels, R _ij, G _ij, B _ijare the colour components of the pixel at location $(i,j)$

in the original image and $R_{ij}^*$ , $G_{ij}^*$ , $B_{ij}^*$ are the colour components of the pixel in quantised image. The smaller the MSE value, the better is the quantised image. Other error measure applied to evaluation of quantisation is Peak Signal-to-Noise Ratio (PSNR), good correlated with MSE value and expressed in decibel scale:

$\mathit{PSNR} = 20{\log _{10}}\frac{255}{\sqrt{\mathit{MSE}}}$

(5)

Unfortunately, these both measures that come from the signal processing field are poorly correlated with subjective visual quality of an image. The quantisation error can be treated as a colour error that should be determined in a perceptually uniform colour space. Therefore, an average colour difference in CIELAB colour space ( $\Delta E$ ) is sometimes applied as a quantisation error:

$\Delta E = \frac{1}{MN}\sum\limits_{i = 1}^M \sum\limits_{j = 1}^N {\sqrt{(L_{ij} - L_{ij}^*)^2 + {(a_{ij} - a_{ij}^*)}^2 + (b_{ij} - b_{ij}^*)^2}}$

(6)

where: L _ij, a _ij, b _ijare the colour components of the pixel at location $(i,j)$

in the original image and $L_{ij}^*$ , $a_{ij}^*$ , $b_{ij}^*$ are the CIELAB colour components of the pixel in the quantised image. Also the loss of image colourfulness due to colour quantisation can be used as an additional tool for evaluation of quantisation error [13].

$\Delta M = \left| {{M_{orig}} - \,{M_{quant}}} \right|$

(7)

where: M _orig– colourfulness of the original image, M _quant– colourfulness of the quantised image. Formulas for computing of image colourfulness are simple and good correlate with the perceptual colourfulness of the image [6]:

$M = \sqrt{\sigma _{rg}^2 + \sigma _{yb}^2} + 0.3 \times \sqrt{\mu _{rg}^2 + \mu _{yb}^2}$

(8)

where $\sigma _{rg}$ , $\sigma _{yb}$ are the standard deviations and $\mu _{rg}$ , $\mu _{yb}$ are the mean values of opponent colour components of the image pixels. The opponent components are approximated by following simplified equations:

$rg = \;R - G$

(9)

$yb = \;0.5(R + G) - B$

(10)

where rg – red-green opponency and yb – yellow-blue opponency.

It should be noted here that a common drawback of all these quality measures based on colour similarity is that they compare the images by using pixel to pixel comparison, without taking into account an impact of neighbouring pixels on the perception of colour of considered pixel. The additional factors, defining the quality of quantised image can include the edge similarity and structural similarity [7]. In this paper a new quality measure as a combination of all three similarities was proposed. However, in many cases the human visual system is the best final judge of quality of quantised image (subjective quality measures).

3 Preliminary Experimental Tests

A set of five natural images has been randomly chosen from Berkeley’s image database [11] and presented in Fig. 3 in order of their number of unique colours. All these images were acquired at the same spatial resolution, i.e. 481×321 pixels. First tests were conducted to show that the larger unique number of colours in the original image, the larger also quantisation errors for a given size of the palette (here eight colours). The number of iterations in used clustering techniques was equal to 15 and the quantisation was realised by KM and KHM techniques in the RGB colour space. The data in Table 1 shows the error values for KM technique with two different initialisations: DC and SD. Similarly, Table 2 contains error values calculated for more efficient KHM technique. It should be noted that in both cases with the decreasing numbers of unique colours in images in Fig. 3 generally decreases the values of quantisation errors, i.e. increases PSNR and decrease $\Delta E$ and $\Delta M$ . A similar effect also occurs for two tested splitting algorithms: MC and Wu’s (see Table 3).