Basic Search / Detailed Display

Author: 鄭翔芬
Hsiang-Fen Cheng
Thesis Title: 影像分群與搜尋
Image Clustering and Retrieval
Advisor: 徐俊傑
Chiun-Chieh Hsu
Committee: 賴源正
Yuan-Cheng Lai
Shih-Chen Huang
Degree: 碩士
Department: 管理學院 - 資訊管理系
Department of Information Management
Thesis Publication Year: 2009
Graduation Academic Year: 97
Language: 中文
Pages: 65
Keywords (in Chinese): 內容式影像檢索JPEG離散餘弦轉換分群
Keywords (in other languages): Content-Based Image retrieval, JPEG, Discrete cosine transforms, Clustering
Reference times: Clicks: 321Downloads: 1
School Collection Retrieve National Library Collection Retrieve Error Report

近年來由於網路盛行,大量多媒體資料在網路間流通,為了能夠方便傳輸及儲存,大部分的影像皆以JPEG壓縮格式管理。然而目前影像檢索的相關研究,大多以未壓縮影像之內容為主,故必須先將JPEG影像解壓縮至空間域 (spatial domain) 來處理,其計算過程的複雜度極高,非常耗時且缺乏效率。因此為縮短冗長的檢索時間,直接在壓縮域 (compressed domain) 作影像擷取及檢索,此舉能省下大量的時間成本,且透過部份解壓縮 (partial decoding) 所取得的數值,亦能明確地代表影像的特性。然而此領域中的研究,多數仍以選取大量係數作為影像特徵,或對係數作額外的計算,使影像檢索時間隨影像資料庫而擴大。因此本論文主要的研究目的為擷取壓縮域之代表性特徵值,有效地運用於影像檢索系統,搜尋出使用者所需之影像。

本論文提出了有效率的影像分群與檢索技術,以加快影像檢索的速度,並精準地搜尋相似的影像。首先將影像資料庫利用二分分群 (Bisecting K-means Clustering) 方法,依照影像不同的內含分為數個群聚,因此在之後的檢索過程中,不必搜尋所有資料庫的影像,而只要計算少部分影像特徵。且本論文不需完全解壓縮而採用直接擷取離散餘弦轉換 (Discrete Cosine Transformation, DCT) 域的直流係數 (Direct Current Coefficient, DC Coefficient) 影像特徵,不僅降低相似度測量的時間,管理上也較為方便。透過DC特徵值在分群階段以及相似度計算階段的處理,有效地搜尋符合使用者需求之影像。根據實驗數據顯示,本論文提出之方法具高效率檢索回應特性,並改善影像檢索的效果。

Nowadays, due to the rapid growth of World Wide Web (WWW), a large amount of multimedia data is generated on Internet, which is usually compressed in JPEG format in order to transmit and store efficiently. However, current approaches for content based image retrieval almost focus on uncompressed images. They need to decode images to spatial domain first, which would consume a lot of computation and search time. Therefore, in order to shorten the retrieval time, directly processing the feature extraction and image retrieval from compressed domain can save a lot of time. In addition, the value obtaining by only partial decoding could also represent the image’s characteristic explicitly. Nevertheless, most of approaches in this compressed domain still select a lot of coefficients to represent the image’s features or process those coefficients in additional steps for obtaining image features. However, in this way, the search time will increase dramatically with the size of the image database. Hence, the purpose of this thesis is to extract only a few representative features from the compressed domain, and effectively use these features in image retrieval system such that the images requested by users can be retrieved efficiently.

This thesis proposes an efficient image clustering and retrieval approaches. They can improve search time and effectively retrieve the similar images. Using bisecting K-means algorithm, the images from an compressed image database are separated according to the image’s content first, so the retrieval approach is not necessary to search all images in the image database in later processes. Moreover, DC (Direct Current) coefficients are directly extracted from DCT (Discrete Cosine Transformation) domain without fully decoding the compressed images. Therefore, the time of similarity measurement is decreased, and the features extracted from the image database are easy to be managed. In addition, using DC features on the clustering stage and similarity computing stage, the proposed approach can efficiently retrieve the images which match the user’s demand. Experimental results reveal that the proposed approach has highly efficient response time and improves the performance of image retrieval result.

