# Audio Fingerprint Extraction Based on Locally Linear Embedding for Audio Retrieval System
## 3 Audio Fingerprint Matching
### Dynamic Time Warping  
For improving the resistance against linear distortion of the audio signal in the matching process, the DTW is adopted. The DTW is mainly used to solve the case that the two sequences are not equal in length of the comparison, which exactly corresponds to the change of audio signal in linear speed. The retrieved objects include speech and music. If the query is a recording or someone's speech received by microphone, the playback speeds depends on the speaking speeds which varies from person to person. The same goes for retrieving music by humming. Especially in the copyright protection, differences in audio versions can result in different playback speeds. When the reference is compared with the query, the length of two sequences is no longer equal, denoted \(R\) and \(R^{\prime}\). The algorithm calculates the similarity between every two fingerprints, then plans a matching path from the first to the last comparison according to the minimum accumulative error. The path planning strategy ensures the alignment in time and reduces the errors caused by time dislocation. The specific method to achieve the following:  
(1) Similarity Matrix Computation  
Before aligning the query and the reference, first a similarity matrix of size \(R\times R^{\prime}\) needs to be constructed, denoted as \(\mathbf{X}\) where \(R\) is the length of reference and \(R^{\prime}\) is the length of query. The elements in the matrix is the similarity of every two fingerprints in the query and the reference. The row and column represent the positions of two fingerprints in the respective sequences of the comparison. To be expressed more clarity, an example of matrix \(\mathbf{X}\) is given in Figure 5.  
The matrix \(\mathbf{X}\) is shown schematically in Figure 5 where the numbers in the grid is the similarities between the reference and query fingerprints computed by the Equation (11). The length of the reference and the query could be different or be set artificially to gain a better resistance against linear speed changes. (2) Similarity Accumulation Matrix Computation  
Accumulating the above similarity matrix \(\mathbf{X}\) from the starting point (1, 1) to (\(R\), \(R^{\prime}\)). There are three kinds of paths for each accumulation: transverse, longitudinal, or oblique. The direction with the minimum similarity is chosen for each accumulation. The computation is carried out first in row and then in column, and the result is recorded as matrix \(\mathbf{Y}\). Its formula can be express as:  
\[\mathbf{Y}(i,j)=\mathbf{X}(i,j)+\min\{\mathbf{Y}(i-1,j-1),\mathbf{Y}(i-1,j), \mathbf{Y}(i,j-1)\} \tag{12}\]  
The similarity accumulation of the first row is computed from left to right as shown in Figure 5(a) and the second row is computed in the same order represented in Figure 5(b). The computation rule of the similarity accumulation is the number in grid plus the former accumulation according to the minimum of the sum as mentioned in Equation (12). All the accumulations are labeled in the upper right corner of each number in grid and these superscripts form the matrix \(\mathbf{Y}\). Figure 5: Similarity matrix. Figure 6: Similarity accumulation. (3) The Shortest Path Planning  
Once the accumulation matrix \(\mathbf{Y}\) is obtained, the DTW works backwards from the end point to the starting point to plan the path with minimum similarity accumulation and count the number of matching points it passes served as compensation. The path planning process is shown in Figure 7:  
The superscripts in Figure 7a shows the accumulation results and the red arrow is the accumulation direction. The blue arrow in Figure 7b is the matching path obtained by looking back from the end to the beginning. It is important to notice that three conditions must be met for path planning:  
1. The path planning begins from (1, 1) and ends at (\(R\), \(R^{\prime}\));
2.