In this paper we introduce a re nement and diversi cation process for re-ranking image search results based on social metadata and visual characteristics of the photos. The goal of the developed re-ranking algorithm is to construct a new sequence with maximal value of the harmonic mean of precision and diversity. Our contribution is twofold: estimation of precision using the statistical average and mixing of clustering results in order to get better diversity. In the combined clustering the new label set is the Cartesian product of the two original cluster label sets.
Many potential tourists do websearches when they try to
nd more information about a place they are potentially
visiting. These people have only a vague idea about the
location, knowing the name of the place. Our aim is to
help them by providing a set of photos, as summary of the
di erent views of the location. In the o cial challenge of the
MediaEval 2014 Retrieving Diverse Social Images task [
The goodness of the re nement process can be
measured using the precision and diversity metric. In a
previous participation in the task we have solved a very
similar problem via diversi cation of initial results using
clustering [
We took ve approaches to generate the nal re-ranking of the inital search result. This required ve di erent systems that share similar components. The components can be seen in Figure 1, where the 'relevance scoring' part creates a model, based on this model the 'estimation' component estimates the relevance of test data (optionally using the credibility set), 'clustering' part generates clusters, and 're-ranking' component produces nal ranks.
All the systems take the inital ranks as input along with the visual feature descriptors and the textual descriptors corresponding to the images. In each case the relevance of all images are estimated, the images are grouped into clusters and based on this two type of information the nal ranks are determined.
Section 2.1. describes the 'average' relevance estimation and its extended versions using user tagging credibility information. Tagging credibilities are used with di erent weights in the last two approaches. Section 2.2. de nes the methods we used to cluster the data. 2.1
For every kth place in the initial sequence of the development data set we compute the probability of the item at the kth place of being relevant. Before giving the formal de nition let denote the set of all initial sequences in the development set as L, the kth element of the sequence l 2 L as lk and the binary function of the relevance (based on the ground truth data) as rgt(lk). Then pk, the estimated probability of the kth element in an ordering is relevant: pk = jL1j Pl2L rgt(lk). avg avg avg avg + credibility 1 avg + credibility 2 visual textual visual+textual visual+textual visual+textual
When processing an initial sequence (from the test data set) we give the relevance score of pk to the kth element of the sequence. In Table 1 'avg + credibility' means that the relevance estimation is multiplied by the user tagging credibility. 2.2
The provided data sets contain visual feature descriptors
(color moments, histogram of oriented gradients, etc) in csv
les. First, we merged the descriptors into a long feature
vector, one vector for each image. Then the components of
the vectors are normalized to bring all the data to the same
scale. The vectors are clustered with the K-means algorithm
by trying all clustering number parameters from 6 to 18. For
every clustering the silhouette score [
Clusterings based on textual and visual data can di er, but merging the two results can be bene cial. Having two clustering functions c1(x) and c2(x) that are mapping an image ID to a cluster label, one can construct c3(x) = (c1(x); c2(x)) that maps an image ID to a new cluster labeled by the pair of the two original cluster labels. Note that the new label set is the Cartesian product of the two original cluster label sets. 2.3
Our re-ranking algorithm (in order to get maximal F1 value in each subset of the answer list) consists of four phases: 1) Take the elements in each cluster in descending order and select the element that possessing the largest probability of relevance, this will be the 1st in the reordered list. 2) Lth step: take the rst elements in each cluster as candidate and calculate the estimated F1 measure: (1) 3) Select the element that has the largest estimated F1 measure and move to the re-ranked list. 4) Continue with phase 2 until we have cluster elements left.
Table 1 shows the di erent system compositions we used. 'Avg' is for the 'average' relevance estimation detailed in Section 2.1. Figure 2 shows the values of F1 for the di erent runs, while Table 2 shows the average P@20, CR@20 and F1@20 results. The results of the ve approaches mainly di er in P@N performance. The cluster recall (CR) is almost the same, so P@N has more impact on the F1 score.
The credibility information tends to have negative e ect on both P and CR in our tests, compared to the other runs.
However run3 (clustering based on visual+textual data) underperforms run2 in P@20 average, it is more diverse, so the overall F1@20 score is the hightest for run3. 0.7602 0.7809 0.7756 0.7415 0.7431 0.4107 0.4065 0.4127 0.3651 0.3682 4.
The publication was supported by the TAMOP-4.2.2.C-11/1/KONV-2012-0001 project. The project has been supported by the European Union, co- nanced by the European Social Fund. 5.