tutorial

Unsupervised Distance Learning By Reciprocal kNN Distance for Image Retrieval

Authors:

Daniel C. G. Pedronette,

Otávio A. B. Penatti,

Rodrigo T. Calumby,

Ricardo da S. TorresAuthors Info & Claims

ICMR '14: Proceedings of International Conference on Multimedia Retrieval

Pages 345 - 352

https://doi.org/10.1145/2578726.2578770

Published: 01 April 2014 Publication History

Abstract

This paper presents a novel unsupervised learning approach that takes into account the intrinsic dataset structure, which is represented in terms of the reciprocal neighborhood references found in different ranked lists. The proposed Reciprocal kNN Distance defines a more effective distance between two images, and is used to improve the effectiveness of image retrieval systems. Several experiments were conducted for different image retrieval tasks involving shape, color, and texture descriptors. The proposed approach is also evaluated on multimodal retrieval tasks, considering visual and textual descriptors. Experimental results demonstrate the effectiveness of proposed approach. The Reciprocal kNN Distance yields better results in terms of effectiveness than various state-of-the-art algorithms.

References

[1]

N. Arica and F. T. Y. Vural. BAS: a perceptual shape descriptor based on the beam angle statistics. Pattern Recognition Letters, 24(9-10):1627--1639, 2003.

Digital Library

[2]

R. A. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval. Addison-Wesley Longman, 1999.

Digital Library

[3]

X. Bai, B. Wang, X. Wang, W. Liu, and Z. Tu. Co-transduction for shape retrieval. In ECCV, volume 3, pages 328--341, 2010.

Digital Library

[4]

S. Belongie, J. Malik, and J. Puzicha. Shape matching and object recognition using shape contexts. PAMI, 24(4):509--522, 2002.

Digital Library

[5]

P. Brodatz. Textures: A Photographic Album for Artists and Designers. Dover, 1966.

[6]

Y. Chen, X. Li, A. Dick, and R. Hill. Ranking consistency for image matching and object retrieval. Pattern Recognition, 47(3):1349--1360, 2014.

Digital Library

[7]

G. V. Cormack, C. L. A. Clarke, and S. Buettcher. Reciprocal rank fusion outperforms condorcet and individual rank learning methods. In ACM SIGIR, pages 758--759, 2009.

Digital Library

[8]

R. da S. Torres and A. X. Falcão. Content-Based Image Retrieval: Theory and Applications. Revista de Informática Teórica e Aplicada, 13(2):161--185, 2006.

[9]

R. da S. Torres and A. X. Falcão. Contour Salience Descriptors for Effective Image Retrieval and Analysis. Image and Vision Computing, 25(1):3--13, 2007.

[10]

R. Datta, D. Joshi, J. Li, and J. Z. Wang. Image retrieval: Ideas, influences, and trends of the new age. ACM Computing Surveys, 40(2):5:1--5:60, 2008.

Digital Library

[11]

T. Deselaers, D. Keysers, and H. Ney. Features for image retrieval: an experimental comparison. Information Retrieval, 11(2):77--107, 2008.

Digital Library

[12]

Z. Ghahramani. Unsupervised Learning. In Advanced Lectures on Machine Learning, pages 72--112. 2004.

[13]

R. Gopalan, P. Turaga, and R. Chellappa. Articulation-invariant representation of non-planar shapes. In ECCV'2010, volume 3, pages 286--299, 2010.

Digital Library

[14]

C.-B. Huang and Q. Liu. An orientation independent texture descriptor for image retrieval. In ICCCAS 2007, pages 772--776, 2007.

[15]

J. Huang, S. R. Kumar, M. Mitra, W.-J. Zhu, and R. Zabih. Image indexing using color correlograms. In CVPR, pages 762--768, 1997.

Digital Library

[16]

H. Jegou, C. Schmid, H. Harzallah, and J. Verbeek. Accurate image search using the contextual dissimilarity measure. PAMI, 32(1):2--11, 2010.

Digital Library

[17]

J. Jiang, B. Wang, and Z. Tu. Unsupervised metric learning by self-smoothing operator. In ICCV, pages 794--801, 2011.

