Dynamic Time Warping

From MSc Voice Technology
Revision as of 17:34, 19 September 2023 by WANGYINQIU (talk | contribs) (→‎Impact)
Jump to navigation Jump to search

Introduction

Dynamic Time Warping (DTW) is a widely used technique for finding the best alignment between two given (time-correlated) sequences under certain conditions. Intuitively, the sequences are twisted in a nonlinear fashion to match each other. Initially, DTW was used to compare different speech modes in automatic speech recognition.[1]

While first introduced in 60s and extensively explored in 70s by application to the speech recognition, its applications have since expanded considerably. Today, DTW is employed in various domains, including but not limited to handwriting and online signature matching, sign language recognition, gesture recognition, and time series clustering. [2]

Historical Context

The roots of Dynamic Time Warping (DTW) can be traced back to the 1960s when it was first introduced as an algorithm for solving time series alignment problems. In the 1970s, DTW began to gain prominence through its application to speech recognition tasks.[3]

During this early period of research, scientists were grappling with fundamental challenges in recognizing spoken words and phrases. Even when the same word was spoken by the same person multiple times, factors like speech rate, emphasis, and coarticulation effects resulted in nonlinear time distortions when comparing utterances. These variations made it difficult to precisely match spoken words against templates or reference patterns, as the alignment of speech signals was non-linear and complex. This misalignment of timing poses a significant problem for accurate distance measurement in speech recognition systems. Even small shifts can lead to incorrect identification of words. Researchers explored linear normalization techniques to account for timing differences, but these proved insufficient for complex speech patterns.[4]

The groundbreaking contribution of DTW was its ability to address these challenges effectively. DTW allowed for "elastic" transformation of time series, which means it could align and compare speech signals with different time scales and phases. This flexibility in time-series alignment was crucial in mitigating the effects of shifting and distortion in speech signals.[3] In parallel with these challenges, DARPA's Speech Understanding Research program in the 1970s aimed to enhance the capabilities of speech recognition systems, paving the way for innovative approaches like Dynamic Time Warping (DTW) to address the complexities of speech pattern alignment.

One of the primary motivations for developing DTW was to improve the accuracy of speech recognition systems. Traditional methods that relied on fixed templates for word recognition struggled to handle the variations in pronunciation time. DTW emerged as a method to measure the similarity of spoken patterns with different time zones, effectively solving the time alignment problem that had previously plagued speech recognition.

T. K. Vintsyuk's seminal paper titled "Speech Discrimination by Dynamic Programming" in 1972 played a significant role in introducing DTW as a powerful tool for speech recognition. This work emphasized the importance of time normalization, where the duration of unknown words is equated to that of standard words, to enhance recognition accuracy.[5]

In 1978, Sakoe and Chiba proposed using DTW for automatic word recognition. DTW allowed for an "elastic" time alignment through non-linear warping of the time axis between two time series. This dynamic programming approach was shown to outperform previous linear methods by more accurately modeling intrinsic fluctuations in speech. Around the same time, other pioneering studies also employed DTW for "time normalization" prior to classification.[6]

Key Innovations

The speech recognition algorithm based on DTW is a classic algorithm to solve the template matching problem, and its essence is the idea of dynamic programming (DP).

"Template matching" refers to the training phase, the feature vector sequence of speech corresponding to each word in vocabulary table was extracted as the template, and then was stored to the characteristics template library; Then, in the recognition phase, to compare the feature vector sequences of the speech to be recognized with each template of template library by dynamic time warping algorithm, and the result with the highest similarity would be taken as the recognition output.[7]

The traditional template matching commonly uses the Euclidean distance metric to measure the degree of distortion, as follows:

Where n and m are frame indices, T is the length of the feature vector, p is the metric exponent, typically 2, representing the Euclidean distance. This formula is used to calculate the distortion between a test model frame T(m) and a reference model frame R(m). The smaller the distortion, the higher the similarity between the two feature vectors.[8]

However, in practical speech recognition, random variations occurring during pronunciation (such as differences in the duration of syllables and other subtle pronunciation variations) can result in two syllables not having a linear temporal correspondence. Euclidean distance measurement only considers numerical differences at the same time points, and therefore, it cannot capture temporal distortions and nonlinear relationships.

The core innovation of DTW lies in introducing a novel sequence similarity measurement method, which involves point-wise matching and utilizes dynamic programming to obtain the optimal path. This approach measures the similarity between sequences by calculating distances at different time points, enabling alignment of time series with different lengths. It possesses the capability to adapt to various data patterns and provides a more accurate assessment of similarity between speech samples.

Specific Method:

First, in a two-dimensional Cartesian coordinate system, construct an n × m matrix grid, with the horizontal axis representing the test model (n) and the vertical axis representing the reference model (m). Each intersection point (n, m) in the grid corresponds to a frame in the test model and the training model. The DP (Dynamic Programming) algorithm can find a path passing through multiple grid points in the grid. The points passed through by the path represent the alignment points for the calculation of the two sequences. Therefore, the sum of frame distortions at all intersection points in this path is minimized, and this path is the optimal warping path, which is the shortest distance measure between these two sequences. The smaller the path warping value, the more similar the two patterns become.

