在影像資料庫中基於內容的影像尋取是一個查詢影像的重要方法。利用字串表示影像中物件之間的空間關係，以及利用空間關係進行空間推論及相似尋取之方法已被廣泛的討論。 
本論文利用2D B-string的概念表示影片中一段時間內物件間移動的空間關係。假設物件在空間上是以MBR之中心點表示，需標記每個物件於此段影片的「啟始位置」和「結束位置」，並由啟始位置到結束位置之間定義成一個區段，稱之為此段影片中該物件的「位移區段」。將根據物件的位移區段，利用2D B-string的概念來建立一個新的字串稱為「2D M-string」，此時的字串就能表達出在該段影片中，物件彼此之間移動的空間關係。以本論文提出之2D M-String來空間推論和利用索引結構進行搜尋時，能大量過濾較不相似之影片片段，減少字串比對的次數，增加尋取的效能，藉此將可達到有效率地影片查詢之目的。

In image database systems, Content-Based Image Retrieval (CBIR) is an important approach to image retrieval. How to use strings to express the spatial relationship between objects and how to perform the inference and similarity retrieval have been widely discussed. 
The concept of 2D B-string notation is used to indicate the moving spatial relationship between objects in a video. Each object is represented as a focal point, and the point is marked in the "initiation position" and "end position" of each object of the video. A section from the point in the "initiation position" to the point in the "end position" is defined as the “displacement” of the object in the video. The 2D M-string is created based on the displacement of the objects in the video. The 2D M-String to spatial reasoning and search using the index structure can be a lot less similar to the filter clips to reduce the number of string matching and the efficient retrieval of similar video can be achieved.

目錄
第一章 緒論 ............................................. 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
第三章 研究方法 ........................................ 10
   3.1 建立位移區段 .................................... 10
   3.2 依位移區段建立2D M-String ....................... 12
   3.3 以2D M-String建立索引結構 ....................... 23
   3.4 影片相似查詢 .................................... 27
第四章 實驗結果 ........................................ 33
第五章 結論 ............................................ 40
參考文獻 ............................................... 42

圖目錄
圖2-1　2D String表示法之範例..............................6
圖2-2　2D B-string表示法之範例............................8
圖3-1　範例影片..........................................11
圖3-2　位移區段圖及2D M-string...........................12
圖3-3　考慮位移區段之方向性..............................15
圖3-4　監視行人移動影片之擷圖............................23
圖3-5　監視行人移動影片之2D M u-string...................25
圖3-6　監視行人移動影片之位移區段圖......................26
圖3-7　監視行人移動影片之索引結構........................26
圖3-8　查詢條件之隧道超車位移區段圖......................27
圖3-9　隧道超車影片之擷圖................................28
圖3-10　隧道超車影片之索引結構...........................29
圖3-11　影片查詢之演算法.................................32
圖4-1　查詢條件之烏山頭路段超車位移區段圖................33
圖4-2　烏山頭路段超車影片之擷圖..........................34
圖4-3　標示物件MBR之中心點...............................35
圖4-4　建立烏山頭路段超車影片之索引結構..................35
圖4-5　影片相似尋取之介面................................36
圖4-6　手繪之位移區段圖..................................36

表目錄
表2-1　2D C-String空間運算子的定義........................9
表3-1　兩物件在一維空間上位移區段之移動空間關係..........14
表3-2　五十二種移動空間關係之隱含關係....................17
表3-3　在一維空間上物件不移動之空間關係..................18
表3-4　二十三種移動空間關係之隱含關係....................21
表3-5　五十二種移動空間關係考慮物件不移動的隱含關係......22
表4-1　使用本論文方法查詢影片的結果......................38

[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] A. J. T. Lee and H.P. Chiu, "2D Z-string: A new spatial knowledge representation for image databases," Pattern Recognition Letters Vol. 24, pp. 3015-3026, 2003.
[12] 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.
[13] 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.
[14] H. C. Lin, L. L. Wang and S. N. Yang, “Color image retrieval based on hidden Markov models,” IEEE Transactions on Image Processing, Vol. 6, No. 2, 1997.
[15] 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.
[16] 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.
[17] 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.
[18] D. Sagarmay, Z. Yanchun, "An Overview of Content-based Image Retrieval Techniques," aina, Vol. 01, No. 1, p. 59, 18th 2004.
[19] H. Tamura and N. Yokoya, “Image database systems: a survey,”Pattern Recognition, Vol. 17, NO. 1, pp.29-43, 1984.