基於內容的影片相似尋取(content-based video retrieval)是一種處理影片資料較合適的解決方法之一。然而隨著影片資料量越來越龐大，複雜性也越來越高，因此如何找到一個方法來建立影片資料索引，使得影片相似尋取能夠更有效率，儼然成為一個重要的議題。本研究提出一個較有效率的索引結構，來提高影片尋取的效率。我們採用兩兩物件之間的空間關係(spatial relation)為基礎，來建立影片資料的索引，並且將索引資料以圖形的方式來呈現，透過圖形的呈現，以利分析兩影片段空間關係變化的差異。接著，我們利用R-Tree來建立這些圖形資料索引結構，並利用window query過濾影片資料，以提高影片尋取的效率；影片相似比對部分，我們利用尋找子字串(substring matching)以及最大完全子圖(Largest Complete Subgraph, LCS)來衡量影片相似度。

With recent advances in multimedia technologies, digital TV and information highways, more and more video data are being captured, produced and stored. However, without appropriate techniques that can make the video content more accessible, all these data are hardly usable. So the research on the management of video data is now a hot field. But the differences between multimedia and textual data in continuity and dimensionality make traditional database technology unavailable for access to handle the multimedia information. Consequently, the content-based access and retrieval become a proper solution
In this paper, we propose a new spatial index structure to alleviate the above facing limitations for efficient video retrieval. We index spatial relations between objects in a video and present these spatial information by graphs. Using the graphs, we can compare any two segment video data more easier. Besides, we establish the graphs a index structure by the R-Tree. Based on the R-Tree data structure, we can use window query to filter video data, and let video retrieval more efficient. In video similarity retrieval, we use substring matching and largest complete subgraph (LCS) to measure video similarity.

目錄
第一章 緒論	1
1.1	研究動機與目的	1
1.2	論文架構	4
第二章 文獻探討	5
2.1  利用空間關係建立影像及影片的索引表示法	5
2.2   R-Tree	9
2.3  影像相似尋取	12
第三章 利用空間索引結構之影片尋取	15
3.1	影片資料索引	15
3.1.1	關係座標及空間關係圖	16
3.1.2	空間關係序列	17
3.1.3	序列矩形	20
3.2	影片索引結構	26
3.3  影片相似衡量	29
3.4  影片尋取	32
第四章 實驗	36
4.1  影片資料	36
4.2  建立影片資料庫	37
4.3  影片查詢	38
第五章 結論	42
參考文獻	43
 
圖目錄
圖2.1.1  一維空間上之13種空間關係	5
圖2.1.2  二維空間上之169種空間關係	6
圖2.1.3  物件起始點及終點投影在雙軸上	7
圖2.1.4  2D C字串表示法的例子	7
圖2.1.5  一部影片中的6個畫面	8
圖2.2.1  R-Tree	10
圖2.2.2  (a) dead space  (b) overlap	11
圖2.2.3  R+-tree	12
圖2.3.1  2D字串的影像比對範例	13
圖2.3.2  2D-String-LCS 尋取結果	14
圖3.1.1  空間關係圖	16
圖3.1.2  畫面654到畫面659之內容	18
圖3.1.3  物件O1及物件O2	20
圖3.1.4  物件O1從左向右超越物件O2	21
圖3.1.5  兩段shots之物件O1及O2所形成的SR	22
圖3.1.6  物件O1從O2物件下方向上超越物件O2	22
圖3.1.7  兩段shots中相同物件對之SR	24
圖3.1.8  序列矩形查詢範例	25
圖3.2.1  R-tree在空間關係座標圖所呈現的結構	27
圖3.2.2  R-tree	28
圖3.2.3  影片索引結構	28
圖3.3.2  時空序列相似尋取的結果圖	32
圖3.4.1  查詢的範例影片的每個物件對之序列矩形	33
圖4.1.1  影片中固定不動的物件	36
圖4.2.1  序列矩形分布情形	37
圖4.2.2  R-tree在空間關係座標圖上的結構	38
圖4.3.1  查詢影片段介面	39
圖4.3.2  範例影片段移動變化	39
圖4.3.3  範例影片段查詢結果	40
 
表目錄
表3.1.1  空間關係畫面表	17
表4.1.1  影片中物件代碼與名稱對應表	37
表4.3.1  查詢型態	41
表4.3.2  實驗結果	41

