Skip to main content
SpringerLink
Log in

Click-boosting multi-modality graph-based reranking for image search

  • Special Issue Paper
  • Published:
Multimedia Systems Aims and scope Submit manuscript

Abstract

Image reranking is an effective way for improving the retrieval performance of keyword-based image search engines. A fundamental issue underlying the success of existing image reranking approaches is the ability in identifying potentially useful recurrent patterns from the initial search results. Ideally, these patterns can be leveraged to upgrade the ranks of visually similar images, which are also likely to be relevant. The challenge, nevertheless, originates from the fact that keyword-based queries are used to be ambiguous, resulting in difficulty in predicting the search intention. Mining useful patterns without understanding query is risky, and may lead to incorrect judgment in reranking. This paper explores the use of click-through data, which can be viewed as the footprints of user searching behavior, as an effective means of understanding query, for providing the basis on identifying the recurrent patterns that are potentially helpful for reranking. A new reranking algorithm, named click-boosting multi-modality graph-based reranking, is proposed. The algorithm leverages clicked images to locate similar images that are not clicked, and reranks them in a multi-modality graph-based learning scheme. Encouraging results are reported for image reranking on a real-world image dataset collected from a commercial search engine with click-through data.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. The queries include: (1) 15 party dresses, (2) baby shower, (3) backsplash ideas, (4) back tattoos, (5) billy beer, (6) boston fire hazmat, (7) bouncy castles, (8) cute offices, (9) deadmau5, (10) fall decorating ideas, (11) fb profile pics for girls, (12) fresh beat band logo, (13) funny spongebob pictures, (14) gingerbread house glue, (15) gingerbread man, (16) girl teen bedrooms, (17) graffiti drawings, (18) gray wolf, (19) guitar factory, (20) gymnastics pictures, (21) hawaii, (22) jesus married mary magdalene, (23) lady gaga, (24) ledge stone hearth, (25) lyndon b. johnson ranch, (26) madonna gangnam style, (27) man with the golden gun, (28) marianas trench, (29) mermaids, (30) michael jackson house, (31) monster high pictures, (32) murano glass, (33) nudity children, (34) ohio state backgrounds, (35) proletariat, (36) skull, (37) vintage christmas prints, (38) vote for me posters, (39) water fountains, (40) winter coloring pages.

