李瑞庭臺灣大學:資訊管理學研究所洪瑞文Hong, Ruey-WenRuey-WenHong2010-05-052018-06-292010-05-052018-06-292009U0001-1401200900255100http://ntur.lib.ntu.edu.tw//handle/246246/179934近年來，由於影像及視訊資料的快速成長，如何從大量的影像及視訊資料中，獲取有用的資訊，愈來愈受到重視。本論文針對影像及視訊資料庫，提出三種探勘頻繁樣式的演算法，分別稱為9DLT-Miner、2DZ-Miner及3DZ-Closed。其中9DLT-Miner是從9DLT影像資料庫中探勘頻繁空間樣式；2DZ-Miner是從2DZ影像資料庫中探勘頻繁空間樣式；3DZ-Closed則是從3DZ視訊資料庫中探勘頻繁封閉性時空樣式。9DLT-Miner及2DZ-Miner演算法中，我們除了運用Apriori演算法提出之反單調修剪原則，修剪不可能的候選樣式外，並針對9DLT及2DZ影像資料表示法的特性，各提出一個關係查詢表。透過關係查詢表，我們可以在探勘過程有效刪除不可能的候選樣式。DZ-Closed演算法使用「樣式索引」(pattern index)及「樣式索引樹」(pattern index tree)資料結構，探勘3DZ視訊資料庫中頻繁封閉性時空樣式。3DZ-Closed演算法除延伸2DZ-Miner演算法中關係查詢表的修剪方法，並提出「多檢查一層」(one-level-ahead checking)的修剪策略，可有效地在樣式索引樹中標示不須延展的節點，進而刪除該節點下不必要的分支，減少耗時的候選樣式產生時間。相較於Apriori-like演算法，實驗結果顯示，9DLT-Miner演算法、2DZ-Miner演算法及3DZ-Closed演算法的執行效率均優於Apriori-like演算法。Because of fast growth in the volume of image and video data, how to get useful information from image and video databases has attracted more and more attention in recent years. In this dissertation, we propose three algorithms, 9DLT-Miner, 2DZ-Miner, and 3DZ-Closed algorithms. The 9DLT-Miner algorithm is to find the frequent spatial patterns in 9DLT image databases. The 2DZ-Miner algorithm is to find the frequent spatial patterns in 2DZ image databases. The 3DZ-Closed algorithm is to find the frequent closed spatial-temporal patterns in 3DZ video databases.In the 9DLT-Miner and 2DZ-Miner algorithms, in addition to using the anti-monotone pruning strategy to prune impossible candidate patterns, we utilize the characteristics of the 9DLT and 2DZ-string representations to design the relation inference matrices respectively. By using the inference matrices, we prune most impossible candidate patterns. he 3DZ-Closed algorithm uses the pattern index and pattern index tree to mine all frequent closed spatial-temporal patterns in 3DZ video databases. In the 3DZ-Closed algorithm, we not only use the 2DZ relation inference matrix to prune impossible candidate patterns, we also propose a “one-level-ahead checking” pruning strategy, which can mark the non-expandable nodes in the pattern index tree. Therefore, the 3DZ-Closed algorithm can effectively prune the unnecessary branch nodes in the pattern index tree and avoid the costly candidate generation. The experimental results show that the 9DLT-Miner, 2DZ-Miner and 3DZ-Closed algorithms outperform the Apriori-like algorithms.論文摘要 iiiissertation Abstract ivable of Contents vist of Figures viist of Tables viiihapter 1 Introduction 1.1 Motivations 1.2 Contributions 7.3 Dissertation layout 8hapter 2 Background and Literature Survey 10.1 Knowledge structures for image and video databases 10.2 Frequent itemsets mining 16.3 Frequent closed itemsets mining 17.4 Spatial pattern mining and image mining 19.5 Spatial-temporal pattern mining and video mining 20.6 Discussion 21hapter 3 Mining Frequent Directional Patterns in 9DLT Image Databases 24.1 Preliminaries and problem definitions 24.2 Pruning strategies 31.3 Mining frequent directional patterns 31.4 An example 35hapter 4 Mining Frequent Positional Patterns in 2DZ Image Databases 39.1 Preliminaries and problem definitions 39.2 Pruning strategies 46.3 Mining frequent positional patterns 47.4 An example 51hapter 5 Mining Frequent Closed Spatial-Temporal Patterns in 3DZ Video Databases 56.1 Preliminaries and problem definitions 56.2 Pruning strategies 66.3 Mining frequent closed spatial-temporal patterns 69.4 An example 72hapter 6 Performance Analysis 77.1 Synthetic data 77.2 Real data 89hapter 7 Conclusions and Future Work 97eferences 100application/pdf1326683 bytesapplication/pdfen-US頻繁樣式探勘空間樣式時空樣式影像探勘視訊探勘Frequent pattern miningspatial patternspatial-temporal patternimage miningvideo mininghttp://ntur.lib.ntu.edu.tw/bitstream/246246/179934/1/ntu-98-D90725004-1.pdf