article

Re-ranking algorithm using post-retrieval clustering for content-based image retrieval

Authors:

Gunhan Park,

Yunju Baek,

Heung-Kyu LeeAuthors Info & Claims

Information Processing and Management: an International Journal, Volume 41, Issue 2

Pages 177 - 194

https://doi.org/10.1016/j.ipm.2003.08.002

Published: 01 March 2005 Publication History

Abstract

In this paper, we propose a re-ranking algorithm using post-retrieval clustering for content-based image retrieval (CBIR). In conventional CBIR systems, it is often observed that images visually dissimilar to a query image are ranked high in retrieval results. To remedy this problem, we utilize the similarity relationship of the retrieved results via post-retrieval clustering. In the first step of our method, images are retrieved using visual features such as color histogram. Next, the retrieved images are analyzed using hierarchical agglomerative clustering methods (HACM) and the rank of the results is adjusted according to the distance of a cluster from a query. In addition, we analyze the effects of clustering methods, querycluster similarity functions, and weighting factors in the proposed method. We conducted a number of experiments using several clustering methods and cluster parameters. Experimental results show that the proposed method achieves an improvement of retrieval effectiveness of over 10% on average in the average normalized modified retrieval rank (ANMRR) measure.

References

[1]

Anick, P. G., & Vaithyanathan, S. (1997). Exploiting clustering and phrases for context-based information retrieval. In Proceedings of 20th ACM SIGIR international conference on research and development in information retrieval (pp. 314-323).]]

Crossref

Google Scholar

[2]

Ballard, D. H., & Brown, C. M. (1982). Computer vision (pp. 181-189). New Jersey: Prentice Hall.]]

Crossref

Google Scholar

[3]

Celebi, E., & Alpkocak, A. (2000). Clustering of texture features for content-based image retrieval. In Proceedings of international conference on advances in information systems (ADVIS2000) (pp. 216-225).]]

Crossref

Google Scholar

[4]

Cutting, D. R., Karger, D. R., Pederson, J. O., & Tukey, J. W. (1992). Scatter/gather: a cluster-based approach to browsing large document collections. In Proceedings of 15th ACM SIGIR international conference on research and development in information retrieval (pp. 318-329).]]

Crossref

Google Scholar

[5]

Faloutsos, C., Barber, R., Flickner, M., Hafner, J., Niblack, W., Petkovic, D., & Equitz, W. (1994). Efficient and effective querying by image content. Journal of Intelligent Information Systems, 3(3), 231-262.]]

Digital Library

Google Scholar

[6]

Frakes, W. B., & Baeza-Yates, R. (1992). Information retrieval: Data structures & algorithms (pp. 419-442), New Jersey: Prentice Hall.]]

Crossref

Google Scholar

[7]

Haralick, R. M., & Shapiro, L. G. (1992). Computer and robot vision (pp. 453-470). Addison-Wesley publishing company.]]

Crossref

Google Scholar

[8]

Hearst, M. A., & Pederson, J. O. (1996). Reexamining the cluster hypothesis: scatter/gather on retrieval results. In Proceedings of 19th ACM SIGIR international conference on research and development in information retrieval (pp. 76-84).]]

Crossref

Google Scholar

[9]

Jain, A. K., & Vailaya, A. (1996). Image retrieval using color and shape. Pattern Recognition, 29(8), 1233-1244.]]

Crossref

Google Scholar

[10]

Krishnamachari, S., & Abdel-Mottaleb, M. (1999). Hierarchical clustering algorithm for fast image retrieval. In Proceedings of the IS&T/SPIE conference on storage and retrieval for image and video databases VII (pp. 427-435).]]

Google Scholar

[11]

Lee, K. S., Park, Y. C., & Choi, K. S. (2001). Re-ranking model based on document clusters. Information Processing and Management, 37(1), 1-14.]]

Digital Library

Google Scholar

[12]

Ma, W. Y., & Zhang, H. (1998). Benchmarking of image features for content-based retrieval. In Proceedings of the 32nd asilomar conference on signals, systems, and computers (pp. 253-257).]]

Google Scholar

[13]

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

Digital Library

Google Scholar

[14]

Mukherjea, S., Hirata, K., & Hara, Y. (1998). Using clustering and visualization for refining the results of a WWW image search engine. In Proceedings of the 1998 workshop on new paradigms in information visualization and manipulation (pp. 29-35).]]

Crossref

Google Scholar

[15]

Parker, J. R. (1997). Algorithms for image processing and computer vision (pp. 23-53). John Wiley & Sons, Inc.]]

Google Scholar

[16]

