수색…


동적 시간 왜곡 소개

동적 시간 왜곡 (DTW)은 속도가 다를 수있는 두 시간 순서 간의 유사성을 측정하기위한 알고리즘입니다. 예를 들어 한 사람이 다른 사람보다 더 빨리 걷고 있더라도 DTW를 사용하여 보행 중 유사점을 감지 할 수 있으며 관찰 중에 가속 및 감속이있는 경우에도 유사점을 DTW를 사용하여 감지 할 수 있습니다. 사전 녹음 된 샘플 음성보다 빨리 또는 느리게 말을해도 샘플 음성 명령을 다른 명령과 일치시키는 데 사용할 수 있습니다. DTW는 비디오, 오디오 및 그래픽 데이터의 시간 순서에 적용 할 수 있습니다. 실제로 선형 순서로 변환 할 수있는 모든 데이터는 DTW로 분석 할 수 있습니다.

일반적으로 DTW는 특정 제한 사항을 사용하여 주어진 두 시퀀스 간의 최적 일치를 계산하는 방법입니다. 그러나 여기서 더 간단한 점을 고집합시다. 두 개의 음성 시퀀스 인 SampleTest 가 있고이 두 시퀀스가 ​​일치하는지 확인하고 싶습니다. 여기서 음성 시퀀스는 변환 된 음성 신호입니다. 그것은 당신이 말한 단어를 나타내는 당신의 목소리의 진폭 또는 빈도 일 수 있습니다. 가정 해 봅시다.

Sample = {1, 2, 3, 5, 5, 5, 6}
Test   = {1, 1, 2, 2, 3, 5}

이 두 시퀀스 간의 최적의 일치를 찾고자합니다.

처음에는 두 점 d (x, y) 사이의 거리를 정의합니다. 여기서 xy 는 두 점을 나타냅니다. 방해,

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)입니다. 여기서 mn 은 각 시퀀스의 길이를 나타냅니다. DTW를 계산하기위한보다 빠른 기술에는 PrunedDTW, SparseDTW 및 FastDTW가 포함됩니다.

응용 분야 :

  • 음성 인식
  • 상관 전력 분석


Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow