Perceptual-Based Color Quantization Vittoria Bruni1,2 , Giuliana Ramella2(B) , and Domenico Vitulano2 1 Department of SBAI, University of Rome La Sapienza, Rome, Italy vittoria.bruni@sbai.uniroma1.it 2 Institute for the Applications of Calculus, CNR, Rome, Italy {giuliana.ramella,d.vitulano}@iac.cnr.it Abstract. The paper presents a method for color quantization (CQ) which uses visual contrast for determining an image-dependent color palette. The proposed method selects image regions in a hierarchical way, according to the visual importance of their colors with respect to the whole image. The method is automatic, image dependent and requires a moderate computational eﬀort. Preliminary results show that the quality of quantized images, measured in terms of Mean Square Error, Color Loss and SSIM, is competitive with some existing CQ approaches. Keywords: Human Visual System tion · RGB color space 1 · Visual contrast · Color quantiza- Introduction Although the Human Visual System (HVS) is able to distinguish a large numbers of colors, it behaves as an imperfect sensor. It tends to group colors with similar tonality since few colors are generally enough for image representation and understanding. A color quantization (CQ) method attempts to emulate this perceptual behavior by selecting a suitable reduced number of representative colors and by producing a quantized image which still is visually similar to the original one with minimum distortion. A number of CQ methods are available in the literature [1,3,13]. The standard approach is based on the interpretation of CQ as a clustering problem in the 3D color space. Colors are grouped into clusters, by using any clustering technique, and the representative color for each cluster is generally obtained as the average of the colors in the cluster. Most CQ methods belong to the category of image dependent clustering methods. Usually, they can be categorized into two families: preclustering methods [3,8,9,18] and postclustering methods [6]. Methods in the former class are based on a hierarchical structure and recursively ﬁnd nested cluster either in a top-down or bottom-up manner; on the contrary, methods in the second class ﬁnd all clusters simultaneously as a partition of the data. Visual perception is mediated by a collection of individual mechanisms in the visual cortex due to the neuron response to stimuli above a certain contrast. Hence, to integrate the properties of the HVS in the quantization step, c Springer International Publishing AG 2017 S. Battiato et al. (Eds.): ICIAP 2017, Part I, LNCS 10484, pp. 671–681, 2017. https://doi.org/10.1007/978-3-319-68560-1_60 672 V. Bruni et al. a perceptual-based method should exploit the spatio-temporal masking properties and establish thresholds based on psychophysical contrast phenomena. This contrast sensitivity varies with spatial frequency, temporal frequency and orientation and can be used to indicate the threshold at which a spatial frequency just becomes visible under certain viewing conditions. Some perceptual-based methods based on contrast sensitivity have been proposed in the literature [5,12,15], especially for image compression purposes. However, a contrast-based analysis, which allows an integration of the perceptual mechanisms of the HVS in the quantization step to achieve the best possible visual quality, has still not received the adequate attention. In this paper we propose a CQ method which selects quantization bins according to measures related to contrast sensitivity in order to reach a good visual quality. The proposed model, named perception-based color quantization (PCQ), aims at applying some basic rules which guide human perception in the selection of the most K representative colors in an image, when K is given. It mainly consists of a 3D extension of the model proposed by the same authors in [2] for dermoscopic images processing. Speciﬁcally, the quantities used for measuring contrast variations have been generalized to the color space. They allow an automatic selection of the threshold to use for selecting those image pixels which contribute to the deﬁnition of representative image colors. PCQ is automatic since perceptive thresholds are automatically tuned according to the analyzed image. It can be framed in the preclustering method category and can be considered as context adaptable, since the resulting CQ is image-dependent. PCQ has been compared with some representative methods belonging to the same class in terms of some well known objective measures. Experimental results show that the simple use of basic quantities related to human vision allows us to reach results that are comparable to some reference methods in the literature, with a very good subjective visual quality. The outline of the paper is the following. Section 2 gives a detailed description of the general perceptual model extended to the three color channels. As well as a through description of the main steps of the whole quantization procedure. Experimental results, discussions and concluding remarks are in Sect. 3. 2 The Proposed CQ Model Color contrast is one of the main property of vision and plays a key role in object detection and discrimination. It has a direct connection with two of the main rules of primary vision, like chromatic adaptation and color constancy. Chromatic adaptation is the ability of the HVS to discount the color of a light source and to approximately preserve the appearance of an object. Color constancy is the property by which objects tend to appear with the same color under changes in illumination. The strength of chromatic contrast is inﬂuenced by several factors including relative illumination, spatial scale, spatial conﬁguration and context as well as object dimension and background variability. More precisely, the perception of an object with a given color (foreground) depends Perceptual-Based Color Quantization 673 on the color of its background as well as on the chromatic variability of the same background. Based on this consideration, we are interested in quantifying: (i) how the visual contrast of the foreground changes if its background is gradually modiﬁed and (ii) how the perception of the same object changes if its color is modiﬁed while its background is leaved unchanged. The combination of these two quantities provides a sort of visual distortion curve where the optimal quantization bin can be determined. More precisely, by denoting with Iij (k) the image I at point with coordinates (i, j) ∈ Ω, where Ω is the image domain, and color channel k (for example, in the RGB color space, k = 1, 2, 3 respectively denote red, green and blue components), with R the reference color (R is a vector having three components) and with B the color which represents the background, it is possible to deﬁne the following quantity Iij − B22 R − B22 , ∀ (i, j) ∈ Ω (1) − D1 (i, j) = B22 B22 where Iij − B22 (2) B22 is the square of the contrast of the object having color Iij with respect to a Cij = R−B2 background whose color is B – B2 2 has a similar meaning; ∗ 2 denotes the 2 euclidean distance. D1 quantiﬁes the variation of the contrast of an object with respect to a ﬁxed background having average color B if the object changes its color (from Ii,j to R). It is worth noticing that Eq. (2) is a generalization of the classical Weber’s contrast for monochromatic images [17]. Similarly, it is possible to deﬁne a quantity which works in the opposite way: the color of the object is ﬁxed (Iij ), while its background changes (from B to BR ). It is deﬁned as follows Iij − B22 Iij − BR 22 . (3) D2 (i, j) = − B22 BR 22 D1 and D2 can be then combined to deﬁne a pointwise distortion as follows D(i, j) = D1 (i, j)D2 (i, j), (4) which accounts for the two competing phenomena. In order to use D for determining the optimal detection threshold, it is necessary to deﬁne the spatial domain where those measures have to be deﬁned. The latter depends on the rule used for the estimation of R and BR in Eqs. (1) and (3). This rule can depend of the speciﬁc kind of application and purposes and it will be presented in the following section. 2.1 Representative Color Selection The aim of this section is to separate image foreground and background in an iterative manner. At each iteration, the foreground represents the object of interest, while the background consists of the remaining part of the image. The object 674 V. Bruni et al. of interest is a region of the image whose color is perceived as homogeneous. Since we are interested in ﬁnding perceptual representative colors in the image, in this paper the foreground is determined starting from the color which occurs more in the image and enlarging the color region by including tones having increasing distance from it. The chromatic region growing process stops when the variation of contrast becomes clearly visible to a human observer—this contrast threshold determines the amplitude of the bin which gives a color in the ﬁnal palette as well as the region of interest to which assign this color. This process is then iterated on the remaining part of the image. The number of iterations is the number of colors K to be used for image quantization, which is an input value. More precisely, if c = [c1 , c2 , c3 ] is the color having more occurrences in the image I, we deﬁne the domain Ωm = {(i, j) ∈ Ω : |Iij (k) − ck | ≤ mδk , k = 1, 2, 3}, m ≥ 1, m ∈ N, (5) where δk is the minimum allowed bin for the k-th color channel and it is estimated separately from each color component, as explained in the next subsection. Ωm contains pixels having colors close to c. R is then deﬁned as the average color of I in the region Ωm , BR as the average color of I in Ω − Ωm while B as the average color of I in Ω. The extension of Eq. (4) to the domain Ωm is then 1 D(Ωm ) = D(i, j), (6) |Ωm | (i,j)∈Ωm where |Ωm | is the cardinality of Ωm . Regions of interest in I are selected using a threshold value that has to correspond to the point of maximum visibility of the foreground with respect to its background, which represents an optimal point of D(Ωm ) as a function of |Ωm |—see Fig. 1. More precisely, the region of interest is selected as the one which realizes the maximum curvature of D. This point can be approximated as follows δ2D m̄ : |m=m̄ = 0 (7) δ|Ωm |2 3 δ D with δ|Ω 3 |m=m̄ < 0 . This optimal point represents the frontier between image m| foreground and background, i.e. from that point on pixels of the background would be confused with foreground. Finally, the mean value of the colors (in the RGB color space) of points belonging to Ωm̄ is considered as the dominant color of the region and represents the ﬁrst value c1 of the color palette to be used in the quantization step. The procedure is iterated by considering only the remaining image domain, i.e. Ω − Ωm̄ , till the number of desired colors is reached. 2.2 Estimation of the Least Allowed Bin Size In the preattentive phase, human eye acts as a low pass ﬁlter [17] since it is not interested in the detection of image details in this phase. As a result nonhomogeneous colored image regions are usually perceived at the ﬁrst glance as Perceptual-Based Color Quantization 675 Fig. 1. Original Parrots image (left); distortion curve D(Ωm ) versus the size of Ωm , as in Eq. (6) (middle) (the optimal point is marked); selected region in the original image which is estimated from the optimal point of the distortion curve (right). uniform areas. This visual resolution also gives the minimum allowed bin width (i.e. the one to which human eye is almost insensitive at ﬁrst glance). This visual resolution, namely δ, corresponds to a precise scale level of a pyramid decomposition of the image. For example, in the dyadic case, δ = 2J , where J is a ﬁxed positive integer number. It means that a variation h in color components, h at level J of the pyramid. In particular, if h = 2J−1 , it vanishes reduces to 2J−1 (less than 1) at level J—in other words, diﬀerences in amplitude greater than 2J−1 are hard to be perceived and then a bin size greater than 2J−1 can be considered. For the estimation of the “visual resolution”, the method in [2] has been adopted. It computes the contrast between two successive low-pass ﬁltered versions of the analysed image (where ﬁlters have increasing support) and selects δ as the resolution which gives the minimum perceivable contrast. This procedure is independently applied to the three color channels in this paper. 2.3 PCQ Algorithm 1. Compute the 3D histogram H(r, g, b) of the RGB image I. 2. For each color channel I(k) (k = 1, 2, 3), estimate the minimum bandwidth (respectively δ1 , δ2 , δ3 1 ) as in Sect. 2.2 as well as the mean value Mav (k) and the mode M o(k). Let Mav, Mo and δ be the corresponding 3D vectors. 1 |Mav−Mo| 1 and the parameter 3. Compute the correction parameter σ = 3K Mav 128 Δ = δ∞ . 4. Repeat the following steps K times (for l = 1, 2, . . . , K) – Compute the average color B of I in the domain Ω and correct it using the following rule: B = B (1 − lσ). – Set c = argmaxr,g,b H(r, g, b) and m = 1. – For each integer m ∈ [1, Δ]: • Find Ωm using in Eq. (5). • Compute the average color R in Ωm and the average color BR in Ω − Ωm . • Evaluate D(Ωm ) using in Eq. (6). 1 They are given as power of 2. 676 V. Bruni et al. – Extract the optimal m̄ as in Eq. (7) and the corresponding region Ωm̄ . – Compute the average color cl of I in Ωm̄ and put it in the palette and set H(Iij (1), Iij (2), Iij (3)) = −1, ∀ (i, j) ∈ Ωm̄ . – Set Ω = Ω − Ωm̄ and I = I(Ω) (the latter denotes I restricted to the domain Ω). 5. Assign to each pixel in the original image the closest color in the selected color palette {c1 , c2 , . . . , cK , } and let IQ the quantized image. The correction parameter σ is used for adapting the algorithm to the number of desired colors. In fact, the detection algorithm can be less sensitive to some details as K decreases; while it is the opposite as K increases. That is why, the value B, which represents the image background, is deﬁned as a correction of the actual average value of the image to be analysed. It is also worth observing that for K ≤ 16 the algorithm is applied to the low pass ﬁltered version of I at resolution log2 (min{δr , δg , δb }). 3 Experimental Results and Concluding Remarks PCQ has been tested on several color images having diﬀerent features. In order to perform a comparative study, in this section results achieved on 21 images taken from some public available databases (such as [19–23]) and the 8 images used in [3] will be shown and discussed. The ﬁrst dataset has been used for a direct comparison with some standard CQ methods. Speciﬁcally, the following methods have been considered: (i) the Median-cut (MC) [9], which recursively split boxes obtained using a uniformly quantized image along the longest axis at the median point. At each step, the split is applied to the box that contains the greatest number of colors; (ii) the Octree (OCT) [8], which merges colors represented in a tree data structure by pruning the tree until the desired number of colors is obtained; (iii) the greedy orthogonal bipartitioning (WU) [18], which uses the minimum SSE (sum of squared error) for boxes splitting; (iv) self-organizing map (SOM) [6], which uses a one-dimensional self-organizing map with K neurons and the weights of the ﬁnal neurons deﬁne the color palette. Table 1 contains the results achieved using no more than 16 colors (K = 16). They have been measured in terms of Mean Square Error (MSE) and Color Loss (CL), since commonly used measures for the evaluation of color image quality. We have also evaluated the structural similarity index (SSIM) as a measure which is more consistent with visual perception, even though it has not been speciﬁcally deﬁned for color images. For two images v and w of dimension H × K, H K 3 1 – MSE [14] is computed as: M SE(v, w) = HK i=1 j=1 k=1 (vij (k) − 2 wij (k)) , where i, j denote pixel location while k is the color channel; – CL [4,10,11] is the average color loss between v and w, i.e. CL(v, w) = H K 3 1 2 i=1 k=1 k=1 (vij (k) − wij (k)) ; HK – SSIM [7,16], for two gray-level images v and w is deﬁned as: SSIM (v, w) = (2μv μw +c1 )(2σvw +c2 ) 2 (μ2 +μ2 +c1 )(σ 2 +σ 2 +c2 ) , where μ∗ is the average of ∗; σ∗ is the variance of ∗; v w v w Perceptual-Based Color Quantization 677 Table 1. SSIM, MSE and CL results achieved on the images in Fig. 2 by Median Cut (MC) [9], the Octree (OCT) [8], Greedy orthogonal bipartitioning (WU) [18], Self-organizing map (SOM) [6] and the proposed perception-based color quantization method (PCQ) using 16 colors. For each metric, the average values (Avg) computed on the whole dataset are also given. Finally, for each method, the number of used colors K is provided. 678 V. Bruni et al. Fig. 2. Images used for the comparative studies in Table 1. Table 2. MSE and MAE results achieved by PCQ and the two methods proposed in [3] (VC and VCL). The set of images is the same used in [3]. Image Method (K = 32) MSE MAE Image Fish PCQ VC VCL 179.8 17.6 168.1 17.2 169.9 17.1 Goldhill PCQ VC VCL Method (K = 32) MSE MAE 199.9 19.7 174.8 17.8 169.3 17.3 Motocross PCQ VC VCL 283.4 22.8 253.2 20.5 240.6 19.4 Lena PCQ VC VCL 156.4 16.9 145.6 16.5 146.3 16.5 Parrots PCQ VC VCL 287.4 22.0 290.6 22.4 263.7 21.6 Peppers PCQ VC VCL 292.0 22.9 294.8 22.9 261.1 22.9 Baboon PCQ VC VCL 452.3 29.1 450.6 29.4 425.6 28.5 Pills 251.7 21.3 234.4 20.9 229.8 20.5 PCQ VC VCL σvw is the covariance of v and w; c1 and c2 are two stabilizing constants. For RGB images, SSIM is computed for the three color channels independently and the quality value is obtained by averaging the three indexes. As it can be observed in Table 1, PCQ provides, on average, results close to Wu and SOM, while it outperforms MC and OCT. It is worth observing that PCQ does not start from a rigid and preﬁxed uniform quantization of image colors. It adaptively quantizes the image according to the estimated resolution of each color channel; in addition, each bin is determined by evaluating the visibility of image regions having the assigned representative color with respect to a changing image background and ﬁxes the size of the bins as the ones which provides a not negligible contrast. However, the computation of the optimal point of the distortion curve, as deﬁned in Eq. (7), suﬀers from some numerical instability Perceptual-Based Color Quantization 679 Fig. 3. (Left) Original image; (Right) quantized image by the proposed PCQ method with K = 32. (Color ﬁgure online) 680 V. Bruni et al. that can inﬂuence the right selection of the optimal threshold, especially if K is low. Even though the correction of the numerical instability is able to further improve results in Table 1, this reﬁnement has not been considered here, since out of the scope of the paper. The second dataset, has been used for a direct comparison with the variance cut (VC) method in [3] and its reﬁned version VCL. VC is a divisive CQ method which employs a binary splitting strategy. It starts from a 32 × 32 × 32 color histogram obtained from a 5 bits/channel uniform quantization. At each iteration, the method splits the partition with the greatest SSE along the coordinate axis with the greatest variance at the mean point. The centroids of the resulting K sub-partitions deﬁne the color palette. VCL uses a few Lloyd-Max iterations for a local optimization of the two sub-partitions obtained at each step. In the same paper the authors compare their method with the ones considered in the ﬁrst dataset and then they will be not reported in Table 2. MSE and MAE (Mean Absolute Error) are the two metrics used for comparing quantized image quality, as in [3]. The Mean Absolute Error MAE [14] is computed as: H K 3 1 M AE(v, w) = HK i=1 j=1 k=1 |vi,j (k) − wij (k)|. As it can be observed in Table 2, PCQ, in its present and not optimized version, approaches and sometimes outperforms VC method. In addition the quality of quantized image is good, as it is shown in Fig. 3. Textured regions are well recovered, as for example the plumage of the Parrots, or in Lena hat or in Baboon. In addition, there is a good match between image region and assigned representative color. These results show that PCQ is promising and the use of simple rules of human vision allows us to reach the results of some optimized methods which are based on statistical image features. In addition, using this kind of approach, some of the adopted measures and criteria could be embedded and interpreted in this new way of facing the problem. For example, the SSE is strictly related to the variability of the background which is used in the computation of image contrast. In addition, the deﬁnition of contrast measures allows us to simply embed some locality and spatial constraints which deﬁnitely would contribute to improve CQ, enabling the method to be more image content and perception dependent. Finally, the computational eﬀort of PCQ is moderate since few simple operations are required. In fact, the most expensive step of the method is the iterative construction of the distortion curve. Future research will be devoted to deﬁne a more robust numerical scheme able to detect the optimal threshold, without constructing the whole curve. References 1. Brun, L., Tremeau, A.: Chapter 9: Color quantization. In: Digital Color Imaging Handbook. Electrical and Applied Signal Processing. CRC Press (2002) 2. Bruni, V., Ramella, G., Vitulano, D.: Automatic perceptual color quantization of dermoscopic images. In: Braz, J., et al. (eds.) Proceedings of VISAPP 2015, pp. 323–330. SciTePress Science and Technology Publications, Berlin (2015) Perceptual-Based Color Quantization 681 3. Celebi, M.E., Wen, Q., Hwang, S.: An eﬀective real-time color quantization method based on divisive hierarchical clustering. J. Real-Time Image Process. 10(2), 329– 344 (2015) 4. Chan, H.C.: Perceived image similarity and quantization resolution. Displays 29, 451–457 (2008) 5. Chandler, D.M., Hemami, S.S.: Dynamic contrast-based quantization for lossy wavelet image compression. IEEE Trans. Image Process. 14(4), 397–410 (2005) 6. Dekker, A.: Kohonen neural networks for optimal colour quantization. Netw.: Comput. Neural Syst. 5(3), 351–367 (1994) 7. De Simone, F., Ticca, D., Dufaux, F., Ansorge, M., Ebrahimi, T.: A comparative study of color image compression standards using perceptually driven quality metrics. In: Proceedings of SPIE Conference on Optics and Photonics, Applications of Digital Image Processing XXXI (2008) 8. Gervautz, M., Purgathofer, W.: Simple method for color quantization: octree quantization. New Trends Comput. Graph. 219–231 (1988). Springer, Berlin 9. Heckbert, P.: Color image quantization for frame buﬀer display. ACM SIGGRAPH Comput. Graph. 16(3), 297–307 (1982) 10. Hsieh, I.S., Fan, K.C.: An adaptive clustering algorithm for color quantization. Pattern Recogn. Lett. 21, 337–346 (2000) 11. Kim, N., Kehtarnavaz, N.: DWT-based scene-adaptive color quantization. RealTime Imaging 11, 443–453 (2005) 12. Nadenau, M.J., Reichel, J., Kunt, M.: Wavelet-based color image compression: exploiting the contrast sensitivity function. IEEE Trans. Image Process. 12(1), 58–70 (2003) 13. Ozturk, C., Hancer, C.E., Karaboga, D.: Color image quantization: a short review and an application with artiﬁcial bee colony algorithm. Informatica 25(3), 485–503 (2014) 14. Salomon, D.: Data Compression: The Complete Reference. Springer, London (2007) 15. Yao, J., Liu, G.: A novel color image compression algorithm using the human visual contrast sensitivity characteristics. Photonic Sens. 7(1), 72–81 (2017) 16. Wang, Z., Lu, L., Bovik, A.C.: Video quality assessment based on structural distortion measurement. Sig. Process. Image Commun. 19(2), 121–132 (2004) 17. Winkler, S.: Digital Video Quality. Vision Models and Metrics. Wiley, Hoboken (2005) 18. Wu, X.: Eﬃcient statistical computations for optimal color quantization. In: Arvo, J. (ed.) Graphics Gems, vol. II, pp. 126–133. Academic Press, London (1991) 19. http://www.hlevkin.com/TestImages/ 20. http://sipi.usc.edu/database/ 21. http://r0k.us/graphics/kodak/ 22. http://www.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/ 23. http://decsai.ugr.es/cvg/dbimagenes/

1/--страниц