Abstract
We introduce a measure for computing the similarity between multiple polylines and a polygon, that can be computed in O(km 2 n 2) time with a straightforward dynamic programming algorithm. We then present a novel fast algorithm that runs in time O(kmn logmn). Here, m denotes the number of vertices in the polygon, and n is the total number of vertices in the k polylines that are matched against the polygon. The effectiveness of the similarity measure has been demonstrated in a part-based retrieval application with known ground-truth.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ansari, N., Delp, E.J.: Partial shape recognition: A landmark-based approach. PAMI 12, 470–483 (1990)
Arkin, E., Chew, L., Huttenlocher, D., Kedem, K., Mitchell, J.: An efficiently computable metric for comparing polygonal shapes. PAMI 13, 209–215 (1991)
Asano, T., de Berg, M., Cheong, O., Everett, H., Haverkort, H.J., Katoh, N., Wolff, A.: Optimal spanners for axis-aligned rectangles. CGTA 30(1), 59–77 (2005)
Cohen, S.D., Guibas, L.J.: Partial matching of planar polylines under similarity transformations. In: Proc. SODA, pp. 777–786 (1997)
Huttenlocher, D., Klanderman, G., Rucklidge, W.: Comparing images using the hausdorff distance. PAMI 15, 850–863 (1993)
Latecki, L.J., Lakämper, R., Wolter, D.: Shape similarity and visual parts. In: Nyström, I., Sanniti di Baja, G., Svensson, S. (eds.) DGCI 2003. LNCS, vol. 2886, pp. 34–51. Springer, Heidelberg (2003)
Liu, H.-C., Srinath, M.D.: Partial shape classification using contour matching in distance transformation. PAMI 12(11), 1072–1079 (1990)
Mokhtarian, F., Abbasi, S., Kittler, J.: Efficient and robust retrieval by shape content through curvature scale space. In: Workshop on Image DataBases and MultiMedia Search, pp. 35–42 (1996)
Navarro, G.: A guided tour to approximate string matching. ACM Computing Surveys 33(1), 31–88 (2001)
Siddiqi, K., Shokoufandeh, A., Dickinson, S.J., Zucker, S.W.: Shock graphs and shape matching. IJCV 55(1), 13–32 (1999)
Tanase, M.: Shape Deomposition and Retrieval. PhD thesis, Utrecht University, Department of Computer Science (February 2005)
Wolfson, H., Rigoutsos, I.: Geometric hashing: an overview. IEEE Computational Science & Engineering, 10–21 (October-December 1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tănase, M., Veltkamp, R.C., Haverkort, H. (2005). Multiple Polyline to Polygon Matching. In: Deng, X., Du, DZ. (eds) Algorithms and Computation. ISAAC 2005. Lecture Notes in Computer Science, vol 3827. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11602613_8
Download citation
DOI: https://doi.org/10.1007/11602613_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30935-2
Online ISBN: 978-3-540-32426-3
eBook Packages: Computer ScienceComputer Science (R0)