一個影片的內容可以視為一連串的影格，而每一個影格可以經由轉換以一個符號影像(symbolic image)來表示。根據符號影像中物件間空間關係之影片相似尋取是一個影片尋取的重要方法。在先前許多影片相似尋取的研究中，大多是根據影像中物件之空間關係計算查詢影片中之影像與參考影片中之影像的相似度，並以此作為計算查詢影片與參考影片相似程度之基礎。然而在影片中通常物件會移動，因此物件間之空間關係會產生變化，此種方法並未直接明確的考慮到在影片中物件間之空間關係的變化。
   在本論文中，我們將先定義物件間九種空間關係變化的類型。在影片中，從一影格至其下一影格，每兩個物件之間就會發生一種類型的空間關係變化，當多個物件同時存在時，在相鄰兩影格間就會有一組空間關係的變化，稱為空間關係變化集合(the Integrated Spatial Relationship Change，簡稱ISRC)。我們提出計算兩ISRC間之相似度方法。影片的相似尋取可以根據一串查詢的ISRC進行，將查詢ISRC序列和參考影片之ISRC序列做比較，並根據ISRC間之相似度，我們提出在參考影片之ISRC序列中找出與查詢影片相似的片段的方法。如此一來，即可進行以物件間之空間關係的變化為基礎之查詢。

A video can be viewed as a sequence of frames. Each frame can be transformed into a symbolic image. Similarity retrieval of video based on the spatial relationship between objects in the symbolic image is an important method for video retrieval. In the previous research, the similarity between the images of the query video and that of the reference video according to the spatial relationship between objects is computed, and then it is used as the base for computing the similarity between the query video and the reference video. However, objects usually move in the video and the spatial relationships between objects may change.  The change of the spatial relationship between objects in the video is not considered directly and precisely in previous research.
   In this thesis, we define nine types of changes of spatial relationship between objects. In the video, one type of change between two objects occurs from one frame to the next.  When multiple objects exist, there will be a set of spatial relations between the two adjacent frames, named as the integrated spatial relationship change (ISRC). We propose a method to calculate the similarity between two ISRCs. Similarity retrieval of video can be performed according to a sequence of query ISRC. The query ISRC sequence is compared with the ISRC sequence of the reference video. We proposed a method to locate the segment in the reference video similar to the query ISRC sequence based on the similarity between ISRCs. Hence, Similarity retrieval of video based on the change of spatial relationship can be achieved.

目錄
第一章 緒論	1
1.1 論文動機與目的	1
1.2 論文架構	4
第二章 相關研究	5
2.1 2D String	5
2.2 2D C-String	7
2.3 影片相似尋取	10
I.	全序列比對(Full-sequence Matching)	10
II.	段比對(Segment Matching)	10
III.	子序列比對(Subsequence Matching)	11
第三章 研究方法	13
3.1序值	13
3.2 物件間空間關係變化之類型	15
3.3 ISRC間相似度計算	19
3.4 影片相似尋取方法	21
第四章 範例說明	25
第五章 實驗	29
5.1 系統說明	31
5.2 影片查詢	35
5.2.1 m=3、z=3和t=8的實驗	39
5.2.2 m=3、z=4和t=8的實驗	40
5.3 實驗分析	42
5.3.1 尋取片段數統計	42
5.3.2 執行時間	44
第六章 結論	48
參考文獻	49

 
表目錄
表 1、2D C-String之空間關係符號涵意表	9
表 2、九種空間關係變化的類型	16
表 3、範例影片物件之序值	19
表 4、查詢ISRC序列與參考ISRC序列之相似關聯圖	27
表 5、ISRC間之相似度	27
表 6、m=3之9組實驗之尋取片段數 (單位：個)	43
表 7、m=4之9組實驗之尋取片段數 (單位：個)	43
表 8、m=5之9組實驗之尋取片段數 (單位：個)	44
表 9、m=3之9組實驗之執行時間 (單位：毫秒)	45
表 10、m=4之9組實驗之執行時間 (單位：毫秒)	45
表 11、m=5之9組實驗之執行時間 (單位：毫秒)	45
表 12、m=3之9組實驗比對兩個ISRC間是否相似所花費的平均時間 (單位：毫秒)	46
表 13、m=4之9組實驗比對兩個ISRC間是否相似所花費的平均時間 (單位：毫秒)	46
表 14、m=5之9組實驗比對兩個ISRC間是否相似所花費的平均時間 (單位：毫秒)	47
 
