臺灣博碩士論文加值系統

內容式影像擷取(Content-based image retrieval)已成為現今設計影像資料庫(Image database)的趨勢。本論文提出了一套影像資料庫的智慧型影像擷取系統。本系統結合了顏色，形狀和空間關係等特徵來做圖形相似性的索引和測量。本論文比較了數種廣泛地應用在電腦繪圖上的顏色空間，以便做到顏色的簡化既顏色叢集(color clustering)。另外，根據顏色叢集的方法，本文提出一套自動產生圖形資料庫索引的機制，此索引機制可使圖形的過濾更有效率。
本論文並提出了一個類似播種(Seed-Filling)的演算法，可以順利的求得影像中物件的形狀及空間的關係。由於一般而言，使用者很難確定物件間的距離，所以本系統使用定性的(qualitative)空間關係來分析空間的相似性。另外，本系統所提供的圖形式使用者介面及繪圖工具，可以讓使用者以載入或描繪影像的方式，輕鬆的查詢影像。除此之外，本系統的回饋學習機制更可增強搜尋的準確度。我們的經驗證明本論文所提之方法，可讓使用者有效地找出所求之影像。

Content-based image retrieval has become more desirable for developing large image database. This thesis presents an intelligent method of retrieving images from an image database. This system combines color, shape and spatial features to index and measure similarity of images. Several color spaces that widely used in computer graphic were discussed and compared for color clustering. In addition, this dissertation propose a new automatic indexing scheme of image database according to our clustering method and color sensation, which could be used to retrieve image efficiently.
As a technical contribution, a Seed-Filling like algorithm that could extract the shape and spatial relationship feature of image is proposed. Due to the difficulty of determining how far objects are separated, this system uses qualitative spatial relations to analyze object similarity. Also, the system is incorporated with a visual interface and a set of tools, which allows the users to express the query by specify or sketch the images conveniently. Besides, the feedback learning mechanism enhances the precision of retrieval. The experience shows that the system is able to retrieve image information efficiently by the proposed approaches.

Contents
Chapter 1 Introduction1
1.1 Motivation1
1.2 Query by Image Content3
1.3 Overview8
Chapter 2 Related Work11
2.1 Color-based retrieval11
2.2 Shape-based retrieval13
2.3 Retrieval by spatial relations15
2.4 Index methods18
2.5 Systems for image retrieval19
Chapter 3 Color Space and Color Clustering27
3.1 Selection of The Color Space27
3.1.1 RGB Color Space27
3.1.2 CMY Color Space29
3.1.3 C.I.E. L*u*v* Color Space30
3.1.4 YUV, YIQ and YCbCr Color Space32
3.1.5 HSI, HSV and HLS Color Space33
3.2 Color Clustering and Normalization34
Chapter 4 Extraction of Features37
4.1 Color Feature Extraction37
4.2 Shape Feature Extraction38
4.2.1 Shape Extraction39
4.2.2 Edge Detection40
4.2.3 Shape Representation and Normalization41
4.3 Spatial Relation Feature Extraction44
Chapter 5 The Similarity Measure of Features46
5.1 The Similarity Measure of Colors46
5.1.1 The Similarity of two Colors46
5.1.2 The Color Similarity of two Images47
5.2 The Similarity Measure of Shape49
5.3 The Similarity Measure of Spatial relation50
Chapter 6 Management of Image Database56
6.1 The Architecture of Database58
6.2 The Indexing Scheme59
6.3 The Filter Mechanism61
Chapter 7 Procedure for Image Retrieval64
7.1 The Procedure of Online Query65
7.2 Query Interface66
7.3 Query Examples63
Chapter 8 Conclusion and Future Research74
8.1 Conclusion74
8.2 Future Research75
References76
Appendix A. Publication List85
Journal Publications85
Conference Publications86
Appendix B. “An Intelligent Content-based Image Retrieval System based on Color, Shape and Spatial Relations,“ Proceedings of the National Science Council, R.O.C., Part A: Physical Science and Engineering.89
Appendix C. “Indexing and Retrieval Scheme of the Image Database Based on Color and Spatial Relations,” Proc. IEEE International Conference on Multimedia & Expo 2000 (ICME’2000).90
List of Figures
1.1 Sketch of visual image retrieval system3
2.1 User interface of QBIC system23
2.2 User interface of Virage Search Engine24
2.3 User interface of Picasso system24
2.4 User interface of photobook system25
2.5 User interface of Netra system25
2.6 User interface of VisualSEEK system26
3.1 RGB color space28
3.2 The relation of RGB and CMYK30
3.3 Chromaticity diagram for CIE primary system31
3.4 HSI color space33
3.5 Procedure diagram for the color clustering and normalization35
3.6 The clustering 12*4*4 + 6 HSI color space36
4.1 Color histogram of image38
4.2 Example of a processed image. (a) Original image, (b) color clustering image, (c) shape extraction image, (d) refined image.40
4.3 An example image and the result after the edge detection process41
4.4 The turning angle representation of the object42
4.5 Use of orthogonal projection to find the centroid of the object43
4.6 The starting point of turning angle representation43
4.7 The 13 interval relations and 5 point-interval relations44
4.8 The orthogonal projection of the shape in X and Y coordinates45
6.1 The user interfaces and procedures of creating image database57
6.2 Structural diagram of the image database58
6.3 (a) Show an example of indexing an image (image ID: 1, the dominant colors of this image are 37 (00100101), 38 (00100110) and 154 (10011010) (b) Indexing another image (image ID: 2, the dominant colors of this image are 38 (00100110), 39 (00100111), 152(10011000) and 154(10011010)60
6.4 Show a filtering example of a query image (the dominant colors of this image are 37 (00100101), 38 (00100110), 39 (00100111), 152 (10011000) and 154 (10011010)62
7.1 Overview of the system architecture64
7.2 Query Interface67
7.3 Query by sketched image68
7.4 Query by modified image (cut a piece of image)68
7.5 Query by modified image (modify the query image)69
7.6 Query example based on color70
7.7 Query example based on shape70
7.8 Query by multiple query images71
7.9 Query example based on spatial relations72
List of Tables
3.1 YcbCr Color bars32
5.1 Starting and Ending Point Relations51
5.2 Point Relation Distance (PRD)52
5.3 The Extended Point-Interval Relation Distance53

[1]M. Flicker, H. S. Saehney, 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 Computers, 28(9), 23-32, 1995.
[2]J. R. Bach, C. Fuller, A. Gupta, A. Hampapur, B. Horowitz, R. Humphrey, R. Jain, and C. fe Shu, “The Virage image search engine: An open framework for image management,“ SPIE Storage and Retrieval for Still Image and Video Databases, 2760, 76-87, 1996.
[3]A. Pentland, R. Picard, and S. Sclaroff, “Photobook: Content-based manipulation of image databases,” International Journal of Computer Vision, 18(3), 233-254, 1996.
[4]J. R. Smith and S. F. Chang, “VisualSEEK: a fully automated content-base image query system,” Proceeding of ACM International Conference Multimedia, Boston, MA, 87-98, November. 1996.
[5]J. Dowe, “Content-based retrieval in multimedia imaging,” in Proc. SPIE Conf. on Visual Communications and Image Processing. 1993.
[6]W. Y. Ma and B. S. Manjunath, “ Netra: A toolbox for navigating large image databases,” in Proc. ICIP’97, Santa Barbara, CA, October, 568-571. 1997.
[7]Alshuth, P., Termes, C. Klauck, J. Kreiss and M. Roper. “IRIS image retrieval for images and video.” Proc. First Int. Workshop on Image Database and Multimedia Search, Amsterdam, August, 170-179. 1996.
[8]Wu, J. K., A, D. Narashihalu, B. M. Mehtre, C. P. Lam and Y. J. Gau. “CORE, a content-based retrieval engine for multimedia information systems.” Multimedia System, 3, 25-41, 1995.
[9]Jia Wang, Wen-jann yang and Raj Acharya, ”Color Clustering Techniques for Color-Content-Based Image Retrieval from Image Databases,” Proceeding of IEEE International Conference on Multimedia Computing and Systems, ICMCS, 442-449, Jun 3-6. 1997.
[10]M.J. Swain and .H. Ballard, "Color index,” Internal Journal of Computer Vision, 7(1), 11-32, 1991.
[11]Xia Wan and C.-C Jay Kuo, “Color Distribution Analysis and Quantization for Image Retrieval,” in SPIE storage an Retrieval for Image an Video Database IV, SPIE 2670, 9-16, Feb. 1996.
[12]E. Person and K. S. Fu, “Shape discrimination using Fourier Descriptors,” IEEE Trans. Sys. Man, 7, 170-179, 1977.
[13]D. Kapur, Y. N. Lakshman, and T. Saxena, "Computing invariants using elimination methods," in Proc. IEEE Int. Conf. on Image Proc., 1995.
[14]H. G. Barrow, "Parametric correspondence and chamfer matching: Two new techniques for image matching," in Proc 5th Int. Joint Conf. Artificial Intelligence, 1977.
[15]G. Borgefors, "Hierarchical chamfer matching: A parametric edge matching algorithm," IEEE Trans. on Pattern Analysis and Machine Intelligent, 10(November), 49-865, 1988.
[16]E. M. Arkin, L. Chew, D. Huttenlocher, K. Kedem, and J. Mitchell, "An efficiently computable metric for comparing polygonal shapes," IEEE on Pattern Analysis and Machine Intelligent, 13(March), 209-216, 1991.
[17]G. C.-H. Chuang and C.-C. J. Kuo, "Wavelet descriptor of planar curves: Theory and applications," IEEE Trans. Image Proc., 5, 56-70, January 1996.
[18]Michael Vazirgiannis, Yannis Theodoridis, and Timos Sellis ''Spatio - Temporal Composition in Multimedia Applications,'' in proceedings of the International Workshop on Multimedia Software Development, Berlin, Germany, March 25-26 1996, 120-127.
[19]Thomas Wahl, et. al., ''TIEMPO: Temporal Modeling and Authoring of Interactive Multimedia'' in proceedings of the International Conference on Multimedia Computing and Systems, Washington DC, U.S.A., May 15-18 1995, 274 -277.
[20]Mohammad Nabil, Anne H. H. Ngu, and John Shepherd, ''Picture Similarity Retrieval Using 2D Projection Interval Representation,'' IEEE Transactions on Knowledge and Data Engineering, 8(4), August 1996, 533-539.
[21]Soo-Chang Pei an Hui-Lirng Shiue, “Indexing and Retrieval of Color Image Database,” Proceeding of Conference on Computer Vision, Graphics and Image Processing, Taipei, 196-199, 1998.
[22]Youping Niu, M. Tamer Ozsu and Xiaobo Li, ”2D-h Trees: An Index Scheme for Content-Base Retrieval of Image in Multimedia Systems,” Proceeding of IEEE International Conference on Intelligent Processing Systems, 1710-1715, October 28-31. 1997.
[23]Canny, J., ”A Computational Approach to Edge Detection”, IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-8. (6): 679-698, 1986.
[24]Shen, J and S. Castan., ”An Optimal Linear Operator for Step Edge Detection”, Computer Vision, Graphics, and Image Processing: Graphical Model and Understanding, 54(2), 112-133, 1992.
[25]Freeman, H., “ Computer processing of line drawing images”, Computer Survey, 6, 57-97, 1974.
[26]Yuan Y. Tang and Ching Y. Suen, “ Extraction of peripheral Shape Features in Chinese Character Recognition”, 377-379, 1994.
[27]James F. Allen, ''Maintaining Knowledge about Temporal Intervals,'' Communications of the ACM, 26(11), 1983.
[28]Keh, Huan-Chao, Timothy K. Shih, and Anthony Y. Chang “ Properties of Temporal Constraint Network for Supporting Distributed Multimedia Applications,” Journal of Computer Science and Information Management, 2(4), 1999, 15-26.
[29]John Z. Li, M. TamerOzsu, and Duane Szafron, ''Spatial Reasoning Rules in Multimedia Management Systems,'' in proceedings of the 1996 Multimedia Modeling international conference (MMM'96), Toulouse, France, November 12- 15, 1996, 119-133.
[30]Thomas D. C. Little and Arif Ghafoor, ''Spatio-Temporal Composition of Distributed Multimedia Objects for Value-Added Networks,'' IEEE Computer, October 1991, 42-50.
[31]Alberto Del Bimbo, “Visual Information Retrieval,” Academic Press, San Francisco, California, 1999.
[32]Shoji Tominaga, “Color Classification of Natural Color Image,” COLOR research and application, 17(4), Aug. 1992, 230-239.
[33]Shih-Fu Chang and John R. Smith, “Extracting Multi-Dimensional Signal Features for Content-Based Visual Query,” SPIE Symposium on Visual Communications and Signal Processing, May 1995.
[34]H.V. Jagadish, ''A Retrieval Technique for Simple Shape,'' in proceedings of ACM SIGMOD 1991International Conference on Management of Data, May 29-31 1991, 208-217.
[35]C. H. The, and R. T. Chin, ''On Digital Approximation of Moment Invariants,'' in Computer Vision, Graphics, and Image Processing, 33, 1986, 318-326.
[36]R. A. Schmidt, ''Fast Generation of Chain-Code Image Descriptors, '' in proceedings of the IEEE Internal Conference on Robotics and Automation, St. Louis, MO, 1985, 886-872.
[37]T. Phillips, ''A Shrinking Technique for Complex Object Decomposition,'' in Pattern Recognition Letters, 3, 1985, 271-277.
[38]H. Samet, Design and Analysis of Spatial Data Structures, Addison-Wesley, Reading, MA, 1990.
[39]Hanan Samet and Aya Soffer, ''MARCO: MAp Retrieval by COntent,'' IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(8), August 1996, 783-798.
[40]Judd, D.B. and G. Wyszecki. 1975. Color in Business, Science and Industry. New York: John Wiley.
[41]Boynton, R.M. Human color perception. In Science of Vision, Leibovic K.N. (ed.). NY: Springer, 211-253. 1990.
[42]Rosenfeld, A. and J.L. Pfalz. 1968. “Distance functions on digital pictures,” Pattern Recognition, 1, 33-61.
[43]Borgefors, G. “Distance transformations in digital images,” Computer Vision Graphics and Image Processing, 34, 344-371. 1986.
[44]Huttenlocher, D.P., G.A. Klanderman and W.J. Rucklidge. 1993. “Comparing images using the Hausdorff distance,” IEEE trans. on Pattern Analysis and Machine Intelligence, 15(9), 850-863.
[45]Shapiro, L. and R. Haralick. “Decomposition of two-dimensional shapes by graph-theoretic clustering,” IEEE Trans. on Pattern Analysis and Machine Intelligence, 1, 10-20. 1979.
[46]Shapiro, L.G. and R.M. Haralick. “Structural descriptions and inexact matching,” IEEE Trans. on Pattern Analysis and Machine Intelligence, 3(5), 504-519. 1981.
[47]Santini, S. and R. Jain. “Image databases are not database with images,” Proc. ICIAP’ 97, Firenze, Italy, 38-46.
[48]Basri, R. and D. Weinshall. “Distance Metric between 3D Models and 2D Images for Recognition and Classification,” AI Memo 1373, AI Lab., MIT, July. 1992.
[49]Pentland, A., R.W. Picard and S. Sclaroff. “Photobook: Tools for content-based manipulation of image databases,” Proc SPIE Storage and Retrieval for Image and Video Database, San Kose CA, February. 1994.
[50]Chang, S.K., Q.Y. Shi and C.W. Yan. Iconic indexing by 2D-strings. IEEE Trans. on Pattern Analysis and Machine Intelligence, PAMI-6(4), 484-492. 1987.
[51]Samet, H. Hierarchical representations of collections of small rectangles. ACM Computing Surveys, 20(4), 271-309. 1988.
[52]Egenhofer, M.J. and R. Franzosa. Point-set topological spatial relations. International Journal of Geographical Information System. 9(2), 1992.
[53]Shih, Timothy K. and Anthony Y. Chang, “The Algebra of Spatio-Temporal Intervals. 12th International Conference on Information Networking,” Japan, January 21-23. 1998.
[54]Nievergelt, J., H. Hinterberger and C. Sevcik. “The grid file: an adaptable, symmetric, multikey file structure,” ACM TODS, 9(March), 38-71. 1984.
[55]Samet, H. “The quad-tree and related data structures,” ACM Computing Surveys, 16(2), 187-259. 1984.
[56]Samet, H. “A geographic information system using quadtrees,” Pattern Recognition, 6, 674-656. 1984.
[57]Unnikrishnan, A., P. Shankar and Y. V. Venkatech. “Threaded linear hierarchical quadtrees for computation of geometric properties of binary images,” IEEE Transactions on Software Engineering, 14(5), 659-665. 1998.
[58]Samet, H. “Hierarchical representations. Of collections of small rectangles,” ACM Computing Surveys, 20(4), 271-309. 1988.
[59]Samet, H. The Design and Analysis of Spatial Data Structures. Reading, MA: Addison Wesley. 1989.
[60]Guttmann, “A. R-trees: a dynamic index structure for spatial searching,” Proc. ACM-SIGMOD International Conference on Management of Data, June, 47-57. 1984.
[61]Tanimoto, S. L. “An iconic/symbolic data structuring scheme,” In Pattern Recognition and Artificial Intelligence. New York: Academic Press. 1976.
[62]Egenhofer, M. J. “Reasoning about binary topological relations,” Proc. 2nd Symposium on the Design and Implementation of Large Spatial Databases, Springer Verlag, Lecture Notes in Computer Science, 143-160. 1991.
[63]Egenhofer, M. J. and R. Franzosa. “Point-set topological spatial relations,” International Journal of Geographical Information Systems, 5(2), 161-174. 1991.
[64]Chang, S. K. and S. H. Liu. “Picture indexing and abstraction techniques for pictorial databases,” IEEE Trans. on Pattern Analysis and Machine Intelligence, 6(July), 475-484. 1984.
[65]Chang, S. K., Q. Y. Shi and C. W. Yan. “Iconic indexing by 2-D strings,” IEEE Trans. on Pattern Analysis and Machine Intelligence, 9(3), 413-427. 1987.
[66]Hungert, E. “Extended Symbolic projection used in a knowledge structure for spatial reasoning,” Proc. 4th BPRA Conf. On Pattern Recognition, Springer, Cambridge, March. 1988.
[67]Holmes, P. D. and E. Jungert. “Symbolic and geometric connectivity graph methods for route planning in digitized maps,” IEEE Trans. on Pattern Analysis and Machine Intelligence, 14(5), 549-565. 1992.
[68] Lee, S. Y. and F. J. Hsu. “2D-C String: A new spatial knowledge representation for image database systems,” Picture Recognition, 23(10), 1077-1087. 1990.
[69]Lee, S. Y. and F. J. Hsu. “Picture algebra for spatial reasoning of iconic images represented in 2D C-String,” Pattern Recognition Letters, 12(July), 425-435. 1990.
[70]Lee, S. Y. and F. J. Hsu. “Spatial reasoning and similarity retrieval of images using 2D C-String knowledge representation,” Pattern Recognitions, 25(3), 1077-1088. 1992.
[71]Lee, S. Y., M. C. Yang and J. W. Chen “Signature file as a spatial filter for iconic image database. Journal of Visual Languages and Computing,” 3, 373-397. 1992.
[72]Del Bimbo, A. and P. Pala. “Retrieval by elastic matching of user sketches,” IEEE Trans. on Pattern Analysis and Machine Intelligence, 19(2), 121-132. 1997.
[73]Del Bimbo, A., M. Mugnaini, P. Pala and F. Turco. “Visual querying by colour perceptive regions,” Pattern Recognition, 31(9), 1241-1253. 1998.
[74]Ma, W. Y. and B. S. Manjunath. “Netra: A toolbook for navigating large image databases,” Proc. ICIP’97, Santa Barbara, CA, October, 568-571. 1997.
[75]Widrow, B. “The rubber mask technique-Ⅱ - pattern storage and recognition,” Pattern Recognition. 5, 199-211. 1973.
[76]Kass, M., A. Witkin and D. Terzopoulos. “Snakes: active contour models,” International Journal of Computer Vision, 3(6), 321:331. 1988.
[77]Burr, D. j. “A dynamic model for image registration,” Computer Graphics and Image Processing, 15(2), 102-112. 1981.
[78]Sclaroff, S. and A. Pentland. “A modal framework for correspondence and recognition,” Proc. ICCV, May. 1993.
[79]Burr, D. J. “Elastic matching of line drawing,” IEEE Trans. on Pattern Analysis and Machine Intelligence, 3(6), 708-713. 1981.
[80]Youille, A. L., K. Honda and C. Peterson, “Particle tracking by deformable templates,” Proc. Int. Joint Conf. On Neural Networks, 7-11. 1991.
[81]Youille, A. L., P. W. Hallinan and D. S. Cohen. “Feature extraction from faces using deformable templates,” Int. Journal of Computer Vision, 8(2), 99-111. 1992.
[82]Del Bimbo, A. and P. Pala. “Image retrieval by elastic matching of using sketches,” IEEE Trans. on Pattern Analysis and Machine Intelligence, 19(2), 121-132. 1997.
[83]Sclaroff, S. “Deformable prototypes for encoding shape categories in image databases,” Pattern Recognition, 30(4), 627-742. 1997.
[84]A. Guttman, “R-tree: a dynamic index structure for spatial searching,” in Proc ACM SIGMOD, 1984.
[85]T. Sellis, N. Roussopouls, and C. Faloutsos, “ The R+ tree: A dynamic index for multi-dimensional objects,” in Proc. 12th VLDB, 1987.
[86]D. Greene, “ An implementation and performance analysis of spatial data access,” in Proc ACM SIGMOD, 1989.
[87]N. Beckmann, H. P. Kriegel, R. Schneider, and B. Seeger, “The R*- tree: an efficient and robust access method for points and rectangles,” in Proc ACM SIGMOD, 1990.
[88]Y. Rui, K. Chakrabarti, S. Mehrotra, Y. Zhao, and T. S. Huang, “ Dynamic clustering for optimal retrieval in high dimensional multimedia databases,” in TR-MARS-10-97, 1997.
[89]R. O. Duda and P. E. Hart, Pattern Classification and Scene Analysis, John Wiley and Sons, Inc.
[90]H. Zhang and D. Zhang, “ A scheme for visual feature based image retrieval,” in Proc. SPIE Conference on Visual Communications and Image Processing, 1995.