Qualitative polyline similarity testing with applications to query-by-sketch, indexing and classification

ABSTRACT

We present an algorithm for polyline (and polygon) similarity testing that is based on the double-cross formalism. To determine the degree of similarity between two polylines, the algorithm first computes their generalized polygons, that consist of almost equally long line segments and that approximate the length of the given polylines within an $varepsilon$-error margin. Next, the algorithm determines the double-cross matrices of the generalized polylines and the difference between these matrices is used as a measure of dissimilarity between the given polylines. We prove termination of our algorithm and show that its sequential time complexity is bounded by $Oleft((fracmax(N_1,N_2)varepsilon)^2right)$, where $N_1$ and $N_2$ are the number of vertices of the given polylines. We apply our method to query-by-sketch, indexing of polyline databases, and classification of terrain features and show experimental results for each of these applications.

REFERENCES

• 1: F.L. Bookstein. Size and shape spaces for landmark data in two dimensions. Statistical Science, 1:181--242, 1986.
• 2: N. Van de Weghe. Representing and Reasoning about Moving Objects: A Qualitative Approach. PhD thesis, Ghent University (Belgium), 2004.
• 3: N. Van de Weghe, A. G. Cohn, and Ph. De Maeyer. A qualitative representation of trajectory pairs. In R. López de Mántaras and L. Saitta, editors, em Proceedings of the 16th Eureopean Conference on Artificial Intelligence (ECAI'04), pages 1103--1104, 2004.
• 4: N. Van de Weghe, A.G. Cohn, G. de Tré, and Ph. De Maeyer. A qualitative trajectory calculus as a basis for representing moving objects in geographical information systems. To appear in Control and Cybernetics, 2006.
• 5: N Van de Weghe, A.G. Cohn, Ph. De Maeyer, and F. Witlox. Representing moving objects in computer based expert systems: the overtake event example. Expert Systems with Applications, 29(4):977--983, 2005.
• 6: N. Van de Weghe and Ph. De Maeyer. Conceptual neighbourhood diagrams for representing moving objects. In J. Akoka et al., editor, ER (Workshops), volume 3770 of em Lecture Notes in Computer Science, pages 228--238, 2005.
• 7: N. Van de Weghe, G. De Tré, B. Kuijpers, and Ph. De Maeyer. The double-cross and the generalization concept as a basis for representing and comparing shapes of polylines. In R. Meersman et al., editor, Proceedings of the 1st International Workshop on Semantic-based Geographical Information Systems (SeBGIS'05), volume 3762 of Lecture Notes in Computer Science, pages 1087--1096. Springer, 2005.
• 8: I. Dryden and K.V. Mardia. Statistical Shape Analysis. Wiley, 1998.
• 9: M. Egenhofer. Query Processing in Spatial-Query-by-Sketch. Journal of Visual Languages and Computing, 8(4):403--424, 1997.
• 10: M. Erwig and M. Schneider. A visual language for the evolution of spatial relationships and its translation into a spatio-temporal calculus. Journal of Visual Languages and Computing, 14(2):181--211, 2003.
• 11: Kenneth D. Forbus, Qualitative physics: past present and future, Readings in qualitative reasoning about physical systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 12: Christian Freksa, Using Orientation Information for Qualitative Spatial Reasoning, Proceedings of the International Conference GIS - From Space to Territory: Theories and Methods of Spatio-Temporal Reasoning on Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, p.162-178, September 21-23, 1992
• 13: John S. Gero, Representation and Reasoning about Shapes: Cognitive and Computational Studies in Visual Reasoning in Design, Proceedings of the International Conference on Spatial Information Theory: Cognitive and Computational Foundations of Geographic Information Science, p.315-330, August 25-29, 1999
• 14: B. Gottfried. Tripartite line tracks qualitative curvature information. In Kuhn et al., editor, Proceedings of the International Conference on Spatial Information Theory (COSIT'03), volume 2825 of em Lecture Notes in Computer Science, pages 101--117. Springer, 2003.
• 15: E. Jungert. Symbolic spatial reasoning on object shapes for qualitative matching. In Proceedings of the International Conference on Spatial Information Theory (COSIT'93), pages 444--462, 1993.
• 16: J.T. Kent and K.V. Mardia. Shape, procrustes tangent projections and bilateral symmetry. Biometrika, 88:469--485, 2001.
• 17: L. Kulik and M. Egenhofer. Linearized terrain: Languages for silhouette representations. In Kuhn et al., editor, Proceedings of the International Conference on Spatial Information Theory (COSIT'03), volume 2825 of em Lecture Notes in Computer Science, pages 118--135. Springer, 2003.
• 18: Longin Jan Latecki , Rolf Lakämper, Shape Similarity Measure Based on Correspondence of Visual Parts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.10, p.1185-1190, October 2000 [doi>10.1109/34.879802]
• 19: M. Leyton, A process-grammar for shape, Artificial Intelligence, v.34 n.2, p.213-247, March 1988 [doi>10.1016/0004-3702(88)90039-2]
• 20: R.C. Meathrel. A General Theory of Boundary-Based Qualitative Representation of 2D Shape. Phd thesis, University of Exeter (UK), 2001.
• 21: Farzin Mokhtarian , Alan K. Mackworth, A Theory of Multiscale, Curvature-Based Shape Representation for Planar Curves, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.8, p.789-805, August 1992 [doi>10.1109/34.149591]
• 22: Chr. Schlieder. Geographic Objects with Indeterminate Boundaries, chapter Qualitative shape representation, pages 123--140. Taylor & Francis, 1996.
• 23: K. Zimmermann and Chr. Freksa. Qualitative spatial reasoning using orientation, distance, and path knowledge. Appl. Intell., 6(1):49--58, 1996.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

General Terms:
Algorithms, Design, Theory

Keywords:
classification, double-cross calculus, indexing, polygons, polylines, qualitative calculi, query-by-sketch, similarity