Handle local optimum traps in CBIR systems

ABSTRACT

Existing CBIR systems, designed around query refinement based on relevance feedback, suffer from local optimum traps. That is, when the user is examining a relevant cluster surrounded by less relevant images, essentially the same set of images will be returned for the user to provide relevance feedback. Since the user would select the same query images again, the relevance feedback process gets trapped in a local optimum. This local-optimum trap problem may severely impair the overall retrieval performance of today's CBIR systems. In this paper, we therefore propose a simulated annealing-based approach to address this important issue. When a stuck-at-a-local-optimum occurs, we employ a neighborhood search technique (i.e., simulated annealing) to escape from the local optimum. We also propose an index structure to speed up such neighborhood search. Our experimental study confirms that our approach can efficiently address the local-optimum trap problem, and therefore can improve the effectiveness of existing CBIR systems.

REFERENCES

• 1: V. Athitsos, J. Alon, S. Sclaroff, and G. Kollios. Boostmap: A method for efficient approximate similarity rankings. In Proceedings of the IEEE CVPR Conference, pages 268--275, 2004.
• 2: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 3: S. Belongie, J. Malik, and J. Puzicha. Matching shapes. In Proceedings of the IEEE ICCV Conference, pages 454--461, 2001.
• 4: Christian Böhm , Stefan Berchtold , Daniel A. Keim, Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases, ACM Computing Surveys (CSUR), v.33 n.3, p.322-373, September 2001 [doi>10.1145/502807.502809]
• 5: Kaushik Chakrabarti , Michael Ortega-Binderberger , Sharad Mehrotra , Kriengkrai Porkaew, Evaluating Refined Queries in Top-k Retrieval Systems, IEEE Transactions on Knowledge and Data Engineering, v.16 n.2, p.256-270, February 2004 [doi>10.1109/TKDE.2004.1269602]
• 6: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 7: Christos Faloutsos , King-Ip Lin, FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.163-174, May 22-25, 1995, San Jose, California, United States
• 8: T. Gevers and A. W. M. Smeulders. Content-based Image Retrieval: An Overview. In G. Medioni and S. B. Kang, editors, Emerging Topics in Computer Vision. Prentice Hall, 2004.
• 9: Jiawei Han, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 10: T. Hertz, A. Bar-Hillel, and D. Weinshall. Learning distance functions for image retrieval. In Proceedings of the IEEE CVPR Conference, pages 570--577, 2004.
• 11: Gísli R. Hjaltason , Hanan Samet, Properties of Embedding Methods for Similarity Searching in Metric Spaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.5, p.530-549, May 2003 [doi>10.1109/TPAMI.2003.1195989]
• 12: Kien A. Hua , Ning Yu , Danzhou Liu, Query Decomposition: A Multiple Neighborhood Approach to Relevance Feedback Processing in Content-based Image Retrieval, Proceedings of the 22nd International Conference on Data Engineering, p.84, April 03-07, 2006 [doi>10.1109/ICDE.2006.123]
• 13: Yoshiharu Ishikawa , Ravishankar Subramanya , Christos Faloutsos, MindReader: Querying Databases Through Multiple Examples, Proceedings of the 24rd International Conference on Very Large Data Bases, p.218-227, August 24-27, 1998
• 14: Deok-Hwan Kim , Chin-Wan Chung, QCluster: relevance feedback using adaptive clustering for content-based image retrieval, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872829]
• 15: S. Kirkpatrick, C. D. Gelatt, and J. M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671--680, 1983.
• 16: D. Liu, K. A. Hua, K. Vu, and N. Yu. Fast Query Point Movement Techniques for Large CBIR Systems. Under review.
• 17: Y. Rui, T. Huang, M. Ortega, and S. Mehrotra. Relevance feedback: A power tool for interactive content-based image retrieval. IEEE Transactions on Circuits and Systems for Video Technology, 8(5):644--655, 1998.
• 18: Robert E. Schapire , Yoram Singer, Improved Boosting Algorithms Using Confidence-rated Predictions, Machine Learning, v.37 n.3, p.297-336, Dec. 1999 [doi>10.1023/A:1007614523901 ]
• 19: X. Wang, J. Wang, K. Lin, D. Shasha, B. Shapiro, and K. Zhang. An index structure for data mining and clustering. Knowledge and Information Systems, 2(2):161--184, 2000.

INDEX TERMS

Keywords:
content-based image retrieval, local optimum traps, query point movement techniques, relevance feedback