中文摘要 I 英文摘要 II 誌謝 III 目錄 IV 圖索引 VI 表索引 VII 第一章 緒論 1 1.1 研究背景 1 1.2 研究動機與目的 2 1.3 研究方法及貢獻 4 1.4 論文架構 5 第二章 文獻探討 6 2.1 內容式影像檢索技術 6 2.1.1 空間域之影像檢索技術 8 2.1.2 頻率域之影像檢索技術 9 2.2 CBIR系統 10 2.2.1 QBIC 10 2.2.2 VisualSEEk 11 2.2.3 Virage 12 2.3 JPEG影像壓縮格式 13 2.3.1 色相轉換 15 2.3.2 離散餘弦轉換 16 2.3.3 量化 17 2.3.4 熵編碼 18 2.4 影像分群技術 21 2.4.1 階層式分群演算法 22 2.4.2 分割式分群演算法 22 2.4.3 K-means分群演算法及Bisecting K-means分群演算法 23 第三章 研究方法 25 3.1 系統架構 25 3.2 影像解碼 27 3.2.1 DC霍夫曼解碼 27 3.2.2 脈差調變解碼 29 3.3 影像特徵擷取 30 3.4 分群 32 3.4.1 Bisecting K-means演算法 33 3.4.2 影像特徵分群 36 3.4.3 影像分群 37 3.5 影像相似度測量 39 3.5.1 平均距離計算 39 3.5.2 相似區塊數計算 40 第四章 實驗分析與結果 43 4.1 影像檢索系統 43 4.2 環境設置 45 4.2.1 影像資料 45 4.2.2 評估準則 47 4.3 實驗規劃 47 4.4 實驗結果 49 第五章 結論與未來研究方向 53 5.1 結論 53 5.2 未來方向 54 參考文獻 55

[1] F. Arnia, I. Iizuka, M. Fujiyoshi, and H. Kiya, ”DCT Sign-Based Similarity Measure for JPEG Image Retrieval”, IEICE Trans. Fundamentals, Vol. E90–A, No.9, pp. 1976-1985, 2007.

[2] J. R. Bach, C. Fuller, A. Gupta, A. Hampapur, B. Horowitz, R. Humphrey, R. Jam, C. F. Shu, “The Virage Image Search Engine: An open framework for image management”, Proc. of SPIE, Vol. 2670, pp. 76-87, 1996.

[3] M. Bajaj and J. A. Lay, “Image Indexing and Retrieval in Compressed Domain Using Color Clusters”, Proc. of the 2007 IEEE Symposium on Computational Intelligence in Image and Signal Processing (CIISP), pp. 271-274, 2007.

[4] Y. K. Chan and Y. T. Liu, “An image retrieval system based on the image feature of color differences on edges in spiral scan order”, International Journal of Pattern Recognition and Artificial Intelligence, Vol. 17, Issue 8, pp. 1417-1429, 2003.

[5] C. C. Chang, “Spatial Match Retrieval of Symbolic Pictures”, Journal of Information Science and Engineering, Vol. 7, No.3, pp. 405-422, 1991.

[6] C. C. Chang, J. C. Chuang, and Y. S. Hu, “Retrieving digital images from a JPEG compressed image database”, Image and Vision Computing, Vol. 22, pp. 471–484, 2004.

[7] S. K. Chang, Q. Y. Shi, and C. W. Yan, “Iconic indexing by 2-D Strings”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-9, No.3, pp.413-428, 1987.

[8] Y. Chen, J. Z. Wang, and R. Krovetz, “Content-Based Image Retrieval by Clustering”, Proc. of ACM SIGMM, pp. 193 – 200, 2003.

[9] Y. Y. Chung and M. T. Wong, “Image Retrieval from Compressed Images”, Proc. of DICTA, pp.145-150, 2002.

[10] R. Datta, D. Joshi, J. Li, and J. Z. Wang, “Image Retrieval: Ideas, Influences, and Trends of the New Age”, ACM Computing Surveys, Vol. 40, Issue 2, 2008.

[11] G.. C. Feng and J. Jiang, “Image extraction in DCT domain”, IEE Proceedings-Vision, Image and Signal Processing, Vol. 150, Issue 1, pp. 20-27, 2003.

[12] M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B. Dom, M. Gorkani, J. Hafher, D. Lee, D. Petkovie, D. Steele, and P. Yanker, “Query by image and video content: The QBIC system”, IEEE Computer, Vol. 28, pp.23-32, 1995.

