电子产品世界

3 优化GDTW-SVM算法
尽管GDTW-SVM获得了较高的识别率，但是其计算复杂度高。DTW算法的计算复杂度是O(NT,NR)，而SVM算法在训练和识别过程中需要反复使用GDTW核函数，对于嵌入式设备的计算能力要求较高。因此，需要对GDTW核函数进行优化。
分析图1中的最优对齐路径，当两个样本完全相同时，最优对齐路径和对角线重合；当两个样本有所差别时，最优对齐路径偏离对角线，且差别(DTW距离)越大最优路径越偏离对角线。下面以字母m和n为例，进一步分析以上结论。
(1)依次从字母n的所有训练样本中选择一个样本，计算其到字母n的所有训练样本最优对齐路径，并规整到80’80矩阵；
(2)将所有计算结果叠加后得到n-n最优对齐路径叠加图；
(3)绘制叠加图，即图2的第一幅图，图中像素点灰度越高，代表越多最优对齐路径经过此点。同理，绘制n-m最优对齐路径叠加图和m-m最优对齐路径叠加图，分别为图2的第二和第三幅图所示。

从图2可以看到，两个相同或相似字符的最优对齐路径集中在对角区域：由于n的不同样本、m的不同样本的起笔写法比收笔写法随意，第一和第三幅图的对角区域的左下角比较宽；n和m的最优对齐路径在对角区域中分布较均匀，且第二幅图显示对角区域的中部有明显的低灰度区域。
假设训练样本可以代表联机手写字符的特征，则可以通过仅计算对角区域中的最优对齐路径来优化GDTW核函数。计算两个样本T=(t1，…，tNT)和R=(r1，…，rNR)的GDTW核函数时，假定二者属于相同的字符类，那么二者的差别不大，因此，在GDTW核函数计算中引入参数k和τ

式(9)中lbottom，ltop，lleft，lright如图3所示。引入参数k和τ之后，不在NT×NR的矩阵中求解式(8)，而是在k和τ约束的区域(即图3中两条虚线所夹的对角区域)中求解，计算最优对齐路径。

从直观的角度看，参数k和τ减少了最优对齐路径的计算空间，因此，修改后的GDTW核函数的计算时间减少。而另外一方面，如果参数τ保持不变(如τ=0．6)，参数k越小，最优对齐路径的前端的计算被约束在越小的空间，迫使其“最优”对齐路径的计算选择非最优对齐路径，即参数k是两个字符样本头部的相识程度的权重；类似地，参数τ是两个字符样本尾部的相识程度的权重。参数k和τ的权重作用对于如数字“0”和“6”等相似字符的分类有重要意义。

1 2 3 4

关键词： GDTW-SVM 算法 联机 识别