臺灣博碩士論文加值系統

近來在多媒體資料庫中如何有效率的管理音樂資料，已獲得了高度的注意。 現在大部分的研究工作，多利用音樂資料的特性萃取(feature extraction)，以加速音樂資料的搜尋。在以內容擷取(content-based retrieval)為主的音樂查詢程序上，無論以萃取音樂的何種特性做為其核心技術，其效能均與音樂的長度息息相關，因此音樂的長度若太長將嚴重影響查詢時間。 在檢視音樂旋律的組成上，我們可以發現有很多一序列的音符結合在一起，其在整首音樂中出現超過一次以上者，我們稱此為重覆片段(repeating pattern)。 而在一首音樂中會出現多次的片段，大部份均為主旋律也是人們記憶較熟悉的部分，且其長度較實際音樂短，因此可以利用此特徵來建構索引，以加快音樂資料搜尋的速度。
非不重要重覆片段(non-trivial repeating pattern)常用於分析音樂的重覆片段與尋找主旋律。在所有重覆片段中，扣除該片段已全包含於其他更長片段中的項目，即非不重要重覆片段。如此能減少重覆片段的個數，並大幅提昇音樂搜尋的效率。到目前為止，找尋音樂旋律中重覆片段之研究，全都著重於片段之完全重覆出現，不允許部份的差異，亦即只差一個音的兩個片段也不能視為相同，如此在實際運用上就受到了限制。 如果在一定差異範圍內的片段也能視為同一重覆片段，則此找尋近似重覆片段之技術，不只在音樂資料庫，在基因資料庫或其他相關領域，都可能有其運用的價值。 因此在本研究中，發展出找尋音樂旋律中近似重覆片段的演算法。 期望近似重覆片段的搜尋技術，也能擴展應用於找尋DNA與蛋白質中的重覆序列。

Recently, how to efficiently manage music data in multimedia databases is getting more attentions. The most of research works used feature extractions for music objects, to create indices for speeding up searching in music data. The performance of content-based retrieval on the features of melodies, chords or rhythms is mainly related with the length of music data. The length of music is significantly influence the query time. A repeating pattern is a sequence of notes appearing more than once in a music object. Most of the repeating patterns, which are always shorter than their original object, are key melodies or easy to familiarize and remember for people. Therefore, to represent an original music by the repeating patterns, the content-based retrieval for music searching will promote the query performance.
　　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 they can reduce the redundancy of the repeating patterns and speedup music search. So far the proposed approaches discover the exact repeating pattern in which the repeated parts of music object have exact same sequence of notes and length. These approaches, with searching for exact repeating patterns, limit their capabilities for most of applications. If similar repeating pattern with partial different notes in the sequences is allowed, such discovering approach should be very helpful not only in music databases but also in genome databases et al. In this research, we make efforts on how to discover the similar repeating patterns for music data. We expect that our approaches can be used to discover not only repeating patterns on music objects but also repeating sequences on the DNA and protein.

第一章 緒論 1
1.1 背景與現況 1
1.2 重覆片段在音樂資料中扮演的角色 4
第二章 文獻探討 7
2.1 相關矩陣(CORRELATIVE MATRIX) 7
2.2 RP-TREE 10
2.3 快速片段萃取技術(FASTPET) 14
2.4 二列比較法(TWO-ROW COMPARISON, 2RC) 15
2.5 平行非不重要重覆片段找尋技術(PARALLEL NON-TRIVIAL REPEATING PATTERN DISCOVERING TECHNIQUE) 17
第三章 近似非不重要重覆片段找尋技術(SIMILAR NON-TRIVIAL REPEATING PATTERN DISCOVERING TECHNIQUE ) 20
3.1 演算法說明 23
3.2 範例說明 28
第四章 評估分析 35
第五章 結論與未來研究工作 40
參考文獻 42

