Curve matching, time warping, and light fields: New algorithms for computing similarity between curves

Alon Efrat, Quanfu Fan, Suresh Venkatasubramanian

Research output: Contribution to journalArticlepeer-review

120 Scopus citations


The problem of curve matching appears in many application domains, like time series analysis, shape matching, speech recognition, and signature verification, among others. Curve matching has been studied extensively by computational geometers, and many measures of similarity have been examined, among them being the Fréchet distance (sometimes referred in folklore as the "dog-man" distance). A measure that is very closely related to the Fréchet distance but has never been studied in a geometric context is the Dynamic Time Warping measure (DTW), first used in the context of speech recognition. This measure is ubiquitous across different domains, a surprising fact because notions of similarity usually vary significantly depending on the application. However, this measure suffers from some drawbacks, most importantly the fact that it is defined between sequences of points rather than curves. Thus, the way in which a curve is sampled to yield such a sequence can dramatically affect the quality of the result. Some attempts have been made to generalize the DTW to continuous domains, but the resulting algorithms have exponential complexity. In this paper we propose similarity measures that attempt to capture the "spirit" of dynamic time warping while being defined over continuous domains, and present efficient algorithms for computing them. Our formulation leads to a very interesting connection with finding short paths in a combinatorial manifold defined on the input chains, and in a deeper sense relates to the way light travels in a medium of variable refractivity.

Original languageEnglish (US)
Pages (from-to)203-216
Number of pages14
JournalJournal of Mathematical Imaging and Vision
Issue number3
StatePublished - Apr 2007


  • Curve compression
  • Curve matching
  • Light field
  • Signature verification

ASJC Scopus subject areas

  • Statistics and Probability
  • Modeling and Simulation
  • Condensed Matter Physics
  • Computer Vision and Pattern Recognition
  • Geometry and Topology
  • Applied Mathematics


Dive into the research topics of 'Curve matching, time warping, and light fields: New algorithms for computing similarity between curves'. Together they form a unique fingerprint.

Cite this