Improvement Research And Application Of Dynamic Time Warping Algorithm

With the development of computer technology and mathematical theory research,pattern recognition technology based on the combination of mathematics and computer has been deeply studied in various fields of scientific research and social production.In the pattern recognition algorithms,the similarity measure between samples is an important basis for recognition and classification.The distance definitions based on mathematical theories,as a common measure,are introduced into the pattern recognition.In recent years,with the emergence of more complex and more accurate sampling tools,a large number of matrixes with different size have emerged.The traditional one-dimensional distance algorithm has some limitations in measuring matrix similarity.Inspiring by the advantage of the traditional dynamic time warping(DTW)algorithm that can deal with unequal vectors in one-dimensional samples,some new two-dimensional DTW algorithms expended from the traditional DTW algorithm are proposed in the thesis,which are developed to solve the problems of matrix samples and to provide the new distance measurement between unequal-size matrix samples.In the application of matrix data,grayscale images are the most intuitive display,so,grayscale images become one of the main object of DTW researches.However,the grayscale image commonly contains noise information,in order to eliminate deviation,a new sampling optimization method based on 4-neighborhood mean template and histogram search is proposed.A fast 4-neighborhood mean template is defined to distinguish the edge pixel from the middle pixel.Meanwhile,pixel points with more statistics are searched as sampling points based on the gray histogram.The pixel values obtained after the optimized sampling and the calculated values of the 4-neighborhood mean template are used as the training set to complete the fingerprint binarization by the support vector machine.The FVC2004 database verification and the comparison with the results of relevant algorithms show that the new algorithm has higher classification accuracy,more accurate processing of edge pixel points and faster computing speed.What's more,the basic research samples are provided by the new optimization method for the subsequent application of the improved DTW algorithms.Firstly,the Non-Interlaced DTW algorithm is proposed.The algorithm calculates the DTW distance between the row vector samples of the matrixes,introduces the intermediate distance matrix to calculate the DTW distance.Meanwhile,Non-Interlaced DTW algorithm defines the standardized DTW distance as the final distance measure.The verification results on the FVC2004 database show that the new algorithm can solve the distance between unequal-size matrix samples well.More important,the accuracy of matrix sample similarity measurement is greatly improved through multiple DTW distance calculation.In addition,in order to reduce the complexity of the algorithm caused by a large number of distance calculations in the Non-Interlaced DTW algorithm,the 2D-DTW algorithm is then proposed.The algorithm designs the distance-cuboid between matrix samples by means of fixed matrix row or column with equal-size and construct distance matrix by distance-cuboid cutting.The minimum distance is solved by the DTW algorithm,and the normalized distance is defined as the final distance measure.Using CIFAR-10 database and MNSIT database to verify the new model,2D-DTW developed from Non-Interlaced DTW reduces the use of DTW algorithm,consequently,it decreases the calculation time and also ensures the accuracy of distance calculation.