>  기사  >  DTW 알고리즘이란 무엇입니까?

DTW 알고리즘이란 무엇입니까?

coldplay.xixi
coldplay.xixi원래의
2020-12-18 10:08:5411064검색

dtw 알고리즘은 동적 프로그래밍 DP의 아이디어를 기반으로 하는 동적 시간 왜곡 알고리즘을 의미합니다. 이는 두 시계열, 특히 길이가 다른 시퀀스의 유사성을 계산하는 동적 프로그래밍 알고리즘입니다. 서로 다른 발음 길이를 가진 템플릿의 일치 문제는 음성 인식의 더 초기의 고전적인 알고리즘입니다. dtw 알고리즘은 고립된 단어 음성 인식, 동작 인식, 데이터 마이닝 및 정보 검색과 같은 시계열 데이터에 주로 사용됩니다.

DTW 알고리즘이란 무엇입니까?

이 튜토리얼의 운영 환경: Windows 7 시스템, Dell G3 컴퓨터.

시계열 데이터에는 여러 유사성 또는 거리 함수가 있으며 그 중 가장 두드러지는 것은 DTW입니다. 고립된 단어 음성 인식에서 가장 간단하고 효과적인 방법은 DTW(Dynamic Time Warping) 알고리즘을 사용하는 것입니다. 이 알고리즘은 DP(동적 프로그래밍) 아이디어를 기반으로 하며 서로 다른 발음의 템플릿 매칭 문제를 해결합니다. 음성 인식 분야의 더 초기의 더 고전적인 알고리즘이며 고립된 단어 인식에 사용됩니다.

DTW(동적 시간 워핑) 동적 시간 워핑 알고리즘은 두 시계열, 특히 길이가 다른 시퀀스의 유사성을 계산하는 동적 프로그래밍 알고리즘입니다. 고립된 단어 음성 인식, 동작 인식, 데이터 마이닝, 정보 검색 등 시계열 데이터에 주로 사용됩니다.

HMM 알고리즘은 학습 단계에서 많은 양의 음성 데이터를 제공해야 하며 반복 계산을 통해 모델 매개변수를 얻을 수 있는 반면, DTW 알고리즘의 학습에는 추가 계산이 거의 필요하지 않습니다. 따라서 DTW 알고리즘은 여전히 ​​고립된 단어 음성 인식에 널리 사용됩니다.

훈련 및 템플릿 구축 단계에서든 인식 단계에서든 먼저 끝점 알고리즘을 사용하여 음성의 시작점과 끝점을 결정합니다. 템플릿 라이브러리에 저장된 각 항목을 참조 템플릿이라고 합니다. 참조 템플릿은 R={R(1), R(2),..., R(m),..., R(M)으로 표현될 수 있습니다. }, m은 훈련 음성 프레임의 타이밍 번호, m=1은 시작 음성 프레임, m=M은 종료 음성 프레임이므로 M은 템플릿에 포함된 전체 음성 프레임 수, R( m)은 m번째 프레임의 음성 특징 벡터입니다. 인식하고자 하는 입력 입력 음성을 테스트 템플릿이라고 하며, 이는 T = {T(1), T(2), ..., T(n), ..., T(N)}로 표현할 수 있으며, n은 테스트 음성입니다. 프레임의 타이밍 레이블, n=1은 시작 음성 프레임, n=N은 종료 음성 프레임이므로 N은 템플릿에 포함된 음성 프레임의 총 개수이고, T(n)은 n번째 프레임의 음성 특징 벡터입니다. 참조 템플릿과 테스트 템플릿은 일반적으로 동일한 유형의 특징 벡터(예: MFCC, LPC 계수), 동일한 프레임 길이, 동일한 창 함수 및 동일한 프레임 이동을 사용합니다.

테스트 템플릿과 참조 템플릿을 각각 T와 R로 표현한다고 가정하면, 두 템플릿 사이의 거리는 D[T, R]로 계산될 수 있습니다. 이 왜곡 거리를 계산하려면 T와 R의 해당 프레임 사이의 거리부터 시작하세요. n과 m을 각각 T와 R에서 임의로 선택한 프레임 번호라고 하고, d[T(n),R(m)]은 이 두 프레임의 특징 벡터 사이의 거리를 나타냅니다. 거리 함수는 사용되는 실제 거리 측정법에 따라 달라지며 일반적으로 DTW 알고리즘에서는 유클리드 거리가 사용됩니다.

