We develop for the CLEF PHOTO 2008 task a new visual features using various pixel projections for training SVMs, allowing us to produce image retrieval and clustering using a nity propagation. To heighten the diversity of the top of the retrieval results, we put the images with the lowest rank in each cluster into the top. The LSIS run which used only the visual information is at the 6th best team rank in the AUTO IMG run type. For AUTO TXTIMG runs, we merge by simple harmonic or arithmetic average our visual ranks to the textual ranks of the LIG language model participating to the AVEIR consortium. Then we also perform the a nity propagation and the reranking on this TXTIMG run, which gives complementary information to the AVEIR consortium, helping in producing the third best AUTO TXTIMG run (after XEROX). We discuss on the clustering performance of the various run types, and then we give some perspectives for enhancing such diversity image retrieval system. If a nity propagation clustering seems e cient for promoting visual diversity, our results show that clustering process itself should merge independant textual and visual clustering informations.
captions based on queries in a di erent language; both text and image matching techniques are
potentially exploitable. The photo retrieval task of ImageCLEF2008 is taking a di erent approach
to evaluation by studying image clustering. A good image search engine ensures that duplicate
or near duplicate documents retrieved in response to a query are hidden from the user. Ideally
the top results of a ranked list contains diverse items representing di erent sub-topics within the
results. Providing this functionality is particularly important when a user types in a query that
is either poorly speci ed or ambiguous; a common query in image search. Given such a query, a
search engine that retrieves a diverse, yet relevant set of images at the top of a ranked list is more
likely to satisfy its users [
Participants to ImageClef Photo run each provided topic on their image search system and
produce a ranking that in the top 20, holds as many relevant images that are representative of the
di erent sub-topics within the results. The de nition of what consitutes diversity varies across the
topics [
The CLEF image challenge is running on the image collection of the IAPR TC-12 photographic
collection provided for this task consists of 20,000 still natural images (plus 20,000 corresponding
thumbnails) taken from locations around the world and comprising an assorted cross-section of still
natural images [
These paper rst describes LSIS entropic features, LS-SVM and a nity propagation. Then we precise the LSIS runs method, before to detail and compare the results in the last section. The conclusion gives nally some strategies to enhance the clustering. 2
An important step in content-based image retrieval (CBIR) system is the extraction of discriminant visual feature that are fast to compute. Information theory and Cognitive sciences can provide some inspiration for developping such feature.
Among the many visual features that have been studied, the distribution of color pixels in an image is the most common visual feature studied. The standard representation of color for content-based indexing in image databases is the color histogram. A di erent color representation is based on the information theoretic concept of entropy. Such entropic feature can simply equal the entropy of the pixel distribution of the image, as proposed in [3]. A more theoretical presentation of this kind of image entropy feature, accompanied by a practical description of its merits and limitations compared to color histograms, has been given in [4].
We propose in [5,6] a new feature equal to the pixel 'pro l' entropy. A pixel pro l can be a simple arithmetic mean in horizontal (or vertical) direction. The advantage of such feature is to combine raw shape and texture representations in a low cpu cost feature. These feature, associated to mean and color std, reached the second best rank in the o cial ImagEval 2006 campaing (see www.imageval.org and [6]).
In this paper we extend these features using another projection to get the pixel pro l. We then propose also to use the harmonic mean of the pixel of each lign or column. The idea is that the object or pixel region distribution, which is lost in arithmetic mean projection, could be partly catch by the harmonic mean. These two projections are then expected to give complementary and/or concept dependant informations. We detail below the algorithm of the Pro l Entropy New num. of each topic 1 TOPIC 2 2 TOPIC 3 3 TOPIC 5 4 TOPIC 6 5 TOPIC 10 6 TOPIC 11 7 TOPIC 12 8 TOPIC 13 9 TOPIC 15 10 TOPIC 16 11 TOPIC 17 12 TOPIC 18 13 TOPIC 19 14 TOPIC 20 15 TOPIC 21 16 TOPIC 23 17 TOPIC 24 18 TOPIC 28 19 TOPIC 29 20 TOPIC 31 21 TOPIC 34 22 TOPIC 35 23 TOPIC 37 24 TOPIC 39 25 TOPIC 40 26 TOPIC 41 27 TOPIC 43 28 TOPIC 44 29 TOPIC 48 30 TOPIC 49 31 TOPIC 50 32 TOPIC 52 33 TOPIC 53 34 TOPIC 54 35 TOPIC 55 36 TOPIC 56 37 TOPIC 58 38 TOPIC 59 39 TOPIC 60
Topic short de nition church with more than two towers religious statue in the foreground
animal swimming straight road in the USA destinations in Venezuela black and white photos of Russia people observing football match exterior view of school building night shots of cathedrals people in San Francisco
lighthouse at the sea sport stadium outside Australia exterior view of sport stadium close-up photograph of an animal accommodation provided by host families
sport photos from California snowcapped building in Europe
cathedral in Ecuador views of Sydney's world-famous landmarks volcanoes around Quito group picture on a beach
bird ying sights along the Inka-Trail
people in bad weather tourist destinations in bad weather winter landscape in South America
sunset over water mountains on mainland Australia
vehicle in South Korea images of typical Australian animals indoor photos of a church or cathedral
sports people with prizes views of walls with unsymmetric stones famous television (and telecommunication) towers drawings in Peruvian deserts photos of oxidised vehicles
seals near water creative group pictures in Uyuni
salt heaps in salt pan Feature (PEF).
Let I be an image, or any rectangular subpart of an image. For each normalized color (L = R + G + B, r = R=L, and g = G=L), we rst calculate two orthogonal pro ls by the projections of the pixels of I. We consider two simple orthogonal projection axes : the horizontal axis X (noted
X ), versus the vertical one Y (noted Y ). The projection operator is either the arithmetic mean (noted 'Ar', then the projection is noted AXr), as illustrated in Figure 2, or the harmonic mean of the pixels on each column or each lign of I (noted 'Ha', then we have HXa).
Then, we estimate the probability distribution function (pdf) of each pro l according to [7]. Considering that the sources are ergodic, we naly calculate each PEF equal to the normalized entropy (H(pdf )=log(#bins(pdf ))). We detail below each steps of the PEF extraction. Let be op the selected projection, for each color of I of L(I) ligns and C(I) columns :
oXp(I) = p^df ( oXp(I)), over nbinX (I) = round(pC(I)) bins, where oXp is the vertical projection with operator op, P EFX (I) = H( oXp(I))=log(nbinX (I)).
P EFYoYp((II)) == Hp^d(f (oYpoY(pI()I))=)l,ogo(vnerbinnbYi(nIY))(.I) = round(pL(I)) bins,
We add to these P EFa the image entropic feature [3,4]: p^df (I) = pdf of all the pixels of I over nbinXY (I) = nbinX (I) nbinY (I) bins, P EF:(I) = H(p^df (I))=log(nbinXY (I)).
We naly complete the PEF features by the usual mean and standard deviation of each normalized color of I. Like in our VCDT IAPR CLEF system [8], we can calculate the PEF into three horizontal (versus vertical) subimages. For each, we have 3 bands and 3 di erent PEF for each of the 3 colors, plus their mean and variance, thus we have 3 3 3 + 3 3 2 = 45 dimensions for vertical and horizontal subimage features, for a total of 90 features by images for one projection type. Details can be found in [8].
70 60 50 40 300
signal RGB X profil 200 400 600 240 220 200 180 160 140 1200 50 Y profil 100
150 R/L G/L L
In this task, we used the support vector machine (SVM) to implement image retrieval. The
working mechanism of the SVM [
In our experiments we use LS-SVM with the RBF kernel
K(x1 x2) = exp( jx1 x2j2= 2) . So there is a corresponding parameter, , to be tuned. A large value of 2 indicates a stronger smoothing. Moreover, there is another parameter, , needing tuning to nd the tradeo between to stress minimizing of the complexity of the model and to stress good tting of the training data points.
In the experiment, we train for each topic an hundred of SVM with di erent and , and we selected the best SVM using a validation set. 4
A
nity Propagation We rst tried to use Clef Visual Concept models to clusterize the top 20 answers, but the result was not interesting, thus we changed for a recent clustering method : the a nity propagation clustering.
The advantages of a nity propagation clustering [
maxf0; r(i0; k)gg; f or i 6= k
X i06=i&i06=k a(k; k)
X maxf0; r(i0; k)g
i06=k
where s(i; k) re ects the similarity between the data points i and k. For all i 6= k , s(i; k) can
be set to be the negative Euclidean distance, namely, s(i; k) = kxi xkk2 ; while for all i = k,
s(k; k) is a varying parameter, and the initialized values of s(k; k) for all ks are set to be equal
to each other because all data points are equally suitable as exemplars. The a nity propagation
takes a real number s(k; k) as its input. The number of identi ed exemplars (number of clusters)
is in uenced by the initialized value of s(k; k) . As reported in the literature [
In our experiments, we computed the weighted averages of two ranks : our visual system
described in this paper, and the LIG TXTIMG [
The process we adopt to implement the image retrieval in photo task is shown in g. 3, and
depicted by the following steps:
Step 1) According to the keywords of each topic, perform the text retrieval on the XML text
database, and then get the TXT rank (please refer to the LIG Photo Clef paper [
In photo task, we set equal to 20. 5
to be 0.2 in order that the number of clusters we get is approximately Step 2) Extract the visual features from the training image data using our extraction method; train and generate an hundrer of SVMs with di erent parameters.
Step 3) Use the rst 20 images in TXT ranks as the positive samples, and the others as the negative samples to construct the validation set; select the best one among the SVMs. Step 4) Extract the visual features from the visual image database using our extraction method; use the best SVM as the tool to perform the image retrieval and produce the rank result called IMG rank.
Step 5) Merge IMG and TXT rank into Rank-without-Clustering, where 't' in the gure denotes the text ratio, in our experiments t=0.5.
Step 6) Perform the clustering on the top 1000 images in Rank-without-Clustering for each topic, using a nity propagation.
Step 7) Select the image with the lowest rank in each cluster, put these images in their old order from Rank-without-Clustering and on the top of 'Final Rank'; then they are followed by the others in the old order.
We submitted 15 runs, one of which used only the visual information, others used both text and visual information. We make the fusions with either arithmetic or harmonic means.
Evaluation are based on two measures: precision at 20 and instance recall at rank 20 (also
called S-recall) [
The rst run is a visual only run. We simply train several SVMs on the training set, optimised
with the TEXT AVEIR preprocess without clustering. Then we make 20 clusters using a nity
propagation on the top 1000 images for each topic and we place the best (the image with the
lowest rank) of each cluster to the top 20 (nearly), and we keep the rest of the list as the order
before the clustering. This baseline LSIS IMG+CLUSTER (RUN1) is the 6th best team run in
the Auto IMG run type [
We use LIG TXTIMG to train SVMs and to make fusions, then we make 20 clusters using a nity propagation on the top 1000 images for each topic after the fusion of visual and LIG TXTIMG and we place the best (the image with the lowest rank) of each cluster to the top 20 (nearly), and we keep the rest of the list as before the clustering. It is important to note that here the visual and text information are merged before the clustering. We will show in the end of the paper that it could be more e cient to make a nity propagation on visual and on textual ranking, and then to merge them. 6
The results for visual on only LSISrun1(IMG) with clustering are given in table 2. For comparison we give the results of the other runs of the same type submitted to CLEF. The LSIS visual only system seems quite e cient : using the low dimensional PEF features the LSIS team rank in the IMG run type is 6th. Moreover, this visual information, giving complementary information, enhanced the AVEIR consortium run (third rank at the IMGTXT run type).
The results for combination of visual with textual informations (IMG+TXT), with (run12) or not (run0) clustering, are given in table 3. For comparison we give the results of few runs of the same type submitted to CLEF, and some runs of AVEIR consortium in which our IMG+TXT LSISrun0 has been merged.
Because of the large variation of the considered topics (see tab. 1), the clustering evaluation must be analysed at the topic level. We then analyse for each topic in the next gure the CR20 after a nity propagation of each topics (numeroted from 1 to 39) for LSIS run1 (IMG) vs LSIS run12 (TXT IMG), see g 4. The correlation between the two runs is low (0.3). We see clearly that some topics like 14 or 28 are di cult to cluster, contrary to 6 or 33 topics. Moreover if for most of the topics the CR20 is improved, we see the inversed for some topics.
To detail the impact of the text information to the cluster quality, we plot in g. 5 the gain values for each run between these two runs. We see then clearly that the global gain of nearly 68% is not uniform over each topic. If the majority of the CR20 are, some topics are better clusterised by a nity propagation using only the visual ranking. These variations need more research for being well interpreted.
The next gure shows the gain of CR20 from the LSIS visual only TXTIMG run to the LSIS TXTIMG+ a nity propagation CLUSTER (see g. 6). The global gain is low (3.7%) but again the variation for each topic is high : if for some topics the text information itself allows an e cient 0.9 0.8 T0.7 X T ILG0.6 18 d n a liua0.5 s v S ILS0.4 0 2 R C0.3 0.2 0.4 0.5 0.6 CR20 LSIS visual only 0.7 implicit image clustering, the visual clustering alone is fondamental for some other topics. This could be explained by the fact that some clusters are more or less high level clusters. In other terms, some clusters may be more cultural (cities, country,...) than being only based on visual criteria.
Even if a nity propagation clustering seems e cient for promoting visual diversity, our results show that visual and textual information brings complementary clustering informations, which should be weigthed according to each topic. We shown that linear weighted fusion was e cient for topic retrieval in ImagEval campaign [6]. In this paper the visual and text information are merged before the clustering, so we can't weight textual and visual clustered ranks. It may be more e cient to make a nity propagation separatly on visual and on textual ranks, and then to merge them. Further works will be conducted for designing such simple clustering linear weighting fusion schemes.
We thank P. Mulhem from LIG for having provided the IMGTXT runs in the AVEIR consortium image CLEF. This work was partially supported by the French National Agency of Research (ANR-06-MDCA-002). IGM 150 − S U L C − ILSS 100 t s n i a g a TTX 50 G M I − S U L−C 0 S I S L ) % ( ian −50 g −1000
5 10 15 20 25 30 35 topics renumeroted from 1 to 39. gain > 200 are repres. as 200. Global gain = 67. 40
[3] M. Jagersand, Saliency maps and attention selection in scale and spatial coordinates: An information theoretic approach, in Proc. of 5th Int. Conference on Computer Vision, 1995. [4] Iyengar J. Zachary, S.S and Barhen J., Content based image retrieval and information theory: A generalized approach, in Special Topic Is- sue on Visual Based Retrieval Systems and Web Mining, Journal of the American Society for Information Science and Technology, 2001, pp. 841-853. [5] H. Glotin, "Robust Information Retrieval and perception for a scaled Lego-Audio-Video multistructuration", Thesis of habilitation for research direction, University Sud Toulon-Var, 2007. [6] S. Tollari and H. Glotin, Web image retrieval on imageval: Evidences on visualness and textualness concept dependency in fusion model, in ACM Int Conf on Image Video Retrieval, 2007. [7] R. Moddemeijer, On estimation of entropy and mutual information of continuous distributions, Signal Processing, vol.16, no.3, pp. 233-246, 1989. [8] H. Glotin, Z. Zhao, Pro l Entropic visual Features for Visual Concept Detection in CLEF 2008 campaign, In Working Notes of ImageCLEF2008, Danmark, in conjuction with ECDL 2008. [9] Chen, H. and Karger, D. R. 2006. Less is more: probabilistic models for retrieving fewer relevant documents. In Proceedings of the 29th Annual int. ACM SIGIR Conference on Research and Development in information Retrieval (Seattle, Washington, USA, August 06 - 11, 2006).
SIGIR '06. ACM, New York, NY, 429-436. [10] Song, K., Tian, Y., Gao, W., and Huang, T. 2006. Diversifying the image retrieval results. In Proceedings of the 14th Annual ACM int. Conference on Multimedia (Santa Barbara, CA, USA, Oct. 23-27). MULTIMEDIA '06. ACM, New York, NY, 707-710. [11] Zhai, C. X., Cohen, W. W., and La erty, J. 2003. Beyond independent relevance: methods and evaluation metrics for subtopic retrieval. In Proceedings of the 26th Annual int. ACM 40
SIGIR Conference on Research and Development in informaion Retrieval (Toronto, Canada, July 28 - August 01, 2003). SIGIR '03. ACM, New York, NY, 10-17.