14-4 DTW of Type-1 and 2

[chinese][all]
Slides: DTW, DTW for melody recognition, DTW for speech recognition
DTW (Dynamic Time Warping) is another commonly used method for frame-based approach to QBSH in melody recognition. The major advantage of DTW is its high recognition rate for QBSH. This is partly due to its robustness in dealing with undesirable pitch vectors, especially for type-1 DTW which allow skipping of sporadic unlikely pitch values. On the other hand, the major disadvantage of DTW is its requirement for massive computation, which is worsen by the fact that there is no one-shot scheme for dealing with key transposition. Since the applications of DTW are quite extensive in numerous different fields, research on speeding up DTW is a rather hot topic.
For technical details of DTW, please refer to the chapter on dynamic programming. In this section, we shall give some examples of using DTW for QBSH. First of all, we can plot the mapping path when comparing a query input with a database entry using type-1 DTW, as follows:
Example 1: mrDtw1Plot01.m

In the above example of type-1 DTW, we need to be aware of two issues:

For QBSH application, we have two types of comparisons:

Comparison from beginning: The acoustic input corresponds to the beginning of a song in the database. This is exactly the case in the above example, so we set anchorBeginning=1 and anchorEnd=0.
Comparison from anywhere: The acoustic input corresponds to the middle of a song. Under such a condition, we need to set anchorBeginning=0 and anchorEnd=0.
In fact, if we can define the "beginning position" of a query input, then all comparisons can be viewed as "comparison from beginning" with different beginning positions. Several commonly used "beginning positions" are listed next, according to their complexities:

The beginning of a song: This is not a realistic assumption since the most well-known part of a song does not necessarily starts from the beginning.
The refrain (chorus or burden, 副歌) of a song: However, refrains of a song cannot be defined objectively.
The beginning of each sentence: This is most likely to be the case in karaoke systems since such information is already embedded in the songs in order to display the lyrics in a sentence-by-sentence manner.
The beginning of each note: This is the final catchall which requires a lot of computation.

To deal with key transposition, we use a linear search between the interval of [-2, 2] with a resolution of 11. It is possible to use some sort of heuristic search, such as the one mentioned in section 2 of this chapter.

Besides plotting the mapping path, we can also employ two other methods for displaying the result of DTW, as mentioned in the chapter of dynamic programming. One of them is the mapping between two curves in a 2D plane, as shown next:
Example 2: mrDtw1Plot02.m

Similarly, we can plot the mapping between two curves in a 3D space, as shown next:
Example 3: mrDtw1Plot03.m

Hint
If you try the above example in MATLAB, you can actually use the mouse to rotate the plot to get a better view of the mapping between these two curves.

We can simply change "dtw1" to "dtw2" in these examples to obtain the results of type-2 DTW. In practice, the performance of type-1 and type-2 DTW is likely to be data dependent. There is no guarantee as which one is the clear winner for different data sets.
As long as we have grasped the characteristics of DP, we can devise tailored comparison methods suitable for different scenarios of melody recognition.
Audio Signal Processing and Recognition (音訊處理與辨識)