請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41777
標題: | 影像及視訊資料庫之頻繁樣式探勘 Mining Frequent Patterns in Image and Video Databases |
作者: | Ruey-Wen Hong 洪瑞文 |
指導教授: | 李瑞庭 |
關鍵字: | 頻繁樣式探勘,空間樣式,時空樣式,影像探勘,視訊探勘, Frequent pattern mining,spatial pattern,spatial-temporal pattern,image mining,video mining, |
出版年 : | 2009 |
學位: | 博士 |
摘要: | 近年來,由於影像及視訊資料的快速成長,如何從大量的影像及視訊資料中,獲取有用的資訊,愈來愈受到重視。本論文針對影像及視訊資料庫,提出三種探勘頻繁樣式的演算法,分別稱為9DLT-Miner、2DZ-Miner及3DZ-Closed。其中9DLT-Miner是從9DLT影像資料庫中探勘頻繁空間樣式;2DZ-Miner是從2DZ影像資料庫中探勘頻繁空間樣式;3DZ-Closed則是從3DZ視訊資料庫中探勘頻繁封閉性時空樣式。
在9DLT-Miner及2DZ-Miner演算法中,我們除了運用Apriori演算法提出之反單調修剪原則,修剪不可能的候選樣式外,並針對9DLT及2DZ影像資料表示法的特性,各提出一個關係查詢表。透過關係查詢表,我們可以在探勘過程有效刪除不可能的候選樣式。 3DZ-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. The 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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41777 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊管理學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-98-1.pdf 目前未授權公開取用 | 1.3 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。