臺灣博碩士論文加值系統

隨著網際網路的發展，大量的多媒體資料(例如文字、影像、語音和視訊)儲存需求也愈增加，多媒體的檢索和搜尋也愈形重要。傳統上，材質特徵以文字、內容和關鍵字被使用於註解和查詢影像。當使用於大型資料庫，關鍵字的使用變成不但難處理也不能勝任表示影像的內容。因此，許多的以內容為主的影像檢索系統被提出來解決上述問題。
本論文為了改進傳統使用長條圖統計方法，需要較高的索引和檢索成本，我們提出以物件為主的方式進行檢索，並以物件的方式結合物件內容低階特徵作為查詢比對的條件，使查詢更準確。一般長條圖方法缺乏索引結構必需循序比對，我們提出以三角不等式的原理之有效的K-NNR搜尋技術，用以提昇長條圖比對的效率。除此之外，快速K-NNR搜尋方法也被應用於建立資料庫層索引結構，藉由簡化和減少高維特徵向量距離計算次數的方式，提昇檢索效能。最後，本論文使用邊緣偵測和區域成長方法來切割物件，並且提出一物件式的影像內容相似度計算方法。
本論文及若干文獻上的檢索方法，均經過兩個不同張數皆為自然影像的影像資料庫測試。實驗證明，本論文所提出的方法不僅在準確性優於所比較的其他方法，而且應用到大型資料庫系統上，仍維持相當好的效能。

As the advances of the Internet, the demand of storing multimedia information (such as text, image, audio, and video) has increased. And the multimedia retrieval and search is more and more important. Traditionally, textual features such as filenames, captions, and keywords have been used to annotate and retrieve images. As it is applied to a large database, the use of keywords becomes not only cumbersome but also inadequate to represent the image content. Therefore, many content-based image retrieval system have been proposed to solve this problem.
In this thesis, we propose an efficient object-based image retrieval method by using a fast K-NNR search algorithm which is designed according to the triangle inequality principle. The computational complexity of the traditional histogram-based image retrieval which is also improved by fast K-NNR search method is high due to the usage of the high-dimensional histogram and the lack of the indexing structure. Furthermore, a new indexing structure for the proposed object-based image retrieval technique is also proposed in this study. A special attention to object segmentation which combines the moment-preserving edge detection and the region-growing techniques is paid in this thesis. Finally, an object-based similarity metric is also proposed for query processing.
Experimental results show that the proposed image retrieval method is effective and superior to other methods in terms of overall computational complexity. Applying to a very large image database, the performance of the proposed method can be sustained.

