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

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