Thiết kế hệ thống nhận dạng các dạng âm thanh

LỜI MỞ ĐẦU Ngày nay nhu cầu của con người càng ngày càng lớn hơn. Sự phát triển của Internet, Google, Yahoo, MSN là những tên tuổi được biết đến trong lĩnh vực cung cấp dịch vụ tìm kiếm tài liệu qua mạng. Với những dịch vụ tìm kiếm tài liệu qua mạng. Với những dịch vụ này người dùng có thể tìm kiếm các tài liệu, hình ảnh, video, hay những tài nguyên khác có trên Internet qua từ khóa. Cho đến nay, phương pháp tìm kiếm bằng từ khóa vẫn là phương pháp chủ đạo trong các hệ thống truy vấn thông tin và tìm kiếm dữ liệu. Tuy nhiên, phương pháp này cũng thể hiện những hạn chế và khả năng ứng dụng của nó trong loại dữ liệu không phải là văn bản. Với dữ liệu hình ảnh, việc tìm kiếm phụ thuộc rất nhiều vào việc gán nhãn cho hình ảnh trong dữ liệu. Phương pháp này xa rời với bản chất của hình ảnh là màu sắc và đường nét. Trong âm nhạc, phương pháp này cũng tỏ ra những mặt hạn chế của nó. Bản chất của âm nhạc là giai điệu, nhưng hầu hết các từ khóa không thể hiện được tính chất này của bản nhạc. Tìm kiếm dựa vào thông tin nhạc sĩ, ca sĩ và lời bài hát là những ứng dụng chính trong truy vấn thông tin âm nhạc hiện nay.Tưởng tượng rằng khi bạn đang nghe một bài hát nào đó và rất thích nó và bạn muốn nghe lại nó. Nhưng bạn không biết tên bài hát hay tên tác giả của nó. Bạn bắt đầu hỏi bạn bè của bạn, ngân nga giai điệu đó lên. Không có một ai biết để giúp bạn, bởi vậy bạn sẽ rơi vào bế tắc. Vì vậy phát sinh ra máy tìm kiếm âm nhạc như hệ thống QBH (Query By Humming) như vậy để thỏa mãn nhu cầu của con người. Hệ thống giúp người dùng tìm kiếm dễ dàng hơn dựa trên giai điệu được hát hay ngân nga từ người dùng. Đề tài gồm 3 chương chính: Chương 1 Giới thiệu về hệ thống nhận dạng âm thanh Chương 2 Các vấn dề nghiên cứu liên quan Chương 3 Hệ thống truy vấn âm nhạc qua giọng hát Chương 4 Thực nghiệm, kết quả và hướng phát triển tìm kiếm âm nhạc Tài liệu tham khảo

