Khóa luận đã trình bày một cách tổng quan về hệ thống chuỗi đặc trưng âm
thanh và các ứng dụng phổ biến của nó. Trong khóa luận cũng trình bày chi tiết hai
phương pháp khác nhau về việc trích rút ra chuỗi đặc trưng âm thanh của một đoạn
âm thanh và cách thức tìm kiếm chuỗi đặc trưng phù hợp với nó trong một cơ sở dữ
liệu lớn. Qua đó chúng ta đã có hình dung khái quát về chuỗi đặc trưng – một nền
tảng quan trọng trong các ứng dụng liên quan đến âm thanh.
42 trang |
Chia sẻ: lylyngoc | Lượt xem: 2726 | Lượt tải: 3
Bạn đang xem trước 20 trang tài liệu Luận văn Chuỗi đặc trưng âm thanh và ứng dụng trong tìm kiếm nhạc số, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
tốt. Siêu dữ liệu thường không
thống nhất, không đầy đủ và đôi lúc thậm chí còn không đúng. Giả sử cơ sở dữ liệu
chuỗi đặc trưng chứa các siêu dữ liệu đúng, chuỗi đặc trưng âm thanh có thể tạo nên
siêu dữ liệu của các bài hát trong một thư viện đồng nhất, cho phép tổ chức sắp xếp
dễ dàng trên cơ sở đó, ví dụ theo album hay theo nghệ sĩ. Ví dụ, ID3Man – một công
cụ mạnh được phát triển bởi kỹ thuật chuỗi đặc trưng Auditude để tạo nhãn các file
MP3 không gán nhãn hay nhãn sai. Một công cụ tương tự là Moodlogic sẵn có như
một plug-in trong Winamp.
9
CHƯƠNG 2: CÁC PHƯƠNG PHÁP XÂY DỰNG VÀ TÌM KIẾM
CHUỖI ĐẶC TRƯNG ÂM THANH
2.1. Nguyên tắc cơ bản xây dựng hệ thống chuỗi đặc trưng âm thanh
Các chuỗi đặc trưng âm thanh có khuynh hướng giữ lấy những đặc điểm có liên
quan đến tri giác của âm thanh. Việc rút ra và tìm kiếm các chuỗi đặc trưng cùng một
lúc nên được thực hiện nhanh chóng và dễ dàng, tốt nhất là với một granularity (độ
dài của đoạn âm thanh truy vấn) nhỏ để cho phép sử dụng trong các ứng dụng đòi hỏi
cao (ví dụ việc nhận dạng qua điện thoại di động). Chúng ta sẽ đưa ra một vài câu
hỏi cơ bản trước khi bắt đầu xây dựng và thực thi chuỗi đặc trưng âm thanh. Câu hỏi
dễ thấy nhất là: những loại thuộc tính nào phù hợp nhất? Trong những tài liệu được
công bố hiện có thì tập các thuộc tính có liên quan nói chung được chia làm hai lớp:
lớp các thuộc tính ngữ nghĩa và lớp các thuộc tính phi ngữ nghĩa. Các yếu tố điển
hình trong lớp thuộc tính ngữ nghĩa là loại (genre), số nhịp trên phút (beats-per-
minute), và điệu (mood). Những loại thuộc tính này thường có thể hiểu trực tiếp, và
trên thực tế được dùng để phân loại nhạc, tạo ra các danh sách. Lớp thuộc tính phi
ngữ nghĩa bao gồm các thuộc tính có tính chất toán học hơn và con người khó có thể
“đọc” trực tiếp ra từ bản nhạc. Yếu tố điển hình trong lớp này là AudioFlatness được
đề xuất trong MPEG-7 như một tập các kí hiệu mô tả âm thanh. Dưới đây sẽ trình
bày một vài lý do để chúng ta nên chọn làm việc với các thuộc tính phi ngữ nghĩa:
• Các thuộc tính ngữ nghĩa luôn luôn có nghĩa mập mờ và không rõ ràng. Ví
dụ những người có sở thích khác nhau thì có quan điểm khác nhau đối với
việc phân loại. Ngoài ra, trên thực tế ngữ nghĩa có thể thay đổi theo thời
gian. Ví dụ, âm nhạc được phân loại như cách đây 25 năm là hard rock thì
ngày nay được coi là soft listening. Điều này làm cho việc phân tích toán
học trở nên khó khăn.
• Các thuộc tính ngữ nghĩa nói chúng khó tính toán hơn các thuộc tính phi
ngữ nghĩa.
• Các thuộc tính ngữ nghĩa không thích hợp với tất cả. Ví dụ, số nhịp trên
phút không thể áp dụng tiêu biểu cho nhạc cổ điển được.
Câu hỏi thứ hai được đưa ra là sự biểu diễn của các chuỗi đặc trưng. Một dạng
điển hình là ta có thể biểu diễn nó như một vectơ các số thực, trong đó mỗi thành
10
phần biểu thị trọng lượng (weight) của thuộc tính thuộc tri giác cơ bản nào đó. Quan
điểm thứ hai là ngăn cản tiến gần hơn đến các hàm băm mã hóa và biểu diễn các
chuỗi đặc trưng số như những xâu bit. Vì lý do giảm độ phức tạp tìm kiếm chúng ta
quyết định làm việc với quan điểm thứ hai. Theo quan điểm đầu tiên thì việc đo độ
giống nhau có dính dáng đến các phép cộng/trừ các số thực thậm chí có thể là các
phép nhân số thực. Các chuỗi đặc trưng dựa trên cơ sở biểu diễn bởi các bit có thể
được so sánh bằng cách đơn giản là đếm các bit. Khi đưa ra viễn cảnh những ứng
dụng được mong đợi, chúng ta không mong muốn robustness cao cho mỗi ứng dụng
và mỗi bit trong chuỗi đặc trưng nhị phân. Vì thế, trái ngược với các hàm băm mật
mã mà điển hình có tối đa vài trăm bit, chúng ta sẽ cho phép các chuỗi đặc trưng có
vài nghìn bit. Các chuỗi đặc trưng chứa số lượng bit lớn cho phép nhận dạng tin cậy
thậm chí nếu tỷ lệ phần trăm của các bit không phù hợp là khá cao.
Câu hỏi cuối cùng liên quan đến granularity của các chuỗi đặc trưng. Trong các
ứng dụng mà chúng ta vạch ra không đảm bảo rằng các file âm thanh cần nhận dạng
được hoàn thành xong. Ví dụ, trong BM, bất kỳ khoảng thời gian 5 giây nào cũng là
một đơn vị âm nhạc có giá trị thương mại, và vì thế có thể được xác định và được
nhận ra. Ngoài ra trong các ứng dụng về bảo mật như việc lọc file trên mạng ngang
hàng (peer-to-peer), một ứng dụng sẽ không mong muốn việc xóa bỏ vài giây đầu
tiên của một file âm thanh sẽ ngăn cản việc nhận dạng. Vì thế trong công việc này
chúng ta chấp nhận cách giải quyết của luồng chuỗi đặc trưng bằng cách chia thành
những chuỗi đặc trưng con (sub-fingerprint) là những khoảng thời gian nguyên tử đủ
nhỏ (chỉ đến frame). Những chuỗi con này có thể không đủ lớn để tự chúng xác định
các frame, nhưng một khoảng thời gian dài hơn – chứa đủ nhiều frame – sẽ cho phép
nhận dạng chắc chắn và mạnh mẽ.
2.2. Các phương pháp xây dựng và tìm kiếm chuỗi đặc trưng trong ứng dụng
nhận dạng nhạc.
Phần này chúng ta sẽ tìm hiểu hai phương pháp xây dựng và tìm kiếm chuỗi đặc
trưng dùng trong nhận dạng nhạc tiêu biểu hiện nay.
2.2.1. Phương pháp xây dựng hệ thống chuỗi đặc trưng mạnh
Phương pháp này được phát triển bởi Jaap Haitsma và Ton Kalker.
2.2.1.1. Trích rút chuỗi đặc trưng
a) Thuật toán trích chọn
11
Kế hoạch trích chọn chuỗi đặc trưng được đề xuất trong phương pháp này dựa
trên cơ sở phương pháp luồng nói chung. Nó rút ra những chuỗi đặc trưng con 32 bit
cho mỗi khoảng thời gian 11.6 mili giây. Một khối chuỗi đặc trưng bao gồm 256
chuỗi con nối tiếp nhau, tương ứng với granularity chỉ 3 giây. Một qui trình tổng
quan được biểu diễn ở hình 2. Tín hiệu âm thanh đầu tiên được chia đoạn vào các
frame chồng nhau (overlapping). Các frame chồng có độ dài 0.37 giây và có trọng
lượng bằng cửa sổ Hamming với một thừa số chồng 31/32. Kết quả của kế hoạch này
trong việc trích rút của một chuỗi đặc trưng con cho mỗi 11.6 mili giây. Trong
trường hợp xấu nhất các ranh giới của frames sử dụng trong việc nhận dạng là 5.8
mili giây với chú ý là các ranh giới được dùng trong cơ sở dữ liệu của các chuỗi đặc
trưng đã được tính toán trước. Sự chồng lấp lớn đảm bảo rằng thậm chí trong trường
hợp xấu nhất các chuỗi đặc trưng con của đoạn âm thanh được nhận dạng vẫn giống
các chuỗi đặc trưng con của những đoạn giống thế trong cơ sở dữ liệu. Vì sự chồng
lấp lớn các chuỗi đặc trưng con tiếp sau có sự giống nhau nhiều và biến đổi rất chậm
theo thời gian. Hình 3a biểu diễn một ví dụ về khối chuỗi đặc trưng được rút ra và
các đặc trưng biến đổi rất chậm theo thời gian.
Hình 1: Tổng quan về quá trình trích chọn chuỗi đặc trưng.
Các thuộc tính âm thanh thuộc tri giác quan trọng nhất nằm trong miền tần số.
Vì thế một sự biểu diễn quang phổ được tính toán bởi hiệu quả biểu diễn của phép
biến đổi Fourier trên mỗi frame. Vì độ nhạy pha của khai triển Fourier khác ranh giới
của frame và sự kiện mà cơ quan thính giác của con người (Human Auditory System
– HAS) không nhạy với pha, chỉ có giá trị tuyệt đối của phổ là được giữ lại, ví dụ
năng lượng mật độ phổ.
12
Để mà rút ra giá trị chuỗi con 32 bit cho mỗi frame thì các dải tần không chồng
chất 33 được chọn. Những dải tần này nằm trong phạm vi từ 300Hz đến 2000Hz
(phạm vi phổ có liên quan nhất đến HAS) và có một khoảng cách logarit. Khoảng
cách logarit được chọn bởi vì nó được biết đến bởi HAS có tác dụng trên những dải
tần xấp xỉ logarit (vì thế được gọi là thang Bark). Bằng thực nghiệm dải tần được
kiểm tra sự khác nhau của tín hiệu năng lượng (đồng thời theo thời gian và tần số) là
thuộc tính rất mạnh của nhiều loại quá trình xử lý. Nếu chúng ta ký hiệu năng lượng
của dải tần m của frame n là E(n,m) và m bit của chuỗi đặc trưng con của frame là
F(n,m), số bit của chuỗi con được xác định chính thức là (xem khối màu xám trong
hình 2, ở chỗ T là yếu tố trễ):
⎩⎨
⎧
≤−−−−−+−
>−−−−−+−=
0))1,1(),1(()1,(),(0
0))1,1(),1(()1,(),(1
).(
mnEmnEmnEmnifE
mnEmnEmnEmnifE
mnF (2.1)
Hình 2: (a) Khối chuỗi đặc trưng của đoạn nhạc gốc
(b) khối chuỗi đặc trưng của đoạn nhạc đã bị nén
13
(c) sự khác nhau giữa (a) và (b) thể hiện ở những bit lỗi màu đen (BER=0.078)
Hình 2 biểu diễn một ví dụ của 256 chuỗi con 32 bit nối tiếp nhau (ví dụ về một
khối chuỗi đặc trưng), trích ra theo cách trên từ một đoạn trích ngắn của bản “O
Fortuna” của Carl Orff. Bit ‘1’ tương ứng với điểm ảnh trắng và bit ‘0’ tương ứng
với điểm ảnh đen. Hình 2a và hình 2b biểu diễn khối chuỗi đặc trưng tương ứng từ
một đĩa CD gốc và một bản MP3 nén (32Kbps) của cùng một đoạn trích. Lý tưởng
thì hai hình này sẽ được xác định, nhưng vì việc nén một vài bit được tìm lại không
đúng. Những bít lỗi này được sử dụng như độ đo sự giống nhau cho chuỗi đặc trưng
của chúng ta – được biểu diễn bằng màu đen trong hình 2c.
Những tài nguyên tính toán cần cho thuật toán được đề xuất là có giới hạn. Bởi
vì thuật toán chỉ được tính toán với âm thanh nhận được có tần số dưới 2kHz được
lấy mẫu lần đầu tiên thấp xuống từ luồng âm thanh đơn sắc (mono) với tốc độ lấy
mẫu 5kHz. Các chuỗi đặc trưng con được xây dựng có khả năng chống lại sự suy
giảm tín hiệu. Hiện tại các bộ lọc 16 nút FIR đang được sử dụng. Thao tác đòi hỏi
tính toán khắt khe nhất là biến đổi Fourier của mỗi frame âm thanh. Trong tín hiệu
âm thanh được lấy mẫu một frame có độ dài 2048 mẫu. Nếu biến đổi Fourier được
thực thi như một điểm cố định FFT giá trị thực thuật toán chuỗi đặc trưng vừa nói
chạy hiệu quả trên các thiết bị cầm tay như PDA hoặc điện thoại di động.
b) Phân tích khẳng định sai
Hai tín hiệu âm thanh 3 giây được trình bày giống nhau nếu khoảng cách
Hamming (ví dụ số bit lỗi) giữa hai khối chuỗi đặc trưng được suy ra thấp hơn điểm
bắt đầu T một ít. Giá trị điểm bắt đầu T này xác định trực tiếp tỷ lệ khẳng định sai fP ,
ví dụ tỷ lệ của tín hiệu âm thanh không được trình bày trực tiếp bằng: T nhỏ hơn, xác
xuất fP sẽ nhỏ hơn. Mặt khác, giá trị T nhỏ sẽ không ảnh hưởng đến xác xuất phủ
định sai nP , ví dụ xác xuất mà hai tín hiệu ”bằng nhau” nhưng không được xác định.
Để phân tích sự lựa chọn điểm bắt đầu T, chúng ta giả sử rằng quá trình xử lý
việc rút ra chuỗi đặc trưng mang lại các bit i.i.d ngẫu nhiên (i.i.d = independent and
identically distributed – độc lập và được phân bố tương tự nhau). Số bit lỗi sau đó sẽ
có phân phối nhị thức (n,p), trong đó n bằng số bit được lấy ra và p (=0.5) là xác xuất
mà bit 0 hoặc 1 được rút được lấy ra. Từ đó n (=8192=32*256) lớn trong ứng dụng
của chúng ta, phân phối nhị thức có thể xấp xỉ bằng phân phối thông thường với một
giá trị trung bình np=μ và độ lệch chuẩn ))1(( pnp −=σ . Đưa ra khối chuỗi đặc
trưng 1F , xác xuất mà khối chuỗi đặc trưng 2F được chọn ngẫu nhiên có ít hơn
14
nT α= lỗi với 1F được đưa ra bởi:
⎟⎠
⎞⎜⎝
⎛ −== ∫∞− nerfcdxeP n xf 2
)21(
2
1
2
1)(
)21(
2/1 2 α
πα α (2.2)
Trong đó α là kí hiệu của tỷ lệ bit lỗi (Bit Error Rate – BER)
Tuy nhiên, trong thực tế các chuỗi đặc trưng có sự tương quan cao theo thời
gian. Sự tương quan này không chỉ là vì sự tương quan thời gian vốn có trong âm
thanh mà còn bởi sự chồng lấp lớn của các frame được dùng trong việc rút ra chuỗi
đặc trưng. Sự tương quan cao hơn kéo theo một độ lệch chuẩn lớn hơn, như biểu diễn
bởi tham số dưới đây.
Giả sử 1 nguồn đối xứng {-1,1} với xác xuất có kí hiệu ix và 1+ix là giống nhau
và bằng q. Sau đó được biểu diễn:
[ ] kkii axxE =+ (2.3)
Trong đó a=2.q-1. Nếu nguồn Z là độc nhất hoặc 2 chuỗi X và Y, sau đó Z là
đối xứng và
[ ] kkii azzE 2=+ (2.4)
Với N lớn, độ lệch chuẩn trung bình NZ trên N mẫu liên tiếp của Z có thể được
mô tả xấp xỉ bằng phân phối thông thường với giá trị trung bình 0 và độ lệch chuẩn
bằng:
)1(
1
2
2
aN
a
−
+ (2.5)
Thừa số tương quan a giữa các bit chuỗi đặc trưng nối tiếp bao hàm sự tăng lên
trong độ lệch tiêu chuẩn vì tỉ lệ bit lỗi (BER) bởi thừa số:
2
2
1
1
a
a
−
+ (2.6)
Để xác định phân phối của BER với những khối chuỗi đặc trưng thực, một cơ sở dữ
liệu chuỗi đặc trưng của 10000 bài hát được tạo ra. Về sau BER của cơ sở dữ liệu
100000 bài hát được chọn ngẫu nhiên từ những cặp khối chuỗi đặc trưng đã được xác
định. Độ lệch chuẩn của kết quả phân phối BER được đo là 0.0148, cao hơn xấp xỉ 3
lần 0.0055 kỳ vọng từ các bit i.i.d ngẫu nhiên.
15
Hình 3: So sánh xác xuất hàm mật độ của tỷ lệ bit lỗi (BER) được biểu thị bằng
dấu ‘+’ và phân phối thông thường
Hình 3 biểu diễn hàm mật độ xác xuất (Probability Density Function – PDF)
của phân phối BER đã được đo và phân phối thông thường với giá trị trung bình 0.5
và độ lệch tiêu chuẩn 0.0148. Hàm mật độ xác xuất của tỷ lệ bit lỗi là sự xấp xỉ gần
với phân phối thông thường. Đối với những phân phối tỷ lệ bit lỗi dưới 0.45 chúng ta
theo dõi thêm một vài giá trị tham khảo bên ngoài, bởi vì thống kê không đầy đủ. Để
hợp nhất độ lệch chuẩn lớn hơn của phân phối tỷ lệ bit lỗi công thức (2.2) được sửa
bằng cách bao gồm thừa số 3
⎟⎠
⎞⎜⎝
⎛ −= nerfcPf 23
)21(
2
1 α (2.7)
Điểm bắt đầu cho tỷ lệ bit lỗi sử dụng trong các thử nghiệm là α = 0.35. Giá trị trung
bình này vượt qua 8192 bits và phải ít hơn 2867 bits lỗi để mà quyết định những khối
chuỗi đặc trưng bắt nguồn từ những bài hát giống nhau. Sử dụng công thức (2.7)
chúng ta đạt tới tỷ lệ khẳng định sai của erfc(6.4)/2=3.6*10-20 rất thấp.
16
2.2.1.2. Tìm kiếm chuỗi đặc trưng trong cơ sở dữ liệu
Tìm kiếm các chuỗi đặc trưng đã được trích rút trong cơ sở dữ liệu chuỗi đặc
trưng là công việc không đơn giản. Thay vào đó việc tìm kiếm chuỗi đặc trưng dạng
bit dễ dàng hơn, chuỗi đặc trưng gần giống nhất sẽ được tìm ra. Chúng ta trình bày
quá trình tìm kiếm này với các số liệu dựa trên những chuỗi đặc trưng được trích rút
như bên trên. Giả sử cơ sở dữ liệu chuỗi đặc trưng có cỡ vừa phải chứa khoảng
10000 bài hát với độ dài trung bình là 5 phút. Điều này tương đương với xấp xỉ 250
triệu chuỗi đặc trưng con. Để xác định một khối chuỗi đặc trưng có nguồn gốc từ
đoạn âm thanh chưa biết chúng ta phải tìm ra khối chuỗi đặc trưng giống nhất trong
cơ sở dữ liệu. Nói theo cách khác chúng ta phải tìm ra vị trí trong 250 triệu chuỗi đặc
trưng con mà ở đó tỷ lệ bít lỗi là tối thiểu. Đây là quá trình của cách tìm kiếm brute
force. Tuy nhiên phải làm phép so sánh với 250 triệu khối chuỗi đặc trưng. Sử dụng
một máy PC hiện đại thì có thể đạt được tỷ lệ so sánh xấp xỉ 200000 khối chuỗi đặc
trưng trong một giây. Vì thế tổng thời gian tìm kiếm cho mỗi ví dụ sẽ là 20 phút.
Điều này cho thấy tìm kiếm brute force là giải pháp không thể dùng được cho các
ứng dụng thực tế.
Chúng ta sẽ sử dụng một thuật toán tìm kiếm hiệu quả hơn. Thay vì tính toán tỷ
lệ bit lỗi cho mỗi vị trí có thể trong cơ sở dữ liệu như phương pháp tìm kiếm brute
force, ở đây ta chỉ tính toán cho một vài vị trí ứng cử. Những vị trí ứng cử này có xác
xuất rất cao trở thành vị trí phù hợp nhất trong cơ sở dữ liệu.
Trong phiên bản đơn giản của thuật toán tìm kiếm được cải tiến, các vị trí ứng
cử được phát ra trên cơ sở giả sử rằng nó rất phù hợp ít nhất là một chuỗi đặc trưng
con ở vị trí tốt nhất trong cơ sở dữ liệu. Nếu giả thiết này là hợp lý, chỉ những vị trí
cần được kiểm tra là những vị trí mà một trong 256 chuỗi đặc trưng con của truy vấn
khối chuỗi đặc trưng phù hợp hoàn toàn. Để kiểm tra tính hợp lệ của giả thiết này, đồ
thị trong hình 4 thể hiện số bit lỗi trên chuỗi đặc trưng con cho những chuỗi đặc
trưng được mô tả trong hình 2. Nó thể hiện rằng quả thật là có một chuỗi đặc trưng
con không chứa bất kỳ lỗi nào. Trên thực tế 17 trong số 256 chuỗi đặc trưng con
không có lỗi. Nếu chúng ta giả thiết rằng chuỗi đặc trưng “gốc” của hình 2a quả thật
được lấy ra từ trong cơ sở dữ liệu, vị trí của nó sẽ được chọn trong số các vị trí ứng
cử cho “chuỗi đặc trưng MP3@128Kbps” của hình 2b.
17
Hình 4: Bit lỗi trên chuỗi đặc trưng đối với bản MP3@128Kbps trích từ
bài “O Fortuna” của Carl Orff
Các vị trí trong cơ sở dữ liệu mà một chuỗi đặc trưng con 32 bit cụ thể được xác
định để tìm kiếm sử dụng kiến trúc cơ sở dữ liệu trong hình 6. Cơ sở dữ liệu chuỗi
đặc trưng chứa một bảng tra cứu (LUT) với tất cả các chuỗi đặc trưng con 32 bit có
thể có như một mục từ (entry). Mỗi mục từ chỉ rõ một danh sách với các con trỏ đến
những vị trí trong danh sách chuỗi đặc trưng thực nơi mà những chuỗi đặc trưng 32
bit tương ứng được định vị. Trong các hệ thống thực tế với bộ nhớ giới hạn một bảng
tra cứu chứa 232 mục từ thường không khả thi hoặc không thực tế hoặc là cả hai. Hơn
nữa bảng tra cứu sẽ được làm đầy bởi vì chỉ một số giới hạn các bài hát có thể đặt
trong bộ nhớ. Vì thế trong thực tế một bảng băm được dùng thay cho bảng tra cứu.
Chúng ta thực hiện lại tính toán số các phép so sánh khối chuỗi đặc trưng trung
bình trên định dạng đối với 10000 bài hát trong cơ sở dữ liệu. Vì cơ sở dữ liệu chứa
xấp xỉ 250 triệu chuỗi đặc trưng con, số vị trí trung bình trong một danh sách sẽ là
0.0058 (=250*106/1032). Nếu chúng ta giả thiết rằng tất cả các chuỗi đặc trưng con có
khả năng bằng nhau, số phép so sánh chuỗi đặc trưng trung bình trên định dạng chỉ là
15 (=0.058 * 256). Tuy nhiên chúng ta quan sát trong thực tế, vì sự phân phối không
đồng đều của các chuỗi đặc trưng con, số phép so sánh chuỗi đặc trưng tăng lên xấp
18
xỉ 20. Trong 300 phép so sánh trung bình được yêu cầu, thời gian tìm kiếm trung
bình cho mỗi lần là 1.5 mili giây trên một máy PC hiện đại. Bảng tra cứu có thể được
thực thi theo cách mà nó không ảnh hưởng đến thời gian tìm kiếm. Theo giá của
bảng tra cứu, thuật toán tìm kiếm được đề xuất nhanh hơn xấp xỉ 800000 lần phương
pháp brute force.
Một ví dụ về biểu đồ các lỗi bít trên chuỗi đặc trưng đối với một khối chuỗi đặc
trưng mà không chứa bất kỳ chuỗi đặc trưng con không lỗi nào- được thể hiện trong
hình 5.
Hình 5: Bit lỗi trên chuỗi đặc trưng (đường nhạt) và độ tin cậy của bit sai
đáng tin cậy nhất (đường đậm) cho bản MP3@Kbps của “O Fortuna” của Carl
Orff.
Tuy nhiên có những chuỗi đặc trưng con chỉ chứa một lỗi. Vì vậy thay vì chỉ
kiểm tra những vị trí trong cơ sở dữ liệu mà ở đó một trong 256 chuỗi đặc trưng con
xuất hiện, chúng ta có thể kiểm tra toàn bộ các vị trí nơi mà các chuỗi đặc trưng xuất
hiện và có khoảng cách Hamming của một chuỗi với toàn bộ 256 chuỗi đặc trưng
con. Điều này sẽ dẫn đến phép so sánh chuỗi đặc trưng nhiều hơn 33 lần và như vậy
vẫn có thể chấp được. Tuy nhiên, nếu chúng ta muốn đối phó với tình huống mà ví
19
dụ số bit lỗi tối thiểu trên chuỗi đặc trưng con là 3 (điều này có thể xuất hiện trong
ứng dụng điện thoại di động), số phép so sánh chuỗi đặc trưng sẽ tăng lên là 5489,
điều đó dẫn đến thời gian tìm kiếm không được chấp nhận. Chú ý rằng hệ số không
đều 20 bị giảm đi với sự tăng lên của số bit đảo chiều. Ví dụ nếu tất cả 32 bit của các
chuỗi đặc trưng được sử dụng để đảo chiều, chúng ta kết thúc lại với thuật toán brute
force.
Vì những bit đảo chiều ngẫu nhiên phát ra những vị trí ứng cử rất nhanh trong
những khoảng thời gian tìm kiếm không được chấp nhận, chúng ta đề xuất một
phương pháp khác để sử dụng thông tin giải mã mềm. Đó là chúng ta đề nghị ước
lượng và sử dụng xác xuất mà một bit chuỗi đặc trưng được thu nhận đúng.
Các chuỗi đặc trưng con đạt được bằng cách so sánh và tạo ngưỡng năng lượng
khác nhau (xem khối bit gốc trong hình 1). Nếu sự khác nhau về mức năng lượng là
rất gần với điểm bắt đầu, thì có khả năng bit thu nhận được là không đúng (một bit
không tin cậy). Mặt khác, nếu sự khác nhau về mức năng lượng là lớn hơn điểm bắt
đầu thì xác xuất của một bit không đúng là nhỏ (bit đáng tin cậy). Xuất phát từ thông
tin đáng tin cậy đối với mỗi bit của chuỗi đặc trưng con, có thể mở rộng một chuỗi
đặc trưng con được đưa ra thành một danh sách các chuỗi đặc trưng con có thể. Bằng
cách giả sử rằng một trong những chuỗi đặc trưng con có thể nhất có vị trí tối ưu
trong cơ sở dữ liệu, khối chuỗi đặc trưng có thể được xác định như trước đó. Các bit
được chỉ định độ tin cậy có thứ hạng từ 1 đến 32, trong đó 1 là kí hiệu cho độ tin cậy
thấp nhất và 32 là cho bit có độ tin cậy cao nhất.
Những kết quả này theo một cách đơn giản sẽ tạo ra một danh sách những chuỗi
đặc trưng con có thể nhất bằng cách chỉ đảo chiều những bit ít tin cậy nhất. Chính
xác hơn, danh sách bao gồm toàn bộ các chuỗi đặc trưng con có N bit cố định đáng
tin cậy nhất và tất cả các bit có thể thay đổi khác. Nếu thông tin về độ tin cậy là
chính xác, giả sử rằng trong trường hợp một chuỗi đặc trưng con có 3 bit lỗi, những
bit với độ tin cậy 1, 2 và 3 là không chính xác. Nếu đây là trường hợp – các khối
chuỗi đặc trưng mà trong đó số bit lỗi trên một chuỗi đặc trưng con tối thiếu là 3 – có
thể được xác định bằng cách tạo ra những vị trí ứng cử với chỉ 8 (=23) chuỗi đặc
trưng con. So sánh với hệ số 5489 đạt được khi sử dụng tất cả các chuỗi đặc trưng
con với một khoảng cách Hamming của 3 để phát ra các vị trí ứng cử, đây là một cải
tiến với hệ số xấp xỉ 686.
Trong thực tế thông tin về độ tin cậy là không chính xác (ví dụ nó xẩy ra khi
một bit với độ tin cậy thấp được thu nhận chính xác và ngược lại) và vì thế sự cải
20
tiến là ít hiệu quả, nhưng vẫn có ý nghĩa. Điều này có thể thấy trong ví dụ ở hình 5.
Số bit lỗi tối thiểu trên chuỗi đặc trưng con là một. Như vừa đề cập trước đó, khối
chuỗi đặc trưng sau đó có thể được xác định bằng cách phát ra 33 nhịp. Hình 5 cũng
có một biểu đồ về độ tin cậy cho bit đáng tin cậy nhất bị thu nhận sai. Những độ tin
cậy được suy ra từ bản MP3@32Kbps sử dụng phương pháp đã đề xuất trên. Chúng
ta thấy rằng chuỗi đặc trưng con đầu tiên chứa 8 lỗi. Tám bit lỗi này không phải là 8
bit kém nhất bởi vì một trong những bit sai có độ tin cậy được chỉ ra là 27. Vì thế,
thông tin về độ tin cậy luôn luôn không đáng tin. Tuy nhiên nếu chúng ta coi như
chuỗi đặc trưng con 130 – chuỗi mà chỉ có một bit lỗi đơn – thì ta thấy rằng độ tin
cậy của bit sai được chỉ ra là 3. Vì thế khối chuỗi đặc trưng này chỉ đến vị trí chính
xác trong cơ sở dữ liệu chuỗi đặc trưng khi chỉ đảo chiều 3 bit kém nhất. Vì vậy bài
hát sẽ được nhận dạng chính xác.
Hình 6: Trình bày cơ sở dữ liệu chuỗi đặc trưng
Chúng ta sẽ kết thúc phần này bằng cách tham khảo hình 6 và đưa ra một ví dụ
về cách làm việc với thuật toán tìm kiếm đã được đề xuất. Chuỗi đặc trưng rút ra
cuối cùng của khối chuỗi đặc trưng trong hình 6 là 0x00000001. Đầu tiên khối chuỗi
đặc trưng được so sánh với các vị trí trong cơ sở dữ liệu nơi mà chuỗi đặc trưng con
0x00000001 được định vị. LUT chỉ đến chỉ một vị trí cho chuỗi đặc trưng con
0x00000001, một vị trí p nào đó trong bài hát 1. Bây giờ chúng ta tính toán tỷ lệ bit
lỗi giữa 256 chuỗi đặc trưng con được rút ra (khối chuỗi đặc trưng) và các giá trị
chuỗi đặc trưng con của bài hát 1 từ vị trí p-255 lên vị trí p. Nếu tỷ lệ bit lỗi thấp hơn
21
điểm bắt đầu 0.35, xác xuất cao là khối chuỗi đặc trưng đã rút ra có nguồn gốc từ bài
hát 1. Tuy nhiên đây không là trường hợp bài hát không có trong cơ sở dữ liệu hoặc
chuỗi đặc trưng con chứa một lỗi. Chúng ta giả sử bit 0 là bit đáng tin ít nhất. Ứng cử
có thể nhất tiếp theo sẽ là chuỗi đặc trưng con 0x00000000. Vẫn tham khảo trong
hình 6, chuỗi đặc trưng con 0x00000000 có hai vị trí ứng cử có khả năng: một trong
bài hát 1 và một trong bài hát 2. Nếu khối chuỗi đặc trưng có tỷ lệ bit lỗi thấp dưới
điểm bắt đầu đối với khối chuỗi đặc trưng kết hợp trong bài hát 1 hoặc 2, sau đó một
ứng cử phù hợp sẽ được biểu thị cho bài hát 1 hoặc 2 một cách tương ứng. Nếu cả
hai vị trí ứng cử đưa ra thấp dưới tỷ lệ bit lỗi bắt đầu, các chuỗi đặc trưng con có thể
khác được sử dụng để phát ra nhiều vị trí ứng cử hơn, hoặc có một cái chuyển mạch
đến 1 trong 254 chuỗi đặc trưng con còn lại trong đó lặp lại quá trình xử lý như trên.
Nếu tất cả 256 chuỗi đặc trưng con và những chuỗi đặc trưng con có thể nhất của
chúng vừa được dùng để phát ra các vị trí ứng cử và không cái nào phù hợp thấp
dưới điểm bắt đầu vừa được tìm thấy thì thuật toán quyết định rằng nó không thể
nhận dạng bài hát.
2.2.2. Phương pháp xây dựng và tìm kiếm chuỗi đặc trưng dựa trên waveprint
Phương pháp xây dựng này được phát triển bởi Shumeet Baluja và Michele
Covell.
2.2.2.1. Trích rút chuỗi đặc trưng
Chúng ta cũng bắt đầu quá trình xử lý rút ra chuỗi đặc trưng bằng việc chuyển
âm thanh đầu vào thành ảnh phổ như phương pháp của Haitsma. Theo đó chúng ta sử
dụng các ảnh phổ 371ms chia thành các hình ảnh thuộc quang phổ, mỗi hình ảnh dài
11.6 ms, khoảng cách loga là 32 và nằm trong dải tần từ 319Hz đến 2kHz. Việc rút ra
các hình ảnh thuộc phổ đã biết độ dài từ các ảnh phổ cho phép chúng ta tạo ra những
chuỗi đặc trưng con bao gồm những cấu trúc biểu thị thời gian mà không dễ bị ảnh
hưởng bởi những thay đổi theo thời gian. Chúng ta sẽ sử dụng sự hiển thị dựa trên
wavelets.
Đối với mỗi hình ảnh thuộc quang phổ mà chúng ta tạo ra, ta rút ra wavelets cao
nhất theo cường độ của chúng. Wavelets là công cụ toán học để phân tách các hàm
theo thứ bậc. Chúng cho phép một hàm được mô tả bởi toàn bộ hình dạng của nó,
cộng với những chi tiết tăng dần liên tiếp. Giống như việc phân tích Fourier,
wavelets cung cấp một vài mức phân tách theo tần số không gian. Wavelets có thêm
22
thuộc tính của sự hỗ trợ cục bộ, với mỗi sự hỗ trợ của wavelet bao phủ một số lượng
thích hợp các chu kỳ tần số của dải tần của wavelet đó.
Hình 7: Sự hiển thị cho 3 bài hát – 5 frames liên tiếp nhau hiển thị cho mỗi bài,
nhảy qua 0.2 giây. Đối với mỗi bài hát, hàng đầu tiên là hình ảnh phổ ảnh gốc,
hàng thứ 2 là cường độ wavelet, hàng thứ 3 hiển thị 200 sóng đầu tiên (t=200).
Chú ý rằng những wavelet đầu tiên có một mẫu phân biệt với mỗi bài trong 3
bài hát.
Để mô tả một hình ảnh m×n với wavelets, m×n wavelets được trả lại: không có
sự nén. Nếu chỉ một mình nó thì hình ảnh-wavelet không chống đỡ được tiếng ồn
hoặc sự suy giảm âm thanh; sẽ có sự thay đổi của những giá trị này do những thay
đổi nhỏ trong âm thanh (vd một chút tiếng ồn, tiếng vang, những âm thanh nền khác,
hoặc được chơi bằng điện thoại di đông,…). Thay vì sử dụng toàn bộ tập wavelets,
chúng ta chỉ giữ lại những thành phần đặc trưng nhất của bài hát. Theo cách đơn giản,
ta chọn t wavelets đầu (theo cường độ), trong đó t<<m×n. Khi nhìn vào wavelets của
23
những hình ảnh liên tiếp của hai bài hát, chúng ta dễ thấy những mẫu được xác định
cả trong không gian wavelet và thậm chí còn rõ ràng hơn khi t wavelets đầu được giữ
(xem hình 7).
Bước cuối cùng của quá trình tạo ra chuỗi đặc trưng con là lấy vecto wavelet rải
rác mô tả ở trên và tạo ra sự hiển thị ngắn gọn của nó. Ta khảo sát cách dùng của
hàm băm Min (Min-Hash) để tính toán các chuỗi đặc trưng con cho những vecto bit
rải rác này. Một yêu cầu cơ bản của các chuỗi đặc trưng con là chuỗi con v1 và chuỗi
con v2 giống nhau nhau nếu và chỉ nếu tín hiệu wavelet v1 và tín hiệu wavelet v2
tương tự nhau.
Đối với mục đích của phương pháp này, đưa ra hai vecto v1 và v2, ta sẽ chỉ ra
các kiểu phù hợp như bốn kiểu a, b, c, d như biểu diễn trong bảng 1, phụ thuộc vào
các bit tương ứng trong các vecto. Đưa ra những kiểu hợp/không hợp này cần chú ý
rằng với những vecto rải rác, hầu hết các vị trí bit sẽ là kiểu d. Ta sẽ định nghĩa sự
giống nhau của hai vecto là số hàng liên quan có kiểu là a: vd Sim(v1, v2)=a/(a+b+c).
Bảng 1: Các kiểu hợp/không hợp giữa những bit đơn của các vecto nhị phân.
Kiểu Vecto 1 Vecto 2
a 1 1
b 1 0
c 0 1
d 0 0
Một cách tiếp cận trực tiếp với vấn đề này là chọn ngẫu nhiên đơn giản một tập
các vị trí bit và sử dụng chúng như tín hiệu, tuy nhiên nó sẽ không làm việc. Bởi vì
các vecto là rời rạc, các tín hiệu kết quả có khả năng sẽ giống nhau bởi vì chúng hầu
hết được tạo ở 0 giây, tuy nhiên nó sẽ không đưa ra dấu hiệu đúng của sự giống nhau
bởi vì các hàng của kiểu a được quan tâm nhất.
Kỹ thuật hàm băm Min làm việc như dưới sau. Hoán vị các vị trí bit thành một
vài thứ tự ngẫu nhiên (nhưng đã biết). Sau đó với hoán vị này, đo mỗi vecto mà trong
đó ví trí đầu tiên ‘1’ được chỉ ra. Có một chú ý quan trọng là xác xuất mà sự xuất
hiện đầu tiên (v1) bằng sự xuất hiện đầu tiên (v2) là giống nhau và giống xác xuất
a/(a+b+c): giá trị băm được chấp nhận nếu vị trí đầu tiên với 1 trong vecto bit là kiểu
24
a, và chúng không được chấp nhận nếu vị trí đầu tiên là kiểu b hoặc c. Chú ý rằng
xác xuất này giống như Sim(v1, v2) – là cái mà chúng ta cần.
Chúng ta có thể nhắc lại thủ tục trên nhiều lần, mỗi lần với một hoán vị mới của
các vị trí bit. Nếu chúng ta nhắc lại quá trình p lần với p hoán vị khác nhau, chúng ra
nhận được p phép chiếu của vecto bit. Những giá trị p này là tín hiệu cho vecto bit.
Ta có thể so sánh sự giống nhau của các vecto bit bằng cách nhìn vào các giá trị phù
hợp chính xác trong các tín hiệu có độ dài p; với p đủ lớn sẽ rất gần để đạt được sự
giống nhau với các vecto gốc. Trong phương pháp này, ta không giữ sự hiển thị bit
trung gian mô tả ở trên. Thay vào đó ta lưu trữ tín hiệu tính toán của hàm băm Min,
đây là chuỗi chuỗi đặc trưng con cuối cùng của hình ảnh âm thanh.
Trong nghiên cứu này, hàm Min làm giảm cỡ của tín hiệu từ việc biểu diễn
wavelet trung gian được mô tả trong phần này đến sự biểu diễn ngắn gọn của p giá trị.
Có rất nhiều những kỹ thuật khác nhau được sử dụng cho việc làm giảm bậc - trong
số đó có kỹ thuật như Principal Components Analysis (PCA) và Linear Discriminant
Analysis (LDA). Chúng ta chọn sử dụng hàm băm Min bởi một chuỗi các lý do. Đầu
tiên là yêu cầu khả năng tách biệt qua các tín hiệu top wavelet, không yêu cầu khả
năng mô tả. Yêu cầu này có nghĩa là PCA có thể không là sự biểu diễn tốt nhất và
thay vào đó là các phương pháp truyền thống trên cơ sở LDA. Vì các tín hiệu wavelet
hiển thị vecto rời rạc, chúng ta quyết định khảo sát việc sử dụng các kỹ thuật đã được
thiết kế để sử dụng xác xuất tín hiệu phù hợp và tách biệt qua các vecto rời rạc.
Theo cách này, chúng ta phải giảm lượng thông tin từ mỗi ảnh phổ qua ba bước.
Đầu tiên, ta chỉ giữ wavelets đầu của những hình ảnh thuộc phổ, kết hợp với ảnh phổ.
Thứ hai, ta làm giảm wavelets đầu chỉ còn 2 bit. Thứ ba, sử dụng thủ tục hàm băm
Min để làm giảm rõ ràng kết quả vecto bit thành p giá trị và nó trở thành chuỗi phụ
cuối cùng.
Sau những bước này, mỗi hình ảnh thuộc phổ (hoặc đoạn âm thanh có cùng độ
dài) được biểu diễn bằng một chuỗi p số nguyên 8 bit – chuỗi đặc trưng. Tuy nhiên
khi bị nén thì việc tìm ra những tín hiệu ở gần một cách hiệu quả trong không gian p
chiều cũng là công việc không nhẹ nhàng (khi p>50). Thay vào đó, chúng ta sử dụng
1 kỹ thuât gọi tên là Locality-Sensitive Hashing (LSH). Nó không chỉ hiệu quả trong
số lượng các so sánh được yêu cầu (1 phần nhỏ của tập dữ liệu sẽ được khảo sát), mà
còn cung cấp các thuộc tính mạnh về tiếng ồn.
25
2.2.2.2. Tìm kiếm chuỗi đặc trưng
Toàn bộ quá trình tìm kiếm được biểu diễn bằng biểu đồ trong hình 8. Sự khác
nhau đầu tiên trong quá trình tìm kiếm, trong sự so sánh với quá trình tạo ra cơ sở dữ
liệu, là bài hát được chia ra thành các đoạn chồng lấp lên nhau một cách ngẫu nhiên,
đúng hơn là các đoạn chồng lấp lên nhau không đồng nhất.
Hình 8: Toàn bộ quá trình mô tả và tìm kiếm chuỗi đặc trưng.
26
Sau khi đoạn âm thanh được tạo ra, các tín hiệu của nó được tính toán chính xác
giống như mô tả trong quá trình tạo ra cơ sở dữ liệu chuỗi đặc trưng như trên. Tiếp
theo ta mô tả kỹ thuật cho việc tìm ra những bản phù hợp trong cơ sở dữ liệu.
Như trên đã nói chúng ta sẽ sử dụng LSH cho qua trình tìm kiếm. Trái ngược
với hàm băm chuẩn, LSH thực hiện một chuỗi các hàm băm, mỗi hàm khảo sát chỉ
một vị trí của chuỗi đặc trưng con. Mục đích là phân chia các vecto thuộc tính thành l
vecto con và băm mỗi điểm thành l bảng băm riêng biệt, mỗi bảng băm sử dụng một
trong các vecto con như đầu vào của hàm băm. Các ứng cử gần nhau có thể phục hồi
hiệu quả bằng cách phân chia các vecto thuộc tính thử nghiệm và thu thập các mục
trong các khối băm tương ứng. Danh sách những ứng cử gần nhau cuối cùng có thể
được tạo ra bằng cách biểu quyết đếm, với mỗi số biểu quyết hàm băm cho các mục
của khối đã được đánh chỉ mục và giữ lại các ứng viên nhận được số bình chọn tối
thiểu v. Nếu v = 1 thì hợp với các danh sách ứng viên. Nếu v = l thì giao nhau.
LSH cũng hỗ trợ các ràng buộc linh động trong các ứng viên từ các bảng băm
thành phần độc lập sẽ được khảo sát xa hơn như danh sách cuối cùng của các ứng
viên phù hợp. Sự linh động này đạt được bằng cách thêm một yêu cầu cho việc tối
thiểu các biểu quyết bảng băm thành phần. Mỗi bảng băm thành phần biểu quyết cho
chuỗi đặc trưng con được phục hồi sử dụng p/l byte. Sau đó, chỉ những chuỗi phụ
này với v thành phần biểu quyết tối thiểu được giữ lại. Ví dụ, thiết lập v=1, một ứng
viên chỉ phù hợp với một trong những miền con theo thứ tự trong danh sách ứng viên
cuối cùng. Tại điểm cực trị ngược lại, thiết lập v=l, ứng viên phải phù hợp với tất cả
các miền con và LSH điều khiển xác định (mặc dù không hiệu quả) đến 1 bảng băm
chuẩn.
Các chuỗi đặc trưng có ít nhất v biểu quyết sau đó được so sánh với truy vấn
chuỗi đặc trưng con. Bởi vì mỗi byte của chuỗi đặc trưng con là một tín hiệu hàm
băm Min nên ta nhìn vào số byte (lớn hơn p) phù hợp một cách chính xác. Chuỗi đặc
trưng con với số điểm tối đa là tín hiệu phù hợp nhất trong hình ảnh quang phổ đó.
27
CHƯƠNG 3: ỨNG DỤNG THỬ NGHIỆM
3.1. Phát biểu bài toán
Nhận dạng nhạc số là một dạng của ứng dụng liên thông âm thanh nằm trong
chuỗi các ứng dụng của chuỗi đặc trưng âm thanh. Xuất phát từ nhu cầu thực tế,
khóa luận này hướng tới việc xây dựng một ứng dụng thử nghiệm dùng để nhận
dạng nhạc mà mục tiêu là nhận ra chính xác một bài hát từ một mẫu âm thanh nhỏ
được chơi trên các thiết bị khác nhau như điện thoại di động hoặc phát qua radio.
Gần đây, vấn đề nhận dạng nhạc thu hút sự chú ý đáng kể, cả từ các công ty
thương mại như AT&T Wireless ( Musikube
( Shazam Entertainment ( cho
đến các nhà nghiên cứu như J.Haitsma, T.Kalker…. Tuy nhiên, công việc này vẫn
luôn là thách thức, đặc biệt là đối với các truy vấn thế giới thực. Vấn đề mà một ứng
dụng nhận dạng nhạc kiểu này có thể gặp phải là: Đầu tiên, truy vấn có thể bị sai lệch
bởi sự không chính xác gây ra do những thiết bị ghi âm bỏ túi điển hình hoặc do
tiếng ồn từ những âm thanh xung quanh. Thứ hai, mẫu âm thanh từ truy vấn sẽ chỉ
hợp với một phần chia nhỏ của bài hát đích, như tín hiệu số truyền thống tính toán
trên truy vấn không chắc hợp với tín hiệu của toàn bộ bài hát. Thứ ba, một hệ thống
nhận dạng nhạc trong thực tế nên có cùng tỷ lệ cả trong độ chính xác và tốc độ đến
cơ sở dữ liệu chứa hàng trăm nghìn bài hát khác nhau.
3.2. Tổng quan hệ thống
Trên cơ sở mô hình chung cho các ứng dụng nhận dạng âm thanh dựa vào nội
dung như trong hình 9, ứng dụng thử nghiệm được xây dựng dựa trên hệ thống phát
triển bởi Yan Ke. Hệ thống sử dụng những kỹ thuật về học máy để phát triển một
thuật toán chuỗi đặc trưng âm thanh cho nhận dạng nhạc số. Khi đưa ra 10 giây nhạc
của một bản ghi có chất lượng thấp qua điện thoại di động chẳng hạn, hệ thống sẽ
nhận dạng chính xác bài hát trong một cơ sở dữ liệu gồm rất nhiều bài hát.
28
Hình 9: Mô hình chung của các ứng dụng nhận dạng nhạc dựa vào nội
dung.
Trong ứng dụng này sử dụng phương pháp computer vision (một kỹ thuật mạnh
cho việc phân tích dữ liệu âm thanh) để lựa chọn ra các thuộc tính trong quá trình
trích rút ra chuỗi đặc trưng. Ta coi ảnh phổ của mỗi đoạn nhạc như một hình ảnh 2-D
và chuyển việc nhận dạng nhạc thành vấn đề tìm kiếm và phục hồi lại ảnh con bị
hỏng. Bằng việc sử dụng thuật toán pairwise boosting trên một tập lớn các thuộc
tính, hệ thống của chúng ta biết thỏa thuận, phân biệt các kí hiệu nhận diện cục bộ
tuân theo chỉ mục có hiệu quả. Trong giai đoạn tìm kiếm, chúng ta tìm lại được tập
những đoạn trích ngắn của bài hát phù hợp với mẫu âm thanh truy vấn và sử dụng
việc kiểm tra hình học trong sự liên kết với một mô hình EM-based “occlusion” để
xác định bài hát phù hợp nhất với tín hiệu được theo dõi. Chúng ta thực thi thuật toán
trong một hệ thống cụ thể mà có thể nhận ra nhanh chóng và chính xác nhạc từ
những mẫu âm thanh ngắn trong sự biểu diễn không rõ ràng như chất lượng thu âm
kém và có tiếng ồn xung quanh.
3.2.1. Mô tả âm thanh và trích rút chuỗi đặc trưng
Hệ thống này sử dụng kiến trúc cơ bản là kỹ thuật chuỗi đặc trưng âm thanh để
mô tả xúc tích các tín hiệu âm thanh. Nó sử dụng các cửa sổ chồng của âm thanh đơn
sắc từ đó rút ra những thuộc tính đáng quan tâm. Các cửa sổ chồng phải được sử
dụng để duy trì sự bất biến về thời gian cho cho các trường hợp trong đó sự liên kết
thời gian chính xác chưa được biết. Sự hiển thị phổ của âm thanh có thể được xây
dựng bằng nhiều cách: bằng cách đo năng lượng của MFCCs (Mel Frequency
29
Cepstrum Coefficients) hoặc BFCCs (Bark Frequency Cepstrum Coefficients). Trong
nghiên cứu này sẽ sử dụng BFCCs. 33 dải BFCCs được sử dụng nằm trong thứ tự
300Hz-2000Hz. Với mỗi 11.6 mili giây một chuỗi đặc trưng con được tạo ra để bao
hàm một frame dài 370 mili giây. Sự chồng lấp lớn trong các frame kế tiếp đảm bảo
rằng các chuỗi đặc trưng con biến đổi chậm theo thời gian. Các chuỗi đặc trưng con
32 bit cho biết sự khác nhau trong việc tăng hay giảm các dải BFCCs liên tiếp trong
các frame liên tiếp nhau. Đưa ra những chuỗi này làm sự so sánh trở nên đơn giản
hơn. Khi đó sự khác nhau giữa các frame là khoảng cách Hamming của các chuỗi
đặc trưng. Các chuỗi đặc trưng con được sử dụng trong hệ thống là nhỏ gọn và được
tính toán nhanh.
Ngoài ra hệ thống cũng sử dụng một phương pháp nghiên cứu nữa vào quá trình
xử lý lựa chọn các thuộc tính. Đó là phương pháp nghiên cứu trên cơ sở Adaboost
thường được dùng trong các ứng dụng computer vision, nó cho phép các tín hiệu âm
thanh 1-D có thể được xử lý như một hình ảnh khi quan sát trong sự hiển thị tần số
thời gian 2-D. Vấn đề cơ bản của việc lựa chọn các thuộc tính là khả năng tách bạch
vùng hình chữ nhật được phân biệt giữa hai frame khi chúng giống nhau (đó là khi 1
trong 2 frame bị suy biến bởi tiếng ồn) và khi chúng khác nhau.
3.2.2. Tìm kiếm chuỗi đặc trưng phù hợp
Sau khi xây dựng các tín hiệu (là các chuỗi đặc trưng) cho tất cả các bài hát
trong cơ sở dữ liệu chúng ta tiến hành tìm kiếm. Trong thời gian tìm kiếm, ta thực thi
một sự tìm kiếm giống nhau cho các kí hiệu mô tả của đoạn truy vấn dựa vào cơ sở
dữ liệu tín hiệu này. Cỡ của cơ sở dữ liệu lớn và số truy vấn yêu cầu cao cho mỗi
đoạn thúc đẩy chúng ta cố tìm cho được sự sắp xếp hiệu quả cho việc tìm kiếm tương
tự trong không gian kí hiệu mô tả nhiều chiều (tiêu biểu là 32-bit). Một sự lựa chọn
tự nhiên là sử dụng hàm băm vị trí nhạy cảm (locality-sensitive hashing - LSH), một
kĩ thuật có thể xấp xỉ những tìm kiếm tương tự trong thời gian tuyến tính nhỏ, nhất là
bởi vì nó rất phù hợp với khoảng cách Hamming. Các thử nghiệm ban đầu của chúng
ta sử dụng LSH cho ra những kết quả xuất sắc nhưng có một chút ngạc nhiên khi mà
phát hiện ra rằng các kí hiệu mô tả của chúng ta mạnh đến nỗi mà chỉ mục hóa trực
tiếp (direct indexing) sử dụng một bẳng băm kinh điển làm giảm nhiều thời gian
chạy (running time) mà không ảnh hưởng lớn đến độ chính xác. Chúng ta mô tả qua
về phương pháp chỉ mục này.
30
Ta băm tất cả các tín hiệu vào một bảng băm chuẩn (có khóa là các kí hiệu mô
tả M-bit thích hợp). Sau đó định nghĩa những kí hiệu mô tả này trong phạm vi
khoảng cách Hamming là 2 từ truy vấn được đưa ra gần nhau. Những kí hiệu này
được phục hồi với chuỗi dò tìm kĩ lưỡng dưới đây. Đầu tiên, chúng ta thăm dò bảng
băm với truy vấn; nó phục hồi tất cả những bản phù hợp trong phạm vi khoảng cách
Hamming là 0. Tiếp theo, chúng ta thêm M vào hàm băm, gồm có kí hiệu mô tả truy
vấn với một bit đơn đảo chiều; nó tìm thấy sự phù hợp ở khoảng cách Hamming là 1.
Cuối cùng, chúng ta lặp lại quá trình này với mỗi sự kết hợp của hai bit đảo chiều để
phục hồi những kí hiệu mô tả này ở khoảng cách Hamming là 2. Trong khi phương
pháp xuất hiện ban đầu không hiệu quả, như vừa quan sát thì thấy rằng nó nhanh hơn
đáng kể so với LSH cho ứng dụng của chúng ta bởi vì mỗi mẫu thử là không đắt và
nó trả lại kết quả chính xác hơn là những kết quả xấp xỉ. Chúng ta quan sát thấy rằng
việc sử dụng khoảng cách Hamming thay vì phân loại độ tin cậy làm nền tảng cho sự
giống nhau của kí hiệu mô tả là sự xấp xỉ hợp lý, từ đó ta tìm ra độ tin cậy đánh giá
cho các lớp phân loại yếu khác nhau gần bằng nhau trong thử nghiệm của chúng ta.
Mỗi lần trong tất cả các bài hát gần giống nhau vừa được tìm thấy, chúng ta cần
xác định bài hát phù hợp nhất với tập kí hiệu mô tả trong truy vấn. Đúng hơn là việc
chọn lựa đơn giản trên cơ sở số bài phù hợp, chúng ta sử dụng sự kiểm tra có dạng
hình học mà tương tự với việc sử dụng trong nhận dạng đối tượng dùng các thuộc
tính cục bộ. Đối với mỗi bài hát ứng cử, chúng ta xác định kí hiệu mô tả nào phù hợp
theo thời gian. Vì điều này ta sử dụng RANSAC để lặp lại thông qua sự liên kết thời
gian ứng cử và sử dụng căn cứ EM. Chúng ta khảo sát hai mô hình liên kết. Đầu tiên
cho rằng truy vấn có thể được chỉ đến một tín hiệu gốc với một tham số đơn (độ dịch
của thời gian) vừa được xác định. Trong trường hợp này tập tối thiểu là một tập các
cặp kí hiệu mô tả đơn phù hợp. Mô hình thứ hai cho rằng truy vấn có thể là phiên bản
gốc được chia tỷ lệ (kéo dài tuyến tính hoặc bị nén). Mô hình này được định nghĩa
bởi hai tham số (tỷ lệ tốc độ và độ dịch) và yêu cầu một tập tối thiểu hai kí hiệu mô
tả phù hợp. Các mô hình làm méo biểu thị thời gian phức tạp hơn có thể thực hiện
được. Trong thực tế, ta thấy rằng mô hình đầu tiên đưa ra các kết quả chính xác đặc
biệt là từ khi các đoạn truy vấn của chúng ta ngắn gọn. Ta cũng thấy rằng RANSAC
hội tụ tại ít hơn 500 bước lặp thậm chí trong sự hiện diện của nút thắt quan trọng. Tất
cả các ứng cử vừa được tìm thấy được sắp xếp lại chỉ một lần, chúng ta chọn bài hát
với căn cứ EM tốt nhất và thừa nhận rằng nó vượt qua điểm bắt đầu nhỏ nhất.
31
3.3. Thực thi chương trình
Ứng dụng tìm kiếm nhạc bao gồm hai phần: chương trình phục vụ nhận dạng
nhạc và giao diện người dùng đồ họa (GUI), nó có thể chạy trên những máy khác
nhau và giao tiếp trên các socket. Đầu tiên chúng ta mô tả cách tạo ra cơ sở dữ liệu
tín hiệu âm thanh sau đó mô tả giai đoạn truy vấn và cuối cùng đề cập đến giao diện
người dùng.
Với mỗi bài hát trong cơ sở dữ liệu, chúng ta xây dựng một tín hiệu âm thanh
như mô tả dưới đây; quá trình xử lý trước giống với quá trình xử lý sau sử dụng trên
đoạn truy vấn. Đầu tiên chúng ta tính toán ảnh phổ theo cách đã mô tả trên. Ta
chuyển mỗi bài hát thành đơn sắc và lấy mẫu xuống 5512.5 KHz. Đối với một tín
hiệu âm thanh chất lượng CD lấy mẫu ở 44.1 KHz, chúng ta quấn lại tín hiệu với một
bộ lọc và chia mỗi cái ra 8 mẫu . Tiếp theo chúng ta áp dụng một biến đổi Fourier
ngắn với một khung cỡ 2048 mẫu (0.372s) với các khung kế tiếp bởi 64 mẫu (11.6s).
Chúng ta chia nguồn năng lượng giữa 300Hz và 2000 Hz thành 33 dải theo không
gian logarit. Dãy tần số này phù hợp với dãy mà có thể dễ dàng truyền trên điện thoại
di động. Chúng ta sử dụng khoảng cách logarit từ đó phân phối năng lượng của âm
thanh đặc trưng điển hình xấp xỉ loga qua tần số. Cuối cùng, ta áp dụng 32 bộ lọc đã
nghiên cứu và các điểm bắt đầu để lấy được cái kí hiệu mô tả 32-bit cho mỗi bước
thời gian (11.6ms) của tín hiệu; chuỗi kí hiệu mô tả này được biết đến như là tín hiệu.
Đối với độ dài trung bình của một bài hát là 200 giây thì yêu cầu lưu trữ cho việc
hiển thị nó là xấp xỉ 70KB. Chúng ta tải tất cả các kí hiệu mô tả vào trong bộ nhớ và
đặt chúng vào trong một bảng băm cùng với id của bài hát và id của frame (độ dịch
của thời gian). Mặc dù sự thực thi bộ nhớ chính làm việc tốt với vài nghìn bài hát
nhưng những phương pháp khác có thể là cần thiết đối với những cơ sở dữ liệu lớn
hơn.
Trong suốt giai đoạn truy vấn, chương trình phục vụ nhận dạng nhạc xây dựng
một tập các kí hiệu mô tả 32-bit giống nhau cho đoạn âm thanh. Với mỗi kí hiệu mô
tả, nó tìm ra tất cả các kí hiệu mô tả mà trong phạm vi khoảng cách Hamming 2 bit
(theo kinh nghiệm là xác định sự cân bằng tốt giữa độ chính xác và sự phù hợp).
Cuối cùng, chúng ta thực hiện sự liên kết hình học sử dụng RANSAC và tìm ra bản
phù hợp nhất theo căn cứ EM.
Giao diện người dùng (GUI) ghi lại các đoạn âm thanh từ micro và gửi dưới
dạng sóng đến server để nhận dạng. Hình 10 hiển thị một screenshot của GUI của hệ
thống. Phần dưới cùng bên trái và bên phải của khung hiển thị ảnh phổ của bản thu
32
âm và bài hát gốc, lần lượt theo thứ tự riêng rẽ. Mặc dù ảnh phổ thô nhìn khác do
tiếng ồn và sự tắc nghẽn nhưng trông nó vẫn có cấu trúc tương tự. Khung văn bản
đưa ra tên của bài hát được nhận dạng chính xác.
Hình 10: Ảnh phổ của truy vấn được thu âm và ảnh phổ của bài hát được
nhận dạng chính xác.
3.4. Đánh giá hiệu quả của ứng dụng thử nghiệm
3.4.1.1. Cài đặt thử nghiệm
Chúng ta xây dựng bộ thử nghiệm có dữ liệu huấn luyện bao gồm 78 bài hát
được chơi trên loa có chất lượng thấp và được thu âm sử dụng micro chất lượng thấp,
được chỉ đến bản gốc sử dụng các bộ lọc mồi. Tiếp theo, ta thu âm lại dữ liệu kiểm
tra trong một môi trường khác sử dụng phòng ghi âm, máy tính, loa và micro khác.
Các thử nghiệm sử dụng hai tập kiểm tra trong thế giới thực được thiết kế để minh
họa các trường hợp xấu nhất. Đầu tiên bao gồm 71 bài hát chơi ở âm lượng nhỏ và
được ghi âm lại với một chiếc micro bị bóp méo (biểu diễn “Test A”). Thứ hai tập
33
khó hơn chứa 220 bài hát được thu với một bản ghi rất ồn (biểu diễn “Test B”).
Trong nhiều trường hợp, tiếng ồn át tiếng nhạc nhiều đến nỗi mà bài hát trở nên
nghèo nàn đến nỗi mà khó có thể nghe thấy tiếng nhạc. Những bản ghi âm này lấy ra
từ cơ sở dữ liệu của 145 album với 1862 bài hát trải rộng trên rất nhiều thể loại nhạc
bao gồm nhạc cổ điển, jazz, rock và pop. Từ đó mỗi truy vấn có thể có 1861 khả
năng sai, ranh giới chính xác của công việc này chỉ là 0.05%.
3.4.2. Hiệu quả của hệ thống
Hình 11: Tốc độ tìm kiếm bài hát trên tập dữ liệu kết hợp với các đoạn
truy vấn âm thanh có độ dài khác nhau
Hình 11 hiển thị tốc độ tìm kiếm bài hát trên tập test kết hợp A và B với các
đoạn truy vấn từ 10-15 giây tương ứng với 860 và 1290 kí hiệu mô tả, tách biệt nhau.
Chúng ta thấy rằng các truy vấn dài hơn cải thiện không đáng kể các kết quả tìm
kiếm. Trong một hệ thống thực tế người sử dụng mong muốn đạt được độ chính xác
lý tưởng trong khi sử dụng một truy vấn ngắn nhất có thể.
34
Hình 12: Đường cong P-R cho việc tìm kiếm ở mức bài hát trên những tập
dữ liệu riêng biệt với những truy vấn có độ dài 10 giây
Hình 12 biểu diễn các kết quả cho những tập dữ liệu riêng biệt trên các bản ghi
âm có độ dài 10 giây. Đối với Test A, chúng ta đạt được 90% độ hồi tưởng với độ
chính xác 96%. Test B có nhiều thử thách hơn nhưng chúng ta vẫn có thể đạt được
80% độ hồi tưởng với độ chính xác 93%.
Hình 13: Tác động của điểm bắt đầu với khoảng cách Hamming trong việc
tìm kiếm bài hát
35
Hình 13 biểu diễn tốc độ tìm kiếm bài hát đối với điểm bắt đầu có khoảng cách
Hamming là 0, 1 và 2 bit trong Test A. Hiệu quả cải thiện khi chúng ta cho phép
nhiều bit lỗi hơn, nhưng sự tăng biên thấp đi sau khoảng cách là 1 trong khi thời gian
truy vấn tiếp tục tăng theo hàm mũ, vì thế quyết định của chúng ta giới hạn việc tìm
kiếm kí hiệu mô tả gần nhau trong phạm vi 2 bit.
36
KẾT LUẬN
Khóa luận đã trình bày một cách tổng quan về hệ thống chuỗi đặc trưng âm
thanh và các ứng dụng phổ biến của nó. Trong khóa luận cũng trình bày chi tiết hai
phương pháp khác nhau về việc trích rút ra chuỗi đặc trưng âm thanh của một đoạn
âm thanh và cách thức tìm kiếm chuỗi đặc trưng phù hợp với nó trong một cơ sở dữ
liệu lớn. Qua đó chúng ta đã có hình dung khái quát về chuỗi đặc trưng – một nền
tảng quan trọng trong các ứng dụng liên quan đến âm thanh.
Trong phần cuối của khóa luận cũng đã xây dựng được một hệ thống thử
nghiệm ứng dụng chuỗi đặc trưng trong việc nhận dạng nhạc số. Ứng dụng mới dừng
lại ở việc nhận dạng các bài hát trên một tập cơ sở dữ liệu nhỏ. Sau này ứng dụng sẽ
tiếp tục được hoàn thiện với việc nghiên cứu cải tiến độ chính xác của thuật toán tìm
kiếm và mở rộng ra nghiên cứu các thuộc tính của chương trình bằng cách chỉ mục
hóa những bộ sưu tập nhạc lớn hơn.
Hi vọng rằng khóa luận này sẽ góp phần khuyến khích các nghiên cứu sâu hơn
nữa về chuỗi đặc trưng của các đối tượng đa phương tiện trong tương lai(bao gồm cả
âm thanh và hình ảnh nói chung) nhằm mục đích tạo ra nhiều ứng dụng tiện ích phục
vụ cuộc sống của con người.
37
TÀI LIỆU THAM KHẢO
[1] Baluja, Covell, Content fingerprinting using wavelets, Proceedings of the 3rd
European.
Conference on Visual Media Production (CVMP), 2006.
[2] P. Cano, E. Batlle, T. Kalker, J. Haitsma, A review of algorithms for audio
fingerprinting, In Workshop on Multimedia Signal Processing, 2002.
[3] J. Haitsma, T. Kalker, A Highly Robust Audio Fingerprinting System,
Proceedings of International Conference for Music Information Retrieval, 2002.
[4] Y. Ke, D. Hoiem, R. Sukthankar, Computer Vision for Music Identification,
Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern
Recognition (CVPR), 2005.
[5] Y. Ke et al., Computer vision for music identification: server code,
yke/musicretrieval/musicretr-1.0.tar.gz, 2005.
[6] Website Auditude
[7] Website Napster
[8] Website Music Brainz
[9] Website Shazam
[10] Website Tunatic
[11] Website Yacast
Các file đính kèm theo tài liệu này:
- LUẬN VĂN-CHUỖI ĐẶC TRƯNG ÂM THANH VÀ ỨNG DỤNG TRONG TÌM KIẾM NHẠC SỐ.pdf