(3.227.0.150) 您好!臺灣時間:2021/05/06 12:49
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:許瑋玲
研究生(外文):Wel-Ling Hsu)
論文名稱:以PAT-Tree為基礎的近似搜尋於哼唱式音樂檢索
論文名稱(外文):PAT-Tree Based Approximate Search for Query by Humming in Music Retrieval
指導教授:楊燕珠楊燕珠引用關係
指導教授(外文):Yen-Ju Yang
學位類別:碩士
校院名稱:大同大學
系所名稱:資訊經營學系(所)
學門:商業及管理學門
學類:一般商業學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:中文
論文頁數:80
中文關鍵詞:容錯派樹音樂檢索哼唱式查詢近似搜尋
外文關鍵詞:PAT-TreeMusic RetrievalQuery by HummingFault ToleranceApproximate Search
相關次數:
  • 被引用被引用:0
  • 點閱點閱:370
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:51
  • 收藏至我的研究室書目清單書目收藏:2
哼唱式音樂檢索是讓使用者在不熟悉歌詞也能自由哼唱歌曲片段旋律當作查詢樂句,從音樂資料庫中檢索出最類似的歌曲。由於使用者並非受過訓練的專業歌手,亦非在專業錄音室專心演唱,再加上並非對旋律百分之百熟悉,故可能使哼唱出的查詢樂句包含多音、少音、或走音等不正確的輸入,進而增加了檢索的困難。
PAT-Tree是一種應用於文件資訊檢索的索引結構(index),其特徵是將文句字串轉換為位元串,將所有半無限字串(semi-infinite string, sistring)對應的位元串建構在樹狀結構中,能夠有效率對全文檢索內容作變更及取用,不依賴詞庫或文法就能擷取中文詞。
本論文所使用的音樂資料庫與查詢樂句,利用劉爵志[A5]提供的音符特徵擷取,先將每個樂句的旋律轉換為音符串,然後以音符串進行檢索。研究中應用PAT-Tree建構音符串的索引結構,並提出近似搜尋及相似度計算,以解決哼唱樂句有錯誤時,也能檢索出近似的歌曲。經由實驗結果顯示,當查詢樂句的錯誤率在40%以下,前5名檢索正確率都可達90%以上,可見我們所提出的方法具備高度的容錯能力。
Query by humming in music retrieval lets user who is unfamiliar with lyric can be free to hum melody as query phrases and retrieves the most similar songs. Because general users are not well-trained professional singers and may not completely keep melody in mind, user could hum query phrases involved in deletion, insertion or transposition errors that increase the difficulties in retrieval.
PAT-Tree is a kind of index structure applied in text retrieval. It converts a sentence of string into a binary string, and then insert all semi-infinite strings in tree. The full text can be efficiently updated and extractd from PAT-Tree. Chien in 1997 [B2] raises the significance of keyword extraction using PAT-Tree based approach, which is efficient in automatic keyword extraction from a set of relevant Chinese documents.
The music database and query phrases used in this research have been preprocessed by tool[A5] provided feature extraction. The phrases are converted to musical note string, on which the retrieval is performed. This research applies PAT-Tree to constructing indexes of musical note string and presents an approximate search with similarity measurement to solve the query errors by humming. The experimental results show that when the error rate of queries less than 40%, the top 5 retrieval accuracy can achieve higher than 90%. It is thus clear that the presented approach has high fault-tolerance.
目錄

