K-Means Color Image Quantization with Deterministic Initialization: New Image Quality Metrics

Abstract

Color image quantization is used in several tasks of color image processing as an image segmentation, image compression, image watermarking, etc. In this paper we consider four traditional (MSE, PSNR, DE76 and DM) and four new perceptual metrics (DSCSI, HPSI, MDSIs and MDSIm) as useful tools for evaluating quantized images. The values of these metrics confirm that Wu’s algorithm can be used as effective deterministic initialization of K-Means method. No empty clusters are produced by this method of quantization. The experiments were realized using 24 benchmark color images for different numbers of quantization levels. The same quantization with additional Floyd-Steinberg dithering generates the images with even better values of tested perceptual metrics.

1 Introduction

Color image quantization is a process of reduction of the number of colors in true color images. Obtaining a small quantization error needs a color palette designed for the particular image. The quantization error depends on the number of colors in the palette (e.g. 8, 16, 32, 64, 128, 256 colors), the method of building a color palette and the pixel classifying technique. The color quantization is still applied to different tasks of computer vision and computer graphics. Among the color quantization methods the splitting techniques, e.g. median-cut (MC) [5], Wu’s algorithm [13] and clustering techniques, e.g. most popular K-Means (KM) technique [8] can be distinguished. The splitting techniques are faster than the clustering techniques, but they give larger quantization errors. KM clustering results depend on the method of initialization, i.e. determining the initial cluster centers. The classic version of KM uses a random choice of initial centers, but in this case we will not have repeated results. Therefore, it makes sense to search for a deterministic initialization, which allows to get a small quantization error. An important issue remains a way to assess this error.

Previous searches for deterministic initializations of KM method were based on the use of heuristic approaches (KMDC, KMSD; see below) or the use of splitting quantization (MC, WU) as KM initialization (KMMC, KMWU). An example of such work is in the article [10]. In it was shown for five benchmark images and using traditional quality metrics (MSE, DE76, DM), that KMWU technique offers a better performance than KM technique with other initializations. In our paper we would like to get an answer to the question: How the four new perceptual metrics assess the investigated initializations of the KM method used for color image quantization?

This paper is organized in four sections. In Sect. 2 we present the traditional and new image quality metrics, which are used for the quality assessment of color quantization. In Sect. 3 we describe the use of four perceptual metrics to evaluate selected splitting and combined KM quantization methods. Finally, the Sect. 4 concludes the paper.

2 Color Quantization Quality Assessment

The most popular and widely used in image processing metric is the MSE, that version for color images is defined as:

$$\begin{aligned} MSE=\frac{1}{{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] \end{aligned}$$

(1)

where MN represents the resolution of the image, $R_{ij}$, $G_{ij}$, $B_{ij}$ are the color value components of the pixel (i, j) in the original image and $R_{ij}^*$, $G_{ij}^*$, $B_{ij}^*$ are the color value components in the same pixel of the quantized image. Another metric applied to color quantization, well correlated with MSE value and usually expressed in decibels is PSNR:

$$\begin{aligned} PSNR=10\log _{10}\frac{255^2}{MSE} \end{aligned}$$

(2)

The quantization error can be treated as a color error calculated on the whole image. From the point of view of the color science, such color error should be determined in a perceptually uniform color space, i.e. CIELAB space. An average color error calculated in the CIELAB color space can be expressed as:

$$\begin{aligned} DE76=\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 } \end{aligned}$$

(3)

where $L_{ij}$, $a_{ij}$, $b_{ij}$ are the color value components of the pixel (i, j) in the original image and $L_{ij}^*$, $a_{ij}^*$ and $b_{ij}^*$ are the CIELAB color value components in the same pixel of the quantized image.

The loss of image colorfulness [4] can be used as an additional measure of quantization error:

$$\begin{aligned} DM = \left| {\,{M_{orig}} - \,{M_{quant}}} \right| \end{aligned}$$

(4)

where $M_{orig}$ and $M_{quant}$ are respectively the colorfulness of the original and quantized images. The formula for computing of image colorfulness is simple and good correlate with perceptual colorfulness of the image:

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

(5)

where $\sigma _{rg}$, $\sigma _{yb}$, $\mu _{rg }$, $\mu _{yb}$ are respectively standard deviations and means of opponent color components calculated on the whole image. The opponent color components are approximated by following simplified equations: $rg = \;R - G$, $yb = \;0.5(R + G) - B$, where rg represents the red-green opponency and yb represents the yellow-blue opponency.

