Tìm kiếm âm nhạc theo nội dung sử dụng đặc trưng tần số cơ bản F0 và giải thuật thời gian động DTW

Pitch, 
cửa sổ âm thanh nên chứa ít nhất hai chu kỳ 
cao độ (N >2/F0). 
Kỹ thuật phân lớp dùng thời gian động 
DTW (Dynamic Time Warping) 
Cho chuỗi đầu vào  Lwwww ,..., 21 có độ 
dài L và có chuỗi vector đặc tính 
 TxxxX ,..., 21 , nhiệm vụ của hệ thống là 
phải nhận dạng chuỗi âm đầu vào và trong 
quá trình xử lý cần phải giảm thiểu tối đa các 
sai số quyết định. Mỗi tín hiệu đầu vào Wl sẽ 
đƣợc so sánh với các mẫu Yl. Mỗi Yl là chuỗi 
các vector đặc tính của tín hiệu Wl . Nhằm 
tăng khả năng nhận dạng, mỗi tín hiệu có một 
tập hợp các mẫu khác nhau: 
lMll
YY ,1, ,..., . 
),(minminarg ,
*
ml
ml
YXDl  (2 ) 
Nhƣ vậy Wl* là phù hợp nhất với mẫu Yl tìm 
đƣợc. 
Khoảng cách D(X,Y) giữa dữ liệu đầu vào và 
dữ liệu mẫu Y=y1.ys có độ dài thời gian 
khác nhau S  T đƣợc xác định bằng tổng các 
khoảng cách cục bộ ),( jiij yxdd  trên cả 
đƣờng đi của quá trình biến dạng thời gian. 
Khoảng cách tích luỹ 
)...,...( 11 jiij yyxxDD  đƣợc xác định theo 
công thức (3) 
 






 ijjijiji dDDD 1,,11,1 ,,min
0
I=J=0
I>0, J>0
Kh¸c
Và khoảng cách tổng D(X,Y)=DTS. 
Giả sử cho hai chuỗi vec tơ tƣơng ứng với 
mẫu tín hiệu là  Iaaaaa ,....,, 321

 và 
 Jbbbbb ,....,, 321

. Cho rằng tín hiệu mẫu 
a có chiều dài lớn hơn mẫu 

b tức là giá trị 
(I > J). Thuật toán sẽ thực hiện việc tìm 
đƣờng đi tối ƣu của chuỗi b theo chuỗi a (tức 
là các vị trí khác nhau giữa hai chuỗi theo 
thời gian) sao cho tổng chênh lệch giữa hai 
chuỗi vec tơ là nhỏ nhất. 
Để thực hiện đƣợc điều này ta dùng thuật toán 
dùng ma trận lƣới các điểm H2 
Hình 2. Ma trận lƣới các điểm 
Hai chuỗi véc tơ sẽ tƣơng ứng với hai cạnh 
của ma trận. Giả sử, véc tơ a theo trục x và 
véc tơ b theo trục y. Các nút của ma trận 
tƣơng ứng với khoảng cách tính đƣợc của hai 
chuỗi véc tơ tại các thời điểm thứ i của véc tơ 
a tƣơng ứng thời điểm thứ j của véc tơ b 
tƣơng ứng nút (i,j). Nhƣ vậy, đƣờng đi tối ƣu 
trong ma trận sẽ có dạng nhƣ hình 3 
Phùng Thị Thu Hiền và cs Tạp chí KHOA HỌC & CÔNG NGHỆ 61(12/2): 55 - 59 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  
57 
Hình 3. Hình dạng đƣờng đi trong ma trận 
Việc xác định đƣờng đi tối ƣu trong ma trận 
lƣới đƣợc thực hiện sao tổng khoảng cách sai 
lệch giữa các cặp véc tơ của hai chuỗi là nhỏ 
nhất. Ký hiệu, d(i,j) là độ chênh lệch của hai 
véc tơ a và b tại thời điểm i và j tƣơng ứng. 
Yêu cầu của thuật toán DTW cho hai chuỗi 
vec tơ bất kỳ là cùng bắt đầu tại các vị trí 
(0,0) và kết thúc tại vị trí (I,J). Giá trị tại nút 
(0,0) xác định bằng 0. 
Đƣờng đi đƣợc xác định theo các cặp nút liên 
tiếp (ik-1,jk-1)  (ik,jk) . Dùng ký hiệu ik để 
biểu diễn chỉ số của véc tơ a tại thời điểm k 
và jk là chỉ số của véc tơ b tại thời điểm k. 
Nhƣ vậy tổng khoảng cách giữa hai chuỗi véc 
tơ là : 
),(),(),( 11 kkkkkk jidjiDjiD   (4) 
Việc tìm giá trị min D(i,j) theo công thức sau: 
  ),(),(min),( 11
*
kkkkkk jidjiDjiD   
 (5) 
Một số bắt buộc của DTW: 
- Chỉ số của i phải tăng đều tức là : 
ik - ik-1 =1 
- Chỉ số của j tăng theo i với điều kiện: 
jk -jk-1  0 
Giới hạn của đƣờng đi không thể tuỳ ý đƣợc 
vì nhƣ thế nó sẽ gây ra kết quả sai lệch và làm 
tăng khối lƣợng tính toán (nếu xét trên toàn 
bộ ma trận điểm). Vì vậy, cần phải giới hạn 
phạm vi của đƣờng đi sao cho việc tính toán 
giảm và độ chính xác cao. Phạm vi cho 
đƣờng đi đƣợc chọn nhƣ hình vẽ 4: 
 Hình 4. Phạm vi cho đƣờng đi 
Luật đƣờng đi đƣợc lựa chọn theo nhƣ hình 5. 
Hình 5. Luật đƣờng đi 
Giả sử vị trí hiện tại đang ở thời điểm ik-1 và 
điểm đi tiếp là ik. Nhƣ vậy các giá trị jk có thể 
là jk, jk+1, jk+2 tƣơng ứng với các mũi tên trên 
ma trận. 
KẾT QUẢ THỰC NGHIỆM 
Chuẩn bị dữ liệu 
Dữ liệu bao gồm 20 bài hát thiếu nhi nổi tiếng 
thế giới đƣợc download từ 
g4public/QBSH-corpus/ . Trong các cấu trúc 
file âm thanh thì MIDI là định dạng file đơn 
giản, kích cỡ nhỏ gọn nhƣng vẫn biểu diễn 
đƣợc giai điệu âm nhạc. Do đó, trong bƣớc 
huấn luyện, chƣơng trình sử dụng 20 bản 
nhạc định dạng MIDI. PCM Wave là chuẩn 
mã hóa âm thanh đƣợc sử dụng khá phổ biến 
trong các hệ cơ sở dữ liệu âm nhạc, do vậy 
khi tìm kiếm chƣơng trình thử nghiệm trên 20 






 


km
m
mm jid
0
),(min
Phùng Thị Thu Hiền và cs Tạp chí KHOA HỌC & CÔNG NGHỆ 61(12/2): 55 - 59 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  
58 
file âm thanh PCM Wave có tần số lấy mẫu 8 
KHz, mã hóa 8 bít / mẫu, thu từ các điệu ngân 
nga không lời (humming) hoặc các đoạn hát 
không nhạc (singing) với giai điệu tƣơng ứng 
với 20 bản nhạc MIDI đã huấn luyện. 
Các tham số thực nghiệm 
Cao độ Pitch đƣợc tính theo phƣơng pháp tự 
tƣơng quan ACF với các tham số: kích cỡ 
khung là 256 ms, không chồng lấp. Sau khi 
tính Pitch bằng hàm ACF (AutoCorrelation 
Function), pitch đƣợc làm trơn bằng lọc trung 
vị. Phƣơng pháp phân lớp sử dụng thuật toán 
thời gian động DTW tiến hành so sánh chuỗi 
Pitch đầu vào cần tìm kiếm tính từ file Wave 
với lần lƣợt các chuỗi Pitch của các file MIDI 
trong cơ sở dữ liệu. Thuật toán thời gian động 
cho phép so sánh 2 chuỗi Pitch có độ dài khác 
nhau với sai số nhỏ nhất. Độ tƣơng tự của 2 
chuỗi pitch sau đó đƣợc tính toán bằng khoảng 
cách Euclid để tìm ra chuỗi phù hợp nhất. 
Kết quả thực nghiệm và đánh giá 
Phƣơng pháp trích đặc trƣng giai điệu dùng 
tham số cao độ Pitch (hay tần số cơ bản F0) 
sử dụng đặc trƣng các giá trị cao độ và sự 
biến đổi cao độ làm tham số so sánh. Do vậy, 
hệ thống không yêu cầu khắt khe về mẫu đầu 
vào và có thể tìm kiếm đƣợc một tập nhiều 
kết quả đầu ra có giai điệu tƣơng tự. Ƣu điểm 
của hệ thống này là có thể tìm đƣợc nhiều kết 
quả dựa trên giai điệu mà chỉ cần ngƣời sử 
dụng cung cấp giai điệu bài hát một cách 
tƣơng đối nhƣ hát thử không nhạc, đánh thử 
một đoạn nhạc hay ngân nga giai điệu không 
có lời (humming). Nhƣợc điểm của hệ thống 
này là kết quả tìm kiếm có thể thiếu chính xác 
do một số bài hát khác nhau có thể có những 
phần nhỏ giai điệu tƣơng tự nhau. 
Trong chƣơng trình thực nghiệm, kết quả 
nhận dạng đúng sau 20 lần là 100%. Kết quả 
này cao hơn kết quả đã công bố trong [8] và 
[10] dù dùng cùng thuật toán. Lý do có thể do 
chƣơng trình demo mới thử nghiệm trên bộ 
cơ sở dữ liệu rất nhỏ. Tỷ lệ nhận dạng sẽ giảm 
xuống khi dùng cơ sở dữ liệu lớn hơn (đặc 
biệt khi trong cơ sở dữ liệu có các bài hát có 
những phần tƣơng tự nhau), tỷ lệ nhận dạng 
và tìm kiếm đúng cũng sẽ giảm xuống khi độ 
dài mẫu âm thanh đầu vào là nhỏ. 
Về mặt thời gian, thời gian tìm kiếm cho mỗi 
file Wave (dài khoảng 1 phút) là xấp xỉ 0.2 s 
với điều kiện đã huấn luyện trƣớc. Thời gian 
này là chấp nhận đƣợc với ngƣời sử dụng. 
Thời gian tìm kiếm trong [8] là lớn hơn do 
thực nghiệm trên cơ sở dữ liệu âm nhạc lớn. 
Chƣơng trình mô phỏng đƣợc xây dựng trên 
phần mềm matlab: 
Hình 6. Kết quả chạy chƣơng trình 
Hƣớng phát triển 
Trƣớc hết cần xây dựng một cơ sở dữ liệu âm 
nhạc đủ lớn để thử nghiệm. Từ đó sẽ đánh giá 
đƣợc độ chính xác, hiệu quả của các phƣơng 
pháp tìm kiếm và có thể đề xuất các phƣơng 
pháp cải tiến thao tác trích đặc trƣng và phân 
lớp của hệ thống tìm kiếm. 
Hƣớng nghiên cứu tiếp theo cũng sẽ là tìm 
hiểu sâu hơn về các phƣơng pháp phân lớp dữ 
liệu triển vọng nhƣ dùng mạng Neural, giải 
thuật di truyền GA, mô hình Markov ẩn 
HMM, 
TÀI LIỆU THAM KHẢO 
[1]. E.Riskin and R.Gray, “A greedy tree growing 
algorithm for the design of variable rate vector 
quantizers”, IEEE Trans. On Sig.Proc, Nov 1991 
[2]. J.-S. Roger Jang, Hong-Ru Lee, 
"Hierarchical Filtering Method for Content-based 
Music Retrieval via Acoustic Input", The 9th 
ACM Multimedia Conference, PP. 401-410, 
Ottawa, Ontario, Canada, September 2001. 
Phùng Thị Thu Hiền và cs Tạp chí KHOA HỌC & CÔNG NGHỆ 61(12/2): 55 - 59 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  
59 
[3]. Beth Logan and Ariel Salomon, “A Music 
Similarity Function Based on Signal Analysis”, 
Cambridge Research Laboratory. 
[4]. S.Blackburn and D. De Roure, “A tool for 
content based navigation of music”, in ACM 
Multimedia ,1998. 
[5]. R. Mc Nab, L. Smith, I. Witten, C.Henderson, 
and S.Cunningham, “Towards the digital music 
library: Tune retrieval from acoustic input,” in 
Digital Libraries 1996, 1996, pp.11-18 
[6]. A.Ghias, J.Logan, D. Chamberlin and 
B.Smith, “Query by humming,” in ACM 
Multimedia, 1995 . 
[7]. M Goto, “A predominant-F0 estimation 
method for CD recordings: MAP estimation using 
EM algorithm for adaptive tone models,” in Proc. 
ICASSP, 2001 
[8]. Beth Logan and Stephen Chu, “Music 
Summarization Using Key Phrases”, Cambridge 
Research Laboratories 
[9]. J.T. Foote, “Content-based retrieval of Music 
and Audio,” in SPIE, 1997, p.p 138- 147 
[10]. J.-S. Roger Jang, Hong-Ru Lee, 
"Hierarchical Filtering Method for Content-based 
Music Retrieval via Acoustic Input", The 9th 
ACM Multimedia Conference, PP. 401-410, 
Ottawa, Ontario, Canada, September 2001. 
SUMMARY 
USING FUNDAMENTAL FREQUENCY AND ALGORITHM DYNAMIC TIME 
WARPING (DTW) TO SEARCH CONTEND MUSIC 
Phung Thi Thu Hien
1
, Thai Quang Vinh
2
, Phung Trung Nghia
3 
, Le Tuan Anh
4 
1University of Technology, 
 2Academy of Information Technology - Vietnam Academy of Science and Technology 
3Japan Advanced Institute of Science and Technology 
, 4Faculty of information Technology- Thai Nguyen University 
Song searching in a database is interesting field which attract many researchers recently. Music 
searching in current database is usually based on text query. In a huge multimedia database, content-
based music searching becomes incredible. 
This paper presents the content-based music searching method using F0 and the DTW algorithm. 
Experimental results show that this is an effective method and need to continue researching. 
Keywords: Dynamic Time Warping, Pitch. 
 Tel: 0986060545, Email: pthientng@gmail.com