[1]羅有隆、游合成(2002)，「以線性記憶體空間發現音樂資料中非不重要重覆片段之技術」，2002年第六屆資訊管理學術暨警政資訊實務研討會，中央警察大學，桃園，第341-350頁。
[2]V. Bakhmutova, V. D. Gusev, and T. N. Titkova (1997), “The search for adaptations in song melodies,” Computer Music Journal, vol. 21, no. 1, pp. 58~67.
[3]S. Blackburn and D. DeRoure (1998), “A Tool for Content-based Navigation of Music,” In Proc. of ACM Multimedia, pp. 361-368.
[4]James C.C. Chen and Arbee L.P. Chen (1998), “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.
[5]M.T. Chen and J. Seiferas, “Efficient and Elegant Subword-Tree Construction (1984),” 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, pp. 97-107.
[6]Arbee L.P. Chen, M. Chang, J. Chen, J.L. Hsu, C.H. Hsu, and Spot Y.S. Hua (2000), “Query by Music Segments: An Efficient Approach for Song Retrieval,” In Proc. ofIEEE Int''l Conf. on Multimedia and Expro.
[7]T.C. Chou, Arbee L.P. Chen, and C.C. Liu (1996), “Music Databases: Indexing Techniques and Implementation,” In Proc. of IEEE Int''l Workshop on Multimedia Data Base Management Systems.
[8]G. Davenport, T.A. Smith, and N. Pincever (1991), “Cinematic Primitives for Multimedia,” IEEE Computer Graphics & Applications, July, pp. 67-74.
[9]Y.F. Day, S. Pagtas, M. Iino, A. Khokhar, and A. Ghafoor (1995), “Object-Oriented Conceptual Modeling of Video Data,” In Proc. Of IEEE Data Engineering, pp. 401-408.
[10]E.A. El-Kwae and M.R. Kabuka (2000), “Efficient Content-Based Indexing of Large Image Databases,” ACM Trans. On Information Systems, Vol. 18, No. 2, April, pp. 171-210.
[11]J. Foote (1999), “An overview of audio information retrieval,” Multimedia Systems, vol. 7, no. 1, ACM Press & Springer-Verlag, pp. 2-10.
[12]A. Ghias, J. Logan, D. Chamberlin, and B.C. Smith (1995), “Query by Humming: Musical Information Retrieval in an Audio Database,” In Proc. of ACM Multimedia, pp. 231-236.
[13]S.T. Goh and K.L. Tan (2000), “MOSAIC: A Fast Multi-Feature Image Retrieval System,” Data & Knowledge Engineering, Vol. 33, pp. 219-239.
[14]M. Hawley (1990), “The Personal Orchestra,” Computing Systems, Vol. 3, No. 2, pp. 289-329.
[15]R. Hjelsvold, and R. Midtsraum (1994), “Modeling and Querying Video Data,” In Proc. of Int''l Conf. on VLDB, pp. 686-694.
[16]J.L. Hsu, C.C. Liu, and Arbee L.P.Chen (1998), “Efficient Repeating Pattern Finding in Music Databases, “ In Proc. of ACMInt''l Conf. on Information and Knowledge Management.
[17]J.L. Hsu, C.C. Liu, and Arbee L.P.Chen (2001), “Discovering Non-Trivial Repeating Patterns in Music Data,” IEEE transaction on Multimedia, Vol. 3, No. 3, September, pp. 311-325.
[18]K.A. Hua, K. Vu, and J.H. Oh (1999), “SamMatch: A Flexible and Efficient Sampling-Based Image Retrieval Technique for Large Image Databases,” In Proc. ofACM Multimedia, pp. 225-234.
[19]C. L. Krumhansl (1990), CognitiveFoundations of Musical Pitch, Oxford University Press, New York.
[20]W. Lee and A.L.P. Chen (2000), “Efficient Mult-Feature Index Structures for Music Data Retrieval,” In Proc. of SPIE Conference onStorageand Retrieval for Imageand Video Databases.
[21]C.C. Liu, J.L. Hsu, and Arbee L.P.Chen (1999), “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.
[22]C.C. Liu and ArbeeL.P. Chen (2002), “3D-List: A Data Structure for Efficent Video Query Processing,” IEEE TKDE, Vol. 14, No. 1, January/February, pp. 106-122.
[23]C.C. Liu, J.L. Hsu, and Arbee L.P.Chen (1999), “Efficient Theme and Non-Trivial Repeating Pattern Discovering in Music Databases,” In Proc. of IEEE Data Engineering, pp. 14-21.
[24]Yu-lung Lo, Ho-cheng Yu, and Mei-chin Fan (2001), "FastPET: A Fast Non-trivial Repeating Pattern Extracting Technique for Music Data," 2001 National Computer Symposium, Taipei, Dec. 20-21 pp. D043-052.
[25]Yu-lung Lo and Chun-yu Chen (2003), "Parallel Scheme for Non-trivial Repeating Pattern Discovering in Music Data," 2003 Symposium on Application and Development of Information Technologies , 國立屏東商業技術學院, June, pp. 657-666.
[26]E. McCreight (1976), “A Space-Economical Suffix Tree Construction Algorithm,” Journal of Association for Computing Machinery, pp. 262-272.
[27]E. Narmour (1990), The Analysis and Cognition of Basic Melodic Structures, The University of Chicago Press, Chicago.
[28]S. Nepal and M.V. Ramakrishna (1999), “Query Processing Issue in Image (Multimedia) Databases,” In Proc. of Int''l Conf. on Data Engineering, pp. 22-29.
[29]J.H. Oh and K.A. Hua (2000), “Efficient and Cost-Effective Techniques for Browsing and Indexing Large Video Databases,” In Proc. of ACM SIGMOD, pp. 415-426.
[30]E. Oomoto and K. Tanaka (1993), “OVID: Design and Implementation of a video-Object Database System,” IEEE Trans. on Knowledge and Data Engineering, August, pp. 629-643.
[31]S. Pfeiffer, S. Fischer, and W. Effelsberg (1996), “Automatic audio content analysis,” InProc. of ACM Multimedia Conference, pp. 21-30.
[32]S. W. Smoliar and H.J. Zhang (1994), “Content-Based Video Indexing and Retrieval,” IEEE Multimedia Magazine, pp. 62-72.
[33]J. Sundberg, A. Friberg, and L. Fryden (1991), “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.
[34]Y.H. Tseng (1999), “Content-Based Retrieval for Music Collections,” In Proc. of ACM SIGIR''99, Berkley, CA, USA, pp. 176-182.
[35]A.L. Uitdenbogerd and J. Zobel (1999), “Melodic Matching Techniques for Large Music Databases,” In Proc. of ACM Multimedia, pp.57-66.
[36]E. Ukkonen (1995), “On-Line Construction of Suffix Tree,” Algorithmica, Vol. 14, pp. 249-260.
[37]P. Weiner (1973),“Linear Pattern Matching Algorithms,” In Proc. Of IEEE Ann. Symp. On Switching and Automata Theory, pp. 1-11.
[38]E. Wold, T. Blum, D. Keislar, and J. Wheaton (1996), “Content-based classification, search, and retrieval of audio,” IEEE Multimedia, vol. 3, No. 3, Fall, pp. 27-36.