Math @ Duke

Publications [#330395] of Christopher Tralie
Papers Published
 Tralie, CJ, SelfSimilarity Based Time Warping
(November, 2017)
(last updated on 2019/01/06)
Abstract: In this work, we explore the problem of aligning two timeordered point
clouds which are spatially transformed and reparameterized versions of each
other. This has a diverse array of applications such as cross modal time series
synchronization (e.g. MOCAP to video) and alignment of discretized curves in
images. Most other works that address this problem attempt to jointly uncover a
spatial alignment and correspondences between the two point clouds, or to
derive local invariants to spatial transformations such as curvature before
computing correspondences. By contrast, we sidestep spatial alignment
completely by using selfsimilarity matrices (SSMs) as a proxy to the
timeordered point clouds, since selfsimilarity matrices are blind to
isometries and respect global geometry. Our algorithm, dubbed "Isometry Blind
Dynamic Time Warping" (IBDTW), is simple and general, and we show that its
associated dissimilarity measure lower bounds the L1 GromovHausdorff distance
between the two point sets when restricted to warping paths. We also present a
local, partial alignment extension of IBDTW based on the Smith Waterman
algorithm. This eliminates the need for tedious manual cropping of time series,
which is ordinarily necessary for global alignment algorithms to function
properly.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

