利用改進的最長共同子序列法做音樂比對
學年 97
學期 1
出版（發表）日期 2009-01-01
作品名稱 利用改進的最長共同子序列法做音樂比對
作品名稱（其他語言） Music Matching Using an Improved LCS Method
著者 林慧珍; 顏淑惠
單位 淡江大學資訊工程學系
描述 計畫編號：NSC98-2221-E032-034 研究期間：200908~201007 研究經費：707,000
委託單位 行政院國家科學委員會
摘要 隨著數位音樂文件數量上快速增加，音樂搜尋的研究領域日益受到重 視。以音樂內容來查詢音樂資料的方式已成為發展的趨勢，這方面的研究， 國內外的學術單位已陸續開發出一些應用系統並發表許多相關論文，這些查 詢系統在效能上仍有許多不足之處。本計畫擬提出一個有效率、具彈性的以 內容為基礎之音樂擷取系統。 音樂查詢系統中最關鍵的部份為音樂比對的演算法，其直接影響查詢效 能。在相關比對演算法研究中最常被使用的以文字比對 (string matching) 與幾 何比對(geometric matching) 兩種類型。幾何比對方法的特性是正確性高，但 時間複雜度也高，因此必須耗費大量的計算時間；而文字比對若採用單一特 徵則對大型資料庫的搜尋比對其正確性不夠高。因此本計畫擬提出一個以文 字比對為基礎，類似最長共同子序列(longest common subsequence: LCS)的方法 來量測兩個音樂序列的相似性，稱之為粗略最長共同子序列 (rough longest common subsequence: RLCS)。RLCS 使用音高 (pitch)與音符長度 (duration)為 特徵，且兩音符間之距離則以這兩個特徵之歐式距離或曼哈頓 (Manhattan distance or city block distance) 距離來量測。傳統的最長共同子序列 (longest common subsequence: LCS) 使用精確的字元比對 (exact match)，我們則採用粗 略比對，容許音符之間有些許差距。同時這個差距將回饋至RLCS 長度的計 算，若兩音符之間的距離越大，其增加的 RLCS 長度就越小。 此外 RLCS 長度不是唯一衡量比對結果好壞的依據；我們另外計算兩個 矩陣稱為「橫跨本文寬度」 (width-across-reference: WAR) 與「橫跨查詢寬度」 (width-across-query: WAQ)，這兩個矩陣中的數值分別代表共同子序列在本文 序列與查詢序列中所跨越的最小範圍之寬度，其值皆為越小越好。最後比對 分數參照 RLCS 長度、WAR、與WAQ 三個值加權來決定。 在本計畫當中擬提出一個新的方法來擷取旋律中近似重複樂段做為主旋 律集合。因為RLCS 具有區域比對能力，因此可以容易地應用在音樂的主旋 律抽取 (main melody extraction)，只要簡單的改變遞迴式中的初始條件並設定 分數閥值即可。實驗初步的結果顯示，粗略最長共同子序列的比對法，在資 料庫上搜尋有令人滿意的結果。而我們目前還有一些新的想法，例如將 RLCS 以位元向量 (bit-vector) 進行平行計算以降低時間複雜度，或是以小節為單位 並應用 RLCS 來做主旋律抽取等等，且所提的比對方法也持續地在研究與改 進當中。 為了拓展系統之應用性，本計畫擬將之移植到行動裝置 (mobile devices) 上，如行動電話 (Cellular Phone)、個人數位助理 (Personal Digital Assistant) 等 設備上，可做各種查詢，例如音樂隨選系統 (audio-on-demand)、線上卡拉OK 等，以實現更便捷的音樂查詢應用。期盼在國科會的支持下，順利完成計畫， 讓我們的研究對這個領域能有所貢獻。 With the widespread use of computers and internet, and the growth of the amount of diverse digital information including texture, musical, and image documents, demand for an efficient search engine over huge music databases become more and more urgent. This project emphasizes on the research of music search. Music retrieval based on text information has been implemented in many existing systems, but retrieval of a piece of music based on musical content has not yet been fully explored. For the task of content-based music retrieval or melody extraction, music matching is one of the crucial parts, which directly affects the performance of the system. For comparison of two melodic fragments, techniques based on geometric have been explored in the past few years. The advantage of geometric matching is its high accuracy rate of search; while the drawback is being time-consuming for the time complexity is usually higher than a polynomial of degree 2. The objective of this project is to develop a sequence comparison algorithm for music retrieval. The distance measure between a given query melody and a reference melody is defined as the minimal number of edit operations. Our approach, as a variant of the LCS method, uses rough comparison instead of exact comparison for two music notes. If this distance is smaller than a given threshold, then these two notes are considered to be roughly matched (or roughly equal, or similar) and the distance of two notes are feedback to the length of RLCS table. When we evaluate the length of RLCS, we simultaneously evaluate the matrices of width-across-query (WAQ) and width-across-reference (WAR), which describes how good the rough longest common subsequence distributed in the query and the reference, respectively. Meanwhile, the scoring matrix is also constructed concurrently by the length of RLCS, WAR, and WAQ matrices. In our preliminary experiments, we tested our searching approach over a collection of entire melodies. The results are satisfactory, but can be further improved by our new thoughts, such as column-wise parallel evaluation of the length of RLCS by bit-vectors. Our goal is to develop an efficient, convenient and widely applicable music retrieval system, that can be used as many applications such as audio-on-demand and online Karaok. In order to promote the applicability of our system, we shall apply it in mobile devices such as Cellular Phone or Personal Digital Assistance.
關鍵字 以內容為基礎之音樂擷取; 音樂搜尋; 幾何比對; 查詢樂段; 本文樂段; 分支與剪裁機制; 行動裝置; 主旋律抽取; 音樂隨選系統; 近似重複樂段; content-based music retrieval; music search; geometric matching; querymelody; reference melody; branch-and-prune mechanism; main melody extraction; mobile devices; audio-on-demand; approximately repeated melody
語言
相關連結

機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/47057 )

機構典藏連結