基於內容的影片相似尋取(Content-Based Video Retrieval)是一種處理影片資料較合適的解決方法之一。然而隨著影片資料量越來越龐大，複雜性也越來越高。因此如何在大量的資料中進行影片尋取，儼然成為一個重要議題。
	在先前許多影片相似尋取的研究中，根據影像中物件之空間關係計算查詢影片中之影像與參考影片中之影像的相似度，並以此做為計算查詢影片與參考影片相似程度之基礎，然而此種方法並未明確考慮到在連續影格間物件間空間關係的變化及物件的移動方向。
	然而在影片中，在兩相鄰影格間因物件移動而造成空間關係變化及其移動方向之資訊是重要的。因此，在本論文中我們提出如何根據在兩相鄰影格之間物件間空間關係之變化，以及物件移動方向之變化計算相似度之方法，並以此作為影片相似尋取之依據。如此一來，即可進行以影格間之物件移動資訊作為條件之查詢。

Content-based video retrieval is an appropriate solution for retrieving video data. However, there are more and more video data and the task of video retrieval becomes more complicated. Therefore, how to perform video retrieval in the large amount of data is a critical issue.
	In the previous research, the similarity between the query video and the reference video is based on the similarity between the images of query video and that of reference video. As a result, the change of spatial relation between objects in the video and the moving direction of the objects are not considered in this approach.
	However, it is important because object movement between two continuous frames will cause the change of spaital relation between objects and the moving direction of the objects in the video. In this paper, we propose the approach to calculate the similarity of the change of the spatial relation between objects and their moving direction  between two continuous frames and use it as the basis of video similarity retrieval. Therefore, we can perform the similarity retrieval of video using the moving information of the objects between two continuous frames.

目錄
第一章 緒論	1
1.1 論文動機與目的	1
1.2 論文架構	4
第二章 相關研究	5
2.1 2D String	5
2.2 2D B-String	7
2.3 2D C-String	8
2.4 影片相似尋取	10
I.	全序列比對(Full-sequence Matching)	10
II.	段比對(Segment Matching)	10
III.	子序列比對(Subsequence Matching)	11
第三章 研究方法	15
3.1 建立位移區段及移動向量組	15
3.2 七十五種物件對間移動向量之空間關係	18
3.3移動向量組相似度之評量	22
3.3.1 移動向量對的空間關係距離之計算	22
3.3.2移動向量的移動方向距離之計算	30
3.3.3 計算移動向量組之距離	32
3.4 影片相似尋取方法	34
3.5影片相似尋取範例	38
第四章 實驗與分析	43
4.1 系統說明	45
4.2 影片查詢	48
4.2.1 z=q之情形的尋取範例	49
4.2.2 z>q之情形的尋取範例	50
4.3 實驗分析	52
第五章 結論	55
參考文獻	56

圖目錄
圖 1、2D String範例及其表示法	6
圖 2、2D B-String表示法之範例	8
圖 3、一維空間上物件對的13種空間關係	9
圖 4、三種影片尋取方法之架構	13
圖 5、Type-0、1、2子序列比對示意圖	14
圖 6、物件投影至x軸及y軸之字串範例	16
圖 7、物件A之位移區段	17
圖 8、物件A於Frame i及Frame i+1之移動情形	17
圖 9、物件A之移動向量	18
圖 10、MVSx之範例	18
圖 11、兩物件在一維空間上位移區段之移動空間關係	20
圖 12、在一維空間上某物件不移動之位移區段空間關係	21
圖 13、範例影片	23
圖 14、物件對AB於某一影格中可能的空間關係距離圖	23
圖 15、MVSx相似尋取範例說明1	25
圖 16、MVSx相似尋取範例說明2	27
圖 17、MVSx P與S間距離之計算過程	28
圖 18、(向量A,向量B)之SRD圖	29
圖 19、在x軸上一物件移動方向調整過程之範例	31
圖 20、一物件於x軸及y軸移動方向之MDD圖	31
圖 21、計算兩個MVSx距離之範例	33
圖 22、U和V之MBF match之情形	37
圖 23、查詢MBF序列	39
圖 24、參考影片MBF序列	40
圖 25、尋取結果1	40
圖 26、尋取結果2	41
圖 27、系統中四條虛擬邊線與得分線示意圖	44
圖 28、兩個擊球盤與曲棍球之物件標示示意圖	45
圖 29、系統畫面1	46
圖 30、系統畫面2	48
圖 31、查詢MBF序列	50
圖 32、z=q之情形的相似尋取結果之一	50
圖 33、z>q之情形的相似尋取結果之一	52