項　　　目
中文摘要----------------------------------------------------i
英文摘要----------------------------------------------------ii
誌謝----------------------------------------------------iv
目錄----------------------------------------------------v
表目錄----------------------------------------------------ix
圖目錄----------------------------------------------------x
一、緒論------------------------------------------------1
1.1研究背景--------------------------------------------1
1.2研究動機--------------------------------------------3
1.3研究目的--------------------------------------------6
1.4論文架構--------------------------------------------7
二、文獻探討--------------------------------------------8
2.1影像低階特徵的萃取----------------------------------8
2.1.1顏色特徵的表示--------------------------------------8
2.1.2形狀特徵的表示--------------------------------------10
2.1.3材質特徵的表示--------------------------------------11
2.2顏色特徵比對----------------------------------------11
2.2.1顏色長條圖------------------------------------------11
2.2.2長條圖交集法----------------------------------------12
2.2.3權重的歐幾里德距離----------------------------------13
2.3形狀特徵比對----------------------------------------14
2.3.1基於數位矩量----------------------------------------14
2.3.2使用二維傅立葉轉換係數------------------------------15
2.3.3鏈碼編碼--------------------------------------------16
2.4紋理特徵比對----------------------------------------18
2.4.1伴隨出現矩陣----------------------------------------18
2.4.2自動回歸模型----------------------------------------19
2.4.3小波轉換--------------------------------------------19
2.5結合多特徵比對--------------------------------------20
2.6國內外相關研究--------------------------------------21
三、基於三角不等式原理之高效率長條圖相似度計算方法之設計25
3.1快速長條圖儲存格向量對映----------------------------25
3.1.1顏色相似度------------------------------------------25
3.2快速K-NNR搜尋演算法---------------------------------28
3.3影像檢索比對策略------------------------------------34
3.4實驗結果和討論--------------------------------------35
3.4.1實驗結果--------------------------------------------35
3.4.2討論------------------------------------------------42
四、物件為主的影像檢索系統------------------------------43
4.1物件切割--------------------------------------------44
4.1.1邊緣偵測--------------------------------------------44
4.1.2區域成長--------------------------------------------48
4.2物件內容表示----------------------------------------49
4.2.1顏色特徵萃取與表示----------------------------------50
4.2.2形狀特徵萃取與表示----------------------------------51
4.3物件特徵比對----------------------------------------54
4.3.1顏色特徵比對----------------------------------------54
4.3.2形狀特徵比對----------------------------------------55
4.4相似度量測------------------------------------------56
4.4.1顏色相似度量測--------------------------------------56
4.4.2形狀相似度量測--------------------------------------57
4.5輸出結果--------------------------------------------57
五、影像資料庫索引機制設計------------------------------59
5.1資料庫的建立----------------------------------------59
5.2索引機制設計----------------------------------------60
5.2.1索引架構--------------------------------------------61
5.2.2K個最近鄰居法則索引---------------------------------62
5.2.3利用三角不等式簡化K-NNR索引-------------------------62
5.3多維資料結構索引------------------------------------65
5.4K值的決定-------------------------------------------66
六、系統實現與實驗結果----------------------------------69
6.1只使用物件顏色特徵查詢的實驗結果--------------------69
6.2只使用物件形狀特徵查詢的實驗結果--------------------76
6.3結合兩者特徵的實驗結果------------------------------82
6.4不同方法之檢索效能及速度比較------------------------89
6.5實現系統與網路化------------------------------------93
6.5.1使用者介面------------------------------------------93
6.5.2實現結果--------------------------------------------94
七、結論------------------------------------------------98
參考文獻----------------------------------------------------99