Digital Library

[18]

P. Kontschieder, M. Donoser, and H. Bischof. Beyond pairwise shape similarity analysis. In ACCV, pages 655--666, 2009.

Digital Library

[19]

V. Kovalev and S. Volmer. Color co-occurence descriptors for querying-by-example. In International Conference on Multimedia Modeling, page 32, 1998.

Digital Library

[20]

S. Lafon and A. B. Lee. Diffusion maps and coarse-graining: A unified framework for dimensionality reduction, graph partitioning, and data set parameterization. PAMI, 28(9):1393--1403, 2006.

Digital Library

[21]

L. J. Latecki, R. Lakmper, and U. Eckhardt. Shape descriptors for non-rigid shapes with a single closed contour. In CVPR, pages 424--429, 2000.

[22]

B. Leibe and B. Schiele. Analyzing appearance and contour based methods for object categorization. In CVPR, volume 2, pages II--409--15 vol.2, 2003.

[23]

J. Lewis, S. Ossowski, J. Hicks, M. Errami, and H. R. Garner. Text similarity: an alternative way to search medline. Bioinformatics, 22(18):2298--2304, 2006.

Digital Library

[24]

H. Ling and D. W. Jacobs. Shape classification using the inner-distance. PAMI, 29(2):286--299, 2007.

Digital Library

[25]

H. Ling, X. Yang, and L. J. Latecki. Balancing deformability and discriminability for shape matching. In ECCV, volume 3, pages 411--424, 2010.

Digital Library

[26]

Y. Liu, D. Zhang, G. Lu, and W.-Y. Ma. A survey of content-based image retrieval with high-level semantics. Pattern Recognition, 40(1):262--282, 2007.

Digital Library

[27]

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, 2001.

Digital Library

[28]

T. Ojala, M. Pietikäinen, and T. Mäenpää. Multiresolution gray-scale and rotation invariant texture classification with local binary patterns. PAMI, 24(7):971--987, 2002.

Digital Library

[29]

D. C. G. Pedronette and R. da S. Torres. Shape retrieval using contour features and distance optmization. In VISAPP, volume 1, pages 197--202, 2010.

[30]

D. C. G. Pedronette and R. da S. Torres. Exploiting clustering approaches for image re-ranking. Journal of Visual Languages and Computing, 22(6):453--466, 2011.

Digital Library

[31]

D. C. G. Pedronette and R. da S. Torres. Exploiting pairwise recommendation and clustering strategies for image re-ranking. Information Sciences, 207:19--34, 2012.

Digital Library

[32]

D. C. G. Pedronette and R. da S. Torres. Image re-ranking and rank aggregation based on similarity of ranked lists. Pattern Recognition, 46(8):2350--2360, 2013.

Digital Library

[33]

D. Qin, S. Gammeter, L. Bossard, T. Quack, and L. van Gool. Hello neighbor: Accurate object retrieval with k-reciprocal nearest neighbors. In CVPR, pages 777 --784, june 2011.

Digital Library

[34]

T. Qin, T.-Y. Liu, X.-D. Zhang, D.-S. Wang, and H. Li. Global ranking using continuous conditional random fields. In NIPS, pages 1281--1288, 2008.

[35]

S. E. Robertson, S. Walker, S. Jones, M. Hancock-Beaulieu, and M. Gatford. Okapi at trec-3. In TREC, pages 109--126, 1994.

[36]

R. O. Stehling, M. A. Nascimento, and A. X. Falcão. A compact and efficient image retrieval approach based on border/interior pixel classification. In CIKM, pages 102--109, 2002.

Digital Library

[37]

M. J. Swain and D. H. Ballard. Color indexing. International Journal on Computer Vision, 7(1): 11--32, 1991.

Digital Library

[38]

B. Tao and B. W. Dickinson. Texture recognition and image retrieval using gradient indexing. JVCIR, 11(3):327--342, 2000.

Digital Library

[39]

J. B. Tenenbaum, V. d. Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319--2323, 2000.

