臺灣博碩士論文加值系統

近年來，隨著電腦科技的進步、資料儲存媒介容量的增加以及數位影像的普及，數位影像的資料量日益龐大。因此，影像內容檢索逐漸成為近年來重要的研究課題。在傳統的影像內容檢索技術中，使用影像低階特徵值的比對來判斷圖片間的相似度，並且利用關聯性回饋的技術來解決人類主觀意識與影像低階特徵值間的差異。雖然關聯性回饋的確可以有效增加查詢的準確度，但我們認為，如果能分析使用者的查詢行為並找到某些規則，將可以使查詢結果更符合使用者的需求。因此，我們將影像內容檢索結合資料探勘的技術，透過查詢日誌的分析，找出圖片與圖片間的關聯性以及特徵值與特徵值權重的關係，並將這些找到規則整合到影像內容檢索系統中。實驗結果顯示，採用我們所提出的方法，在相同回饋次數的條件下約能增10%的準確度，也就是說，我們能在較少的回饋次數中獲得較佳的結果。

In recent years, due to the rapid progress of computer science, the improved storage techniques and popularity of digital images, content-based image retrieval (CBIR) has gradually become an important issue for multimedia processing. In order to increase the precision of image retrieval, the methods of relevance feedback arise to complement traditional CBIR systems that concentrate only on the computation of similarity among images. In this research, we utilize the association rules mining methods to satisfy the requests from different users by analyzing users' behavior during the whole retrieval procedure. Accordingly, we combine the image content and usage log to discover the useful association rules and the feature weights are adjusted dynamically for the relevant image feedback. Through experimental evaluation, our proposed approach is shown to deliver significant improvement on retrieval precision. That is to say, better retrieval results can be provided for users by our approach with less numbers of feedback.

<font face="Courier New"><font face="細明體">英文摘要..............................................I
中文摘要............................................III
致謝.................................................IV
目錄..................................................V
表目錄...............................................IX
圖目錄................................................X

第一章　導論..........................................1
　1.1　研究目的.......................................1
　　1.1.1　研究背景...................................1
　　1.1.2　研究動機...................................2
　　1.1.3　問題描述...................................2
　1.2　研究方法.......................................4
　1.3　研究貢獻.......................................6
　1.4　論文架構.......................................6

第二章　文獻探討......................................7
　2.1　影像低階特徵...................................7
　　2.1.1　色彩佈局 (Color Layout)....................8
　　2.1.2　可調色彩 (Scalable Color)..................8
　　2.1.3　顏色結構 (Color Structure).................9
　　2.1.4　齊次性紋理 (Homogeneous Texture)...........9
　　2.1.5　邊界直方圖 (Edge Histogram)...............10
　　2.1.6　區域形狀 (Region Shape)...................10
　2.2　影像內容檢索(Content-Based Image Retrieval)...11
　　2.2.1　影像檢索技術..............................11
　　2.2.2　影像相似度比對............................12
　　2.2.3　關聯性回饋 (Relevance Feedback)...........14
　　2.2.4　特徵值權重調整............................15
　2.3　CBIR系統簡介..................................16
　　2.3.1　Blobworld.................................17
　　2.3.2　MARS......................................18
　　2.3.3　NETRA.....................................19
　　2.3.4　QBIC......................................19
　　2.3.5　VIR Image Engine..........................21
　　2.3.6　VisualSEEK................................21
　2.4　關聯規則探勘 (Association Rule Mining)........22
　　2.4.1　關聯規則定義..............................23
　　2.4.2　問題分析..................................23
　　2.4.3　Apriori演算法.............................24
　2.5　資料分群演算法 (Clustering)...................26
　　2.5.1　分割式分群法..............................26
　　2.5.2　K-Means...................................27
　　2.5.3　K-Medoids.................................27
　2.6　決策樹分類法 (Classification).................28
　　2.6.1　決策樹分類................................28
　　2.6.2　ID3.......................................29
　　2.6.3　C4.5......................................30