致謝 i
摘要 ii
Abstract iii
目錄 iv
圖目錄 vi
表目錄 vii
第1章 緒論 1
1.1研究背景與動機 1
1.2研究目的 2
1.3目前研究 2
1.4 研究限制 4
1.5章節結構 4
第2章 文獻探討 5
2.1 MP3(MPEG Audio Layer-3)簡介 5
2.2 擷取MP3的特徵值(MP3 features) 6
2.3哼唱式查詢的問題 10
2.4建立音樂索引或比對的相關文獻 11
2.5 音樂比對的方法 12
2.6 Suffix Tree 21
2.7 PAT-Tree(Patricia tree) 24
2.8 Suffix tree(字尾樹)與PAT-tree的差異 28
第3章 研究方法 30
3.1研究流程 30
3.1.2 音樂檢索流程 31
3.2 使用PAT-tree的建構方法 33
3.2.1 用PAT-tree建構音樂索引的原因 33
3.2.2 以PAT-tree建構索引 33
3.2.3 PAT-tree的建構流程 35
3.3音樂查詢演算法 35
3.3.1 基本錯誤 38
3.3.2 综合錯誤 40
3.4相似度計算 40
第4章 實驗 44
4.1 歌曲人工分段成樂句的情形(一共20首歌) 45
4.2 PAT-Tree分析 46
4.2.1 子樂句的重複情形(有多少不重複的pattern) 46
4.2.2樂句分成子字串的情形(一共20首歌) 47
4.2.3子樂句轉換成binary的情形(一共20首歌) 48
4.3正確樂句的查詢結果 49
4.4樂句容錯查詢比較 50
4.4.1實驗結果 50
4.4.2實驗結果評估與分析 55
4.5 哼唱查詢 59
第5章 結論與未來研究 60
第6章 參考文獻 62
6.1 中文文獻 62
6.2英文文獻 63
附 錄 MIDI音名編號的頻率變換 70
1. 中文文獻

[A1] [鄭2007年] 鄭雯妮,2007年9月5日,以統計方法與音樂理論為基礎之和絃辨識系統,國立清華大學資訊工程學系碩士論文。
[A2] [黃、劉2002年] 黃群菘、劉志俊,2002年,MP3數位音樂資料的自動化分類,中華大學資訊工程學系,國科會補助之研究成果,計劃編號NSC 90-2213-E-216-010
[A3] [許2000年]許文豪、高名揚、張智星,2000年11月,直覺式歌唱輸入音樂搜尋引擎,第五屆人工智慧與應用研討會,台灣科技大學,pp. 734-740。
[A4] [高2001年]高名揚、張智星,2001,以聲音內容為主的音樂資料庫檢索系統的加速方法,國立清華大學資訊工程學系碩士論文。
[A5] [劉2003年] 劉爵至,2003年7月,哼唱式查詢—以內容為基礎的MP3資訊檢索,大同大學資訊經營研究所碩士論文。
[A6] [劉2007年] 劉瓊雙,2007年3月1日,適合於允許容錯查詢的音樂資料索引方法,朝陽科技大學資訊管理系碩士論文。
[A7] [林2003年]林朝興、王怡君,2003年10月,高效能分段擷取MP3樂曲高頻重覆樣型,2003年民生電子研討會,國立成功大學電機系。
[A8] [林2004年]林朝興、王怡君,2004年4月,支援MP3斷句快速內容查詢之索引結構,第十五屆國際資訊管理學術研討會,中原大學資訊管理學系。
[A9] [林2007年]林朝興、王怡君,2005年12月,建立分段MP3歌曲重複樣型之分類索引結構,資訊、科技與社會。
[A10][林2000年]林豐茂,2000年,生物體之重複序列找尋之演算法設計與實作,國立中央大學資訊工程研究所碩士論文。
[A11][曾2000年]曾元顯 ,2000年6月,音樂內容查詢不匹配問題與檢索模式之研究,資訊傳播與圖書館學,第6卷,第4期,pp. 35-48。
[A12][吳、顏2007年] 吳炳飛、顏志旭、魏宏宇等人編著,2007年6月,AUDIO CODING MP3篇技術手冊(第二版),全華圖書股份有限公司。

[A13][游、劉2001年] 游弘明、劉志峻,2001年,以哼唱方式查詢mp3音樂資料庫,中華大學資訊工程系,國科會計畫編號NCS-90-2213-E-216-010.

2. 英文文獻

