An Adaptive Clustering Approach for the Diversification of Image Retrieval Results

Abstract

In this paper, we explore the application of an adaptive clustering approach for the diversi cation of image retrieval results in the context of the MediaEval 2016 Retrieving Diverse Social Images Task. The proposed approach exploits available textual descriptions, the visual content of the images, and a set of common clustering techniques to select the best combination for each image query individually and in an unsupervised manner.

1. INTRODUCTION

The immense amount on publicly available media content commonly challenges end users in making use of the broad variety of accessible data. As a result, a lot of recent research focuses on the optimization of retrieval results in terms of improved relevance estimation and increased diversi cation [ 3, 6, 13, 21 ]. The MediaEval Retrieving Diverse Social Images task fosters the development and comparability of algorithms in this context [ 12 ]. The goal of the task in 2016 is to re ne a set of images retrieved from Flickr as result of a general (and often multi-topic) query.

Increasing the relevance commonly leads to decreased diversity of the underling image set and vice versa. The magnitude of this reciprocal e ect is di cult to estimate for different data settings. Therefore, in order to exploit the real potential of a clustering-based approach for data diversi cation, we consider all images as relevant for the given query. To address a general image retrieval scenario with arbitrary queries, we only consider commonly available textual information (title, description, tags) and the visual content of the images. The proposed approach does not make any assumptions about the initial image query or data characteristics. Moreover, the approach autonomously selects the best combination of image descriptions and clustering approach for each query individually and, thus, it is fully adaptive for di erent queries and data settings. Preliminary experiments demonstrate the generalization ability of the proposed approach and both its potentials and limitations.

APPROACH

The fundamental assumption behind the proposed approach is that di erent queries require for di erent features This work has been partly funded by the Vienna Science and Technology Fund (WWTF) through project ICT12-010. (a) sailing boats on sea (b) trees re ected in water to e ciently describe the retrieval results in terms of diversi cation of the nal image set. Figure 1 shows examples for desired image groupings for two queries: sailing boats on sea and trees re ected in water. While the results of the rst query indicate potential relevance of the overall composition and edge-based descriptors, the second query suggests the use of color-based descriptors. On the contrary, color information is less meaningful for the rst query since the retrieved images exhibit common color settings. Similarly, edges do not provide enough discriminative power to support the building of the desired image groupings for the second query. Therefore, in our study we consider a set of commonly employed visual- and text-based descriptors to represent the image data. Next to the two convolutional neural network (CNN)-based descriptors provided by the organizers [ 12 ], we additionally employ the rst 36 coe cients of the discrete cosine transform (DCT) [ 1 ], intensity histogram (IH) [ 10 ], KANSEI shape descriptor [ 15 ], and six MPEG-7 visual descriptors [ 4, 18 ]: color layout (CL), color structure (CS), edge histogram (EH), homogeneous texture (HT), regionbased shape (RS), and scalable color (SC). As text-based features we consider the well-established term frequencyinverse document frequency (TF-IDF) [ 14 ]. We compute the TF-IDF vector for each image using the available textual description (title, tags, and descriptions) in combination and individually. The textual descriptions are rst preprocessed to increase their expressiveness, i.e., we remove potential occurrences of the corresponding user name, web links, and stopwords and we additionally stem all remaining terms.

