隨著多媒體資料庫技術的發展，多媒體資料的數量愈來愈多，其中包括影像資料、影片資料等等。在影片資料庫中，影片中的每一個畫面可視為是一張靜態影像，因此影片的相似尋取技術可由影像相似尋取技術延伸而來。影像內容大致可分為低階視覺特徵(low-level visual feature)和高階關係特徵(high-level relationship feature)。而高階關係特徵中的空間關係(spatial relationships)則是常用衡量兩張影像之間的相似度的標準之一。在過去的研究中，多是以字串表示的方式來描述影像中物件對之間的空間關係，並以這種字串做為相似尋取之根據。在本篇論文中，我們對空間關係做編碼，並提出一個以編碼後的結果表示影片中兩兩物件一連串的空間關係變化的表示法，稱為關係序列(Relation Number Sequence，RNS)，並利用關係序列的內容做為相似尋取的依據。此外為了更客觀地表示相似程度，本篇論文以從圖(graph)中找出最大完全子圖(maximal complete subgraph)的方式，提供相似度的值。

According to the improvement of multimedia techniques there are more and more multimedia data such as image and video. There are also many multimedia database including image database systems and video database systems. In video data, each frame of the video is exactly a still image. The techniques of video data similarity retrieval can be extended from that in image data. Image content can be categorized into low-level visual features and high-level relationship features. In high-level relationship, spatial relationships are usually used in determining the similarity between two images. In the previous researches, spatial relations between two objects are recorded by using string. These strings are then used to determine the similarity between two images.
In this paper, we encode spatial relations by giving each of them a number. We use these numbers to represent the sequential spatial relation changes between two objects in the video. The sequences of number changes are called Relation Number Sequence (RNS for short). The RNSs are the criteria for determinant the similarity between two videos. In order to provide an objective similarity degree, we use the nodes of a maximal complete subgraph to represent the similarity between two videos.

目錄
第一章	緒論-----------------------------------------------------------------------1
1.1	研究背影及動機-----------------------------------------------------1
1.2	論文架構--------------------------------------------------------------2
第二章	相關研究-----------------------------------------------------------------3
2.1	影像資料的表示結構--------------------------------------------------3
2.1.1	2D字串-----------------------------------------------------------3
2.1.2	2D C字串--------------------------------------------------------4
2.1.3	2D C+字串--------------------------------------------------------7
2.2	影片資料的表示結構--------------------------------------------------9
2.2.1	3D C字串--------------------------------------------------------9
2.2.2	3D Z字串-------------------------------------------------------10
2.3	影像相似尋取---------------------------------------------------------12
2.4	相關研究總結---------------------------------------------------------14
第三章	利用時空資訊之影片相似尋取------------------------------------15
3.1	基本概念---------------------------------------------------------------15
3.2	影片索引方法---------------------------------------------------------16
3.2.1	關係號碼及空間關係畫面表--------------------------------16
3.2.2	關係序列--------------------------------------------------------18
3.3	影片相似尋取---------------------------------------------------------23
3.3.1	typ-1及type2相似--------------------------------------------23
3.3.2	相似尋取方法--------------------------------------------------30
第四章	實驗---------------------------------------------------------------------36
第五章	結論---------------------------------------------------------------------41
參考文獻--------------------------------------------------------------------------42

圖目錄
圖2.1.1 (a) 2D字串範例圖形------------------------------------------------------------------4
圖2.1.1 (b) (a)的字串表示法------------------------------------------------------------------4
圖2.1.2 一維空間上之13種空間關係------------------------------------------------------5
圖2.1.3 2維平面上的169種空間關係-------------------------------------------------------6
圖2.1.4 (a) 影像f1-------------------------------------------------------------------------------6
圖2.1.4 (b) 影像f2------------------------------------------------------------------------------6
圖2.1.5 具有相同之2D C字串但物件相對位置不一樣的圖---------------------------7
圖2.2.1 一部影片中的6個畫面------------------------------------------------------------10
圖2.2.2 (a) 某段影片中的3個畫面--------------------------------------------------------11
圖2.2.2 (b) 將4個物件的初始位置投影至x及y軸------------------------------------11
圖2.3.1 2D字串的影像比對範例-----------------------------------------------------------13
圖2.3.2 (a) f1及f2的type-0相似物件對----------------------------------------------------14
圖2.3.2 (b) f1及f2的type-1相似物件對----------------------------------------------------14
圖2.3.2 (c) f1及f2的type-2相似物件對----------------------------------------------------14
圖3.2.1 鏡頭架構示意圖---------------------------------------------------------------------20
圖3.2.2 物件O1及物件O2-------------------------------------------------------------------22
圖3.3.1 物件1與物件2的空間關係變化情形-------------------------------------------24
圖3.3.2 畫面1至畫面47期間，物件O1、O3、O4的空間關係變化---------------------27
圖3.3.3 STRS((1, 3), (1, 4))形成過程之概念示意圖------------------------------------------29
圖3.3.4 (a) 在頂點(O1, O3)及(O1, O4)之間加上邊---------------------------------------35
圖3.3.4 (b) type-2相似尋取的結果圖------------------------------------------------------35
圖4.1 影片中固定不動的物件--------------------------------------------------------------37
圖4.2 產生查詢界面--------------------------------------------------------------------------38
圖4.3 以拖曳的方式產生查詢影片之查詢結果-----------------------------------------40
 
