Mining Closed Patterns in Pointset Video Databases

隨著多媒體影像技術的蓬勃發展，多媒體資料量快速地遽增，如何從龐大的多媒體資料中找到有意義的資訊和特性已成為熱門的研究議題。我們可以將影片中發生的一個事件視為一個連續的點集合，而找到影片資料庫中由點集合所構成的封閉性樣式，則可以表達出影片中發生該事件的特性。因此，在本論文中，我們提出一個有效率的探勘演算法「CVP」來探勘出影片資料庫中的封閉性樣式。我們所提出的演算法主要先利用兩種資料結構儲存頻繁樣式的資訊，以深度優先搜尋的方式先對空間維度、再對時間維度產生出可能的頻繁樣式，最後再利用我們所提出的方法來修剪不符合或不必要的樣式以及判斷其封閉性。我們的演算法利用投影資料庫去產生可能的樣式和進行修剪，並不需要重複地搜尋整個影片資料庫，因此效率能夠得到明顯的改善。在人造及真實資料庫的實驗結果中顯示我們所提出的方法較改良式Apriori的方法來得更有效率。Nowadays, the number of multimedia datasets is increasing rapidly. Thus, mining implicit and meaningful patterns from multimedia databases has attracted more and more attention in recent years. The event object can be viewed as a sequence of pointsets in a video. Mining closed patterns in pointset video databases can help us understand the pattern of an event in video databases. In this thesis, we first devise two data structures, called rplist and CV-tree, to store the information of frequent video patterns. Next, we propose a novel algorithm, called CVP, to mine frequent closed patterns from a video database in a depth-first search (DFS) manner. Our proposed algorithm consists of two phases. We first grow frequent video patterns in the spatial dimension and then grow them in the temporal dimension. To efficiently mine frequent closed patterns, we develop several pruning strategies to prune non-closed patterns. The CVP algorithm can localize the candidate generation, pattern join, and support counting in a small amount of rplists. Therefore, it can efficiently mine frequent closed patterns in a video database. The experiment results show that our proposed method outperforms modified Apriori algorithm in synthetic data and real data.Table of Contents iist of Figures iiist of Tables iiihapter 1 Introduction 4hapter 2 Preliminaries and Problem Definitions 8hapter 3 Our Proposed Method 12.1 Rplist and CV-tree 12.2 Pattern generation 14.3 Closure checking and pruning strategies 21.4 The CVP algorithm 25.5 An example 29hapter 4 Performance Evaluation 33.1 Synthetic datasets 34.2 Performance evaluation on synthetic datasets 34.3 Performance evaluation on real datasets 38hapter 5 Conclusions and Future work 41eferences 4