臺灣博碩士論文加值系統

在音樂內容擷取(music content-based retrieval)的研究領域，大多都是利用特徵的萃取，例如旋律(melody)、節拍(rhythm)、和弦(chord)等等，再利用這些特徵建立索引，以加速對音樂資料的搜尋。而有關音樂資料查詢最直接且簡便的方式，乃是哼唱一段旋律或由鍵盤輸入一段樂曲，做為查詢樣本(Query By Example, QBE)，分析出其音樂特徵，以尋找最近似的音樂物件。然而並非每位使用者都具有音樂專長，因此往往無法提供完全準確的音樂範例以進行精確查詢。因此，我們必須容許使用者在記憶中與現實音樂片段帶有些許差異的產生，如多音、少音與錯音等等。 也就是對音樂的查詢，必須具有允許容錯(fault tolerance)之近似搜尋(approximate search)的能力。目前於音樂資料中的允許容錯查詢仍然還有很大的改善空間，本研究的目的在於透過檢視現有字串比對技術，以尋找適用於音樂查詢所可能面臨之多音、少音、升音與降音等之近似比對的方法，期望再經過我們的改良，可以提升允許容錯之音樂查詢能力。

In the researches of music content-based retrievals, the researchers extract the features, such as melodies, rhythms and chords, from the music data and develop indices that will help to retrieve the relevant music quickly. The query by example (QBE) is widely used for multimedia content-based retrieval. Since users are not all expert in music, we cannot expect users to be able to precisely specify music query examples. Therefore, certain errors in music query examples, such as dropout notes, insertion notes, and transposition notes, should be allowed for users’ queries. That is, the fault tolerance ability in approximate search is needed for music query. However, there is still room for improvement in approximate music searching. In this research, we will investigate the ability of existing similar string matching techniques for performing the approximate music search. Thereafter, a new approach will be developed to enhance the fault tolerant music query.

摘要 I
Abstract II
誌謝 III
目錄 IV
表目錄 VI
圖目錄 VII
第一章 緒論 1
第二章 現有文獻探討 3
2.1音樂資料的近似搜尋 3
2.1.1利用近似字串比對 3
2.1.2利用近似數值比對 7
2.1.3近似混合內容容錯比對 10
2.2近似字串比對技術 13
2.2.1頻率分佈的近似比對 13
第三章 研究方法 18
第四章 效能評估 22
4.1實驗設定 22
4.2 單特徵的實驗分析 24
4.2.1 單特徵-旋律 25
4.2.2 單特徵-前後音差 29
4.3多特徵的合併實驗分析 33
第五章 結論與未來研究方向 40
參考文獻 41
表目錄
表 1、容錯比對說明 ................................................................................ 3
表 2、音樂數值差的絕對值可容許範圍(m=4) .................................... 10
表 3、兩字串間頻率分率Divergence為2 ........................................... 13
表 4、Edit distance特徵差距比較表 ..................................................... 38
表 5、Jaccard similarity特徵差距比較表 ............................................. 38
表 6、組合Jaccard similarity與Edit distance比較表 ......................... 39
圖目錄
圖 1、精確連接(exact link) ...................................................................... 4
圖 2、缺音連接(dropout link) .................................................................. 5
圖 3、多音連接(insertion link) ................................................................ 6
圖 4、走音連接(transposition link) .......................................................... 6
圖 5、音樂片段所建構R-tree索引的結果 ............................................ 8
圖 6、採用近似比對所對應到R-tree的節點 ........................................ 9
圖 7、QueST 音樂資料庫架構圖 ......................................................... 11
圖 8、Signature file 的例子 ................................................................... 12
圖 9、RBF 架構圖 ................................................................................. 12
圖 10、李文斯頓距離(distance為3) ..................................................... 15
圖 11、音樂查詢流程圖 ......................................................................... 18
圖 12、旋律分佈圖 ................................................................................ 23
圖 13、旋律特徵 - 多音與查詢樣本之平均差距 ............................... 26
圖 14、旋律特徵 - 少音與查詢樣本之平均差距 ............................... 27
圖 15、旋律特徵 - 錯音與查詢樣本之平均差距 ............................... 28
圖 16、旋律特徵 - 升調與查詢樣本之平均差距 ............................... 29
圖 17、音差特徵 - 多音與查詢樣本之平均差距 ............................... 30
圖 18、音差特徵 - 少音與查詢樣本之平均差距 ............................... 31
圖 19、音差特徵 - 錯音與查詢樣本之平均差距 ............................... 32
圖 20、音差特徵 - 升調與查詢樣本之平均差距 ............................... 33
圖 21、多特徵 - 多音與查詢樣本之平均差距 ................................... 35
圖 22、多特徵 - 少音與查詢樣本之平均差距 ................................... 35
圖 23、多特徵 - 錯音與查詢樣本之平均差距 ................................... 36
圖 24、多特徵 – 升調與查詢樣本之平均差距 .................................. 37

