I

LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu của bản thân. Các số liệu, kết
quả trình bày trong luận văn này là trung thực và chƣa từng đƣợc ai công bố trong
bất kỳ công trình luận văn nào trƣớc đây.
Học viên
Phạm Cẩm Ngọc

II

LỜI CẢM ƠN

Lời đầu tiên, tôi xin gửi lời cảm ơn chân thành và biết ơn sâu sắc tới TS.
Nguyễn Hải Châu – ngƣời đã tận tình hƣớng dẫn tôi trong suốt quá trình thực hiện
đề tài. Sự giúp đỡ tận tình, những lời khuyên bổ ích và những góp ý của Thầy đối
với bản luận văn là động lực lớn giúp tôi hoàn thành đề tài của mình.
Tôi xin gửi lời cảm ơn chân thành đến các Thầy Cô trong Trƣờng Đại học
Công nghệ - những ngƣời đã dìu dắt và giúp đỡ tôi trong suốt 2 năm học.
Và cuối cùng, tôi xin gửi lời cảm ơn tới gia đình, ngƣời thân và bạn bè –
những ngƣời luôn bên tôi những lúc khó khăn nhất, luôn động viên tôi, khuyến
khích tôi trong cuộc sống và trong công việc.
III

MỤC LỤC

LỜI CAM ĐOAN I
LỜI CẢM ƠN II
DANH MỤC CÁC KÍ HIỆU, CÁC CHỮ VIẾT TẮT V
DANH MỤC CÁC BẢNG VI

2.3.1. Nạp động (dynamic loading) 30
2.3.2. Các kiểu dữ liệu cơ sở trong C 31
2.3.3. Chuẩn gọi hàm theo phiên bản 0 cho các hàm C 36
2.3.4. Chuẩn gọi hàm phiên bản 1 cho các hàm C 39
2.3.5. Các quy tắc viết chƣơng trình 43
2.3.6. Biên dịch và liên kết tới các hàm động (Dynamically-Loaded
Function) 44
2.3.7. Cơ sở cài đặt (Build Infrastructure) các mở rộng 46
2.4. Tổng kết chƣơng 48
CHƢƠNG 3. 49
3.1. Xây dựng cơ sở dữ liệu các fingerprint 50
3.1.1. Thiết kế cơ sở dữ liệu bài hát trong PostgreSQL 50
3.1.2. Xây dựng các hàm mở rộng trong PostgreSQL để tìm kiếm bản nhạc
52
3.2. Xây dựng tập dữ liệu huấn luyện 53
3.3. Kết quả thực nghiệm 54
KẾT LUẬN 57
TÀI LIỆU THAM KHẢO 58 V

DANH MỤC CÁC KÍ HIỆU, CÁC CHỮ VIẾT TẮT Ký hiệu/viết tắt
Mô tả
DDA
Distortion Discriminant
JDBC


Hình 1. 1 Mô hình trích chọn fingerprint của Haitsma 9
Hình 1. 2 (a) fingerprint block của bài hát gốc, (b) fingerprint block của bài hát
sau khi đã bị nén, (c) sự khác nhau giữa (a) và (b) thể hiện trên số bít lỗi màu đen
(BER=0,078). 10
Hình 1. 3 Biểu diễn của 4 ảnh phổ liên tiếp của 2 bài hát khác nhau. Với mỗi bài
hát, dòng đầu: ảnh phổ ban đầu, dòng hai: độ lớn wavelet, dòng 3: 200 wavelet
đầu tiên. 13
Hình 1. 4 Biểu diễn âm thanh theo biên độ, tần số và mã nhị phân 15
Hình 1. 5 Các đặc trưng hình chữ nhật được biểu diễn trong mối quan hệ với các
cửa sổ tìm kiếm bao xung quanh. 16
Hình 1. 6 So sánh phương pháp tính toán đặc trưng của Yanke (thuật toán
Pairwise Boosting) với thuật toán của Haitsma và Haitsma cải tiến. 20
Hình 1. 7 Mô hình phụ thuộc đơn giản được giả lập bởi hệ thống 22
Hình 2. 1 Kiến trúc PostgreSQL 28
Hình 3. 1 Tổ chức cơ sở dữ liệu theo LUT 51
Hình 3. 2 Mô hình cơ sở dữ liệu 52
Hình 3. 3 So sánh kết quả thực nghiệm với các bộ dữ liệu huấn luyện khác nhau 55
Hình 3. 4 Thời gian tìm kiếm trên mỗi bản nhac thu với hệ thống nhận dạng của
Y.Ke. 56
Hình 3. 5 Thời gian tìm kiếm trên mỗi bản nhạc thu âm đối với hệ thống nhận
dạng mới. Error! Bookmark not defined.
1

