摘要
　　音樂資料庫中的資料格式直接影響到資料庫的效能與搜尋速度。以往的研究中，通常使用音符為基本單位儲存在音樂資料庫中，但是音樂中最基本的單位卻不是音符而是音型。音型是由一組連續的音符所構成，並且能夠被人們感覺到它們的邊界。由於音型通常與人們所認知的音樂片段是相符合的，因此音型適合當做音樂資料庫中基本的單位。為了要從原始音樂中取出音型，音樂片段切割演算法是必要的，LBDM 是目前一種常見的音樂片段切割演算法，它可以用來切割原始音樂片段使成為數個連續的音型。除此之外，一般的經驗中，人們通常把一些重要連續的音型記憶在腦海裡。由於重複是音樂的重要特徵之一，同時，音樂中重要的片段往往會重複許多次，如歌曲中的副歌或者是音樂中的主題，往往會在一首曲子中重複多次。因此受限於人類記憶的限制，大家通常只會記憶這些重要的重複音型。為了要擷取音樂中重要的重複音型，我們可以應用一個重複片段找尋的演算法來找尋音樂的重要重複音型。另外由於音型通常與人類感知相符合，因此這些重複的音型也會與人類感知相符合，也就是說，人們在查詢所需要的音樂片段時，其輸入的音樂片段也會是數個音型，同時將會與資料庫中的音型相符合。但是目前重複片段找尋的演算法的速度均不理想，因此在這篇論文中，基於過去的重複片段演算法中我們提出了一個效能加強的重複片段找尋演算法，同時一個準確率加強的LBDM 演算法也在這篇論文中被討論。最後我們可以搭配使用這兩個演算法，找出與人們感知相符合的音樂重要重複音型，基於這樣的重要重複音型，往後的音樂資料庫研究中，效能與準確率將較容易被提升。

　　The unit of data stored in music database directly affects the data size and searching complexity of music database. Most of research in music database use note as basic unit of data stored in music database. But in musicology, the basic unit of music is not note but figure. Figure is a group of successive notes, and people usually can feel the boundary of a figure. Because figure is consistent with human perception, therefore, figure is suitable for being basic unit of music database. In order to extract figures of a music work, a music surface segmentation algorithm LBDM (Local Boundary Detection Model) is needed. Besides, there is a common observation that human usually keeps only some successive important figures of a music work in mind. And such important parts of music work can be extracted by applying a repeating pattern finding algorithm because important parts of a music work usually repeat frequently. Therefore, if figure is basic unit of music database, then it can easily find human perceptive repeating patterns in a song because figure is consistent with human perception.But, when applying repeating pattern finding algorithm on huge music database, the speed is critical because the time complexity of repeating pattern finding algorithm is very high and searching space of current music database is huge. In this thesis, a speed enhancement repeating pattern finding algorithm and an improved version of LBDM algorithm are developed. By combining these two algorithms, human perceptive repeating patterns can be found quickly and could help to increase the performance of music database for further research.