第三章　研究方法.....................................32
　3.1　方法架構......................................32
　3.2　特徵值權重預測................................33
　　3.2.1　目的......................................33
　　3.2.2　特徵值權重日誌............................34
　　3.2.3　權重的分群................................35
　　3.2.4　特徵值權重決策樹..........................36
　　3.2.5　權重預測的修正............................38
　3.3　圖片關聯規則..................................38
　　3.3.1　圖片查詢日誌..............................38
　　3.3.2　圖片關聯規則..............................39
　　3.3.3　關聯規則查詢..............................39
　　3.3.4　關聯規則查詢與相似度查詢的整合............40
　3.4　系統整合架構..................................45

第四章　實驗分析.....................................47
　4.1　影像檢索系統..................................47
　　4.1.1　系統簡介..................................47
　　4.1.2　系統特性..................................49
　4.2　實驗資料及參數設定............................49
　　4.2.1　實驗資料..................................49
　　4.2.2　參數設定..................................53
　4.3　實驗規劃......................................53
　　4.3.1　自動測試..................................54
　　4.3.2　人工測試..................................55
　4.4　實驗結果......................................55
　　4.4.1　實驗數據..................................55
　　4.4.2　實驗範例..................................58
　4.5　實驗總結......................................60

第五章　結論與未來研究方向...........................61
　5.1　結論..........................................61
　5.2　應用..........................................62
　5.3　未來研究方向..................................62

第六章　參考文獻.....................................63</font></font>