MỞ ĐẦU

Sự phát triển của máy tính và mạng Internet nhƣ hiện nay dẫn đến nhu cầu
tìm kiếm trên Internet là rất lớn. Nếu nhƣ trƣớc đây ngƣời ta chỉ quan tâm đến tìm
kiếm thông tin, văn bản thì hiện nay nhu cầu tìm kiếm dữ liệu đa phƣơng tiện
(multimedia) cho mục đích giải trí không ngừng tăng lên. Việc tìm kiếm các bản

quả trong một cơ sở dữ liệu fingerprint.
Mục tiêu của một hệ thống nhận dạng nhạc số dựa trên chuỗi đặc trƣng âm
thanh (audio fingerprint) là từ một bản thu âm ngắn đã bị nhiễu, hệ thống cho phép
tìm kiếm chính xác bài hát gốc của bản thu âm đó. Trong thực tế có thể gặp tình
huống sau, ngƣời sử dụng nào đó lắng nghe một ca khúc qua radio trên xe hơi của
mình hay tại một bữa tiệc. Đây là bài hát nối tiếng mà đã lâu rồi anh ta không
đƣợc nghe nên đã quên mất lời bài hát và tên tác giả bài hát này. Ngƣời này có thể
gửi một đoạn ngắn của bản nhạc đã đƣợc thu âm qua điện thoại di động tới một
server tìm kiếm nhạc số để nhận lại một tin nhắn chứa các thông tin liên quan nhƣ
tên bài hát, lời bài hát hay tác giả của bài hát. Công việc này đặt ra những thách
thức vì những lý do sau đây:
 Bản thu âm bị sai khác so với bản nhạc gốc do ảnh hƣởng nhiễu tín hiệu
của các thiết bị thu âm thông dụng (thƣờng là điện thoại di động) hay do
ảnh hƣởng của tiếng ồn và các tạp âm xung quanh trong quá trình thu âm.
 Bản thu âm chỉ là một đoạn nhạc nào đó thuộc bài hát gốc nên các
phƣơng pháp tính toán đặc trƣng truyền thống trên bản nhạc thu âm
thƣờng cho kết quả là một chuỗi đặc trƣng khác với chuỗi đặc trƣng đƣợc
tính toán trên toàn bộ bài hát gốc.
3

 Hệ thống nhận dạng nhạc số cần phải đáp ứng đƣợc nhu cầu tìm kiếm
trong thực tế là cho kết quả nhanh và chính xác trên một cơ sở dữ liệu
gồm hàng trăm nghìn bài hát.
Trên cơ sở các nghiên cứu gần đây của Haitsma và Kaller [10, 11] và Y. Ke
[5, 6] chúng tôi tiến hành xây dựng một hệ thống nhận dạng nhạc số dựa trên
chuỗi đặt trƣng âm thanh có tính ứng dụng trong thực tế sử dụng phƣơng pháp
trính rút đặc trƣng cửa sổ gối kết hợp học máy. Bên cạnh đó, luận văn tiến tới xây
dựng một bộ dữ liệu huấn luyện cho kết quả tìm kiếm với độ chính xác cao và một
cơ sở dữ liệu meta-dada/fingerprint dựa trên hệ quản trị cơ sở dữ liệu PostgreSQL,
đồng thời luận văn kết hợp xây dựng các hàm mở rộng bằng ngôn ngữ C trong

f
có độ dài nhỏ
hơn. Thay vì so sánh mức độ tƣơng tự giữa 2 chuỗi bít (tín hiệu âm thanh) A
1
và
A
2
, chúng ta so sánh mức độ tƣơng tự của hai chuỗi đặc trƣng tƣơng ứng A
1f
và
A
2f
. Trong thực tế, một phiên bản chất lƣợng CD gốc của bài hát “Rolling Stones
– Angie” và một phiên bản mp3 120Kb/s đƣợc cảm nhận là giống nhau với hệ
thống thính giác của con ngƣời, tuy nhiên biểu diễn sóng của chúng có thể rất khác
nhau. Vì thế, việc so sánh A
1f
và A
2f
không phải sự so sánh bằng nhau tuyệt đối về
mặt toán học mà là sự so sánh có tính cảm quan.
5

