Histograms For Texture Based Image Retrieval
Histograms For Texture Based Image Retrieval
Histograms For Texture Based Image Retrieval
Christian Wolf 1, Jean-Michel Jolion 2 and Horst Bischof 1 1 Vienna Univ. of Technology, Pattern Recognition and Image Proc. Group Favoritenstr.9/1832, 1040 Wien, Austria http://www.prip.tuwien.ac.at 2 INSA de Lyon, Lab. Reconnaissances de Formes et Vision 20, Avenue Albert Einstein, 69621 Villeurbanne cedex, France http://rfv.insa-lyon.fr
Abstract: Content based image retrieval is the task of searching images from a database, which are visually similar to a given example image. Since there is no general de nition for visual similarity, there are di erent possible ways to query for visual content. In this work we present methods for content based image retrieval based on texture similarity using interest points and Gabor features. Interest point detectors are used in computer vision to detect image points with special properties, which can be geometric (corners) or non-geometric (contrast etc.). Gabor functions and Gabor lters are regarded as excellent tools for texture feature extraction and texture segmentation. We present methods how to combine these methods for content based image retrieval and to generate a histogram based texture description of images. Experimental results of the query system on test image databases are given.
1 Introduction
Content based image retrieval systems use the contents of a query image provided by the user to search for similar images in a possibly large database. All of the known methods for pre-attentive search emphasize the need for descriptions of images and powerful metrics to compare these descriptions. Most common approaches are based on colour 11], structure 5], textures 8] or combinations 10]. Histograms have already been used extensively for image indexation, especially colour histograms 12] and structure based methods 5]. They provide an e ective and e cient means to compare image contents. However, they rely on raw image data like colour or gray values, which are not available for textures without pre-processing. In this paper we describe a method based on histograms lled with local texture features extracted on interest points using a Gabor lter bank.
now on referred to as amplitude only. It tells how strong this interest region responds to the lter applied to it. Literally spoken we could say that it speci es how much structure of the given orientation in the given scale can be found in that region. Depending on the ordering of the lter responses we can build di erent image descriptors. In this paper we will introduce two di erent types: An ordered set of histograms storing amplitude distributions and an ordered set of histograms storing di erences of amplitudes.
Filling the histograms this way we ignore the spatial coherence of the di erent interest regions, i.e. the locations of the regions are not represented in the histogram. It does not matter where an interest region is found, since only the contents (translated into lter responses) is used to create the histograms. In order to add the spatial coherence to our representation we use two-dimensional histograms instead of one-dimensional ones. We need couples of data instead of single values to increase the histogram bins. These couples are created by performing a -nearest neighbour search for every interest point.
n
The entries, which increase the histograms, are pairs of interest points. All points of the image are traversed and taken as rst points of these pairs. The second points are the neighbours found by a -nearest neighbour search performed for each interest point found during the traversal. Hence, for each interest point traversed we create pairs of points. The amplitudes of the couples are entered into the histogram: The amplitude of the rst point is used to calculate the -index of the bin, the amplitude of the second point (the neighbour) to calculate the -index.
n n x y
Figure 1 shows an example image and two 2D histograms out of its histograms. The images contains mainly horizontal structures (orientation 0). Therefore, the histogram for orientation 0 shows strong responses, i.e. high bins from indices 4 to 6. The histogram for orientation index K , which corresponds to structures in orientations around 45 degrees, shows 4
K S
Figure 1: Image (a) and the histograms (amplitude amplitude) for 0o (b) and 45o (c)
The comparison of two images is based on already known distance measurements of histograms and the means of these distances. For the distances between two single histograms we used the Battacharrya distance, which performed slightly better than the 2 distance, thus con rmed results of Huet and Hancock 5]. We included some compensation for rotation by comparing each histogram not only with its corresponding histogram but as well with the immediate neighbours of the same scale. We can represent our ordered set of 3 8 histograms as a set of 3 vectors, each containing 8 histograms. By cyclic permutation of each of these vectors and taking the minimum of comparison and comparison with one rotated vector, we get the nal distance.
L
The information we store in this representation can be described in the following way: Like in our rst histogram representation the data is separated by lter index, i.e. one histogram for each orientation and scale of the lter bank. Each histogram holds the information how the amplitudes for this lter change between the interest points to their neighbours. The dimension of the histogram stores the neighbourhood ranking of the -nearest neighbourhood search, thus the bins with higher indices store the di erences of amplitudes between interest points which are further away than couples of interest points stored in the bins with lower indices.
y n y y
Figure 2: Two images and the histogram (di erences of amplitude ranking) for 0o
Figure 2 shows two example images of one of our test databases and their histograms for scale index 0 and orientation index 0, which corresponds to an orientation of 0o . The histogram of the texture example (Figure 2.a) shows an almost uniform distribution along the coordinate of the histogram. This can be explained by the periodic nature of the texture example, where the di erences in the amplitudes are almost constant across the di erent distances between two interest points. Considering the histogram of the natural image on the other hand (2.b), we remark the di erence in the bin sizes along the coordinate of the histogram. The reason is the di erent type of the image, which contains sharp changes in structure. In this image the distance between two interest points determines the di erence in their responses to a speci c lter, hence the di erence in amplitudes.
y y
4 Experimental Results
Our test database contains 609 images grabbed from a French television channel. The images are all of the same format (384x288 pixels) and coded in JPEG with 75% quality. The contents
di ers from outdoor activities (reports of sports) to talk shows, full scope shots of people, weather forecasts, logos and advertisements. To be able to measure a query performance a manual clustering of the image set was necessary. The clusters contain images of successive sequences. In fact, the pictures of one cluster mostly are taken from the same program and sometimes even from the same scene. We used the following parameters in our experiments: We extract = 200 interest regions of size 32 32 pixels. The Gabor lter bank contains = 8 3 lters.
N S
Since there is no general de nition for visual similarity between images, measuring retrieval performance is a di cult task and depends on the purpose. A single query uses one image out of a cluster , which contains images. The system answers with images of which are from the original cluster . We use a measure which is widely used for indexation systems: precision.
C d c r C P
r c
As the name suggests, the precision of the result of a single query denotes how precise the result set responds to the desires of the user. By changing the size of the result set we get a performance curve for this query. We calculate the nal curve for a retrieval method by averaging the curves for all single queries using di erent query images. Figure 3.a shows two curves measured for the two histogram types. For a typical result set of 10 pictures 74 % of the images are relevant, for 20 pictures 62 %. The histogram set storing the amplitude distribution performs slightly better than the version storing amplitude di erences and neighbourhood ranking. We conclude, that the absolute amplitude information is more descriptive than the relative information. I.e. the information, which orientations and scales are present in the image is more descriptive than the information how much the amplitudes change in the spatial neighbourhood of the interest points. Figure 3.b shows performance curves of the amplitude distribution method with di erent counts of interest points collected. As we can see the performance of the algorithm is weakly dependent on the number of interest points. If enough area of the image is covered by interest regions, and if the histograms are lled enough | i.e. the number of non-zero bins of the normalised histogram is su ciently high | then increasing the number of interest points does not increase query performance. For our experiments we used di erent interest operators: Two di erent implementations of the Harris corner detector 3], two di erent versions of the Loupias wavelet based interest point detector 7] based on the Haar and the Daubechie wavelet respectively, and the Jolion multiresolution contrast based interest point detector 2]. To evaluate the dependency of our algorithms
100 (a) Average precision - amplitude distribution (b) Average precision - difference of Amplitudes 80 Average precision (%)
100 600 points 400 points 300 points 200 points 100 points 50 points
80
60
60
40
40
20
20
(a)
100 Haar wavelet (Loupias) Daubechie wavelet (Loupias) Harris implementation 1 Harris implementations 2 Multiresolution contrast based (Jolion) Detector selecting random points Average precision (%) 100 80 Average precision (%) 80
(b)
48 neighbours 24 neighbours 12 neighbours 6 neighbours 3 neighbours
60
60
40
40
20
20
(c) (d) Figure 3: The performance curves for both histogram types (a) for di erent counts of interest points (b) for di erent interest point detectors (c) and for di erent counts of neighbours (d) on the choice of the interest point operator, we additionally implemented an "interest point operator" selecting a xed number of random points in an image. Figure 3.c shows performance curves of the amplitude based algorithm and di erent detectors. We remark, that the di erences in performance between the various detectors are not significant. However, surprising is the good performance of the algorithms in experiments where the random interest point detector is used. The performance of the random points operator is equal to the performance of the other operators. This can be explained with the richness of our image features. The feature data collected on the interest points has enough descriptive power, which is not improved by a stable interest point detector choosing points "appropriate" for our type of features. The number of neighbours for the -nearest neighbour search determines how much in uence of the spatial coherence of the feature data is represented in the histogram. However, the number has to be adjusted to the data. If the algorithm does not search enough neighbours, then the spatial coherence is under represented in the histogram. If the algorithm searches too
n n
many neighbours on the other hand, then the information about the spatial coherence is lost, since the found neighbours tend to be the same for points near to each other. We conducted experiments using 3, 6, 12, 24 and 48 neighbours. Surprisingly there is almost no di erence in the query performance (Figure 3.d), although counts of = 12 or even = 48 are far too high to store any spatial information in the histograms, considering that = 200 interest points are collected on each image. We conclude, that the additional information about the spatial coherence does not change the descriptiveness of the histograms.
n n N
References
1] Sushuil Bhattacharjee. Image retrieval based on structural content. Technical Report SSC/1999/004, Dept. of Electrical Eng., E.P.F.L, CH-1015, Lausanne, 1999. 2] Stephan Bres and Jean-Michel Jolion. Detection of interest points for image indexing. In 3rd Int. Conf. on Visual Information Systems, Visual 99, pages 427{434. Springer, Lecture Notes in Computer Science, 1614, June 1999. 3] Chris Harris and Mike Stephens. A combined corner and edge detector. In Proceedings 4th Alvey Visual Conference. Plessey Research Roke Manor, UK, 1988. 4] A Heinrichs, D Koubaroulis, B Levienaise-Obadia, P. Rovida, and J.M. Jolion. Image indexing and content-based search using pre-attentive similarities. In 6th RIAO Conference, PARIS, April 12-14 2000. 5] Benoit Huet and Edwin R. Hancock. Cartographic indexing into a database of remotely sensed images. In Third IEEE Workshop on Applications of Computer Vision (WACV96), pages 8{14, Sarasota, Florida, Dec 1996. 6] A K Jain and F Farrokhina. Unsupervised texture segmentation using gabor lters. Pattern Recognition, 24(12):1167{1186, 1991.
7] Eienne Loupias and Nicu Sebe. Wavelet-based salient points for image retrieval. Technical Report RR 99.11, Laboratoire Reconnaissance de Formes et Vision, 1999. 8] B S Manjunath and W Y Ma. Texture features for browsing and retrieval of image data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(8), August 1996. 9] Ovidiu Popescu. Utilisation des points d'inter^t pour l'indexation d'images. Technical Report RR 99.07, e Laboratoire Reconnaissance de Formes et Vision., 1999. 10] Cordelia Schmidt and Roger Mohr. Local gray value invariants for image retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(5), May 1997. 11] Markus Stricker and Alexander Dimai. Color indexing with weak spatial constraints. SPIE, 2670/29(08194-2044-1), 1996. 12] M Swain and D Ballard. Color indexing. International Journal of Computer Vision, 7(1):11{32, 1991.