Abstract
Multimedia information is becoming an ubiquitous part of our lives, which brings an equally ubiquitous need for efficient multimedia retrieval. One of the possible solutions to this problem is to attach text descriptions to multimedia data objects, thus allowing users to utilize traditional text search mechanisms. Search-based annotation techniques attempt to determine the descriptive keywords by analyzing the descriptions of similar, already annotated multimedia objects, which are detected by content-based retrieval techniques. One of the main challenges of this approach is the extraction of semantically connected keywords from the possibly noisy descriptions of similar objects. In this paper, we address this challenge by proposing the ConceptRank, a new keyword ranking algorithm that exploits semantic relationships between candidate keywords and utilizes the random walk mechanism to compute the probability of individual candidates. The effectiveness of the ConceptRank algorithm is evaluated in context of web image annotation. We present a complex image annotation system that includes the ConceptRank component, and compare it to other state-of-the–art annotation techniques.
Similar content being viewed by others
Notes
The value 0.01 associated with the hasInstance edge has no real justification here, its only purpose is to show that some connections are much less reliable than others. The exact edge weighting mechanism will be discussed later.
References
Bartolini I, Ciaccia P (2010) Multi-dimensional keyword-based image annotation and search. In: Proceedings of the 2nd International workshop on keyword search on structured data (KEYS 2010), pp 5:1–5:6
Batko M, Novak D, Zezula P (2007) MESSIf: Metric similarity search implementation framework. In: 1st international DELOS conference, revised selected papers. Springer, LNCS, vol 4877, pp 1–10
Batko M, Botorek J, Budikova P, Zezula P (2013) Content-based annotation and classification framework: a general multi-purpose approach. In: 17th international database engineering & applications symposium (IDEAS 2013), pp 58–67
Batko M, Budikova P, Elias P, Zezula P (2014) CLAN Photo presenter: Multi-modal summarization tool for image collections. In: International conference on multimedia retrieval (ICMR 2014), pp 541–542
Botorek J, Budikova P, Zezula P (2014) Visual concept ontology for image annotations. CoRR arXiv:1412.6082
Brin S, Page L (1998) The anatomy of a large-scale hypertextual web search engine. Comput Netw 30(1-7):107–117
Budikova P, Batko M, Zezula P (2011) Evaluation platform for content-based image retrieval systems. In: International conference on theory and of digital libraries (TPDL 2011), pp 130–142
Budikova P, Botorek J, Batko M, Zezula P (2014) DISA at ImageCLEF 2014: The search-based solution for scalable image annotation. In: CLEF 2014: evaluation labs and workshop, Online Working Notes
Budikova P, Batko M, Botorek J, Zezula P (2015) Search-based image annotation: Extracting semantics from similar images. In: Experimental IR meets multilinguality, multimodality, and interaction: 6th international conference of the CLEF association (CLEF 2015), pp. 327–339
Cai X, Wang H, Huang H, Ding CHQ (2012) Simultaneous image classification and annotation via biased random walk on tri-relational graph. In: 12th European conference on computer vision (ECCV 2012), pp 823–836
Caputo B, Müller H, Martinez-Gomez J, Villegas M, Acar B, Patricia N, Marvasti N, ÜSküdarlı S, Paredes R, Cazorla M, Garcia-Varea I, Morell V (2014) ImageCLEF2014: Overview and analysis of the results. In: CLEF proceedings, lecture notes in computer science. Springer, Berlin Heidelberg
Dai L, Wang X, Zhang L, Yu N (2012) Efficient tag mining via mixture modeling for real-time search-based image annotation. In: Proceedings of the 2012 IEEE international conference on multimedia and expo (ICME 2012), pp 134–139
Deng J, Dong W, Socher R, Li L J, Li K, Li FF (2009) ImageNet: A large-scale hierarchical image database. In: IEEE computer society conference on computer vision and pattern recognition (CVPR 2009), pp 248–255
Deselaers T, Keysers D, Ney H (2008) Features for image retrieval: an experimental comparison. Inf Retr 11:77–107
Donahue J, Jia Y, Vinyals O, Hoffman J, Zhang N, Tzeng E, Darrell T (2014) DeCAF: a deep convolutional activation feature for generic visual recognition. In: Proceedings of the 31th international conference on machine learning (ICML 2014), pp 647–655
Fellbaum C (1998) WordNet: An electronic lexical database. The MIT Press
Fu J, Wang J, Rui Y, Wang X, Mei T, Lu H (2015) Image tag refinement with view-dependent concept representations. IEEE Trans Circ Syst Video Technol 25(8):1409–1422
Gupta M R, Bengio S, Weston J (2014) Training highly multiclass classifiers. J Mach Learn Res 15(1):1461–1492
Gyöngyi Z, Garcia-Molina H, Pedersen J (2004) Combating web spam with TrustRank. In: Proceedings of the 30th international conference on very large data bases - volume 30, VLDB Endowment, VLDB ’04, pp 576–587
He X, Li X, Yang G, Xu J, Jin Q (2014) Adaptive tag selection for image annotation. In: Advances in multimedia information processing (PCM 2014), pp 11–21
Hu J, Lam K M (2013) An efficient two-stage framework for image annotation. Pattern Recogn 46(3):936–947
Ke X, Li S, Chen G (2013) Real web community based automatic image annotation. Comput Electr Eng 39(3):945–956
Krizhevsky A, Sutskever I, Hinton G E (2012) ImageNet classification with deep convolutional neural networks. In: Advances in neural information processing systems (NIPS 2012), pp 1106–1114
Leskovec J, Rajaraman A, Ullman JD (2014) Mining of massive datasets, 2nd edn. Cambridge University Press, Cambridge
Li X, Chen L, Zhang L, Lin F, Ma W (2006) Image annotation by large-scale content-based image retrieval. In: Proceedings of the 14th ACM international conference on multimedia, pp 607–610
Lin Z, Ding G, Hu M, Wang J, Sun J (2012) Automatic image annotation using tag-related random search over visual neighbors. In: 21st ACM international conference on information and knowledge management (CIKM’12), pp 1784–1788
Lin Z, Ding G, Hu M (2015) Image auto-annotation via tag-dependent random search over range-constrained visual neighbours. Multimedia Tools Appl 74(11):4091–4116
Lindstaedt S N, Mȯrzinger R, Sorschag R, Pammer V, Thallinger G (2009) Automatic image annotation using visual content and folksonomies. Multimedia Tools Appl 42(1):97–113
Liong VE, Lu J, Wang G, Moulin P, Zhou J (2015) Deep hashing for compact binary codes learning. In: IEEE conference on computer vision and pattern recognition, CVPR 2015, pp 2475–2483
Liu D, Hua X, Yang L, Wang M, Zhang H (2009) Tag ranking. In: Proceedings of the 18th international conference on world Wide Web (WWW 2009), pp 351–360
Lokoc J, Novák D, Batko M, Skopal T (2012) Visual image search: Feature signatures or/and global descriptors. In: 5th international conference on similarity search and applications (SISAP 2012), pp 177–191
Lux M, Pitman A, Marques O (2010) Can global visual features improve tag recommendation for image annotation? Future Internet 2(3):341–362
Maier O, Kwasnicka H, Stanek M (2012) Image auto-annotation with automatic selection of the annotation length. J Intell Inf Syst 39(3):651–685
Makadia A, Pavlovic V, Kumar S (2008) A new baseline for image annotation. In: 10th European conference on computer vision (ECCV 2008), pp 316–329
Muja M, Lowe D G (2014) Scalable nearest neighbor algorithms for high dimensional data. IEEE Trans Pattern Anal Mach Intell 36(11):2227–2240
Naidan B, Boytsov L, Nyberg E (2015) Permutation search methods are efficient, yet faster search is possible. In: Proceedings of the 41st international conference on very large data bases, pp 1618– 1629
Novak D, Zezula P (2016) PPP-codes for large-scale similarity searching. Transactions on Large-Scale Data- and Knowledge-Centered Systems XXIV 9510:61–87
Novak D, Batko M, Zezula P (2015) Large-scale image retrieval using neural net descriptors. In: Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval, pp 1039–1040
Russakovsky O, Deng J, Su H, Krause J, Satheesh S, Ma S, Huang Z, Karpathy A, Khosla A, Bernstein M, Berg A C, Fei-Fei L (2015) ImageNet large scale visual recognition challenge. Int J Comput Vis 115(3):211–252
Schickel-Zuber V, Faltings B (2007) OSS: A semantic similarity function based on hierarchical ontologies. In: Proceedings of the 20th international joint conference on artificial intelligence, pp 551–556
Sivic J, Zisserman A (2003) Video Google: A text retrieval approach to object matching in videos. In: 9th IEEE international conference on computer vision (ICCV 2003), pp 1470–1477
Smeulders A, Worring M, Santini S, Gupta A, Jain R (2000) Content-based image retrieval at the end of the early years. IEEE Trans Pattern Anal Mach Intell 22 (12):1349–1380
Suchanek F M, Kasneci G, Weikum G (2008) YAGO: A large ontology from wikipedia and wordnet. J Web Semantics 6(3):203–217
Szegedy C, Liu W, Jia Y, Sermanet P, Reed S, Anguelov D, Erhan D, Vanhoucke V, Rabinovich A (2015) Going deeper with convolutions. In: IEEE conference on computer vision and pattern recognition (CVPR 2015), pp 1–9
Szegedy C, Vanhoucke V, Ioffe S, Shlens J, Wojna Z (2015) Rethinking the inception architecture for computer vision. CoRR arXiv:1512.00567
Tong H, Faloutsos C, Pan J (2008) Random walk with restart: fast solutions and applications. Knowl Inf Syst 14(3):327–346
Torralba A, Fergus R, Freeman WT (2008) 80 million tiny images: A large data set for nonparametric object and scene recognition. IEEE Trans Pattern Anal Mach Intell 30(11):1958–1970
Tousch A M, Herbin S, Audibert J Y (2012) Semantic hierarchies for image annotation: a survey. Pattern Recogn 45(1):333–345
Vijayanarasimhan S, Shlens J, Monga R, Yagnik J (2014) Deep networks with large output spaces. CoRR arXiv:1412.7479
Villegas M, Paredes R (2014) Overview of the ImageCLEF 2014 scalable concept image annotation task. In: Working notes for CLEF 2014 conference, pp 308–328
Wang C, Jing F, Zhang L, Zhang H (2006) Scalable search-based image annotation of personal images. In: Proceedings of the 8th ACM SIGMM international workshop on multimedia information retrieval (MIR 2006), pp 269–278
Wang C, Jing F, Zhang L, Zhang H (2008) Scalable search-based image annotation. Multimedia Syst 14(4):205–220
Wang C, Blei DM, Li F (2009) Simultaneous image classification and annotation. In: IEEE computer society conference on computer vision and pattern recognition (CVPR 2009), pp 1903–1910
Wang X J, Zhang L, Ma W Y (2012) Duplicate-search-based image annotation using web-scale data. Proc IEEE 100(9):2705–2721
Wang X, Du J, Wu S, Li X, Xin H, Zhang Y, Li F (2015) High-level semantic image annotation based on hot internet topics. Multimedia Tools Appl 74 (6):2055–2084
Yu J, Cao D, Li S, Lin D (2012) A novel image annotation feedback model based on internet-search. In: Web information systems and mining (WISM 2012), pp 580–588
Zezula P, Amato G, Dohnal V, Batko M (2006) Similarity search: the metric space approach, advances in database systems, vol 32. Springer-Verlag
Zhang D, Islam M M, Lu G (2012) A review on automatic image annotation techniques. Pattern Recogn 45(1):346–362
Zhang L, Chen L, Li M, Zhang H (2003) Automated annotation of human faces in family albums. In: Proceedings of the 11th ACM international conference on multimedia, pp 355–358
Zhang X, Li Z, Chao WH (2013) Improving image tags by exploiting web search results. multimedia tools and applications 62(3):601–631
Acknowledgements
This paper is based on research supported by the Czech Science Foundation project No. P103/12/G084.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Budikova, P., Batko, M. & Zezula, P. ConceptRank for search-based image annotation. Multimed Tools Appl 77, 8847–8882 (2018). https://doi.org/10.1007/s11042-017-4777-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11042-017-4777-8