Chúng ta cần có một số tiêu chí để đánh giá hàm  nói trên. Sau đây là một
số tiêu chí thƣờng đƣợc sử dụng:
 Tính bền vững (robustness): Chuỗi đặc trƣng phải ít thay đổi khi tín
hiệu âm thanh bị suy giảm hoặc tín hiệu âm thanh bị nhiễu, bị méo …
Tính chất này làm tăng độ tin cậy khi nhận dạng âm thanh trong môi
trƣờng thực, có nhiễu và tập âm hoặc biên độ tín hiệu nhỏ. Để đạt đƣợc
tính bền vững cao, các fingerprint đƣợc trích chọn cần dựa trên các đặc

các ứng dụng dành cho ngƣời dùng có liên quan tới âm thanh/âm nhạc cùng với
các thông tin liên quan. Một ví dụ đặc trƣng nhất là ứng dụng tìm kiếm bản nhạc
qua điện thoại di động. Ngƣời dùng khi nghe một bản nhạc đƣợc phát qua loa,
hoặc đài phát thanh và muốn biết tên bản nhạc, ca sĩ thể hiện. Ngƣời này sẽ gọi tới
một số điện thoại dịch vụ để bản nhạc thu qua điện thoại đƣợc truyền tới server
chứa cơ sở dữ liệu âm nhạc. Server căn cứ vào chuỗi đặc trƣng để tìm tên bản
nhạc, ca sĩ thể hiện … và gửi kết quả cho ngƣời dùng. Đây là một bài toán khó vì
tín hiệu âm thanh sau nhiều lần truyền đã bị suy giảm và có nhiều nhiễu.
1.2.3. Các bộ lọc trong ứng dụng dùng chung file
Trong các ứng dụng dùng chung file, chuỗi đặc trƣng đƣợc sử dụng để nhận
ra các file âm thanh có bản quyền và không cho ngƣời dùng tải về các file này.
Năm 2001, Napster [4] cài đặt bộ lọc dựa trên tên file nhƣng bộ lọc này hoạt động
không hiệu quả bởi vì ngƣời dùng thƣờng cố tình đánh sai tên cho các file có bản
quyền mà họ muốn tải về. Do đó vào tháng 5-2001, Napster đã sử dụng bộ lọc dựa
trên chuỗi đặc trƣng của Relatable [2] cho phép phát hiện ra các file có bản quyền
ngay cả khi ngƣời sử dụng đánh sai tên file.
1.2.4. Tự động tổ chức thƣ viện âm nhạc
7

Chuỗi đặc trƣng có thể đƣợc sử dụng vào việc tự động tổ chức thƣ viện âm
nhạc. Hiện nay, MP3 là khuôn dạng file thƣờng đƣợc sử dụng để lƣu trữ trong các
thƣ viện âm nhạc. Các file MP3 đƣợc tạo ra từ nhiều nguồn khác nhau do đó siêu
dữ liệu (meta-data) kèm theo nhƣ tên tác giả, tác phẩm, ngƣời thể hiện, năm thu
âm không đƣợc đầy đủ và nhất quán. Khi đó, chuỗi đặc trƣng đƣợc sử dụng để
hoàn thiện các thông tin này.
1.2.5. Một số ứng dụng khác
Chuỗi đặc trƣng còn có rất nhiều ứng dụng khác trong thực tiễn. Chuỗi đặc
trƣng có thể đƣợc sử dụng trong các ứng dụng về truyền hình có tƣơng tác mà
không cần sử dụng thêm các thiết bị đặc biệt, hoặc tự động phát hiện và thay thế
các đoạn quảng cáo. Khác biệt so với các công nghệ khác, chuỗi đặc trƣng hƣớng