[40]

Z. Tu and A. L. Yuille. Shape matching and recognition - using generative models and informative features. In ECCV, pages 195--209, 2004.

[41]

J. van de Weijer and C. Schmid. Coloring local feature extraction. In ECCV, pages 334--348, 2006.

Digital Library

[42]

C. J. van Rijsbergen. Information Retrieval. Butterworth-Heinemann, London, 1979.

Digital Library

[43]

B. Wang, J. Jiang, W. Wang, Z.-H. Zhou, and Z. Tu. Unsupervised metric fusion by cross diffusion. In CVPR, pages 3013 --3020, 2012.

[44]

A. Williams and P. Yoon. Content-based image retrieval using joint correlograms. MTAP, 34(2):239--248, August 2007.

Digital Library

[45]

L. Wolf, T. Hassner, and Y. Taigman. Similarity scores based on background samples. In ACCV'09, pages 88--97, 2009.

Digital Library

[46]

P. Wu, B. S. Manjunanth, S. D. Newsam, and H. D. Shin. A texture descriptor for image retrieval and browsing. In CBAIVL, pages 3--7, 1999.

Digital Library

[47]

X. Yang, X. Bai, L. J. Latecki, and Z. Tu. Improving shape retrieval by learning graph transduction. In ECCV, volume 4, pages 788--801, 2008.

[48]

X. Yang, S. Koknar-Tezel, and L. J. Latecki. Locally constrained diffusion process on locally densified distance spaces with applications to shape retrieval. In CVPR, pages 357--364, 2009.

[49]

X. Yang, L. Prasad, and L. Latecki. Affinity learning with diffusion on tensor product graph. PAMI, PP(99):1, 2012.

Digital Library

[50]

H. P. Young. An axiomatization of borda's rule. Journal of Economic Theory, 9(1):43--52, 1974.

[51]

S. Zhang, M. Yang, T. Cour, K. Yu, and D. N. Metaxas. Query specific fusion for image retrieval. In ECCV, pages 660--673, 2012.

Digital Library

Cited By

Pereira-Ferrero VLewis TValem LFerrero LPedronette DLatecki L(2024)Unsupervised affinity learning based on manifold analysis for image retrieval: A surveyComputer Science Review10.1016/j.cosrev.2024.10065753(100657)Online publication date: Aug-2024
https://doi.org/10.1016/j.cosrev.2024.100657
Guimarães Pedronette DPascotti Valem LLatecki L(2021)Efficient Rank-Based Diffusion Process with Assured ConvergenceJournal of Imaging10.3390/jimaging70300497:3(49)Online publication date: 8-Mar-2021
https://doi.org/10.3390/jimaging7030049
Pisani FPascotti Valem LGuimarães Pedronette Dda S. Torres RBorin EBreternitz M(2020)A unified model for accelerating unsupervised iterative re‐ranking algorithmsConcurrency and Computation: Practice and Experience10.1002/cpe.570232:14Online publication date: 3-Mar-2020
https://doi.org/10.1002/cpe.5702
Show More Cited By

Index Terms

Unsupervised Distance Learning By Reciprocal kNN Distance for Image Retrieval
1. Information systems
  1. Information retrieval
  2. Information storage systems

Recommendations

Unsupervised manifold learning through reciprocal kNN graph and Connected Components for image retrieval tasks

Presentation of an unsupervised manifold learning method based on Reciprocal kNN Graphs and Connected Components.Discussion about the use of the method for distance learning in order to improve the effectiveness of image retrieval tasks.Discussion about ...
Kernel-based distance metric learning for content-based image retrieval

For a specific set of features chosen for representing images, the performance of a content-based image retrieval (CBIR) system depends critically on the similarity or dissimilarity measure used. Instead of manually choosing a distance function in ...
Effective, Efficient, and Scalable Unsupervised Distance Learning in Image Retrieval Tasks
ICMR '15: Proceedings of the 5th ACM on International Conference on Multimedia Retrieval

