UPMC at MediaEval 2013: Relevance by Text and Diversity by Visual Clustering

Abstract

In the diversity task, our strategy was to, rst, try to improve relevance, and then to cluster similar images to improve diversity. We propose a four step framework, based on AHC clustering and di erent reranking strategies. A large number of tests on devset showed that most of the best strategies include text based reranking for pertinence, and visual clustering for diversity - even compared to location based descriptors. Results on expert and crowd-sourcing testset grounds truths seem to con rm these observations.

1. INTRODUCTION

In the Retrieving Diverse Social Images Task of MediaEval 2013 challenge [ 1 ], participants were provided with a ranked list (we called \baseline") of at most 150 photos of a location (the query) from Flickr.com. For each query, our strategy to induce diversity while keeping the relevance is based on four steps. Step 1: Rerank the baseline to improve relevance. Step 2: Cluster the results using an Agglomerative Hierarchical Clustering (AHC). Step 3: Sort the clusters based on a cluster priority criteria; and then sort the images in each cluster. Step 4: Finally rerank the results alternating images from di erent clusters.

It is important to notice that the AHC does not take the image rank into account, but when we sort the clusters and the images in the cluster (Step 3) the rank obtained in Step 1 is crucial information that we exploit. In fact, it is the only way to guarantee global relevance with respect to the query.

SIMILARITIES AND DISTANCES

To rerank the baseline list according to the similarity to the query (Step 1) and to cluster images (Step 2), we need to compare the images. We tested on the devset several similarities and distances, for di erent types of descriptors: visual, textual, GPS and a geographic tree thesaurus. For all visual descriptors provided by the organizers [ 1 ] (CN3x3, LBP3x3, CSD, HOG... ), we use the Euclidean distance. For textual descriptors, we use Dirichlet Prior Smoothing [ 3 ] for the probabilistic model; the cosinus for TF-IDF weighting; the formula mentioned in [ 4 ] for Social TF-IDF weighting.

To estimate the distance between two GPS coordinates, we compute the classical great-circle distance using the Haversine formula. For the keywordsGPS subset, all the retrieved images have GPS coordinates; but for the keywords subset, approximately 60% of the images do not have any coordinates. For these images, we choose to attribute them the GPS coordinates of the nearest image, among the images of the same query, according to the visual distance. Moreover, if the smallest visual distance is greater than a threshold, the system associates the (0,0) GPS coordinates to the image in order to avoid some noisy results.

To better exploit geographical granularity between images, we use the \thesaurus" developed by the commercial search engine Xilopix (see [ 2 ] for details). The \travel" domain of this thesaurus is organized into a tree of concepts: continents, countries, regions, departments and locations. For each concept, the thesaurus provides its name and its GPS coordinates. For images with GPS, the system calculates the great-circle distance between the GPS coordinates of the image and the GPS coordinates of each concept in the thesaurus, and nally selects the closest concept and its parent nodes (method called tree). For images without GPS, the system matches the terms of the image and the terms of each thesaurus node using TF-IDF weighting (method called tree-t df ) or probabilistic models (method called tree-proba) and nally selects the closest concept and its parent nodes. To estimate the similarity between two concepts in the thesaurus, we use the Wu-Palmer's similarity [ 5 ] that quanti es the similarity between two concepts of a same tree. 3.

CLUSTERING BY AHC

The Agglomerative Hierarchical Clustering (AHC) is a clustering method that provides a hierarchy of clusters of images. Applying the AHC to the query results provides a dendrogram. In order to obtain groups of similar images, we choose to cut the dendrogram to obtain a xed number of unordered clusters (method called FixedN where N is the number of clusters to obtain) (see [ 2 ] for more details).

The way most diversity methods work implies what we call \rank priority" (rank ): we rst choose the cluster containing the image of rank 1 in Step 1, then we choose a di erent cluster containing the next possible lowest rank. Other ways to prioritize the clusters may be interesting, we propose to consider the number of images contained in each cluster. We sort the clusters in decreasing order from the cluster with the largest numbers of images to the cluster with the less images (dec priority). After sorting the clusters, we sort the images in each cluster according to their rank in Step 1. 4.

EXPERIMENTS AND RESULTS

On devset, we tested our model for all descriptors and for most of the parameters. For textual models, on keywords subset, we choose to use the title, tags and descriptions (ttd) elds, while on keywordsGPS, we choose to use only the title and tags (tt) elds. Among our large number of tests, Table 3 shows an example of comparison of AHC results on devset keywordsGPS for tree, GPS and visual (CSD) descriptors using the same parameters and the same Step 1 reranking approach (i.e. t df(tt)). Best diversity results are obtained with visual descriptors compared to tree and GPS.

According to the results on devset, we choose the methods and the parameters for each subset. Table 1 summarizes the parameters and the scores obtained on devset and testset according of the expert ground truth, while Table 2 compares the results on the crowd-sourcing grounds truths. 5.

CONCLUSION AND DISCUSSION

Results on expert and crowd-sourcing grounds truths suggest that an interesting and robust strategy to improve diversity - in the sense of this challenge - is to increase the relevance using the text, and then to exploit visual clustering to diversify the results. Preliminary tests on devset showed that the exploitation of these descriptors outperforms, in terms of diversity, the use of location descriptors (GPS or tree). This is an unexpected results taking into account that queries were formulated around the notion of location.

References

[1] B. Ionescu , M. Menendez , H. Muller, and A. Popescu . Retrieving diverse social images at MediaEval 2013: Objectives, dataset and evaluation . In MediaEval 2013 Workshop, Barcelona, Spain, October 18 -19 2013 .

[2] C. Kuoman , S. Tollari , and M. Detyniecki . Using tree of concepts and hierarchical reordering for diversity in image retrieval . In CBMI , pages 251 { 256 , 2013 .

[3] T. M. Mitchell . Machine Learning. McGraw-Hill , 1997 .

[4] A. Popescu and G. Grefenstette . Social media driven image retrieval . In ACM ICMR , 2011 .

[5] Z. Wu and M. Palmer . Verbs semantics and lexical selection . In Ass. for Computational Linguistics , 1994 .