# Improving the Robustness of DTW to Global Time Warping Conditions in Audio Synchronization
## 1 Introduction  
Dynamic time warping (DTW) is a dynamic programming algorithm that calculates the optimal alignment between two sequences under certain assumptions. Though designed to handle an unknown amount of time warping, in practice DTW's performance often degrades when the two sequences differ substantially in scale [1; 2; 3], resulting in a global time warp factor that deviates from one. Scale differences arise naturally in many domains: query-by-humming systems must handle singing at different tempos [4], gait recognition involves different walking speeds [5], query-by-sketch systems must handle differences in scale [6], and similar issues arise in multimedia [7] and bioinformatics [8]. This paper studies the effect of global time warping conditions on the alignment accuracy of DTW in a systematic manner and experimentally explores several ways to improve the robustness of DTW to varying levels of global time warping. To make our study concrete, we will focus on an audio-audio alignment scenario in which the goal is to accurately estimate the temporal alignment between two different audio recordings of the same piece of music (e.g., two different piano performances of a composition). Previous works on DTW generally fall into one of four groups. The first group focuses on speeding up exact DTW (or subsequence DTW), often in the context of a database search. This has been accomplished in many ways, including lower bounds [9; 10], early abandoning [11; 12], parallelizing across multiple cores [13; 14], or using specialized hardware [15; 16]. Several recent works have utilized GPUs to reduce the runtime of computing exact DTW on long sequences [17; 18]. The second group focuses on reducing the quadratic memory and computation costs through approximations of DTW. These include approximate lowerbounds [19; 20], imposing bands in the cost matrix to limit severe time warping [21; 22], performing alignments at multiple different resolutions [23; 24], parallelizable approximations of DTW [18; 25], and estimating alignments within strict memory limitations [26]. The third group focuses on extending the behavior of DTW to make it more flexible. Examples in the music information retrieval literature include handling structural differences due to repeats or jumps in music [27; 28; 29], aligning sequences in an online setting [30; 31; 32], handling partial alignments [33; 34], utilizing multiple performances of a piece to improve alignment accuracy [35], and handling pitch drift in a capella music [36]. The fourth group focuses on integrating DTW into modern neural network models. These include differentiable approximations of DTW suitable for backpropagation [37; 38; 39] or adopting a hard alternating scheme [40; 41; 42]. We note that our present study falls into the third group (more flexible behavior), as our focus is on improving robustness under certain conditions. This paper poses the following question: \"How can we make DTW more robust to global time warping conditions?\" There are two practices that are commonly used to handle differences in scale. The first practice is to select an appropriate set of allowable transitions to handle the amount of expected time warping. For example, the set \(\{(1,1),(1,2),(2,1)\}\) allows for a maximum time warping factor of 2, while the set \(\{(1,1),(0,1),(1,0)\}\) theoretically allows for an infinite amount of time warping. This is a design decision that must be made whenever DTW is invoked. The second practice is to re-scale the sequences to be the same length before invoking DTW [1; 2]. Though these two practices are commonly adopted, we are not aware of any studies that systematically study their effectiveness as a function of the global time warping factor. This paper compares these two approaches--and others--to determine how well they perform across a range of global time warping conditions.