表目錄
表 1、2D C-string空間運算子的定義	9
表 2、(向量A,向量B)之起始點與結束點可能的空間關係表	26
表 3、u1與v1~v7之尋取過程	41
表 4、u2與v1~v7之尋取過程	42
表 5、各實驗與各門檻值之D、E、F對照表	53
表 6、各實驗之準確率及召回率對照表	54

[ 1 ] 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. 
[ 2 ] S. K. Chang, Q. Y. Shi and C. W. Yan, ”Iconic indexing by 2D-strings,” IEEE Trans. On Pattern Analysis and Matching Intelligence, PAMI-9, pp.413-428, May 1987. 
[ 3 ] A. Del Bimbo and P. Pala, “Visual Image Retrieval by Elastic Matching of User Sketches,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 19, No. 2, February 1997. 
[ 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 ] M. Flickner et al., “Query by image and video content: The QBIC system”, IEEE Compute. Mag., Vol.28, pp.23-32, Sept. 1995. 
[ 6 ] V.N. Gudivada and V.V. Raghavan, eds., “Content-based Image Retrieval Systems,”IEEE Computer, Vol. 28, No. 9, pp. 18-22, Setember 1995. 
[ 7 ] P.W. Huang and Y.R. Jean, “Spatial reasoning and similarity retrieval for image database system based on RS-strings,” Pattern Recognition, pp.2103-2114, 1996. 
[ 8 ] 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. 
[ 9 ] E. B. Hunt, J. Marin, and P. J. Stone, Experiments in Induction, Academic Press, New York, 1966. 
[ 10 ] 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. 
[ 11 ] C. C. Liu and A. L. P. Chen, “3D-List: A Data Structure for Ecient Video Query Processing,” IEEE Trans. on Knowledge and Data Engineering, Vol. 14, No. 1, pp. 106-122, Feb. 2002. 
[ 12 ] A. J. T. Lee, H. P. Chiu, P. Yu, “3D C-string: a new spatio-temporal knowledge structure for video database systems,” Pattern Recognition, Vol. 35, pp. 2521-2537, 2002. 
[ 13 ] S. Y. Lee, M. C. Yang, and J. W. Chaen, "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.
[ 14 ] A. J. T. Lee, P. Yu, H.P. Chiu and R.W. Hong, 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, pp. 2500-2508, 2005.
[ 15 ]H. C. Lin, L. L. Wang and S. N. Yang, “Color image retrieval based on hiMDDen Markov models,” IEEE Transactions on Image Processing, Vol. 6, No. 2, 1997.
[ 16 ] Hsu, F.J., Lee, S.Y., and Lin, B.S., “Video data indexing by 2D C-trees,” Journal of Visual Languages and Computing, vol. 9, pp. 375-397, 1998.
[ 17 ] D. Sagarmay, Z. Yanchun, "An Overview of Content-based Image Retrieval Techniques," aina, Vol. 01, No. 1, p. 59, 18th 2004. 
[ 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, Venkatesh, S., and Kieronska, D., “Spatial Indexing for Video Databases,” J. Visual Commun. Image Representation, vol. 7, pp. 325-335, 1996.
[ 20 ] H. Tamura and N. Yokoya, “Image database systems: a survey, ”Pattern Recognition, Vol. 17, NO. 1, pp.29-43, 1984.
[ 21 ] Ping Yu, Weighted similarity retrieval of video database, ICIC Express Letters, Vol. 4, Number 5( B ), Oct. 2010