【DWT】计算两不等序列相似度：DWT

发布时间：2026/7/19 22:44:32

note

DTW（DP-matching）用于计算两个不等长、但变化趋势相关的序列的相似度。论文给出了最优的对齐规则：对称权重 + 斜率约束P=1，让对齐更准，识别错误率降到了原来的2/3
针对两个时长不同、采样点数量不一致的语音特征序列，用动态时间规整（DTW）找最优非线性对齐路径，消除语速波动带来的时间轴偏差。
创新引入斜率约束（P=1），禁止路径过陡/过缓，避免短语音段错误匹配长语音段，同时采用对称权重设计，确保两个序列的所有特征都被纳入计算，对齐更合理。
实验验证该优化后的DTW算法在孤立词识别任务上错误率仅为传统算法的2/3，成为后续DTW应用的经典标准方案。

文章目录

note
- 一、研究动机
- 二、论文核心
- - 1. 时间归一化距离的一般定义
  - 2. 规整函数的约束条件
  - 3. 对称形式与非对称形式的权重设计
  - 4. DP 递推算法与斜率约束的具体化
- 三、实验结果
- - 实验一：对称/非对称与斜率约束对比（日语数字）
  - 实验二：对称形式在地名集上的斜率约束（日语地名）
  - 实验三：与同期其他DP算法对比
- 四、分析与结论
五、Python代码示例
Reference

一、研究动机

论文：Dynamic Programming Algorithm Optimization for Spoken Word Recognition
作者：Hiroaki Sakoe, Seibi Chiba
会议/期刊：IEEE Transactions on Acoustics, Speech and Signal Processing
年份：1978
是语音识别领域中关于动态时间规整（DTW/DP‑matching）的经典文献，系统提出了带斜率约束的对称型DP算法并验证其优越性

说话速率变化导致时间轴非线性波动：早期线性时间归一化无法处理复杂的非线性波动，影响孤立词识别准确率。
已有DP‑matching缺乏系统性优化：虽然DP可用于非线性时间对齐，但在对称/非对称形式选择、权重设计、斜率约束等方面缺乏理论分析与实验验证，不同研究组算法差异大、性能不明确。
目标：在通用等间隔采样、无先验语言学知识的前提下，给出一种最优的DP时间归一化算法，提升类别间判别能力并降低识别错误率。

二、论文核心

1. 时间归一化距离的一般定义

将两段语音表示为特征向量序列
A = a 1 , … , a I A = a_1,\dots,a_IA=a1,…,aI，B = b 1 , … , b J B = b_1,\dots,b_JB=b1,…,bJ。
通过规整函数（warping function）
F = { c ( k ) = ( i ( k ) , j ( k ) ) } F = \{c(k)=(i(k),j(k))\}F={c(k)=(i(k),j(k))}建立时间点对应关系。
定义时间归一化距离为沿规整路径的加权距离之和再除以权重总和：
D ( A , B ) = min ⁡ F ∑ k = 1 K d ( i ( k ) , j ( k ) ) w ( k ) ∑ k = 1 K w ( k ) D(A,B)=\min_F \frac{\sum_{k=1}^K d(i(k),j(k))\,w(k)}{\sum_{k=1}^K w(k)}D(A,B)=Fmin∑k=1Kw(k)∑k=1Kd(i(k),j(k))w(k)
其中d ( i , j ) = ∥ a i − b j ∥ d(i,j)=\|a_i-b_j\|d(i,j)=∥ai−bj∥，w ( k ) w(k)w(k)为非负权重。

2. 规整函数的约束条件

为保证时间对齐符合语音实际特性，对 ( F ) 施加多重约束：

单调性：i ( k − 1 ) ≤ i ( k ) , j ( k − 1 ) ≤ j ( k ) i(k-1)\le i(k),\,j(k-1)\le j(k)i(k−1)≤i(k),j(k−1)≤j(k)
连续性：相邻步长不超过1（( i,j ) 每步最多+1）
边界条件：( 1 , 1 ) (1,1)(1,1)到( I , J ) (I,J)(I,J)
调整窗口：∣ i ( k ) − j ( k ) ∣ ≤ r |i(k)-j(k)|\le r∣i(k)−j(k)∣≤r，限制最大时间偏差
斜率约束（核心创新）：
限制规整函数斜率，避免在对角方向前进步数不足时过度偏向 i 或 j 轴；用P = n / m P=n/mP=n/m度量约束强度（P PP越大越刚性，线性对齐对应P → ∞ P\to\inftyP→∞）。

3. 对称形式与非对称形式的权重设计

对称形式：
w ( k ) = ( i ( k ) − i ( k − 1 ) ) + ( j ( k ) − j ( k − 1 ) ) w(k) = (i(k)-i(k-1)) + (j(k)-j(k-1))w(k)=(i(k)−i(k−1))+(j(k)−j(k−1))，归一化系数N = I + J N=I+JN=I+J
→ 满足D ( A , B ) = D ( B , A ) D(A,B)=D(B,A)D(A,B)=D(B,A)，且最小权重为1，不会遗漏特征向量。
非对称形式：
w ( k ) = ( i ( k ) − i ( k − 1 ) ) w(k) = (i(k)-i(k-1))w(k)=(i(k)−i(k−1))（或仅对 j），N = I N=IN=I（或J JJ）
→ 可能出现w ( k ) = 0 w(k)=0w(k)=0，导致部分特征被排除，理论上不利于均衡比较。