[1] T. C. Chou, A. L. Chen, and C. C. Liu, “Music Databases: Indexing Techniques and Implementation,”
Proc. of the IEEE International Workshop on Multimedia Data Base Management Systems,
pp. 46–53, Aug. 1996.
[2] A. L. Chen and J. C. Chen, “Query by Rhythm: An Approach for Song Retrieval in Music
Databases,” Proc. of IEEE International Workshop on Research Issues in Data Engineering,
pp. 139–146, Feb. 1998.
[3] J. L. Hsu, A. L. Chen, M. Chang, J. Chen, C.-H. Hsu, and S. Y. Hua, “Query by Music Segments:
An Efficient Approach for Song Retrieval,” Proc. of IEEE International Conference on Multimedia
and Expo (II), pp. 873–876, July 2000.
[4] A. L. Chen and W. Lee, “Efficient Multi-Feature Index Structures for Music Data Retrieval,” Proc.
of SPIE Conference on Storage and Retrieval for Image and Video Databases, pp. 177–188, 2000.
[5] K. Lemstrom, G. A. Wiggins, and D. Meredith, “A Three-Layer Approach for Music Retrieval
in Large Databases,” Proc. of the 2nd Annual International Symposium on Music Information
Retrieval, pp. 13–14, Oct. 2001.
[6] H. R. Turtle and W. Croft, “A Comparison of Text Retrieval Models,” The Computer Journal,
vol. 35, no. 3, pp. 279–290, June 1992.
[7] J. Foote, “Content-based Retrieval of Music and Audio,” Proc. of the Multimedia Storage and
Archiving Systems II, vol. 3229, pp. 138–147, 1997.
[8] J. Foote, “An Overview of Audio Information Retrieval,” Multimedia Systems, vol. 7, no. 1, pp. 2–10,
Jan. 1999.
[9] C. C. Liu and P. J. Tsai, “Content-based Retrieval of MP3 Music Objects,” Proc. of the International
Conference on Information and Knowledge Management, pp. 506 – 511, Nov. 2001.
[10] N. Kosugi, Y. Nishihara, T. Sakata, M. Yamamuro, and K. Kushima, “A Practical Query-By-
Humming System for a Large Music Database,” Proc. of the 8th ACM International Conference on
Multimedia, pp. 333–342, 2000.
[11] N. Kosugi, Y. Nishihara, S. Kon’ya, M. Yamamuro, and K. Kushima, “Let’s Search for Songs by
Humming! ,” Proc. of the 7th ACM International Conference on Multimedia (Part 2), p. 194, Oct.
1999.
[12] J. L. Ghias, D. Chamberlin, and B. C. Smith, “Query by Humming: Musical Information Retrieval
in an Audio Database,” Proc. of ACM Multimedia, pp. 231–236, Dec. 1995.
[13] J. L. Hsu, C. C. Liu, and A. L. Chen, “Discovering Nontrivial Repeating Patterns in Music Data,”
IEEE Transactions on Multimedia, vol. 3, no. 3, pp. 311–325, Nov. 2001.
[14] F. Lerdahl and R. Jackendoff, A Generative Theory of Tonal Music. The MIT Press, Cambridge,
1983.
[15] Y. Zhu and D. Shasha, “Warping Indexes with Envelope Transforms for Query by Humming,” Proc.
of the 2003 ACM SIGMOD International Conference on Management of Data, pp. 181–192, June
2003.
[16] L. Stein, Structure and Style: The Study and Analysis of Musical Forms. Warner Brothers /
Summy-Birchard Publications, Dec. 1979.
[17] N. P. Todd, “A Model of Expressive Timing in Tonal Music,” Music Perception, vol. 3, pp. 33–58,
Fall 1985.
[18] E. Cambouropoulos, “A Formal Theory for The Discovery of Local Boundaries in A Melodic Surface,”
Proc. of the III Journees d’ Informatique Musicale, 1996.
[19] E. Cambouropoulos, “The Local Boundary Detection Model (LBDM) and Its Application in The
Study of Expressive Timing,” Proc. of the International Computer Music Conference, pp. 17–22,
Sept. 2001.
[20] J. Tenney and L. Polansky, “Temporal Gestalt Perception in Music,” Journal of Music Theory,
vol. 24, no. 2, pp. 205–241, Fall 1980.
[21] D. Conklin and I. Witten, “Multiple Viewpoint Systems for Music Prediction,” Journal of New
Music Research, vol. 24, no. 1, pp. 51–73, Mar. 1995.
[22] D. Conklin, “Representation and Discovery of Vertical Patterns in Music,” Proc. of 2th International
Conference on Music and Artificial Intelligence, pp. 32–42, Sept. 2002.
[23] Y. Lo, H. Yu, and M. Fan, “FastPET: A Fast Non-trivial Repeating Pattern Extracting Technique
for Music Data,” Proc. of National Computer Symposium, pp. D043–D052, Dec. 2001.
[24] C. W. Chang and H. C. Jiau, “Using Quantized Melody Contour to Discover Significant Repeating
Figures in Classical Music,” Proc. of International Computer Symposium, pp. 1641–1648, Dec. 2002.
[25] C. W. Chang and H. C. Jiau, “Extracting Significant Repeating Figures in Music by Using Quantized
Melody Contour,” Proc. of International Computer Symposium, June 2003.
[26] P. White, Basic MIDI. Sanctuary Press, miniature ed., Feb. 2000.
[27] http://www.noteworthysoftware.com.