| 摘要: | 將一個短的查詢樂段 (query) 與一個較長的參考樂段 (reference) 做比對，並依照查詢與參考樂段的相關性，建立出相關參考樂段之排名，即為以內容為基礎的音樂擷取系統的目的。這種系統的效能取決於其採用的音樂比對 (matching) 法。以內容為基礎的音樂擷取系統中，最常使用的比對技術為字串比對 (string-based matching) 與幾何比對 (geometric matching) 兩種，此兩種比對方式在最近幾年被廣泛的探討。前者比對方式較具彈性且快速，然而後者則具較高之正確率。
在本論文中，我們研究上述兩種比對技術，分別改善其問題並提出一字串比對的改良版本，稱之為 RLCS法，與幾何比對的改良版本。
最長共同子序列 (longest common subsequence: LCS) 為以字串為基礎的比對中最常見的一種相似度量測方式，因為它極具彈性且有效率，但它僅反應出兩序列的全域相似度，並不適合前述的內容為基礎的音樂擷取系統。因此我們提出一個 LCS 的變化版本，rough longest common subsequence (RLCS)，並利用RLCS以及我們所定義的參考樂段跨越寬度(width-across-reference，WAR) 與查詢樂段跨越寬度 (width-across-query，WAQ) 來計算兩序列的區域相似度。
我們亦提出改進D. Ó. Maidín [20] 所提的幾何比對方法。首先使用音程 (pitch interval) 取代音高 (pitch) 以達成音調不變性 (transposition invariance) ，同時避免在幾何比對時，搜尋最佳位置所需的垂直方向移動。除此我們還提出一個「分支與剪裁」(branch-and-prune)的機制用以加速搜尋。之後我們將音長 (duration) 特徵以音長比 (duration ratio) 取代之，以達成速度不變性 (tempo invariance)。無論如何，使用音程與音長比為特徵時，當一個音符的音高或音長改變時，會影響兩個連續音符之音程或音長比值，我們稱此問題為「反對稱性」(antisymmetry)。我們亦提出偵測與降低此反對稱性問題的方法。最後我們提出以平衡二元搜尋樹 (balanced binary search tree)來改進幾何比對演算法之時間複雜度。
The aim of a content-based music retrieval system is to match a short query melody against a longer reference melody to establish and rank the relevant references according to the similarity measurement. The performance of such a system is heavily dependent on the matching method adopted. Techniques of string-based matching and geometric matching, the most commonly used in content-based music retrieval systems, have been explored in the past few years. The former is more flexible and more efficient than the latter, and the latter has higher accuracy rate than the former.
In this dissertation, we investigate the improvement of these two matching techniques and propose an improved version of the string-based matching method, called RLCS, and an improved version of the geometric matching method.
The longest common subsequence (LCS) is commonly used for similarity measure in string-based matching techniques due to its flexibility and efficiency, but it reflects only the global similarity between two musical sequences. We propose a variant of the LCS, called the Rough LCS (RLCS), with which and the values of width-across-reference (WAR) and width-across-query (WAQ) we define and evaluate the local similarity between two musical sequences. We also improve the geometric matching proposed by D. Ó. Maidín [20] by the use of pitch interval instead of absolute pitch, to achieve transposition (key) invariance and avoid the vertical shifting required in the search of the best matching, required by D. Ó. Maidín’s method. We then further speed up the proposed method with the aid of a branch-and-prune mechanism. To achieve tempo invariance, we replace the feature of duration with duration ratio. However, the use of pitch interval and duration ratio might encounter antisymmetry problems caused by the change of pitch and the change of duration, respectively. Thus, we also propose to detect and reduce such problems. Finally, an efficient matching mechanism with the aid of a balanced binary search tree is proposed. |
