вход по аккаунту


978-3-319-68560-1 60

код для вставкиСкачать
Perceptual-Based Color Quantization
Vittoria Bruni1,2 , Giuliana Ramella2(B) , and Domenico Vitulano2
Department of SBAI, University of Rome La Sapienza, Rome, Italy
Institute for the Applications of Calculus, CNR, Rome, Italy
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 effort. 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
· Visual contrast · Color quantiza-
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
find nested cluster either in a top-down or bottom-up manner; on the contrary,
methods in the second class find all clusters simultaneously as a partition of the
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.
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. Specifically, 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 definition 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.
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 influenced
by several factors including relative illumination, spatial scale, spatial configuration 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
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 modified and (ii) how the perception of the same object changes if its
color is modified 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 define
the following quantity
Iij − B22
R − B22 , ∀ (i, j) ∈ Ω
D1 (i, j) = B22
B22 where
Iij − B22
is the square of the contrast of the object having color Iij with respect to a
Cij =
background whose color is B – B2 2 has a similar meaning; ∗ 2 denotes the
euclidean distance. D1 quantifies the variation of the contrast of an object with
respect to a fixed 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 define a quantity which works in the opposite way:
the color of the object is fixed (Iij ), while its background changes (from B to
BR ). It is defined as follows
Iij − B22
Iij − BR 22 .
D2 (i, j) = −
BR 22 D1 and D2 can be then combined to define a pointwise distortion as follows
D(i, j) = D1 (i, j)D2 (i, j),
which accounts for the two competing phenomena. In order to use D for determining the optimal detection threshold, it is necessary to define the spatial
domain where those measures have to be defined. 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 specific kind of application and purposes and it will be presented in the
following section.
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
V. Bruni et al.
of interest is a region of the image whose color is perceived as homogeneous. Since
we are interested in finding 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 final 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 define the domain
Ωm = {(i, j) ∈ Ω : |Iij (k) − ck | ≤ mδk ,
k = 1, 2, 3},
m ≥ 1, m ∈ N,
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 defined 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
D(Ωm ) =
D(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
m̄ :
|m=m̄ = 0
δ|Ωm |2
δ D
with δ|Ω
3 |m=m̄ < 0 . This optimal point represents the frontier between image
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 first 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.
Estimation of the Least Allowed Bin Size
In the preattentive phase, human eye acts as a low pass filter [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 first glance as
Perceptual-Based Color Quantization
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 first 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 fixed positive integer number. It means that a variation h in color components,
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, differences 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 filtered
versions of the analysed image (where filters 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.
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 and the parameter
3. Compute the correction parameter σ = 3K
Δ = δ∞ .
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).
They are given as power of 2.
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 defined 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 filtered version of I at
resolution log2 (min{δr , δg , δb }).
Experimental Results and Concluding Remarks
PCQ has been tested on several color images having different 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 first dataset has been used for a direct
comparison with some standard CQ methods. Specifically, 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 final neurons define 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 specifically
defined for color images. For two images v and w of dimension H × K,
H K 3
– MSE [14] is computed as: M SE(v, w) = HK
k=1 (vij (k) −
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) =
k=1 (vij (k) − wij (k)) ;
– SSIM [7,16], for two gray-level images v and w is defined as: SSIM (v, w) =
(2μv μw +c1 )(2σvw +c2 )
(μ2 +μ2 +c1 )(σ 2 +σ 2 +c2 ) , where μ∗ is the average of ∗; σ∗ is the variance of ∗;
Perceptual-Based Color Quantization
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.
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].
Method (K = 32) MSE MAE Image
179.8 17.6
168.1 17.2
169.9 17.1
Goldhill PCQ
Method (K = 32) MSE MAE
199.9 19.7
174.8 17.8
169.3 17.3
Motocross PCQ
283.4 22.8
253.2 20.5
240.6 19.4
156.4 16.9
145.6 16.5
146.3 16.5
287.4 22.0
290.6 22.4
263.7 21.6
Peppers PCQ
292.0 22.9
294.8 22.9
261.1 22.9
452.3 29.1
450.6 29.4
425.6 28.5
251.7 21.3
234.4 20.9
229.8 20.5
σ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 prefixed 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 fixes 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 defined in Eq. (7), suffers from some numerical instability
Perceptual-Based Color Quantization
Fig. 3. (Left) Original image; (Right) quantized image by the proposed PCQ method
with K = 32. (Color figure online)
V. Bruni et al.
that can influence 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 refinement 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 refined 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 define 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 first 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
M AE(v, w) = HK
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 definition of contrast measures allows us to simply
embed some locality and spatial constraints which definitely would contribute
to improve CQ, enabling the method to be more image content and perception
dependent. Finally, the computational effort 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 define a more robust numerical scheme able to detect the optimal threshold,
without constructing the whole curve.
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
3. Celebi, M.E., Wen, Q., Hwang, S.: An effective 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 buffer 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 artificial bee colony algorithm. Informatica 25(3), 485–503
14. Salomon, D.: Data Compression: The Complete Reference. Springer, London
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
18. Wu, X.: Efficient statistical computations for optimal color quantization. In: Arvo,
J. (ed.) Graphics Gems, vol. II, pp. 126–133. Academic Press, London (1991)
Без категории
Размер файла
3 515 Кб
978, 68560, 319
Пожаловаться на содержимое документа