以編號矩陣為基礎之相似視訊擷取方法

近年來，由於資訊科技及設備的普及，到處充滿了多媒體資料，包含文字、聲音、圖片以及影片。因此，我們需要一個自動化的工具來幫助使用者從浩翰的資料庫中找尋感興趣的資料。過去，張玉盈教授提出UID matrix的知識結構來代表一張圖片，這樣的知識結構記錄的是一張圖片中任何兩個物件在空間上的相對關係，但是卻沒有記錄物件的大小及位置，而且此方法還不能運用到視訊上。李瑞庭教授等人所提出的3D C-string雖然可以應用至視訊上，也有記錄物件的大小及位置，但其相似度比對的演算法所花的時間複雜度很高。因此，我們在本篇論文中提出了一個新的知識結構以及新的相似度比對的演算法，是以UID matrix的觀念為基礎，也就是我們把UID matrix方法延伸至視訊中，可以針對一部視訊產生相對應的矩陣以記錄的物件的大小，位置及物件的空間關係。稱做以編號為基礎的視訊矩陣（Unique-ID-based Video matrix），簡稱UV-matrix。這個新的方法主要分成兩個階段。第一個階段，是針對一部視訊產生一系列的矩陣。第二個階段，基於這些矩陣，針對一個查詢視訊，我們可以利用一些簡單的矩陣運算來達成視訊的相似度比對。由於我們的方法是利用一些簡單的矩陣運算來達成視訊的相似度比對，因此，與3D C-string方法相比，我們的時間複雜度顯得比較低。在相似度比對的衡量方面，我們也提出了17種不同型態的查詢方式以供使用者可以根據其需求來對資料庫的視訊檢索及擷取所需要的視訊。最後，我們可以從實驗的結果得知UV-matrix的效率及有效性，同時我們也對3D C-string方法和UV-matrix方法的效能做了比較。

關鍵字

視訊檢索；視訊資料庫； UV-matrix ； UID matrix ； 3D C-string

並列摘要

In this thesis, we propose a new similarity retrieval method called Unique-ID-based Video matrix (UV-matrix) to represent a symbolic video and to retrieve the videos similar to a given query video. We extended the idea behind the similarity retrieval of images in the UID matrix approach to the UV-matrix approach. Our proposed approach has two phases. First, we generate a sequence of matrices to represent the spatial relation between objects, sizes and locations of objects for a video. Second, based on these matrices, similarity retrieval can be performed by simple matrix operations from the video database for a given query video. According to our analysis, the time complexity of the UV-matrix approach is bounded by O(n2 ´ q ´ f), where n is the number of objects in a query, q is the number of frames in a query and f is the number of frames in a database video. In comparison with 3D C-string, the UV-matrix approach has less time complexity. We also define 17 types of similarity measures. By providing various types of similarity between videos, our proposed similarity retrieval algorithm can meet the different types of user’s need. Finally, some experiments are performed to compare the performance of the 3D C-string and the UV-matrix approach.

並列關鍵字

UV-matrix ； Video databases ； Similarity retrieval ； UID matrix ； 3D C-string

參考文獻

[1] S.K. Chang, Q.Y. Shi and C.W. Yan, Iconic indexing by 2D strings, IEEE Trans. On Pattern Analysis and Machine Intelligence 9 (5) (1987) 413-429.

[2] S.K. Chang, E. Jungert and Y. Li, Representation and retrieval of symbolic pictures using generalized 2D strings, Technical Report, University of Pittsburgh, 1988.

[3] Ye-In Chang, Hsing-Yen Ann, Wei-Horng Yeh, A unique-ID-based matrix strategy for efficient iconic indexing of symbolic pictures, Pattern Recognition 33 (2000) 1263-1276.

[4] P.W. Huang and Y.R. Jean, Using 2D C+-string as spatial knowledge representation for image database systems, Pattern Recognition 27 (1994) 1249-1257.

[5] P.W. Huang and Y.R.Jean, Spatial reasoning and similarity retrieval for image database systems based on RS-strings, Pattern Recognition 29 (1996) 2103-2114.

國際替代計量

以編號矩陣為基礎之相似視訊擷取方法

全文下載

主題瀏覽