In the last few years many new perceptual image quality assessment (IQA) metrics have been developed. A good example of such metrics is the DSCSI [7], which consists of three steps. The first step is the image transformation from the RGB into the S-CIELAB color space. In a second step, the local features for color similarity are calculated to three color components: hue, chroma and lightness. In this way we obtain the following six features: the hue mean similarity, the hue dispersion similarity, the chroma mean similarity, the chroma contrast similarity, the lightness contrast similarity and the lightness structural similarity. In the third step, these six features are combined into two scores: the chromatic similarity $S_C$ and achromatic similarity $S_A$, which are directly used in the final DSCSI formula:

$$\begin{aligned} Q(I,{I^*}) = {S_A} \cdot {\left( {{S_C}} \right) ^\lambda } \end{aligned}$$

(6)

where I - original image, $I^*$ - distorted image and $\lambda$ is a weighting factor. The smaller the difference between the original and distorted images, the value of DSCSI metric is closer to 1. In papers [2, 11] the usefulness of the DSCSI metric for assessment of color quantization is shown.

Other new perceptual metric is called HPSI (Haar wavelet-based Perceptually Similarity Index) [12]. This metric is based on the coefficients of three stages of a discrete Haar wavelet transform. These coefficients assess the local similarities between two compared images. The six simple 2D Haar wavelet filters to detect horizontal and vertical edges are used. It is built in both local similarity maps (horizontal and vertical) and both weight functions. In addition, a non-linear mapping in the form of the logistic function is introduced in the HPSI computation process. HPSI metric can be considered as a simplified version of the FSIM metric. Also, here the YIQ color space for the generalization to color is used. Discussion on the similarities and differences between HPSI and FSIM can be found in [12].

The last considered metric is named MDSI (Mean Deviation Similarity Index) [9]. Firstly are redefined both gradient and chromaticity similarities. Gradient similarity (GS) represents the local structural distortions and chromaticity similarity (CS) represents the color distortions. These both image features in the form of maps are further pooling by novel deviation technique into a single quality index. Two similarity maps are combined by summation (MDSIs version) or multiplication (MDSIm version). Further details can be found in [9].

In a new paper [2] we considered an application of four above-mentioned perceptual quality metrics for assessment of quantized images. All these perceptual metrics achieved the highest correlation coefficients with Mean Opinion Scores (MOS) after tests on many images, what encourages to choose these metrics for assessment. Statistical analysis of these correlation coefficients showed that the differences between the four perceptual metrics are not statistically significant.

3 The Experiment and Its Results

The experiment was done on 24 Kodak images [6] for the whole range of typical palette sizes k = 8, 16, .., 256. Six quantization methods were tested: MC, WU, KMDC, KMSD, KMMC and KMWU. The results of quantization with dithering by Floyd-Steinberg method [1] were also included as KMWU+FS. More on the properties of FS dithering can be found in the paper [11]. The values of individual metrics (averages for 24 images) are given in Tables 1, 2 and 3. The best result for each metric is bolded. Due to limited space of this paper we do not present results for k = 16, 32, 128. These results were very similar to the presented here results.

Table 1. Average values of quality metrics of quantized Kodak images ($k=8$)

Table 2. Average values of quality metrics of quantized Kodak images ($k=64$)

Table 3. Average values of quality metrics of quantized Kodak images ($k=256$)

The results in Tables 1, 2 and 3 show that adding dithering to KMWU color quantization improves the values of four perceptual quality metrics and achieves the best results. The DM metric behaves similarly to perceptual metrics. By the contrast, the values of three classic metrics (MSE, PSNR, DE76) then get worse. If you do not use dithering, then the KMWU continues to quantize images with results evaluated as the best by all eight metrics. Exceptions are the results for $k=8$ where KMWU is indicated by the half of metrics.

Table 4. Average computation time for quality metrics

In addition, it was verified that the best initialization method does not generate the empty clusters, i.e., the number of colors obtained after quantization is always equal to k. This is not the case for KMDC and KMSD initializations. Finally, the calculation times for eight quality metrics were compared (Table 4). Calculations were performed a hundred times for each metrics using following setup: Intel i7 920, 8.0 GB RAM, Windows 7 Professional and Matlab R2016b. For the high quality of DSCSI metric, we pay a calculation time that is much higher than the times for other metrics. In work [3] we showed that there are no statistically significant differences (Friedman test with post-hoc procedures) between these new metrics, therefore we can use any of them. The best choice from the point of view of the calculation time is the MDSIs metric.

4 Conclusions

In this paper we looked for the effective deterministic initialization of the K-Means method used for color quantization. Of the few tested initializations, the best results give the initialization based on the palette from the Wu’s algorithm (KMWU). Eight image quality metrics were used for assessment of 24 quantized images. Additional inclusion of Floyd-Steinberg dithering procedure improves the quantization results (KMWU+FS) judged by newly created perceptual metrics. This represents a significant advantage of these metrics.