=Paper=
{{Paper
|id=Vol-547/paper-14
|storemode=property
|title=Color Quantization and its Impact on Color Histogram Based Image Retrieval
|pdfUrl=https://ceur-ws.org/Vol-547/60.pdf
|volume=Vol-547
|dblpUrl=https://dblp.org/rec/conf/ciia/MeskaldjiBC09
}}
==Color Quantization and its Impact on Color Histogram Based Image Retrieval==
https://ceur-ws.org/Vol-547/60.pdf
Color Quantization and its Impact on Color Histogram
Based Image Retrieval
Khouloud Meskaldji1, Samia Boucherkha2 et Salim Chikhi3
1
Meskaldji.khouloud@gmail.com,2 samchikhi@yahoo.com,3 slchikhi@yahoo.com
Abstract. The comparison of color histograms is one of the most widely used techniques
for Content-Based Image Retrieval. Before establishing a color histogram in a defined model
(RGB, HSV or others), a process of quantization is often used to reduce the number of used
colors. In this paper, we present the results of an experimental investigation studying the
impact of this process on the accuracy of research results and thus will determine the number
of intensities most appropriate for a color quantization for the best accuracy of research
through tests applied on an image database of 500 color images.
Keywords: histogram-based image retrieval, color quantization, color model, precision,
Histogram similarity measures.
1 Introduction
Content-based image retrieval (CBIR) is a technique that uses visual attributes (such
as color, texture, shape) to search for images. These attributes are extracted directly
from the image using specific tools and then stored on storage media. The Search in
this case is based on a comparison process between the visual attributes of the image
request and those of the images of the base (Fig.1). This technique appeared as an
answer to an eminent need of techniques of automatic annotaion of images. Manual
annotation of images is an expensive, boring, subjective, sensitive to the context and
incomplete task.
Color attributes are considered among the most used low-level features for image
search in large image databases. They have been used in several CBIR systems such
as QBIC [6] and Chabot [11]. The use of color in this area is justified by two factors.
First, the color is a powerful descriptor that facilitates the identification and
extraction of objects from a scene [3]. Second, humans can discern thousands of
shades and intensities of color, compared to about two dozen shades of gray [9].
However color quantization consists in reducing the number of used colors to
represent an image. The maximal number of colors used generally is 256 3. The
purpose of this process is to reduce the number of existing intensities in every
channel of a color model. This work is organized as follows: section 2 is dedicated
to the definition of color histogram, section 3 presents some color models, section 4
exposes color quantization, section 5 is dedicated to similarity measures between
histograms, section 6 for defining performance measures, section 7 for
experimentation and interpretation before giving a general conclusion and some
perspectives on this work.
User Query Image
formulation Base
Visual Visual
content content
description description
Feature Feature
vector vector
Feature
comparison
Output Retrieval
S results
Fig. 1. Framework of a CBIR system.
2 Color histogram
The color histogram is a method for describing the color content of an image, it
counts the number of occurrences of each color in an image [8] (Fig. 2).
Fig. 2. Color histogram diagram of three channels (R, G and B).
The color histogram of an image is rotation, translation, and scale-invariant [3];
therefore, it is very suitable for color-based CBIR: content-based image retrieval
using solely global color features of images. However the main drawback of their
use is that they do not take account of space information concerning the color. This
can lead to unexpected errors (Fig. 3).
Fig. 3. Two distinct images are displayed. However, once represented by their color
histograms, they are considered as identical.
Several alternatives were proposed in the literature to include space information
by using the space relations between the pixels (such as color moments [5], color
constants [7], color signatures [4]). These methods are concerned with optimizing
color matching techniques on a spatial level; i.e., utilizing the spatial relations
between pixels, in relation to their colors. According to Venn den [3] a larger
attention must be attracted towards the way in which a search engine based on the
color handles (codes or categorizes) a color.
3 Color models
Color model describes colors in a formal way according to a certain specification.
Usually color models represent a color in the form of tuples (generally of three). For
example, according to RGB (Red, Green, Blue), white color is represented by the
tuple (0, 0, 0) and the black color is represented by (255,255,255). The purpose of a
color model is to facilitate the specification of colors in a certain way and common
standard [10]. Color models lend themselves to (in principle) reproducible
representations of color, particularly in digital representations, such as digital
printing or digital electronic display [3].
3.1 RGB (Red, Green, Blue) color model
RGB color model (RGB: Red, Green, Blue) is the most used color model for
computer graphics. It is an additive color model: the lights red, green, and blue are
combined to create other colors. It is not perceptually uniform [3] i.e the same
variation of the value of the components is not always perceived as the same
variation of color. In other words, this means that the measure of the variation
perceived by a human is different from the mathematical distance. The RGB color
model can be visualized in the form of a cube, as illustrated in Fig. 4.
Fig. 4. RGB Coordinate system. Fig. 5. Hue, saturation, and the value
(brightness/luminosity) represented on a wheel of
colors.
3.2 HSV (Hue, Saturation, Value) color model
HSV (HSL, HSB) models are much closer to human eye perception of color [1], but
are perceptually not uniform [2]. The components of these models are: Hue,
Saturation, and Value (lightness or brightness). The hue represents the chromatic
component in this model and it is the definition of a color by the combination of the
primary colors. Saturation refers to the predominance of a particular hue in a color.
The value of a color refers to the intensity (the lightness or the darkness of the color)
(figure 5).
3.3 RGB to HSV
In order to use a good color model for a specific application, conversion between
color models is necessary. A good color model for an image retrieval system should
preserve the perceived differences in color.
[( ) ( )]
= cos (1)
( ) ( )( )
=1− [min(R, G, B)] (2)
= (R + G + B) (3)
3.4 CIE XYZ color model
The first color model developed by CIE (Commission Internationale de l’Eclairage)
is XYZ color model. The Y component is the luminance component defined by the
weighted sums of R (0.212671), G (0.715160), and B (0.072169). X and Z are the
chromatic components. The XYZ color model is not perceptually uniform [3]. The
transition from RGB to CIE XYZ is a simple linear transformation, which means that
XYZ model is proportional to RGB color model. XYZ model is only an RGB model
like another. We find the same notation of colors by triplets. The chromaticity plan is
materialized by the Maxwell triangle (Fig. 6).
Fig. 6. Representation of CIE XYZ model by Maxwell's triangle.
4 Color quantization
In order to produce color histogram, color quantization is often applied. Color
quantization is the process to reduce the number of colors employed to represent an
image. A quantization scheme is determined by the color model and the
segmentation (i.e., split up) of the color model used. As we said before, usually color
models represent a color in the form of tuples (generally of three) .By applying a
standard quantization scheme to a color model, each axis is divided into a certain
number of fractions. When the axes are divided into k, l, and m parts, number (n) of
the colors used to represent an image will be: n= k.l.m.
A quantization of color model in n colors is often referred to as a n-bins
quantization scheme. Fig. 7 illustrates the effect of color quantization of an image.
The segmentation of each axis depends on the used color [3].
(a) (b)
Fig. 7. (a) The original image 256 bins, (b) Quantified image in 8 bins.
5 Histogram similarity measures
An image can be represented by a color histogram, defined by a quantization scheme
of color applied to a color model. In order to express the similarity of two histograms
in a digital asset, a metric distance is employed In literature, a wide variety of
distance measures between histograms can be found, the most commonly used and
which we have therefore used are the following.
5.1 Histogram Euclidean distance
The Euclidean distance between two color histograms h and g is given by:
(h, g) = ∑ ∑ ∑ (h(a, b, c) − g(a, b, c)) (4)
Where a, b, c are color components (in the case of RGB a=r, b=g, c=b).
In this formula there is only comparison between the identical bins in the
respective histograms. Two different bins may represent perceptually similar colors
but are not compared crosswise.
5.2 Intersection distance
The color histogram intersection distance between two histograms is given by:
∑ ∑ ∑ ( ( , , ), ( , , )) (5)
d(h, g) = (| |,| |)
| h | and | g |: denote the number of samples used for the construction of the
histogram.
6 Performance measure
To evaluate the performance of a CBIR system, two measures, namely, the recall and
the precision [9], were borrowed from traditional information retrieval. Let A be the
set of images in the base which are appropriate to the image request q, and B the set
of returned images as result for that query. Sets a, b, c and d are given in Fig. 8.
Fig. 8. A representative diagram to explain performance measures of retrieval
In Fig. 8, a represents returned appropriate images, b represents inappropriate
returned images, c appropriate but not returned images and d inappropriate and not
returned images.
Recall and precision can be defined as follows:
| |
=| |
(6)
| |
=| |
(7)
7 Experimentation
7.1 Image database
The used base of images comprises 500 color images. It was downloaded from
http://wang1.ist.psu.edu/. The original image database comprises 1000 images
divided into 10 classes. We chose the use of 500 images and 5 classes for calculation
reasons. Each class represents a definite topic: African and villages, beach, buildings,
bus and dinosaurs. A sample of the base is presented in Fig. 9.
Fig. 9. A sample of the used base, an image from each class.
7.2 Developed prototype
Our prototype has been developed for the purpose of studying the impact of color
quantization on the accuracy (precision) of CBIR. Precision represents in a retrieval
process the chance of obtaining images which are similar to the image request among
a group of n returned images. In our case we have calculated the precision of the top
25 of returned images. This number is approximately the number of the first returned
images by a retrieval system as thumbnails.
The working principle of our prototype can be described in Fig. 10.
Loading images Calculation of Performing a
from image base histograms according to search for 10 (15.20)
quantization scheme image queries and
(i, i, i), Such as calculate the average
i ≤ max- accuracy of top 25 of
quantization returned images
If i < max-quantization increment i
Displaying graphs
y = f (x) as:
X: quantization
scheme
Y: average precision
Fig. 10. A diagram describing experimentation process
As described above, the first step consists of loading images from the image base.
In the second step, color histograms are calculated according to a quantization
scheme (i, i, i) such as i ≤ max-quantization. The third step consists of performing a
search for 10 (15, 20) images. We have to note that those images have been
randomly chosen from the base but with one condition; the different classes must
participate by the same number of images ( if we take 5 images from the first class,
we have to take 5 from the second class and the third and so on). If max-quantization
is reached the process stops and graph y= f(x) is displayed such as: x is the
quantization scheme, y is obtained precision.
7.3 Results and interpretations
RGB model. We initially carried out tests on the quantization schemes from 2 to 256
with step of 8(2, 10, 18, 26…). The first tests showed that the optimum is situated in
the first fifteen values of the quantization schemes. Then we reduced the traversed
interval of quantization to the first fifteen quantization schemes for better locating the
optimum. Obtained results are presented in Fig. 11.
(a) (b)
Fig. 11. Calculation of the precision according to the RGB quantization for:
(a) Intersection distance, (b) Euclidean distance
As we can notice it, the optimal precision is reached when the used quantization
scheme is of (12, 12, and 12). This value also depends on used distance but with tiny
variations (about +/- 2). We can also notice that the use of quantization schemes with
greater values does not necessarily lead to a better precision. On the contrary it leads
to a much less efficient search. Then the choice of a quantization scheme or another
is a decision which must be taken after a meticulous study.
HSV model. Obtained results for this model are described by Fig. 12
(a) (b)
Fig. 12. Calculation of the precision according to the HSV quantization for:
(a) Euclidean distance, (b) Intersection distance
As the figures show it above, there is a light difference between the results
obtained of the two distances. The quantization scheme which leads to an optimal
precision is located between the scheme of 10 and that of 15. In order to be able to
determine the exact value a thorough study of this model must be established.
XYZ model. The results obtained of this model are described by Fig. 13.
(a) (b)
Fig. 13. Calculation of the precision according to the XYZ quantization for:
(a) Euclidean distance, (b) Intersection distance
We can notice that the results obtained of both distances are almost identical. The
quantization scheme which leads to an optimal precision in this case is that of (8, 8,
8).
Obtained results showed image search precision depends indeed on the used
quantization scheme. Thus the used scheme must be selected after a meticulous
study. According to the tests carried out the difference of the precision between the
optimal scheme and the maximum scheme can go up to 20% of returned images. So
the use of a vector of size 256 is not necessary, rather it is inadvisable since it leads
to less efficient search. In other words, in one hand, the use of a quantization scheme
of very great values allow us to describe the images in a more detailed way, and in
the other hand, it increases the distance between images. We cannot say that the
optimal schemes obtained with these tests can be generalized on all the bases of
images because they also depend on the type of images used.
Suppose we want to classify the various models according to their strength of
description (by strength of description we denote the optimal quantization scheme);
for example in our case XYZ color model is classified in first because its optimal
quantization scheme is the smallest, which means that this model makes it possible
to describe the images in a significant way compared with both others. However the
best results among all the tests carried out are those of model HSV with the
intersection distance. In this case, we suggest studying thoroughly color models and
finding measurements which enable us to compare them according to their
quantization and their search performance.
8 Conclusion and perspectives
In this work we have been able to show in the first place the need of a quantization
process in CBIR system using color histograms. We have also demonstrated that the
use of a quantization scheme of great values does not necessarily lead to an optimal
precision of search. On the contrary it can lead to less efficient search. Then a
thorough study must be established in order to be able to determine the best
parameters of quantization for a better search for all color models. This implies the
use of this process on other image bases as well as on other color models. In
perspective we will study the impact of quantization on the recall of search.
9 References
1 A. M. W. Smeulders, M. Worring, S. Santini, A. Gupta, and R. Jain, "Content-
based image retrieval at the end of the early years, " IEEE Trans. on Pattern Analysis
and Machine Intelligence, Vol.22, No.12, pp. 1349
-1380, Dec. 2000.
2 A. Vailaya, M. A. G. Figueiredo, A. K. Jain, and H. J. Zhang, "Image
classification for content-based indexing," IEEE Trans. on Image Processing, Vol.10,
No.1, Jan. 2001
3 Broek, E. L. van den (2005). Human-Centered Content-Based Image Retrieval.
PhD-thesis Nijmegen Institute for Cognition and Information (NICI), Radboud
University Nijmegen, The Netherlands - Nijmegen.
4 J. Kender and B. Yeo. Video scene segmentation via continuous video coherence.
In Proceedings of IEEE Computer Vision and Pattern Recognition, pages 367.373,
Santa Barbara, CA, june 1998. IEEE Computer Society.
5 K. Ravishankar, B. Prasad, S. Gupta, and K. Biswas. Dominant color region based
indexing for cbir. In V. Roberto, V. Cantoni, and S. Levialdi, editors, Proceedings of
the International Conference on Image Analysis and Processing, pages 887-892.
Italian Chapter of the International Association for Pattern Recognition (IAPR-
IC), september 1999.
6 M. Flickner and al. Query by image and video content: The QBIC system. IEEE
Computer, 28(9):23{32, September 1995.
7 M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B. Dom, M. Gorkani,
J. Hafner, D. Lee, D. Petkovic, D. Steele, and P. Yanker. Query by Image and Video
Content: The QBIC system. IEEE Computer, 28(9):23.32, 1995.
8 M. Worring and Th. Gevers. Interactive retrieval of color images. International
Journal of Image and Graphics, 1(3):387.414, 2001.
9 R. C. Gonzales and R. E. Woods. Digital image processing. Prentice-Hall, Inc.,
New Jersey, 2nd edition, 2002.
10 Virginia Ogle and Michael Stonebraker. Chabot: Retrieval from a relational
database of images. IEEE Computer, 28(9):40{48, September 1995.
11 W. Y. Ma, and B. S. Manjunath, "Edge flow: a framework of boundary detection
and image segmentation," IEEE Int. Conf. on Computer Vision and Pattern
Recognition, pages 744-749, Puerto Rico, June 1997.