[[alternative]]Video retrieval based on the similarity between spatial event strings

碩士[[abstract]]一個影片的內容可以視為一連串的影格，而每一個影格可以經由轉換以一個符號影像(symbolic image)來表示。在先前許多相關的研究中，根據符號影像中物件間空間關係之影片相似尋取是一個影片尋取的重要方法。然而，此方法並未明確的考慮到物件在影片中相鄰影格間的空間關係變化及移動資訊。 在本論文中，我們定義在相鄰影格間，因各物件不同的移動向量所發生空間關係的變化稱為空間事件(Spatial Event)。當多個空間事件同時發生時，以字串的方式表示，稱為空間事件字串(Spatial Event String, 簡稱SES)。我們提出計算兩SES間之相似度方法。將查詢的SES序列與參考影片之SES序列做比較，並根據SES間之相似度，我們提出在參考影片之SES序列中找出與查詢影片相似的片段的方法。因此，即可進行以空間事件為基礎的影片相似尋取。[[abstract]]A video can be viewed as a sequence of frames. Each frame can be transformed into a symbolic image. In the previous research, similarity retrieval of video based on the spatial relationship between objects in the symbolic image is an important method. The change of the spatial relationship between objects and the information about the movement of the objects in the video are not considered directly and precisely. In this paper, the spatial event is defined as the change of the spatial relationship between objects due to the movements of the objects from a frame to its next. When multiple events occur, the spatial events are represented as a string, named the spatial event string (SES). We propose a method to calculate the similarity between two SESs. Similarity retrieval of video can be performed by comparing the query SES sequence with the SES sequence of the reference video. We proposed a method to locate the segment in the reference video similar to the query SES sequence based on the similarity between SESs. Hence, Similarity retrieval of video based on spatial events can be performed.[[tableofcontents]]目錄 中文論文提要 I 英文論文提要 II 目錄 III 表目錄 V 圖目錄 VI 第一章 緒論 1 1.1 研究動機與目的 1 1.2 論文架構 4 第二章 相關研究 5 第三章 研究方法 13 3.1 序值及六種空間關係的變化 13 3.2 空間事件與空間事件字串 18 3.3 空間事件字串間之相似度 24 3.4 影片相似尋取 24 3.5 影片尋取範例 26 3.5.1 z = m之尋取範例 27 3.5.2 z > m之尋取範例 28 第四章 實驗與分析 30 4.1 z = m之影片相似尋取 32 4.2 z > m之影片相似尋取 39 4.3 執行時間 46 第五章 結論 49 參考文獻 50 表目錄 表 2 1：2D C-String空間運算子的定義 8 表 2 2：圖2-2中各物件於X軸及Y軸中的序值 9 表 3 1：六種空間關係的變化 17 表 3 2：z = m方法的參考SES子序列 28 表 3 3：z > m方法的參考SES子序列 29 表 4 1：各組實驗設定值及需比對子序列數 46 表 4 2：各組實驗比對所有子序列所需執行時間 47 表 4 3：各組實驗平均比對一個子序列所需執行時間 48 圖目錄 圖 2 1：一維空間中物件對的13種空間關係 7 圖 2 2：2D B-String表示法之範例 9 圖 2 3：過去研究中影格序列的匹配方法 12 圖 2 4：本論文關注於物件間在連續影格中的空間關係變化 12 圖 3 1：範例符號圖 15 圖 3 2：物件於兩相鄰畫面中移動之情形 16 圖 3 3：物件於frame i及frame i+1 之位置 18 圖 3 4：圖3-3中物件由frame i移動至frame i+1之移動向量 19 圖 3 5：圖3-3中物件於X軸之移動向量 19 圖 3 6：圖3-3中物件於Y軸之移動向量 20 圖 3 7：範例相鄰影格 20 圖 3 8：物件對AB可能發生空間關係變化1之情形 21 圖 3 9：30種空間事件 22 圖 3 10：範例影片 23 圖 3 11：查詢範例影片 27 圖 4 1：兩個擊球盤與曲棍球等物件之示意圖 31 圖 4 2：判斷發生空間事件之物件參考點 31 圖 4 3：z = m = 2之情形之查詢影片 33 圖 4 4：z = m = 2之情形之相似尋取結果 34 圖 4 5：z = m = 3之查詢影片 35 圖 4 6：z = m = 3之相似尋取結果 36 圖 4 7：z = m = 4之查詢影片 37 圖 4 8：z = m = 4之相似尋取結果 38 圖 4 9：z = 4、m = 2之查詢影片 40 圖 4 10：z = 4、m = 2之相似尋取結果 41 圖 4 11：z = 5、m = 3之查詢影片 42 圖 4 12：z = 5、m = 3之相似尋取結果 43 圖 4 13：z = 6、m = 4之查詢影片 44 圖 4 14：z = 6、m = 4之相似尋取結果 45[[note]]學號: 602630021, 學年度: 10