论文从理论与实验两方面论证对称形式更优，尤其在无/弱斜率约束时。

4. DP 递推算法与斜率约束的具体化

给出初始条件与DP方程：
g 1 ( c ( 1 ) ) = d ( c ( 1 ) ) w ( 1 ) g_1(c(1)) = d(c(1)) w(1)g1(c(1))=d(c(1))w(1)，
g k ( c ( k ) ) = min ⁡ c ( k − 1 ) [ g k − 1 ( c ( k − 1 ) ) + d ( c ( k ) ) w ( k ) ] g_k(c(k)) = \min_{c(k-1)}[g_{k-1}(c(k-1)) + d(c(k)) w(k)]gk(c(k))=minc(k−1)[gk−1(c(k−1))+d(c(k))w(k)]。
针对P = 0, 1/2, 1, 2等斜率约束，分别给出对称/非对称形式的具体DP方程与可达前驱点集合（见表Ⅰ），并对非对称形式做加权改进以避免零权重问题。

三、实验结果

实验基于日语数字（10词）与日语地名（50词）孤立词数据，10名说话人、多重复，采用带通滤波器组+18ms采样+自动增益控制，Chebyshev距离，强制决策最近邻分类。

实验一：对称/非对称与斜率约束对比（日语数字）

对称形式明显优于非对称形式；
随斜率约束增强（P PP增大），两者差距缩小；
对称形式在 ( P\le1 ) 性能几乎不受影响，非对称形式在 ( P=1 ) 达到最优；
( P>1 ) 后性能下降（过度约束退化为近似线性对齐）；
线性时间归一化错误率约0.8%，而最优DP算法更低。

实验二：对称形式在地名集上的斜率约束（日语地名）

地名集存在易混淆词对（如 Chiba–Shiga 等）；
对称形式在P ≈ 1 P\approx1P≈1达到最优，证明斜率约束对提升判别有效；
说明即使在对称形式下，适当斜率约束仍有益，尤其在词汇量大、混淆度高时。

实验三：与同期其他DP算法对比

对比算法包括：Sakoe–Chiba(1973)、Velichko–Zagoruyko、White–Neely、Itakura 及线性方法，结果（错误率 %）如下：

算法	日语数字	日语地名
本文对称 P=1	0.2	0.8
本文非对称 P=1	0.3	1.3
Sakoe–Chiba(1973)	0.3	1.5
White–Neely	0.33	1.3
Itakura	0.4	1.3
Velichko–Zagoruyko	2.0	2.7
线性方法	0.87	5.9

→本文提出的“对称形式 + 斜率约束 P=1”在两项任务上均取得最低错误率，相比次优算法错误数减少约至2/3。

四、分析与结论

对称形式优势：理论上有对称性、无特征排除；实验上在各约束条件下均优于或等价于非对称形式，尤其弱约束时差距明显。
斜率约束的作用：
- 防止过度扭曲导致异类词误配（如短辅音段对齐长元音）；
- ( P=1 ) 在性能与计算复杂度间取得最佳平衡（DP方程较简单）；
- 对对称形式在困难任务（地名）中同样有效。
综合结论：
在等间隔采样、无额外语言学先验条件下，对称型DP‑matching + 斜率约束 ( P=1 )是最优的时间归一化算法，较同期多种DP方法识别错误显著更低，且利于硬件实时实现（文末已构建300ms处理60地名的DP处理器）。

五、Python代码示例

importnumpyasnp# 视频A每帧特征A=np.array([1,2,3,4,5])# 视频B每帧特征（播放慢一点）B=np.array([1,2,2,3,4,5])m=len(A)n=len(B)# DP矩阵dp=np.full((m+1,n+1),np.inf)dp[0,0]=0foriinrange(1,m+1):forjinrange(1,n+1):# 当前两帧距离cost=abs(A[i-1]-B[j-1])dp[i,j]=cost+min(dp[i-1,j],# 删除dp[i,j-1],# 插入dp[i-1,j-1]# 匹配)print(dp)print("DTW distance =",dp[m,n])

结果：

[[0.inf inf inf inf inf inf][inf0.1.2.4.7.11.][inf1.0.0.1.3.6.][inf3.1.1.0.1.3.][inf6.3.3.1.0.1.][inf10.6.6.3.1.0.]]DTW distance=0.0

如果使用fastdwt：

importnumpyasnpfromfastdtwimportfastdtwfromscipy.spatial.distanceimporteuclidean A=np.array([[1],[2],[3],[4],[5]])B=np.array([[1],[2],[2],[3],[4],[5]])distance,path=fastdtw(A,B,dist=euclidean)print(distance)print(path)