Viterbi和DTW算法的关系分析——在非特定人手语识别中的应用

Mapping Analysis Between Viterbi and DTW Algorithms——Application to the Identification of Signer Independent Sign Language

在经典的模式识别理论中,Viterbi算法代表了统计概率的模式匹配算法,而DTW算法代表了模版匹配的模式匹配算法,它们之间是否存在关系至今尚无定论.为了找到这两种算法之间的关系,在"类别隶属度"是广义概率的假设前提下,应用模糊数学的理论在Viterbi算法与DTW算法之间建立起联系.首先,提出了利用模糊数学的贴近度把DTW算法的"距离"向Viterbi算法的"概率"转化的通用贴近度表达式,并对通用贴近度表达式给出了理论上的证明.其次,应用DTW的通用贴近度表达式重估HMM参数,建立DTW算法与Viterbi算法之间的模糊贴近度关系,并为此提出了δ-ε算法,得到基于数据帧的类似于HMM的参数重估形式.然后,为了确保建立DTW算法与Viterbi算法之间的模糊贴近度关系的正确性,以定理的形式给出了相应的证明.再次,通过设定的DTW贴近度表达式对HMM参数重估的过程中,发现了DTW贴近度的重估参数与HMM重估参数之间存在着的模糊关系,以定理的形式对这种模糊关系加以证明.最后,依据上述定理提出了Dtw-ViterbiⅠ,Ⅱ,Ⅲ算法,以定理的形式对Dtw-ViterbiⅠ,Ⅱ,Ⅲ算法的正确性加以证明,并将对Dtw-ViterbiⅠ,Ⅱ,Ⅲ算法应用于非特定人手语的识别.实验表明,把DTW算法的路径搜索策略以概率的形式引进到Viterbi算法中,能够以削减候选词集的方式部分消除非特定人手语识别的误识,从而提高大词汇量情况的下非特定人手语识别的识别率和速度.

In classical pattern classification theory, Viterbi algorithm represents pattern matching algorithm of statistic probability. However, DTW algorithm represents pattern matching algorithm of template matching algorithm. Whether there is any relationship between them have not been presented clearly. Aiming at this problem, the authors set up relationship between Viterbi algorithm and DTW algorithm based on application of fuzzy math theory under the premise that ＂the category of fuzzy math membership is the general probability＂. Firstly, they propose the common closeness degree expression transferring ＂distance＂ of DTW algorithm to ＂probability＂ of Viterbi algorithm making use of closeness degree in fuzzy math and prove the common closeness degree expression theoretically. Secondly, the HMM parameters are re-estimated with the common closeness degree of DTW to set up fuzzy closeness degree relationship between DTW algorithm and Viterbi algorithm, for which the δ-ε algorithm is presented to obtain parameter re-estimating form similar to HMM based on data frame. Then, in order to ensure correctness of the fuzzy closeness relationship between DTW algorithm and Viterbi algorithm, corresponding proof is given as a theorem. Thirdly, during the HMM parameter re-estimation with the decided DTW closeness degree expression, it is found that there exists fuzzy relationship between the DTW closeness degree re-estimating parameters and the HMM re-estimating parameters and it is proved as a theorem. Finally, the authors propose Dtw- Viterbi Ⅰ , Ⅱ, Ⅲ based on the above theorem, prove the correctness of them as a theorem and implement them in signer-independent sign language recognition. Experiment results show that introducing the path searching strategy of DTW algorithm in Viterbi algorithm in the form of probability can partly reduce the failures in signer-independent sign language recognition by reducing candidate vocabulary thus improving the signer-independent sign language recognition rate and speed in case of large vocabulary.