簡易檢索 / 詳目顯示

回結果列表
研究生： 張傳旺
Chang, Chuan-Wang
論文名稱： 以旋律相似性為基礎的音樂檢索系統索引技術之研究
A Study on Melodic Similarity-based Indexing Techniques for Music Retrieval System
指導教授： 焦惠津
Jiau, Hewijin Christine
學位類別： 博士
Doctor
系所名稱： 電機資訊學院 - 電機工程學系
Department of Electrical Engineering
論文出版年： 2010
畢業學年度： 98
語文別： 英文
論文頁數： 121
中文關鍵詞： 音樂檢索系統 、數值索引 、相似比對 、查詢擴展
外文關鍵詞： music retrieval system, numeric indexing, similarity matching, query expansion
相關次數： 點閱：150  下載：6 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 隨著音訊壓縮技術與網際網路的快速發展，音樂資料庫的數量愈來愈多，資料量也愈來愈大。傳統上使用曲名、歌詞、演唱者、作曲者等文字型態的資料庫管理方式已經不合時宜。隨著音樂檔案的大量增加，快速且有效的音樂檢索技術有其必要性。

    本論文探討了許多有關於以旋律相似性為基礎的音樂檢索系統相關問題，包含了特徵擷取、音樂分段、索引技術以及相似比對等。在特徵擷取方面，我們提出一個從音樂檔案中擷取出重複音形的方法，這些重複音形通常是音樂裡最重要的組成元素；也提出一個結合和弦行進規則的音樂和弦指定方法。這些從音樂檔案中擷取出的重複音形與和弦都可以進一步做為代表音樂檔案的索引值。

    在音樂分段方面，我們提出一個方法能從多軌音樂中擷取出有意義的音樂片段。這些音樂片段就像是有意義的樂句，亦可以進一步做為音樂的索引值。
    由於現有的音樂索引技術，例如n-gram和suffix tree，均會建立許多冗餘的索引值，既費時又浪費儲存空間。因此，在索引技術方面，我們提出一個有效且快速的數值索引方法，以樂句做為建立索引值的基本單位。如此，可大幅降低檢索處理的時間並減少建立索引所需的儲存空間。

    由於使用者對於音樂的記憶可能與存在資料庫裡的音樂不同。因此，相似比對技術是音樂檢索系統能否成功的重要因素之一。為了提高容錯性，本論文提出查詢擴展的相似比對方法能有效地解決因多音、少音、錯音等所造成的比對問題。

    With the development of the Internet and the standardization of audio compression technology, there has been great growth in the number and size of music databases. Conventional organization methods for music collections that use the title, lyrics, singer’s name, composer’s name, or any other text-based information are becoming inadequate. The increasing availability of digital music has created a need for effective music retrieval methods.

    In this dissertation, many issues in content-based music information retrieval (MIR) system are discussed, including feature extraction, music segmentation, index construction, and similarity matching. For feature extraction, a method for extracting repeating figures from music is proposed and a method for monophonic music chord arrangement is presented. The extracted repeating figures and chords can be applied to music indexing.

    For music segmentation, a heuristic method for extracting the representative fragments of a melody from polyphonic music is proposed.

    For index construction, since existing approaches, such as n-gram and suffix tree indexing methods, create indexes full of redundancies. A numeric index construction method for efficient content-based melody retrieval is proposed. Music phrases are adopted as the basic unit for processing, with each phrase having a unique numeric index. The proposed method significantly reduces the required processing time and storage for retrieving and indexing music.

    For similarity matching, a query expansion approach is proposed for solving the problems caused by the complex interaction of substitution, insertion, and deletion errors. The proposed approach is compared with state of the art techniques and its effectiveness in melody retrieval is demonstrated. Extensive experiments show the robustness of the proposed approach against various kinds of query error.

    Table of Contents Chinese Abstract i English Abstract iii Acknowledgment(誌謝) v Table of Contents vi List of Tables ix List of Figures x 1.　Introduction 1 1.1　Music Information Retrieval 1 1.2　Motivation 3 1.3　Contribution 3 1.3.1　Chord Arrangement Algorithm for Monophonic Music 4 1.3.2　Music Segmentation 4 1.3.3　MIR System Based-on n-Gram Scheme 5 1.3.4　Numeric-based Indexing and Access Mechanism for MIR 5 1.4　Organization of the Dissertation 6 2.　Review of Related Work 9 2.1　Feature Extraction for Music Retrieval 9 2.1.1　Melodic Pitch Contours 9 2.1.2　Repeating Pattern 11 2.1.3　Repeating Figures 16 2.2　Indexing Methods for Music Retrieval 19 2.2.1　Suffix tree-based indexing 20 2.2.2　N-gram indexing 22 2.2.3　Numeric Indexing 23 3.　A Practical Chord Arrangement Algorithm for Monophonic Music 26 3.1　Introduction 27 3.2　Terminology and Notation 29 3.3　Chord Arrangement Algorithm 31 3.3.1　Outline of Chord Arrangement System 31 3.3.2　Common Chord Templates 33 3.3.3　Local Recognition Phase 35 3.3.4　Global Arrangement Phase 37 3.4　Example 39 3.5　Conclusion 45 4.　 Representative Music Fragment Extraction 46 4.1　Introduction 46 4.2　Sentence-based Music Segmentation 49 4.2.1　LBDM Concatenation Strategy 50 4.2.2　Sentence-like Melody Extractor 53 4.3　Experimental Results and Observations 57 4.3.1　Experimental Results 57 4.3.2　Observation 58 4.4　Conclusion 61 5.　 Music Retrieval System Based on n-Gram Scheme 62 5.1　Introduction 62 5.2　Outline of Proposed Music Retrieval System 64 5.3　Proposed Method 66 5.3.1　Melodic Contour Transformation 66 5.3.2　Segmentation and Storage 68 5.4　Search 70 5.4.1　Exact Matching 71 5.4.2　Similarity Matching 71 5.4.3　Candidate Ranking 72 5.5　Performance Evaluation of the Proposed Melody Retrieval System 74 5.5.1　Segmented Pitch Score vs. Euclidean Distance 76 5.5.2　Effect of Segmentation Length 77 5.5.3　Contour-based Searching vs. Note-based Searching 77 5.5.4　Effect of Query Length 78 5.6　Conclusion 80 6.　A Numeric Indexing and Access Mechanism for Music Retrieval System 81 6.1　Introduction 82 6.2　Proposed Music Information Retrieval System 86 6.3　Terminology and Notation 89 6.4　Proposed Indexing Approach 91 6.4.1　Dual Ternary Indexing Techniques 91 6.4.2　Similarity Matching 96 6.4.2.1　Prefix/Suffix Query Expansion 96 6.4.2.2　Query Expansion with Insertion, Deletion, or Substitution Error 100 6.4.3　Candidate Ranking 102 6.5　Experiments and Results 103 6.5.1　Experimental Conditions 104 6.5.2　Evaluation Measurement 105 6.6　Conclusion and Future Work 110 7.　Conclusions 111 References 113 Vita 121

    [1] Ghias. A, H. Logan, D. Chamberlin, and B.C. Smith, “Query by Humming：Musical Information Retrieval in an Audio Databases,“ Proceedings of the 3rd ACM International Conference on Multimedia, pp. 231-236, 1995.
    [2] N. Kosugi, Y. Nishihara, S. Kon’ya, M. Yamanuro, and K. Kushima. “Music Retrieval by Humming”. Proceedings of the IEEE PACRIM’99, pp. 404-407, 1999.
    [3] N. Kosugi, Y. Nishihara, T. Sakata, M. Yamanuro, and K. Kushima. “A Practical Query-By-Humming System for a Large Music Database”. Proceedings of the ACM Multimedia, pp. 333-342, 2000.
    [4] S. Rho and E. Hwang, “FMF:Query adaptive melody retrieval system,” The Journal of Systems and Software, vol. 79, pp. 43-56, 2004.
    [5] L. Kennedy, S.F Chang, and A. Natsev, “Query-Adaptive Fusion for Multimodal Search,” Proceedings of the IEEE, vol. 96, no. 4, pp. 567-588, 2008.
    [6] K.S. Park, W.J. Yoon, K.K. Lee, S.H. Oh, and K.M. Kim, “MRTB Framework: A Robust Content-Based Music Retrieval and Browsing,” IEEE Transactions on Consumer Electronics, vol. 51, no. 1, pp. 117-122, 2005.
    [7] M. Melucci and N. Orio, “SMILE: a System for Content-based Musical Information Retrieval Environments,” Proceedings of ACM Digital Libraries Conference, vol. 2, pp. 1261-1276, 2000.
    [8] F.F. Kuo and M.K. Shan, ”Looking for New, Not Known Music Only: Music Retrieval by Melody Style,” Proceedings of the Joint ACM/IEEE Conference on Digital Libraries, pp. 243-251, 2004.
    [9] J. Shen, D. Tao, and X. Li, “QUC-Tree: Integrating Query Context Information for Efficient Music Retrieval,” IEEE Transactions on Multimedia, vol. 11, no. 2, pp. 313-323, 2009.
    [10] R.L. Kline and E.P. Glinert, “Approximation Matching Algorithms for Music Information Retrieval Using Vocal Input,” Proceedings of the ACM International Multimedia Conference, pp. 130-139, 2003.
    [11] D. Byrd and T. Crawford, “Problems of music information retrieval in the real world,” Information Processing and Management, vol. 38, pp. 249—272, 2002.
    [12] J. Shen, J. Shepherd, and A.H. Ngu, “Towards effective content-based music retrieval with multiple acoustic feature combination,” IEEE Transactions on Multimedia, vol. 8, no. 6, pp. 1179-1189, 2006.
    [13] C. Nopthaisong and M.M. Hasan, “Automatic Music Classification and Retrieval: Experiments with THAI Music Collection,” Proceedings of the IEEE International Conference on Information and Communication Technology, pp. 76-81, 2007.
    [14] C. Xu, C. Maddage, and S. Shao, “Automatic Music Classification and Summarization,” IEEE Transactions on Speech and Audio Processing, vol. 13, no. 3, pp.441-450, 2005.
    [15] M.A. Raju, B. Sundaram, and P. Rao, ”TANSEN: A Query-by-Humming based Music Retrieval System, “ Proceedings of the National Conference on Communications, 2003.
    [16] J.L. Hsu, C.C. Liu, and A.L.P. Chen, “Discovering Nontrivial Repeating Patterns in Music Data,“ IEEE Transactions on Multimedia, pp. 311-325, 2001.
    [17] S.C. Chiu, M.K. Shan, J.L. Huang and H.F. Li, “Mining polyphonic repeating patterns from music data using bit-string based approaches,” IEEE International Conference on Multimedia and Expo, pp. 1170 – 117, 2009.
    [18] Y.L. Lo and C.Y. Chen, “Fault Tolerant Non-trivial Repeating Pattern Discovering for Music Data,” Proceedings of the 1st IEEE/ACIS International Workshop on Component-Based Software Engineering, Software Architecture and Reuse, pp. 130 – 135, 2006.
    [19] C.W. Chang and H.C. Jiau, “Using Quantized Melody Contour to Discover Significant Repeating Figures in Classic Music,” Proceedings of the International Computer Symposium, pp. 1641-1648, 2002.
    [20] C.W. Chang and H.C. Jiau, “Extracting Significant Repeating Figures in Classic Music by Using Quantized Melody Contour,” Proceedings of IEEE International Symposium on Computers and Communications, pp. 1061-1066, 2003.
    [21] E.M. McCreight, “A space-economical suffix tree construction algorithm,” Journal of Algorithms, vol. 23, no. 2, pp. 262-272, 1976.
    [22] E. Ukkonen, “On-line construction of suffix trees,” Algorithmica, vol. 14, no. 3, pp. 249-260, 1995.
    [23] P. Weiner, “Linear pattern matching algorithm,” Proceedings of the 14th Annual IEEE Symposium on Switching and Automata Theory, pp. 1–11, 1973.
    [24] M.T. Chen and J. Seiferas, ”Efficient and elegant subword-tree construction,” Combinational Algorithms on Words, vol. 12, pp. 97-107, 1984.
    [25] D. Gusfield, “Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology,” Cambridge University Press, 1997.
    [26] S. Downie and M. Nelson, “Evaluation of a simple and effective music information retrieval method.” Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 73-80, 2000.
    [27] A. Uitenbogerd and J. Zobel, ”Melodic matching techniques for large music databases.” Proceedings of the 7th ACM International Multimedia Conference, pp. 57-66, 1999.
    [28] Y.H. Tseng, “Content-Based Retrieval for Music Collections,” Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval, 1999.
    [29] C. L. Yip and B. Kao, “A study on n-gram indexing of music features.” Proceedings of the IEEE International Conference on Multimedia and Expo, pp. 869-872, 2000.
    [30] C. W. Chang, C. Y. Chang, and H. C. Jiau, “A practical music retrieval system based on sliding melodic contour,” Proceedings of the International Computer Symposium, pp. 1162-1167, 2004.
    [31] C. W. Chang and H.C. Jiau, “Implementation and evaluation of a music retrieval system based on n-gram scheme,” International Journal of Control Theory and Applications. vol. 2, no. 2, pp. 97-108, 2010.
    [32] D. Bainbridge, M. Dewsnip, and I.H. Witten, “Searching digital music libraries,” Information Processing and Management, pp. 41-56, 2005.
    [33] T. Kumamoto, “A Query by Musical Impression System using N-gran based Features,” Proceedings of the IEEE Conference on Cybernetics and Intelligent Systems, pp. 993-998, 2004.
    [34] F. Lerdahl and R. Jackendoff, AGenerative Theory of Tonal Music, MIT Press, Cambridge, 1983.
    [35] J. Rahn, Basic Atonal Theory, New York, Longman, 1980.
    [36] W. Charles, Basic Forms in Music, Alfred Publishing, 1974.
    [37] E. Narmour, The Analysis and Cognition of Basic Melodic Structures, Chicago, IL: Univ. of Chicago Press, 1990.
    [38] Y.L. Lo and S.J. Chen, “The numeric indexing for music data,” Proceedings. 22nd International Conference on Distributed Computing Systems Workshops, pp. 258-263, 2002.
    [39] Y.L. Lo and S.J. Chen, “Multi-feature indexing for music data,” Proceedings. 23nd International Conference on Distributed Computing Systems Workshops, pp. 654-659, 2003.
    [40] T.C. Chou, Arbee L.P. Chen, and C.C. Liu,” Music Databases: Indexing Techniques and Implementation,“ Proceedings of International Workshop on Multimedia Database Management Systems, pp. 46-53, 1996.
    [41] M.K. Shan and F.F. Kuo, “Music Style Mining and Classification by Melody,” IEICE Transactions on Information and Systems, vol. E86-D(4), pp. 655-659, 2003.
    [42] B. Pardo, and W. Birmingham,” Automated Partitioning of Tonal Music,” Proceedings of the 13th International Florida Artificial Intelligence Research Society Conference, pp. 23-27, 2000.
    [43] B. Pardo, and W. Birmingham,” The Chordal Analysis of Tonal Music,” Technical Report (CSE-TR-439-01), 2001.
    [44] B. Pardo, and W. Birmingham,” Algorithms for Chordal Analysis,” Computer Music Journal, 2002.
    [45] A. Forte,“ The Structure of atonal Music,” Yale University Press, 1973.
    [46] A. Uitdenbogerd and J. Zobel, “Manipulation of Music for Melody Matching,” Proceedings of ACM International Multimedia Conference, pp. 235–240, 1998.
    [47] A. Uitdenbogerd and J. Zobel, “Melodic Matching Techniques for Large Music Databases,” Proceedings of ACM International Multimedia Conference, pp. 57–66, 1999.
    [48] A. Uitdenbogerd and J. Zobel, “Music Ranking Techniques Evaluated,” International Symposium on Music Information Retrieval, pp. 275-283, 2000.
    [49] H. C. Chen and A. L. Chen, “A Music Recommendation System Based on Music Data Grouping and User Interests,” Proceedings of the 10th International Conference on Information and Knowledge Management, pp. 231–238, 2001.
    [50] S.G. Blackburn, Content Based Retrieval and Navigation of Music Using Melodic Pitch Contours. A thesis submitted for the degree of Doctor of Philosophy, 2000.
    [51] S.G. Blackburn and D.D. Roure, “Musical Part Classification in Content Based Systems,” Proceedings of the 6th International Workshop and 2nd International Workshop on Open Hypertext Systems and Structural Computing, pp. 66–76, 2000.
    [52] M. Tang, C. L. Yip, and B. Kao, “Selection of Melody Lines for Music Databases,” Proceedings of the 24th Annual International Computer Software and Applications Conference, pp. 243–248, 2000.
    [53] Z. Q. Wu, A Guide to Musical Forms. Mercury Publishing House, 1996.
    [54] L. Stein, Structure and Style–The Study and Analysis of Musical Forms. Evanston, Ill., Summy-Birchard Company, 1962.
    [55] W.J. Ke, C.W. Chang and H.C. Jiau, “Representative Music Fragment Extraction by Using Segmentation Techniques,” Proceedings of the International Computer Symposium, pp. 1156-1161, 2004.
    [56] C.W. Chang, W.J. Ke and H.C. Jiau, “A Heuristic Approach for Music Segmentation,” Proceedings of the Second International Conference on Innovative Computing, Information and Control, 2007.
    [57] E. Cambouropoulos, “A Formal Theory for the Discovery of Local Boundaries in a Melodic Surface,” Proceedings of the III Journees d’ Informatique Musicale, 1996.
    [58] E. Cambouropoulos, “The Local Boundary Detection Model (LBDM) and its Application in the Study of Expressive Timing,” Proceedings of the International Computer Music Conference, pp. 17–22, 2001.
    [59] 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, 1996.
    [60] S. Pfeiffer, S. Fischer and W. Effelsberg, “Automatic Audio Content Analysis,” Proceedings of the Fourth ACM International Multimedia Conference, pp.21-30, 1996.
    [61] A L.P. Chen, M. Chang, J. Chen, J.L. Hsu, C.H. Hsu, and S.Y.S., Hua, “Query by Music Segments：An Efficient Approach for Song Retrieval‚ ” Proceedings of IEEE International Conference on Multimedia and Expro‚ pp. 873-876‚ 2000.
    [62] C.C. Liu, J.L. Hsu, and A.L.P. Chen, “An Approximate String Matching Algorithm for Content-Based Music Data Retrieval,“ Proceedings of IEEE International Conference on Multimedia Computing and Systems, pp.451-456, 1999.
    [63] W. Lee, and A.L.P. Chen, “Efficient Multi-Feature Index Structures for Music Data Retrieval," Proceedings of SPIE Conference on Storage and Retrieval for Image and Video Databases, pp.177-188, 2000.
    [64] J. Foote, “Content-based retrieval of music and audio,” Proceedings of SPIE Multimedia Storage and Archiving systems II, Vol.3229, pp. 138-147, 1997.
    [65] MIDI Manufactures Association (MMA), MIDI1.0 Specification‚ http://www.midi. org
    [66] Standard MIDI-File Format Spec.1.1, http://duskblue.org/proj/toymidi/midi format.pdf
    [67] CMIDI.com‚http://www.cmidi.com/.
    [68] MIDI Music Center‚ http://members.at.infoseek. co.jp/midicentre/index2.html.
    [69] D. Bainbridge, M. Dewsnip, and I. H. Witten, Searching digital music libraries, Information Processing and Management, pp.41-56, 2005.
    [70] D. Parsons, The directory of tunes and musical themes, Spencer Brown, 1991.
    [71] S. Rho, B. Han, E. Hwang, and M. Kim, MUSEMBLE: a novel music retrieval system with automatic voice query transcription and reformulation. The Journal of Systems and Software, vol.81, pp.1065-1080, 2008.
    [72] H. C. Jiau and C. W. Chang, A dual ternary indexing approach for music retrieval systems. Journal of Advanced Computational Intelligence and Intelligent Informatics, vol.12, no.3, pp.227-233, 2008.
    [73] C.W. Chang and H.C. Jiau, “An Efficient Numeric Indexing Technique for Music Retrieval,” Proceedings of the IEEE International Conference on Multimedia & Expo, pp.1981-1984, July 2006.
    [74] R. McNab, L.A. Smith, I.H. Witten and C.L. Henderson, Tune retrieval in the multimedia library. Multimedia Tools and Applications, vol.10, pp.113-112, 2000.
    [75] E. G. Gutierrez, Melodic Description of Audio Signals for Music Content Processing. A thesis submitted for the degree of Doctor of Philosophy, 2002.

    下載圖示 校內：2012-07-29公開
    校外：2014-07-29公開
    QR CODE