Rui, Y., Huang, T. S., & Chang, S. F. (1999). Image retrieval: current techniques, promising directions, and open issues. Journal of Visual Communication and Image Presentation, 10, 39-62.]]

Digital Library

Google Scholar

[17]

Sheikholeslami, G., Chang, W., & Zhang, A. (2002). SemQuery: semantic clustering and querying on heterogeneous features for visual data. IEEE Transactions on Knowledge and Data Engineering, 14(5), 988-1002.]]

Digital Library

Google Scholar

[18]

Smith, J. R. (1997). Integrated spatial and feature image systems: retrieval, analysis and compression. Ph.D. Thesis, Department of Electrical Engineering, Columbia University.]]

Google Scholar

[19]

Swain, M. J., & Ballad, D. H. (1991). Color indexing. International Journal of Computer Vision, 7(1), 11-32.]]

Digital Library

Google Scholar

[20]

Tombros, A., Villa, R., & Van Rijsbergen, C. J. (2002). The effectiveness of query-specific hierarchic clustering in information retrieval. Information Processing and Management, 38(4), 559-582.]]

Digital Library

Google Scholar

[21]

Vailaya, A., Jain, A. K., & Zhang, H.-J. (1998). On image classification: city images vs. landscapes. Pattern Recognition, 31(12), 1921-1936.]]

Crossref

Google Scholar

[22]

Vinod, V. V., & Manjunath, B. S. (1999). Report on AHG of color and texture. ISO/IEC/JTC1/SC29/WG11, Doc. M5560, Maui.]]

Google Scholar

[23]

Voorhees, E. M. (1985). The cluster hypothesis revisited. In Proceedings of 8th ACM SIGIR international conference on research and development in information retrieval (pp. 188-196).]]

Crossref

Google Scholar

[24]

Voorhees, E. M. (1986). Implementation agglomerative hierarchic clustering algorithms for use in document retrieval. Technical Report TR 86-765 of the Department of Computing Science, Cornell University.]]

Crossref

Google Scholar

[25]

Willett, P. (1988). Recent trends in hierarchic document clustering: a critical review. Information Processing and Management, 24(5), 577-587.]]

Digital Library

Google Scholar

[26]

Yoo, H. W., Jung, S. H., Jang, D. S., & Na, Y. K. (2002). Extraction of major object features using VQ clustering for content-based image retrieval. Pattern Recognition, 35(5), 1115-1126.]]

Crossref

Google Scholar

[27]

Yu, D., & Zhang, A. (2000). ClusterTree: integration of cluster representation and nearest neighbor search for image databases. In Proceedings of the IEEE international conference on multimedia and expo (ICME) (pp. 1713-1716).]]

Google Scholar

Cited By

View all

Franco PNguyen GMullot ROgier J(2018)Alternative patterns of the multidimensional Hilbert curveMultimedia Tools and Applications10.1007/s11042-017-4744-477:7(8419-8440)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s11042-017-4744-4
Valem LPedronette D(2017)Selection and Combination of Unsupervised Learning Methods for Image RetrievalProceedings of the 15th International Workshop on Content-Based Multimedia Indexing10.1145/3095713.3095741(1-6)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3095713.3095741
Pedronette DTorres R(2016)Combining re-ranking and rank aggregation methods for image retrievalMultimedia Tools and Applications10.1007/s11042-015-3044-075:15(9121-9144)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1007/s11042-015-3044-0
Show More Cited By

Index Terms

Re-ranking algorithm using post-retrieval clustering for content-based image retrieval
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Unsupervised learning
        Cluster analysis
2. Information systems
  1. Information retrieval
    1. Retrieval models and ranking
    2. Retrieval tasks and goals
      1. Clustering and classification
  2. Information systems applications
    1. Data mining
      1. Clustering
    2. Multimedia information systems
      1. Multimedia databases

Recommendations

Clustering for photo retrieval at Image CLEF 2008
CLEF'08: Proceedings of the 9th Cross-language evaluation forum conference on Evaluating systems for multilingual and multimodal information access

This paper presents the first participation of the University of Ottawa group in the Photo Retrieval task at Image CLEF 2008. Our system uses Lucene for text indexing and LIRE for image indexing. We experiment with several clustering methods in order to ...
Content-based image retrieval by clustering
MIR '03: Proceedings of the 5th ACM SIGMM international workshop on Multimedia information retrieval

In a typical content-based image retrieval (CBIR) system, query results are a set of images sorted by feature similarities with respect to the query. However, images with high feature similarities to the query may be very different from the query in ...
A Ranking Algorithm Using Dynamic Clustering for Content-Based Image Retrieval
CIVR '02: Proceedings of the International Conference on Image and Video Retrieval

