淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


  查詢圖書館館藏目錄
系統識別號 U0002-2106200613295000
中文論文名稱 一個應用於影片尋取之Suffix trie資料結構
英文論文名稱 A Suffix Trie Data Structure for Video Retrieval
校院名稱 淡江大學
系所名稱(中) 資訊管理學系碩士班
系所名稱(英) Department of Information Management
學年度 94
學期 2
出版年 95
研究生中文姓名 黃貫展
研究生英文姓名 Kuan-Chan Huang
學號 692520025
學位類別 碩士
語文別 中文
口試日期 2006-05-20
論文頁數 40頁
口試委員 指導教授-梁恩輝
委員-張昭憲
委員-連志成
委員-吳瑞堯
中文關鍵字 相似尋取  拓撲關係  空間關係  Suffix trie 
英文關鍵字 Similarity Retrieval  Topology  Spatial relationship  Suffix trie 
學科別分類 學科別社會科學管理學
學科別社會科學資訊科學
中文摘要 相似資料的尋取一直都是影像資料庫及影片資料庫兩個領域裡相當重要的議題。影片資料庫延伸了影像資料庫中擷取特徵的概念,依照不同的尋取方式可以分為兩類。第一類為低階的視覺特徵(Low-level visual features),例如物件的顏色、紋理、或是形狀等。第二類為高階的關係特徵(High-level relationship features),例如兩兩物件間的相對距離、位置、及拓撲(topology)關係。在本篇論文中,我們以空間關係運算子描述兩兩物件在影片當中所產生的空間關係,並且將其記錄在空間關係畫面表裡,將影片尋取簡化為子字串搜尋,並且透過建立suffix trie的方式以增進影片尋取的效率,其時間複雜度僅取決於查詢影片的物件個數與長度。
英文摘要 Similarity retrieval is a very popular issue in both fields of image databases and video databases. Video databases extend the concept of image database by extracting features. These features can be classified as low-level visual features such as color, texture or shape and high-level relationship features such as distance, direction or topology. In this thesis, we use operators to describe spatial relationship which is formed between objects and record them in spatial relationship frame tables of x-axis and y-axis. Finally, the suffix trie is used to create an efficient index structure for each spatial relationship frame tables. The time complexity is determined by the number of objects and the length of query video only.
論文目次 目錄
第一章 緒論
1.1 研究背景...............................................1
1.2 研究動機...............................................2
1.3 研究目的...............................................3
1.4 論文架構...............................................3
第二章 相關研究
2.1 在影像資料庫中的知識表示法.............................4
2.1.1 2D-string簡介......................................5
2.1.2 2D C-string簡介.....................................6
2.2 在影片資料庫中的知識表示法.............................7
2.2.1 3D C-string簡介.....................................7
2.2.2 3D Z-string簡介....................................10
2.3 索引結構Suffix trie...................................12
2.4 討論..................................................14
第三章 以空間關係為基礎之影片尋取方法
3.1 物件對與空間關係畫面表................................15
3.2 利用Suffix trie結構建立空間關係畫面表之索引..........20
3.3 以空間關係為基礎之影片尋取............................23
第四章 分析與實驗
4.1 分析..................................................31
4.2 真實影片之尋取........................................32
第五章 結論與未來研究方向....................................38
參考文獻.....................................................39

圖目錄
圖2-1:範例影像及其2D String.........................................5
圖2-2:範例影像及其u-string與v-string...............................6
圖2-3:將圖2-3影片投影在x-、y-及時間軸上...........................8
圖2-4:範例影片以及相對應的3D C-string...............................9
圖2-5:Frame 7至Frame 9之變化.......................................10
圖2-6:範例影片及對應的3D Z-string..................................11
圖2-7:依照英文單字「GOOGLE」所建立之Suffix trie......................13
圖2-8:查詢「OGL」之走訪範例.........................................14
圖3-1:物件位置相反時2D C-string的表示方式.........................16
圖3-2:範例影片1...................................................18
圖3-3:x軸上的Suffix trie..........................................23
圖3-4:y軸上的Suffix trie.........................................23
圖3-5:Suffix trie之走訪範例.......................................29
圖4-1:路口影片的物件名稱定義......................................32
圖4-2:查詢工具程式畫面............................................33
圖4-3:尋取條件1 ..................................................34
圖4-4:尋取條件1的尋取結果........................................35
圖4-5:尋取條件2...................................................36
圖4-6:尋取條件2的尋取結果.........................................37

