An Interactive Map Search System Using Wavelet and Shape Contexts
Jungpil Shin* and Hsien-Chou Liao**
*Graduate School of Computer Science and Engineering, The University of Aizu, Aizu-Wakamatsu City, Fukushima 965-8580, Japan
**Department of Computer Science and Information Engineering, Chaoyang University of Technology, 168 Jifong E. Rd., Wufong District, Taichung 41349, Taiwan, R.O.C.
In this paper a new interactive map search system is presented using shape context and bipartite graph matching. Shape context is used for measuring shape similarity and the recovering of point correspondences. After the above information is generated from the shape context bipartite graph matching is used to obtain the optimal correspondence between two shapes. Hierarchical description is also used to increase the recognition rate. Shape context is a method to treat shapes as a set of points and generate the histogram of the distribution of points. Wavelet analysis is used in hierarchical description. In order to shorten the calculation time, piecewise linear approximation is implemented as the feature extraction method. The systemlists the sixmost similar shapes to hand-written input shapes from the reference shapes, i.e., Japan’s 47 prefectures. Comparison results of linear matching, Dynamic Programming (DP) matching and shape context with bipartite graph matching indicate that the 1st place recognition rates are 82%, 84.52% and 92.45%, respectively. The evaluation result of hierarchical description shows that hierarchical approximation can improve the recognition rate from 92.45 to 94.97% using the deepest-4 depth. These results show that the proposed method is effective on fulfilling the interactive map search system.
-  E. G. M. Petrakis, A. Diplaros, and E. Milios, “Matching and Retrieval of Distorted and Occluded Shapes Using Dynamic Programming,” IEEE Trans. Pattern Analysis and Machine Intelligence, Vol.24, No.11, pp. 1501-1516, 2002.
-  D. Geiger, T. L. Liu, and R. V. Kohn, “Representation and Self-Similarity of Shapes,” IEEE Trans. Pattern Analysis and Machine Intelligence, Vol.25, No.1, pp. 86-99, 2003.
-  Y. Nakamura and T. Yoshida, “Reconstructable Hierarchical Description of Two-Dimensional Shapes,” IEICE Trans. Information & Systems, Vol.J78-D-II, No.9, pp. 1288-1297, 1995.
-  K. Kanetani, “Easily Understandable Applied Mathematics from Least-square Method to Wavelet,” Kyouritsu-publisher, 2003 (in Japanese).
-  H. Aoyama and M. Kawagoe, “A Piecewise Linear Approximation Method Preserving Visual Feature Points of Original Figures,” CVGIP: Graphical Models and Image Processing, Vol.53, Issue 5, pp. 435-446, Sept. 1991.
-  H. C. Chen and A. K. C. Wong, “Generalized Texture Representation and Metric,” Computer Vision, Graphics, and Image Processing, Vol.23, Issue 2, pp. 187-206, Aug. 1983.
-  S. Belongie, J. Malik, and J. Puzicha, “Shape Matching and Object Recognition Using Shape Contexts,” IEEE Trans. Pattern Analysis and Machine Intelligence, Vol.24, No.24, pp. 509-522, 2002.
-  S. Belongie and J. Malik, “Matching with Shape Contexts,” IEEE Workshop Content-Based Access of Image and Video Libraries, pp. 20-26, 2000.
-  M. Werman, S. Peleg, R. Melter, and T. Y. Kong, “Bipartite Graph Matching for Points on a Line or a Circle,” J. of Algorithms, Vol.7, pp. 277-284, 1986.
-  H. F. Chen and A. R. S. Ponter, “Shakedown and Limit Analyses for 3-D Structures Using the Linear Matching Method,” Int. J. of Pressure Vessels and Piping, Vol.78, Issue 6, pp. 443-451, June 2001.