This project uses the principles of dynamic time warping (DTW) to develop a speaker dependent word recognition system.  The words required to be recognized are the spoken digits zero through nine.  Part A of this project deals with the recording of words that are used for the remainder of the project.  The next part involves the processing of the recorded words and an implementation of the recognition algorithm.  The third part deals with optional enhancements that were made to the algorithm developed in part B.  Commentary on the results of this project can be found in the final section of this page.  All algorithms were implemented using the MATLAB software package.  When necessary, links to the source code are provided in each part. 

Part A - Test Material

In this part of the project the database of words to be used was created.  Each digit was recorded five times at a sampling rate of 8kHz with a resolution of 16-bits.  Four of the five recordings of each digit were randomly selected and used for the reference database.  The fifth (remaining) recording of each digit  was used as the test utterance.  End point detection was assumed to be done manually during this step while recording the files.  The zip file of the test material used for the project can be downloaded here. 

Part B - System Development

Before DTW is applied to the words they must be processed.  All audio is cut up into frames of length 512 samples with 50% overlap and windowed using a 512 point Hamming window.  A 1024 (512 non-redundant) point FFT of each of these frames is then taken laying the groundwork for the frame to be divided into sub-bands.  In this case the sub-bands correspond to the 17 critical bands of human hearing between 0 and 4000Hz.  Sub-bands with such a division are often referred to as Bark bands.  The following equation was used to convert from frequency to Bark:

z(i) = 13*atan(0.76*(f/1000)) + 3.5*atan(((f/1000)/7.5).^2)

The results of this equation do not correspond exactly with the table of critical bands that was provided in the project description but the discrepancies introduced are negligible.  All of the aforementioned work was used to make a function named energy_per_frame.  The source code can be downloaded by clicking the name of the function.  The input of this function is a wav file and the output is a matrix of width 17 (corresponding to the number of sub-bands) that varies in length.  The length depends on how many frames are contained in the inputted audio file.

Now that the audio is adequately processed a DTW implementation must be developed to compare two given wav files.  To handle this, a dtw function was coded based on the examples in the class notes.  The input to the function is two matrices, each of which correspond to the outputs of the previously established energy_per_frame function.  One of the two inputs is the reference sound and the other is the test sound.  In this section this function returns just the final distance.  The code can be downloaded here. 

With the functions described in the prior two paragraphs a word recognition system can now be implemented.  For testing purposes all 10 files were tested against the 40 reference files in one pass of the program.  The output of this program is a 10x40 matrix with each column representing the computed distances for the given test file against all of the reference files.  This matrix is shown below.  The blue numbers across the top are the test sounds and the blue numbers along the side are the reference sounds.  The four smallest distances in each column are highlighted in red providing a good indicator of the accuracy of the system. 

The results of the above table can be summarized in a confusion matrix, shown below. 

The implementation code for this part is available here.  A 'one at a time' implementation was also developed.  This program prompts the user for the input (the sound to be recognized) and then calculates the DTW against all of the 40 reference sounds.  The detected value is simply the number that corresponds to the shortest distance of the forty.  This code is available here.  Outputting the number with the lowest distance always resulted in correct detection, thus giving it a percentage error of 0. 

Part C - Optional Enhancements

1. The first of two optional enhancements to be implemented is the use of a threshold in recognition.  Using this threshold will allow for the possibility of words outside of the vocabulary to be rejected; it will also allow for the rejection of a word if it is too similar to more than one word in the database.  The threshold of 495 was selected to be the slightly higher than highest low value in the results table shown above.  It is obvious just from the data in the table that there will be plenty of recognition errors with such a high threshold.  The recognition error for known words is actually 90% (only zero is recognized correctly) with this high of a threshold.  Two 'outside' words (ten and eleven) were tested on this system as well.  Ten was detected as eight and eleven was detected as not being similar enough to any in the database.  The latter is correct, the former is obviously not correct.  This gives makes the false acceptance rate 50%.  The code for this part can be found here.  If the threshold was lowered better results would be attained with the sacrifice of one never being able to be detected because it is the reason that such a high threshold is needed.  Using a threshold in the manner just described is not a very good idea.  This sets the stage for the additional enhancement used in the next part. 

2. To complete this part another function was written and the original DTW function from above was modified.  The modification was made to not only return the final distance but to return the distance matrix that is used to obtain the final distance.  The distance matrix is needed to calculate the optimal path which is of great importance in this section.

The new function written was the most complex of the entire project.  It takes as an input a value of 0 through 9 and outputs a single sequence based on the four reference files for the inputted number.  The first step in doing this is to calculate the shortest file for the inputted number and this becomes the target length for the other three files so that they can be averaged to create the final (single) sequence.  The shortest file is then used as the reference in the modified DTW function while the other three are used as test files and the optimal path for each is calculated based on the distance matrix outputted from the DTW function.  Horizontal parts of the optimal path represent frames in the file being tested that can be averaged in order to shorten the length.  This averaging is always done in pairs to combine two frames into one.  After every average operation the new length of the sequence is compared to that of the reference (shortest) sequence.  If the sequence is not short enough the next horizontal part of the optimal path is detected and another average is performed.  This process is repeated until the desired length is obtained.  After all four of the reference sequences are of the same length they are averaged and then that single sequence is returned by the function.  The code for this function can be found here. 

In the main implementation for this part of the project the previously explained averaging function is called 10 times, once for each of the possible word values.  The results of this operation are compared one at a time to each of the test files thus generating a matrix similar to the one shown above, but of a smaller size.  This one is only 10x10 rather than 40x10 because all four of the references are combined into one thanks to the function explained earlier.  This matrix is shown below with the lowest value in each column highlighted in red. 

There is a 0% error for this technique.  It proves to be the more successful than the previous methods.  As the system becomes trained with more variations of the same sound this system will most likely increase in accuracy.  The implementation code for this section is available here. 

Part D - Summary and Discussion of Results

At first the implementation in Part B was done by creating a large three-dimensional array of the frame data for all of the numbers in the reference database.  Storing these values in such a way resulted in frames of zeros being appended on numbers that don't have the same number of frames as the longest file.  The presence of these zeros slightly altered the results of the DTW and made Part C more difficult--this is the reason for creating functions for everything.  It takes longer to run but it is more accurate.  When outputting the number corresponding to the index of the shortest distance this system is 100% accurate.  The only limitation of this process is that the words being inputted must be in the known vocabulary because this system doesn't have any sort of false detection algorithm implemented yet.  When analyzing the results of all four reference values for a given input the system is 90% accurate. 

Adding a threshold to reject words not in the system and to detect when an inputted word is similar to more than one number in the database proved to not be very accurate thus demonstrating the limitations of DTW (See above for percentage values).  DTW is an effective method of word recognition when only a very limited vocabulary is used. 

Exploiting the principles of time warping to combine all of the reference values for a given number into one increases the accuracy of the system while using less computational resources and less memory to store the reference database.  This is the best way to implement DTW.  A threshold may be added to this part and the results would be better than those of the previous section but they would still not be 100% accurate.  Once again, this proves that DTW is best when the user will always input from a finite and small set of known words which in this case are the spoken digits from zero to nine.