In this paper, we propose a ranking algorithm using dynamic clustering for content-based image retrieval(CBIR). In conventional CBIR systems, it is often observed that visually dissimilar images to the query image are located at high ranking. To remedy ...

Reviews

Reviewer: Joaquin Ordieres

In this work, the authors propose an algorithm for reordering the results of a classical query content-based image retrieval, obtained, for example, by means of visual features like color histograms. The idea is to produce a list of images related to the original one, and ordered, as much as possible, by their similarity to the original image. The problem seems not to be a crucial one, as far as it addresses the re-ranking of the query output. In order to obtain this, the authors propose the use of a hierarchical agglomerative method, classically used for clustering, as a measure for similarity between samples. The key point is to use the clustering algorithm as a post-retrieval tool instead of as a retrieval criterion. The authors use a measure for retrieval effectiveness proposed by the MPEG-7 research group. The algorithm depends on clustering parameter values, taking into account the cluster distance and the ranking distance. Obviously, the proposed algorithm is not the most unique one available, but the interesting idea is in trying to use a cluster algorithm instead of single laws or monotonic strategies. The authors show some examples of ranking and post-ranking approaches, as well as examples of the effectiveness and percentage of change. They claim an improvement of about ten percent on average when using their algorithm. It is clear that the algorithm does not produce an optimal series, even in the post-query set of images, but it improves the quality of the answer from the user's point of view. In any case, a much more extensive set of trials to assess the claimed improvement could be interesting. No information about the algorithm's cost is provided. This could be a major drawback, but since the algorithm is concerned only with the output of the query, instead of with the total set of images, its importance is reduced. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Information Processing and Management: an International Journal Volume 41, Issue 2

March 2005

248 pages

ISSN:0306-4573

Issue’s Table of Contents

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 01 March 2005

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Franco PNguyen GMullot ROgier J(2018)Alternative patterns of the multidimensional Hilbert curveMultimedia Tools and Applications10.1007/s11042-017-4744-477:7(8419-8440)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s11042-017-4744-4
Valem LPedronette D(2017)Selection and Combination of Unsupervised Learning Methods for Image RetrievalProceedings of the 15th International Workshop on Content-Based Multimedia Indexing10.1145/3095713.3095741(1-6)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3095713.3095741
Pedronette DTorres R(2016)Combining re-ranking and rank aggregation methods for image retrievalMultimedia Tools and Applications10.1007/s11042-015-3044-075:15(9121-9144)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1007/s11042-015-3044-0
de Ves EAyala GBenavent XDomingo JDura E(2015)Modeling user preferences in content-based image retrievalNeurocomputing10.1016/j.neucom.2015.05.041168:C(829-845)Online publication date: 30-Nov-2015
https://dl.acm.org/doi/10.1016/j.neucom.2015.05.041
Shrivastava NTyagi V(2015)An efficient technique for retrieval of color images in large databasesComputers and Electrical Engineering10.1016/j.compeleceng.2014.11.00946:C(314-327)Online publication date: 1-Aug-2015
https://dl.acm.org/doi/10.1016/j.compeleceng.2014.11.009
Mei TRui YLi STian Q(2014)Multimedia search rerankingACM Computing Surveys10.1145/253679846:3(1-38)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1145/2536798
Mai HKim M(2014)Utilizing similarity relationships among existing data for high accuracy processing of content-based image retrievalMultimedia Tools and Applications10.1007/s11042-013-1360-972:1(331-360)Online publication date: 1-Sep-2014
https://dl.acm.org/doi/10.1007/s11042-013-1360-9
Pedronette DDa Silva Torres RCalumby R(2014)Using contextual spaces for image re-ranking and rank aggregationMultimedia Tools and Applications10.1007/s11042-012-1115-z69:3(689-716)Online publication date: 1-Apr-2014
https://dl.acm.org/doi/10.1007/s11042-012-1115-z
Pedronette DDa S. Torres R(2013)Image re-ranking and rank aggregation based on similarity of ranked listsPattern Recognition10.1016/j.patcog.2013.01.00446:8(2350-2360)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1016/j.patcog.2013.01.004
Li JMa QAsano YYoshikawa M(2012)Re-ranking by multi-modal relevance feedback for content-based social image retrievalProceedings of the 14th Asia-Pacific international conference on Web Technologies and Applications10.1007/978-3-642-29253-8_34(399-410)Online publication date: 11-Apr-2012
https://dl.acm.org/doi/10.1007/978-3-642-29253-8_34
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Clustering for photo retrieval at Image CLEF 2008

Content-based image retrieval by clustering

A Ranking Algorithm Using Dynamic Clustering for Content-Based Image Retrieval

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations