臺灣博碩士論文加值系統

近年來，隨著數位圖書館的建立，如何有效率地管理一個大型的影像資料庫變得越來越重要。在影像資料庫中可能包含商標，彩色圖片，照片，郵票以及油畫等等。事實上，若將傳統處理文字資料的圖書館分類系統用於影像資料庫上並不太適當，因若想用傳統文字檢索鍵(keyword)的方法來搜尋影像資料庫，勢必要將每一筆影像資料用文字建立檢索鍵。如此一來不只要花費大量的時間和金錢建立文字檢索鍵，而且所建立的檢索鍵又可能太過主觀不符合實際需求。因此對於影像資料庫的管理，首先要建立一個有效率的搜尋方法，而捨棄傳統以文字為檢索鍵的方法。目前以影像本身的內容為檢索鍵的搜尋方式是影像資料庫管理上的最佳利器！
配合著數位圖書館的建立網際網路應用的普及，此項技術已吸引許多研究單位的投入。其中大部份的系統都是處理彩色影像資料庫，事實上商標搜尋本身，也是有著很大的應用市場。由於著作及智慧財產權觀念的建立，如何設計一個商標，不致於去模倣到現有已註冊商標也變成越來越重要。因此，如何設計一良好的商標搜尋系統以幫助使用者在極短的時間內，找尋出相似的商標已成為一重要研究課題。因此，本論文首先將提出商標檢索系統。此系統含三部分：商標切割、特徵擷取及商標檢索。第一個部分將提出半自動的切割系統，使用者可利用此系統，將商標中最具代表性的數個圖樣找出來。接下來，對每個圖樣，我們會以幾個特徵來描述它，包括不變矩量、邊界方向的直方統計圖，還有兩種較不受幾何變形影響的轉換係數。綜合考量每個特徵所做的搜尋結果，我們可以找到數個相似的商標。最後，可依使用者對目前搜尋結果的意見，自動調整每個特徵值的權重，以期使用者能在下一次的搜尋中，得到更滿意的結果。
在另一方面，我們亦提出兩個彩色影像檢索系統，此兩系統主要是利用影像本身的子影像(sub-image)作搜尋。在第一個系統中，首先，對每張影像中的每個像素，取其上下左右的像素及自己本身構成一個內容單元。由於在一張影像中，有很多相似的內容單元，因此我們利用一個分群演算法將影像中具代表性的內容單元 (稱為基本單元) 先找出來，再利用這些基本單元搜尋相似的影像。同樣的，我們也可利用使用者對目前搜尋結果的意見，調整影像中每個基本單元在搜尋時的權重，以符合使用者之需求。
在第二個系統中，我們將提出一個以區塊為單位的搜尋法，希望能搜尋與原影像部分相似的影像。首先，我們先將一張影像切成好幾塊，對每一小塊影像我們計算其彩色矩量當作特徵，因為在一張影像中可能會有很多部分是相似的，因此我們可先將這些彩色矩量做一個分群的動作，找到其中具代表性的數個彩色矩量，然後利用它們來做搜尋的動作。
由於每張影像有其不同的特性，因此任何方法都不可能滿足所有影像的需求。基於此，最後我們將提出一個回饋演算法，依使用者對目前綜合各種方法的搜尋結果的意見，決定對目前這張搜尋影像最有利的方法。實驗結果顯現，我們所提出的各式搜尋方法的確相當有效。

In recent year, with the construction of digital libraries, the management of the large multimedia databases such as trademarks, color photographs, stamps and paintings becomes an important issue. Thus, the demand for an automatic and user-friendly image retrieval system based on image content become urgent.
Most of the current image retrieval systems search the similar images based on the keyword of each image. However, the keywords must be defined by persons. If the image database contains many images, it will be time consuming to define keywords for the entire database. Moreover, what are the proper keywords for an image is difficult to decide. Thus, the demand for an automatic and user-friendly image retrieval system based on image content, such as color, texture, shape, spatial relationship, motion, and so on, become urgent. The major problem for a content-based image retrieval system is how to extract proper features to represent the visual content in an image and query the similar images by these features. Hence, in this dissertation, we will propose methods to extract the shape and color features for images.
First, with the gradual increase of the number of trademarks, trademark imitation becomes a serious problem. Thus, to build an efficient trademark retrieval system is imperative. In this dissertation, such a system will first be presented. It consists of three phases: trademark segmentation, feature extraction, and trademark retrieval. A semi-automatic segmentation method will be proposed to extract the shapes of those representative objects, called "masks", in each trademark. Next, some features will be selected to describe a mask. These include invariant moments, the histogram of edge directions, and two kinds of transform coefficients that are robust to geometric deformation. Then, based on the rank of the feature distance, a similarity measure is provided to do the similar trademark retrieval. A feedback algorithm will be also proposed to automatically determine the weight of each feature according to the user''s response.
Secondly, a color image retrieval method based on the primitives of images will be proposed. The context of each pixel in an image will be defined. Then, the contexts in the image are clustered into several classes based on the algorithm of fast non-iterative clustering. The mean of the contexts in the same class is considered as a primitive of the image. The primitives are used as feature vectors. Since the numbers of primitives between images are different, a specially designed similarity measure is then proposed to do color image retrieval. To better adapt to the preferences of users, a relevance feedback algorithm is provided to automatically determine the weight of each primitive according to the user’s response.
Finally, a region-based color image retrieval method will be proposed to find those images that are partly similar to the query one. An image is divided into several blocks. Then, the color features of all blocks are extracted and clustered into several classes. The mean vectors of each class are considered as a primitive of the image. All primitives are used as features. Furthermore, since for few special types of images, other methods may have better results occasionally, a relevance feedback algorithm is also provided to automatically determine the most appropriate method according to the user’s response. Experiment results show that these proposed methods are superior to others.

Abstract (in Chinese) …………………….……….……. ii
Abstract (in English) ……………………………………. v
Acknowledgments (in Chinese) …………….……………… iii
Table of contents ………………………………….……….. ix
List of Figures ..……………………………………………. xiv
List of Tables …………………………………………….. xviii
Chapter 1 Introduction ………………………… 1
1.1 Motivation………………..………………… 3
1.2 Previous Works…..…………………………… 3
1.2.1 Review of the content-based image retrieval system 3
1.2.1.1 QBIC ……………………………………… 3
1.2.1.2 Virage ……………………………………. 5
1.2.1.3 MARS …………………………………….. 5
1.2.1.4 WebSEEk ……………………………….. 6
1.2.1.5 Blobworld …………………………………. 6
1.2.2 Review of the features for content-based image retrieval6
1.2.2.1 Shape feature……………………………… 7
1.2.2.1.1 Invariant moments…………………… 9
1.2.2.1.2 Fourier Descriptor …………………. 10
1.2.2.1.3 Chain code ……….…………………. 10
1.2.2.1.4 Zernike moments ….……………….. 11
1.2.2.1.5 Multi-layer eigenvecter (MLEV) ……… 12
1.2.2.1.6 Angular Radial Transformation (ART) … 12
1.2.2.1.7 Curvature Scale Space (CSS) …………… 13
1.2.2.2 Color feature ………………………….. 15
1.2.2.2.1 Color histogram ………………….. 15
1.2.2.2.2 Color moments …………………… 16
1.2.2.2.3 Color set ………………………….. 17
1.2.2.2.4 Color Correlogram ……………………. 17
1.2.2.2.5 Scalable Color ………………………… 18
1.2.2.2.6 Dominant Color ………………………. 19
1.2.2.2.7 Color Layout ……………………….. 20
1.2.2.2.8 Color Structure …………………….. 21
1.2.2.3 Texture feature ……………… 22
1.2.2.3.1 Wavelet moments …………….. 22
1.2.2.3.2 Water-filling …………………… 23
1.3 The Proposed Methods……………………… 23
1.3.1 The trademark segmentation and retrieval system 24
1.3.2 A Context-Based Approach for Color Image Retrieval 25
1.3.3 Color Image Retrieval Based on Primitives of Color Moments 26
1.4 Synopsis of the dissertation ………… 27
Chapter 2 A New System for Trademark Segmentation and Rtrieval .. 28
2.1 Introduction ……………………………….. 28
2.2 Trademark Segmentation ……………….… 31
2.3 Feature Extraction …………………………… 34
2.3.1 Invariant Moments ………………………. 34
2.3.2 Polar-coordinate Transform, Edge Detector, Derivative, and Fourier Transform …………….… 35
2.3.3 Histogram of Edge Directions…………… 38
2.4 Trademark Retrieval …………………………. 39
2.5 Experimental Results …………………….... 41
2.5.1 Experimental Results on Database D1 …… 42
2.5.2 Experimental Results on Database CE1 …… 46
2.6 Summary ……………………………………………… 48
Chapter 3 A Context-Based Approach for Color Image Retrieval50
3.1 Introduction ……………………… 50
3.2 Primitive Extraction ……………………… 53
3.2.1 Contexts ……………………………………. 53
3.2.2 Primitives ………………………………….. 55
3.3 Color Image Retrieval ………………………. 57
3.3.1 Similarity Measure …………………….… 58
3.3.2 Relevance Feedback Algorithm ………………… 59
3.4 Experimental Results ……………………………… 60
3.4.1 Experimental Results on Small Database D1 … 61
3.4.2 Experimental Results on Large Database D2 … 66
3.5 Summary ………………………………………………… 70
Chapter 4 Color Image Retrieval Based on Primitives of Color Moments 72
4.1 Introduction …………………………………… 72
4.2 Primitives of Color Moments Extraction … 75
4.3 Color Image Retrieval ………………………… 79
4.3.1 Similarity Measure …………………………… 79
4.3.2 Relevance Feedback Algorithm ……………… 80
4.4 Experimental Results ………………………… 82
4.4.1 Experimental Results on Small Database D1 83
4.4.2 Experimental Results on Large Database D2 90
4.5 Summary ……………………………………………… 92
Chapter 5 Conclusions and future research directions 95
5.1 Conclusions ……………………………….…… 95
5.2 Future research directions ………………… 98
5.2.1 Visual feature combination ……………… 98
5.2.2 Image Searching Engine …………………… 98
References ……………………..…………………… 100
Publication Lists …………..…………………… 106

1. QBIC, the IBM QBIC project, Demo: http://wwwqbic.almaden.ibm.com/.
2. M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B. Dom, M. Gorkani, J. Hafner, D. Lee, D. Petkovic, D. Steele, and P. Yanker, “Query by image and video content: The QBIC system,” IEEE Computer, Vol. 28, No. 9, pp. 23-32, 1995.
3. Virage, the project of Virage Inc., Demo: http://virage.com/.
4. J. R. Bach, C. Fuller, A. Gupta, A. Hampapur, B. Horowitz, R. Humphrey, R. Jain, and C. F. Shu, “The Virage image search engine: An open framework for image management,” in Proc. SPIE Storage and Retrieval for Still Image and Video Databases IV, pp. 76-87, San Jose, CA, USA, February 1996.
5. MARs, the Multimedia analysis and retrieval system developed at University of Illinois at Urbana-Champaign. Demo: http://jadzia.ifp.uiuc.edu:8000/.
6. S. Mehrotra, Y. Rui, O. B. Michael, and T. S. Huang, “Supporting content-based queries over images in MARS,” in Proc. IEEE Int. Conf. Multimedia Computing and Systems, pp. 632-633, 1997.
7. Y. Rui, T. S. Huang, M. Ortega, and S. Mehrotra, “Relevance feedback: A power tool in interactive content-based image retrieval,” IEEE Tran. Circuits Systems Vedio Technol (Special Issue on Interactive Multimedia Systems for the internet), Vol. 8, No. 5, pp. 644-655, Sept. 1998.
8. X. S. Zhou, T. S. Huang, “ Image retrieval: feature primitives, feature representation, and relevance feedback,” in Proc. IEEE Workshop on Content-Based Access of Image and Video Libraries, in Conjunction with CVPR''00, pp. 10-14, 2000.
9. WebSEEk, the World Wide Web oriented text/image search engine, Demo: http://www.ee.columbia.edu/~sfchang/demos.html/.
10. R. Smith and S. F. Chang, “Visually searching the web for content,” IEEE Trans. Multimedia, Vol. 4, No. 3, pp. 12-20, 1997.
11. C. Carson, S. Belongie, H. Greenspan, and J. Malik, “Region-based image querying,” in Proc. IEEE Workshop on Content-Based Access of Image and Video Libraries, in Conjunction with CVPR''97, pp. 762-768, 1997.
12. Hu, “Visual pattern recognition by moment invariants,” IRE Trans. on Inform. Theory, Vol. IT-8, pp. 179-187, 1962.
13. J. K. Wu, C. P. Lam, B. M. Mehtre, Y. J. Gao, and A. D. NarasiMhalu, “Content-based retrieval for trademark registration,” Multimedia Tools and Applications Vol. 3, pp. 245-267, 1996.
14. S. Zhang and K. K. Ma, “A novel shape matching method using biological sequence Dynamic alignment,” in Proceedings of IEEE International Conference on Multimedia and Expo, 2000.
15. W. Y. Kim and Y. S. Kim, “A region-based shape descriptor using Zernike moments, “ Signal Processing: Image Communication Vol. 16, pp. 95-102, 2000.
16. H. K. Kim and J. D. Kim, “Region-based shape descriptor invariant to rotation, scale and translation,”in Signal Processing: Image Communication Vol. 16, pp. 87-93, 2000.
17. M. Swain and D. Ballard, “Color indexing,” International Journal of Computer Vision, Vol. 7, No. 1, pp. 11-32, 1991.
18. M. Stricker and M. Orengo, “Similarity of Color Images,” in Proc. SPIE Storage and Retrieval for Still Image and Video Databases III, pp. 381-392, San Jose, CA, USA, February 1995.
19. J. Huang, S. K. Kumar, M. Mitra, W. Zhu and R. Zabih, “Image indexing using color correlograms, ” in Proc. CVPR Int. Conf., pp. 762-768, 1997.
20. X. S. Zhou and T. S. Huang, “ Image retrieval: feature Primitives, feature representation, and relevance feedback,” in Proc. IEEE Workshop on Content-Based Access of Image and Video Libraries, in Conjunction with CVPR''00, pp. 10-14, 2000.
21. Laine and J. Fan, ” Texture classification by wavelet packet signatures,” IEEE Tran. Pattern Anal. Machine Intell., Vol. 15, No. 11, pp. 1186-1191, 1993.
22. M. Mehtre, M. S. Kankanhalli, and W. F. Lee, “Content-based image retrieval using a composite color-shape approach,” Information Processing and management, Vol. 34 No. 1, pp. 109-120, 1998.
23. M. S. Kankanhalli, B. M. Mehtre, and J. K. Wu, “Cluster-based color matching for image retrieval,” Pattern Recognition, Vol. 29, No. 4, pp. 701-708, 1996.
24. K. Jain, A. Vailaya, “Image retrieval using color and shape,” Pattern Recognition, Vol. 29, pp. 1233-1244, 1996.
25. Vailaya, A. K. ZhongYuJam, “A hierarchical system for efficient image retrieval,” in Proceedings of IEEE International Conference on Pattern Recognition, 1996.
26. G. Cortelazzo, G. A. Mian, G. Vezzi, P. Zamperoni, “Trademark shapes description by stringmatching techniques,” Pattern Recognition, Vol. 27, No.8, pp. 1005-1018, 1994.
27. Bimbo, P. Pala, “Image Indexing using shape-based visual features,” in Proceedings of IEEE International Conference on Pattern Recognition, 1996.
28. R. C. Gonzalez and Richard E. Woods, Digital Image Processing, 1992.
29. O. Maron and A. L. Ratan, “Multiple-instance learning for natural scene classification,” in Proc. Machine Learning Int. Conf., 1998.
30. J. L. Shih and P. C. Chung, “2-D Invariant pattern recognition using a backpropagation network improved by distributed associative memory,” in Proceedings of Visual Communications and Image Processing, pp. 140-147, 1995.
31. N. Akrout, R. Prost, and R. Goutte, “Image compression by vector quantization: a review focused on codebook generation,” Image and Vision Computing, Vol. 12, No. 10, pp. 627-637, 1994.
32. Y. Deng and B. S. Manjunath, “ An efficient low-dimensional color indexing scheme for region-based image reitrieval,”, in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing, Vol. 6, pp. 3017-3020, 1999.
33. M. Stricker and A. Dimai, “Color indexing with weak spatial constrains,” in Proc. SPIE Storage and Retrieval for Still Image and Video Databases IV, Vol. 2670 pp. 29-40, 1996.
34. S. Manjunath, Jens-Rainer Ohm, Vinod V. Vasudevan and Akio Yamada, “Color and texture descriptors,” IEEE Tran. Circuits Systems Vedio Technol (Special Issue on MPEG-7), Vol. 11, No. 6, pp. 703-715, June 2001.
35. MPEG-7 Information Technology-Multimedia Content Descriptor Interface-Part3: Visual. Final Committee Draft, ISO/IEC/JTC1/SC29/WG11/N4062, Mar. 2001.
36. MPEG-7 Visual Part of Experimentation Model Version 9.0, Akio Yamada, Mark Pickering, Sylvie Jeannin, Leszek Cieplinski, Jens Rainer Ohm and Munchurl Kim, Eds., ISO/IEC/JTC1/SC29/WG11/N3914, Jan. 2001.
37. Y. Deng, B. S. Manjunath, C. Kenney, M. S. Moore, H. Shin, “An efficient color representation for image retrieval,” IEEE Tran. Image Processing, Vol. 10, No. 1, pp. 140-147, Jan. 2001.
38. S. Manjunath, Jens-Rainer Ohm, Vinod V. Vasudevan and Akio Yamada, “MPEG-7 visual shape descriptors,” IEEE Tran. Circuits Systems Vedio Technol (Special Issue on MPEG-7), Vol. 11, No. 6, pp. 716-719, June 2001.
39. Google, Demo: http://www.google.com/