[1] Rakesh Agrawal, Tomasz Imielinski, and Arun N. Swami. "Mining association rules between sets of items in large databases". Proc. of ACM SIGMOD, page 207-216, 1993.
[2] R Agrawal, R Srikant "Fast algorithms for mining association rules" Proc. 20th Int. Conf. Very Large Data Bases, VLDB, 1994.
[3] R. C. Agrawal, C. C. Aggarwal and V. V. V. Prasad. "Depth first generation of long patterns". In Proc. of the 6th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pages 108-118, 2000.
[4] Aggarwal, G. Ashwin, T.V. Ghosal, S. "An image retrieval system with automatic query modification". Multimedia, IEEE Transactions, Volume: 4, Issue: 2, page: 201-214, Jun 2002.
[5] Black, J., Fahmy, G., Panchanathan, S. "A Method for Evaluating the Performance of Content-Based Image Retrieval Systems". Image Analysis and Interpretation, Proceedings of the Fifth IEEE Southwest Symposium, Page: 96-100, 2002.
[6] Sergey Brin, Rajeev Motwani, Jeffrey D. Ullman, Shalom Tsur "Dynamic itemset counting and implication rules for market basket data". Proceedings of ACM SIGMOD international conference on Management of data, 1997.
[7] C. Carson, S. Belongie, H. Greenspan and J. Malik, "Blobworld: Image Segmentation Using ExpectationMaximization and Its Application to Image Querying". IEEE Trans. PAMI, pp. 1026-1038, 2002.
[8] I. Cox, M. L. Miller, S. M. Omohundro and P. N. Yianilos, "Pichunter: Bayesian Relevance Feedback for Image Retrieval". in Proc. Inter. Conf. Pattern Recogn, Vol. 3, pp. 362-369, 1996.
[9] A. Gupta "Visual Information Retrieval: A Virage Perspective". 1995.
[10] Jiawei Han and Micheline Kamber. "Data Mining: Concepts and Techniques". Morgan Kaufmann Publisher, 1999.
[11] Jiawei Han, Jian Pei, Yiwen Yin "Mining frequent patterns without candidate generation" Proceedings of ACM SIGMOD international conference on Management of data, 2000.
[12] J Han, KK Ma, "Fuzzy color histogram and its use in color image retrieval". Image Processing, IEEE Transactions, Volume: 11, Issue: 8, 2002.
[13] J. A. Hartigan, M.A. Wong "A k-means clustering algorithm". Applied Statistics, Vol. 28, pp. 100-108, 1979.
[14] T. Huang, S. Mehrotra, and K. Ramchandran. "Multimedia analysis and retrieval system (MARS) project". Proceedings of the 33rd Annual Clinic on Library Application of Data Processing-Digital Image Access and Retrieval, 1996.
[15] A. K. Jain and R. C. Dubes. "Algorithms for Clustering Data". Prentice Hall, 1988.
[16] S. Jeannin, "Mpeg-7 visual part of eXperimentation model version 9.0". ISO/IEC JTC1/SC29/WG11/N3914, 55th Mpeg Meeting, Pisa, 2001.
[17] L. Kaufman and P. J. Rousseeuw. "Finding Groups in Data: an Introduction to Cluster Analysis". John Wiley & Sons, 1990.
[18] Hae-Kwang Kim, Jong-Deuk Kim, Dong-Gyu Sim, Dae-Il Oh, "A Modified Zernike Moment Shape Descriptor Invariant to Translation, Rotation and Scale for Similarity-Based Image Retrieval". Multimedia and Expo, 2000.
[19] Jose M. Martinez, "MPEG-7 Overview (version 10)". ISO/IEC JTC1/SC29/WG11N6828, Palma de Mallorca, October 2004.
[20] J. McQueen "Some methods for classification and analysis of multivariate observations". 5th Berkeley Symposium on mathematics, Statistics and Probability, pp. 281-298, 1967.
[21] W. Niblack, R. Barber, W. Equitz, M. Flickner, E. Glasman, D. Petkovic, P. Yanker, C. Faloutsos, and G. Taubin. "The QBIC project: Querying images by content using color, texture and shape". In Proc. SPIE Storage and Retrieval for Image and Video Databases, February 1994.
[22] Jong Soo Park, Ming-Syan Chen, and Philip S. Yu. "An effective hash based algorithm for mining association rules". Proceedings of ACM SIGMOD international conference on Management of data, 1995.
[23] Payne, J.S. Stonbam, T.J. "Can texture and image content retrieval methods match human perception". Intelligent Multimedia, Video and Speech Processing, 2001.
[24] G Qiu, "Colour image indexing using BTC". Image Processing, IEEE Transactions, vol. 12, pp. 93-101, 2003.
[25] J. Ross Quinlan "Induction of Decision Tree". Machine Learning, pp. 81-106, 1986.
[26] J. Ross Quinlan "C4.5: programs for machine learning". Morgan Kaufmann, 1992.
[27] Y. Rui, T. S. Huang, M. Ortega, and S. Mehrotra. "Relevance feedback: A power tool for interactive content-based image retrieval". IEEE Trans. Circuits Syst. Video Technol, 644-655, 1998.
[28] A. W. M. Smeulders et al, "Content-based image retrieval at the end of the early years", IEEE Trans PAMI, vol. 22, pp. 1349-1380, 2000.
[29] J. R. Smith and S. F. Chang, "VisualSEEK: A Fully Automated Content-Based Image Query System". ACM Multimedia Conf. pp. 87-98, Boston, MA, Nov. 1996.
[30] J.R. Smith. "Integrated spatial and feature image systems: retrieval, analysis and compression". PhD thesis, Center for Telecommunications Research, Graduate School of Arts and Sciences, Columbia University, 1997.
[31] Yimin Wu and Aidong Zhang. "A feature re-weighting approach for relevance feedback in image retrieval". In Proc. IEEE Int. Conf. on Image Proc. 2002.
[32] Show-Jane Yen, Arbee L. P. Chen "An efficient approach to discovering knowledge from large databases". Proceedings of the fourth international conference on Parallel and distributed information systems, 1996.
[33] L. Zhang , F. Lin, B. Zhang, "A CBIR method based on color-spatial feature". IEEE Region 10th Ann. Int. Conf. 1999.
[34] http://elib.cs.berkeley.edu/blobworld/
[35] http://maya.ece.ucsb.edu/Netra/
[36] http://www.chiariglione.org/mpeg/standards/mpeg-7/mpeg-7.htm
[37] http://www.corel.com.tw/
[38] http://www.ctr.columbia.edu/VisualSEEk/
[39] http://www.lis.e-technik.tu-muenchen.de/research/bv/topics/mmdb/e_mpeg7.html
[40] http://www.virage.com/online/
[41] http://www-db.ics.uci.edu/pages/research/mars.shtml
[42] http://wwwqbic.almaden.ibm.com/