簡易檢索 / 詳目顯示

研究生: 葉哲宇
論文名稱: 以NIOSⅡ處理器為基礎的音樂檢索FPGA硬體電路之實現
FPGA implementation of music retrieval systems based on NIOSⅡ processor
指導教授: 黃文吉
學位類別: 碩士
Master
系所名稱: 資訊教育研究所
Graduate Institute of Information and Computer Education
論文出版年: 2007
畢業學年度: 95
語文別: 中文
論文頁數: 108
中文關鍵詞: 音樂檢索字串比對精確比對近似比對
英文關鍵詞: String matching, Fast Text Searching Allowing Errors, Altera, FPGA
論文種類: 學術論文
相關次數: 點閱:170下載:1
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 隨著數位內容數量的大幅成長,包含聲音、音樂、影像、視訊等多媒體資料,對於數位內容的檢索也變成一個很重要的課題。音樂檢索則是針對音樂部份,使用者透過啍唱、語音與敲擊等不同的方式來選取網路上或資料庫中的歌曲。在目前多媒體數位內容日趨成熟,人們對於資訊需求不再侷限於文字上而已,愈來愈多的圖片、聲音、影像等多媒體將會成為搜尋對象。
    目前的音樂檢索均以字串比對為核心,不單單只有精確比對也要允許錯誤比對(近似比對)。但若在資料量大時作比對,會需要大量的計算時間。以精確比對為例子,m為搜尋音符的個數,n為歌曲的音符個數,精確比對的時間複雜度為O(m × n)。
    String Matching是很普遍且重要的問題,要在T=t1t2...tn中搜尋字串P=p1p2...pm,P及T有可能是一個檔案中的字元、DNA鹼基對(DNA base pairs)、程式中的一段程式碼、一多邊形的角或是樂譜中的音符及拍子等等。要在T中找尋有符合P字串的位置,也就是F = {i | 1≦i≦n-m+1 , titi+1...ti+m-1 = P},這類問題最有名的就是Boyer-Moore[13]和Knuth Morris Pratt[14]演算法。
    本篇論文採用Fast Text Searching Allowing Errors[6]理論基礎實現硬體的音樂檢索。對於只有Shift、AND、OR的演算法非常適合應用在硬體上面,且對時間複雜度更有大大的改善。當搜尋音符個數為m,歌曲音符個數為n時,時間複雜度為O(n),和允許錯誤個數d無關;相較於應用在軟體上面時間複雜度是O (d × n)。將整個電路放置在Altera公司的Stratix開發板上,搭配使用者端利用Borland C++ Builder程式開發使用者介面,透過網路便可組成一個完整快速又兼具FPGA特性的音樂檢索系統。

    With a great deal growth of digital contents such as media data of voices、musics、images and videos,it becomes an important topic for digital contents retrieval.The music retrieval focuses on the part of musics,and users retrieve songs from internet or database by humming、voicing and keying.In this day,people are no longer restricted to get resources in words with the maturation of media techniques. Accordingly,more and more pictures、voices and images would be objects to be searched.
    Music retrieval is based on the core of string matching presently.There are not only exact matching but approximate matching(allowing errors).However,it’s would take large number of time when it proceeds with huge datas.Take exact matching,m denotes the number of querying notes and n denotes the number of music notes,and the time complexity is O(m × n).
    String matching is a normal and significant problem. We are searching for the set of starting positions F = {i | 1≦i≦n-m+1 ,titi+1...ti+m-1 = P} for a string P=p1p2...pm inside a large text file T=t1t2...tn.The characters may be English characters in a text file, DNA base pairs, lines of source code, angles between edges in polygons, music notes and tempo in a musical score, and so forth. The two most
    famous algorithms for this problem are the Boyer-Moore algorithm [13] and the Knuth Morris Pratt algorithm [14].
    This thesis adopts Fast Text Searching Allowing Errors[6] as theorem to achieve music retrieval.It’s very suitable to apply on hardware with Shift、AND、OR algorithm only,and improves time cost significantly.m denotes the number of querying notes and n denotes the number of music notes.The hardware time complexity of the algorithm is O(n) irrelevant to the number of allowing errors(d) while O (d × n) for software.We append our circuits on Stratix development board by Altera corp. accompany with user querying UI(user interface) coded by Borland C++ 6.0 composed with network forms a high-speed FPGA music retrieval system.

    中文摘要....................................................i Abstract.................................................iii 誌謝.......................................................v 目錄......................................................vi 附表目錄...................................................x 附圖目錄...................................................xi 第一章 簡介.................................................1 第一節 研究動機..........................................1 壹、音樂檢索(Music Retrieval).........................1 貳、字串比對(String Matching).........................2 參、NIOS(Ⅱ)嵌入式核心處理器...........................3 第二節 研究目的..........................................5 第二章 字串比對法則..........................................6 第一節 Sliding Window...................................6 第二節 近似字串比對(Approximate String Matching)..........7 壹、允許替代 (substitution)...........................7 貳、允許插入 (insertion)..............................8 參、允許刪除 (deletion)...............................8 第三章 比對法則的硬體實現.....................................9 第一節 Exact Matching (完全比對).........................9 壹、shift-and 法則...................................9 貳、shift-and 實例...................................10 參、將shift-and 套用在電路上..........................11 第二節 Approximate Matching (近似比對)..................12 壹、允許取代 (substitution)..........................13 一、substitution法則..............................13 二、substitution實例..............................14 三、將substitution套用在電路上.....................15 貳、允許插入 (insertion).............................16 一、insertion法則.................................16 二、insertion實例.................................17 三、將insertion套用在電路上........................19 參、允許刪除 (deletion)..............................19 一、deletion法則..................................19 二、deletion實例..................................20 三、將deletion套用在電路上.........................22 肆、允許取代、插入、刪除...............................22 第三節 時間複雜度........................................23 壹、以軟體實現.......................................23 一、完全比對(Exact matching)......................23 二、近似比對(Approximate matching)................24 貳、以硬體實現.......................................26 第四章 系統架構............................................28 第一節 使用者端(Client).................................29 第二節 比對端(Server)...................................30 壹、Top circuit module..............................33 貳、內部各個module介紹................................35 一、Decoder......................................36 二、Num_note_keeper..............................38 三、Mask_table...................................38 四、Song_index_counter...........................39 五、Address_encoder..............................39 六、Matching_center..............................40 七、Check_pointer................................42 八、Result_storeroom.............................42 第五章 技術背景(Related Work)..............................43 第一節 Database........................................43 壹、Client端Database................................43 貳、Server端Database................................43 第二節 傳送Client端音符數目與mask table( )...............44 第三節 Read only file system...........................47 第四節 CF卡的存取.......................................47 第六章 系統運作實例.........................................51 第七章 實驗數據與效能評估....................................66 第一節 音樂database數目n對比對時間的影響..................68 壹、軟體數據.........................................68 貳、硬體數據.........................................71 參、軟硬體比較.......................................73 第二節 允許錯誤數目d對比對時間的影響.......................78 壹、軟體數據.........................................78 貳、硬體數據.........................................81 參、軟硬體比較.......................................82 第八章 結論與未來展望.......................................85 參考著作...................................................88 附錄一(Decoder真值表)......................................92

    [1]A. Ghias, J. Logan, D. Chamberlain, B. C. Smith,” Query
    by humming-musical information retrieval in an audio
    database”, ACM Multimedia ’95 San Francisco, 1995.
    [2]Chen, A. L. P., 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,” in Proc. of
    IEEE International Conference on Multimedia and Expo,
    2000.
    [3]J. Brown and B. Zhang, “Musical frequency tracking
    using the methods of conventional and ‘Narrowed’
    autocorrelation”. Journal of the Acoustical Society of
    America, Volume 89, Number 5, pages 2346-2354,1991.
    [4]Park, J. H., and George, K. M.,1999, “Parallel String
    Matching Algorithms Based on Dataflow,”Proceedings of
    the 32nd Hawaii International Conference on System
    Sciences.
    [5]Court, T. V., and Herbordt, M. C.,2006, “Families of
    FPGA-based accelerators for approximate string
    matching,” Microprocessors and Microsystems.
    [6]Wu, Sun and Manber, Udi,1992, “Fast Text Searching
    Allowing Errors,” Communications of the ACM, Vol. 35,
    No.10, pp.83-91.
    [7]Jyh-Shing Roger Jang, Hong-Ru Lee, and Chia-Hui Yeh,
    2001,“Query by Tapping: A New Paradigm for Content-
    based Music Retrieval from Acoustic Input,” Multimedia
    Information Retrieval Laboratory Computer Science
    Department, National Tsing Hua University, Taiwan, Vol. 8
    [8]Sastry, R., Ranganathan, N., and Remedios, K.,
    1995, “CASM: A VLSI Chip for Approximate String
    Matching,”IEEE Transactions on Pattern Analysis and
    Machine Intelligence, Vol. 17, No. 8, pp. 824-830.
    [9]Ranganathan, N., and Motamarri, R., 1997, “A VLSI
    Architecture for Computing the Optimal Correspondence of
    String Subsequences,” Computer Architectures for
    Machine Perception,pp. 290-294.
    [10]Mukherjee, A., 1989, “Hardware Algorithms for
    Determining Similarity Between Two String,” IEEE
    Transaction on Computers, Vol. 38, No. 4, pp. 600-603.
    [11]Navarro, G., 2001, “A Guided Tour to Approximate
    String Matching,” ACM Computer Surveys, Vol. 33, No. 1.
    [12]Bazea-Yates, R. A., and Gonnet, G. H., 1992, “A new
    approach to text searching,”Communication of the ACM,
    Vol. 35, No. 10, pp.74-82.
    [13]Boyer, R. and Moore, J., 1977, “A fast string
    searching algorithm.” Communication of the ACM, Vol.
    20, No. 10, pp.762-772.
    [14]Knuth, D. E., Morris, J. H., and Pratt, V. R.,
    1977, “Fast pattern matching in strings.” SIAM
    Journal on Computing, Vol.6, pp. 323-350.
    [15]Ukkonen, E., 1985, “Finding Approximate Patterns in
    Strings.,” Journal of Algorithms, Vol. 6, pp. 132-137.
    [16]Shang, H., and Merrettal, T. M., 1996, “ Tries for
    approximate string matching,” Knowledge and Data
    engineering, IEEE Transactions on, Vol. 8,Issue: 4, pp.
    540-547.
    [17]Shyamala Doraisamy, and Stefan M Rüger, 2001,“An
    Approach Towards A Polyphonic Music Retrieval System”,
    Dept. of Computing Imperial College,London SW7 2BZ,
    Vol.7
    [18]Weiner, P., 1973, “Linear pattern matching
    algorithms,”In Proceedings of IEEE Symposium on
    Switching and Automata Theory, pp. 1-11.
    [19]Lemstrom, K., 2000, “String Matching Techniques for
    Music Retrieval,” Department of Computer Sciencs
    Series of Publication A Report A.
    [20]曾元顯, 2000, “ 音樂內容查詢不匹配問題與檢索模式之研究,”輔仁
    大學圖書資訊學系 資訊傳播與圖書館學, Vol. 6, No. 4, pp.35-
    48.
    [21]Mukherjee, A., 1989,“Hardware Algorithms for
    Determining Similarity Between Two Strings”, Dept. of
    Comput. Sci., Univ. of Central Florida, Orlando, FL,
    IEEE TRANSACTIONS ON COMPUTERS, VOL. 38, NO. 4
    [22]Stephen Downie, and Prof. Michael Nelson,
    2000,“Evaluation of a simple and effective music
    information retrieval method”, Middlesex College,
    Univ.of Western Ontario,London, Ontario, Canada, Vol.8
    [23]J. Stephen Downie, 1999,“Music retrieval as text
    retrieval (poster abstract): simple yet effective”,
    University of Illinois at Urbana-Champaign501 E. Daniel
    St, Champaign IL, Vol.2
    [24]陳江村, 2001,“平行處理的音樂比對核心”, 清華大學資訊工程學
    系, Vol.45, No.2, No.8, No.9, No.10
    [25]Galil, Z., and Park, K., 1990,“An improved algorithm
    for approximate string matching”, SIAM Journal on
    Computing, Vol.19

    QR CODE