表目錄
表3.2.1 空間關係編碼表---------------------------------------------------------------------17
表3.2.2 空間關係畫面表---------------------------------------------------------------------18
表4.1 效能分析--------------------------------------------------------------------------------36
表4.2 影片中物件代碼與名稱對應表-----------------------------------------------------38

[1]	J. F. Allen, “Maintaining Knowledge about Temporal Intervals,” Commun. ACM, vol. 26, pp.832-843, 1983.
[2]	T. Arndt and S. K. Chang, “Image Sequence Compression by Iconic Indexing,” 1989 IEEE Workshop on Visual Languages, The Institute of Electrical and Electronic Engineers, IEEE Computer Society, Silverspring, MD, pp. 177-182, Oct. 1989.
[3]	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, May 1987.
[4]	M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B. Dom, M. Gorkani, J. Hafner, D. Lee, D. Petkovic, D. Streele, and P. Yanker, “Query by Image and Video Content: The QBIC System,” Computer, vol. 28, no. 9, pp. 23-32, Sept. 1995.
[5]	P. W. Huang and Y. R. Jean, “2D C+-String as Spatial Knowledge Representation for Image Database Systems,” Pattern Recognition, vol. 27, no. 9, pp. 1249-1257, 1994.
[6]	P. W. Huang and C. H. Lee, “Image Database Design Based on 9D-SPA Representation for Spatial Relations,” IEEE Trans. on Knowledge and Data Engineering, vol. 16, no. 12, 2004.
[7]	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.
[8]	D. E. Knuth, J. H. Morris (Jr), V. R. Pratt, “Fast Pattern Matching in Strings,” SIAM Journal on Computing vol. 6, no. 1, pp. 323-350, 1977.
[9]	Tony C. T. Kuo and Arbee L. P. Chen, “Content-Based Query Processing for Video Databases,” IEEE Trans. on Multimedia, vol. 2, no. 1, March 2000.
[10]	Anthony J. T. Lee, Han-Pang Chiu and Ping Yu, “3D C-String: A New Spatio-Temporal Knowledge Representation for Video Database Systems,” Pattern Recognition, vol. 35, no. 11, 2002.
[11]	Anthony J. T. Lee, Ping Yu, Han-Pang Chiu, and Ruey-Wen Hong, “3D Z-String: A New Knowledge Structure to Represent Spatio-Temporal Relations between Objects in a Video,” Pattern Recognition Letters, vol. 26, pp. 2500-2508, 2005.
[12]	S. Y. Lee and F. J. Hsu, “2D C-String: A New Spatial Knowledge Representation for Image Database Systems,” Pattern Recognition, vol. 23, no. 10, pp. 1077-1087, Oct, 1990.
[13]	S. Y. Lee and F. J. Hsu, “Spatial Reasoning and Similarity Retrieval of Images Using 2D C-String Knowledge Representation,” Pattern Recognition, vol. 25, no. 3, pp. 305-318, March 1992.
[14]	S. Y. Lee, M. K. Shan, and W. P. Yang, “Similarity Retrieval of Iconic Image Database,” Pattern Recognition, vol. 22, pp. 675-682, 1989.
[15]	C. C. Liu and Arbee L. P. Chen, “3D-List: A Data Structure for Efficient Video Query Processing,” IEEE Trans. on Knowledge and Data Engineering, vol. 14, no. 1, 2002.
[16]	M. Nabil, A.H.H. Ngu, and J. Shepherd, “Picture Similarity Retrieval Using the 2D Projection Interval Representation,” IEEE Trans. Knowledge and Data Eng., vol. 8, no. 4, pp. 533-539, Aug. 1996.
[17]	E. Oomoto and K. Tanaka, “OVID: Design and Implementation of a Video-Object Database System,” IEEE Trans. On Knowledge and Data Engineering, vol. 5, no. 4, pp. 629-643, Aug. 1993.
[18]	K. R. Shearer, H. Bunke, and S. Venkatesh, “Video Indexing and Similarity Retrieval by Largest Common Subgraph Detection using Decision Trees,” Pattern Recognition, vol. 34, pp. 1075-1091, 2001.
[19]	K. R. Shearer, S. Venkatesh, and D. Kieronska, “Spatial Indexing for Video Databases,” J. Visual Commun. Image Representation, vol. 7, pp. 325-335, 1996.
[20]	K. R. Shearer, D. Kieronska, and S. Venkatesh, “Resequencing Video Using Spatial Indexing,” J. Visual Languages Comput., vol. 8, pp. 193-214, 1997.
[21]	J. R. Smith and S. F. Chang, “VisualSEEK: A Full Automated Content-Based Image Query System,” Proc. Fourth ACM Int’l Multimedia Conf., pp. 87-98, 1996.
[22]	Sagarmay Deb, “Video Data Management and Information Retrieval,” Idea Group Inc. 2005.