參考文獻
[1]	A. Guttman,“R-trees: a Dynamic Index Structure of Spatial Searching,”ACM SIGMOD international conference on Management of data, pp.47-57, 1984.
[2]	A.J.T. Lee, H.P. Chiu and P. Yu, “3D C-string: A New Spatio-Temporal Knowledge Structure for Video Database Systems,” Pattern Recognition Letters, Vol. 35, No. 11, pp.2521–2537, 2002.
[3]	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, Iss. 16, pp.2500–2508, 2005.
[4]	A. Nagasaka and Y. Tanaka,“Automatic Video Indexing and Full-Video Search for Object Appearances,”IFIP TC2/WG 2.6 Second Working Conference on Visual database System II, pp.113-127, 1991.
[5]	C.C. Liu and A.L.P. Chen, “3D-List: A Data Structure for Efficient Video Query Processing,” IEEE Transaction on Knowledge and Data Engineering, Vol. 14, Iss. 1, pp.106-122, 2002.
[6]	D.E. Knuth, J.H. Morris and V.R. Pratt, “Fast Pattern Matching in Strings,” SIAM Journal on Computing, Vol. 6, No. 1, pp.323-350, 1997.
[7]	D. Sagarmay, “Video Data Management and Information Retrieval,” IRM Press, 2004.
[8]	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.
[9]	E. Oomoto and K. Tanaka, “OVID: Design and Implementation of a Video-Object Database System,” IEEE Transaction on Knowledge and Data Engineering, Vol. 5, No. 4, pp.629-643, 1993.
[10]	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, 1997.
[11]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.
[12]H.M. Kao,“Video Indexing: An Approach Based on Moving Object and Track,”Storage and Retrieval for Image and Video Databases (SPIE), Vol. 1908, pp.25-36, 1993.
[13]	J.F. Allen, “Maintaining Knowledge about Temporal Intervals,” Communications of the ACM, Vol. 26, No. 11, pp.832-843, 1983.
[14]	J.R. Smith and S.F. Chang, “VisualSEEK: A Full Automated Content-Based Image Query System,” ACM Multimedia, pp.87-98, 1996.
[15]	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, 1996.
[16]	K. Shearer, D. Kieronska and S. Venkatesh, “Resequencing of Video Using Spatial Indexing,” Journal of Visual Languages and Computing, Vol. 8, No. 2, pp.193-214, 1997.
[17]	K. Shearer, H. Bunke and S. Venkatesh, “Video Indexing and Similarity Retrieval by Largest Common Subgraph Detection Using Decision Trees,” Pattern Recognition, Vol. 34, No. 5, 2001, pp.1075-1091, 2001.
[18]	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,” IEEE Computer Magazine, Vol. 28, No. 9, pp.23-32, 1995.
[19]	M. Nabil, A.H.H. Ngu and J. Shepherd, “Picture Similarity Retrieval Using the 2D Projection Interval Representation,” IEEE Transactions on Knowledge and Data Engineering, Vol. 8, Iss. 4, pp.533-539, 1996.
[20]M. Yeung, B. Liu and B.L. Yeo,“Extracting Story Units from Long Programs for Video Browsing and Navigation,”International Conference on Multimedia Computing and Systems (ICMCS), pp.296-305, 1996.
[21]	N. Beckmann, H.P. Kriegel, R. Schneider and B. Seeger, “The R*-tree: an Efficient and robust Access Method for Points and Rectangles,” ACM SIGMOD International Conference on Data Management, pp.323-331, 1990.
[22]N. Dimitrova and F. Golshani,“Rx for Semantic Video Database Retrieval,”ACM Multimedia, pp.219-226, 1994.
[23]	P.H. Sellers, “The Theory and Computation of Evolutionary Distance: Pattern Recognition,” Journal of Algorithms, Vol. 1, No. 4, pp.359-373, 1980.
[24]	P. Rigaux, M. Scholl and A. Voisard, “Spatial Databases with Application to GIS,” Morgan Kaufmann, 2001.
[25]	P.W. Huang and C.H. Lee, “Image Database Design Based on 9D-SPA Representation for Spatial Relations,” IEEE Transaction on Knowledge and Data Engineering, Vol. 16, No. 12, pp.1486-1496, 2004.
[26]	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.
[27]	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. 9, Iss. 3, pp.413-428, 1987.
[28]	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.
[29]	S.Y. Lee, M.K. Shan and W. P. Yang, “Similarity Retrieval of Iconic Image Database,” Pattern Recognition, Vol. 22, No. 6, pp.675-682, 1989.
[30]	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.
[31]	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, 1992.
[32]	T. Arndt and S.K. Chang, “Image Sequence Compression by Iconic Indexing,” IEEE Workshop on Visual Languages, pp.177-182, 1989.
[33]	T.C.T. Kuo and A.L.P. Chen, “Content-Based Query Processing for Video Databases,” IEEE Transaction on Multimedia, Vol. 2, Iss. 1, pp.1-13, 2000.
[34]	T. Sellis, N. Roussopoulos, and C. Faloutsos, “The R+-Tree: A Dynamic Index for Multidimensional Objects,” The 13th International Conference on Very Large Databases (VLDB), pp.507-518, 1987.