LB_Keogh supports exact indexing of shapes under rotation invariance with arbitrary representations and distance measures

• DOI: 10.5555/1182635.1164203
• Publication Date: 2006-09-01
• Authors: Eamonn Keogh; Wei Li; Xiaopeng Xi; Sang‐Hee Lee; Michail Vlachos
• Keywords: Dynamic Time Warping; Scale invariance; Distance measures; Hamming distance; Similarity measure; Image warping; Representation

The matching of two-dimensional shapes is an important problem with applications in domains as diverse biometrics, industry, medicine and anthropology. distance measure used must be invariant to many distortions, including scale, offset, noise, partial occlusion, etc. Most these distortions are relatively easy handle, either the representation data or similarity used. However rotation invariance seems uniquely difficult. Current approaches typically try achieve data, at expense discrimination ability, measure, efficiency. In this work we show that can take slow but accurate dramatically speed them up. On real world problems our technique current make four orders magnitude faster, without false dismissals. Moreover, any dozens existing shape representations all most popular measures Euclidean distance, Dynamic Time Warping Longest Common Subsequence.