algorithm
동적 시간 왜곡
수색…
동적 시간 왜곡 소개
동적 시간 왜곡 (DTW)은 속도가 다를 수있는 두 시간 순서 간의 유사성을 측정하기위한 알고리즘입니다. 예를 들어 한 사람이 다른 사람보다 더 빨리 걷고 있더라도 DTW를 사용하여 보행 중 유사점을 감지 할 수 있으며 관찰 중에 가속 및 감속이있는 경우에도 유사점을 DTW를 사용하여 감지 할 수 있습니다. 사전 녹음 된 샘플 음성보다 빨리 또는 느리게 말을해도 샘플 음성 명령을 다른 명령과 일치시키는 데 사용할 수 있습니다. DTW는 비디오, 오디오 및 그래픽 데이터의 시간 순서에 적용 할 수 있습니다. 실제로 선형 순서로 변환 할 수있는 모든 데이터는 DTW로 분석 할 수 있습니다.
일반적으로 DTW는 특정 제한 사항을 사용하여 주어진 두 시퀀스 간의 최적 일치를 계산하는 방법입니다. 그러나 여기서 더 간단한 점을 고집합시다. 두 개의 음성 시퀀스 인 Sample 과 Test 가 있고이 두 시퀀스가 일치하는지 확인하고 싶습니다. 여기서 음성 시퀀스는 변환 된 음성 신호입니다. 그것은 당신이 말한 단어를 나타내는 당신의 목소리의 진폭 또는 빈도 일 수 있습니다. 가정 해 봅시다.
Sample = {1, 2, 3, 5, 5, 5, 6}
Test = {1, 1, 2, 2, 3, 5}
이 두 시퀀스 간의 최적의 일치를 찾고자합니다.
처음에는 두 점 d (x, y) 사이의 거리를 정의합니다. 여기서 x 와 y 는 두 점을 나타냅니다. 방해,
d(x, y) = |x - y| //absolute difference
이 두 시퀀스를 사용하여 2D 매트릭스 테이블 을 만듭니다. 샘플의 각 포인트와 테스트 포인트 사이의 거리를 계산하고 이들 사이의 최적의 일치를 찾습니다.
+------+------+------+------+------+------+------+------+
| | 0 | 1 | 1 | 2 | 2 | 3 | 5 |
+------+------+------+------+------+------+------+------+
| 0 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 1 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 2 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 3 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | | | | | | | |
+------+------+------+------+------+------+------+------+
| 6 | | | | | | | |
+------+------+------+------+------+------+------+------+
여기서 Table [i] [j] 는 우리가 이전에 관찰 한 모든 최적의 거리를 고려하여 시퀀스를 Sample [i] 와 Test [j] 까지 고려하면 두 시퀀스 간의 최적 거리를 나타냅니다.
첫 번째 행에 대해 Sample 에서 값을 가져 오지 않으면이 값과 Test 값 사이의 거리가 무한대가 됩니다. 그래서 첫 번째 행에 무한대 를 넣습니다. 첫 번째 열에 대해서도 마찬가지입니다. Test 에서 아무 값도 취하지 않으면이 값과 Sample 사이의 거리도 무한대가됩니다. 그리고 0과 0 사이의 거리가 단순히 0이됩니다. 우리는,
+------+------+------+------+------+------+------+------+
| | 0 | 1 | 1 | 2 | 2 | 3 | 5 |
+------+------+------+------+------+------+------+------+
| 0 | 0 | inf | inf | inf | inf | inf | inf |
+------+------+------+------+------+------+------+------+
| 1 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
| 2 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
| 3 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
| 5 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
| 6 | inf | | | | | | |
+------+------+------+------+------+------+------+------+
이제 각 단계마다 관심있는 각 점 사이의 거리를 고려하여 지금까지 발견 한 최소 거리로 추가합니다. 이것은 우리가 그 위치까지 두 서열의 최적 거리를 줄 것입니다. 우리의 공식은,
Table[i][j] := d(i, j) + min(Table[i-1][j], Table[i-1][j-1], Table[i][j-1])
첫 번째 경우, d (1,1) = 0 , Table [0] [0] 은 최소값을 나타냅니다. 따라서 Table [1] [1] 의 값은 0 + 0 = 0이 됩니다. 두 번째 경우, d (1, 2) = 0 . 표 [1] [1] 은 최소값을 나타냅니다. 값은 다음과 같습니다. Table [1] [2] = 0 + 0 = 0 . 이 방법을 계속 사용하면 작업이 완료된 후 표가 다음과 같이 표시됩니다.
+------+------+------+------+------+------+------+------+
| | 0 | 1 | 1 | 2 | 2 | 3 | 5 |
+------+------+------+------+------+------+------+------+
| 0 | 0 | inf | inf | inf | inf | inf | inf |
+------+------+------+------+------+------+------+------+
| 1 | inf | 0 | 0 | 1 | 2 | 4 | 8 |
+------+------+------+------+------+------+------+------+
| 2 | inf | 1 | 1 | 0 | 0 | 1 | 4 |
+------+------+------+------+------+------+------+------+
| 3 | inf | 3 | 3 | 1 | 1 | 0 | 2 |
+------+------+------+------+------+------+------+------+
| 5 | inf | 7 | 7 | 4 | 4 | 2 | 0 |
+------+------+------+------+------+------+------+------+
| 5 | inf | 11 | 11 | 7 | 7 | 4 | 0 |
+------+------+------+------+------+------+------+------+
| 5 | inf | 15 | 15 | 10 | 10 | 6 | 0 |
+------+------+------+------+------+------+------+------+
| 6 | inf | 20 | 20 | 14 | 14 | 9 | 1 |
+------+------+------+------+------+------+------+------+
표 [7] [6] 의 값은 주어진 두 시퀀스 간의 최대 거리를 나타냅니다. 여기서 1은 샘플들 사이의 최대 거리를 나타내고, 시험은 1이다.
이제 마지막 점에서 출발점 (0, 0) 으로 되돌아 가면 가로, 세로, 대각선으로 이동하는 긴 선이 생깁니다. 우리의 역 추적 절차는 다음과 같습니다 :
if Table[i-1][j-1] <= Table[i-1][j] and Table[i-1][j-1] <= Table[i][j-1]
i := i - 1
j := j - 1
else if Table[i-1][j] <= Table[i-1][j-1] and Table[i-1][j] <= Table[i][j-1]
i := i - 1
else
j := j - 1
end if
우리가 도달 할 때까지 (0, 0) 이 작업을 계속할 것입니다. 각 이동에는 고유 한 의미가 있습니다.
- 수평 이동은 삭제를 나타냅니다. 이는 우리의 테스트 시퀀스가이 간격 동안 가속화되었음을 의미합니다.
- 수직 이동은 삽입을 나타냅니다. 이것은 테스트 시퀀스가이 간격 동안 감속되었음을 의미합니다.
- 대각선 이동은 일치를 나타냅니다. 이 기간 동안 테스트 와 샘플 은 동일했습니다.
우리의 의사 코드는 다음과 같습니다.
Procedure DTW(Sample, Test):
n := Sample.length
m := Test.length
Create Table[n + 1][m + 1]
for i from 1 to n
Table[i][0] := infinity
end for
for i from 1 to m
Table[0][i] := infinity
end for
Table[0][0] := 0
for i from 1 to n
for j from 1 to m
Table[i][j] := d(Sample[i], Test[j])
+ minimum(Table[i-1][j-1], //match
Table[i][j-1], //insertion
Table[i-1][j]) //deletion
end for
end for
Return Table[n + 1][m + 1]
지역 제약 조건을 추가 할 수도 있습니다. 즉, Sample[i] 가 Test[j] 와 일치하면 |i - j| 윈도우 매개 변수 인 w 보다 크지 않습니다.
복잡성:
DTW 계산의 복잡성은 O (m * n)입니다. 여기서 m 과 n 은 각 시퀀스의 길이를 나타냅니다. DTW를 계산하기위한보다 빠른 기술에는 PrunedDTW, SparseDTW 및 FastDTW가 포함됩니다.
응용 분야 :
- 음성 인식
- 상관 전력 분석
