Timezone: »
Dynamic time warping (DTW) is a fundamental technique in time series analysis for comparing one curve to another using a flexible time-warping function. However, it was designed to compare a single pair of curves. In many applications, such as in metabolomics and image series analysis, alignment is simultaneously needed for multiple pairs. Because the underlying warping functions are often related, independent application of DTW to each pair is a sub-optimal solution. Yet, it is largely unknown how to efficiently conduct a joint alignment with all warping functions simultaneously considered, since any given warping function is constrained by the others and dynamic programming cannot be applied. In this paper, we show that the joint alignment problem can be transformed into a network flow problem and thus can be exactly and efficiently solved by the max flow algorithm, with a guarantee of global optimality. We name the proposed approach graphical time warping (GTW), emphasizing the graphical nature of the solution and that the dependency structure of the warping functions can be represented by a graph. Modifications of DTW, such as windowing and weighting, are readily derivable within GTW. We also discuss optimal tuning of parameters and hyperparameters in GTW. We illustrate the power of GTW using both synthetic data and a real case study of an astrocyte calcium movie.
Author Information
Yizhi Wang (Virginia Tech)
David J Miller (The Pennsylvania State University)
Kira Poskanzer (University of California)
Yue Wang (Virginia Tech)
Lin Tian (The University of California)
Guoqiang Yu (Virginia Tech)
More from the Same Authors
-
2023 Poster: NIS3D: A Completely Annotated Benchmark for Dense 3D Nuclei Image Segmentation »
Wei Zheng · Cheng Peng · Zeyuan Hou · Boyu Lyu · Mengfan Wang · Xuelong Mi · Shuoxuan Qiao · Yinan Wan · Guoqiang Yu -
2022 Poster: BILCO: An Efficient Algorithm for Joint Alignment of Time Series »
Xuelong Mi · Mengfan Wang · Alex Chen · Jing-Xuan Lim · Yizhi Wang · Misha B Ahrens · Guoqiang Yu -
2019 Poster: muSSP: Efficient Min-cost Flow Algorithm for Multi-object Tracking »
Congchao Wang · Yizhi Wang · Yinxue Wang · Chiung-Ting Wu · Guoqiang Yu