References

  1. Baeza-Yates, R., Tiberi, A.: Extracting semantic relations from query logs. In: Proceedings of ACM SIGKDD pp. 76–85 (2007)

  2. Carterette, B., Jones, R.: Evaluating search engines by modeling the relationship between relevance and clicks. Adv. Neural Inf. Process. Syst. 217–224(2007)

  3. Chapelle, O., Zhang, Y.: A dynamic bayesian network click model for web search ranking. In: Proceedings of ACM WWW pp. 1–10 (2009)

  4. Dupret, G., Liao, C.: A model to estimate intrinsic document relevance from the clickthrough logs of a web search engine. In: Proceedings of ACM WSDM pp. 181–190 (2010)

  5. Dupret, G., Piwowarski, B.: A user browsing model to predict search engine click data from past observations. In: Proceedings of ACM SIGIR pp. 331–338 (2008)

  6. Gu, S., Yan, J., Ji, L., Yan, S., Huang, J., Liu, N., Chen, Y., Chen, Z.: Cross domain random walk for query intent pattern mining from search engine log. In: Proceedings of IEEE ICDM pp. 221–230 (2011)

  7. Hsu, W.H., Kennedy, L.S., Chang, S.F.: Video search reranking via information bottleneck principle. In: Proceedings of ACM Multimedia pp. 35–44 (2006)

  8. Hsu, W.H., Kennedy, L.S., Chang, S.F.: Video search reranking through random walk over document-level context graph. In: Proceedings of ACM Multimedia pp. 971–980 (2007)

  9. Iyengar, G., Nock, H.J.: Discriminative model fusion for semantic concept detection and annotation in video. In: Proceedings of ACM Multimedia pp. 255–258 (2003)

  10. Jain, V., Varma, M.: Learning to rerank: Query-dependent image reranking using click data. In: Proceedings of ACM WWW pp. 277–286 (2011)

  11. Järvelin, K., Kekäläinen, J.: IR evaluation methods for retrieving highly relevant documents. In: Proceedings of ACM SIGIR pp. 41–48 (2000)

  12. Jhuo, I.H., Lee, D.: Boosting-based multiple kernel learning for image re-ranking. In: Proceedings of ACM Multimedia pp. 1159–1162 (2010)

  13. Joachims, T., Granka, L., Pan, B., Hembrooke, H., Radlinski, F., Gay, G.: Evaluating the accuracy of implicit feedback from clicks and query reformulations in web search. ACM Trans. Inf. Syst. 25(2), Art no. 7 (2007)

  14. Kennedy, L.S., Natsev, A.P., Chang, S.: Automatic discovery of query-class-dependent models for multimodal search. In: Proceedings of ACM Multimedia pp. 882–891 (2005)

  15. Li, H., Wang, X., Tang, J., Zhao, C.: Combining global and local matching of multiple features for precise item image retrieval. Multimed. Syst. 19, 37–49 (2013)

    Article  Google Scholar 

  16. Li, Z., Liu, J., Zhu, X., Liu, T., Lu, H.: Image annotation using multi-correlation probabilistic matrix factorization. In: Proceedings of ACM Multimedia pp. 1187–1190 (2010)

  17. Li, Z., Yang, Y., Liu, J., Zhou, X., Lu, H.: Unsupervised feature selection using nonnegative spectral analysis. In: Proceedings of AAAI pp. 1026–1032 (2012)

  18. Liu, Y., Mei, T., Hua, X.S.: CrowdReranking: Exploring multiple search engines for visual search reranking. In: Proceedings of ACM SIGIR pp. 500–507 (2009)

  19. Liu, Y., Mei, T., Hua, X.S., Tang, J., Wu, X., Li, S.: Learning to video search rerank via pseudo preference feedback. In: Proceedings of IEEE ICME pp. 297–300 (2008)

  20. Mei, T., Rui, Y., Li, S., Tian, Q.: Multimedia search reranking: A literature survey. ACM Computing Surveys (2013)

  21. Pan, Y., Yao, T., Yang, K., Li, H., Ngo, C.W., Wang, J., Mei, T.: Image search by graph-based label propagation with image representation from dnn. In: Proceedings of ACM Multimedia pp. 397–400 (2013)

  22. Snoek, C., van de Sande, K., de Rooij, O., et al.: The mediamill trecvid 2008 semantic video search engine. NIST TRECVID Workshop (2008)

  23. Snoek, C.G.M., Worring, M., Smeulders, A.W.M.: Early versus late fusion in semantic video analysis. In: Proceedings of ACM Multimedia pp. 399–402 (2005)

  24. Song, Y., Zhang, Y., Cao, J., Xia, T., Liu, W., Li, J.: Web video geolocation by geotagged social resources. IEEE Trans. Multimed. 14(2), 456–470 (2012)

    Article  Google Scholar 

  25. Tan, H.K., Ngo, C.W.: Fusing heterogeneous modalities for video and image re-ranking. In: Proceedings of ACM ICMR (2011)

  26. Tang, J., Yan, S., Hong, R., Qi, G.J., Chua, T.S.: Inferring semantic concepts from community-contributed images and noisy tags. In: Proceedings of ACM Multimedia pp. 223–232 (2009)

  27. Wang, M., Hua, X.S., Yuan, X., Song, Y., Dai, L.R.: Optimizing multi-graph learning: Towards a unified video annotation scheme. In: Proceedings of ACM Multimedia pp. 862–871 (2007)

  28. Wang, M., Li, G., Lu, Z., Gao, Y., Chua, T.S.: When amazon meets google: Product visualization by exploring multiple information sources. ACM Trans. Internet Technol. 12(4), Art no. 12 (2013)

  29. Wang, M., Li, H., Tao, D., Lu, K., Wu, X.: Multimodal graph-based reranking for web image search. IEEE Trans. Image Process. 21(11), 4649–4661 (2012)

    Article  MathSciNet  Google Scholar 

  30. Yan, R., Hauptmann, A., Jin, R.: Multimedia search with pseudo-relevance feedback. In: Proceedings of ACM CIVR pp. 238–247 (2003)

  31. Yan, R., Hauptmann, A.G.: The combination limit in multimedia retrieval. In: Proceedings of ACM Multimedia pp. 339–342 (2003)

  32. Yan, R., Yang, J., Hauptmann, A.G.: Learning query-class dependent weights in automatic video retrieval. In: Proceedings of ACM Multimedia pp. 548–555 (2004)

  33. Yang, X., Zhang, Y., Yao, T., Zha, Z.J., Ngo, C.W.: Click-boosting random walk for image search reranking. In: Proceedings of ACM ICIMCS pp. 1–6 (2013)

  34. Yao, T., Mei, T., Ngo, C.W.: Co-reranking by mutual reinforcement for image search. In: Proceedings of ACM CIVR pp. 34–41 (2010)

  35. Yao, T., Mei, T., Ngo, C.W., Li, S.: Annotation for free: Video tagging by mining user search behavior. In: Proceedings of ACM Multimedia pp. 977–986 (2013)

  36. Yao, T., Ngo, C.W., Mei, T.: Circular reranking for visual search. IEEE Trans. Image Process. 22(4), 1644–1655 (2013)

    Article  MathSciNet  Google Scholar 

  37. Zha, Z.J., Yang, L., Mei, T., Wang, M., Wang, Z.: Visual query suggestion. In: Proceedings of ACM Multimedia pp. 15–24 (2009)

  38. Zhang, L., Zhang, Y., Tang, J., Gu, X., Li, J., Tian, Q.: Topology preserving hashing for similarity search. In: Proceedings of ACM Multimedia pp. 123–132 (2013)

  39. Zhou, D., Bousquet, O., Lal, T.N., Weston, J., Schölkopf, B.: Learning with local and global consistency. Adv. Neural Inf. Process. (2004)

  40. Zhou, X.S., Huang, T.S.: Relevance feedback in image retrieval: A comprehensive review. Multimed. Syst. 8(6), 536–544 (2003)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Key Lab of Intelligent Information Processing of Chinese Academy of Sciences (CAS), Institute of Computing Technology, CAS, Beijing, 100190, People’s Republic of China

    Xiaopeng Yang & Yongdong Zhang

  2. City University of Hong Kong, Kowloon, Hong Kong

    Ting Yao & Chong-Wah Ngo

  3. Microsoft Research, Beijing, 100080, People’s Republic of China

    Tao Mei

Authors
  1. Xiaopeng Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yongdong Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ting Yao
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Chong-Wah Ngo
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Tao Mei
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yongdong Zhang.

Additional information

National Natural Science Foundation of China (61172153, 61272290), National Key Technology Research and Development Program of China (2012BAH39B02), National High Technology Research and Development Program of China (2014AA015202).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yang, X., Zhang, Y., Yao, T. et al. Click-boosting multi-modality graph-based reranking for image search. Multimedia Systems 21, 217–227 (2015). https://doi.org/10.1007/s00530-014-0379-8

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00530-014-0379-8

Keywords

Search

Navigation