Interactive high-dimensional index for large Chinese calligraphic character databases

ABSTRACT

The large numbers of Chinese calligraphic scripts in existence are valuable part of the Chinese cultural heritage. However, due to the shape complexity of these characters, it is hard to employ existing techniques to effectively retrieve and efficiently index them. In this article, using a novel shape-similarity- based retrieval method in which shapes of calligraphic characters are represented by their contour points extracted from the character images, we propose an interactive partial-distance-map(PDM)- based high-dimensional indexing scheme which is designed specifically to speed up the retrieval performance of the large Chinese calligraphic character databases effectively. Specifically, we use the approximate minimal bounding sphere of a query character and utilize users' relevance feedback to refine the query gradually. Comprehensive experiments are conducted to testify the efficiency and effectiveness of this method. In addition, a new k-NN search called Pseudo k-NN (Pk-NN) search is presented to better facilitate the PDM-based character retrieval.

REFERENCES

• 1: 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
• 2: S. Belongie , J. Malik , J. Puzicha, Shape Matching and Object Recognition Using Shape Contexts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.4, p.509-522, April 2002 [doi>10.1109/34.993558]
• 3: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 4: Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996
• 5: Independent Quantization: An Index Compression Technique for High-Dimensional Data Spaces, Proceedings of the 16th International Conference on Data Engineering, p.577, February 28-March 03, 2000
• 6: Stefan Berchtold , Christian Böhm , Daniel A. Keim , Florian Krebs , Hans-Peter Kriegel, On Optimizing Nearest Neighbor Queries in High-Dimensional Data Spaces, Proceedings of the 8th International Conference on Database Theory, p.435-449, January 04-06, 2001
• 7: 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]
• 8: Chen, J. Y., Bouman, C. A., and Dalton, J. 2000. Hierarchical browsing and search of large image databases. IEEE Transaction on Image Processing. Vol. 9, No. 3, pp. 442--445.
• 9: Haili Chui , Anand Rangarajan, A new point matching algorithm for non-rigid registration, Computer Vision and Image Understanding, v.89 n.2-3, p.114-141, February 2003 [doi>10.1016/S1077-3142(03)00009-2]
• 10: Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997
• 11: Scott Cohen , Leonidas Guibas, The Earth Mover's Distance under Transformation Sets, Proceedings of the International Conference on Computer Vision-Volume 2, p.1076, September 20-25, 1999
• 12: Manuel J. Fonseca , Joaquim A. Jorge, Indexing High-Dimensional Data for Content-Based Retrieval in Large Databases, Proceedings of the Eighth International Conference on Database Systems for Advanced Applications, p.267, March 26-28, 2003
• 13: Thomas Funkhouser , Patrick Min , Michael Kazhdan , Joyce Chen , Alex Halderman , David Dobkin , David Jacobs, A search engine for 3D models, ACM Transactions on Graphics (TOG), v.22 n.1, p.83-105, January 2003 [doi>10.1145/588272.588279]
• 14: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 15: 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
• 16: H. V. Jagadish , Beng Chin Ooi , Kian-Lee Tan , Cui Yu , Rui Zhang, iDistance: An adaptive B⁺-tree based indexing method for nearest neighbor search, ACM Transactions on Database Systems (TODS), v.30 n.2, p.364-397, June 2005 [doi>10.1145/1071610.1071612]
• 17: Kherfi, M. L., Ziou, D., and Bernardi, A. 2002. Learning from negative example in relevance feedback for content-based image retrieval. In: Proceedings of the 16th International Conference on Pattern Recognition. Quebec, Canada, pp. 933--936.
• 18: Feng Liu , Yueting Zhuang , Fei Wu , Yunhe Pan, 3D motion retrieval with motion index tree, Computer Vision and Image Understanding, v.92 n.2-3, p.265-284, November/December 2003 [doi>10.1016/j.cviu.2003.06.001]
• 19: C. Nastar , M. Mitschke , C. Meilhac, Efficient Query Refinement for Image Retrieval, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.547, June 23-25, 1998
• 20: Réjean Plamondon , Sargur N. Srihari, On-Line and Off-Line Handwriting Recognition: A Comprehensive Survey, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.1, p.63-84, January 2000 [doi>10.1109/34.824821]
• 21: Picard, R. W., Minka, T. P., and Szummer, M. 1996. Modeling user subjectivity in image libraries. In: Proceedings of the International Conference on Image Processing. Lausanne, Switzerland, pp. 777--780.
• 22: Rath, T.M., Kane, S., Lehman, A., Partridge, E. and Manmatha, R. 2002. Indexing for a Digital Library of George Washington's Manuscripts: A Study of Word Matching Techniques, CIIR Technical Report, University of Massachusetts Amherst.
• 23: Rui, Y, Huang, T. S., Oortega, M., Mehrotra, S. 1998. Relevance feedback: A power tool in interactive content-based image retrieval. IEEE Transaction on Circuits and Systems for Video Technology, Vol. 8, No. 5. pp. 644--655.
• 24: Yasushi Sakurai , Masatoshi Yoshikawa , Shunsuke Uemura , Haruhiko Kojima, The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation, Proceedings of the 26th International Conference on Very Large Data Bases, p.516-526, September 10-14, 2000
• 25: Shi, B. L., Zhang, L., Wang, Y. and Chen, Z. F., 2001, Content Based Chinese Script Retrieval Through Visual Similarity Criteria, Chinese Journal of Software Vol. 12. No. 9, pp. 1336--1342.
• 26: The Cadal Project, http://www.cadal.zju.edu.cn, 2005.
• 27: Tieu, K. and Viola, P. 2000. Boosting image retrieval. In: Proceedings of the International Conference on Computer Vision and Pattern Recognition. Hilton Head, SC, pp. 228--235.
• 28: Vasconcelos, N. and Lippman, A. 2000. Learning from user feedback in image retrieval systems. In: Proceedings of the Advances in Neural Information Processing Systems.
• 29: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
• 30: Wu, Y. S. and Ding, X. Q., 1992. Chinese character recognition: the principles and the implementations. Beijing: Advanced Education Press.
• 31: Itay Bar Yosef , Klara Kedem , Its'hak Dinstein , Malachi Beit-Arie , Edna Engel, Classification of Hebrew Calligraphic Handwriting Styles: Preliminary Results, Proceedings of the First International Workshop on Document Image Analysis for Libraries (DIAL'04), p.299, January 23-24, 2004
• 32: Zhang, R. and Zhang, Z. 2004. Stretching Bayesian learning in the relevance feedback of image retrieval. In: Proceedings of the European Conference on Computer Vision. Prague, Czech, pp. 355--367.
• 33: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada
• 34: Zhang X. Z., 1992. Chinese Character Recognition Techniques. Beijing: Tsinghua University Press.
• 35: Zhou, X. S. and Huang, T. S. 2003. Relevance feedback in image retrieval: a comprehensive review. Multimedia Systems. Vol. 8, No. 6, pp. 536--544.
• 36: Zhou, X., and Huang, T. 2001. Small sample learning during multimedia retrieval using Bias Map. In: Proceedings of the International Conference on Computer Vision and Pattern Recognition. Kauai, HI, pp. 11--17.
• 37: Zhi-Hua Zhou , Ke-Jia Chen , Hong-Bin Dai, Enhancing relevance feedback in image retrieval using unlabeled data, ACM Transactions on Information Systems (TOIS), v.24 n.2, p.219-244, April 2006 [doi>10.1145/1148020.1148023]
• 38: Zhuang, Y. T, Zzhang, X. F, Wu, J. Q., and Lu, X. Q. 2004. Retrieval of Chinese Calligraphic Character Image. In: Proceedings of the 5th Pacific-Rim Conference on Multimedia. Beijing, pp. 17--24

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Chinese calligraphic character, Hyper-centre relocation, Pseudo k-NN