[1]M. Swain and D. Ballard, “Color indexing,” Int. J. Comput. Vision, 7(1), pp.11-32, 1991.[2]J. Huang, S. Kumar, M. Mitra, W.-J. Zhu, and R. Zabih, “Image indexing using color correlograms,” in IEEE Comput. Soc. Conf. Comput. Vision Pattern Recognition, Puerto Rico, June, pp.744-749, 1997.[3]X. Wan and C.-C. Jay Kuo, “A new approach to image retrieval with hierarchical color clustering,” IEEE Trans. On Circuits and Systems for Video Technology, 8(5), pp.628-643, 1998.[4]S.C. Pei and C.M. Cheng, “Extracting color features and dynamic matching for image data-base retrieval,” IEEE Trans. On Circuits and Systems for Video Technology, 9(3), pp.501-512, 1999.[5]R. Methrotra and J. Gary, “Similar-shape retrieval in shape data management,” IEEE Computer, 28, pp. 57-62, 1995.[6]A. K. Jain and A. Vailaya, “Image retrieval using color and shape” Pattern Recognition, 29, pp.1233-1244, 1996.[7]B. Manjunath and W. Ma, “Texture features for browsing and retrieval of image data,” IEEE Trans. Pattern Anal. Machine Intell., 18, pp.837-842, 1996.[8]Z. Wang, Z. Chi and D. Feng, “Content-based image retrieval using block-constrained fractal coding and nona-tree decomposition,” IEE Proc.-Vis. Image Signal Process, 147(1), pp.9-15, 2000.[9]S.Y Lee and F.J Hsu, “2D C-string：A new spatial Knowledge representation for image database systems,” Pattern Recognition, 23, pp. 1077-1087, 1990.[10]Essam A. El-Kwae, and Mansur R. Kabuka, “A Robust Framework for Content-Based Retrieval by Spatial Similarity in Image Databases,” Transactions on Information Systems, Vol 17, NO. 2, ACM ,pp.174-198, 1999.[11]A. D. Bimbo, “Visual Information Retrieval,” Morgan Kaufmann Publishers, Inc. San Francisoc, California, 1999.[12]Niblack, W., R. Baeber, W. Equitz, M. Flickner, E. Glassman, D. Petkovic and P. Yanker., “The QBIC project: Querying images by content using colour, texture and shape,” In SPIC 1908, Storage and Retrieval for Image and Video Databases, February. 1993.[13]A. Pentland, R. W. Pichard, and S. Sclaroff, “Photobook: Content-based Manipulation of Image Databases,” International Journal of Computer Vision 18(3), pp.233-254, 1996.[14]J. R. Smith and S. F. Chang, “VisualSEEK: a fully automated content-based image query system,” in Proc. ACM Inetrn. Conf. Multimedia, 11, pp.87-98, 1996.[15]J. R. Smith and S. F. Chang, “WebSEEK: a content-based image and video search engine for the world-wide web,” IEEE Multimedia, 1996.[16]J. R. Smith and S. F. Chang, “Safe: A general framework for integrated spatial and feature image search,” in Workshop on Multimedia Signal Processing, 1997.[17]Thomas S. Huang, Sharad Mehrotra, and Kannan Ramchandran, “Multimedia analysis and retrieval system(MARS) project,” In Proc of 33rd Annual Clinic on Library Application of Data Processing-Digital Image Access and Returebal, 1996.[18]Virginia Ogle and Michael Stonebraker, “Chabot: Retrieval from a Relational Database of Images,” IEEE Computer, Vol. 28, No.9, pp. 40-48, 1995.[19]ISO/IEC JTC1/SC29/WG11, “MPEG-4 Overview - (V.21 — Jeju Version),” Doc. N4668, March 2002.[20]ISO/IEC JTC1/SC29/WG11, “Overview of the MPEG-7 Standard (version 5.0),” Doc. N4031,Singapore, March 2001.[21]Hee-Jung Bae; Sung-Hwan Jung, “Image retrieval using texture based on DCT,” Proceedings of 1997 International Conference on Information, Communications and Signal Processing, 1997. ICICS., 2 , pp.1065 —1068, 1977.[22]Smith, J.R.; Shih-Fu Chang, “ingle color extraction and image query,” Proceedings., International Conference on image Processing., 3, pp.528-531, 1995.[23]Ig-Jae Kim, Je-Ho Lee, Yong-Moo Kwon and Sang-Hui Park, “Content-based image retrieval method using color and shape features,” International Conference on Information, Communications and Signal Processing ,1997. ICICS., 2, pp.9-12, 1997.[24]Swain, M.J. and D.H. Ballard. , “Colour indexing,” International Journal of Computer Vision, 7(1), pp.11-32, 1991.[25]Alt, F.L. “Digital pattern recognition by moments,” Journal of ACM, 11, pp.240-258, 1962.[26]Hu, M.K., “Visual pattern recognition by moment invariants,” IRE Transactions on Information Theory, 8, pp.351-364, 1962.[27]Daubechies, I. , “Orthonomal bases of compactly supported wavelets,” Communications on Pure and Applied Mathematics, XLI pp.909-996, 1988.[28]Chui, C.K, “An Introduction to Wavelets,” San Diego, CA: Academic Press, 1992.[29]Freeman, H. ,“Computer processing of line drawing images”, Computer Surveys,6, pp.57-97, 1974.[30]Haralick, R.M. and L.G. Shapiro. ,“Computer and Robot Vision,” Vol. 1-11. Reading MA, USA: Addison Wesley Publishing Company, 1992.[31]Khotanzad, A. and R.L. Kayshap., “Feature selection for texture recognition based on image synthesis,” IEEE Trans. on Systems, Man and Cybernetics, 17(6), pp.1087-1095. [32]Mao, J. and A.K. Jain, “Texture classification and segmentation using multiresolution, simultaneous autoregressive models,” Pattern Recognition, 25(2), pp.173-188, 1992. [33]Manjunath, B.S. and M.Y. Ma., “Texture feature for browing and retrieval of image data,” IEEE Trans. on Pattern Analysis and Machine Intelligence, 18(8), pp.837-842, 1996.[34]ANIL K. Jain and ADITYA VAILAYA, “Image retrieval using color and shape,” Pattern Recognition, Vol.29 No.8, pp.1233-1244, 1996.[35]Gevers, T.; Smeulders, A.W.M., “PicToSeek: combining color and shape invariant features for image retrieval,” Image Processing, IEEE Transactions on , Volume: 9 Issue: 1 , pp: 102 —119, Jan. 2000 [36]Ozer, B.; Wolf, W.; Akansui, A.N., “A Graph Based Object Description for Information Retrieval in Digital Image and Video Libraries,” Content-Based Access of Image and Video Libraries (CBAIVL ''99) Proceedings. IEEE Workshop on , pp.79 —83, 1999.[37]Kam, A.H.; Ng, T.T.; Kingsbury, N.G.; Fitzgerald, W.J. “Content Based Image Retrieval through Object Extraction and Querying,” Content-based Access of Image and Video Libraries, 2000. Proceedings. IEEE Workshop on , pp. 91 —95, 2000.[38]Nevenka, Thomas McGee, and Herman Elnbaas, “Video Keyframe Extraction and Filtering : A Keyframe is not a Keyframe to Everyone,” Proceedings of the sixth internation al conference on Information and Knowledge management, pp.113-120, 1997.[39]M. Flicker et. al, “Query by image and video content system: the QBIC system,” IEEE Computer, vol. 28, No. 9, Sept., 23-32, 1995.[40]Osmar R. Zaiane, Jiawei Han, Ze-Nian Li, and Jean Hou., “Mining MultiMedia Data,” Proc. CASCON''98: Meeting of Minds, Toronto, Canada, 11, pp.83-96, 1998.[41]Andrea F. Abate, Michele Nappi, Genny Tortora, and Maurizio Tucci. “IME: an image management environment with content-based access,” Image and Vision Computing 17, pp.967-980, 1999.[42]P.S. Williams. and M.D. Alder., “Image segmentation using an entropic UpWrite,” TR97-03, CIIPS,Dept. of EE Engineering,The University of Western Austtralia, 1996.[43]A. Kam and W. Fitzgerald., “Image Segmentation: An unsupervised Multiscale Approach,” In Proceedings of the 3rd International Conference on Computer Vision, Pattern Recognition and image Processing(CVPRIP 2000), volume 2,pp.54-57,February 27March 3, 2000.[44]Hai Gao; Wan-Chi Siu; Chao-Huan Hou , “Improved Techniques for Automatic Image Segmentation,” Circuits and Systems for Video Technology, IEEE Transactions on , Volume: 11 Issue: 12 ,pp: 1273 —1280, Dec. 2001.[45]方俊弘, “應用矩量保持技術於低速率視訊壓縮之研究,” 國立高雄第一科技大學電腦與通訊工程系碩士論文, Jun, 2002[46]Bentley,J.L., “Multidimensional binary search trees used for associative searching,” Communications of ACM. 18(9), pp:509-517, 1975.[47]Guttmann A., “R-trees:A dynamic index structure fir spatial searching,” Proc. ACM SIGMOD Int. Conf. On the Management of Data, June, pp:47-57, 1984. [48]Yining Deng; Manjunath, B.S.; Kenney, C.; Moore, M.S.; Shin, H., “An Efficient Color Representation for Image Retrieval,” Image Processing, IEEE Transactions on , Volume: 10 Issue: 1, pp: 140 —147, Jan. 2001.[49]J. Hafner, H. S. Sawhney, W. Equitz, M. Flickner, and W. Nibllack, “Efficient color histogram indexing for quadratic form distance function,” IEEE Trans. Pattern Anal. Machine Intell, vol. 17, pp.729-736, 1995.[50]G. Cha and C. Chung, “Multi-mode indices for effective image retrieval in multimedia system,” in Proc. IEEE Multimedia Computing Systems, pp.152-159, 1998.[51]Shyi-Chyi Cheng and Chen-Kuei Yang, “A fast and novel technique for color quantization using reduction of color space dimensionality,” to appear on Pattern Recognition Letters.[52]H.A David, Order Statisics. New York: Wiley, 1980.[53]J. Barros , J. French , W. Martin , P. Kelly and M. Cannon , “Using the triangle inequality to reduce the number of comparisons required for similarity — based retrieval,” in Proc. IS&T/SPIE — storage and Retrieval for still Image and Video database IV , 1996.