近年來由於網路盛行，大量多媒體資料在網路間流通，為了能夠方便傳輸及儲存，大部分的影像皆以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.

[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。