影片由一連串連續畫面組成，一個畫面中皆可能有多的物件。在單一畫面中，只包含了在此畫面中物件之間的空間關係的資訊，無法表示影片中物件間空間關係的變化。在本論文中，我們定義在兩個相鄰畫面間物件之間空間關係發生變化稱為空間事件，並提出一個表示這些空間事件的字串，稱為空間事件字串。因此，可以根據此字串推論出影片中物件間的空間關係的變化，使得根據空間事件的影片查詢能有效率得進行。我們提出產生空間事件字串的演算法及根據空間事件的進行影片查詢的方法。
此外，一般而言，在兩個連續畫面中發生空間事件的物件數量是相對的少數。由於在空間事件字串中，只需要記錄發生空間事件的物件而其他沒有產生空間關係變化的物件不必記錄，跟其他字串相比，如此可以大大減少字串的長度，減少字串資料的儲存的需求及處理的時間。

A video is composed of a sequence of frames.  A frame may contain multiple objects.  In a single frame, it contains the spatial relations between objects in this frame.  It does not have information about the change of the spatial relations between objects in the video.  In this paper, we define the occurrence of change of the spatial relations between objects between two adjacent frames as the spatial event and propose the spatial event string to represent the spatial event.  Hence, the change of the spatial relations between objects can be derived from this string and the video query based on spatial events can be processed efficiently.  We would propose the algorithm for the generation of the spatial event string and the way to process the video query based on spatial events.
Generally speaking, the number the objects involved in spatial events is relatively small.  Since the spatial event string contains only the objects involved in spatial events.  Compared with other strings, the length of the string can be reduced dramatically.  Consequently, the requirement of the storage and the process time of the string can be reduced.

目錄
第一章 緒論......................................	1
第二章 相關研究...................................	4
2.1 2D String..................................	4
2.2 2D B String................................	5
2.3 3D C-String................................ 7
第三章 空間事件字串的產生及其查詢....................	11
3.1 空間事件.....................................	11
3.2 合併字串.....................................	13
3.3 空間事件區段（Spatial Event Section）.........	15
3.4 空間事件字串（Spatial Event String, SES）.....	17
3.5 空間事件字串還原2D String.....................	27
3.6 空間事件字串查詢..............................	34
第四章 實驗與分析.................................	42
4.1 影片索引與查詢字串.............................	42
4.2 模擬真實賽車競速實驗...........................	43
4.3 真實游泳競賽實驗..............................	48
4.4 分析........................................	53
第五章 結論......................................	60
參考文獻.........................................	61

圖目錄
圖2-1 2D String範例.............................	5
圖2-2 2D B-String範例...........................	6
圖2-3 3D C-String範例...........................	8
圖3-1 空間事件範例影片............................	12
圖3-2 合併字串範例影片............................	14
圖3-3 空間事件區段範例影片.........................	16
圖3-4 物件在空間中位移範例.........................	19
圖3-5 空間事件字串性質一範例影片....................	20
圖3-6 空間事件字串性質二範例影片....................	22
圖3-7 空間事件字串推論2D String範例影片.............	30
圖3-8 空間事件字串查詢範例影片......................	37
圖3-9 空間事件字串之查詢空間事件....................	38
圖4-1 查詢條件之空間事件...........................	43
圖4-2 模擬賽車範例影片............................	44
圖4-3 第一組游泳競賽影片...........................	49


表目錄
表2-1 type-std定義表.............................	9
表3-1 空間事件字串查詢表...........................	39
表4-1 模擬真實路況超車之空間事件字串表................	44
表4-2 第一組游泳競賽影片之空間事件字串表..............	50
表4-3 第二組游泳競賽影片之空間事件字串表..............	50
表4-4 第三組游泳競賽影片之空間事件字串表..............	50
表4-5 第四組游泳競賽影片之空間事件字串表..............	51
表4-6 第五組游泳競賽影片之空間事件字串表..............	51
表4-7 第六組游泳競賽影片之空間事件字串表..............	52
表4-8 第七組游泳競賽影片之空間事件字串表..............	52
表4-9 第八組游泳競賽影片之空間事件字串表..............	52
表4-10 第九組游泳競賽影片之空間事件字串表.............	52
表4-11 第十組游泳競賽影片之空間事件字串表.............	53
表4-12 第十一組游泳競賽影片之空間事件字串表........... 53
表4-13 空間需要比較表.............................	56

[1] Chang, S.K., Shi, Q.Y., and Yan, C.W., ”Iconic indexing by 2D-strings”, IEEE Trans. On Pattern Analysis and Matching Intelligence, PAMI-9, pp.413-428, May 1987. 
[2] Flickner, M., Sawhney, H., Niblack, W., Ashley, J., Huang, Q., Dom, B., Gorkani, M., Hafner, J., Lee, D., Petkovic, D., Streele, D., and Yanker, P., “Query by Image and Video Content: The QBIC System”, Computer, vol.28, no.9, pp.23-32, Sept. 1995. 
[3] Hsu, F. J., and Lee, S.Y., “Spatial Reasoning and Similarity Retrieval of Images Using 2D C-String Knowledge Representation”, Pattern Recognition, vol.25, no.3, pp.305-318, March 1992. 
[4] Hsu, F.J., and Lee. S.Y., “Similarity Retrieval by 2D C-Trees Matching In Image Database”, Journal of Visual Communication And Image Representation Vol.9, No.1, pp.87-100, March 1998. 
[5] Huang, P.W., and Lee, C.H., “Image Database Design Based on 9D-SPA Representation for Spatial Relations”, IEEE Trans. on Knowledge and Data Engineering, vol.16, no.12, 2004. 
[6] J.T. Lee∗, Han-Pang Chiu, Ping Yu, “3D C-string:a new spatio-temporal knowledge representation for video database systems”, Pattern Recognition, vol.35, pp.2521–2537,2002.
[7] Nabil, M., Ngu, A.H.H., and Shepherd, J., “Picture Similarity Retrieval Using the 2D Projection Interval Representation”, IEEE Trans. Knowledge and Data Eng., vol.8, no.4, pp.533-539, Aug. 1996. 
[8] Shearer, K.R., Venkatesh, S., and Kieronska, D., “Spatial Indexing for Video Databases”, J. Visual Commun. Image Representation, vol.7, pp.325-335, 1996. 
[9] Shearer, K.R., Kieronska, D., and Venkatesh, S., “Resequencing Video Using Spatial Indexing”, J. Visual Languages Comput., vol.8, pp.193-214, 1997. 
[10] Smith, J.R., and Chang, S.F., “VisualSEEK: A Full Automated Content-Based Image Query System”, Proc. Fourth ACM Int’l Multimedia Conf., pp.87-98, 1996.