|
Title
|
|
|
|
Qualitative polyline similarity testing with applications to query-by-sketch, indexing and classification
| |
|
Author
|
|
|
|
| |
|
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) |
| |
|
Language
|
|
|
|
English
| |
|
Source (book)
|
|
|
|
Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, 10-11 November, 2006, Arlington, Virginia, USA
| |
|
Publication
|
|
|
|
New York
:
ACM
,
2006
| |
|
ISBN
|
|
|
|
978-1-59593-529-8
| |
|
DOI
|
|
|
|
10.1145/1183471.1183475
| |
|
Volume/pages
|
|
|
|
p. 11-18
| |
|
Full text (Publisher's DOI)
|
|
|
|
| |
|