Path Selection：The selection of the path is not arbitrary; the path, defined as "W", must adhere to the following conditions at least:

1. Boundary Condition: The boundary conditions dictate that w1 = (1, 1) and wK = (m, n). While speech may exhibit variations, the order of these variations within different segments should not be reversed. Therefore, the only valid path goes from the bottom-left corner of the grid to the top-right corner.

2. Continuity: If wk-1 = (a', b'), then for the next point in the path wk = (a, b), it must satisfy the conditions (a-a') <= 1 and (b-b') <= 1. In other words, it's not possible to jump over a point to make a match; alignment can only occur with adjacent points. This ensures that every coordinate in Q and C appears in W.

3. Monotonicity： If wk-1 = (a', b'), then for the next point in the path wk = (a, b), it must satisfy 0 <= (a-a') and 0 <= (b-b'). This constraint ensures that points on W follow a monotonically increasing pattern over time, preventing intersections like the dashed lines in Figure B.

Combining the constraints of continuity and monotonicity, each grid point's path can only follow three possible directions. For example, if the path has already passed through grid point (i, j), the next point it can pass through must be one of the following: (i+1, j), (i, j+1), or (i+1, j+1).

The dynamic programming (DP) method searches for a suitable path within the grid to find the optimal match between the test model and the reference model, thus accomplishing the task of speech recognition.

Impact

In Speech recognition, as the speech is a time-dependent process, the utterances of the same word will have different durations, and utterances of the same word with the same duration will differ in the middle, due to different parts of the words being spoken at different rates.[9]In other words, the voice signal exhibits a high degree of variability, even for the same person pronounces the same word in the same way but in different time, they can’t be exactly the same because the variation arises from the unpredictable duration of each pronunciation. So it is not ideal to compare each word's feature vector sequence's effect directly.

Dynamic Time Warping algorithm is a prevailing approach which is practical and theoretical. Dynamic Time Warping algorithm is based on dynamic programming, problem solving approach and used for measuring similarity between two sequences, which may vary in time or space. Similarity is measured by computing a distance between two times series. [10]It is an early and classical algorithm for speech recognition especially for isolated word recognition.

Improving Accuracy and Reducing Processing Time

The impact of Dynamic Time Warping on speech recognition is significant. One of the problems of speech recognition is different timing of speech alignment, and two words from the same word by the same user can have different times, which means small changes may result in incorrect recognition. Dynamic Time Warping is an efficient method for solving time alignment problem. Dynamic Time Warping solves this problem by aligning words correctly and calculating the minimum distance between two words. [9]Dynamic Time Warping can utilize automated alignment methods, thereby eliminating the need for time consuming manual alignment procedures.[11] It enhances the effectiveness and efficiency of speech recognition, leading to improved accuracy and reduced processing time.

Reduce the Impact of Background Noise

In real-world scenarios, background noise is often present, making speech recognition challenging. Dynamic Time Warping could be used to reduce the impact of background noise on speech recognition. Most of these DTW-related studies have either developed improved template-matching algorithms, or provided modified schemes for a DTW operation optimization framework for increasing the robustness of the recognition system.[12] Dynamic Time Warping could help distinguish between the speech signal and noise, improving recognition accuracy in noisy environment.

Reduce the Impact of Pronunciation Variations

Dynamic programming is a popular method employed to avoid discontinuities and hence improve the robustness of the pitch detection algorithm.[11] It is well-known that individuals may pronounce words differently while maintaining the same meaning due to speakers' accent, dialect, gender or voice quality. It is important for speech recognition system to recognize speech from diverse sources. DTW's dynamic time alignment capability allowed it to better accommodate these variations.

Versatility Across Domains

Dynamic Time Warping is a versatile technique primarily used in time series analysis and pattern, and it have been used in many applications. For example, road surface monitoring can employ image processing and ultrasonic sensors based on Dynamic Time Warping.[13]Dynamic Time Warping is used to gesture recognition[14], which is useful in applications like sign language recognition or gesture-based control systems. Also, Dynamic Time Warping can be used in medical like X-ray diagnosis[15]and smart healthcare system[16].

Historical Significance

Traditional Dynamic Time Warping was one of the pioneering algorithms in speech recognition which offers important lessons for later developments and new recognition algorithms, like the Hidden Markov Models. The Hidden Markov Model and Dynamic Time Warping are actually sharing the same idea of DP(dynamic programming). [17] And HMMs and DTW are often used together to achieve better performance in speech recognition. [18]Lessons learned from DTW's approach to dynamic programming have paved the way for more sophisticated algorithms and machine learning methods in speech recognition.

Future Research

The field of Dynamic Time Warping (DTW) in speech recognition continues to offer exciting opportunities for exploration and innovation.

Adaptability to Diverse Speaking Styles and Accents:

  • Researchers can investigate methods to make DTW-based systems more adaptable to variations in regional accents, speaking styles, and individual vocal characteristics. This research could draw inspiration from recent advances in accent adaptation and speaker recognition techniques.