圖目錄
圖 1、2D String範例及其表示法	6
圖 2、13種空間關係	8
圖 3、三種影片尋取方法之架構	12
圖 4、影格中物件投影於X軸和Y軸上之範例圖	13
圖 5、X軸上的九種空間關係變化之範例圖	16
圖 6、範例影片	18
圖 7、ISRC之相似關聯圖	21
圖 8、U和V之相似之情形	23
圖 9、查詢影片之範例	25
圖 10、ISRC間之相似示意圖	28
圖 11、上下虛擬邊線與左右虛擬得分線示意圖	30
圖 12、以紅色點表示所有物件之MBR的中心點示意圖	30
圖 13、查詢模式	34
圖 14、瀏覽模式	35
圖 15、m=3之查詢影片	36
圖 16、m=4之查詢影片	37
圖 17、m=5之查詢影片	38
圖 18、z=m之情形的相似尋取結果之一	39
圖 19、z>m之情形的相似尋取結果之一	40
圖 20、z>m之情形的相似尋取結果之二	41

參考文獻
[1] 梁恩輝、陳顗任，〈根據物件間空間關係變化之影片相似尋取〉， 2014第九屆數位教學暨資訊實務研討會，頁30，南台科技大學， 2014。
[2] Chan, Y.K., and Chang, C.C., “Spatial similarity retrieval in video databases,” Journal of Visual Communication and Image Representation, Vol. 12, No. 2, pp. 107–122, 2001.
[3] Chang, S.K., Jungert, E., and Li Y., “Representation and retrieval of symbolic pictures using generalized 2D strings,” in: SPIE Proceedings on Visual Communications and Image Processing, Philadelphia, pp. 1360-1372, 1989.
[4] Chang, S.K., Shi, Q.Y., and Yan, C.W., “Iconic indexing by 2-D strings,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-9, No. 3, pp. 413-428, 1987.
[5] Flickner, M., Sawhney, H., Niblack, W., Ashley, J., Huang, Q, Dom, B., Gorkani, M., Hafner, J., Lee, D., Petkovic, D., Steele, D., and Yanker, P., “Query by image and video content: the QBIC system,” IEEE Computer Society, Vol. 28, No. 9, pp. 23-32, 1995.
[6] Hsu, F.J., Lee, S.Y., and Lin, B.S., “Video data indexing by 2D C-trees,” Journal of Hsu, F.J., Lee, S.Y., and Lin, B.S., “Video data indexing by 2D C-trees,” Journal of Visual Languages & Computing, Vol. 9, No. 4, pp. 375-397, 1998.
[7] Huang, P.W., and Jean, Y.R., “Using 2D C+-string as spatial knowledge representation for image database systems,” Pattern Recognition, Vol. 27, No. 9, pp. 1249–1257, 1994.
[8] Jungert, E., “Extended symbolic projections as a knowledge structure for spatial reasoning,” in: Proceedings of 4th BPRA Conference on Pattern Recognition, pp. 343–351, 1988.
[9] Lee, A.J.T., and Chiu, H.P., “2D Z-string: a  new spatial knowledge representation for image databases,” Pattern Recognition Letters, Vol. 24, No. 16, pp. 3015–3026, 2003.
[10] Lee, A.J.T., Chiu, H.P., and Yu, P., “3D C-string: a new spatio-temporal knowledge representation for video database systems,” Pattern Recognition, Vol. 35, No. 11, pp.  2521–2537, 2002.
[11] Lee, A.J.T., Chiu, H.P., and Yu, P., “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] Lee, A.J.T., Yu, P., Chiu, H.P., and Hong, R.W., “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] Lee, S.Y. and Hsu, F.J., “2D C-String: a new spatial knowledge representation for image database systems,” Pattern Recognition, Vol. 23, No. 10, pp. 1077-1087, 1990. 
[14] Lee, S.Y. and Hsu, F.J., “Spatial reasoning and similarity retrieval of images using 2D C-string knowledge representation,” Pattern Recognition Vol. 25, No 3, pp. 305–318, 1992.
[15] Lee, S. Y., Yang, M. C. and Chaen, J. W., “2D B-string: a spatial Knowledge Representation for Image Database Data and Knowledge Engineering,” in Proceedings of Second International Computer Science Conference (ICSC'92), Hong Kong, pp. 609-615, 1992.
[16] Liu, C.C., and Chen, A.L.P., “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] Shearer, K., Venkatesh, S., and Kieronska, D., “Spatial indexing for video databases,” Journal of Visual Communication and Image Representation, Vol. 7, No. 4, pp. 325–335, 1997.
[18] Yeung, M., Yeo, B.L., and Liu, B., “Extracting story units from long programs for video browsing and navigation,” in: Proceedings of the Third IEEE International Conference on Multimedia Computing and Systems, pp.296–305, 1996.
[19] Yu, P., “Weighted similarity retrieval of video database,” ICIC Express Letters, Vol. 4, No. 5(B), pp. 2009–2014, 2010.