Keywords
|
Content Based Image Retrieval, Shape, Color Coherence Vector, Centroid, Segmentation |
INTRODUCTION
|
CBIR is the process of retrieving images from a database or library of digital images according to the visual content of the images. In other words, it is the retrieving of images that have similar content of colors, textures or shapes. Images have always been an inevitable part of human communication and its roots millennia ago. Images make the communication process more interesting, illustrative, elaborate, understandable and transparent |
In CBIR system, it is usual to group the image features in three main classes: color, texture and shape [1, 2]. Ideally, these features should be integrated to provide better discrimination in the comparison process. Color is by far the most common visual feature used in CBIR, primarily because of the simplicity of extracting color information from images [3, 4]. To extract information about shape and texture [5] feature are much more complex and costly tasks, usually performed after the initial filtering provided by color features. |
Many applications require simple methods for comparing pairs of images based on their overall appearance. For example, a user may wish to retrieve all images similar to a given image from a large database of images. Color histograms [6, 7] are a popular solution to this problem, the histogram describes the gray-level or color distribution for a given image, they are computationally efficient, but generally insensitive to small changes in camera position. Color histograms also have some limitations. A color histogram provides no spatial information; it merely describes which colors are present in the image, and in what quantities. In addition, color histograms are sensitive to both compression artifacts and changes in overall image brightness. For the design of histogram based method the main things we require are appropriate color space, a color quantization scheme, a histogram representation, and a similarity metric [8]. A digital image in this context is a set of pixels. Each pixel represents a color. Colors can be represented using different color spaces depending on the standards used by the researcher or depending on the application such as Red-Green-Blue (RGB), Hue-Saturation-Value (HSV), YIQ or YUV etc. [9] |
In this paper we describe a color-based method for comparing images which are similar to color histograms, but which also takes spatial information into account. We begin with a review of color histograms. Then describe CCV's and how to compare them. Examples of CCV-based image queries demonstrate that they can give superior results. Finally, we present some possible extensions to CCV's. |
This paper also presents an approach to retrieve images through an automatic segmentation technique. This allows us to get approximate information about the shape of the regions in the images. Shape description or representation is an important issue both in object recognition and classification. Many techniques, including chain code, polygonal approximations, curvature, Fourier descriptors and moment descriptors have been proposed and used in various applications. The segmentation is performed through a stochastic algorithm using the brightness of the regions under analysis. We found that the image features generated from the image regions allow higher discrimination among images than the existing approaches. The main idea is to search for the regions in the image [10] looking for typical groups of statistically equally bright elements. First image is segmented based on a specific brightness represents a class of the image. Then, the features are extracted from the segmented classes [11]. |
The rest of the paper is organized as follows. In section 2, discuss the color and shape features representation techniques. Then in section 3 describe proposed schemes of color and shape retrieval. Experimental results with accuracy tables are explained in section 4. Finally conclusion is made in section 5 followed by the references. |
COLOR AND SHAPE FEATURE REPRESENTATIONS
|
The initial step of CBIR system is to represent color component and shape regions into features vector. There are various ways to represent feature of digital images. In this paper following color and shape feature extraction techniques are proposed. |
A. Color Feature
|
For the initial process of histogram matching, we use the HSV color space. The HSV color space is preferred for manipulation of hue and saturation (to shift colors or adjust the amount of color) since it yields a greater dynamic range of saturation [12]. Figure 1 illustrates the single hex cone HSV color model. The top of the hex cone corresponds to V = 1, or the maximum intensity of colors. The point at the base of the hex cone is black and here V = 0. Complementary colors are 180° opposite one another as measured by H, the angle around the vertical axis V, with red at 0°. The value of S is a ratio, ranging from 0 on the center line vertical axis V to 1 on the sides of the hex cone. Any value of S between 0 and 1 may be associated with the point V = 0. The point S = 0, V = 1 is white. Intermediate values of V for S = 0 are the grays. Note that when S = 0, the value of H is irrelevant. From an artistâÃâ¬ÃŸs viewpoint, any color with V = 1, S = 1 is a pure pigment whose color is defined by H. Adding white and black corresponds to decreasing S without changing V and corresponds to decreasing V without changing S respectively. Tones are created by decreasing both S and V. |
Unlike general techniques of forming bins we divide the color space into parts depending on perception. Figure 2 shows the variation of Hue against Saturation plot with constant values of Value at its maximum. Note that as shown by the vertical partitions the segmentation of Hue is done. We can observe that the color in each partition is almost correlated and seems similar to the eyes. Thus we have 6 bins in the Hue plane. |
Color coherence vector is double color histograms which consist of coherent vector and incoherent vector. We define a color's coherence as the degree to which pixels of that color are members of large similarly-colored regions. We refer to these significant regions as coherent regions, and observe that they are of significant importance in characterizing images. Our coherence classifies pixels as either coherent or incoherent. Coherent pixels are a part of some sizable contiguous region, while incoherent pixels are not. A color coherence vector represents this classification for each color in the image. This notion of coherence allows us to make fine distinctions that cannot be made with simple color histograms. |
The initial stage in computing a CCV [13] is similar to the computation of a color histogram. First blur the image slightly by replacing pixel values with the average value in a small local neighborhood including the 8 adjacent pixels. Define the color space with only n distinct colors in the image. The next step is to classify the pixels within a given color bucket as either coherent or incoherent. A coherent pixel is part of a large group of pixels of the same color, while an incoherent pixel is not. After words determine the pixel groups by computing connected components |
When this is complete, each pixel will belong to exactly one connected component. Classify pixels as either coherent or incoherent depending on the size of its connected component. A pixel is coherent if the size of its connected component exceeds a fixed value τ; otherwise, the pixel is incoherent. |
For a given discredited color [14], some of the pixels with that color will be coherent and some will be incoherent. Let us call the number of coherent pixels of the jth discrete color αj and the number of incoherent pixels βj. Clearly, the total number of pixels with that color is αj + βj, and so a color histogram would summarize an image as |
![image](https://www.rroij.com/articles-images/IJAREEIE-674-e002.gif) |
Instead, for each color we compute the pair (αj, βj) which we will call the coherence pair for the jth color. The color coherence pairâÃâ¬ÃŸs vector for the image consists of |
![image](https://www.rroij.com/articles-images/IJAREEIE-674-e002.gif) |
Classification of coherence is determined by a fixed value τ. Each pixel is checked whether coherent or not. A pixel is coherent if its surrounding pixels have the same values to form a large contiguous region. Two images I and I1 can be compared using their CCV's, by using the L distance. Let the coherence pairs for the jth color bucket is (aj, bj) in I and (a1j, b1j) in I1. Using the L distance to compare CCV's, the jth bucket's contribution to the distance between I1 and I is |
![image](https://www.rroij.com/articles-images/IJAREEIE-674-e003.gif) |
B. Shape Feature`
|
Shape is an important visual feature and it is one of the basic features used to describe image content. However, shape representation and description is a difficult task. This is because when a 3-D real world object is projected onto a 2-D image plane, one dimension of object information is lost. As a result, the shape extracted from the image only partially represents the projected object. To make the problem even more complex, shape is often corrupted with noise, defects, arbitrary distortion and occlusion. Further it is not known what is important in shape. Current approaches have both positive and negative attributes; computer graphics or mathematics use effective shape representation which is unusable in shape recognition and vice versa. In spite of this, it is possible to find features common to most shape description approaches. |
Basically, shape-based image retrieval consists of measuring the similarity between shapes represented by their features. Some simple geometric features can be used to describe shapes. Usually, the simple geometric features can only discriminate shapes with large differences; therefore, they are usually used as filters to eliminate false hits or combined with other shape descriptors to discriminate shapes. They are not suitable to stand alone shape descriptors. A shape can be described by different aspects [15]. These shape parameters are Mass, Center of gravity(Centroid) [16], Mean, Variance, Dispersion, Axis of least inertia, Digital bending energy, Eccentricity, Circularity ratio, Elliptic variance, Rectangularity, Convexity, Solidity, Euler number, Profiles, Hole area ratio, etc. Some of these are described as follows. |
Mass is the no. of pixels contained in one class. It is given as |
![image](https://www.rroij.com/articles-images/IJAREEIE-674-e004.gif) |
Centroid is also called as the center of mass; h is a mask of cluster c over image S(x, y). The co-ordinates (xc, yc) of the Centroid are defined as: |
![image](https://www.rroij.com/articles-images/IJAREEIE-674-e005.gif) |
and |
![image](https://www.rroij.com/articles-images/IJAREEIE-674-e006.gif) |
The mean and variance features of the class c are computed over the original image I considering the resulting segmentation S, and they are respectively denoted by μc and σ2 c |
![image](https://www.rroij.com/articles-images/IJAREEIE-674-e007.gif) |
and |
![image](https://www.rroij.com/articles-images/IJAREEIE-674-e008.gif) |
Dispersion is the sum of the distances of each region of a class from the class Centroid. The distance is calculated by Euclidean distance formula. The dispersion can be given as |
![image](https://www.rroij.com/articles-images/IJAREEIE-674-e009.gif) |
Where, dist (Oc,Oi,c) is the Euclidean distance |
Oc= centroid of the class c |
Oi,c= centroid of region I of class c |
PROPOSED WORK
|
A. Color Retrieval
|
Color retrieval system works in two stages. |
1) In the first stage, Histogram based comparison is done and matching images are short listed. |
2) In the second stage, the Color Coherence Vectors of the short listed images (stage 1) are used to refine the results. |
Numbers of coherent and non-coherent pixels for all color intensities are calculated in the image. Then size of coherency array, coherency array and no. of coherency pixels are stored as a vector. The Euclidean Distance is used for matching two histograms h and hâÃâ¬ÃŸ each of which n bins is given as |
![image](https://www.rroij.com/articles-images/IJAREEIE-674-e010.gif) |
It operates by assuming each vector as a point in an n-dimensional vector space and computes the physical distance between the 2 points. |
B. Algorithm for Color Retrieval
|
Step1: Read the image |
Step2: Convert from RGB to HSV |
Step3: Find HSV histogram and create vectors v1. |
Step4: Read the vectors from database and compare one by one by one with vector v1. |
Step5: Shortlist all the images which fall within the threshold. |
Step6: find coherency of the query image for each color and create coherency vector c1. |
Step7: Compare coherency vectors of all the short listed images from step5 with c1. |
Step8: Store all matching images in results folder and also display them. |
C. Shape Retrieval
|
The proposed shape retrieval system based on the automatic segmentations process to get approximate information about the shape of an object. It begins by segmenting the image into 5 classes depending on their brightness. Then three attributes: Mass, Centroid and Dispersion for each class are calculated and stored as the shape vector. For retrieval the vectors of the query image and database images are compared and the most matching images are short listed as results. |
D. Algorithm for shape Retrieval
|
Step1: read the image |
Step2: convert it from RGB to grayscale |
Step3: determine the range and number of classes. |
Step4: calculate the number of pixels i.e. mass belonging to each class. |
Step5: calculate the centroid and dispersion for each class. |
Step6: compare centroid of each class of query image with the centroids of each class from database image and extract out that class. |
Step7: compare that classâÃâ¬ÃŸs mass and dispersion with respective class. |
Step8: increase the count if it satisfies certain threshold. |
Step9: consider second class and repeat steps 6-8 till all classes get over. |
Step10: take another image from the database and repeat the comparison. |
Step11: display the images with maximum count. |
E. Similarity Measure
|
In this algorithm we propose that matching is done on color by color basis. By analyzing histograms, first calculate the number of colors in both query image and database image. Then both the images are matched by seeing if the proportions of a particular color in both the images are comparable. The image which satisfies most of the conditions is the best match. Retrieval result is not a single image but a list of images ranked by their similarities with the query image since CBIR is not based on exact matching. |
If I is the database image and IâÃâ¬ÃŸ is the query image, then the similarity measure is computed as follows, |
1. Calculate histogram vector vI = [vI1, vI2, ….vIn] and ccv vector cI = [cI1, cI2, ….cIn] of the database images. |
2. Calculate the vectors vIâÃâ¬ÃŸ and cIâÃâ¬ÃŸ for the query image also. |
3. The Euclidean distance between two feature vectors can then be used as the similarity measurement: |
4. If d ≤ τ (threshold) then the images match. |
5. From all the matching images we display top 24 images as a result. |
Segmenting the query image into 5 classes based on its brightness and calculates the Euclidean distance between the respective classes of query image and database image attributes. Mass, centroid and dispersion parameters are calculated for each class. These features are compared with database images stored features. The features values which are less than defined threshold are sorted based on increasing difference between query and database images then stored separately. |
EXPERIMENTAL RESULTS
|
Both color and shape retrieval algorithms are implemented in MATLAB with the database of 570 images. All the images are stored in JPEG format with size 384 × 256 or 256 × 384. There are six different categories; which includes 100 horse, 100 rose, 100 dinosaur, 100 bus, 100 elephants and 70 bikes. To evaluate the performance of the image retrieval algorithm we use the two most well known parameters; precision and recall. |
![image](https://www.rroij.com/articles-images/IJAREEIE-674-e011.gif) |
The system is executed with 10 images from each of the six categories and calculated the average precision and average recall parameters for all of them. The results obtained using shape and color based for different category of images is shown in Table-I. Retrieval result images with query image of shape and color based are shown in Figure 3a-b and 4a-b respectively. The combination of color and shape for different types of images is given in Table-II and corresponding result images are shown in Figure 5a-b. In both tables average accuracy of the proposed method is about more than 70 % which is much greater than the histogram based method. |
CONCLUSION
|
With the advent of various search engines, image searching has become an easier task. But all the search engines use text based retrieval techniques. Though CBIR is a happening topic, we cannot expect the entire upheaval of existing techniques with CBIR. But certainly, CBIR can be used to complement the existing machinery to provide better results. The CBIR methods presented herein use low- level features to generate results. The purpose of this paper was to improve the accuracy (precision) of a CBIR application by allowing the system to retrieve more images similar to the source image. The new algorithms under research and also the recently published ones seem to be extremely invasive on the image. Also each new algorithm is always seen to have certain regions where it works best and poor. The proposed methodology had increased the average precision from an average of 44% to an average of 72%. |
Tables at a glance
|
![Click Here Table icon](https://www.rroij.com/articles-images/table-icon.gif) |
![Click Here Table icon](https://www.rroij.com/articles-images/table-icon.gif) |
Table 1 |
Table 2 |
|
|
Figures at a glance
|
![Click Here Figure 1](https://www.rroij.com/articles-images/IJAREEIE-674-g001.gif) |
![Click Here Figure 2](https://www.rroij.com/articles-images/IJAREEIE-674-g002.gif) |
![Click Here Figure 3](https://www.rroij.com/articles-images/IJAREEIE-674-g003.gif) |
![Click Here Figure 4](https://www.rroij.com/articles-images/IJAREEIE-674-g004.gif) |
![Click Here Figure 5](https://www.rroij.com/articles-images/IJAREEIE-674-g005.gif) |
Figure 1 |
Figure 2 |
Figure 3 |
Figure 4 |
Figure 5 |
|
|
References
|
- Y. A. Aslandogan and C. T. Yu, "Techniques and Systems for Image and Video Retrieval," IEEE Transactions on Knowledge and Data Engineering, Vol. 11, Issue 1, pp. 56-63, Jan/Feb 1999.
- A. W. M. Smeulders, M. Worring, S. Santini, A. Gupta, and R. Jain, "Content-Based Image Retrieval at the End of the Early Years," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 22, Issue 12, pp. 1349-1380, December 2000.
- M. J. Swain and D. H. Ballard, „„Color indexingâÃâ¬ÃŸÃ¢Ãâ¬ÃŸ, International Journal of Computer Vision, vol. 7, Issue 1, pp. 11-32, 1991.
- Irena Valova, Boris Rachev and Michael Vassilakopoulos, “Optimization of the Algorithm for Image Retrieval by Color Features”, International Conference on Computer Systems and Technologies- CompSysTechâÃâ¬ÃŸ, pp 1-4, 2006.
- Sarfraz and M. Ridha “Content-Based Image Retrieval Using Multiple Shape Descriptors”, IEEE/ACS International Conference On Computer Systems and Applications, pp. 730-737, 2007.
- G. Pass and R. Zabih, “Histogram Refinement for Content-Based Image Retrieval,” 3rd IEEE Workshop on Applications of Computer Vision, pp. 96-102, 1996.
- A. Vellaikal and C. C. J. Kuo, „„Content Based Image Retrieval using Multiresolution Histogram RepresentationâÃâ¬ÃŸÃ¢Ãâ¬ÃŸ, SPIE - Digital Image Storage and Archiving Systems, Vol. 2606, pp. 312-323, 1995.
- H. J. Zhang, Y. Gong, C. Y. Low and S. W. Smoliar, „„Image Retrieval Based on Color Feature: An Evaluation StudyâÃâ¬ÃŸÃ¢Ãâ¬ÃŸ, SPIE - Digital Image Storage and Archiving Systems, vol. 2606, pp. 212-220, 1995.
- Shamik Sural, Gang Qian and Sakti Pramanik, “Segmentation and Histogram Generation Using the HSV Color Space for Image Retrieval”, International Conference on Image processing, Vol. 2, pp. 589-592, 2002.
- Xiaoqian Xu, Dah-Jye Lee, Sameer Antani, and L. Rodney Long, “A Spine X-Ray Image Retrieval System Using Partial Shape Matching”, IEEE Transactions On Information Technology In Biomedicine, Vol. 12, Issue 1, pp. 100-108, January 2008.
- Amit Jain, R. Muthuganapathy, and Karthik Ramani, “Content-Based Image Retrieval Using Shape and Depth from an Engineering Database”, Proceedings of the 3rd international conference on Advances in visual computing, Vol. Part II, pp. 255-264, 2007.
- Rafel C. Gonzalez and Richard E. Woods, “Digital Image Processing”, Second Edition, Pearson Education Asia, 2005.
- Aleksandra Mojsilovic, Jianying Hu and Emina Soljanin, “Extraction of Perceptually Important Colors and Similarity Measurement for Image Matching, Retrieval, and Analysis”, IEEE Transactions on Image Processing, Vol. 11, No. 11, pp 1238-1248, November 2002.
- Greg Pass, Ramin Zabih and Justin Miller, “Comparing Images Using Color Coherence Vectors”, Proceedings of the fourth ACM international conference on Multimedia, pp. 65-73, 1996.
- Dengsheng Zhang and Guojun Lu, “Review of shape representation andd escription techniques”, Pattern Recognition Society. Published by Elsevier Ltd, Vol. 37, pp. 1-19, 2004.
- A. J. M. Traina, A. G. R. Balan, L. M. Bortolotti, and C. Traina Jr., “Content- based Image Retrieval Using Approximate Shape of Objects”, Proceedings of the 17th IEEE Symposium on Computer- Based Medical Systems, pp. 91-96, 2004.
|