[[alternative]]Spatial similarity retrieval of videos based on the movements of objects

碩士[[abstract]]基於內容的影片相似尋取(Content-Based Video Retrieval)是一種處理影片資料較合適的解決方法之一。然而隨著影片資料量越來越龐大，複雜性也越來越高。因此如何在大量的資料中進行影片尋取，儼然成為一個重要議題。 在先前許多影片相似尋取的研究中，根據影像中物件之空間關係計算查詢影片中之影像與參考影片中之影像的相似度，並以此做為計算查詢影片與參考影片相似程度之基礎，然而此種方法並未明確考慮到在連續影格間物件間空間關係的變化及物件的移動方向。 然而在影片中，在兩相鄰影格間因物件移動而造成空間關係變化及其移動方向之資訊是重要的。因此，在本論文中我們提出如何根據在兩相鄰影格之間物件間空間關係之變化，以及物件移動方向之變化計算相似度之方法，並以此作為影片相似尋取之依據。如此一來，即可進行以影格間之物件移動資訊作為條件之查詢。[[abstract]]Content-based video retrieval is an appropriate solution for retrieving video data. However, there are more and more video data and the task of video retrieval becomes more complicated. Therefore, how to perform video retrieval in the large amount of data is a critical issue. In the previous research, the similarity between the query video and the reference video is based on the similarity between the images of query video and that of reference video. As a result, the change of spatial relation between objects in the video and the moving direction of the objects are not considered in this approach. However, it is important because object movement between two continuous frames will cause the change of spaital relation between objects and the moving direction of the objects in the video. In this paper, we propose the approach to calculate the similarity of the change of the spatial relation between objects and their moving direction between two continuous frames and use it as the basis of video similarity retrieval. Therefore, we can perform the similarity retrieval of video using the moving information of the objects between two continuous frames.[[tableofcontents]]目錄 第一章 緒論 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 2.4 影片相似尋取 10 I. 全序列比對(Full-sequence Matching) 10 II. 段比對(Segment Matching) 10 III. 子序列比對(Subsequence Matching) 11 第三章 研究方法 15 3.1 建立位移區段及移動向量組 15 3.2 七十五種物件對間移動向量之空間關係 18 3.3移動向量組相似度之評量 22 3.3.1 移動向量對的空間關係距離之計算 22 3.3.2移動向量的移動方向距離之計算 30 3.3.3 計算移動向量組之距離 32 3.4 影片相似尋取方法 34 3.5影片相似尋取範例 38 第四章 實驗與分析 43 4.1 系統說明 45 4.2 影片查詢 48 4.2.1 z=q之情形的尋取範例 49 4.2.2 z>q之情形的尋取範例 50 4.3 實驗分析 52 第五章 結論 55 參考文獻 56 圖目錄 圖 1、2D String範例及其表示法 6 圖 2、2D B-String表示法之範例 8 圖 3、一維空間上物件對的13種空間關係 9 圖 4、三種影片尋取方法之架構 13 圖 5、Type-0、1、2子序列比對示意圖 14 圖 6、物件投影至x軸及y軸之字串範例 16 圖 7、物件A之位移區段 17 圖 8、物件A於Frame i及Frame i+1之移動情形 17 圖 9、物件A之移動向量 18 圖 10、MVSx之範例 18 圖 11、兩物件在一維空間上位移區段之移動空間關係 20 圖 12、在一維空間上某物件不移動之位移區段空間關係 21 圖 13、範例影片 23 圖 14、物件對AB於某一影格中可能的空間關係距離圖 23 圖 15、MVSx相似尋取範例說明1 25 圖 16、MVSx相似尋取範例說明2 27 圖 17、MVSx P與S間距離之計算過程 28 圖 18、(向量A,向量B)之SRD圖 29 圖 19、在x軸上一物件移動方向調整過程之範例 31 圖 20、一物件於x軸及y軸移動方向之MDD圖 31 圖 21、計算兩個MVSx距離之範例 33 圖 22、U和V之MBF match之情形 37 圖 23、查詢MBF序列 39 圖 24、參考影片MBF序列 40 圖 25、尋取結果1 40 圖 26、尋取結果2 41 圖 27、系統中四條虛擬邊線與得分線示意圖 44 圖 28、兩個擊球盤與曲棍球之物件標示示意圖 45 圖 29、系統畫面1 46 圖 30、系統畫面2 48 圖 31、查詢MBF序列 50 圖 32、z=q之情形的相似尋取結果之一 50 圖 33、z>q之情形的相似尋取結果之一 52 表目錄 表 1、2D C-string空間運算子的定義 9 表 2、(向量A,向量B)之起始點與結束點可能的空間關係表 26 表 3、u1與v1~v7之尋取過程 41 表 4、u2與v1~v7之尋取過程 42 表 5、各實驗與各門檻值之D、E、F對照表 53 表 6、各實驗之準確率及召回率對照表 54[[note]]學號: 600630114, 學年度: 10