Nowadays, a very large number of digital image archives is easily produced thanks to the wide diffusion of personal digital cameras and mobile devices with embedded cameras. Thus, each personal computer, personal storage unit, as well as photo-sharing and social-network web sites, are rapidly becoming the repository for thousands, or even billions of images (i.e., more than 100 million photos are uploaded every day on the social site Facebook1). As a consequence, there is an increasing need for tools enabling the semantic search, classification, and retrieval of images. The use of meta-data associated to images solves the problems only partially, as the process of assigning reliable meta data to images is not trivial, is slow, and closely related to whom performed the task. One solution for effective image search and retrieval is to combine content-based analysis with feedbacks from the users. In this paper we present Image Hunter, a tool that implements a Content Based Image Retrieval (CBIR) engine with a Relevance Feedback mechanism. Thanks to a user friendly interface the tool is especially suited to unskilled users. In addition, the modular structure permits the use of the same core both in web-based and stand alone applications. Roberto Tronci Gabriele Murgia Maurizio Pili AMILAB - Laboratorio Intelligenza d'Ambiente, Sardegna Ricerche, loc. Piscinamanna, I-09010 Pula(CA), Italy, e-mail: froberto.tronci, gabriele.murgia, maurizio.pilig@sardegnaricerche.it 1 http://blog.facebook.com/blog.php?post=403838582130
The growing number of digital data such as text, video, audio, pictures or photos is pushing the need for tools allowing the quick and accurate retrieval of information from data. Whereas the results of traditional text data search methods are quite satisfactory, the same can not be said for visual or multimedia data. So far, the most common method for image retrieval is predicated on adding meta-data to the images as keywords, tag, label or short descriptions, so that the retrieval can occur through such annotations. The manual cataloguing of images, even though it requires expensive work and a large amount of time, is often not so effective. Describing a picture in words is not always easy, and the relevance of the description is strictly subjective.
By now, all mobile phones are equipped with cameras, and thanks to the Internet,
social networks and almost “unlimited” storage space, the exchange of photos and
digital images has become frenetic, to say the least. As a consequence there is an
increasing need for tools enabling the semantic search, classification, and retrieval of
images. As above-mentioned, the use of meta-data associated to the images solves
the problems only partly, as the process of assigning meta data to images is not
trivial, slow, and closely related to the persons who performed the task. This is
especially true for retrieval tasks in very highly populated archives, where images
exhibit high variability in semantic. It turns out that the description of image content
tends to be intrinsically subjective and partial, and the search for images based on
keywords may fit users’ needs only partially. For this reason, since the early nineties,
the scientific community focused on the study of Content Based Image Retrieval [
Image Hunter is a full content-based image retrieval tool which does not need
a text query in contrast to the vast majority of other applications [
The rest of the paper is organized as follows. Section 2.1 illustrates the core of the application, and its connections between the different modules. Section 2.2 briefly reviews the integrated learning process and relevance feedback mechanisms implemented in the application. Section 2.3 shows the graphical interface and explains how it works. Experimental results are reported in Section 3. Conclusions are drawn in Section 4.
With the aim of building a practical application to show the potentialities of Content
Based Image Retrieval tools with Relevance Feedback, we developed Image Hunter.
This tool is entirely written in JAVA, so that the tool is machine independent. For its
development, we partially took inspiration from the LIRE library [
Image Hunter is made up of two main parts: the core, and the user interface.
The main core of Image Hunter is a full independent module in order to allow the development of a personalized user interface. The core is subdivided into four parts: Indexing LIRE interface Lucene interface for data storing
Collection Search and Relevance Feedback The “Indexing” part has the role of extracting the visual features from the images. The visual features and other descriptors of the images are stored in a particular structure defined inside Image Hunter. For each image collection, all the data are stored in a database built according the Apache Lucene standard. Lucene turned out 2 http://lucene.apache.org/ to be well suited for the storage needs of Image Hunter, as it resulted faster than other SQL based solutions. In particular, the indexes created by the use of Lucene can be easily moved by copying the folder that contains the index. In this way it is also quite simple to build a “portable” version of Image Hunter. Moreover, we had also adapted some of the main classes defined by Lucene to better fit to our needs: e.g., we created some methods to simplify the index administration, and we enriched the functionality of document manipulations.
Finally, we describe the “Collection Search and Relevance Feedback” module that is the more important as it implements the core engine of our system. Each time a user submits an image to be used as a visual query, the system computes the visual similarity between the query and each image in the collection. This visual similarity is computed in terms of the average of the normalized distances in each feature space. Then, the user can label the images provided by the system as relevant to her search or not, and the system exploits this feedback to learn which is the best combination of visual features that represents the semantic meaning that the user is associating to the query. Thus, in the feedback elaboration process, the visual similarity is computed in terms of a weighted combination of the distances in different feature spaces, rather than in terms of the average distance. In the following sections we describe the Relevance Feedback techniques implemented in Image Hunter (Section 2.2), and the web-based user interface that we have developed (Section 2.3).
In this section the three relevance feedback techniques implemented in the core
are described. Two of them are based on the nearest-neighbor paradigm, while one
of them is based on Support Vector Machines. The use of the nearest-neighbor
paradigm is motivated by its use in a number of different pattern recognition fields,
where it is difficult to produce a high-level generalization of a class of objects, but
where neighborhood information is available [
In this work we resort to a technique proposed in [
n=t 1 + n=t where NNr(I) and NNnr(I) denote the relevant and the non relevant Nearest Neighbor of I, respectively, and k k is the metric defined in the feature space at hand, relBQS(I) = 1 e 1 dBQS(I) max dBQS(Ii)
i
1 e
where e is the Euler’s number, i is the index of all images in the database and
dBQS is the distance of image I from a reference vector computed according to the
Bayes decision theory (Bayes Query Shifting, BQS) [
F rel(I) = å w f rel f (I)
f =1 w f =
R 1 å i=1 posif F R 1 å å k=1 i=1 posik
Support Vector Machines are used to find a decision boundary in each feature space f 2 F. The use of a SVM for this tasks is very useful because, in the case of image retrieval, we deal with high dimensional feature spaces. For each feature space f , a SVM is trained using the feedback given by the user. The results of the SVMs in terms of distances from the hyperplane of separation are then combined into to a relevance score through the Mean rule as follows relSV M(I) = 1 F
å relSfV M(I) F f =1 (7)
The user interface is structured to provide just the functionalities that are strictly related with the user interaction (e.g., the list of relevant images found by the user). Image Hunter employs a web-based interface that can be viewed at the address http://prag.diee.unica.it/amilab/WIH. This version is a web application built for the Apache Tomcat web container by using a mixure of JSP and java Servlet. The graphic interface is based on the jQuery framework, and has been tested for the Mozilla Firefox and Google Chrome browsers. When the web container is launched, a servlet checks if the folder of the collection contains an updated Lucene index; if not, the index is updated. Afterward, the index is loaded by the web application and used for all the sessions opened by the remote clients (see Figure 2). The Image Hunter homepage let the user choose the picture from which starting the search. The picture can be chosen either within those of the proposed galleries or among the images from the user hard disk (see Figure 3). Each query is managed by a servlet that queries the Image Hunter engine and displays the 23 most similar images according to the mechanisms reported in Section 2.2. The choice of the number of images displayed to the user on the one hand takes into account the needs of the page layout and, on the other hand, is oriented to maintain high the user attention. In order to make more intuitive and easy the features of the application, the graphical interface has been designed relying on the Drag and Drop approach (see Figure 4). From the result page the user can drag the images that her deems relevant to her search in a special boxcart, and then submit the feedback. Then the feedback is processed by the system, and a new set of images is proposed to the user. The user can then perform another feedback round.
In order to make the system more flexible for skilled users, the Settings page allows choosing the low-level feature used to describe the image content. In particular, it is possible to select between 7 color based descriptors that are: Scalable Color, a color histogram extracted from the HSV color space; Color Layout, that characterizes the spatial distribution of colors; RGB-Histogram and HSV-Histogram, based on RGB and HSV components of the image respectively; Fuzzy Color, that considers the color similarity between the pixel of the image; JPEG Histogram, a JPEG coefficient histogram, and ABIF32 obtained rescaling the images to 32x32 size and returning a color histogram extracted from the RGB color space. It is also possible choosing between different texture and shape features that are: EDGE Histogram, that captures the spatial distribution of edges; Tamura, that captures different characteristic of the images like coarseness, contrast, directionality, regularity, roughness, and Gabor that allows the edge detection. In addition, it is possible to use two descriptors that merge color and texture characteristics: CEDD (Color and Edge Directivity Descriptor), and FCTH (Fuzzy Color and Texture Histogram).
One of Image Hunter’s greatest strengths is its flexibility, as it is possible to add any other image descriptor. The choice of the above mentioned set is due to the “real time” nature of the system. In fact even if some local features such as SIFT or SURF could improve the retrieval performances for some particular kind of searches, on the other hand they are more time expensive in the evaluation of the similarity between images.
In addition, in the Settings page the user can select the Relevance Feedback technique to be used, and the dataset to explore.
In the experimental evaluation of Image Hunter we performed both a full automatic
test by using the MIRFLICKR-25000 collection [
In the automatic test, we analyzed all the tags of the collection by a semantic point of view, and fused the tags with the annotations in a tag verification process. This process was performed to keep only the tags which occur in at least 100 images, so that the single tags/concepts are adequately represented in the dataset used in the evaluation experiments. This process of fusing and discarding tags brought us to keep 24718 images and 69 tags, with an average number of tags per image of 4.19. Thus, as “starting” query images, we chose 1294 of them from the refined collection. These query images have a number of tags per image that varies from 3 to 10 (i.e., the single image can represent different meanings) , with an average number of tags per image equal to 4.69 (thus very similar to the value in all the collection). For each one of the 1294 query image, a relevance feedback experiments had been performed by using all the tags as a target, i.e., given a query image, we considered, one at a time each single tag as target of the retrieval process to be refined through the relevance feedback. Thus, each query image has been used as starting example 3 http://www.sardegnadigitallibrary.it for different retrieval tasks. In this way, 6070 retrieval tasks were performed for each relevance feedback technique implemented inside Image Hunter.
Each automatic experiment consists of 10 iterations: the first one is based on a nearest neighbor search on all the feature spaces, and the other 9 iterations are based on one of the relevance feedback techniques described above. At each iteration we simulated the feedback from the user on 20 images.
The User Experience test has been performed by 52 users that were asked to perform one or more searches by choosing as query one out of 32 images (See Figure 5) that we selected so that they exhibited different subjects, different colors and shapes. The users can choose to perform any number of consecutive iterations to refine the search. On average, each of the 32 queries has been used 6.75 times and the users performed an average of 5 iterations. At each iteration n = 23 images are shown to the user for marking the feedback.
The performance of the experiments will be assessed using the Precision and a modified definition of the Recall, that we named “user perceived” Recall.
The Precision is a measure that captures how many relevant images are found within the images that are “shown” to a user, and it is computed as follows: p =
A(q) \ R(q)
A(q) (8) where A(q) is the ensemble of images retrieved by using the query q, while R(q) is the ensemble of images that in the collection are relevant according to the query q.
The Recall measures how many relevant images are found among the set of images in the collection that have the same tag/concept: In this way we compute the percentage of relevant images with respect to the totality of relevant images in the collection. This measure has a disadvantage: if the total number of relevant images in a collection for a given tag is greater than the number of images shown by the system, the measure is going to be always less than 100% even if all the images shown to the user are relevant. Thus, this measure doesn’t represent the perception, in term of performance, that a real user will have on the system. In addition, each class contains a different number of images, and therefore the denominator of Equation 9 differs from one class to another even in one order of magnitude, and it can completely distort the average performance. For these reasons, we propose to use a modification of the recall measure namely, the “user perceived” Recall. This is a recall measure takes into account just the maximum number of relevant images that can be shown to the user according to the number of iterations, and the number of images displayed per iteration, and it is computed as follows rp =
A(q) \ R(q)
R (q) ;
R (q) =
R(q) , if jR(q)j n i , otherwise n i where A(q) is the number of images retrieved by using the query q up to the iteration i, R(q) is the number of relevant images in the dataset (for the query target), j j indicates the cardinality of the set, and n is the number of images shown to the user per iteration.
In an unlabelled dataset it is more difficult to define the set of similar images, so in the User Experience test for each query image we have formed the set of relevant images by considering the images marked as Relevant by at least the 50% of users. Indicating as Rb(q) this ensemble of images retrieved by using the query q the Recall will be: (9) (10) r =
A(q) \ Rb(q)
Rb(q)
: n i, so the Recall and the “user perceived” Recall
A(q) \ R(q)
R(q) It is worth to note that jRb(q)j agree.
In the automatic test we compared the performance of all the relevance feedback techniques described in the previous section, i.e., the k-NN based on Equation (5) (NN in the tables), the k-NN based on Equation (6) (PR in the table), and the SVM, with the performance attained by simply browsing the image collection. In the User Experience test, we just used the NN relevance feedback mechanism. The term browsing indicates nothing more than showing the user the n images nearest to the query with no feedback. The aim of comparing relevance feedback with browsing is to show the benefits of relevance feedback. To put it simple: can a relevance feedback approach retrieve more relevant images than simply browsing the collection by sorting the images according to the visual similarity with the query?
The average results in terms of Precision, and “user perceived” Recall obtained in the automatic test are presented in Table 1. The results show that, as the number of iterations increase, the performance of the relevance feedback methods increase, as well as the difference in performance with the browsing. From these analysis it turns out that the behavior of the two k-NN methods are quite similar, while the SVM exhibits the biggest increasing performance power. To evaluate the User Experience, we show the values of the recall measure: Table 2 reports the obtained results. The performance of the RF technique w.r.t. the browsing shows as the user interaction permits a very big improvement of the performance and as the system learn how to find images that fulfil the user’s desires. We observed that the users tend to label as “Relevant” less and less images after few iterations, especially if she is satisfied with the previous results, because labelling the images is an annoying task. As a consequence, the reported values of the recall can be considered as a lower bound of the true performances, as they take into account just the images actually labelled by the user.
In this paper we presented Image Hunter, a tool that exploits the potentiality of Relevance Feedback to improve the performance of Content Based Image Retrieval. Unlike other proposed tools, Image Hunter is a full content based image retrieval system in which the user’s feedback is integrated in the core of the application, and permits a dynamical adaptation of the queries driven by the user. The proposed results obtained both in a full automatic test, and in a user test show how the integration of the relevance feedback improves significantly the performance of the image retrieval system making the search more effective w.r.t. the web browsing.