[1]R.J. Bayardo, Y. Ma, and R. Srikant, “Scaling up all-pairs similarity search,” WWW Conference, pp. 131-140, 2007.
[2]Arbee L.P. Chen, M. Chang, J. Chen, J.L. Hsu, C.H. Hsu, and Spot Y.S. Hua, “Query by Music Segments: An Efficient Approach for Song Retrieval,” In Proc. of IEEE Int’l Conf. on Multimedia and Expro, 2000.
[3]James C.C. Chen and Arbee L.P. Chen, “Query by Rhythm An Approach for Song Retrieval in Music Databases,” In Proc. Of Int’l Workshop on Research Issues in Data Engineering, pp. 139-146, 1998.
[4]M.T. Chen and J. Seiferas, “Efficient and Elegant Subword-Tree Construction,” Springer-Verlag, New York, 1985.
[5]B. Cui, L. Liu, C. Pu, J. Shen, and K. Tan, “QueST: Querying Music Databases by coustic and Textual Features,” Proceedings of the 15th international conference on Multimedia, pp. 1055-1064, 2007.
[6]L.R. Dice, “Measures of the Amount of Ecologic Association Between Species,” Ecology 26, pp. 297–302, 1945.
[7]E.A. El-Kwae and M.R. Kabuka, “Efficient Content-Based Indexing of Large Image Databases,” ACM Trans. On Information Systems (18:2), pp. 171-210, 2000.
[8]S.T. Goh and K.L. Tan, “MOSAIC: A Fast Multi-Feature Image Retrieval System,” Data and Knowledge Engineering (33:3), pp. 219-239, 2000.
[9]P. Hall and G. Dowling, “Approximate String Matching,” ACM Computing Survey, Vol. 12, NO.4, pp. 381-402, Dec. 1980.
[10]K.A. Hua, K. Vu, and J.H. Oh, “SamMatch: A Flexible and Efficient Sampling-Based Image Retrieval Technique for Large Image Databases,” Proc. of Multimedia ’99, Florida, pp. 225-234, Oct., 1999.
[11]P. Jaccard, “Étude comparative de la distribution florale dans une portion des Alpes et des Jura.” Bulletin de la Société Vaudoise des Sciences Naturelles 37, pp. 547-579, 1901.
[12]W. Lee and A.L.P. Chen, “Efficient Multi-Feature Index Structures for Music Data Retrieval,” In Proc. Of SPIE Conf. on Storage and Retrieval for Image and Video Database, 2000.
[13]C. H. Lin and Arbee L. P. Chen, “Indexing and Matching Multiple-Attribute Strings for Efficient Multimedia Query Processing,” IEEE Transactions On Multimedia, Vol. 8, No. 2, April 2006.
[14]C.C. Liu, J.L. Hsu, and Arbee L.P. Chen, “An Approximate String Matching Algorithm for Content-Based Music Data Retrieval,” In Proc. of IEEE Int''l Conf. on Multimedia Computing and Systems, pp. 451-456, 1999.
[15]C.C. Liu and Arbee L.P. Chen, “3D-List: A Data Structure for Efficient Video Query Processing,” IEEE Transactions on Knowledge and Data Engineering (14:1), pp: 106-122, 2002.
[16]Y-L. Lo and Shiou-jiuan Chen, “The Numeric Indexing For Music Data,” Proceeedings of the IEEE 22nd International Conference on Distributed Computing Systems (ICDCS''2002) Workshops -- the 4th International Workshop on Multimedia Network Systems and Applications (MNSA''2002), Vienna, Austria, pp. 258-263, 2002.
[17]Y-L. Lo, W-L. Lee, and L-H. Chang, “True Suffix Tree Approach for Discovering Non-trivial Repeating Patterns in a Music Object,” Journal of Multimedia Tools and Applications, Springer, Vol. 37, No. 2, April 2008, pp. 169-187.
[18]Y-L. Lo, C-H. Lee, and C-H. Wang, “Scalable Multi-feature Index Structure for Music Databases,” Information Sciences, Elsevier, Vol.179, Issue 15, pp. 2662-2675, July 2009.
[19]Y-L. Lo and Ling-Yi Tsai, "Approximate Searching for Music Data in Real-Valued Feature Indexing," Journal of Convergence Information Technology, vol. 4, no. 4, pp. 87-95, December 2009.
[20]E. McCreight, “A Space-Economical Suffix Tree Construction Alogorithm,” Journal of the Association for Computing Machinery (23:2), pp:262-272, 1976.
[21]G. Navarro, “A Guided Tour to Approximate String Matching,” ACM Computing Survey, Vol.33, No. 1, pp.31-88, Mar.2001.
[22]. S. Nepal and M.V. Ramakrishna, “Query Processing Issues in Image (Multimedia) Databases,” Proc. of Data Engineering, Washington, pp. 22-29, 1999.
[23]T. Phillips, “Approximate string matching,” C/C++ Users J., Vol. 12, No.4, Apr. 1994.
[24]S.W. Smoliar and H.J. Zhang, “Content-Based Video Indexing and Retrieval,” IEEE MultiMedia (1:2), pp. 62-72, 1994.
[25]Y.H. Tseng, “Content-Based Retrieval for Music Collections,” Proc. of ACM SIGIR on Research and development in information retrieval, pp.176-182, California, 1999.
[26]E. Ukkonen, “On-Line Construction of Suffix Tree,” Algorithmica (14:3), pp:249-260, 1995.
[27]P. Weiner, “Linear Pattern Matching Algorithms,” Proc. of Annual Symposium on Switching and Automata Theory, pp. 1-11, 1973.