臺灣博碩士論文加值系統

重覆片段為一串音符在音樂物件中重覆出現一次以上的音樂片段，而在一首音樂中會出現多次的片段，大部份均為主旋律或較容易為人們所熟悉與記憶的，因此我們可以利用此特徵來建構索引以加快音樂內容的搜尋。而非不重要重覆片段常用於分析音樂的重覆片段與尋找主旋律。所謂非不重要重覆片段，乃指在所有重覆片段中扣除該片段已全包含於其他更長片段中的項目，如此能大大減少重覆片段的項數，並大幅提昇音樂搜尋的效率。然而，在現有找尋音樂主旋律與非不重要重覆片段的技術，大多相當的耗時或需佔用指數次方的記憶體空間。因此在這篇研究報告中，提出了二種有效率的發現非不重要重覆片段技術，第一種是以節省執行時間為考量，能比現有技術更快速的找到非不重要重覆片段，而第二種則是以節省執行時所需的記憶空間為考量，它僅需線性的記憶空間，能僅比前一種技術較些微時間的付出，來換取節省大量的記憶體空間，以找尋音樂資料中非不重要重覆片段。 我們期望這些技術未來亦能應用於發現DNA重覆序列的比對中。

A repeating pattern is a sequence of notes appearing more than once in a music object. Most of the repeating patterns are key melodies or easy to familiarize and remember for people. Therefore, we can use the themes or the repeating patterns to construct indices that can speedup music retrieval. A non-trivial repeating pattern is commonly used in analyzing the repeated part of music data and looking for themes. Non-trivial repeating patterns exclude those patterns which are all contained in other longer patterns, such that we can reduce the redundancy of the repeating patterns and speed up music search. However, the existing techniques for discovering the theme and non-trivial repeating patterns for a music object are significantly time and memory space consuming. In this research report, we proposed two techniques which can efficiently discover non-trivial repeating patterns. The first one is a time saving scheme which can find non-trivial repeating pattern faster than existing techniques. The second is a memory space saving approach. It can use linear memory space and only with a little amount time pay out to find all non-trivial repeating patterns in music objects. We hope that our effort is helpful in discovering the repeating patterns of DNA sequences in the near future.

在音樂資料中有效率的發現非不重要重覆片段

第一章 緒論 1
1.1 背景與現況 1
1.2 論文架構 3
第二章 重覆片段在音樂資料中扮演的角色 5
第三章 文獻探討 7
3.1 關鍵旋律取得(KEY MELODY EXTRACTION) 8
3.2相關矩陣(CORRELATIVE MATRIX) 9
3.3 RP-TREE 14
第四章 快速片段萃取技術 19
4.1 演算法 19
4.2 範例說明 22
第五章 二列比較法 29
5.1 二列比較法演算法(TWO-ROW COMPARISON, 2RC) 29
5.2 範例說明 32
第六章 評估分析 37
6.1 音樂物件大小的影響 38
6.2 非不重要重覆片段長度之影響 40
6.3非不重要重覆片段數目的影響 42
第七章 結論與未來工作 44
參考文獻 46

表 目 錄
============
表 1音樂字串“fcadcafadfca”中所有重覆片段 6
表 2音樂字串“caaccaacdcbc”的所有非不重要重覆片段 13
表 3音樂字串“abcdefghabcdefghijabc”之所有非不重要重覆片般 18
表 4 音樂字串“abcdbcdabcabcd”中所有非不重要重覆片段 28
表 5音樂字串“abcdbcdabcabcd”中所有非不重要重覆片段 36
表 6實驗音樂物件長度與其最長非不重要重覆片段的平均長度 39

圖 目 錄
===========

