Bagaimana mengukur tingkat jarak pada kasus diatas?
Sakoe,H. and Chiba, S. Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans. on Acoust., Speech, and Signal Process., ASSP 26, 43-49 (1978).
Gambar kiri (non elastis) : Jarak manapun (Euclidean, Manhattan,…) yang menyelaraskan titik (i) pada satu seri waktu dengan titik ke (i) di sisi yang lain akan menghasilkan skor kesamaan yang buruk.
Gambar kanan (elastis): Perataan non-linear (elastis) menghasilkan ukuran kesamaan yang lebih intuitif, memungkinkan bentuk-bentuk serupa untuk dicocokkan bahkan jika mereka keluar (beda fase) dalam domain waktu.
Fungsi Dynamic Time Warping
Time-Normalized Distance Measure
Perhitungan DTW
Membuat 2 sinyal yang akan dibandingkan, kita akan mengukur jarak/kemiripan 2 sinyal dibawah ini yang mempunyai time yang berbedax = [1, 1, 2, 3, 2, 0];
y = [0, 1, 1, 2, 3, 2, 1];
Kita akan menghitung distances menggunakan eucledian distancesdistances = zeros(length(y),length(x));
for i=1:length(y)
for j=1:length(x)
distances(i,j) = (y(i)-x(j))^2;
end
end
menghasilkan
distances =
1 1 4 9 4 0
0 0 1 4 1 1
0 0 1 4 1 1
1 1 0 1 0 4
4 4 1 0 1 9
1 1 0 1 0 4
0 0 1 4 1 1
Menghitung accumulated_cost mulai dari baris pertama
accumulated_cost = zeros(length(y),length(x));
accumulated_cost(1,1) = distances(1,1);
for i=2:length(x)
accumulated_cost(1,i) = distances(1,i) + accumulated_cost(1, i-1);
end
for i=2:length(y)
accumulated_cost(i,1) = distances(i,1) + accumulated_cost(i-1,1);
end
Menghitung untuk semua element (yaitu baris dan kolom ke 2) yang lain, dengan rumus berikut
Accumulated Cost (D(i,j))=min{D(i−1,j−1),D(i−1,j),D(i,j−1)}+distance(i,j)
for i=2:length(y)
for j=2:length(x)
accumulated_cost(i, j) = min([accumulated_cost(i-1, j-1), accumulated_cost(i-1, j), accumulated_cost(i, j-1)]) + distances(i, j);
end
end

Mencari path optimal : sekarang perlu menemukan jalan yang meminimalkan jarak yang kita lakukan dengan teknik backtracking (mundur). Prosedur backtracking cukup sederhana dan melibatkan upaya untuk kembali dari titik terakhir (M, N) dan menemukan tempat mana yang akan dicapai (dengan meminimalkan biaya) dan melakukan ini dengan cara berulang.
path(1,:) = [length(x), length(y)];
i = length(y);
j = length(x);
index = 2;
while i>1 && j>1
if i==1
j = j - 1;
elseif j==1
i = i - 1;
else
minimal = min([accumulated_cost(i-1, j-1), accumulated_cost(i-1, j), accumulated_cost(i, j-1)]);
if accumulated_cost(i-1, j) == minimal
i = i - 1;
elseif accumulated_cost(i, j-1) == minimal
j = j - 1;
else
i = i - 1;
j = j- 1;
end
end
path(index,:)=[j, i];
index = index+1;
end
path(index,:)=[1,1];
menghasilkan
path =
6 7
5 6
4 5
3 4
2 3
2 2
1 2
1 1
Kemudian menghitung cost dari path (index distances) yang telah diketahui
cost = 0;
for i=1:length(path)
cost = cost+distances(path(i,2),path(i,1));
end
menghasilkan
cost = 2
No comments:
Post a Comment