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.
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.
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).
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).
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 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 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.
HSV (HSL, HSB) models are much closer to human eye perception of color [
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 [min(R, G, B)] = (R + G + B) 3.4
(1) (2) (3) 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). 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) 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. (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
The color histogram intersection distance between two histograms is given by: d(h, g) = ∑ ∑ ∑ ( ( , , ), ( , , )) (| |,| |) | h | and | g |: denote the number of samples used for the construction of the histogram. 6
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. 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: = | | | | | (5) (6) (7)
7.1
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. 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 from image base
Calculation of histograms according to quantization scheme (i, i, i), Such as
i ≤ maxquantization If i < max-quantization increment i
Performing a search for 10 (15.20) image queries and calculate the average accuracy of top 25 of returned images 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
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.
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
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.
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
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