con tƣơng ứng. Ƣu điểm của phƣơng pháp này là tính đơn giản và tốc độ tính toán
cao.
Để sử dụng phƣơng pháp cửa sổ gối, tín hiệu âm thanh trƣớc tiên đƣợc chia
thành các frame gối nhau. Một tập các đặc trƣng đƣợc tính toán trên mỗi frame
này. Các đặc trƣng cần đƣợc chọn sao cho nó ít thay đổi với các loại nhiễu tín
hiệu. Các đặc trƣng này thƣờng là hệ số Fourier (Fourier coefficients) [16], Mel-
Frequency Cepstral Coefficients (MFCC) [17], độ mịn quang phổ (spectral
flatness) [15] hay hệ số Linear Predictive Coding (LPC) [15]. Đặc trƣng tính toán
trên mỗi frame đƣợc gọi là một sub-fingerprint. Một sub-fingerprint thƣờng không
có đầy đủ thông tin cho phép nhận dạng bản nhạc, đơn vị cơ sở cho nhận dạng là
các khối đặc trƣng (fingerprint block).
9 Hình 1.1 Mô hình trích chọn fingerprint của Haitsma
Mô hình trích chọn đặc trƣng của Haitsma và các cộng sự [10, 11] dựa trên
cách tiếp cận trên. Theo đó, 32 bit sub-fingerprint đƣợc tính toán cho mỗi khoảng
11,6 mili giây. Một fingerprint block bao gồm 256 sub-fingerprint nối tiếp, tƣơng
ứng với độ mịn (granularity) 3 giây. Nhƣ vậy, trong trƣờng hợp xấu nhất, một sub-
fingerprint của bản nhạc thu âm và sub-fingerprint tƣơng ứng trong cơ sở dữ liệu
có thể sai lệch nhau tối đa 5,8 mili giây.
Bởi vì những đặc trƣng âm thanh cảm quan quan trọng nhất nằm trong miền
tần số nên biểu diễn phổ đƣợc tính toán bởi biến đổi Fourier trên mỗi frame. Do độ
nhạy về pha của biến đổi Fourier với các biên khác nhau trên mỗi frame và do
thực tế là hệ thống thính giác của con ngƣời (Human Auditory System - HAS)
không cảm nhận đƣợc sự thay đổi pha nên chỉ những giá trị dƣơng của quang phổ,
chẳng hạn nhƣ mật độ phổ đƣợc giữ lại. Để tính toán đƣợc một giá trị 32 bit sub-
fingerprint cho mỗi frame, một dải gồm 33 miền tần số không trùng lặp đã đƣợc
Haitsma lựa chọn. Dải tần số này nằm trên miền tần số từ 300 Hz đến 2000 Hz
(miền tần số thích hợp đối với HAS) và có độ dộng đều nhau. Thực nghiệm đã chỉ

> 0
0 ế 

, 



, + 1

(



1, 



1, + 1


< 0
Hình 1.2 (a) fingerprint block của bài hát gốc, (b) fingerprint block
của bài hát sau khi đã bị nén, (c) sự khác nhau giữa (a) và (b) thể hiện
trên số bít lỗi màu đen (BER=0,078).
Hình 1.2 đƣa ra ví dụ về biểu diễn của một khối fingerprint (bao gồm 256
sub-fingerprint) của bài hát “O Fortuna” thể hiện bởi Carl Orff đƣợc trích chọn
dựa theo mô hình của Haitsma. Các điểm ảnh màu trắng tƣơng ứng với các bit 1,

các phƣơng pháp khác. DDA đƣợc dựa trên một biến thể của phƣơng pháp LDA
12

(Linear Discriminant Analysis) đƣợc gọi là Oriented Principal Components
Analysis (OPCA).
OPCA giả thiết có một phiên bản tín hiệu bị méo của các mẫu huấn luyện để
từ đó tìm ra các đặc trƣng ít bị biến đổi khi thực hiện bƣớc tiền xử lý tín hiệu để
làm giảm nhiễu đến mức tối thiểu và tăng tối đa mức tín hiệu. Ngƣợc lại, phƣơng
pháp PCA (Principal Components Analysis) tìm tập các vector trực giao để tăng
tối đa sự biến đổi của tín hiệu. Nhƣ vậy, OPCA tìm đƣợc tập các vector không trực
giao có thể dùng để tính toán nhiễu. Thực nghiệm của Burges và các cộng sự [9]
cho thấy chuỗi đặc trƣng xác định bằng phƣơng pháp DDA ít bị biến đổi với vấn
đề căn thời gian và quan trọng hơn là ít bị biến đổi với các loại nhiễu không có
trong dữ liệu huấn luyện.
1.3.4. Phƣơng pháp dựa trên wavelet
Phƣơng pháp này do các tác giả S. Baluja và M. Covell (Google Inc.) phát
triển [8, 12] dựa trên tiếp cận của Y. Ke [5, 6]: áp dụng các kỹ thuật trong lĩnh vực
thị giác máy vào việc xây dựng chuỗi đặc trƣng và tiếp cận dựa trên wavelet của
C. Jacob [18]. Phƣơng pháp này không sử dụng kỹ thuật học máy mà dùng biến
đổi wavelet để tăng tốc độ tìm kiếm trong cơ sở dữ liệu đa phƣơng tiện lớn. Chuỗi
đặc trƣng do S. Baluja và M. Covell đề xuất dựa trên công trình của J. Haitsma
[10, 11] nhƣng có cải tiến nâng cao để có thể đại diện cho mẫu tín hiệu âm thanh
có độ dài lớn hơn.
Shumeet Baluja và cộng sự [7, 8] cũng bắt đầu quá trình tính toán đặc trƣng
bằng việc biến đổi tín hiệu âm thanh thành một ảnh phổ. Từ các ảnh quang phổ
này, Baluja chọn ra các Haar-wavelet tốt nhất theo cƣờng độ giống nhƣ hệ thống
xác thực ảnh đƣợc đƣa ra trong [18]. Trong nghiên cứu của mình, thay vì so sánh
ảnh trực tiếp dựa vào khoảng cách của điểm ảnh, Jacob và các cộng sự [18] đã
phân tách ảnh dựa vào các Haar-wavelet đa phân giải. Trên cơ sở đó, Shumeet
Baluja tính toán một đặc trƣng wavelet cho mỗi ảnh phổ. Bản thân tập các wavelet

1.4.1. Biểu diễn bài hát dƣới dạng một spectrogram
Khi nhận đƣợc một bản nhạc thu âm đã bị nhiễu, ngƣời ta mong muốn rằng
hệ thống bằng cách nào đó sẽ tìm ra đƣợc bài hát tƣơng ứng trong một cơ sở dữ
liệu lớn các meta-data/fingerprint một cách nhanh nhất. Hệ thống cần phải đáp ứng
các yêu cầu về tính chính xác, về độ dài bản nhạc truy vấn và tốc độ tìm kiếm.
Tính chính xác yêu cầu hệ thống phải có khả năng phân biệt giữa các bài hát tƣơng
tự nhau bởi vì trong thực tế, một bài hát đƣợc phát qua bộ phát chất lƣợng không
cao, ghi âm sử dụng microphone tích hợp sẵn sẽ rất khác so với chính bài hát đó
đƣợc phát qua một loa có chất lƣợng cao và đƣợc ghi bởi một microphone chất
lƣợng tốt. Bên cạnh đó, việc mỗi bản nhạc truy vấn có thể có độ dài tùy ý và bắt
đầu tại một vị trí bất kỳ thuộc bài hát gốc cũng đặt ra cho hệ thống các yêu cầu về
tính cục bộ với sự dịch chuyển thời gian. Hệ thống cũng cần có khả năng đánh chỉ
mục hiệu quả để có thể tìm kiếm cho kết quả nhanh và chính xác trên một cơ sở dữ
liệu gồm hàng nghìn bài hát.
Trong thực tế, các tín hiệu âm thanh 1-D nguyên bản sẽ thay đổi rất nhiều khi
bị nhiễu và các hệ thống thƣờng khó tính toán đƣợc các đặc trƣng. Y. Ke sử dụng
15

cách tiếp cận chuyển đổi các tín hiệu âm thanh thành các ảnh 2-D theo tần số (gọi
là ảnh phổ - spectrogram) sử dụng phƣơng pháp biến đổi Fourier ngắn (short-term
Fourier transform) [11]. Với các spectrogram này, ngƣời ta dễ dàng nhận thấy
đƣợc sự tƣơng tự giữa các phiên bản khác nhau của cùng một bài hát ngay cả khi
tín hiệu gốc đã bị biến đổi. Trong hình 1.4, các snippet có độ dài 10 giây của 3 bài
hát: melloncamp bản gốc, waterworld, melloncamp bản thu âm đƣợc biểu diễn
theo biên độ, tần số và mã nhị phân. Ta dễ dàng nhận ra đƣợc sự giống nhau giữa
hai phiên bản melloncamp và khác nhau giữa melloncamp và waterworld khi
chúng đƣợc biểu diễn theo tần số và mã nhị phân.

Hình 1. 4 Biểu diễn âm thanh theo biên độ, tần số và mã nhị phân
Mặc dù việc chuyển đổi từ tín hiệu âm thanh theo miền thời gian sang các


=  



, 


,


<,

<

với 

, 

là intergral image và (, ) là ảnh gốc. Khi sử dụng 2 công thức
sau:


, 

= 

, 1

+ 

tiêu biểu nhất (M đƣợc chọn bằng 32) và ngƣỡng tƣơng ứng để tạo ra một véc tơ
M bit – gọi là một đặc trƣng (sub-fingerprint, descriptor). Tuy nhiên, mỗi đặc
trƣng này không có đầy đủ các thông tin cần thiết cho phép xác định chính xác bài
hát gốc từ truy vấn trong một cơ sở dữ liệu gồm hàng trăm nghìn bài hát, mà các
signature (là tập các đặc trƣng kế tiếp nhau) mới là đơn vị cơ bản cho so sánh và
tìm kiếm.
1.4.2. Tính toán đặc trƣng bởi thuật toán Boosting theo cặp (pairware
boosting)
Khi xây dựng đặc trƣng cho mỗi bài hát cần đảm bảo rằng các bản nhạc từ
cùng một bài hát sẽ tạo ra những đặc trƣng tƣơng tự, trong khi đó các bản nhạc từ
các bài hát khác nhau sẽ cho đặc trƣng khác nhau. Nói cách khác, hệ thống cần
phải học đƣợc một phân lớp 


1
, 
2

=

1, 1

, với 
1
và 
2
là hai ảnh phổ
bất kỳ và nhãn  chỉ ra rằng hai ảnh phổ đó là thuộc về cùng một bài hát gốc
(= 1) hay hai bài hát khác nhau (y = 1). Một phƣơng pháp phổ biến dùng để
18




1

 






2

 


]. Nói theo cách khác, nếu hai
mẫu tạo ra các giá trị tƣơng ứng đƣợc tính toán bởi bộ lọc ở cùng phía với ngƣỡng,
nó đƣợc gán nhãn là nằm tại cùng vị trí trong cùng một bản nhạc, ngƣợc lại, nó
đƣợc cho là hai audio snippet khác nhau. Công thức gán nhãn mà Y. Ke sử dụng
khác với thuật toán Adaboost truyền thống ở chỗ nhãn đƣợc gán theo cặp của các
giá trị lọc. Khi mà các mẫu lọc này đƣợc học bởi hệ thống, một ảnh phổ  sẽ đƣợc
chuyển thành một vec tơ  bit, điều này cho phép việc đánh chỉ mục hiệu quả dựa
trên thuật toán băm.
Cách đánh trọng số của thuật toán Adaboost nguyên bản cho kết quả không
tốt khi áp dụng cho hệ thống trích chọn của Y. Ke, bởi vì thông thƣờng không bộ
phân lớp nào thực hiện việc gán nhãn cho kết quả tốt hơn trƣờng hợp gán nhãn
ngẫu nhiên với những cặp hai mẫu đƣợc chọn khác nhau. Thật vậy, giả sử chúng ta
có mẫu  đƣợc chọn ngẫu nhiên từ tập phân phối  , bộ lọc 




1
, 
2

= 1

= 2

1 

0,5. (1)

Nhƣ vậy, khả năng các bộ hai mẫu khác nhau đƣợc gán nhãn sai là giống
nhau chiếm ít nhất một nửa các mẫu đƣợc xét trong trƣờng hợp kích thức mẫu đủ
lớn, mâu thuẫn điều kiện bộ phân lớp yếu của Adaboost. Y. Ke khắc phục vấn đề
này bằng cách áp dụng thuật toán phân lớp theo cặp bất đối xứng – chỉ những bộ
mẫu giống nhau đƣợc đánh lại trọng số và trọng số của các bộ giống nhau cũng