在影像資料庫中基於內容的相似影像尋取(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.