N=M이면 직접 계산할 수 있으며, 그렇지 않으면 T(n)과 R(m)을 정렬하는 것을 고려해야 합니다. 정렬은 선형 확장 방법을 사용할 수 있습니다. N

2차원 직각 좌표계에서 테스트 템플릿의 각 프레임 번호 n=1~N을 가로축에 표시하고, 참조 템플릿의 각 프레임 번호 m=1~M을 세로축에 표시하면, 프레임 번호를 나타내는 이러한 정수 좌표는 수직선과 수평선을 그려서 네트워크를 형성할 수 있습니다. 네트워크의 각 교차점(n, m)은 테스트 모드에서 특정 프레임의 교차점을 나타냅니다. DP 알고리즘은 이 네트워크의 여러 그리드 포인트를 통해 경로를 찾는 것으로 요약될 수 있습니다. 경로를 통과하는 그리드 포인트는 테스트 및 참조 템플릿에서 계산된 프레임 번호입니다. 경로는 임의로 선택되지 않습니다. 우선 모든 음성의 발음 속도는 변경될 수 있지만 해당 부분의 순서는 변경할 수 없습니다. 따라서 선택한 경로는 왼쪽 하단에서 시작하여 오른쪽 상단에서 끝나야 합니다.

설명 이 경로에 대해 경로를 통과하는 모든 그리드 점은 (n1, m1),..., (ni, mj),..., (nN, mm)라고 가정합니다. 여기서 (n1, m1 ) = (1, 1), (nN,mM)=(N,M). 경로는 m = Oslash;(n) 함수로 설명할 수 있습니다. 여기서 n =i, i=1, 2,...,N, Ø(1)=1, Ø(N)=M입니다. 경로가 너무 기울어지는 것을 방지하기 위해 기울기를 0.5~2 범위로 제한할 수 있습니다. 경로가 이미 그리드 포인트(n, m)를 통과한 경우 다음 그리드 포인트(n, m)가 됩니다. ) 통과는 다음 세 가지만 가능합니다. 사례 1:

(n ,m )=(n +1,m)
(n ,m )=(n +1,m +1)
(n ,m )=(n ,m+1 )

r을 사용하여 위의 세 가지 제약 조건을 나타냅니다. 최적의 경로를 찾는 문제는 제약 조건 r이 만족될 때 최적의 경로 함수 m =Ø(n)을 찾는 것으로 축소될 수 있으므로 경로를 따라 누적된 거리가 최소값에 도달합니다. 즉:

搜索该路径的方法如下:搜索从(n, m)点出发,可以展开若干条满足ŋ的路径,假设可计算每条路径达到(n, m)点时的总的积累距离,具有最小累积距离者即为最佳路径。易于证明,限定范围的任一格点(n, m)只可能有一条搜索路径通过。对于(n, m),其可达到该格点的前一个格点只可能是(n-1, m)、(n-1, m -1)和(n, m-1),那么(n, m)一定选择这3个距离之路径延伸而通过(n, m),这时此路径的积累距离为:

D[(n, m)]=d[T(n),R(m)]+min{D(n-1,m),D(n-1,m-1),D(n,m-1)}

这样可以从(n ,m )=(1,1)出发搜索(n ,m ),对每一个(n ,m )都存储相应的距离,这个距离是当前格点的匹配距离与前一个累计距离最小的格点(按照设定的斜率在三个格点中进行比较)。搜索到(n ,m )时,只保留一条最佳路径。如果有必要的话,通过逐点向前寻找就可以求得整条路径。这套DP算法便是DTW算法。

DTW算法可以直接按上面描述来实现,即分配两个N×M的矩阵,分别为积累距离矩阵D和帧匹配距离矩阵d,其中帧匹配距离矩阵d(i,j)的值为测试模板的第i帧与参考模板的第j帧间的距离。D(N,M)即为最佳匹配路径所对应的匹配距离

更多相关知识,请访问常见问题栏目!

위 내용은 DTW 알고리즘이란 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.