圖 1音樂S的初始相關矩陣 9
圖 2設定第一個音符後的相關矩陣 10
圖 3設定第二個音符後的相關矩陣 10
圖 4處理完所有音符後的相關矩陣 11
圖 5音樂特徵S字串的RP-Tree 16
圖 6刪除所有長度為1的非非不重要重覆片段 17
圖 7刪除所有長度為2的非非不重要重覆片段 17
圖 8刪除所有長度為4的非非不重要重覆片段 17
圖 9產生長度為3重覆片段的RP-Tree 18
圖 10刪除所有非非不重要重覆片段後的RP-Tree 18
圖 11音樂S字串的初始矩陣 22
圖 12設定第一個音符後的矩陣 23
圖 13處理完所有音符後的矩陣 23
圖 14找出“abc”的非不重要重覆片段及次數 24
圖 15找尋完“abc”片段後之結果 25
圖 16找尋完“abcd”片段後之結果 26
圖 17找尋完“bcd”片段後之結果 27
圖 18執行完快速片段萃取技術後之結果 28
圖 19 S1與整個S字串的所有字元比對後之A陣列 32
圖 20 S2與整個S字串的所有字元比對後之A、B陣列 32
圖 21 S3與整個S字串的所有字元比對後之A、B陣列 33
圖 22 S4與整個S字串的所有字元比對後之A、B陣列 34
圖 23 S5與整個S字串的所有字元比對後之A、B陣列 35
圖24執行二列比較法後之結果 36
圖 25 Elapsed time vs. object size of music object 39
圖 26 Elapsed time vs. length of the longest pattern for the real data set. 41
圖 27 Elapsed time vs. length of the longest pattern for the synthetic data set. 41
圖 28 Elapsed time vs. no. of non-trivial repeating pattern for the synthetic data set. 43

