在影像資料庫中基於內容的相似影像尋取(Content-Based Image Retrieval，CBIR)是一個查詢影像的重要方法。物件之間的空間關係(spatial relation)是影像的重要特性之一。利用字串表示影像中物件之間的空間關係，以及利用空間關係進行空間推論及相似尋取之方法已被廣泛的討論。
影片中每一個畫面都可以視為一個靜態的影像，我們可以利用2D B-string表示每一個畫面中物件間的空間關係。在影片中前後的二個畫面往往差異都不大，為了有效減少重覆的字串，本論文利用字串比對的三種編輯運算表達相鄰的二個畫面 2D B-string改變的部份，藉此縮短每個frame字串的長度，達到影片壓縮的效果，而且也能還原為原來的2D B-string。

In image database systems, Content-Based Image Retrieval (CBIR) is an important approach to image query. The spatial relationship between objects is one of the important features of the image. How to use strings to express the spatial relationship between objects and how to perform the inference and similarity retrieval have been widely discussed.
Because every frame in the video is a picture, we can use 2D B-string to describe the spatial relationship between objects in the frame. The difference between adjacent frames is not much. To reduce the repetition in the strings, we use the tree kinds of edit operations in string matching to record the difference between the 2D B-strings of adjacent frames. As a result, the length of the string can be reduced and the goal of compression can be reached. The original 2D B-string can be also recovered.

第一章	緒論	1
1.1	研究背景	1
1.2	研究動機	2
1.3	研究目的	3
1.4	論文架構	4
第二章	相關研究	5
2.1	2D strings簡介	5
2.2	2D B-string簡介	7
2.3	字串比對	8
第三章	運用編輯運算字串壓縮影像及還原	17
第四章	實驗與分析	22
第五章	結論與未來研究方向	44
參考文獻	46

圖一、2D strings範例及其表示法	6
圖二、2D B-string之範例	7
圖三、影片範例	20
圖四、實驗一之影片	28
圖五、實驗二之影片	41

表一、編輯成本表初始化之範例	13
表二、求的D[1,1]三個路徑之範例	13
表三、求的D[1,2]三個路徑之範例	13
表四、編輯成本表	13
表五、最小成本路徑表示	16
表六、實驗一及實驗二之數據	42

[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, Oct. 1989, pp. 177-182.
[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, May 1987, pp.413-428.
[3]Sagarmay Deb, “Video Data Management and Information Retrieval,” Idea Group Inc. 2005.
[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, Sept. 1995, pp. 23-32.
[5]P.W. Huang and Y.R. Jean, “Spatial reasoning and similarity retrieval for image database system based on RS-strings,” Pattern Recognition, 1996, pp.2103-2114
[6]P.W. Huang and Y.R. Jean, “Using 2D C+-string as spatial knowledge representation for image database systems,” Pattern Recognition, 1994, pp.1249-1257.
[7]P. W. Huang and C. H. Lee, “Image Database Design Based on 9D-SPA Representation for Spatial Relations,” IEEE Trans. on Knowledge and Data Engineering, vol. 16, no. 12, 2004.
[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, March 1992, pp. 305-318.
[9]F. J. Hsu and S.Y. Lee, “Similarity Retrieval by 2D C-Trees Matching In Image Database,” Journal of Visual Communication And Image Representation Vol.9, No. 1, March, 1998,pp.87-100.
[10]S. Y. Lee, M. C. Yang and J. W. Chen ,”2D B-string: a spatial knowledge representation for image database systems,” Proc.ICSC’92 Second Int. Computer Sci. Conf.,1992,pp.609-615.
[11]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.
[12]M. Nabil, A.H.H. Ngu, and J. Shepherd, “Picture Similarity Retrieval Using the 2D Projection Interval Representation,” IEEE Trans. Knowledge and Data Eng., vol. 8, no. 4, Aug. 1996, pp. 533-539.
[13]J. R. Smith and S. F. Chang, “VisualSEEK: A Full Automated Content-Based Image Query System,” Proc. Fourth ACM Int’l Multimedia Conf. , 1996, pp. 87-98.
[14]K. R. Shearer, S. Venkatesh, and D. Kieronska, “Spatial Indexing for Video Databases,” J. Visual Commun. Image Representation, vol. 7, 1996 , pp. 325-335.
[15]K. R. Shearer, D. Kieronska, and S. Venkatesh, “Resequencing Video Using Spatial Indexing,” J. Visual Languages Comput., vol. 8, 1997, pp. 193-214.
[16]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.
[17]H. Tamura and N. Yokoya, “Image database systems: a survey,” Pattern Recognition, Vol. 17, NO. 1, 1984, pp.29-43.
[18]R. A. Wagner and M. J. Fischer, “The String-to-String Correction Problem,” Journal of the Association for computing Machinery, Vol. 21, No. 1, January 1974, pp.168-173.
[19]陳彥睿、梁恩輝，「影片以空間關係字串表示之壓縮」，2009 資訊科技國際研討會，朝陽科技大學資訊學院。