表目錄
表3-1:2D C-string的空間關係運算子..................................17
表3-2:增加的空間關係運算子........................................18
表3-3:由範例影片1所產生的空間關係畫面表...........................19
表3-4:查詢用的空間關係畫面表......................................28
表3-5:交集結果....................................................30
參考文獻 [1] P.W. Huang and C. H. Lee, “Image Database Design Based on 9D-SPA Representation for Spatial Relations,” IEEE Trans. Knowledge and Data Eng, vol. 16, no. 12, pp.1486-1496, 2004.
[2] S. Pardhan, K. Tajima, and K. Tanaka, “A Query Model to Synthesize Answer Frames from Indexed Video Units,” IEEE Trans. Knowledge and Data Eng, vol. 13, no. 5, pp. 824-838, 2001.
[3] C. T. Kuo and L. P. Chen, “Content-Based Query Processing for Video Databases,” IEEE Trans. Knowledge and Data Eng, vol. 2, no. 1, pp. 1-13, 2000.
[4] A. Yoshitaka and T. Ichikawa, “A Survey on Content-Based Retrieval for Multimedia Databases,” IEEE Trans. Knowledge and Data Eng, vol. 11, no. 1, pp. 81-93, 1999.
[5] H. Jiang and A. K. Elmagarmid, “WVTDB-A Semantic Content-Based Video Database System on the World Wide Web,” IEEE Trans. Knowledge and Data Eng, vol. 10, no. 6, pp. 947-966, 1998.
[6] E. Oomoto and K. Tanaka, “OVID: Design and Implementation of a Video-Object Database System,” IEEE Trans. Knowledge and Data Eng, vol. 5, no. 4, pp. 629-643, 1993.
[7] J.T. Lee, H. P. Chiu, and P. Yu, “3D C-string: a new spatio-temporal knowledge representation for video database systems,” Pattern Recognition, vol. 35, issue 11, pp. 2521-2537, 2002.
[8] J.T. Lee, P. Yu, H. P. Chiu, and R. W. Hong, “3D Z-string: A new knowledge structure to represent spatio-temporal relations between objects in a video,” Pattern Recognition Letters, vol. 26, issue 16, pp. 2500-2508, 2005.
[9] S.Y. Lee and F.J. Hsu, “2D C-String: A New Spatial Knowledge Representation for Image Database Systems,” Pattern Recognition, vol. 23, pp.1077-1088, 1990.
[10] H. T. Bruns and M. J. Egenhofer, “Similarity of Spatial Scenes,” Seventh International Symposium on Spatial Data Handling, Delft, The Netherlands, Taylor & Francis, London, pp.173-184, 1996.
[11] M.J. Egenhofer and R.D. Franzosa, “Point-Set Topological Spatial Relations,” Int’l J. Geographical Information Systems, vol. 4, no. 2, pp.161-174, 1991.
[12] S.K. Chang, Q.Y. Shi, and C.W. Yan, “Iconic Indexing by 2-D Strings,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 9, no. 3, pp.413-428, 1987.
[13] Briandais, “File Searching Using Variable Length Keys,” In Proceedings of Western Joint Computer Conference, pp.295-298, 1959.
[14] E. Fredkin and B. Beranek, “Trie Memory,” Communications of the ACM, vol. 3, no. 9, pp. 490-500, 1960.
[15] E. Ukkonen, “On-line construction of suffix trees,” Algorithmic., vol.14, issue 3, pp. 249-260, 1995.
[16] F. Idris and S. Panchanathan, “Review of Image and Video Indexing Techniques,” Journal of Visual Communication and Image Representation, vol. 8, no. 2, pp. 146-166, June 1997.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2006-06-26公開。
  • 不同意授權瀏覽/列印電子全文服務。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信