參考文獻
[1]G. Davenport, T.A. Smith, and N. Pincever, “Cinematic Primitives for Multimedia,” IEEE Computer Graphics & Applications, Pages 67-74, July 1991.
[2]Y.F. Day, S. Pagtas, M. Iino, A. Khokhar, and A. Ghafoor, “Object-Oriented Conceptual Modeling of Video Data,” In Proc. Of IEEE Data Engineering, Pages 401-408, 1995.
[3]E.A. El-Kwae and M.R. Kabuka, “Efficient Content-Based Indexing of Large Image Databases,” ACM Trans. On Information Systems, Vol. 18, No. 2, Pages 171-210, April 2000.
[4]S.T. Goh and K.L. Tan, “MOSAIC: A Fast Multi-Feature Image Retrieval System,” Data & Knowledge Engineering, Vol. 33, Page 219-239, 2000.
[5]R. Hjelsvold, and R. Midtsraum, “Modeling and Querying Video Data,” In Proc. of Int”l Conf. on VLDB, Pages 686-694, 1994.
[6]K.A. Hua, K. Vu, and J.H. Oh, “SamMatch: A Flexible and Efficient Sampling-Based Image Retrieval Technique for Large Image Databases,” In Proc. ofACM Multimedia, Pages 225-234, 1999.
[7]C.C. Liu and ArbeeL.P. Chen, “3D-List: A Data Structure for Efficent Video Query Processing,” IEEE TKDE, to appear.
[8]S. Nepal and M.V. Ramakrishna, “Query Processing Issue in Image (Multimedia) Databases,” In Proc. of Int”l Conf. on Data Engineering, Pages 22-29, 1999.
[9]J.H. Oh and K.A. Hua, “Efficient and Cost-Effective Techniques for Browsing and Indexing Large Video Databases,” In Proc. of ACM SIGMOD, Pages 415-426, 2000.
[10]E. Oomoto and K. Tanaka, “OVID: Design and Implementation of a video-Object Database System,” IEEE Trans. on Knowledge and Data Engineering, Pages 629-643, August1993.
[11]S. W. Smoliar and H.J. Zhang, “Content-Based Video Indexing and Retrieval,” IEEE Multimedia Magazine, Pages 62-72,1994.
[12]S. Blackburn and D. DeRoure, “A Tool for Content-based Navigation of Music,” In Proc. of ACM Multimedia, Pages 361-368, 1998.
[13]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, Pages 139-146, 1998.
[14]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. ofIEEE Int”l Conf. on Multimedia and Expro, 2000.
[15]T.C. Chou, Arbee L.P. Chen, and C.C. Liu, “Music Databases: Indexing Techniques and Implementation,” In Proc. of IEEE Int”l Workshop on Multimedia Data Base Management Systems, 1996.
[16]A. Ghias, J. Logan, D. Chamberlin, and B.C. Smith, “Query by Humming: Musical Information Retrieval in an Audio Database,” In Proc. of ACM Multimedia, Pages 231-236, 1995.
[17]J.L. Hsu, C.C. Liu, and Arbee L.P.Chen, “Efficient Repeating Pattern Finding in Music Databases, “ In Proc. of ACMInt”l Conf. on Information and Knowledge Management, 1998.
[18]W. Lee and A.L.P. Chen, “Efficient Mult-Feature Index Structures for Music Data Retrieval,” In Proc. of SPIE Conference onStorageand Retrieval for Imageand Video Databases, 2000.
[19]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, Pages 451-456, 1999.
[20]C.C. Liu, J.L. Hsu, and Arbee L.P.Chen, “Efficient Theme and Non-Trivial Repeating Pattern Discovering in Music Databases,” In Proc. of IEEE Data Engineering, pp.14-21, 1999.
[21]Y.H. Tseng, “Content-Based Retrieval for Music Collections,” In Proc. of ACM SIGIR”99, Berkley, CA, USA, Pages 176-182, 1999.
[22]A.L. Uitdenbogerd and J. Zobel, “Manipulation of Music for Melody Matching,” In Proc. of ACM Multimedia, Pages 235-240, 1998.
[23]A.L. Uitdenbogerd and J. Zobel, “Melodic Matching Techniques for Large Music Databases,” In Proc. of ACM Multimedia, Pages57-66, 1999.
[24]E. Wold, T. Blum, D. Keislar, and J. Wheaton, “Content-based classification, search, and retrieval of audio,” IEEE Multimedia, vol. 3, no. 3, pp. 27-36, Fall 1996.
[25]J.L. Hsu, C.C. Liu, and Arbee L.P.Chen, “Discovering Non-Trivial Repeating Patterns in Music Data,” IEEE transaction on Multimedia, to appears.
[26]M.T. Chen and J. Seiferas, “Efficient and Elegant Subword-Tree Construction,” In A. Apostolico and Z. Galil. Editors, Combinatorial Algorithms on Words, Vol. 12 of NATO ASI Series F: Computer and System Sciences, Springer-Verlag, Berlin, Germany, Pages 97-107, 1984.
[27]E. McCreight, “A Space-Economical Suffix Tree Construction Algorithm,” Journal of Association for Computing Machinery, Pages 262-272, 1976.
[28]E. Ukkonen, “Approximate String-Matching over Suffix Trees,” Combinatorial Pattern Matching, Pages228-242, 1993.
[29]E. Ukkonen, “On-Line Construction of Suffix Tree,” Algorithmica, Vol. 14, Pages 249-260, 1995.
[30]P. Weiner,“Linear Pattern Matching Algorithms,” In Proc. Of IEEE Ann. Symp. On Switching and Automata Theory, Pages 1-11,1973.
[31]J. Foote, “An overview of audio information retrieval,” Multimedia Systems, vol. 7, no. 1, pp. 2-10, ACM Press & Springer-Verlag, 1999.
[32]S. Pfeiffer, S. Fischer, and W. Effelsberg, “Automatic audio content analysis,” InProc. of ACM Multimedia Conference, pp. 21-30, 1996.
[33]M. Hawley, “The Personal Orchestra,” Computing Systems, Vol. 3, No. 2, pp.289-329, 1990.
[34]V. Bakhmutova, V. D. Gusev, and T. N. Titkova, “The search for adaptations in song melodies,” Computer Music Journal, vol. 21, no. 1,page 58~67,Spring 1997.
[35]C. L. Krumhansl, “CognitiveFoundations of Musical Pitch,” Oxford University Press, New York, 1990.
[36]E. Narmour, “The Analysis and Cognition of Basic Melodic Structures,” The University of Chicago Press, Chicago, 1990.
[37]J. Sundberg, A. Friberg, and L. Fryden, “Common secrets of musicians and listeners: an analysis-by-synthesis study of musical performance,” In Representing Musical Structure, P. Howell, R. West, and I. Cross, eds., Academic press, London,1991.