透過您的圖書館登入
IP:3.80.24.244
  • 學位論文

影像及視訊資料庫之頻繁樣式探勘

Mining Frequent Patterns in Image and Video Databases

指導教授 : 李瑞庭

摘要


近年來,由於影像及視訊資料的快速成長,如何從大量的影像及視訊資料中,獲取有用的資訊,愈來愈受到重視。本論文針對影像及視訊資料庫,提出三種探勘頻繁樣式的演算法,分別稱為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.

參考文獻


[53] R. Ng., and J. Han, Efficient and effective clustering method for spatial data mining, In: Proceedings of International Conference on Very Large Data Bases, Morgan Kaufmann, San Francisco, CA, 1994, pp. 144-155.
[10] C. C. Chang, and S. Y. Lee, Retrieval of symbolic pictures, Journal of Information Science and Engineering, Vol. 7, No. 3, 1991, pp. 405-422.
[28] F. J. Hsu, S.Y. Lee, B.S. Lin, Video data indexing by 2D C-trees, Journal of Visual Languages and Computing, Vol. 9, No. 4, 1998, pp. 375-397.
[9] Y. K. Chan, and C. C. Chang, Spatial similarity retrieval in video databases, Journal of Visual Communication and Image Representation, Vol. 12, 2001, pp. 107-122.
[5] G. Bordogna, S. Chiesa, and D. Geneletti, Linguistic modelling of imperfect spatial information as a basis for simplifying spatial analysis, Information Sciences, Vol. 176, No. 4, 2006, pp. 366-389.

延伸閱讀