隨著網際網路和科技的發展，使得在網路中，多媒體資料被大量的建立，影片即是其中之一。然而如何從龐大的影片資料庫中，尋找出所想要的影片片段是很不容易的。一段影片可以視為一連串的畫面，根據畫面中的物件之影片尋取是一有效的方法，然而，在先前的研究中，注重在各個畫面物件的位置，並未考慮到在連續畫面間，物件的移動關係變化。 
在連續畫面中，物件可能移動，因物件移動而發生的空間關係變化是極為重要的資訊。本研究提出一索引結構，利用物件間的移動空間關係變化來建立一矩形圖形的索引，物件對在每個片段的移動資訊被記錄在一作為索引結構的矩形中。將許多矩形記錄在一個圖上，基於這些矩形，我們可以來分析影片片段的差異，並過濾和影片不相似的影片片段。最後我們利用 R-tree 來過濾影片資料，以提高影片查詢的效率。

By the growth of the technology and internet, a huge amount of multi-media data, such as video, have been created on the internet. However, searching for the pieces you want from this massive video database can be extremely challenging. A video can be seen as a series of frames. Video search based on the object in the video is an effective method. However, in previous studies, most of work is based on the location of the object.  The information about the change of the relationship between objects in the continuous frames is not considered.  
In continuous frames, objects may move. The information about the change of the spatial relationship between objects due to their movement is important. In this study, we present an index structure.  The type of change of spatial relationship between objects is used as the index to create a rectangle diagram. The information of objects  for a segment of video is recorded as a rectangle in the index structure.  Many rectangle are recorded in the diagram.  An then we can analyze the difference of each segment of the video based on their rectangle in the diagram, and find the similar segment of the video to the query video. Finally, we use R-tree to filter video data in order to improve the efficiency of the query in video.

第一章 緒論 1
1.1 研究背景動機與目的 1
1.2 論文架構 3
第二章 文獻探討 4
2.1 影片的空間關係表示法 4
2.1.1 2D String	4
2.1.2 2D C-String 6
2.2 R-tree 8
2.3 R-tree 的查詢 10
2.4 STR 演算法 11
第三章 移動區段、移動向量和移動空間關係 13
3.1 移動區段和移動向量 13
3.2 75 種物件對間移動空間關係 15
第四章 研究方法 16
4.1 影片資料索引 16
4.1.1 移動空間關係圖 16
4.1.2 移動空間關係序列 18
4.1.3 序列矩形 20
4.2 影片索引結構 23
4.3 影片過濾方法 25
第五章 實驗 27
5.1 影片資料庫 29
5.2 系統說明 31
5.3 查詢影片 33
第六章 結論 42
參考文獻 43


表目錄
表2-1：2D C-String 空間運算子的定義 7
表4-1：參考單元關係表 19
表4-2：物件對在第一個參考單元中物件的移動空間關係 22
表5-1：影片中物件的命名和順序 28
表5-2：第三層的序列矩形的座標資料 30
表5-3：實驗結果 39
表5-4：各組實驗之物件對和其矩形面積 40
表5-5：實驗執行時間(單位：毫秒) 40

圖目錄
圖2-1：最小邊界矩形 4
圖2-2：2D String 範例及其表示法 5
圖2-3：一維空間上 13 種空間關係 6
圖2-4：二維空間上之 169 種空間關係 7
圖2-5：節點間的重疊區域 9
圖2-6：R-tree 範例 11
圖2-7：STR 範例	12
圖3-1：相鄰影格物件對AB的相對位置	13
圖3-2：物件對AB可能發生的移動情形 13
圖3-3：物件於 fi 及 fi+1 之位置 14
圖3-4：移動向量	14
圖3-5：X 軸移動向量 14
圖3-6：Y 軸移動向量 14
圖3-7：X 軸移動區段 15
圖3-8：Y 軸移動區段 15
圖4-1：移動空間關係圖G 17
圖4-2：X 軸和 Y 軸的移動空間類型產生之二維圖形 17
圖4-3：物件O1和物件O2 18
圖4-4：物件(O1,O2)的參考單元形成之序列矩形	21
圖4-5：物件對(O1,O2)在第一個參考單元之序列矩形 22
圖4-6：參考單元和查詢序列矩形 23
圖4-7：O1O2 索引結構 24
圖4-8：影片過濾 O1O2 索引結構 25
圖5-1：實驗影片截取影像 27
圖5-2：以紅色點表示所有物件在場上的示意圖 28
圖5-3：查看序列矩形介面 29
圖5-4：系統畫面 32
圖5-5：第一組查詢影片 33
圖5-6：第一組查詢影片物件對之序列矩形 34
圖5-7：第二組查詢影片 35
圖5-8：第二組查詢影片物件對之序列矩形 35
圖5-9：第三組查詢影片 37
圖5-10：第三組查詢影片物件對之序列矩形 38