pdf58 trang | Chia sẻ: lvcdongnoi | Ngày: 19/08/2013 | Lượt xem: 2464 | Lượt tải: 6download
Bạn đang xem nội dung tài liệu Thiết kế hệ thống nhận dạng các dạng âm thanh, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
vậy, thực hiện một khảo sát chi tiết và đầy đủ những phương pháp biểu diễn là không khả thi và cũng không có giá trị thực tế. Những mục sau đây cho ta một cách nhìn tổng qua từ tác phẩm đến dạng sóng âm vật lý. 2.2.1 Giai điệu Giai điệu là một dãy các note nhạc được sắp xếp theo một trật tự nhất định. Mỗi thể loại âm nhạc sử dụng giai điệu theo một cách khác nhau. Giai điệu một bài nhạc là cái nền làm bản nhạc du dương do đó dễ nghe và dễ nhớ. Có lẽ bạn chẳng cần hiểu biết tối thiểu về nhạc cũng vẫn có thể nghe và thích các bản nhạc trầm bổng réo rắt của Schubert, Tchaikovski, Mendelssohn… [24, 15, 16] 2.2.2 Đường viền giai điệu (Melody Pitch Contour) Một đại diện giai điệu tốt nên nắm bắt được tất cả các thông tin giai điệu và phù hợp với thói quen mà người dùng “hum” vào. Theo nguyên tắc này, chúng ta đã đề nghị một bộ ba của đại diện giai điệu. Đầu tiên, đường viền giai điệu được dùng.Thuộc tính cơ bản của âm nhạc là chuỗi cao độ của các nốt, giai điệu, nhịp điệu (Nhanh/chậm), kết cấu (âm sắc hay âm thanh) và lời hát. Nó là những phân đoạn mà chúng ta phân biệt một cách đặc trưng một trong những phần của âm nhạc từ cái khác. Giai điệu và nhịp điệu thì đặc biệt nhất. Giai điệu của một phần âm nhạc là một chuỗi các nốt với cao độ khác nhau và trường độ khác nhau. Cao độ được kết hợp với chu kỳ của âm thanh và cho phép sắp xếp. [15, 24, 13, 16] Downling [22] đã đề nghị một phương pháp biểu diễn giai điệu bằng chiều hướng của cao độ (tăng, giảm hoặc lặp lại) và phương pháp này rất hữu dụng trong đa số trường hợp. Cách biểu diễn này được gọi là đường biên giai điệu (Melodic pitch contour). Đường biên giai điệu thể hiện một chuỗi những biến đổi có tính chất định tính trong cao độ. Một note trong một bản nhạc được đem so sánh với note trước đó và sự sai khác được xếp vào một trong ba lớp, được ký hiệu như sau: U (Up - khi cao độ tăng), D (Down – khi cao độ giảm), và R (Repeat – khi cao độ lặp lại). Như vậy, một đoạn nhạc đơn giản có thể được biểu diễn bằng một chuỗi những ký tự (gồm U, D, R). 20 Chẳng hạn như, khúc mở đầu của bản giao hưởng số 5 của Beethoven sẽ được biểu diễn bằng chuỗi sau: - R R D U R R D. Hình 3 cho ta một ví dụ khác về bản nhạc quen thuộc “Happy Birthday” được biểu diễn dưới dạng đường biên giai điệu. Hình 3: Ví dụ biểu diễn đường biên giai điệu của bài hát “Happy Birthday” Đường biên giai điệu thể hiện một chuỗi đặc trưng đường biên của của giai điệu đã loại bỏ những thông tin không cần thiết, như định lượng sự sai khác giữa hai note nhạc liền nhau hay thông tin về nhịp điệu, vì vậy làm giảm không gian và độ phức tạp của việc tìm kiếm. Tuy nhiên, cũng vì thế, thông tin đường biên giai điệu lại trở nên quá thiếu chi tiết (under-specification). Có rất nhiều bản nhạc dù giai điệu khác nhau, nhưng vẫn có thể có đường biên giống nhau do giai điệu cùng lên và xuống theo trật tự giống nhau (nhưng độ lên xuống khác nhau và thời gian của từng note nhạc cũng khác nhau). Đặc trưng đường biên giai điệu như mô tả ở trên không đủ phân biệt trong rất nhiều trường hợp. Một cách khắc phục là phân loại những lớp con trong các lớp UDR.Theo phương pháp này, mỗi lớp cha (U hay D) sẽ có những lớp con tương ứng với mức độ lên xuống nhiều hay ít của các cao độ trong các note liền kề. Lớp R – Repeat chỉ có một lớp con là chính nó, còn các lớp U và D sẽ được biểu diễn tương ứng bằng những số nguyên dương hoặc âm.[13,10, 16] 2.2.4 Đường biên nhịp điệu (Rhythm Contour) Nhịp điệu (Rhythm) của một bản nhạc là một đặc trưng theo thời gian của bản nhạc. Đường biên nhịp điệu (Rhythm Contour) có thể được hiểu tương tự như đường biên cao độ. Độ dài của một note nhạc trong bản nhạc được đem so sánh với độ dài của note nhạc trước đó và sự sai biệt này sẽ được xếp vào ba lớp tương ứng: dài hơn (L –Longer), ngắn hơn (S – Shorter), và bằng nhau (R – Repeat). Từ đó, một bản nhạc sẽ được biểu diễn bởi một chuỗi các ký tự gồm ba ký tự (LSR). Đương nhiên, khi biểu diễn đặc trưng Rhythm Contour, ta phải chấp nhận một sai số nhất định cho lớp R vì trong quá trình biểu diễn bản nhạc, việc biểu diễn hai note giống nhau hoàn toàn về mặt thời gian trên khuôn nhạc là không khả thi. Ngưỡng sai số thường dùng 21 trong trường hợp này là ½ (cho Shorter) và 2 (cho Longer), dựa theo tỉ lệ thời gian của note trước và note sau. Xem [16] Không giống với đường biên giai điệu, đường biên nhịp điệu hoàn toàn không dựa trên cơ sở tâm lý học. Biểu diễn đường biên nhịp điệu chỉ nhằm mục đính làm giảm bớt độ phức tạp trong lưu trữ và tìm kiếm. 2.2.5 MIDI (Musical Intrument Digital Interface) Nhạc thường (bao gồm tiếng đàn, tiếng sáo, tiếng các bộ gõ và cả tiếng hát nữa) đều tồn tại dưới dạng sóng âm thanh hình Sin (Sinus). Dẫu rằng chúng khác nhau về cường độ (mạnh, yếu), trường độ (dài, ngắn), cao độ (trầm, bổng), tiết tấu (nhanh, chậm) và âm sắc (bản sắc riêng của các công cụ nhạc), nhưng điểm chung nhất tất cả đều là sóng âm, với bản chất cơ học : Một luồng sóng âm, bất kể từ nguồn nào, đều làm rung động bầu không khí quanh nó, truyền đi trong không gian bao la, rồi đập vào tai người nghe, làm rung động màng nhĩ, khiến cho người ấy nghe được âm thanh đó.[27, phụ lục 8] Để ghi lại, lưu lại một sóng âm thường thì người ta sử dụng kỹ thuật tương tự (Analog), biến một sóng âm bản chất cơ học thành sóng điện từ, với những định dạng (format) quen thuộc như .wav, .cda, .mp3 v.v... File âm thanh định dạng wav thường chiếm rất nhiều không gian dĩa, file cda cũng là một loại file wav, được sử dụng cho các đĩa CD (compact disc) nên cũng chiếm dụng không gian tương đương .Kỹ thuật nén file ra đời đã hình thành nhạc mp3 với rất nhiều ích lợi (chiếm dụng không gian ít hơn từ 10 lần đến 20 lần so với file wav, nhờ đó có thể truyền tải được trên mạng Internet nhiều và nhanh hơn) Nếu một bài hát thông thường lưu ở định dạng wav chiếm trung bình khoảng 40 Mb , thì file Mp3 tương ứng chỉ cần từ 2Mb cho đến 4 Mb. Giữa các nhạc cụ điện tử giờ đây có một "ngôn ngữ" chung gọi là "MIDI", để nói chuyện với nhau. MIDI tuy là một khái niệm mới nhưng đã trở nên rất quen thuộc trong lĩnh vực âm nhạc điện tử, đến nổi người ta xem nó là một thuật ngữ mà quên rằng MIDI là từ viết tắt của "Miscical Instrument Digital Interface" (giao diện số với các nhạc cụ). Một cách đơn giản, MIDI là một ngôn ngữ giữa các thiết bị âm nhạc. Mặc dù có nhiều ngôn ngữ khác nhau trên thế giới (Việt Nam, Anh, Pháp...) nhưng MIDI chỉ có một ngôn ngữ duy nhất. Do đó, MIDI không phụ thuộc nhà chế tạo nhạc 22 cụ và nơi sản xuất. Hơn nữa nó dùng cho nhiều chủng loại nhạc cụ khác nhau; ví dụ một piano điện có thể nối với một bộ trống điện tử, khi đó nếu ta bấm một phím trên piano thì bộ trống sẽ phát ra một tiếng trống tương ứng. Nhạc Midi không dùng kỹ thuật tương tự (Analog), mà dùng kỹ thuật số (Digital) để lưu lại âm thanh. Mỗi âm thanh của các nhạc cụ khác nhau được gán cho một chuỗi ký tự số nhị nguyên tương ứng (chỉ bao gồm 2 chữ số 0 và 1) Như vậy một chuỗi âm thanh sẽ được ghi lại như một ... chuỗi số. Và quá trình lưu file âm thanh được quy về như một quá trình số hóa, kèm theo là lưu số Ở công cụ nghe, một quá trình ngược sẽ được thực thi: Chuỗi số sẽ được biến đổi, hoán cải ngược lại thành chuỗi âm thanh.Vì thế Nhạc Midi còn được gọi bằng những tên khác như: nhạc điện tử, hay gọn hơn nữa là nhạc số. Vì đã được tiêu chuẩn hóa nên nhạc Midi chơi rất chính xác và rất hay, rất lạ tai. Một lợi ích quan trọng hơn nữa là file nhạc Midi chiếm dụng rất ít không gian. Một bài hát định dạng wav 40 Mb, định dạng Mp3 khoảng 4 Mb, thì một file Midi tương ứng chỉ mất khoảng 40 Kb (ít hơn Mp3 một trăm lần, và ít hơn Wav một ngàn lần !!!). Nghĩa là sẽ có (thật ra là đã có) những dĩa CD kỹ thuật số dung lương cũng chỉ 650 Mb như các dĩa khác, nhưng chứa được trên mười ngàn bài hát. Midi như đã nói ở phần trên, nhờ những tiện nghi vô hạn của nó, nên đã rất nhanh và rất sớm được sử dụng trên mạng InterNet 2.2.5 Digital audio Digital audio là cách biểu diễn thô của âm thanh qua việc số hóa tín hiệu trong sóng âm thanh. Sóng âm thanh sẽ được lấy mẫu và biên độ của sóng tại từng thời điểm sẽ được biến đổi từ tín hiệu analog sang tín hiệu số. [29] Do tính chất của việc biểu diễn dựa trên sóng âm, cách biểu diễn này có thể biểu diễn mọi loại âm thanh (tiếng nói, tiếng hát…) Nhờ tính chất này, việc tạo ra một tập tin âm thanh dạng thô khá đơn giản và có thể thực hiện được từ việc thu âm vào microphone. Do đó có thể sử dụng làm định dạng truy vấn của người dùng. 2.3 Những phương pháp Matching 2.3.1 Thuật toán LSH (Locality Sensitve Hashing) 23 Đưa ra một đoạn giai điệu được định nghĩa bởi điểm pi, chúng ta có thể tìm các đoạn tương tự trong chỉ mục bằng các tìm kiếm các hàng xóm gần nhất (NNs) của điểm ví dụ tất cả các điểm mà khoảng cách nhỏ hơn một ngưỡng cụ thể r nào đó.Điều này có thể được làm bởi việc đo khoảng cáh đơn gian pi đến tất cả các vector trong cơ sở dữ liệu. Tuy nhiên, các kết quả này trong một thời gian tìm kiếm tùy thuộc vào kích cỡ tuyến tính của cơ sở dữ liệu. [16, 4] Để thu được một thời gian tuyến tính dưới một cách phức tạp, chúng ta sử dụng vị trí của hàm băm miền nhạy cảm LSH là một thuật toán ngẫu nhiên cho việc tìm kiếm khoảng cách hàng xóm gần nhất trong không gian nhiều chiều.Ý tưởng là các điểm mà khoảng cách trong cùng một ngưỡng sẽ được băm vào một thùng giống nhau với xác suất cao. Người dùng định nghĩa xác suất điều khiển sự thỏa thuận giữa độ chính xác và tốc độ của LSH. Trong phương pháp của chúng ta, chúng ta thuê LSH hoàn thiện các gói E2LSH bởi các độc giả Dựa trên sự thi hành, chúng ta xây dựng một máy chủ cho việc xử lý các đoạn chỉ số the melodic và một máy khách cho việc truy xuất các đoạn giai điệu giống nhau từ cơ sở dữ liệu. Gần đây LSH được áp dụng ví dụ trong việc công nhận âm nhạc và trong dấu tay âm thanh.Ý tưởng của thuật toán LSH như sau. Thuật toán LSH là thuật toán tìm kiếm K hàng xóm gần nhất hoặc tìm kiếm xấp xỉ K hàng xóm gần nhất. • Truy vấn lân cận K gần nhất KNN (K- nearest neighbour) Người dùng đặc tả một đối tượng truy vấn Q và chấp nhận một số lượng K đối tượng. Hệ thống tìm kiếm K đối tượng tương tự nhất với đối tượng truy vấn từ MMDBMS (Multimedia Database Management Systems). K=|A|, A € DB, ¥ P € A,, P’ € { DB/A },, D (P,Q)<=D(P’,Q) 24 Hình 4: Minh họa phương pháp truy vấn KNN • Truy vấn xấp xỉ lân cận K gần nhất Đối với các ứng dụng mà mục tiêu đưa ra không phải là kết quả thật chính xác mà xét tốc độ là quan trọng hơn, khi đó phương pháp truy vấn xấp xỉ lân cận K gần nhất cho hiệu quả cao hơn phương pháp KNN nêu trên. Truy vấn xấp xỉ lân cận K gần nhất mô tả như sau: Người dùng đặc tả một đối tượng truy vấn Q và một số K đối tượng và sai số epsilon chấp nhận được. Hệ thống tìm kiếm xấp xỉ K đối tượng tương tự nhất với đối tượng truy vấn từ MMDBMS: K=|A|, A € DB, ¥ P € A, P’ € { DB/A }, D(P,Q)<=(1+∂)D(P’,Q). 2.3.2 Thuật toán Dynamic Time Warping (DTW) Dynamic Time Warping (DTW)[1] [24][5] [21] [8] là thuật toán dùng để tính độ tương đồng giữa hai chuỗi đặc trưng, khác nhau về chiều dài. DTW được áp dụng trong nhiều lĩnh vực và là ý tưởng nguyên thuỷ của nhận dạng tiếng nói. Trong đó, DTW được dùng để giải quyết vấn đề khác nhau trong độ nhanh chậm của tiếng nói. Mục đích của DTW dùng để tìm kiếm một ánh xạ giữa hai vector đặc trưng (có chiều dài khác nhau) với khoảng cách ngắn nhất. Phương pháp này được gọi là “time- warping” là vì những vector đặc trưng này thường được lấy theo đơn vị thời gian và ta cần co (hoặc giãn) chiều thời gian cho phù hợp để có được một ánh xạ tốt nhất. 25 Cho hai vector t = [t1, t2,…, tn] và r = [r1, r2,…,rm]. Thuật toán DTW sẽ giúp tìm ra một ánh xạ đường đi {(xi1, yj1), (xi2, yj2),…, (xik, yjk)} với những ràng buộc sau: i. Điều kiện ràng buộc biên: (i1, j1) = (1, 1), (ik, jk) = (m, n). Điều kiện này còn gọi là "neo điểm đầu" và "neo điểm cuối". ii. Ràng buộc về đường đi cục bộ: Với mọi node (i, j) trong đường đi, những node đến được nó chỉ giới hạn trong (i-1, j), (i, j-1), (i-1, j-1). Ràng buộc này giúp đảm bảo luôn tồn tại một song ánh từ t đến r. Minh họa về ràng buộc đường đi cục bộ thể hiện trong hình dưới đây. Hình 5: Minh họa đường đi cục bộ 0 - 45 - 90 Cốt lõi của thuật toán DTW là thuật toán quy hoạch động. Thuật toán được mô tả trong 3 bước sau: i. Gọi D(i, j) là khoảng cách DTW giữa t(1..i) và r(1..j), với ánh xạ đường đi (1,1) đến(i, j). ii. Sử dụng công thức quy hoạch động để điền lần lượt các giá trị vào D(i, j): D (i, j) = |t(i) - r(j)| + min{D(i - 1, j), D(i - 1, j - 1), D(i, j - 1)} với điều kiện đầu D(1,1) = |t(1) - r(1)| iii. Khoảng cách DTW của 2 vector t và r là D(m, n) Trong lập trình, ta xây dựng một mảng hai chiều D gồm m và n phần tử. Khởi tạo giá trị ban đầu của D (1, 1). Sau đó, sử dụng công thức quy hoạch động để điền lần lượt các giá trị lần lượt từ trái qua phải, từ trên xuống dưới. Như vậy, độ phức tạp 26 của thuật toán DTW là O(mn). Để áp dụng trong tìm kiếm âm nhạc, một vài cải tiến đã được đề xuất: Hình 6: Minh họa đường đi 27 – 45 – 63 [16] Khác với đường đi thông thường 0-45-90, đường đi này loại bỏ tính ràng buộc song ánh giữa hai vector, giúp ta loại bỏ nhiễu (outlier) của dữ liệu trong hai vector đặc trưng. Loại bỏ ràng buộc điều kiện "neo điểm cuối" Thông thường, điểm đầu và cuối đoạn truy vấn giai điệu sẽ không trùng khớp hoàn toàn với giai điệu mẫu được lưu trong cơ sở dữ liệu. Vì vậy, điều kiện "neo điểm cuối" có thể bỏ qua. Điều kiện "neo điểm đầu" cũng có thể bỏ qua; tuy nhiên, kết quả thực nghiệm cho thấy phưong pháp làm này hoàn toàn không hiệu quả cả với những đoạn truy vấn mẫu được hát từ đầu giai điệu Vì vậy, với phương pháp DTW, chúng ta giả thiết người dùng hát từ đầu giai điệu. Điểm khiếm khuyết này của DTW sẽ được giải quyết trong phần sau (xem phần 3.4). Để loại bỏ điều kiện "neo điểm cuối", khoảng cách DTW giữa hai vector r và t sẽ là giá trị nhỏ nhất trong các giá trị D[m, i..n]. Xem chi tiết tại [1] [24][5] [21] [8] Ưu điểm của phương pháp DTW ở chỗ có thể sử dụng thẳng chuỗi cao độ vào quá trình tìm kiếm mà không cần phải phân đoạn thành từng note. Thường đây là một vấn đề rất khó giải quyết nếu áp dụng phương pháp String Alignment 2.3.3 Thuật toán Hidden Markov Model (HMM) 27 2.3.3.1 Tổng quan Mô hình Markov (Hidden Markov Model –HMM) [1] ẩn được sử dụng trong việc thống kê mô hình tạo âm thanh. Tính hiệu quả của mô hình được thể hiện trong việc mô tả tín hiệu âm thanh theo dạng toán học dễ dàng cho việc xử lý tín hiệu. Các trạng thái của HMM có được trước khi thực hiện việc xử lý các trạng thái. Như thế đầu vào của HMM chính là chuỗi các thông số vector rời rạc theo thời gian. 2.3.3.2 Định nghĩa mô hình Markov ẩn Mô hình Markov ẩn là một tập các trạng thái hữu hạn, mà mỗi trạng thái có liên quan đến hàm phân phối xác xuất. Việc chuyển tiếp giữa các trạng thái được định nghĩa bởi một tập xác suất được gọi là xác suất chuyển tiếp (transition probability). Trong một trạng thái cụ thể, kết quả có thể được tạo ra dựa trên hàm phân phối xác suất tương ứng. Kết quả này không phải là một trạng thái có thể nhìn thấy được thông qua việc quan sát các trạng thái, cho nên được gọi là mô hình Markov ẩn. [1][4] Trong những nghiên cứu gần đây, hai phương pháp HMM rời rạc và HMM liên tục cũng đã được xem xét đến. với những phương pháp này, mỗi bài bát (hay đoạn giai điệu) sẽ được mô hình thành một HMM. Hình dưới minh họa biểu diễn giai điệu bằng Hidden Markov Model [1][4] Hình 7: Mô hình Markov cho một đoạn giai điệu Hiện nay, HMM chưa đem lại kết quả cao bằng những phương pháp thông thường như String Alignment hay DTW hay LSH vì nhiều lý do: 28 • Thiếu dữ liệu cho việc học máy • Những mô hình và những đặc trưng chưa được nghiên cứu và phát triển 2.3.4 String Alignment [22] Bài toán tìm kiếm cơ sở dữ liệu các đặc trưng pitch contour có thể đưa về bài toán tìm kiếm chuỗi đơn giản. Đương nhiên, để có thể giải quyết những sai sót từ người dùng và trong quá trình rút trích đặc trưng, ta phải xem xét đến thuật toán tìm kiếm chuỗi gần đúng. Những ứng dụng đầu tiên trong lĩnh vực tìm kiếm chuỗi có chấp nhận sai sót (gần đúng) được sử dụng trong ngành tin sinh học (so sánh những chuỗi DNA). Nhà khoa học muốn biết hai chuỗi DNA giống nhau như thế nào, chúng có những điểm chung gì. Chuỗi DNA được biểu diễn bởi một chuỗi ký tự dài nhưng lại giới hạn về loại ký tự (chỉ bao gồm 4 ký tự A, C, G, T). Tìm kiếm sự hiện diện của một chuỗi DNA ngắn, chấp nhận sai sót, cũng gần giống với việc truy vấn từ một cơ sở dữ liệu đường biên giai điệu. Pardo et al đã đề xuất hai phương pháp string alignment có thể áp dụng trong tìm kiếm melodic contour hay pitch interval: Global String Alignment and Local String Alignment. 2.3.4.1 Global String Alignment Thuật toán Global String Alignment, một dạng điển hình của tìm kiếm dựa trên chuỗi, là thuật toán quy hoạch động. Đặt độ dài của chuỗi S là |S|. Và ta có Q (Query) là chuỗi mẫu cần truy vấn, và T (Target) là chuỗi trong cơ sở dữ liệu cần đem so sánh. Giả thiết rằng Q và T chỉ chứa những ký tự trong cùng một bảng chữ cái. Ta xây dựng một bảng AlignScore gồm |Q| + 1 dòng và |T| + 1 cột trong đó AlignScore (i, j) là điểm liên kết tốt nhất giữa hai chuỗi con q1...qi của Q và t1..tj của T. Quy trình này được bắt đầu bằng việc gán AlignScore (0, 0) = 0. Sau đó, những phần tử của mảng sẽ được tuần tự điền vào theo công thức (2-1) dưới (2-1) 29 Hàm matchScore có ý nghĩa như một hàn lượng giác mức độ giống nhau của hai ký tự trong một chuỗi. Hàm matchScore có thể được định nghĩa đơn giản như công thức (2-2) (2-2) Tuỳ thuộc vào bản chất của đặc trang dữ liệu, matchScore có thể được thay đổi cho phù hợp và cho hiệu quả tốt nhất. Hàm skipPenalty cũng được xây dựng dựa theo các điều kiện của matchScore (hay cũng có thể biến thành một trường hợp đặc biệt của matchScore). Với hàm matchScore tương ứng như trên, ta có thể xây dựng hai hàm skipPenalty như (2-3). (2-3) Sau khi xây dựng xong mảng alignScore, giá trị liên kết tốt nhất giữa hai chuỗi sẽ được đọc tại ô ở dòng cuối cùng, góc bên phải của bảng. Từ đó, ta cũng có thể lần ngược lại đường đi để cho ra giá trị tốt nhất này. Hình 8: Ma trận alignScore Trong trường hợp ma trận alignScore ở Hình 2-6, chuỗi tìm kiếm là “G D A C B”, còn chuỗi đích trong cơ sở dữ liệu là “G A B B”. Điểm liên kết giữa hai 30 chuỗi là 3. Dưới đây là những cách thức kết hợp hai chuỗi này (dấu „-‟ có ý nghĩa là một ký tự bị bỏ qua, không khớp) Hình 9: So khớp truy vấn và đích 2.3.4.2 Local String Alignment Thuật toán Global String Alignment sẽ cho kết quả điểm liên kết tốt nhất giữa hai chuỗi. Đây sẽ là một hướng tiếp cận tốt nếu như chúng ta muốn so sánh hai chuỗi được sao chép từ một chuỗi khác. Hay nói cách khác, với mỗi phần tử trong một chuỗi, chỉ có khái niệm trùng hoặc bị bỏ qua. Tuy nhiên, trong trường hợp nhận dạng giai điệu, ta không thể giả thiết rằng người sử dụng hát hoàn toàn đầy đủ một giai điệu trong cơ sở dữ liệu. Rất có thể người sử dụng chỉ hát một đoạn trong giai điệu được lưu hoặc phần lớn giai điệu được hát trùng với phần được lưu trong đoạn đầu và cuối của giai điệu truy vấn và giai điệu được lưu lại khác nhau. Vì vậy, người ta thường dùng phương pháp Local String Alignment cho trường hợp so sánh hai đặc trưng giai điệu. Trong thuật toán Local String Alignment, công thức quy hoạch động cho ma trận (2-4) Sau khi đã điền đầy đủ các trị số vào ma trận alignScore,điểm số tốt nhất của các chuỗi con T và Q được xem như điểm cho độ giống nhau giữa Q và T. Như vậy, điểm độ giống nhau giữa Q và T được lấy bằng cách tìm giá trị lớn nhất trong mảng alignScore. Xem [22, 9, 13] 31 Chương 3. HỆ THỐNG TRUY VẤN ÂM NHẠC QUA GIỌNG HÁT 3.1 Xử lý âm thanh truy vấn 3.1.1 Xóa bỏ các nốt làm nhiễu, ồn và các note ngắn Sau khi việc thu tín hiệu với một card âm thanh của máy tính thì dải tín hiệu này được xử lý thông qua bước lọc bỏ bớt những tiếng ồn nhiễu và sự bóp méo tín hiệu của môi trường ngoài. Tín hiệu được giới hạn trong giải 80 đến 800 Hz hợp lý cho giai điệu hát đầu vào. Các tiếng ồn xung quanh sẽ gây nhiễu giai điệu mà người dùng đưa vào như vậy sẽ khiến cho việc xử lý truy vấn tiêp theo trở nên khó khăn vì thế nên loại bỏ những tạp âm xung quanh đồng thời bỏ đi những nốt ngắn trong truy vấn mà người dùng đưa vào vì nó quá ngắn không đủ để làm đặc trưng nhận dạng cho truy vấn nó mang ít ý nghĩa thông, làm giảm chất lượng của truy vấn đầu vào. Bốn bước làm giảm giá trị nhiễu trong chuỗi cao độ là làm mịn các giá trị trong chuỗi: • Bước 1: Loại bỏ những khoảng lặng ở đầu (pitch = 0). • Bước 2: Xác định những khoảng chuyển đổi cao độ. Một đoạn cao độ mới được hình thành khi hiệu của giá trị trung bình cao độ trong đoạn đó và giá trị cao độ tiếp theo lớn hơn ngưỡng T (0<T<1, đơn vị: bán cung). Sau đó, thay tất cả các giá trị trong đoạn cao độ đó bằng giá trị trung bình [2]. Nếu hai đoạn cao độ liền kề có giá trị chênh lệnh nhau 0.5, nối hai đoạn đó lại với nhau. • Bước 3: Nếu một đoạn cao độ có thời gian nhỏ hơn 100 mili-giây, nối đoạn cao độ đó với đoạn cao độ có giá trị gần nhất. • Bước 4: Nếu một đoạn khoảng lặng (pitch = 0) có thời gian bé hơn 300 mili-giây, các giá trị đó sẽ được thay bằng giá trị trung bình của đoạn cao độ trước đó. [2] [3] 32 Hình 10: Ví dụ về một truy vấn người dùng đưa vào Từ truy vấn trên ta dùng công cụ Praat để chuyển truy vấn này thành chuỗi tần số cơ bản minh họa như hình dưới đây: Hình 11: Mô tả truy vấn trên dưới một dạng sóng 3.1.2 Đặc trưng cao độ (pitch) Đặc trưng cao độ (pitch) là một đặc trưng quan trọng trong những tín hiệu tuần hoàn như âm thanh của giọng người hoặc nhạc cụ. Ta có thể hiểu, đặc trưng cao độ thể hiện tần số dao động của nguồn phát ra âm thanh như dây thanh đới của người hoặc dây đàn trong nhạc cụ. Nói cách khác, cao độ là tần số cơ bản của âm thanh, là nghịch đảo của chu kỳ theo công thức: Đặc trưng hay giá trị này được đo bằng Hertz (số chu kỳ dao động trong một giây). Tuy nhiên, thông số này không tuyến tính với cảm nhận của tai người. Khi tần số cơ bản của một nguồn âm là 440Hz, cao độ của âm thanh đó tương ứng với note A4 (La 4) trên phím đàn piano. Để cao độ tăng lên một quãng 8 (12 đơn vị cao độ) thì tần số phải tăng gấp đôi (A5=880Hz). Vì vậy, trong âm nhạc có một đơn vị khác dùng để biểu thị cao độ và tuyến tính với cảm nhận của tai người: bán cung (semitone). Để chuyển từ đơn vị Hertz sang bán cung, ta sử dụng công thức: (3-1) 33 Đơn vị này tuyến tính với cảm nhận của tai người và giúp tăng độ chịu lỗi của hệ thống. Xem chi tiết [15][11] 3.1.3 Rút trích đặc trưng cao độ (pitch tracking) Việc tính toán giá trị cao độ trong giọng người có thể thực hiện được bằng tay và mắt qua việc quan sát hình dạng sóng âm trong những tập tin âm thanh được số hóa. Đương nhiên, việc này tốn kém thời gian và không hiệu quả. Việc tự động tính toán cao độ trong một bản thu âm tiếng người hoặc nhạc cụ gọi là pitch tracking. [15] Một khi đã xác định được chuỗi cao độ đặc trưng của âm thanh, ta có thể dùng đặc trưng này trong nhiều ứng dụng: • Nhận dạng âm nhạc • Nhận dạng giọng nói địa phương • Tổng hợp tiếng nói • Tăng kết quả nhận dạng trong hệ thống nhận dạng tiếng nói Vì vậy pitch tracking là một trong những kỹ thuật cơ bản và quan trọng trong xử lý tín hiệu số. Nhiều nghiên cứu về pitch tracking đã được báo cáo trong nhiều năm liền, và cho đến bây giờ vẫn còn là một đề tài đang phát triển mạnh mẽ.[12][11] 3.1.4 Nguyên tắc cơ bản của pitch tracking [22] Dù có rất nhiều kỹ thuật pitch tracking, nhưng hầu hết tất cả các loại đều đi theo quy trình chuẩn sau: • Chia nhỏ đoạn âm thanh ra làm nhiều cửa sổ con (mỗi cửa sổ con khoảng 20ms). Các cửa sổ có thể chồng lên nhau. • Tính toán giá trị cao độ cho từng cửa sổ • Loại bỏ những đoạn không phải âm thanh mong muốn hoặc khoảng lặng. Việc này có thể dùng ngưỡng độ lớn âm thanh hay ngưỡng cao độ. • Làm mịn chuỗi cao độ (pitch) bằng những bộ lọc 34 Hình 12: Nguyên tắc cơ bản của phương pháp pitch tracking Việc chọn kích thước cửa sổ và khoảng cách các cửa sổ chồng lên nhau được thực hiện theo những nguyên tắc sau: • Kích thước cửa sổ phải chứa đủ ít nhất hai chu kỳ sóng âm. Chẳng hạn, giới hạn cao độ của giọng nói người khoảng từ 50-1000Hz và tần số lấy mẫu của âm thanh là 16000 mẫu/ giây, khoảng kích thước cửa sổ có thể được tính toán như sau: ƒ Nếu f=50 Hz, chu kỳ cơ bản = 16000/50=320 mẫu. Vậy kích thước cửa sổ sẽ là 640 mẫu. ƒ Nếu f=1000Hz, chu kỳ cơ bản =16000/1000=16 mẫu. Kích thước cửa sổ sẽ là 32 mẫu. • Kích thước cửa số không nen quá lớn vì sẽ ảnh hưởng đến đặc trưng của âm thanh trong cửa sổ. Ngoài ra, kích thước cửa sổ còn ảnh hưởng đáng kể đến thời gian tính toán. • Việc chọn lựa kích thước các cửa sổ chồng lên nhau hay không tùy thuộc vào khả năng của máy tính và yêu cầu về thời gian đáp ứng của hệ thống. Nếu kích thước các cửa sổ chồng lên nhau lớn thì số lượng cửa sổ nhiều và đương nhiên, việc tính toán sẽ chậm và ngược lại. Có rất nhiều phương pháp để tính giá trị cao độ cho một cửa sổ, trong đó có thể kể đến các phương pháp sau: • Phương pháp trên miền thời gian 35 o ACF : Autocorrelation function o SMDF: Average manitude difference function o SIFT: Simple inverser filter tracking • Phương pháp trên miền tần số o Harmonic product spectrum o Cepstrum 3.1.5 Phương pháp Autocorrelation (ACF): Tự tương tác Autocorrelation là phương pháp cổ điển trong pitch tracking. Phương pháp autocorrelation cô lập và theo dõi các đỉnh năng lượng của âm thanh, từ đó có thể tính ra giá trị của tần số cơ bản [22] Hình 13: Dạng đồ thị năng lượng của một sóng âm thanh Hình cho ta hình dạng độ thị năng lượng của một sóng âm thanh cơ bản với các đỉnh năng lượng được đánh dấu. Ta có thể theo dõi đồ thị dao động và quá trình lặp lại của các đỉnh này để suy ra giá trị chuy kỳ trong một số cửa sổ, từ đó ta sẽ tính được tần số cơ bản f0 của âm thanh. Việc này có thể tiếp tục thực hiện bằng cách sử dụng công thức theo phương pháp autocorrelation dưới đây: 36 (3-2) Vị trí τ nào làm cho ACF đạt cực đại thì đó chính là vị trí chu kỳ. Hình dưới minh họa phương pháp dùng hàm ACF để tìm chu kỳ: Hình 14: Minh họa phương pháp dùng hàm ACF để tìm chu kỳ Nói cách khác, với từng cửa sổ tín hiệu ta đã phân tích, ta dịch chuyển cửa sổ đi một đơn vị thời gian τ, tính ACF(τ). Xác định vị trí cực đại của hàm ACF cho ta vị trí của chu kỳ. 3.1.6 Xác định khoảng lặng Xác định khoảng lặng giúp tách biệt phần có âm thanh (giọng hát) và không có âm thanh (khoảng lặng) trong tín hiệu truy vấn. Sau khi tín hiệu truy vấn đã được lấy mẫu và chia thành từng cửa sổ, ta tiến hành đánh dấu những cửa sổ là khoảng lặng và đặt giá trị cao độ cho những cửa sổ này là 0 (pitch= 0) [22] 37 Một cửa sổ được xem là khoảng lặng khi và chỉ khi nó thỏa mãn điều kiện sau: (3-3) Do đặc trưng về năng lượng của mỗi bản thu âm khác nhau nên ta xác định ngưỡng T dựa trên một đoạn âm thanh mẫu “có tiếng” t giây của chính bản thu đó. (3-4) 3.2 Cài đặt thuật toán Dựa trên ý tưởng của hàm ACF, ta có thể cài đặt thuật toán tìm pitch tracking qua hai bước: • Bước 1: Xác định vị trí chu kỳ, đánh dấu những vị trí bắt đầu kết thúc của một chu kỳ • Bước 2: Chia tín hiệu thành từng cửa sổ con, xác định khoảng lặng và tần số của những cửa sổ không phải là khoảng lặng dựa vào vị trí của chu kỳ xác định ở bước 1. Trước hết ta xác định nội dung vài hằng số cơ bản: • PeriodMin: độ dài ngắn nhất có thể chấp nhận được của chu kỳ sóng âm thanh, được tính bằng (thời gian) * Tần số lấy mẫu của tập tin âm thanh. Trong hệ thống này, độ dài ngắn nhất của chu kỳ được chọn là 3mili-giây. • PeriodMax: độ dài dài nhất có thể chấp nhận được của chu kỳ sóng âm thanh, được tính bằng (thời gian) * Tần số lấy mẫu của tập tin âm thanh. Trong hệ thống này, độ dài ngắn nhất của chu kỳ được chọn là 24 mili-giây. Những hằng số này được xác định dựa trên khoảng tần số của giọng người có thể phát ra được. Với mỗi vị trí bắt đầu của một chu kỳ, ta xác định vị trí mới của chu kỳ bằng công thức: 38 (3-5) Vị trí của chu kỳ là giá trị r mà tại đó hàm ACF cho là cực đại: (3-6) Phương pháp pitch tracking dựa trên ACF có thể được cài đặt như sau: 1. Khởi tạo giá trị Pos = mảng đánh dấu vị trí các pitch Signal = Tín hiệu sóng âm theo thời gian (đọc thông tin từ định dạng WAV) t = 0 2. while t < length(Pos) – 2 * PeriodMax do if (Mlag == 0) MMin = PeriodMin 3. Mmax = PeriodMax 4. else MMin = max([PeriodMin, Mlag - 23]) 5. MMax = min([PeriodMax, Mlag + 24]) 6. Fill zeros array Cm[1, MMax-MMin+1] 7. For iCm = MMin to Mmax do Tính Cm(iCm-MMin+1) theo ACF* 8. MLag = max(Cm) 9. Pos Å t + vị trí cực đại của Cm 39 10. MLag = MLag +MMin - 1; 11. t = t + Mlag Với mỗi cửa sổ khác khoảng lặng, ta xác định vị trí pos[mid] với mid là vị trí chu kỳ nằm giữa cửa sổ. Tần số âm thanh của cửa sổ được tính bằng công thức (3-7) Tần số âm thanh sẽ được chuyển sang đơn vị bán cung (công thức ở phần trên 3-7 ) 3.3 Biểu diễn đặc trưng [7] Từ kết quả của việc xử lý giai điệu của phần trên ta được chuỗi các nốt có tần số cơ bản. Từ đó ta thực hiện tiếp việc biểu diễn đặc trưng của các giai điệu. Biểu diễn đặc trưng này được dùng cho truy vấn và cho cơ sở dữ liệu. Một giai điệu ở đây được định nghĩa như là một chuỗi của L nốt n1:L. Note ni= được định nghĩa bởi cao độ pi trong các note MIDI bj: sự bắt đầu thời gian của note ei thời gian kết thúc của note Các đoạn giai điệu được biểu diễn như là các vecto cao độ được đưa ra từ các chuỗi các nốt. Đưa ra một giai điệu n 1:L vector cao độ được đưa ra như sau. Đầu tiên, các khoảng lặng giữa các nốt liên tiếp được xóa bởi sự kéo dài của các khoảng của một note trước đó đến sự bắt đầu của note sau, ví dụ ei Å bi+1 với i=1,...,L-1. Mỗi note , một vecto cao độ pi với chiều dài d được đưa bằng việc xác định giá trị cao độ của giai điệu trong w(s) cửa sổ bắt đầu từ nốt bắt đầu bi. Chính xác hơn, giá trị cao độ được xác định trên một một hệ thống thời gian pi= bi +j *w/(d-1) j=0,…,d-1. (3-8) Không vecto cao độ nào được đưa ra nếu của sổ truy cập đến khoảng trắng của nốt cuốt cùng bi +w > eL. Kết quả trả về vecto cao độ pi được chuẩn hóa để trở thành vô nghĩa. Tất cả các vecto 0 được lờ đi bởi vì chúng chứa nội dung mang lượng thông tin thấp (pitch=0) 40 Hình 15: Một ví dụ về vector biểu diễn đặc trưng của giai điệu Hình 3-8 chỉ ra một ví dụ của việc rút vector đơn vị bởi việc dụng kích thước cửa sổ w=3s à chiều dài vector d=20. Bảng trên chỉ ra một phần của một giai điệu và hình dưới của hình trên chỉ ra đầu tiên 4 của vector pi và vị trí đưa ra của chúng là bi đề cập ở trên đã làm việc tốt nhất trong các thí nghiệm của chúng ta. Dùng phương, pháp trên để tạo đặc trưng cho các đoạn giai điệu ở trong cơ sở dữ liệu. Từ đó chỉ mục các đoạn giai điệu được cấu tạo bởi sự trích chọn vecto cao độ từ cơ sở dữ liệu giai điệu.Chỉ mục kết quả chứa một danh sách của các bản ghi trong đó s chỉ bài hát bi chỉ ra vị trí của bài hát và pi biểu diễn các đoạn giai điệu. Tạo mục lục cho các giai điệu dựa vào các vecto đặc trưng sẽ làm cho việc tìm kiếm trên cơ sở dữ liệu trở nên dễ dàng và nhanh chóng hơn. [7] 3.4 Truy xuất các giai điệu (Thuật toán matching) Trước hết để truy xuất các giai điệu dựa vào các truy vấn đầu vào ta phải tìm sự giống nhau giữa truy vấn đưa vào với các giai điệu trong cơ sở dữ liệu ta dùng thuật toán DTW [theo phần 2.3.2] 3.4.1Tìm kiếm bằng thuật toán DTW 41 Sự giống nhau của các đoạn giai điệu ở đây được đo bằng việc dùng khoảng cách Euclid giữa các vector đơn vị. Một cách chính thức, hai vecto cao độ pi và pj định nghĩa các điểm trong d-chiều không gian nơi mà khoảng cách được đưa ra bởi (3-9) Khoảng cách Euclide thì không chỉ đơn giản mà dường như còn đo hiệu quả với những cái tương tự. Ý tưởng về thuật toán đã nói ở phần trên, phần này sẽ trình bày cụ thể phần cài đặt thuật toán tìm kiếm giai điệu dựa trên đặc trưng chuỗi cao độ (Theo phần trình bày về thuật toán DTW ở phần 2.4.3) Sau khi đã lấy được chuỗi tần số cơ bản của âm thanh truy vấn theo thời gian, ta sẽ đem so sánh với những mẫu đã có sẵn trong cơ sở dữ liệu để tính khoảng cách DTW. Việc tính khoảng cách DTW được thực hiện bằng thuật toán sau: 3.4.2 Cài đặt thuật toán 1. Q = Chuỗi đặc trưng của giai điệu truy vấn. T = Chuỗi đặc trưng của giai điệu trong cơ sở dữ liệu. 2. Khởi tạo giá trị D[1, 1] = abs(Q[1] – T[1]) 3.for i = 1 to length(Q) do for j = 1 to length(T) do minLocalPath = Tìm min khoảng cách trong các đường đi cục bộ ( theo Hình 2-4 hoặc Hình 2-5 ) 4. D[i, j] = minLocalPath + abs(abs(Q[i] – T[j]) 5. Khoảng cách DTW = min{D[length(Q), k], k = 1.. length(T)} 42 Giá trị DTW của một giai điệu trong CSDL với giai điệu truy vấn đặc trưng cho sự sai khác của hai giai điệu đó và được sử dụng làm cơ sở để sắp xếp các giai điệu trong danh sách kết quả tìm kiếm Hạn chế: Thuật toán dựa trên giả thiết người dùng hát từ đầu bài hát. Để giải quyết ta chia một bài hát ra làm nhiều đoạn giai điệu chủ đề nhỏ hơn. Việc chia bài hát ra làm nhiều giai điệu chủ đề được thực hiện lúc tạo cơ sở dữ liệu. 3.5 Sự trả về các giai điệu Để thu được danh sách cuối cùng của các giai điệu truy xuất được, các giai điệu đã chọn được sắp xếp theo khoảng cách của chúng để toàn bộ truy vấn gồm chuỗi các note. Hàng thì được thực thi bởi việc kiểm tra tất cả phép nối được duy trì trong bước trước. Phần 3.3 [7] Việc ghép nối là được biểu thị bởi với: • bq là vị trí của vecto cao độ của truy vấn • mj thì dùng kích thước cửa sổ để sửa đổi • bc là sự đưa ra vị trí của các đoạn giai điệu trong cơ sở dữ liệu • s là bài hát. Thêm vào đó, để t0 (q) và t1 (q) biểu thị thời gian bắt đầu của note truy vấn đầu tiên và thời gian kết thúc của note cuối cùng của truy vấn, theo một thứ tự tương ứng. Sau đó thời gian miền đáp ứng toàn bộ truy vấn trong giai điệu đã chọn được định nghĩa bởi (3-9): t0(c) = bc-(bq-t0 (q))/mj và t1(c) =bc+ (t1 (q)-bq)/mj (3-10) Toàn bộ truy vấn và phân đoạn được chuẩn hóa theo cao độ và thời gian cho việc tính toán khoảng cách. Một chuỗi các note n1:L được chuẩn hóa bởi việc thực thi các phương thức pi Å pi – p’, bi Å (bi-b1)/tdur và ei Å(ei –b1)/tdur với j=1,…,L là trung bình cao độ 43 tdur= eL-b1 là khoảng thời gian của chuỗi . Dưới đây, thuật ngữ đoạn giai điệu được chọn liên quan đến miền giai điệu được chọn. Bảng dưới trong hình 4 chỉ ra một ví dụ đoạn đã được chọn ra được xác định thế nào cho một so khớp. Hình phía dưới trong hình 4 chỉ ra sự chuẩn hóa truy vấn và chuẩn hóa đoạn giai điệu candidate Hình 16: Minh họa việc ghép nối giữa truy vấn và các đoạn giai điệu Khoảng cách giữa chuẩn hóa truy vấn và đoạn chuẩn hóa các đoạn thu được thì được đánh giá bởi việc dùng thuật toán đệ quy (Recursive Alignment) đề ra bởi Wu et al. Birefly, thuật toán đệ quy (RA) dùng thuật toán top-down để tiếp cận. Thứ nhất, phương pháp chia đoạn tìm được trong hai nửa tại vị trí 0.5. Truy vấn thì cũng được chia thành hai nửa nhưng dùng nhiều điểm chia có thể, ví dụ: 0.45, 44 0.5, and 0.55. Cho mỗi điểm chia, hai nửa được so sánh với hai nửa trong đoạn candidate để đo khoảng cách. Điểm chia mà đưa ra khoảng cách nhỏ nhất đầu nối cho hai nửa được duy trì. Sau đó phương pháp áp dụng thủ tục ở trên cho việc chia đôi hai nửa một cách độc lập trong một phương thức đệ quy. Mặt khác RA tìm thuật toán phổ biến nhất cho lần đầu tiên và sau đó đệ quy tiếp tục để căn chỉnh các đoạn nhỏ hơn. Kết quả là RA trả về khoảng cách giữa căn chỉnh chuỗi các note. Sự đánh giá khoảng cách trên được thực thi cho mỗi phép nối. Khoảng cách nhỏ nhất nối đoạn giai điệu đã chọn được duy trì, từ đó có thể tồn tại nhiều đoạn được chọn trên một giai điệu. Cuối cùng, danh sách được chọn được sắp xếp theo khoảng cách tăng dần và trả về cho người dùng. Nếu các giai điệu được truy xuất từ audio, cũng các đoạn giai điệu đã chọn được trả về cho phép chơi lại các giai điệu truy xuất được trong các bản ghi nhạc bình thường. [7] 45 Chương 4. KẾT QUẢ VÀ THỰC NGHIỆM 4. Thực nghiệm Hiện nay có hơn 20 hệ thống QBH trên thực nghiệm, một danh sách đầy của chúng được đưa ra trên trang hệ thống MIR. Cấu trúc của chúng có thể khác nhau, nhưng tất cả chúng thì thỏa mãn chức năng tìm kiếm bản nhạc bởi giai điệu được đưa đến từ micro từ âm thanh hoặc tiếng huýt sáo. Trong số chúng có thể chia ra thành nhiều hệ thống QBH với giao diện web, cái mà thường được cài đặt trong một định dạng của Java. Trong bảng 1 có nhiều hệ thống, hầu hết giống với Sloud QBH về chức năng cơ bản. Trong tất cả các hệ thống QBH tìm kiếm được cài đặt trong hai trạng thái: xử lý truy vấn từ bài hát và tìm kiếm thực các giai điệu trong cơ sở dữ liệu, bài hát đang được chuyển đổi, kết quả tìm kiếm cơ bản tùy thuộc vào chất lượng của truy vấn. Nó bị ảnh hưởng bởi cả chất lượng phát âm và kinh nghiệm ca hát của một ca sĩ và sự đúng đắn giữa cuộc hội thoại Humming và MIDI trong hệ thống với hướng dẫn ký hiệu giai điệu. Thường thì nó rất khó để điều khiển chất lượng kết nối giai điệu “humming” với kinh nghiệm của một ca sĩ. Như một nguyên tắc, người phát triển hệ thống đề nghị đánh giá ảo chất lượng của việc nhận dạng sau khi kết thúc việc giải quyết humming. Sloud QBH, đối lập với các hệ thống tương tự, có một khả năng để điều khiển độ chính xác trong thời giai thực, như là đánh giá chất lượng của truy vấn bằng tai. 4.1 Phương pháp cài đặt và làm thực nghiệm Sử dụng gói open source MaArt để kiểm tra quá trình cơ bản của một hệ thống truy vấn âm nhạc dựa vào giai điệu đơn giản. Download mã nguồn tại trang địa chỉ sau Cấu hình hệ thống thực hiện trên môi trường máy ảo cài đặt ubuntu. 4.1.1 Dữ liệu thực nghiệm Dữ liệu thực nghiệm là các đoạn thu âm các giai điệu hát vào hoặc ngân nga vào được lưu lại dưới dạng mặc định là wav. Các đoạn thu âm này sẽ được chuyển đổi sang dạng midi để trở thành truy vấn hoặc trở thành cơ sở dữ liệu cho việc tìm kiếm. 46 • Cách tạo file midi: o Thu âm một đoạn nhạc bằng trình ghi nhạc soundrecorder được lưu dưới định dạng wav. o Convert bản thu ở trên từ wav sang định dạng midi bằng một chương trình convert viết bằng một shell scripts sau: #! Bin/bash n=`ls *.wav` for i in $n; do file=$1 fileorg=$1 file=${file/.wav/} Echo –n Converting “$fileorg” to “$file.mid” Wave2midi “$fileorg” “file.mid” > /dev/null 2> /dev/null Count=$? Echo done shift done rm –f $pipe rm –f $sem Shell script trên sẽ convert cả một thư mục chứa file wav thành file mid tương ứng. Hình minh họa như dưới đây 47 Hình 17: Hình biểu diễn quá trình chuyển đổi từ WAV sang MIDI • Tạo một cơ sở dữ liệu các file nhạc đuôi midi bằng cách: + Tải trực tiếp các file midi từ midi.com + Tạo các file midi như ở phần trên 4.1.2 Dịch gói open source và sử dụng - Dịch: trong quá trình dịch gặp rất nhiều lỗi do thiếu thư viện vì vậy phải chạy từng tools một và thêm thư viện vào. - Có hai phương pháp truy vấn để đưa ra kết quả đó là: • Tìm kiếm dựa trên giai điệu: Dựa vào bản thu âm mà đưa ra các truy vấn đến cơ sở dữ liệu. Hình minh họa tìm kiếm bằng giai điệu 48 Hình 18: Hình minh họa kết quả mô tả một truy vấn bởi giai điệu • Tìm kiếm dựa trên đặc trưng: Tìm kiếm theo đặc trưng là dựa vào dãy biểu diễn các note để so sánh sự tương đồng. Trong tìm kiếm này có ưu điểm là không phụ thuộc vào giai điệu mà người dùng “hum” vào mà chỉ phụ thuộc vào các note. 49 Hình 19: Mô tả kết quả của một truy vấn bởi đặc trưng 4.2 Đánh giá về bộ dữ liệu truy vấn và cơ sở dữ liệu Quá trình và kết quảthực nghiệm: Thực hiện thu âm các bản nhạc theo các khoảng thời gian khác nhau với thời gian tương ứng là t =10s, 20s, 30s. Qua hai lần thử nghiệm với tổng số lần truy vấn là 50 lần ta có bảng sau: 50 Thời gian 50(truy vấn ) 10s 20s 30s Kết quả tìm thấy 24 36 43 Kết quả tìm thấy(%) 48% 72% 86% Bảng 1 Minh họa độ chính xác của từng bộ truy vấn Hình 20 minh họa kết quả độ chính xác của kết quả tìm kiếm Thời gian Kết quả Số lần 10s 20s 30s Kết quả chính xác 10 29 40 Kết quả tính theo (%) 20% 58% 80% Bảng 2 Minh họa kết quả tìm kiếm chính xác theo từng bộ truy vấn 48 72 86 0 10 20 30 40 50 60 70 80 90 100 10 s 20 s 30 s Do dai truy van (s) Do chinh xac cua truy van 51 Hì nh 21 Minh họa kết quả tìm kiếm theo độ chính xác tuyệt đối Thời gian 10s 20s 30s Kết quả chính xác 15 36 44 Kết quả tính theo (%) 30% 72% 88% Bảng 3 minh họa kết quả tìm kiếm trong top-3 theo từng bộ truy vấn 20 58 80 0 10 20 30 40 50 60 70 80 90 100 10 s 20 s 30 s Do dai truy van (s) Do chinh xac cua truy van 30 76 88 0 10 20 30 40 50 60 70 80 90 100 10 s 20 s 30 s Do dai truy van (s) Top-3 52 Hình 22 Minh họa độ chính xác kết quả tìm kiếm theo top-3 Thời gian 10s 20s 30s Kết quả chính xác 18 40 45 Kết quả tính theo (%) 36% 80% 90% Bảng minh họa kết quả tìm kiếm theo top -5 Hình 23. Minh họa kết quả tìm kiếm theo top-5 theo từng bộ truy vấn Nhận xét: Với truy vấn thì truy vấn nào càng dài thì kết quả trả về càng chính xác hơn. Vì nó mang nhiều đặc trưng nhận dạng của bản nhạc hơn. Theo các bảng và đồ thị ở trên ta thấy độ chính xác của hệ thống ở mức bình thường. Hiện nay trên thế giới đã có rất nhiều máy tìm kiếm âm thanh có hiệu suất cao.Tuy nhiên kết quả này không ổn định vì có thể do thời gian thu âm dài nhưng có thể trong kết quả trả về không được chính xác bằng các truy vấn ngắn hơn vì một số lý do như âm lượng thu không đủ lớn, nhiễu… 30 76 90 0 10 20 30 40 50 60 70 80 90 100 10 s 20 s 30 s Do dai truy van (s) Top-3 53 4.3 Những việc chưa làm được Chưa xác định được thời gian truy cập của từng truy vấn tại các khoảng thời gian khác nhau, tình được thời gian đáp ứng trung bình của hệ thống với từng truy vấn vì cơ sở dữ liệu các bản nhạc chưa đủ lớn để xảy ra một thời gian cho truy vấn. Ta nhận thấy độ phức tạp của thuật toán tuyến tính phụ thuộc vào độ dài đoạn truy vấn. Chưa thử được trên nhiều bộ dữ liệu khác nhau để đưa ra sự khác nhau giữa các bộ dữ liệu. 54 KẾT LUẬN Trong luận văn này đã trình bày những hiểu biết của mình về xây dựng hệ thống tìm kiếm thông tin âm nhạc dựa trên cơ sở dữ liệu do giọng người hát. Trong hệ thống bao gồm các phần: • Phần xử lý âm thanh truy vấn: sử dụng kỹ thuật pitch tracking để rút trích đặc trưng cao độ của âm thanh truy vấn bằng việc sử dụng phương pháp autocorrelation. • Biểu diễn đặc trưng đường cao độ thành một đặc trưng phù hợp trong việc tìm kiếm trong cơ sở dữ liệu. Đặc trưng này được sử dụng trong quá trình tìm kiếm • Tìm kiếm và so sánh đặc trưng trong hệ thống được thực hiện bằng phương pháp DTW. • Phần thực nghiệm: Kết quả thu được khi test thử một demo open source trên hệ điều hành ubuntu. Phát triển tiếp theo Cùng với sự bùng nổ khả năng lưu trữ của máy tính, truy vấn thông tin trở thành một đề tài rất quan trọng trong thời gian gần đây. Việc xây dựng một hệ thống truy vấn phù hợp với bản chất của dữ liệu mà nó thao tác trên đó là rất cần thiết. Việc này sẽ tăng hiệu quả cho việc tìm kiếm thông tin và làm cho giao tác giữa người và máy trở nên gần gũi. Dù đã đạt được những bước tiến cụ thể, lĩnh vực truy vấn bằng giọng hát vẫn cần những nghiên cứu xa hơn để có thể dựa vào ứng dụng thực tế: • Truy vấn trên bộ dữ liệu lớn: Những đề tài về truy vấn âm nhạc bằng giọng phát hiện nay chỉ tập trung vào đặc trưng và phương pháp tìm kiếm. Để có thể đưa ứng dụng vào việc thương mại hoá, những phương pháp cụ thể để truy vấn trên một bộ dữ liệu lớn (hàng chục ngàn bài hát) với thời gian đáp ứng của hệ thống phải được xem xét kỹ lưỡng. • Tự động rút trích thông tin giai điệu trên dữ liệu nhạc số thông thường: Trong đề tài này, cơ sở dữ liệu được xét đến chỉ dừng lại ở MIDI đơn âm. Để có thể có được một bộ dữ liệu lớn mà không tốn quá nhiều công sức, việc rút trích giai điệu chủ đề trên một tập tin MIDI đa âm nên được cân nhắc đến. Đây là một bài toán khó và thường thì lời giải sẽ không được rạch ròi đúng sai với một 55 dữ liệu cụ thể do việc nhận được giai điệu chính từ một bản nhạc phức tạp đa âm (như giao hưởng, concerto, …) cũng không phải đơn giản với những người không có hiểu biết nhiều về âm nhạc. Bài toán còn trở nên phức tạp hơn nếu định dạng dữ liệu là những bản nhạc số thông thường như WAV, MP3, WMA. • Phát triển hệ thống tìm kiếm trên điện thoại di động. Hiện tại mới phát triển một hệ thống tìm kiếm trên điện Nhưng nó lại tìm kiếm trên bản thu âm chứ không phải là dựa trên giai điệu mà người dùng ngân nga vào. Như chúng ta biết điện thoại di động ngày nay rất phổ biến vì vậy ta nên hướng đến nó. Để thực thi một hệ thống tìm kiếm trên điện thoại di động thì ta phải có một tổng đài cố định làm nhiệm vụ như một máy tìm kiếm âm nhạc như đã xây dựng ở trên. Việc tìm kiếm sẽ diễn ra như sau: Người dùng sẽ gọi đến tổng dài cố định nào đó (1900xxx) sau đó sẽ hát hoặc ngân nga giai điệu truy vấn đến tổng đài. Tổng đài sẽ làm nhiệm vụ xử lý truy vấn, tìm kiếm để trả về kết quả qua tin nhắn thoại cho người dùng. 56 TÀI LIỆU THAM KHẢO Tài liệu tiếng Việt [1] Học viện bưu chính viễn thông 2007. Xử lý âm thanh và hình ảnh [2] Lê Tiến Thường, Trần Ngọc Phiên, Trần Đức Tiến.Phương pháp mới trích chu kỳ cao độ trung bình ứng dụng trong nhận dạng thanh điệu tiếng Việt. [3] Khóa luận tốt nghiệp của sinh viên Nguyễn Quốc Đính. Nhận dạng giọng nói. [4] Tạp chí BCVT & CNTT kỳ 3 10/2007. Xây dựng và khảo sát độ dài từ khóa trong nhận dạng người nói phụ thuộc vào từ khóa tiếng Việt theo mô hình Markov ẩn. Tài liệu tham khảo tiếng anh [5] Valeriy Lobaryev Gene Sokolov Alexandr Gordeyev. Sloud Query-by Humming Search Music Engine. National Aerospace University Chkalov str.17 Kharkiv, 61070, Uckrane & USA [6] Tim Anderson April 2008. Development of a query by humming system. Sypervisor: Andrew naftel. [7] Matti Ryynanen and Anssi Klapurri. Query by humming of midi and Audio using Locality sensitive Hashing. Tampere University of Technology Institute of Signal Processing, P.O.Box 553, FI – 33101 Tampere, Finland. [8] Javier Thaine B.Eng., MeGill university,Dec 5 2007. A Query by humming approach to music retrieval. Simon Fraser University Library Bungary, BC, Canada. [9] Presented at the 116th Convention 2004 May 8-11. A Query by humming system using MPEG-7 Descriptors, Audio Engineering Society Convention Paper 6137. Berlin, Germany. [10]Annie Ding, Calvin On, Edmond Lau. 6.830: Database Systems Final Project Report Massachusetts Institute of Technology. MusicDB: A Query by humming System [11] Asif Ghias, Jonathan Logan, David Chamberlin, Brian C. Smith-1995. Query by Humming Musical Information Retrieval in An Audio Database. Proceedings of ACM Multimedia 95, (pp. 231-236). 57 [12] Man Hon Wong and Wai Man Szeto The Chinese University of Hong Kong. Stream Segreation Algorithm for Pattern Matching in Polyphonic Music Database. [13] Fraunhofer Institut Digitale Medientechnologie. Query by Humming Melody Recognition System. Dr-Ing. Karheinz Brandenburg Ehrenbergstr. 3198693 llmenau, Germany. [14] Lloyd A.Smith, Rodger J.McNab and lan H.Writen. Music Information Retrieval Using Audio Input. Department of Computer Science University of Waikato Private Bag 3105 Hamilton, New Zealand. [15] Rui Pedro pinto de Carvalho e Paive, 2006. Melody Detection in Polyphonic Audio. University of Coimbra in partial fulfillment of the requirement for the degree of Doctor of Philosophy in Informations Engineering. [16] Jeffrey Daniel Frey May 2008. Finding song melody similarities using a DNA string matching algorithm. [17] Jonathan T.Foote. Content-based Retrieval in MIDI and Audio. Institute of Systems Science National University of Singapore Heng Mui Keng Terrace, Kent Ridge Singapore 119597. [18] M. nand Raju, Bharat Sundaram and Preeti Rao, Presented at National Conference on Comunications, NCC 2003, Jan 31- Feb 2, IIT Madras 2003, A Query- by-humming based music retrieval system.Dept. of EE, I.I.T. Kanpur. [19] Malcolm Slaney and Michael Casey. 2008 Locality-Sensitve Hashing for Finding Neearst Neighbors. IEEE Signal Processing Magazine. [20] Blackburn, S. G. (2000) Content Based Retrieval and Navigation of Music UsingMelodic Pitch Contours (PhD Thesis). University of Southampton. [21] Pardo, B., Shifrin, J., & Birmingham, W. (2004). Name that Tune: A Pilot Study in Finding a Melody from a Sung Query. Journal of the American Society for Information Science and Technology. [22]Dowling, W. J. (1978) Scale and Contour Two components of a Theory of Memory for Melodies. Psychological Review, 341-354 58 [23] Lie Lu, Hong You, Hong – Jiang Zhang. A new approach to query by humming in music retrieval, Microsoft Research, China 5F, Beijing Sigma Center 49 Zhichun Road, Beijing 100080, China. [24] 4-4%20Dynamic%20Time%20Warping [25] rd.asp?title=4-4%20Recording%20from%20Microphone [26] .asp?title=4-2%20Reading%20Wave%20Files [27] [28] [29]

Các file đính kèm theo tài liệu này:

  • pdfThiết kế hệ thống nhận dạng các dạng âm thanh.pdf
Luận văn liên quan