Tìm kiếm âm nhạc theo nội dung sử dụng đặc trưng đường bao phổ và phương pháp phân cụm K-means
TÌM KIẾM ÂM NHẠC THEO NỘI DUNG SỬ DỤNG ĐẶC TRƢNG ĐƢỜNG BAO PHỔ
VÀ PHƢƠNG PHÁP PHÂN CỤM K-MEANS
Phùng Thị Thu Hiền1, Vũ Tất Thắng2,
Thái Quang Vinh2, Nguyễn Văn Huy1
1Trường Đại học Kỹ thuật Công nghiệp – ĐH Thái Nguyên,
2Viện Công nghệ thông tin - Viện KHCN Việt nam
TÓM TẮT
Trong các cơ sở dữ liệu đa phương tiện lớn vấn đề tìm kiếm âm nhạc theo nội dung rất quan trọng.
Tìm kiếm âm nhạc trong các cơ sở dữ liệu hiện tại thường dựa 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 điểm. Nhiều khi người dùng có thể
không nhớ được các từ khóa text của bài hát như tên bài hát, tác giả, ca sĩ hoặc lời bài hát. Tìm kiếm
âm nhạc theo nội dung khắc phục được những nhược điểm này. Trong cách tiếp cận truyền thống,
các vector đặc trưng của tín hiệu âm thanh được xây dựng từ các đặc trưng vật lý của âm thanh
như độ to, độ cao, năng lượng, phổ tần số,… Gần đây, một số nghiên cứu trên thế giới tập trung
vào một cách tiếp cận khác, trong đó áp dụng các kiến thức về xử lý tín hiệu âm thanh, về phân
tích mô hình tạo âm thanh, mô hình cảm thụ âm thanh của con người có thể giúp việc tính toán
vector đặc trưng âm thanh được chính xác và hạn chế tối đa thông tin dư thừa. Bài báo này trình
bày phương pháp tìm kiếm âm nhạc theo nội dung dùng đặc trưng đường bao phổ Mel Cepstral, được
xây dựng dựa trên mô hình cảm thụ âm thanh của con ngườ, và thuật toán phân cụm K-means.
Từ khóa: Vector đặc trưng, Mel Cepstral, K-mean, MFCC.
dụng như là một hệ số cơ sở trong xử lý tiếng
nói. Những giá trị khác thể hiện một hệ thống
chỉ số dựa trên việc kết nối các đặc trưng như
là độ cao, độ to hoặc hệ số tần số Mel [9].
Foote [9] đã thiết kế một hệ thống chỉ mục âm
nhạc dựa trên biểu đồ các đặc trưng MFCC
xuất phát từ vector lượng tử hóa. Beth Logan
[3] đã thực hiện theo cách của Foote sử dụng
các biểu đồ của các đặc trưng MFCC nhưng
sử dụng thêm giải thuật phân cụm K-means.
Phương thức của ông thực hiện sau kỹ thuật
phục hồi âm thanh thực hiện bởi Liu và
Huang [11].
ĐẶT VẤN ĐỀ
Tìm kiếm âm nhạc theo nội dung là một lĩnh
vực nghiên cứu mới và được nhiều nhà
nghiên cứu quan tâm. Hiện có một số phương
thức đã được áp dụng tìm kiếm âm nhạc theo
nội dung.
Theo Bel Logan [3] cấu trúc âm thanh của âm
nhạc là quan trọng. Vì vậy cần phải có một hệ
thống nhận biết độ tương tự âm thanh theo
cách gần giống như hệ thống nghe của con
người, và hệ thống thính giác của con người
dễ dàng thu và nhận dạng các nhóm âm thanh
hơn là từng nốt nhạc hay âm riêng lẻ. David
Pye [7] áp dụng phương pháp nhận dạng sự
thay đổi phổ của tiếng nói với hai kỹ thuật
chính, Gaussian Mixture Modelling (GMM) –
mô hình phân loại độ vang âm thanh và
phương thức Tree-Based Vector Quantization
(TreeQ) (Lượng tử hoá vector dựa trên cấu
trúc cây). Các kỹ thuật này yêu cầu biểu hiện
các tham số của mẫu âm thanh thành các
vector đặc trưng. Mel Frequency Cepstral
Coefficients (MFCC) - hệ số Mel được sử
Trong các nghiên cứu về giác quan của con
người, phương thức sử dụng hệ số tần Mel để
biểu hiện âm thanh bằng tham số cũng đã
được chứng minh là rất thành công. MFCC
tạo ra chữ ký hay dấu riêng cho mỗi bài hát.
Việc so sánh giữa chữ ký với nội dung âm
thanh là hiệu quả, bởi vì nó không liên quan
tới dữ liệu đã được bỏ đi trong quá trình tính
toán chữ ký, kết quả là cải thiện được việc tìm
kiếm dữ liệu với tỷ lệ thiết lập dữ liệu nhỏ và
yêu cầu lưu trữ bộ nhớ nhỏ.
Tel:0986060545, Email: pthientng@gmail.com
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Phùng Thị Thu Hiền và cs
Tạp chí KHOA HỌC & CÔNG NGHỆ
74(12): 80 - 85
Bài báo này trình bày phương pháp tìm kiếm
âm nhạc theo nội dung sử dụng đặc trưng
đường bao phổ kết hợp phương pháp phân
cụm K-means, cuối cùng là đưa ra một số kết
quả thực nghiệm.
khung. Quá trình phân khung được thể hiện
trong hình 2.
CƠ SỞ LÝ THUYẾT
Quá trình lọc theo thang Mel Cepstral
Theo Beth Logan [3], MFCC gồm 5 bước:
1. Chia tín hiệu thành các khung
2. Với mỗi khung, ta thu được biên độ phổ.
3. Lấy log của biên độ
Hình 2. Phân khung tín hiệu
Hàm cửa sổ bỏ đi những hiệu ứng phụ và
vector đặc trưng cepstral được thực hiện trên
mỗi khung cửa sổ. Thông thường, cửa sổ
Hamming được sử dụng, cửa sổ này có dạng:
2n
N 1
(1)
w(n) 0.540.46cos
,0 n N 1
4. Chuyển đổi sang thang Mel
5. Thực hiện biến đổi Cosine rời rạc.
Ý tưởng ở đây là giảm bớt sự méo phổ bằng
việc sử dụng các cửa sổ để giảm tín hiệu về
không tại điểm bắt đầu và kết thúc mỗi
khung.
Biến đổi Fourier rời rạc của mỗi khung được
tính toán và lấy logarith biên độ phổ. Thông
tin về pha bị bỏ qua do biên độ phổ là quan
trọng hơn pha. Thực hiện lấy logarith biên độ
phổ do âm lượng của tín hiệu là xấp xỉ
logarith. Bước tiếp theo là biến đổi phổ theo
thang Mel. Từ kết quả này, trong vector Mel
– spectral của các thành phần tương quan cao,
bước cuối cùng là thực hiện biến đổi cosine
rời rạc để tổng hợp vector phổ Mel để tương
quan lại các thành phần này.
Hình 1. Quá trình tạo các đặc tính MFCC
Quan sát quá trình trên ta thấy, âm thanh
được chia thành những khung có độ dài cố
định. Mục đích là để lấy mẫu những đoạn tín
hiệu nhỏ (theo lý thuyết là ổn định). Trong
việc lấy mẫu dữ liệu, chúng ta xem xét đến tín
hiệu âm thanh đã được số hóa bằng việc rời
rạc hóa các giá trị trên những khoảng đều
nhau vì vậy cần phải chắc chắn rằng tốc độ
lấy mẫu là đủ lớn để mô tả tín hiệu dạng
sóng. Tấn số lấy mẫu nên ít nhất gấp đôi tần
số dạng sóng như trong định lý của Nyquist.
Tốc độ lấy mẫu phổ biến là 8000, 11025,
22050, 44000, thông thường sử dụng tần số
trên 10kHz
Độ lệch tần số Mel
Để mô tả chính xác sự tiếp nhận tần số của hệ
thống thính giác, người ta xây dựng một
thang khác – thang Mel.
Độ lệch tần số Mel làm nhẵn phổ và làm nổi
lên các tần số cảm thụ có nghĩa. Biến đổi
Fourier lên tín hiệu qua bộ lọc thông dải để
làm đơn giản phổ mà không làm mất dữ liệu.
Điều này được thực hiện bằng cách tập hợp
các thành phần phổ thành một dải tần số. Phổ
được làm đơn giản hóa do sử dụng một giàn
bộ lọc để tách phổ thành các kênh. Các bộ lọc
được đặt cách đều nhau trên thang Mel và lấy
logarit trên thang tần số, các kênh có tần số
thấp là không gian tuyến tính trong khi các
kênh có tần số cao là không gian logarit.
Phân khung là quá trình chia mẫu tín hiệu
thành một số khung chồng lấp lên nhau hoặc
không, mục đích của phân khung là để lấy
mẫu các đoạn tín hiệu nhỏ. Bản chất của âm
thanh là không ổn định, vì vậy, biến đổi
Fourier sẽ thể hiện tần số xảy ra trên toàn
miền thời gian thay vì thời gian cụ thể. Do đó
khi tín hiệu là không ổn định, thì nó nên được
chia nhỏ thành các cửa sổ rời rạc, nhờ đó mỗi
tín hiệu trong một cửa sổ trở nên tĩnh và phép
biến đổi Fourier có thể thực hiện trên mỗi
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Phùng Thị Thu Hiền và cs
Tạp chí KHOA HỌC & CÔNG NGHỆ
74(12): 80 - 85
Tai người không cảm nhận sự thay đổi tần số
của tiếng nói tuyến tính mà theo thang Mel.
Thang tần số Mel tuyến tính ở tần số dưới
1kHz và logarit ở tần số cao hơn 1kHz. Ta
chọn tần số 1kHz, 40 dB trên ngưỡng nghe
1000 Mel. Do đó công thức gần đúng biểu
diễn quan hệ tần số ở thang Mel và thang
tuyến tính như sau:
1. Cố định vùng giá trị dưới mỗi bộ lọc và đôi
khi đưa thang về 1. Đặt M bằng số băng lọc
yêu cầu
2. Phân bố đều trên thang tần số Mel
3. Chuyển đổi từ Hz sang Wi trên thang tuyến
tính. Mối quan hệ giữa mel và frq được cho
bởi công thức:
m=ln(1+f/700)*1000/ln(1+1000/700)
(3)
(2)
Phƣơng pháp phân cụm K-means
Một phương pháp để chuyển đổi sang thang
Mel là sử dụng băng lọc. Khoảng cách của
băng lọc được định nghĩa bởi một hằng số tần
số mel theo thời gian. Băng lọc này được áp
dụng trong miền tần số, nó có thể xem như
các điểm thu được của bộ lọc chính. Với các
khung nhỏ tốt nhất là sử dụng các bộ lọc dạng
tam giác hoặc thậm chí hình chữ nhật vì độ
phân giải là quá thấp trong miền tần số thấp.
K-means là một phương pháp phân cụm.
Phương pháp này quan sát k cụm trong dữ
liệu, và trả lại vector chỉ số của K cụm đã
quan sát.
K-means quan sát trong dữ liệu và tìm cách
phân vùng dữ liệu sao cho dữ liệu trong một
cụm càng gần nhau càng tốt và so với dữ liệu
trong các cụm khác phải càng xa càng tốt.
Mỗi cụm được xác định bởi các thành phần
của nó và bởi thành phần trung tâm của nó.
Thành phần trung tâm của mỗi cụm là thành
phần mà có tổng khoảng cách từ các đối
tượng trong cụm đến nó là nhỏ nhất. Cụm
trung tâm được tính toán khác nhau với mỗi
thước đo khoảng cách, để tổng khoảng cách là
nhỏ nhất với mỗi tiêu chuẩn đánh giá.
Để thực hiện phương thức K-means ta sử
dụng một thuật toán lặp để tính tổng khoảng
cách từ mỗi đối tượng tới cụm trung tâm là
nhỏ nhất trên toàn bộ cụm. Thuật toán này di
chuyển các đối tượng giữa các cụm cho tới
khi tổng khoảng cách không thể giảm hơn
được nữa. Kết quả là tạo được các cụm có
khoảng cách đủ nhỏ và có độ phân cách hợp
lý. Độ nhỏ của dữ liệu có thể được chỉ ra bằng
việc thay đổi các tham số đầu vào giống với
số lượng cụm trung tâm và số lần lặp.
Hình 3. Băng lọc khoảng cách theo tần số mel
Mỗi bộ lọc trong băng lọc được nhân với phổ
tín hiệu vì vậy chỉ có một giá trị đơn của
cường độ trên bộ lọc được trả lại. Điều này có
thể đạt được qua các tính toán của ma trận
đơn. Kết quả là tổng của biên độ trong dải lọc
và vì vậy làm giảm độ chính xác tới mức mà
tai của con người có thể cảm nhận được.
Ý tưởng chính ở đây là tìm cách xác định cụm
trung tâm k từ mỗi cụm. Nên lựa chọn điểm
trung tâm vì các vị trí khác nhau cho các kết
quả khác nhau. Trong điều kiện lý tưởng
chúng phải cách xa các điểm khác tối đa khả
năng có thể. Mỗi điểm trong dữ liệu được gắn
với điểm trung tâm gần nhất. Điểm trung tâm
thứ k mới sẽ được tính toán lại từ kết quả
Hình 4. Phổ sau khi lọc theo thang Mel
Quá trình độ lệch tần số mel được thực hiện
theo ba bước sau:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Phùng Thị Thu Hiền và cs
Tạp chí KHOA HỌC & CÔNG NGHỆ
74(12): 80 - 85
phân cụm của bước trước và quá trình nhóm
các điểm dữ liệu với các điểm trung tâm gần
nhất sẽ được thực hiện lặp đi lặp lại và điều
đó sẽ tiếp tục cho tới khi xác định được điểm
trung tâm chính.
Phương pháp phân cụm K-means tìm nhóm
có kích thước nhỏ nhất trong tổng bình
phương các cụm, chúng ta sử dụng thuật toán
sai số bình phương để tính bình phương
khoảng cách Euclidean.
Thuật toán K-means thực hiện theo các
bước sau:
1. Đặt K điểm vào vùng phân cụm các đối
tượng. Các điểm này mô tả nhóm trung tâm
đầu tiên.
2. Gán mỗi đối tượng vào một nhóm có điểm
trung tâm gần nhất.
3. Khi tất cả các đối tượng đã được đưa vào
các nhóm, tính toán lại vị trí của K điểm trung
tâm.
4. Thực hiện lặp lại bước 2 và 3 cho tới khi
bỏ đi được các điểm trung tâm ở xa. Điều này
giúp phân cách các đối tượng thành các nhóm
có kích thước nhỏ nhất có thể.
Thủ tục lặp sẽ luôn kết thúc khi điểm trung
tâm không thay đổi. Tuy nhiên, cần lưu ý
rằng các thuật toán không nhất thiết phải đưa
ra những kết quả tối ưu. Hình 5 mô tả các
bước đã nêu trên. Mỗi bước dưới đây tương
ứng với trình tự của biểu đồ.
Hình 6. Phương pháp phân cụm K-means
KẾT QUẢ THỰC NGHIỆM
Chuẩn bị dữ liệu
Dữ liệu bao gồm 10 bài hát nhạc trẻ Việt nam
được lưu ở định dạng PCM wave, tần số lấy
mẫu 44 KHz, mã hóa 16 bit trên một mẫu.
Mỗi bài hát được trích ra một đoạn ngắn < 5 s
sử dụng làm mẫu tìm kiếm.
Các tham số thực nghiệm
Đặc trưng MFCC được cài đặt với các tham
số sau : Kích cỡ khung là 512 ms, không sử
dụng khung chồng lấp, số bộ lọc trong dãy
băng lọc Mel là 20, số hệ số Ceptral là 12,
không sử dụng các hệ số đạo hàm Delta, kết
hợp các hệ số MFCC với 1 hệ số năng lượng
Giống như Beth Logan [8], phân lớp bằng
cách phân hệ số cepstral thành 16 cụm theo
thuật toán K-means chuẩn. Sử dụng khoảng
cách Euclidean để tính toán độ tương tự.
Kết quả thực nghiệm và đánh giá
Chọn số lượng cụm k. Ví dụ k=5
Tạo ra ngẫu nhiên vị trí trung tâm cụm
Tại mỗi Centre tìm điểm trung tâm của
chính nó
Thực hiện bước nhảy
Thực hiện lặp lại cho tới khi kết thúc
Chương trình demo tìm kiếm bài hát theo đặc
trưng đường bao phổ MFCC thử nghiệm trên
cơ sở dữ liệu nhỏ (10 bài hát) nên được thiết
kế tích hợp cả thao tác huấn luyện và nhận
dạng cho trực quan. Thao tác tìm kiếm nhận
dạng được thử nghiệm với từng mẫu âm
thanh riêng rẽ và ghi lại kết quả thủ công. Kết
quả nhận dạng đúng sau đó được tổng hợp lại
để cho ra kết quả nhận dạng của hệ thống.
Trong thực tế khi lượng dữ liệu huấn luyện
lớn cần thực hiện huấn luyện trước và lưu
trong cơ sở dữ liệu. Thao tác nhận dạng và
tìm kiếm được tách ra độc lập so sánh với cơ
sở dữ liệu huấn luyện đã lưu. Việc tách riêng
2 thao tác huấn luyện và tìm kiếm sẽ làm
giảm thời gian khi tiến hành thử nghiệm.
Hình 5. Thủ tục K-means
Hình 6 minh họa phương thức phân cụm K
trong hình 5. Chú ý rằng những dữ liệu tương
tự được nhóm cùng nhau.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Phùng Thị Thu Hiền và cs
Tạp chí KHOA HỌC & CÔNG NGHỆ
74(12): 80 - 85
nội dung”, Luận văn thạc sỹ công nghệ thông tin,
Đại học Thái Nguyên, 12/2009.
Trong chương trình thử nghiệm, kết quả nhận
dạng đúng cuối cùng sau 10 lần thử nghiệm 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ỏ. Hơn nữa
độ dài âm thanh đầu vào (trích 1 đoạn từ file
âm thanh cần tìm kiếm) đủ lớn (so với âm
thanh tìm kiếm). 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ỏ.
[2]. Phùng Thị Thu Hiền, PGS.TS. Thái Quang
Vinh, Phùng Trung Nghĩa, Lê Tuấn Anh, “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”, Tạp chí Khoa học & Công nghệ ISSN,
1859 – 2171, 2009, T55 – 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
Về mặt thời gian, quá trình huấn luyện và sau
đó tìm kiếm hết ~ 4 s với một bài hát.
[6]. A.Ghias, J.Logan, D. Chamberlin and
B.Smith, “Query by humming,” in ACM
Multimedia, 1995
Chương trình mô phỏng được xây dựng trên
phần mềm matlab:
[7]. David Pye, “Content Based Methods for the
Management of Digital Music” AT&
T
Labaratories Cambridge
[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.
[11]. Z.Liu and Q.Huang, “Content-based
indexing and retrieval by example in audio,” in
ICME 2000, 2000
Hình 7. Kết quả chạy chương trình
Hƣớng phát triển
TÀI LIỆU THAM KHẢO
[1]. Phùng Thị Thu Hiền, “Trích chọn đặc trưng
âm thanh trong bài toán tìm kiếm âm nhạc theo
nội dung”, Luận văn thạc sỹ công nghệ thông tin,
Đại học Thái Nguyên, 12/2009.
[2]. Phùng Thị Thu Hiền, PGS.TS. Thái Quang
Vinh, Phùng Trung Nghĩa, Lê Tuấn Anh, “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”, Tạp chí Khoa học & Công nghệ ISSN,
1859 – 2171, 2009, T55 – 59.
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 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]. Phùng Thị Thu Hiền, “Trích chọn đặc trưng
âm thanh trong bài toán tìm kiếm âm nhạc theo
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Phùng Thị Thu Hiền và cs
Tạp chí KHOA HỌC & CÔNG NGHỆ
74(12): 80 - 85
SUMMARY
CONTENT-BASED MUSIC RETRIEVAL USING SPECTRAL ENVELOPE FEATURE
AND K-MEANS ALGORITHM
Phung Thi Thu Hien1 , Vu Tat Thang2,
Thai Quang Vinh2, Nguyen Van Huy1
1Thai Nguyen University of Technology
2Institute of Information Technology - VAST
In multimedia database, music retrieval is an important research topic. Current music searching is based on
text indexing. However, this kind of method has some drawbacks. It is difficult to remember the text
keywords such as song name, author name, singer name or the lyric of songs. Content-based music searching
overcomes these drawbacks. In state of the art approaches, feature vectors of music signal are built based on
their physical characteristics as volume, energy, and spectrum.Recently, some researches use another
approach, which based on the signal processing techniques incorporating with human auditory analysis. This
approach minimizes the redundant information as well as accurately represents the music signal. This paper
presens a method of song searching using Mel ceptral spectral envelope and K-means algorithm.
Tel: 0986060545, Email: pthientng@gmail.com
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Bạn đang xem tài liệu "Tìm kiếm âm nhạc theo nội dung sử dụng đặc trưng đường bao phổ và phương pháp phân cụm K-means", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- tim_kiem_am_nhac_theo_noi_dung_su_dung_dac_trung_duong_bao_p.pdf