(44.192.112.123) 您好!臺灣時間:2021/03/01 04:02
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳韋如
研究生(外文):Chen, Wei-Ju
論文名稱:利用後綴樹對唱歌、哼歌搜尋問題的加速
論文名稱(外文):Speed Up Query by Singing/Humming with Suffix Tree
指導教授:韓永楷
指導教授(外文):Hon, Wing-Kai
口試委員:盧錦隆李哲榮
口試委員(外文):Lu, Chin-LungLee, Che-Rung
口試日期:2017-07-17
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2017
畢業學年度:105
語文別:英文
論文頁數:25
中文關鍵詞:後綴樹哼唱選歌
外文關鍵詞:Suffix TreeQuery by Singing/Humming
相關次數:
  • 被引用被引用:0
  • 點閱點閱:60
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
很多時候,走在路上,突然聽到一段熟悉的音樂,但是怎麼想也想不起來這首歌到底叫什麼名字、到底是誰唱的;又或是聽到了一首好聽的歌,因為從未聽過,也不知道要從何處找起這首歌的資訊,這時候我們可依賴旋律辨識系統來幫助使用者找出歌曲資訊。
一個旋律辨識系統有三個要素:要查詢的歌曲 (input query)、歌曲資料庫(song database)、以及有效率的比對方式 (method for comparison)。對使用者而言,Query by Singing/Humming (QBSH) 可謂最方便的查詢方式,使用者只需對著麥克風哼唱未知歌曲的旋律,而系統會自動把輸入與資料庫比對,再從中找出最佳答案。
在過去,張智星教授 (國立臺灣大學及前國立清華大學) 及其團隊對此問題的研究有良好的解決方式,其方法為將查詢歌曲的旋律轉成pitch vector、將資料庫中的每首歌曲轉成note vector,再利用線性伸縮 (linear scaling) 將查詢歌曲和資料庫中的每一首歌去做比較,算出最接近的旋律,用此方法可以迅速的得到答案,並擁有不錯的辨識率。
本論文的目標是在此基礎上再加以加速。我們加入後綴樹 (suffix tree) 的概念,希望以此對資料庫的歌曲進行篩選,而線性伸縮則只對被挑選出來的歌曲進行,進而達到加速的概念。實驗結果顯示我們的系統除了能有預期的加速效果外,更意外地能使辨識率有些微的提高。
Sometimes, we may hear a familiar song on the street but we do not know what the name it is or who the singer is. Or, we may hear a good melody, but we do not know how to find further information of the song since we have never heard this song before. In these situations, one may use a melody recognition system to help.
A melody recognition system has three main components: (1) an input query, (2) a database of songs, and (3) method for comparison. Perhaps the most user-friendly form of input query is by singing and humming (QBSH), where a user sings or hums a melody with a microphone, and then the input data is transformed to a suitable format for comparison with the database to be performed. In the past, Jyh-Shing Jang (formerly with National Tsing Hua University, and now with National Taiwan University) and his team have designed a system that has high recognition rate to solving this problem. The idea is to change the input to a pitch vector, change the database to a note vector, and use linear scaling method to compare the input with every song in the database. After that, the most song with the highest score is reported to the user. Their system performs with good efficiency and achieves high recognition rate.
In this thesis, we attempt to further improve the above performance. Instead of comparing all songs in the database with the input query using linear scaling, we use suffix tree of the songs in the database as a filter to obtain a few candidate songs that are most likely to be a match with the input query. After that, only these candidate songs will be matched, carefully, with the linear scaling method. Experimental results show that this new approach not only speeds up the overall algorithm, but, to our surprise, also improves slightly the recognition rate.
Abstract ……………………………………………………………………………..2
Table of Contents ……………………………………………………………………..4
Figure List …………………………………………………………………………..5
Table List ……………………………………………………………………………6
Chapter 1 Introduction ……………………………………………………………...7
Chapter 2 Related Work ……………………………………………………………..10
2.1 Ghias et al.’s Approach ………………………………………………….10
2.2 Knopke and Jürgensen’s Work ……………………………………..11
2.3 Jang’s Approach …………………………………………………….12
Chapter 3 Methods ……………..……………………………………………………14
3.1 Ghias et al.’s Melody Representation ......………………………………...15
3.2 Suffix Tree and Generalized Suffix Tree ………………………………...15
3.3 Our Proposed Method ….……………………………………………….17
Chapter 4 Experimental Results …………………………………….. ……………..19
4.1 Execution Time …………………………………………………………..19
4.2 Recognition Rate …………………………………………………………19
Chapter 5 Conclusion and Future Work ……………………………………………24
References …………………………………………………………………………25
[1] A. Ghias, J. Logan, D. Chamberlin, and B.C. Smith. “Query by Humming –– Musical Information Retrieval in an Audio Database,” in Proceedings of ACM Multimedia, 1995.
[2] R.J. McNab, L. A. Smith, I. H. Witten, C. L. Henderson, and S. J. Cunningham. “Toward the Digital Music Library: Tune Retrieval from Acoustic Input,” in Proceedings of ACM Digital Libraries, pp. 11–18, 1996.
[3] J.S.R. Jang and M.Y. Gao. “A Query-by-Singing System based on Dynamic Programming,” in Proceedings of International Workshop on Intelligent System Resolutions, pp. 85–89, 2000.
[4] J.S.R. Jang, H.R. Lee, and M.Y. Kao. “Content-based Music Retrieval Using Linear Scaling and Branch-and-Bound Tree Search,” in Proceedings of IEEE International Conference on Multimedia and Expo, 2001.
[5] R.A. Baeza-Yates and C.H. Perleberg. “Fast and Practical Approximate String Matching,” in Proceedings of Combinatorial Pattern Matching, pp. 185–192, 1992.
[6] I. Knopke and F. Jürgensen. “A System for Identifying Common Melodic Phrases in the Masses of Palestrina,” Journal of New Music Research, vol. 38, pp. 171-181, 2009.
[7] I. Knopke. “The Perlhumdrum and Perllilypond Toolkits for Symbolic Music Information Retrieval,” in Proceedings of International Symposium on Music Information Retrieval, pp. 147–152, 2008.
[8] Online link at http://mirlab.org/jang/books/audioSignalProcessing/
[9] E. Ukkonen. “On-Line Construction of Suffix Trees,” Algorithmica, vol. 14, no. 3, pp. 249–260, 1995.
[10] E.M. McCreight. “A Space-Economical Suffix Tree Construction Algorithm,” Journal of the ACM, vol. 23, no. 2, pp.262–272, 1976.
[11] M. Nelson. “Fast String Searching with Suffix Trees”, 1996. Online link at http://marknelson.us/1996/08/01/suffix-trees/
[12] D. Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
無相關期刊
 
無相關點閱論文
 
系統版面圖檔 系統版面圖檔