[1] 董明峰. "一個影片尋取之空間索引結構."淡江大學資訊管理學系碩士班學位論文(2007).
[2] 邱于真. "根據物件移動之影片空間相似尋取."淡江大學資訊管理學系碩士班學位論文(2013): 1-59.
[3] 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,” IEEEComputer Magazine, Vol. 28, No. 9, pp.23-32, 1995. 
[4] S.K. Chang, Q.Y. Shi, and C.W. Yan, “Iconic indexing by 2-D strings,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-9, No. 3, pp. 413-428, 1987. 
[5] E. Jungert, “Extended Symbolic Projection Used in A Knowledge Structure for Spatial Reasoning”, The 4th BPRA Conference on Pattern Recognition, Springer-Verlag, pp. 343-351, 1988. 
[6] S. K. Chang, E. Jungert, Y. Li, “Representation and Retrieval of Symbolic Pictures using Generalized 2D string”, Visual Communications and Image Processing IV, Philadelphia, pp. 1360 - 1372, 1989. 
[7] F.J. Hsu, S.Y. Lee, and B.S. Lin, “Video data indexing by 2D C-trees,” Journal of Visual Languages & Computing, Vol. 9, No. 4, pp. 375-397, 1998. 
[8] Y.K. Chan, and C.C. Chang,  “Spatial similarity retrieval in video databases,” Journal of Visual Communication and Image Representation, Vol. 12, No. 2, pp. 107–122, 2001. 
[9] A.J.T. Lee, and H.P. Chiu,  “2D Z-string: a  new spatial knowledge representation for image databases,” Pattern Recognition Letters, Vol. 24, No. 16, pp. 3015–3026, 2003. 
[10] A.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, No. 11, pp.  2521–2537, 2002. 
[11] A.J.T. Lee, H.P. Chiu, and P. Yu, “Similarity retrieval of videos by using 3D C-string knowledge representation,” Journal of Visual Communication and Image Representation, Vol. 16, No.6, pp.  749–773, 2005. 
[12] A.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, No. 16,  pp. 2500–2508, 2005. 
[13] 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, 1990. 
[14] D. Zhong, H.J. Zhang and S.F. Chang,“Clustering Methods for Video Browsing and Annotation,”SPIE Conference on Storage and Retrieval for Still Image and Video Databases IV, Vol. 2670, pp.239-246.1996 
[15] H.J. Zhang, J.Y.A. Wang and Y. Altunbasak,“Content-Based Video Retrieval and Compression: A Unified Solution,”International Conference on Image Processing(ICIP), Vol.1, pp.13-16, 1997. 
[16] C.C. Liu,  and A.L.P. Chen,  “3D-list: a data structure for efficient video query processing,” IEEE Transactions on Knowledge and Data Engineering, Vol. 14, No. 1, pp. 106–122, 2002. 
[17] K. Shearer, S. Venkatesh, and D. Kieronska, “Spatial indexing for video databases,” Journal of Visual Communication and Image Representation, Vol. 7, No. 4, pp. 325–335, 1997. 
[18] T. Arndt and S.K. Chang, “Image Sequence Compression by Iconic Indexing,” IEEE Workshop on Visual Languages, pp.177-182, 1989. 
[19] Hanjalic, “Adaptive Extraction of Highlights from A Sport Video Based on Excitement Modeling”, IEEE Transactions on Multimedia, vol. 7,no. 6, pp. 1114 – 1122, 2005. 
[20] H. T. Shen, J. Shao, Z. Huang, X. Zhou, “Effective and Efficient Query Processing for Video Subsequence Identification”, IEEE Transactions on Knowledge and Data Engineering, vol. 21, no. 3, pp. 321 – 334, 2008. 
[21] Francois Pitie, Sid-Ahmed Berrani, Anil Kokaram, Rozenn Dahyot, " Offline multiple object tracking using candidate selection and the viterbi algorithm, " IEEE Int. Conf. on Image Processing ICIP 2005, Vol 3, pp. 109-112, Sept. 2005. 
[22] F. J. Hsu and S. Y. Lee, “Spatial Reasoning and Similarity Retrieval of Images Using 2D C-String Knowledge Representation,” Pattern Recognition, Vol. 25, No. 3, pp. 305-318, March 1992. 
[23] F.J. Hsu, S.Y. Lee, B.S. and Lin,  “Video data indexing by 2D C-trees,” Journal of Visual Languages & Computing, Vol. 9, No. 4, pp. 375-397, 1998. 
[24] Y. Manolopoulos, A. Nanopoulos, A. N. Papadopoulos, Y. Theodoridis “R-trees: Theory and Applications”, Springer, ISBN: 9781852339777, 2006.  
[25] T. Brinkhoff, H. P. Kriegel, B. Seeger, “Efficient Processing of Spatial Joins Using R-trees”, Proceedings of the ACM SIGMOD international conference on management of data, New York, pp. 237-246, 1993. 
[26] S.T. Leutenegger, M.A. Lopez, and J.M. Edgington, “STR: A Simple and Efficient Algorithm for R-Tree Packing,” The 13th International Conference on Data Engineering, Vol. 7, Iss. 11, pp.497-506, 1997. 
[27] N. Beckman, H. P. Kriegel, “The R* tree: An efficient and robust access method for points and rectangles”, Proc. ACM SIGMOD, pp.322-331, 1990. 
[28] S. Y. Lee, M. K. Shan, W. P. Yang, “Similarity Retrieval of Iconic Image Database”, Pattern Recognition, vol. 22, no. 6, pp. 675–682, 1989. 
[29] S.K. Chang, Q.Y. Shi, and C.W. Yan,  “Iconic indexing by 2-D strings,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-9, No. 3, pp. 413-428, 1987.