Various unsupervised learning methods have been proposed with significant improvements in the effectiveness of image search systems. However, despite the relevant effectiveness gains, these approaches commonly require high computation efforts, not ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICMR '14: Proceedings of International Conference on Multimedia Retrieval

April 2014

564 pages

ISBN:9781450327824

DOI:10.1145/2578726

Conference Chairs:
Mohan Kankanhalli
National University of Singapore
,
Stefan Rueger
The Open University, UK
,
R. Manmatha
A9.com, USA
,
General Chairs:
Joemon Jose
University of Glasgow, UK
,
Keith van Rijsbergen
University of Glasgow, UK

Copyright © 2014 Owner/Author.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

In-Cooperation

SIGMM: ACM Special Interest Group on Multimedia

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 2014

Check for updates

Author Tags

Qualifiers

Tutorial
Research
Refereed limited

Conference

ICMR '14

ICMR '14: International Conference on Multimedia Retrieval

April 1 - 4, 2014

Glasgow, United Kingdom

Acceptance Rates

ICMR '14 Paper Acceptance Rate 21 of 111 submissions, 19%;

Overall Acceptance Rate 254 of 830 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
244
Total Downloads

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

Reflects downloads up to 09 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pereira-Ferrero VLewis TValem LFerrero LPedronette DLatecki L(2024)Unsupervised affinity learning based on manifold analysis for image retrieval: A surveyComputer Science Review10.1016/j.cosrev.2024.10065753(100657)Online publication date: Aug-2024
https://doi.org/10.1016/j.cosrev.2024.100657
Guimarães Pedronette DPascotti Valem LLatecki L(2021)Efficient Rank-Based Diffusion Process with Assured ConvergenceJournal of Imaging10.3390/jimaging70300497:3(49)Online publication date: 8-Mar-2021
https://doi.org/10.3390/jimaging7030049
Pisani FPascotti Valem LGuimarães Pedronette Dda S. Torres RBorin EBreternitz M(2020)A unified model for accelerating unsupervised iterative re‐ranking algorithmsConcurrency and Computation: Practice and Experience10.1002/cpe.570232:14Online publication date: 3-Mar-2020
https://doi.org/10.1002/cpe.5702
Presotto JValem LPedronette D(2019)Unsupervised Effectiveness Estimation Through Intersection of Ranking ReferencesComputer Analysis of Images and Patterns10.1007/978-3-030-29891-3_21(231-244)Online publication date: 3-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-29891-3_21
Li DChuah M(2018)Accurate Image Retrieval With Unsupervised 2-Stage k-NN Re-RankingComputer Vision10.4018/978-1-5225-5204-8.ch072(1726-1745)Online publication date: 2018
https://doi.org/10.4018/978-1-5225-5204-8.ch072
Liu RZhao YWei S(2018)Enhance Neighbor Reversibility in Subspace Learning for Image RetrievalIEEE Journal of Selected Topics in Signal Processing10.1109/JSTSP.2018.287958112:6(1338-1350)Online publication date: Dec-2018
https://doi.org/10.1109/JSTSP.2018.2879581
Memon MLi JMemon IArain Q(2017)GEO matching regionsMultimedia Tools and Applications10.1007/s11042-016-3834-z76:14(15377-15411)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1007/s11042-016-3834-z
Li DChuah M(2016)Accurate Image Retrieval with Unsupervised 2-Stage k-NN Re-RankingInternational Journal of Multimedia Data Engineering & Management10.4018/IJMDEM.20160101037:1(41-59)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.4018/IJMDEM.2016010103
Almeida JPedronette DAlberton BMorellato LTorres R(2016)Unsupervised Distance Learning for Plant Species IdentificationIEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing10.1109/JSTARS.2016.26083589:12(5325-5338)Online publication date: Dec-2016
https://doi.org/10.1109/JSTARS.2016.2608358
Pedronette DTorres R(2016)A correlation graph approach for unsupervised manifold learning in image retrieval tasksNeurocomputing10.1016/j.neucom.2016.03.081208:C(66-79)Online publication date: 5-Oct-2016
https://dl.acm.org/doi/10.1016/j.neucom.2016.03.081
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents