Khóa luận Chuỗi đặc trưng âm thanh và ứng dụng trong tìm kiếm nhạc số

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Bùi Thanh Xuân

CHUỖI ĐẶC TRƯNG ÂM THANH VÀ ỨNG DỤNG

TRONG TÌM KIẾM NHẠC SỐ

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY

Ngành: Công nghệ thông tin

HÀ NỘI – 2009

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Bùi Thanh Xuân

CHUỖI ĐẶC TRƯNG ÂM THANH VÀ ỨNG DỤNG

TRONG TÌM KIẾM NHẠC SỐ

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY

Ngành: Công nghệ thông tin

Cán bộ hướng dẫn: TS. Nguyễn Hải Châu

HÀ NỘI – 2009

LỜI CẢM ƠN

Trong thời gian qua, để tìm hiểu và hoàn thành khóa luận tốt nghiệp này tôi đã

nhận được nhiều sự giúp đỡ từ gia đình, thầy cô và bạn bè.

Tôi xin được bày tỏ lòng biết ơn chân thành đến các thầy cô giáo trường Đại

Học Công Nghệ đã dậy dỗ tôi trong suốt bốn năm học vừa qua. Đặc biệt, tôi xin

được gửi lời cảm ơn chân thành đến TS. Nguyễn Hải Châu, người đã giúp tôi lựa

chọn đề tài, hướng dẫn tìm tài liệu, đưa ra những nhận xét quan trọng và sửa chữa sai

sót giúp tôi trong quá trình tôi thực hiện đề tài.

Tôi cũng xin được gửi lời cảm ơn đến những người bạn đã luôn quan tâm giúp

đỡ tôi, chia sẻ nhiều kinh nghiệm hay với tôi trong quá trình học tập và làm việc.

Cuối cùng, tôi xin được gửi lời cảm ơn sâu sắc đến gia đình tôi, những người đã

luôn bên cạnh cổ vũ, động viên tôi, tạo mọi điều kiện tốt nhất giúp tôi hoàn thành tốt

khóa luận này.

TÓM TẮT NỘI DUNG

Những năm gần đây đã chứng kiến sự phát triển mạnh mẽ của khoa học và

ngành công nghiệp tính toán các đặc trưng của các đối tượng đa phương tiện. Khái

niệm chuỗi đặc trưng âm thanh ra đời có ý nghĩa quan trọng trong việc phát triển các

ứng dụng liên quan đến âm thanh nhờ đó mang lại rất nhiều tiện ích cho cuộc sống

hiện đại của con người. Một trong những ứng dụng của chuỗi đặc trưng âm thanh

đang rất được quan tâm hiện nay là nhận dạng nhạc số. Trên thế giới đã có rất nhiều

ứng dụng về nhận dạng nhạc được phát triển với các phương pháp khác nhau và thu

được những kết quả khác nhau, song không phải tất cả các trong số chúng đều trả về

kết quả chính xác. Trên cơ sở nghiên cứu về chuỗi đặc trưng âm thanh và những ứng

dụng của nó, khóa luận này hướng đến việc xây dựng một hệ thống nhận dạng nhạc

rất tiện ích với người dùng cho phép trả về thông tin chính xác của một bản nhạc

được chơi qua một thiết bị di động chỉ với vài giây âm thanh. Khóa luận tốt nghiệp

này được thực hiện trong khuôn khổ đề tài nghiên cứu mang mã số QC.08.01 Đại

học Quốc gia Hà Nội.

MỤC LỤC

LỜI MỞ ĐẦU...........................................................................................................1

CHƯƠNG 1: TỔNG QUAN VỀ CHUỖI ĐẶC TRƯNG ÂM THANH VÀ CÁC

ỨNG DỤNG .............................................................................................................3

1.1 Giới thiệu.........................................................................................................3

1.2 Các khái niệm chuỗi đặc trưng âm thanh........................................................3

1.2.1 . Định nghĩa chuỗi đặc trưng âm thanh ...................................................3

1.2.2 . Các tham số của hệ thống chuỗi đặc trưng âm thanh.............................5

1.3 Các ứng dụng ..................................................................................................6

1.3.1 . Broadcast Monitoring (BM)...................................................................6

1.3.2 . Ứng dụng liên thông âm thanh...............................................................6

1.3.3 . Công nghệ lọc chia sẻ file ......................................................................7

1.3.4 . Tổ chức thư viện âm nhạc tự động.........................................................8

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..............................................................................................9

2.1. Nguyên tắc cơ bản xây dựng hệ thống chuỗi đặc trưng âm thanh.................9

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.............................................................................................................10

2.2.1. Phương pháp xây dựng hệ thống chuỗi đặc trưng mạnh.......................10

2.2.1.1. Trích rút chuỗi đặc trưng ................................................................10

2.2.1.2. Tìm kiếm chuỗi đặc trưng trong cơ sở dữ liệu ...............................16

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

..........................................................................................................21

2.2.2.1. Trích rút chuỗi đặc trưng ................................................................21

2.2.2.2. Tìm kiếm chuỗi đặc trưng...............................................................25

CHƯƠNG 3: ỨNG DỤNG THỬ NGHIỆM .........................................................27

3.1. Phát biểu bài toán.........................................................................................27

3.2. Tổng quan hệ thống .....................................................................................27

3.2.1. Mô tả âm thanh và trích rút chuỗi đặc trưng ........................................28

3.2.2. Tìm kiếm chuỗi đặc trưng phù hợp.......................................................29

3.3. Thực thi chương trình ..................................................................................31

3.4. Đánh giá hiệu quả của ứng dụng thử nghiệm..............................................32

3.4.1. Cài đặt thử nghiệm................................................................................32

3.4.2. Hiệu quả của hệ thống...........................................................................33

KẾT LUẬN.............................................................................................................36

TÀI LIỆU THAM KHẢO ......................................................................................37

LỜI MỞ ĐẦU

Trong thực tế có khi chúng ta sẽ gặp phải một tình huống thế này: bạn đang

ngồi trong xe ô tô nghe radio, đang trên xe bus hoặc trong quán cà phê nghe nhạc và

bỗng nhiên bạn nghe được một bài hát rất thu vị. Đó là bài hát mới rất hay mà bạn

từng được nghe sau một khoảng thời gian dài, nhưng bạn đã bỏ lỡ mất phần thông tin

về bài hát và không nhận ra nghệ sĩ đang biểu diễn bài hát đó. Mặc dù vậy bạn vẫn

muốn biết một số thông tin về bản nhạc này. Khi đó bạn nên làm gì? Bạn có thể gọi

đến đài phát thanh để hỏi hay hỏi những người xung quanh nhưng đôi khi điều đó

hơi bất tiện. Nếu bạn có thể nhấn một vài phím trên điện thoại di động và vài giây

sau điện thoại sẽ trả lời cho bạn tên của nghệ sĩ và tên của bản nhạc mà bạn đang

nghe thì có phải tốt hơn không? Thậm chí có thể có một email sẽ được gửi đến hòm

thư của bạn với một vài thông tin được bổ sung thêm.

Xuất phát từ nhu cầu thiết thực đó, nhiều phần mềm nhận dạng nhạc kiểu này

dựa trên các công nghệ khác nhau đã ra đời tuy nhiên không nhiều trong số đó đáp

ứng tốt mong muốn của người dùng và trở nên phổ biến.

Trong khóa luận này sẽ thảo luận về hệ thống chuỗi đặc trưng âm thanh – một

nền tảng quan trọng có thể giúp tạo ra viễn cảnh như chúng ta vừa đề cập bên trên.

Bằng cách sử dụng chuỗi đặc trưng (fingerprint) của một đoạn âm thanh chưa biết

như một truy vấn trong cơ sở dữ liệu chuỗi đặc trưng, cơ sở dữ liệu này chứa các

chuỗi đặc trưng của một thư viện rất nhiều bài hát, và khi đó đoạn âm thanh có thể

được xác định. Điểm cốt lõi của vấn đề được trình bày là phương pháp trích rút chuỗi

đặc trưng và chiến lược tìm kiếm chuỗi đặc trưng rất hiệu quả, nó cho phép tìm kiếm

một cơ sở dữ liệu chuỗi đặc trưng lớn chỉ với những tài nguyên tính toán gới hạn.

Khóa luận gồm ba chương:

Chương 1: Tổng quan về chuỗi đặc trưng âm thanh và các ứng dụng. Chương

này trình bày một cách tổng quan nhất những khái niệm cơ bản liên quan đến chuỗi

đặc trưng âm thanh và những ứng dụng phổ biến của chuỗi đặc trưng âm thanh.

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.

Trình bày hai phương phát trích rút và tìm kiếm chuỗi đặc trưng âm thanh phổ biến

hiện nay trong các ứng dụng nhận dạng nhạc là phương pháp xây dựng chuôi đặc

trưng mạnh và phương pháp xây dựng chuỗi đặc trưng dựa trên wavelet

1

Chương 3: Ứng dụng thử nghiệm. Chương này trình bày một ứng dụng cụ thể

của chuỗi đặc trưng âm thanh trong một lĩnh vực đang rất được quan tâm hiện nay đó

là nhận dạng nhạc số. Trong này sẽ mô tả khái quát về chương trình thử nghiệm của

ứng dụng nhận dạng nhạc và những kết quả đạt được

2

CHƯƠNG 1: TỔNG QUAN VỀ CHUỖI ĐẶC TRƯNG ÂM

THANH VÀ CÁC ỨNG DỤNG

1.1 Giới thiệu

Chuỗi đặc trưng âm thanh là một tập các thuộc tính của âm thanh được dùng để

xác định các dạng khác nhau của âm thanh bao gồm âm nhạc, phát thanh radio và các

tác động khác tới âm thanh. Mục tiêu đầu tiên của chuỗi đặc trưng âm thanh là thiết

lập trạng thái bằng nhau của hai đối tượng âm thanh: không phải bằng cách so sánh

chính hai đối tượng đó mà bằng cách so sánh những chuỗi đặc trưng liên kết của nó.

Trong hầu hết các hệ thống sử dụng công nghệ chuỗi đặc trưng, các chuỗi đặc trưng

của một số lượng lớn các đối tượng âm thanh cùng với siêu dữ liệu (ví dụ tên của

nghệ sĩ, tên album) được lưu trữ trong một cơ sở dữ liệu. Các chuỗi đặc trưng đáp

ứng như một chỉ mục đến siêu dữ liệu. Siêu dữ liệu của nội dung âm thanh chưa

được xác định sau đó sẽ được phục hồi lại bằng cách tính toán một chuỗi đặc trưng

và sử dụng nó như truy vấn trong cơ sở dữ liệu chuỗi đặc trưng/siêu dữ liệu. Ưu điểm

của việc sử dụng chuỗi đặc trưng thay cho chính đối tượng âm thanh là:

1. Giảm bớt yêu cầu bộ nhớ lưu trữ vì các chuỗi đặc trưng tương đối nhỏ.

2. So sánh hiệu quả vì sự không đồng đều được loại bỏ bởi chuỗi đặc trưng.

3. Tìm kiếm hiệu quả vì tập dữ liệu (dataset) để tìm kiếm là nhỏ hơn.

Vì những kết luận trên một hệ thống chuỗi đặc trưng nói chung bao gồm hai

thành phần: một phương pháp để trích ra chuỗi đặc trưng và một phương pháp để tìm

kiếm hiệu quả những chuỗi đặc trưng phù hợp trong cơ sở dữ liệu chuỗi đặc trưng.

1.2 Các khái niệm chuỗi đặc trưng âm thanh

1.2.1. Định nghĩa chuỗi đặc trưng âm thanh

Độ hồi tưởng (recall) một chuỗi đặc trưng âm thanh có thể được xem như một

tóm tắt ngắn của một đối tượng âm thanh. Vì thế một hàm chuỗi đặc trưng F ánh xạ

(map) một đối tượng âm thanh X – bao gồm một số lượng lớn các bit – đến chuỗi

đặc trưng chỉ gồm một số lượng bit giới hạn.

Ở đây chúng ta có thể thấy sự tương tự với các hàm băm đã được biết đến trong

công nghệ mã hóa. Một hàm băm mật mã H rút ra từ một đối tượng X (thường là

3

lớn) thành giá trị băm (thường là nhỏ). Một hàm băm mật mã cho phép so sánh hai

đối tượng X và Y bằng cách so sánh các giá trị băm tương ứng là H(X) và H(Y). Sự

bằng nhau chính xác về mặt toán học của cặp H(X), H(Y) đưa đến sự bằng nhau của

cặp X và Y với xác xuất xẩy ra lỗi rất thấp. Đối với hàm băm mật mã được xây dựng

hợp lệ thì xác xuất này là 2^-n, trong đó n bằng số bit của giá trị băm. Sử dụng các

hàm băm mật mã là một phương pháp hiệu quả hiện có để kiểm tra các dữ liệu cụ thể

của mục X có chứa trong tập dữ liệu lớn được đưa ra là Y = {Y } hay không. Thay

i

vì lưu trữ và so sánh với tất cả dữ liệu trong Y thì chỉ cần lưu trữ thành tập các giá trị

băm {h_i= H(Y_i) } và so sánh H(X) với tập các giá trị băm.

Nếu như thế có thể ta nghĩ rằng các hàm băm mật mã là một ứng cử tốt cho các

hàm chuỗi đặc trưng. Tuy nhiên với độ hồi tưởng được giới thiệu bên trên, thay vì sự

bằng nhau chính xác về mặt toán học, chúng ta quan tâm đến đặc điểm tương tự nhau.

Ví dụ, chất lượng của bản CD gốc của Rolling Stones-Angie và bản MP3 ở tốc độ

128Kb/s giống nhau với cơ quan thính giác của con người nhưng sóng của chúng có

thể khá là khác nhau. Mặc dù hai bản nhạc đó có cảm giác là giống nhau nhưng về

mặt toán học chúng khác nhau. Vì thế các hàm băm mật mã không thể đưa ra quyết

định dựa trên sự bằng nhau trực giác của hai bản đó.

Một câu hỏi khác được đặt ra là: “Có thể tạo ra một hàm chuỗi đặc trưng mà

cung cấp các chuỗi đặc trưng bằng nhau cho những đối tượng giống nhau về mặt

cảm giác không?” Câu hỏi là rất hợp lý nhưng câu trả lời là mô hình cho sự giống

nhau cảm giác về cơ bản là không thực hiện được. Sự giống nhau cảm giác của cặp

đối tượng X và Y và cặp đối tượng khác Y và Z không nhất thiết bao hàm sự giống

nhau của cặp đối tượng X và Z.

Việc đưa ra những lý lẽ trên mục đích là đề xuất cách xây dựng một hàm chuỗi

đặc trưng theo cách mà các đối tượng âm thanh giống nhau về mặt cảm giác đưa đến

kết quả là những chuỗi đặc trưng giống nhau. Hơn nữa, để có thể phân biệt giữa

những đối tượng âm thanh khác nhau, phải có xác xuất mà các đối tượng âm thanh

không giống nhau đưa đến những chuỗi đặc trưng không giống nhau là rất cao.

Chính xác hơn, cho hàm chuỗi đặc trưng F đã được xây dựng, điểm bắt đầu T với

xác xuất lớn ||F(X)-F(Y)|| ≤ T nếu các đối tượng X và Y là giống nhau và ||F(X)-

F(Y)|| > T khi chúng khác nhau.

4

1.2.2. Các tham số của hệ thống chuỗi đặc trưng âm thanh

Bên trên ta đã có một định nghĩa thích hợp của chuỗi đặc trưng âm thanh, phần

này trình bày về các tham số khác nhau của một hệ thống chuỗi đặc trưng âm thanh.

Các tham số chính là:

• Độ mạnh (Robustness): Liệu một đoạn âm thanh vẫn có thể được xác định

sau khi tín hiệu bị suy biến mạnh không? Để đạt được độ mạnh cao chuỗi

đặc trưng nên dựa trên cơ sở những đặc điểm thuộc tri giác không đổi (ít

nhất là đến một mức độ nào đó) với sự suy biến của tín hiệu. Tốt nhất là âm

thanh bị suy biến vẫn đưa đến những chuỗi đặc trưng rất giống nhau. Tỷ lệ

phủ định sai (false negative rate) nói chung được dùng để diễn đạt độ mạnh.

• Độ tin cậy (Reliability): Bao lâu một lần thì một bài hát bị nhận dạng sai?

Ví dụ “Rolling Stones – Angie” bị nhận dạng là “Beatles – Yesterday”. Tỷ

lệ mà tại đó tham số này được chỉ ra thường được tham chiếu đến như là tỷ

lệ khẳng định sai.

• Cỡ chuỗi đặc trưng (Fingerprint size): một chuỗi đặc trưng cần dung

lượng lưu trữ là bao nhiêu? Để có thể tìm kiếm nhanh, các chuỗi đặc trưng

thường được lưu trong bộ nhớ RAM. Vì thế cỡ của chuỗi đặc trưng, thường

được biểu diễn bằng bit/giây hoặc bit/bài hát, xác định độ lớn của tài nguyên

bộ nhớ cần cho server cơ sở dữ liệu chuỗi đặc trưng.

• Granularity: Cần bao nhiêu giây âm thanh để nhận ra một đoạn âm thanh?

Granularity là một tham số có thể phụ thuộc vào từng ứng dụng cụ thể.

Trong một vài ứng dụng thì toàn bộ bài hát có thể được dùng để nhận dạng,

trong những ứng dụng khác thì chỉ một đoạn trích ngắn của âm thanh được

dùng để xác định.

• Tốc độ tìm kiếm và khả năng mở rộng (Search speed and scalability):

Mất bao lâu để tìm ra một chuỗi đặc trưng trong cơ sở dữ liệu chuỗi đặc

trưng? Phải làm gì nếu cơ sở dữ liệu chứa hàng trăm nghìn bài hát? Đối với

sự triển khai về mặt thương mại của các hệ thống chuỗi đặc trưng âm thanh,

tốc độ tìm kiếm và khả năng mở rộng của hệ thống là yếu tố then chốt. Tốc

độ tìm kiếm nên là khoảng mili giây cho cơ sở dữ liệu chứa khoảng 100000

bài hát và chỉ sử dụng nguồn tài nguyên tính toán giới hạn

Năm tham số cơ bản này có ảnh hưởng lẫn nhau. Ví dụ, nếu một ứng dụng

muốn granularity thấp hơn thì nó cần trích ra một chuỗi đặc trưng lớn hơn để thu

5

được cùng độ tin cậy. Điều này là vì tỷ lệ khẳng định sai nghịch đảo liên quan đến cỡ

chuỗi đặc trưng. Một ví dụ khác: tốc độ tìm kiếm nói chung sẽ tăng lên khi một ứng

dụng được xây dựng với chuỗi đặc trưng mạnh (robust) hơn. Điều này là vì tìm kiếm

chuỗi đặc trưng là phép tìm kiếm xấp xỉ. Giả sử một chuỗi đặc trưng tương tự vừa

được tìm thấy, nếu các thuộc tính càng mạnh hơn thì độ xấp xỉ càng nhỏ hơn. Vì thế

tốc độ tìm kiếm có thể được tăng lên đáng kể.

1.3 Các ứng dụng

1.3.1. Broadcast Monitoring (BM)

BM hầu như là ứng dụng nổi tiếng nhất của chuỗi đặc trưng âm thanh. BM là

giải pháp phù hợp để dò tìm, giám sát các bài hát, các quảng cáo và kiểm tra các

chương trình phát thanh. Nó đề cập đến việc tạo ra danh sách (playlist) tự động của

radio, ti vi hoặc truyền hình web, truyền hình vệ tinh, trong số đó mục đích là tập

hợp tiền bản quyền, kiểm tra chương trình, kiểm tra quảng cáo và đo số người sử

dụng. Khi bạn cần giám sát hai đài phát hoặc thậm chí hai nghìn đài phát, hệ thống sẽ

cung cấp những danh sách (playlist) và các bản báo cáo cùng các chỉ dẫn kỹ thuật

phù hợp.

Một hệ thống BM quy mô lớn trên nền tảng chuỗi đặc trưng bao gồm vài site

giám sát (monitoring ) và một site trung tâm ở nơi mà server chuỗi đặc trưng được

đặt. Ở các site monitoring các chuỗi đặc trưng được rút ra từ tất cả các kênh truyền

thanh truyền hình (cục bộ). Site trung tâm thu thập các chuỗi đặc trưng đó từ các site

monitoring. Rồi sau đó, server chuỗi đặc trưng – chứa một cơ sở dữ liệu chuỗi đặc

trưng khổng lồ - cung cấp các playlist cho tất cả các kênh truyền thanh và truyền

hình đó.

1.3.2. Ứng dụng liên thông âm thanh

Ứng dụng liên thông âm thanh là thuật ngữ chung cho những ứng dụng tiêu

dùng mà ở đó âm nhạc được kết nối theo cách này hay cách khác để đưa ra và hỗ trợ

thông tin. Một ví dụ đã được đưa ra trong phần trên là sử dụng một điện thoại di

động để xác định một bài hát. Trong thực tế công việc này hiện đang được tiếp tục

thực hiện bởi một số công ty như Shazam, Yacast. Tín hiệu âm thanh trong ứng dụng

này bị suy biến trở lên rất xấu bởi vì quá trình xử lý áp dụng đài phát thanh, truyền

trên FM/AM, đường dẫn âm thanh giữa loa phóng thanh và micro của điện thoại di

6

động, mã hóa âm thanh và cuối cùng truyền trên mạng di động. Vì thế nhìn nhận về

mặt công nghệ thì đây là 1 ứng dụng đầy thách thức.

Những ví dụ khác về ứng dụng liên thông âm thanh là radio của ô tô với một

nút để nhận dạng bản nhạc đang nghe hoặc các ứng dụng “nghe” luồng âm thanh vào

hoặc ra trên một máy tính. Bằng cách nhấn vào nút “info” trong ứng dụng chuỗi đặc

trưng, người dùng có thể điều hướng đến một trang trên Internet chứa thông tin về

nghệ sĩ biểu diễn, tên bài hát, tên album. Hoặc nhấn vào nút “buy” người dùng có thể

mua album trên Internet. Nói cách khác, chuỗi đặc trưng âm thanh có thể cung cấp

một hệ thống liên kết chung cho tất cả những nội dung âm thanh.

1.3.3. Công nghệ lọc chia sẻ file

Ví dụ điển hình cho công nghệ lọc để chia sẻ file là Napster. Bắt đầu vào tháng

6 năm 1999, người dùng tải về Napster client có thể chia sẻ và tải về được một bộ

sưu tập nhạc miễn phí rất lớn. Sau đó, vì vấn đề pháp lý trong ngành công nghiệp âm

nhạc, người dùng Napster bị cấm tải về những bài hát có bản quyền. Vì thế vào tháng

3 năm 2001 Napster thiết lập một bộ lọc âm thanh trên cơ sở là tên file để ngăn cản

việc tải những bài hát có bản quyền (sử dụng công nghệ lọc dựa trên văn bản để lọc

tên các bài hát). Bộ lọc đó không hiệu quả, bởi vì người dùng bắt đầu cố ý viết sai

chính tả tên file. Vào tháng 5 năm 2001 Napster giới thiệu hệ thống chuỗi đặc trưng

âm thanh bởi Relatable, nó hướng vào việc lọc ra những thành phần có bản quyền

dựa trên nội dung âm thanh vì thế thậm chí nếu chúng có bị viết sai chính tả thì vẫn

bị nhận ra. Napster bị khai tử chỉ hai tháng sau đó.

Trong một dịch vụ chia sẻ file hợp pháp ứng dụng có thể áp dụng lên lịch lọc

chi tiết hơn là việc chỉ lọc được những thành phần có bản quyền.

Mặc dù từ quan điểm của một người tiêu dùng, bộ lọc âm thanh có thể được

xem như một công nghệ không được mong đợi nhưng cũng có một số lợi ích tiềm

năng đối với người tiêu dùng. Đầu tiên nó có thể tổ chức tên của các bài hát trong

các kết quả tìm kiếm theo một cách phù hợp bằng cách sử dụng siêu dữ liệu đáng tin

cậy của cơ sở dữ liệu chuỗi đặc trưng. Thứ hai, chuỗi đặc trưng có thể đảm bảo rằng

những bài hát được tải về thực sự là những bài hát được mong đợi.

7

1.3.4. Tổ chức thư viện âm nhạc tự động

Ngày nay nhiều người dùng máy tính có một thư viện âm nhạc chứa vài trăm

đôi khi thậm chí là vài nghìn bài hát. Các bản nhạc nói chung được lưu trữ trong định

dạng nén (thường là MP3) trong ổ cứng của họ. Bởi vì những bài hát này thu được từ

nhiều nguồn khác nhau, như xao chép từ đĩa CD hoặc tải về từ các mạng chia sẻ file,

nên những thư viện này thường không được tổ chức 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.

8

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

9

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

10

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ổ.

11

Để 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ễ):

1ifE(n,m) − E(n,m +1) − (E(n −1,m) − E(n −1,m −1)) > 0

⎧

F(n.m) =

(2.1)

⎨

⎩

0ifE(n,m) − E(n,m +1) − (E(n −1,m) − E(n −1,m −1)) ≤ 0

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

12

(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 P_f,

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 P_fsẽ 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 P , ví dụ xác xuất mà hai tín hiệu ”bằng nhau” nhưng không được xác định.

n

Để 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 σ = (np(1− p)) . Đưa ra khối chuỗi đặc

trưng F , xác xuất mà khối chuỗi đặc trưng F₂được chọn ngẫu nhiên có ít hơn

1

13

T = αn lỗi với F được đưa ra bởi:

1

∞

2

1

⎛ (1− 2α)

⎞

⎟

P_f(α) =

e^{1x / 2}dx = erfc

n

(2.2)

⎜

∫

(1−2α )

n

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 x_ivà x_i+1là giống nhau

và bằng q. Sau đó được biểu diễn:

E

[x_ix_i+k

]

= a ^k

(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à

E

[z_iz_i+k

]

= a^{2 k}

(2.4)

Với N lớn, độ lệch chuẩn trung bình Z_Ntrê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+ a²

N(1− 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ố:

1+ a²

1− 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.

14

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

1

⎛ (1− 2α)

⎞

⎟

P = erfc

n

(2.7)

⎜

f

2

3 2

⎝

⎠

Đ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^-20rất thấp.

15

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.

16

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 2³²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*10⁶/10³²). 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

17

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í

18

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 (=2³) 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

19

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

20

đ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

21

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

22

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

b

c

d

1

0

1

0

1

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

23

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.

24

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.

25