相似資料的尋取一直都是影像資料庫及影片資料庫兩個領域裡相當重要的議題。影片資料庫延伸了影像資料庫中擷取特徵的概念，依照不同的尋取方式可以分為兩類。第一類為低階的視覺特徵(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.