A connected spoken word recognition method by O(n) dynamic programming pattern matching algorithm

An O(n) dynamic programming (time warping) matching algorithm is proposed for connected spoken word recognition. The algorithm is based on the same principle of Two Level DP, Level Building DP, and Clock-Wise DP matching methods. The O(n) DP method is computationally more efficient than the conventional methods and also does not require many memory storages. This is able to recognize connected spoken words by one level (one pass) DP matching for every reference patterns. The amount of computation is the same as that of isolated spoken word recognition by DP matching. Of course, this algorithm gives the same results as Two Level DP, Level Building DP and Clock-Wise DP methods. Further, the flexibility of this algorithm is increased by embedding the unconstrained endpoints DP matching on both reference patterns and test pattern, and weighted DP matching. We show from the experiment on connected spoken digit recognition that the augmented algorithm improves the results.