Optimizing DTW for Real-Time Applications:

  • Future research can focus on optimizing DTW algorithms for parallel processing and efficient computation. Techniques such as parallelization and hardware acceleration may be explored to meet the demands of real-time applications.

Hybrid Approaches with Deep Learning:

  • Investigating hybrid systems that combine DTW with deep learning techniques, such as convolutional neural networks (CNNs) or recurrent neural networks (RNNs), could lead to more powerful and accurate speech recognition systems. This research direction can explore how to leverage the complementary strengths of both approaches.

Niche Applications:

  • Exploring DTW's application in niche areas like emotional speech recognition is another promising direction. Researchers can delve into the development of DTW-based models that can capture emotional cues and improve the recognition of emotional speech.

Scalability and Efficiency:

  • Scalability and efficiency are critical as speech recognition systems handle larger datasets and real-time tasks. Investigating how DTW can scale efficiently to handle big data while maintaining high recognition accuracy is an area ripe for exploration.

References

Together

  1. ↑ (2007). Dynamic Time Warping. In: Information Retrieval for Music and Motion. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74048-3_4
  2. ↑ Senin P. Dynamic time warping algorithm review[J]. Information and Computer Science Department University of Hawaii at Manoa Honolulu, USA, 2008, 855(1-23): 40.
  3. ↑ 3.0 3.1 Senin, Pavel. ‘Dynamic Time Warping Algorithm Review’, n.d.
  4. ↑ Sakoe, H., and S. Chiba. ‘Dynamic Programming Algorithm Optimization for Spoken Word Recognition’. IEEE Transactions on Acoustics, Speech, and Signal Processing 26, no. 1 (February 1978): 43–49. https://doi.org/10.1109/TASSP.1978.1163055.
  5. ↑ Vintsyuk, T. K. ‘Speech Discrimination by Dynamic Programming’. Cybernetics 4, no. 1 (1972): 52–57. https://doi.org/10.1007/BF01074755.
  6. ↑ Sakoe, H., and S. Chiba. ‘Dynamic Programming Algorithm Optimization for Spoken Word Recognition’. IEEE Transactions on Acoustics, Speech, and Signal Processing 26, no. 1 (February 1978): 43–49. https://doi.org/10.1109/TASSP.1978.1163055.
  7. ↑ Zhang, Jing, and Benzhuo Qin. "DTW Speech Recognition Algorithm of Optimization Template Matching".
  8. ↑ Juang, B.-H. 《On the Hidden Markov Model and Dynamic Time Warping for Speech Recognition-A Unified View》. AT&T Bell Laboratories Technical Journal 63, No.7, September 1984): 1213–43. https://doi.org/10.1002/j.1538-7305.1984.tb00034.x.
  9. ↑ 9.0 9.1 T. B. Amin and I. Mahmood, "Speech Recognition using Dynamic Time Warping," 2008 2nd International Conference on Advances in Space Technologies, Islamabad, Pakistan, 2008, pp. 74-79, doi: 10.1109/ICAST.2008.4747690.
  10. ↑ Yadav M, Alam M A. Dynamic time warping (dtw) algorithm in speech: a review[J]. International Journal of Research in Electronics and Computer Engineering, 2018, 6(1): 524-528.
  11. ↑ 11.0 11.1 Turk O, Arslan L M. Robust processing techniques for voice conversion[J]. Computer Speech & Language, 2006, 20(4): 441-467.
  12. ↑ Ding Jr I, Yen C T, Hsu Y M. Developments of machine learning schemes for dynamic time-wrapping-based speech recognition[J]. Mathematical Problems in Engineering, 2013, 2013.
  13. ↑ Sharma S K, Phan H, Lee J. An application study on road surface monitoring using DTW based image processing and ultrasonic sensors[J]. Applied Sciences, 2020, 10(13): 4490.
  14. ↑ Hartmann B, Link N. Gesture recognition with inertial sensors and optimized DTW prototypes[C]//2010 IEEE International Conference on Systems, Man and Cybernetics. IEEE, 2010: 2102-2109.
  15. ↑ Adwan S, Alsaleh I, Majed R. A new approach for image stitching technique using Dynamic Time Warping (DTW) algorithm towards scoliosis X-ray diagnosis[J]. Measurement, 2016, 84: 32-46.
  16. ↑ Ismail A, Abdlerazek S, El-Henawy I M. Development of smart healthcare system based on speech recognition using support vector machine and dynamic time warping[J]. Sustainability, 2020, 12(6): 2403.
  17. ↑ Fang C. From dynamic time warping (DTW) to hidden markov model (HMM)[J]. University of Cincinnati, 2009, 3: 19.
  18. ↑ Hidden Markov Models (1970s): HMMs revolutionized speech recognition by allowing more accurate modeling of speech patterns, leading to improvements in accuracy.

Group Members

SU CANTAO

ZHANG ZIYUN

WANG YINQIU

Retrieved from "http://wiki.voice-technology.nl/index.php?title=Dynamic_Time_Warping&oldid=695"