[13] D. S. Guru and P. Punitha, “An invariant scheme for exact match retrieval of symbolic images based upon principal component analysis”, Pattern Recognition Letters, Vol. 25, Issue 1 , pp. 73–86, 2004.

[14] V. R. Khapli and A. S. Bhalchandra, “Compressed Domain Content Based Image Retrieval: State of the Art, Challenges and Open Issues”, Proceedings of World Academy of Science, Engineering and Technology, Vol. 32, pp. 579-584, 2008.

[15] S. Y. Lee, M. C. Yang, and J. W. Chen, “2D B-string: a Spatial Knowledge Representation for Image Database Systems”, Proc. ICSC’92 Second Int.
Computer Sci. Con., pp. 609-615, 1992.

[16] Y. Li and S. M. Chung, “Parallel Bisecting K-Means with Prediction Clustering Algorithm”, Journal of Supercomputing, Vol. 39, Issue 1, pp. 19-37, 2007.

[17] T. C. Lu and C. C. Chang, “Color image retrieval technique based on color features and image bitmap”, Information Processing and Management, pp. 461-472, 2007.

[18] Z. M. Lu, S. Z. Li, and H. Burkhardt, “A Content-Based Image Retrieval Scheme In JPEG Compressed Domain”, ICIC International, Vol. 2, No.4, pp. 831-839, 2006.

[19] A. Mohamed, Y. Weng, and J. Jiang, “An Efficient Face Image Retrieval through DCT Features”, Proc. of the 10th IASTED International Conference, 2008.

[20] H. Nezamabadi-pour and S. Saryazdi, “Object-Based Image Indexing and Retrieval in DCT Domain using Clustering Techniques”, Proc. of World Academy of Science, Engineering and Technology, Vol. 3, pp. 207-210, 2004.
[21] Y. Rui, T. S. Huang, and S. F. Chang, “Image Retrieval: Current Techniques, Promising Directions, and Open Issues”, Journal of Visual Communication and Image Representation, Vol. 10, Issue 1, pp. 39–62, 1999.

[22] E. D. Sciascio, M. Mongiello, F. M. Donini, and L. Allegretti, “Retrieval by spatial similarity: an algorithm and a comparative evaluation”, Pattern Recognition Letters, Vol. 25, pp. 1633-1645, 2004.

[23] J. R. Smith and S. F. Chang, “VisualSEEk: a fully automated content-based image query system”, Proc. ACM Multimedia 96, Vol. 11, pp. 87-98, 1996.

[24] M. Steinbach, G. Karypis, and V. Kuma, “A Comparison of Document Clustering Techniques”, In KDD Workshop on Text Mining, 2000.

[25] M. J. Swain and D. H. Ballard, “Color Indexing”, International Journal of Computer Vision, Vol. 7, No. 1, pp. 11-32, 1991.

[26] C. Theoharatos, V. K. Pothos, G. Economou, and S. Fotopoulos, “Compressed Domain Image Indexing and Retrieval based on the Minimal Spanning Tree”, In IEEE International Conference on Multimedia and Expo (ICME), pp. 1516-1519, 2005.

[27] G. K. Wallace, “The JPEG still picture compression standard”, Comm. ACM, Vol. 34, Issue 4, pp. 30-44, 1991.

[28] Y. G. Wu and J. H. Liu, “Entropy classification and discrete-cosine-transform-based image indexing system”, Journal of Electronic Imaging, Vol. 15, Issue 2, pp. 023019-1~023019-9, 2006.

[29] Y. Zhong and A. K. Jain, “Object localization using color, texture and shape”, Pattern Recognition, Vol. 33, pp. 671-684, 2000.

[30] ISO/IEC 10918 (JPEG), “Information Technology - Digital Compression and Coding of Continuous-Tone Still Images - Requirements and Guidelines”, 1992.

[31] J. Miano, “Compressed Image File Formats”, Addison-Wesley, 1999.

[32] 戴顯權,“資料壓縮第二版”,紳藍出版社,2002。

無法下載圖示 Full text public date 2014/07/27 (Intranet public)
Full text public date This full text is not authorized to be published. (Internet public)
Full text public date This full text is not authorized to be published. (National library)