9DLT影片資料庫中頻繁樣式之資料探勘

Abstract

隨著影音設備、數位相機、網路的盛行，多媒體資料系統也變得愈來愈受歡迎。因此，如何從一個影片資料庫中找出頻繁樣式越來越受到矚目。在本篇論文中，我們提出了一個有效率的探勘演算法「FVP-Miner」，用來找出影片資料庫中的頻繁樣式。演算法主要可分為兩個階段。第一階段，我們將每一段影片轉換成9DLT字串。第二階段，我們先找出所有長度為2的影像頻繁樣式，接著再對這些頻繁樣式作空間和時間上兩個維度的成長以找出所有的頻繁樣式。我們應用了三個修剪技巧和投影資料庫以去除不可能的候選樣式和加速演算法。因此，我們所提出的演算法可以有效率地在影片資料庫中找出頻繁樣式。實驗結果顯示，不管在合成資料或真實資料中，我們所提出的方法皆比改良式的Apriori演算法更有效率與擴充性。

Multimedia database systems are becoming increasingly popular owing to the widespread use of audio-video equipment, digital cameras, CD-ROMs, and the Internet. Therefore, mining frequent patterns from video databases has attracted increasing attention in recent years. In this thesis, we proposed a novel algorithm, FVP-Miner (Frequent Video Pattern Miner), to mine frequent patterns in a video database. Our proposed algorithm consists of two phases. First, we transform every video into 9DLT strings. Second, we find all frequent image 2-patterns from the database and then recursively mine the frequent patterns in the spatial and temporal dimension. We employ three pruning strategies to prune many impossible candidates, and the concept of projected database to localize the support counting, pattern joining, and candidate pruning on the projected database. Therefore, our proposed algorithm can efficiently mine the frequent patterns in a video database. The experiment results show that our proposed method is efficient and scalable, and outperforms the modified Apriori algorithm in several orders of magnitude.