The unsupervised detection of existing groupings in a dataset is commonly performed by means of a clustering algorithm. However, the choice of a clustering approach is not a trivial decision. Di erent clustering approaches commonly address di erent data characteristics. Furthermore, potential clustering parameters usually require for an additional parameter tuning process. In this context, clustering internal validation indices are commonly applied in order to assess the quality of a clustering solution in terms of compactness and/or separability of the detected clusters [ 16 ]. We exploit the performance of several, broadly employed validation indices covering di erent aspects of a clustering solutions: 1) compactness in terms of sum of squares and C-index [ 11 ], 2) separability by means of single linkage distance between two clusters, 3) combination of compactness and separability in terms of Calinski-Harabasz [ 5 ], DaviesBouldin [ 7 ], and Silhouette [ 20 ], and 4) consistency comparison measures by means of Gamma and Tau indices [ 2 ]. We employ the clustering validation measures to select the best combination of image feature and clustering algorithm for each query individually. As clustering methods we investigate two model-based approaches: A nity Propagation (AP) [ 9 ] and expectation maximization (EM) [ 8 ], and two partitional approaches: k-means (KM) [ 17 ] and X-means (XM) [ 19 ]. The clustering methods were selected for their e ciency. Additionally, the only parameter tuning concerns the potential speci cation of the expected number of clusters, k. In this case, we perform clustering for various settings, k = f5; 10; 20; 30; 40; 50g, and consider each clustering solution individually. The nal selection of a clustering solution for a given query is based on the quality assessment of all possible combinations between the considered clustering approaches and the employed image features. The nal selection of images from the clusters follows a Round-Robin approach according to the Flickr-provided relevance scores. We start by selecting the image with the best relevance score from each cluster. These images, sorted in ascending order, constitute the m highest ranked results, where m is the number of detected clusters. The selected images are removed from their clusters and the selection process is repeated until the required number of retrieved results is achieved.

EXPERIMENTAL RESULTS

In our rst experiment we investigate whether or not different datasets require for di erent features. For this purpose we perform clustering on the development dataset using all possible combinations between the considered clustering approaches (including potential clustering con gurations) and the employed visual- and text-based features. The best clustering solution is selected using the ground truth information in terms of highest F1@20-score. Due to space limitations Table 1 shows an overview of the optimal clustering combinations for each topic (query) using the visual features only. The achieved results are presented in Table 2 (see Optimal solution ). The balanced distribution of the clustering solutions across the employed visual features indicate that di erent image queries favor di erent features. Additionally, the achieved performance in terms of F1@20score signi cantly outperforms the baseline de ned by the original Flickr result. The best performing clustering solution considers the DCT feature in combination with the KM clustering approach and the C validation index. This result is notably lower than the achievable performance. Additionally, the combination is selected based on experiments on a single dataset and, thus, over tting the data. Experiments with the performance of the clustering validation indices indicated the C-index as the best performing validation measure stressing the importance of compactness for the nal clustering solution. The results achieved using the proposed adaptive approach in combination with the C-index are presented in Table 2. The results are slightly lower than the best performing xed setting yet not over tting the data.

Table 3 summarizes the results on the test set. Runs 1 3 employ the adaptive approach while run 4 exploits the best performing xed settings on the development set as proof-of-concept for its over tting. The proposed approach adapts well to the new dataset indicated by the di erence in the selected features and clustering approaches. The xed selection of image feature and clustering approach in run 4 performs lowest as expected. Overall, the results are lower in comparison to the development dataset. However, this can only be evaluated in relation to the baseline which is not available for the test set yet. 4.

CONCLUSION

In this paper we presented an initial study of the applicability of an unsupervised and adaptive clustering-based approach for the diversi cation of image retrieval results. The results indicate that di erent image queries favor di erent image representations and di erent clustering methods. The optimal solution for a dataset achieves an outstanding performance. However, the considered validation indices could not re ect the optimal solution. This might be due to the fact that di erent clustering solutions require for di erent validations. Our future work will exploit the potential of combining clustering validation indices in order to approach the best achievable performance.

References

[1] N. Ahmed , T. Natarajan , and K. R. Rao . Discrete cosine transform . IEEE Transactions on Computers, C- 23 ( 1 ): 90 { 93 , 1974 .

[2] F. B. Baker and L. J. Hubert . Measuring the power of hierarchical cluster analysis . Journal of the American Statistical Association , 70 ( 349 ): 31 { 38 , 1975 .

[3] G. Boato , D.- T. Dang-Nguyen , O. Muratov , N. Alajlan , and F. G. B. De Natale . Exploiting visual saliency for increasing diversity of image retrieval results . Multimedia Tools and Applications , 75 ( 10 ): 5581 { 5602 , 2016 .

[4] M. Bober . Mpeg-7 visual shape descriptors . IEEE Transactions on Circuits and Systems for Video Technology , 11 ( 6 ): 716 { 719 , Jun 2001 .

[5] T. Calinski and J. Harabasz . A dendrite method for cluster analysis . Communications in Statistics , 3 ( 1 ):1{ 27 , 1974 .

[6] D. T. Dang-Nguyen , L. Piras , G. Giacinto, G. Boato, and F. G. B. D. Natale . A hybrid approach for retrieving diverse social images of landmarks . In IEEE International Conference on Multimedia and Expo (ICME) , pages 1 { 6, June 2015 .

[7] D. L. Davies and D. W. Bouldin . A cluster separation measure . IEEE Transactions on Pattern Analysis and Machine Intelligence , PAMI- 1 ( 2 ): 224 { 227 , 1979 .

[8] A. P. Dempster , N. M. Laird , and D. B. Rubin . Maximum Likelihood from Incomplete Data via the EM Algorithm . Journal of the Royal Statistical Society. Series B (Methodological) , 39 ( 1 ):1{ 38 , 1977 .

[9] B. J. Frey and D. Dueck . Clustering by passing messages between data points . Science , 315 ( 5814 ): 972 { 976 , 2007 .

[10] R. C. Gonzalez and R. E. Woods. Digital Image Processing. Prentice-Hall, Inc., 3rd edition , 2006 .

[11] L. J. Hubert and J. R. Levin . A general statistical framework for assessing categorical clustering in free recall . Psychological Bulletin , 83 ( 6 ): 1072 { 1080 , 1978 .

[12] B. Ionescu , A. L. Ginsca , M. Zaharieva , B. Boteanu , M. Lupu , and H. Mu ller. Retrieving diverse social images at MediaEval 2016: Challenge, dataset and evaluation . In MediaEval 2016 Multimedia Benchmark Workshop , 2016 .

[13] B. Ionescu , A. Popescu , A.-L. Radu , and H. Mu ller. Result diversi cation in social image retrieval: a benchmarking framework . Multimedia Tools and Applications , 75 ( 2 ): 1301 { 1331 , 2016 .

[14] K. S. Jones . A statistical interpretation of term speci city and its application in retrieval . Journal of Documentation , 28 ( 1 ): 11 { 21 , 1972 .

[15] H. Kobayashi , Y. Okouchi , and S. Ota . Image retrieval system using KANSEI features . In Paci c Rim International Conference on Arti cial Intelligence: Topics in Arti cial Intelligence , pages 626 { 635 , 1998 .

[16] Y. Liu , Z. Li , H. Xiong , X. Gao , and J. Wu . Understanding of internal clustering validation measures . In IEEE International Conference on Data Mining (ICDM) , pages 911 { 916 , 2010 .

[17] S. Lloyd . Least squares quantization in PCM . IEEE Transactions on Information Theory , 28 ( 2 ): 129 { 137 , 1982 .

[18] B. Manjunath , J.-R. Ohm , V. Vasudevan , and A. Yamada . Color and texture descriptors . IEEE Transactions on Circuits and Systems for Video Technology , 11 ( 6 ): 703 { 715 , Jun 2001 .

[19] D. Pelleg and A. W. Moore . X-means: Extending k-means with e cient estimation of the number of clusters . In International Conference on Machine Learning (ICML) , pages 727 { 734 , 2000 .

[20] P. Rousseeuw. Silhouettes : A graphical aid to the interpretation and validation of cluster analysis . Journal of Computational and Applied Mathematics , 20 ( 1 ): 53 { 65 , 1987 .

[21] E. Spyromitros-Xiou s , S. Papadopoulos, A. L. Ginsca , A. Popescu , Y. Kompatsiaris , and I. Vlahavas . Improving diversity in image search via supervised relevance scoring . In ACM International Conference on Multimedia Retrieval , pages 323 { 330 , 2015 .