[B1] [A., Logan , Chambirlin et al. 1995] A. Ghias , Logan H., Chambirlin Dr and Smith B. C.,1995, “Query by Humming: Musical Information Retrieval in an Audio Database,” in Proceedings of Third ACM International Conference on Multimedia, pages 231-236.
[B2] [Chien 1997] Chien Lee-Feng (簡立峰), 1997, “PAT-Tree-Based Keyword Extraction for Chinese Information Retrieval”,ACM,0-89791-836-3/97/7.
[B3] [Chen, Chang, Chen et al. 2000] Chen Arbee L. P., Chang M., Chen J., Hsu J. L., Hsu C. H., and Hua Spot Y. S. ,2000, “Query by Music Segments: An Efficient Approach for Song Retrieval” , In Proceedings of the IEEE International Conference on Multimedia and Expro, pp. 873-876.
[B4] [Chen, Chen 2001] Chen Hung-Chen, Chen Arbee L. P. , 2001 Nov., “A Music Recommendation System Based on Music Data Grouping and User Interests” , In Proc. of ACM International Conference on Information and Knowledge Management CIKM’01, pp. 231-238.
[B5] [Chou, Chen, Liu 1995] T. C. C. Chou, A. L. P. Chen, and C. C. Liu, “Music databases: indexing echniques and implementation” ,MS Thesis, National Tsing Hua University, Taiwan, R.O.C., 1995.
[B6] [Dan. 1997] Dan. Gusfield, 1997,“Algorithms on Strings, Trees, and Sequences: computer science and compu-tational biology,.” Cambridge University Press, New York.
[B7] [D. 1968] D. Morrison, 1968, “PATRICIA:Practical Algorithm to Retrieve Information Coded in Alphanumeric”,JACM,pp.514-534.
[B8] [Dan 1997] Dan Gusfield, 1997, “Algorithms on strings,trees, and sequences : computer science and compu-tational biology”,Cambridge [England] New York Cambridge University.
[B9] [E., T., E. et al. 1996] E. Wold, T. Blum, E. Keislar and J. Wheaton, 1996 Fall, “Content-Based Classification, Search, and Retrieval of Audio”, IEEE Multimedia, Vol. 3, No. 3, pp. 27-36.
[B10][G., G., P. 2001] G. Tzanetakis, G. Essl, and P. Cook, 2001, “Automatic Musical Genre Classification of Audio Signals," in Proc. Int. Symposium on Music Information Retrieval (ISMIR), Bloomington, Indiana.
[B11][G. and P. 1999] G. Tzanetakis and P. Cook, 1999 , “A Framework for Audio Analysis Based on Classification and Temporal Segmentation” ,in Proc. EUROMICRO Conf., Vol. 2, p.2061
[B12][Hsu, Liu, Chen 1998] Hsu J. L., Liu C. C., and Chen Arbee L. P., 1998, “Efficient Repeating Pattern Finding in Music Databases,” Proceedings of the ACM International Conference on Information and Knowledge Management, pp. 281-288.
[B13][Hsu, Liu, Chen 2001] Hsu J. L., Liu C. C.and Chen Arbee L. P., 2001, “Discovering Non-Trivial Repeating Patterns in Music Data”, IEEE Transaction on Multimedia, Vol. 3, No. 3, pp. 311-325.
[B14][Horowitz, Sahni, Anderson-Freed 1993] Horowitz Ellis, Sahni Sartaj, Anderson-Freed Susan,1993, “Fundamentals of Data Structures in C”,Computer Science Press ,ISBN: 0-7167-8250-2.
[B15][Jang, Gao 2000] Jang J.-S. Roger, Gao Ming-Yang, 2000 Dec., “A Query-by-Singing System based on Dynamic Programming", International Workshop on Intelligent Systems Resolutions (the 8th Bellman Continuum) ”,Hsinchu, Taiwan, pp. 85-89.
[B16][K. Brandenburg, G. Stoll 1994] K. Brandenburg and G. Stoll, Oct 1994,“ISO-MPEG-1 Audio: A Genereic Standard for Coding of High Quality Digital Audio,” Journal of the Audio Engineering Society, Vol. 42, No. 10, pp. 780-792.
[B17][Tseng 1999] Tseng, Y.H., 1999, “Content-Based Retrieval for Music Collections,” In Proc. Of ACM SIGIR’99, Pages 176-182.
[B18][Liu, Hsu, Chen 1999] Liu C. C., Hsu J. L., and Chen Arbee L. P., 1999, “Efficient Theme and Non-Trivial Repeating Pattern Discovering in Music Databases,” Proceedings of the IEEE Data Engineering, pp. 14-21.
[B19][Liu, Huang 2002] Liu Chih-Chin, Huang Chuan-Sung, 2002, “A Singer Identification Technique for Content- Based Classification of MP3 Music Objects,” International Conference on Information and Knowledge Management (CIKM 2002), USA, pp. 438-445.
[B20][Lo and Chen 2002] Lo Y. L. and Chen S. J., 2002, "Numeric Indexing Approach for Music Database Retrieval," Journal of Chaoyang University of Technology, Vol. 2, pp. 141-163.
[B21][Lo and Chen 2003] Lo Y. L. and Chen S. J., 2003, “Multi-feature Indexing For Music Data,” Proceedings of the IEEE 23nd International Conference on Distributed Computing Systems (ICDCS'2003) Workshops -- the 5th International Workshop on Multimedia Network Systems and Applications (MNSA'2003), pp.654-659.
[B22][Lee and Chen 2000] Lee W. and Chen A. L. P. ,2000, "Efficient Multi-Feature Index Structures for Music Data Retrieval," Proceedings of the SPIE Conference on Storage and Retrieval for Image and Video Databases.
[B23][Lee 2005] Lee Wen-Ling, 2005,True Suffix Tree Approach for Discovering Non-trivial Repeating Patterns in a Music Object, Chaoyang University of Technology Information Management discourse.
[B24][Liu, Hsu, Chen 1999] Liu C.C., Hsu J.L. and Chen Arbee L.P., 1999, “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.
[B25][Liu, Chiang, Tsai] Liu Chueh-Chih, Chiang Te-Wei and Tsai Tienwei, 2007,“Using an N-gram-Based Mapping Approach to Content-Based Music Information Retrieval”, Journal of Science and Engineering Technology, Vol. 3, No. 1, pp. 49-58.
[B26][S., DeRoure 1998] S. Blackbum and DeRoure D., 1998, “A Tool for Content-Based Navigation of Music”, in Proceedings of the 6th ACM International Multimedia Conference, pages 361-368.
[B27] [Kwok, Lyu, King 2000] Kwok Kenny, Lyu Michael R., King Irwin, 2000, “A Novel PAT-Tree Approach to Chinese Document Clustering”, Department of Computer Science and Engineering, The Chinese University of Hong Kong.
[B28][K., R. 1998] K. Melih, R.Gonzalez, 1998, “Audio Retrieval Using Perceptually Based Structures”,In Proc. Of IEEE International Conference on Multimedia Computing and System, Austin, Texas, USA, pp.338-347.
[B29][N., Y., S. et al. 1999] N.Kosugi, Y. Nishihara, S. Kon'ya , M. Yamamuro and K. Kushima, 1999, “Music Retrieval by Humming”, In Proceedings of IEEE PACRIM'99, pp. 404-407.
[B30][N., Y., T. et al. 2000] N. Kosugi, Y. Nishihara, T. Sakata, M. Yamamuro and K. Kushima, 2000 October, “A practical query-by-humming system for a large music database”, In Proc. ACM Int. Conf. on Multimedia,Los Angeles, CA, pp. 333-342.
[B31][Pfeiffer, Fischer, Effelsberg 1996] Pfeiffer S., Fischer S., Effelsberg W., 1996, “Automatic audio content analysis,” In Proc. of ACM Multimedia Conference, pp. 21-30.
[B32][Uitdenbogerd and Zobel 1999] Uitdenbogerd A.L. and Zobel J., 1999, “Melodic Matching Techniques for Large Music Databases,” In Proc. of ACM Multimedia, Pages 57-66.
[B33][Weiner 1973] Weiner P., 1973, “Linear pattern matching algorithm,” In 14th Annual IEEE Symposium on Switching and Automata Theory, pages 1-11.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