臺灣博碩士論文加值系統

近年來由於寬頻網路、高性能個人電腦及工作站、音訊/視訊壓縮標準，及許多應用，諸如數位圖書館、醫學資料庫、商標及著作權資料庫、地理資訊系統、隨意視訊系統等之來臨，多媒體資訊系統愈來愈重要。因為要儲存、處理影像/視訊資料需要使用大量的記憶空間及計算能力，所以，影像資料庫系統中的影像/視訊資料需要建立有效的索引、儲存、查詢機制。在本研究中，針對以特徵為基礎之影像資料庫系統，我們將使用快速叢聚技術及基因法則建立有效的索引及搜索策略。
在本研究中，每一個查詢或儲存的影像都以從該影像抽取的一組特徵代表。為了要評估查詢影像的排名順序，我們將使用合適的相似度量(距離函數)。我們將使用一系列的快速叢聚技術把影像資料庫系統中的影像S = {x(1), x(2), …, x(Q)} 分為K群，其對應的群重心是{z1, z2, …, zK}。一個查詢影像(特徵向量)利用其與K個群重心的距離決定其最近的C群，接著其最相似的影像則是利用基因法則從這最近的C群中決定，優良的實驗結果證實了所提的方法的可適性。

Multimedia information systems are becoming increasingly important with the advent of broadband networks, high-powered PC’s and workstations, audio/visual compression standards, and many applications such as digital libraries, medical databases, trademark and copyright databases, geographic information systems, and video-on-demand systems. Because visual media data require a large amount of memory and computing power for storage and processing, it is greatly desired to efficiently index, store, and retrieve the visual information from image database systems. In this study, efficient indexing and searching strategies for feature-based image database systems using fast clustering and genetic algorithms are proposed.
Here each query or stored image is represented by a set of features (a feature vector) extracted from the image. A suitable similarity measure (distance function) is utilized to evaluate the ranks of the retrieved images. A set of fast clustering algorithms (a set of inequalities) is used to partition the Q images (feature vectors) in the image database system S = {x(1), x(2), …, x(Q)} into K clusters with K cluster centers {z1, z2, …, zK}. A query image (feature vector) first determines its C closest clusters among the K clusters (with respective to the K cluster centers). Then the most similar images for the query image are determined within the C closest clusters using genetic algorithms. Good simulation results show the feasibility of the proposed approach.

摘 要i
ABSTRACTii
ACKNOWLEDGEMENTSiii
TABLE OF CONTENTSiv
LIST OF FIGURESvi
LIST OF TABLESix
CHAPTER 1INTRODUCTION1
1.1Motivation1
1.2Survey of Related Researches4
1.3Overview of Proposed Approaches11
1.4Thesis Organization12
CHAPTER 2FAST CLUSTERING AND GENETIC ALGORITHMS14
2.1Clustering Algorithms14
2.2Fast Clustering Algorithms15
2.3Genetic Algorithms24
CHAPTER 3PROPOSED INDEXING AND SEARCHING STRATEGIES FOR IMAGE DATABASE SYSTEMS27
3.1Features Extracted From Uncompressed Images27
3.2DCT-Based Features Extracted From Blocked DCT-Based Compressed Images34
3.3Proposed Indexing and Searching Strategies for Image Database Systems Using Fast Clustering and Genetic Algorithms35
CHAPTER 4SIMULATION RESULTS47
CHAPTER 5DISCUSSIONS AND CONCLUSIONS74
5.1Discussions74
5.2Conclusions75
REFERENCES76

[1]M. Orzessek and P. Sommer, ATM & MPEG-2 Integrating Digital Video into Broadband Networks. New Jersey: Prentice Hall PTR, 1998.
[2]R. C. Gonzalez and R. E. Woods, Digital Image Processing. Reading, Massachusetts: Addison-Wesley, 1992.
[3]W. B. Pennebaker and J. L. Mitchell, JPEG: Still Image Data Compression Standard. New York: Van Nostran Reinhold, 1993.
[4]Video codec for audiovisual services at p´64 kbit/s, CCITT Recommendation H.261, 1990.
[5]J. L. Mitchell, W. B. Pennebaker, C. E. Fogg, and D. J. LeGall, MPEG Video Compression Standard. New York: Chapman & Hall, 1997.
[6]B. G. Haskell, A. Puri, and A. N. Netravali, Digital Video: An Introduction to MPEG-2. New York: Chapman & Hall, 1997.
[7]Video coding for low bitrate communication, ITU-T Recommendation H.263, May 1996.
[8]F. Idris and S. Panchanathan, “Review of image and video indexing techniques,” J. of Visual Communication and Image Representation, Vol. 8, No. 2, pp. 146-166, 1997.
[9]C. W. Chang and S. Y. Lee, “Video content representation, indexing, and matching in video information systems,” J. of Visual Communication and Image Representation, Vol. 8, No. 2, pp. 107-120, 1997.
[10]G. Amato, G. Mainetto, and P. Savino, “An approach to a content-based retrieval of multimedia data,” Multimedia Tools and Applications, Vol. 7, pp. 9-36, 1998.
[11]M. Flickner, et al., “Query by image and video content: the QBIC system,” IEEE Computer, Vol. 28, No. 9, pp. 23-32, 1995.
[12]J. R. Bach, et al., “The Virage image search engine: an open framework for image management,” in Proc. of SPIE, Conf. on Visual Communication and Image Processing, 1996.
[13]A. Pentland, R. W. Picard, and S. Sclaroff, “Photobook: tools for content-based manipulation of image database,” in Proc. of SPIE: Storage and Retrieval for Image and Video Database II, Bellingham, Wash., 1994, Vol. 2185, pp. 34-47.
[14]ISO/IEC JTC1/SC29/WG11, Coding of Moving Pictures and Audio (MPEG 97), Oct. 1997.
[15]ISO/IEC JTC1/SC29/WG11, Coding of Moving Pictures and Audio (MPEG 98), July 1998.
[16]C. Faloutsos, “Access methods for text,” ACM Computing Surveys, Vol. 1, No. 1, pp. 49-74, 1985
[17]W. B. Croft and P. Savino, “Implementing ranking strategies using text signatures,” ACM Trans. on Office Information Systems, Vol. 6, No. 1, pp. 42-62, 1988.
[18]A. K. Jain and A. Vailaya, “Image retrieval using color and shape,” Pattern Recognition, Vol. 29, No. 8, pp. 1233-1244, 1996.
[19]Y. Alp Aslandogan and Clement T. Yu, “Techniques and Systems for image and video retrieval,” IEEE Trans. on Knowledge and Data Engineering, Vol. 11, No. 1, pp. 56-63, 1999.
[20]Z. J. Zheng and H. C. Leung, “Automatic image indexing for rapid content-based retrieval,” in Proc. of IEEE Int. Workshop on Multimedia Database Management Systems, Blue Mountain Lake, NY, USA, 1996, pp. 38-45.
[21]T. S. Huang and Y. Rui, “Image retrieval: past, present and future,” in Proc. of Int. Symposium on Multimedia Information Processing, Taipei, Taiwan, R. O. C, 1997, pp. 12-29.
[22]S. Santini and R. Jain, “Similarity queries in image databases,” in Proc. of IEEE Conf. on Computer Vision and Pattern Recognition, San Francisco, CA, USA, 1996, pp. 646-651.
[23]J. R. Smith, “Image retrieval evaluation,” in Proc. of IEEE Workshop on Content-Based Access of Image and Video Libraries, Santa Barbara, CA, USA, 1998, pp. 112-113.
[24]C. H. Lee and L. H. Chen, “Fast closest codeword search algorithm for vector quantisation,” IEE Proc.-Vision Image Signal Processing, Vol. 141, No. 3, pp. 143-148, 1994.
[25]C. H. Lee and L. H. Chen, “High-speed closest codeword search algorithms for vector quantization,” Signal Processing, Vol. 43, pp. 323-331, 1995.
[26]C. H. Lee and L. H. Chen, “A fast search algorithm for vector quantization using mean pyramids of codewords,” IEEE Trans. on Communications, Vol. 43, No. 2/3/4, pp. 1697-1702, 1995.
[27]S. C. Tai, C. C. Lai, and Y. C. Lin, “Two fast nearest neighbor searching algorithms for image vector quantization,” IEEE Trans. on Communications, Vol. 44, No. 12, pp. 1623-1628, 1996.
[28]S. J. Baek, B. K. Jeon, and K. M. Sung, “A fast encoding algorithm for vector quantization,” IEEE Signal Processing Letters, Vol. 4, No. 12, pp. 325-327, 1997.
[29]Y. C. Lin and S. C. Tai, “A fast Linde-Buzo-Gray Algorithm in Image Vector Quantization,” IEEE Trans. on Circuits and Systems-II: Analog and Digital Signal Processing, Vol. 45, No. 3, pp. 432-435, 1998.
[30]C. C. Chang and Y. C. Hu, “A fast LBG codebook training algorithm for vector quantization,” IEEE Trans. on Consumer Electronics, Vol. 44, No. 4, pp.1201-1208, 1998.
[31]M. J. Swain and D. H. Ballard, “Color indexing,” Int. J. of Computer Vision, Vol. 7, No. 1, pp. 11-32, 1991.
[32]B. M. Mehtre, M. S. Kankanhalli, A. D. Narasimhalu, and G. C. Man, “Color matching for image retrieval,” Pattern Recognition Letters, Vol. 16, pp. 325-331, 1995.
[33]B. V. Funt and G. D. Finlayson, “Color constant color indexing,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 17, No. 5, pp. 522-529, 1995.
[34]X. Wan and C. -C. J. Kuo, “Image retrieval with an octree-based color indexing scheme,” in Proc. of 1997 IEEE Int. Symposium on Circuits and Systems, Hong Kong, 1997, Vol. 2, pp. 1357-1360.
[35]X. Wan and C. -C. J. Kuo, “A new approach to image retrieval with hierarchical color clustering”, IEEE Trans. on Circuits and Systems for Video Technology, Vol. 8, No. 5, pp. 628-643, 1998.
[36]A. D. Bimbo, M. Mugnaini, P. Pala, and F. Turco, “Visual querying by color perceptive regions,” Pattern Recognition, Vol. 31, No. 9, pp. 1241-1253, 1998.
[37]J. Huang, S. R. Kumar, M. Mitra, W. J. Zhu, and R. Zabih, “Image indexing using color correlograms,” in Proc. of IEEE Computer Society Conf. on Computer Vision and Pattern Recognition, San Juan, Puerto Rico, 1997, pp. 762-768.
[38]G. Pass and R. Zabih, “Histogram refinement for content-based image retrieval,” in Proc. of Third IEEE Workshop on Applications of Computer Vision, Sarasota, FL, USA, 1996, pp. 96-102.
[39]H. C. Lin, “Content-based image retrieval by color, texture, and shape,” Ph.D Thesis, Department of Computer Science and Information Engineering, National Tsing Hua University, Hsinchu, Taiwan, R. O. C, 1997.
[40]F. Liu and R. W. Picard, “Periodicity, directionality, and randomness: wold features for image modeling and retrieval,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 18, No. 7, pp. 722-733, 1996.
[41]B. S. Manjunath and W. Y. Ma, “Texture features for browsing and retrieval of image data,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 18, No. 8, pp. 837-842, 1996.
[42]G. L. Gimel’Farb and A. K. Jain, “On retrieving textured images from an image database,” Pattern Recognition, Vol. 29, No. 9, pp. 1461-1483, 1996.
[43]R. Mehrotra and J. E. Gary, “Similar-shape retrieval in shape data management,” IEEE Computer, Vol. 28, No. 9, pp. 57-62, 1995.
[44]B. Gunsel and A. M. Tekalp, “Shape similarity matching for query-by-example,” Pattern Recognition, Vol. 31, No. 7, pp. 931-944, 1998.
[45]A. D. Bimbo and P. Pala, “Visual image retrieval by elastic matching of user sketches,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 19, No. 2, pp. 121-132, 1997.
[46]A. K. Jain, Y. Zhong, and S. Lakshmanan, “Object matching using deformable templates,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 18, no. 3, pp. 267-278, 1996.
[47]S. Belongie, C. Carson, H. Greenspan, and J. Malik, “Color- and texture-based image segmentation using EM and its application to content-based image retrieval,” in Proc. of IEEE Sixth Int. Conf. on Computer Vision, 1998, pp. 675-682.
[48]M. Shneier and M. Abdel-Mottaleb, “Exploiting the JPEG compression scheme for image retrieval,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 18, No. 8, pp. 849-853, 1996.
[49]H. J. Bae and S. H. Jung, “Image retrieval using texture based on DCT,” in Proc. of 1st IEEE Int. Conf. on Information Communications and Signal Processing, Singapore, 1997, Vol. 2, pp. 1065-1068.
[50]S. W. Smoliar and H. Zhang, “Content-based video indexing and retrieval,” IEEE Multimedia, Vol. 1, No. 2, pp. 62-72, 1994.
[51]E. Ardizzone and M. L. Cascia, “Automatic video database indexing and retrieval,” Multimedia Tools and Applications, Vol. 4, pp. 29-56, 1997.
[52]S. F. Chang, W. Chen, H. J. Meng, H. Sundaram, and D. Zhong, “A fully automated content-based video search engine supporting spatiotemporal queries,” IEEE Trans. on Circuits and Systems for Video Technology, Vol. 8, No. 5, pp. 602-615, 1998.
[53]Y. Deng and B. S. Manjunath, “Content-based search of video using color, texture, and motion,” in Proc. of IEEE Int. Conf. on Image Processing, Santa Barbara, CA, USA, 1997, Vol. 2, pp. 534-537.
[54]Y. S. Avrithis, N. D. Doulamis, A. D. Doulamis, and S. D. Kollias, “Efficient content representation in MPEG video databases,” in Proc. of IEEE Workshop on Content-Based Access of Image and Video Libraries, Santa Barbara, CA, USA, 1998, pp. 91-95.
[55]H. Samet, “The quadtree and related hierarchical data structures,” Comput. Surveys, Vol. 16, No. 2, pp. 187-260, 1984.
[56]J. T. Robinson, “The K-D-B-tree: a search structure for large multidimensional dynamic indexes,” in Proc. of ACM SIGMOD Int. Conf. on Management of Data, 1981, pp. 10-18.
[57]J. Nievergelt, H. Hinterberger, and K. C. Sevcik, “The grid file: an adaptable, symmetric multikey file structure,” ACM Trans. on Database Systems, Vol. 9, No. 1, pp. 38-71, 1984.
[58]Q. Yang, A. Vellaikal, and S. Dao, “MB+-tree: a new index structure for multimedia databases,” in Proc. of IEEE Int. Workshop on Multi-Media Database Management Systems, 1995, pp. 151-158.
[59]D. B. Lomet and B. Salzberg, “The hB-tree: a robust multi-attribute indexing method,” ACM Trans. on Database Systems, Vol. 15, No. 4, pp. 625-658, 1990.
[60]B. Seeger and H. P. Kriegel, “The buddy-tree: an efficient and robust access method for spatial database systems,” in Proc. of the 16th Int. Conf. on Very Large Databases, 1990, pp. 590-601.
[61]A. Guttman, “R-trees: a dynamic index structure for spatial searching,” in Proc. of ACM SIGMOD Int. Conf. on Management of Data, 1984, pp. 47-57.
[62]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. of ACM SIGMOD Int. Conf. on Management of Data, 1990, pp. 322-331.
[63]T. Sellis, N. Roussopoulos, and C. Faloutsos, “The R+-tree: a dynamic index for multidimensional objects,” in Proc. of the 13th Int. Conf. on Very Large Databases, 1987, pp. 507-518.
[64]N. Katayama and S. Satoh, “The SR-tree: an index structure for high-dimensional nearest neighbor queries,” in Proc. of ACM SIGMOD Int. Conf. on Management of Data, 1997, pp. 369-380.
[65]K. Chakrabarti and S. Mehrotra, “The hybrid tree: an index structure for high dimensional feature spaces,” in Proc. of the 15th IEEE Int. Conf. on Data Engineering, 1999, pp. 440-447.
[66]G. H. Cha and C. W. Chung, “A new indexing scheme for content-based image retrieval,” Multimedia Tools and Applications, Vol. 6, pp. 263-288, 1998.
[67]O. Gunther and J. Bilmes, “Tree-based access methods for spatial databases: implementation and performance evaluation,” IEEE Trans. on Knowledge and Data Engineering, Vol. 3, No. 3, pp. 342-356, 1991.
[68]H. D. Tagare, “Increasing retrieval efficiency by index tree adaptation,” in Proc. of IEEE Workshop on Content-Based Access of Image and Video Libraries, 1997, pp. 28-35.
[69]D. A. White and R. Jain, “Similarity Indexing with the SS-tree,” in Proc. of the 12th IEEE Int. Conf. on Data Engineering, 1996, pp. 516-523.
[70]Y. Gong, C. H. Chuan, and G. Xiaoyi, “Image indexing and retrieval based on color histograms,” Multimedia Tools and Applications, Vol. 2, pp. 133-156, 1996.
[71]Y. Gong, G. Proietti, and C. Faloutsos, “Image indexing and retrieval based on human perceptual color clustering,” in Proc. of 1998 IEEE Computer Society Conf. on Computer Vision and Pattern Recognition, Santa Barbara, CA, USA, 1998, pp. 578-583.
[72]J. Hafner, H. S. Sawhney, W. Equitz, M. Flickner, and W. Niblack, “Efficient color histogram indexing for quadratic form distance functions,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 17, No. 7, pp. 729-736, 1995.
[73]M. Vazirgiannis, Y. Theodoridis, and T. Sellis, “Spatio-temporal composition and indexing for large multimedia applications,” Multimedia Systems, Vol. 6, pp. 284-298, 1998.
[74]S. S. Chen, “Content-based indexing of spatial objects in digital libraries,” J. of Visual Communication and Image Representation, Vol. 7, No. 1, pp. 16-27, 1996.
[75]J. K. Wu, “Content-based indexing of multimedia databases,” IEEE Trans. on Knowledge and Data Engineering, Vol. 9, No. 6, pp. 978-989, 1997.
[76]S. K. Chang, Q. Y. Shi, and C. W. Yan, “Iconic indexing by 2-D strings,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. PAMI-9, No. 3, pp. 413-428, 1987.
[77]S. K. Chang, C. W. Yan, D. C. Dimitroff, and T. Arndt, “An intelligent image database system,” IEEE Trans. on Software Engineering, Vol. 14, No. 5, pp. 681-688, 1988.
[78]S. Y. Lee, M. K. Shan, and W. P. Yang, “Similarity retrieval of iconic image database,” Pattern Recognition, Vol. 22, No. 6, pp. 675-682, 1989.
[79]K. Shearer, S. Venkatesh, and D. Kieronska, “Spatial indexing for video databases,” J. of Visual Communication and Image Representation, Vol. 7, No. 4, pp. 325-335, 1996.
[80]F. J. Hsu, S. Y. Lee, and B. S. Lin, “Similarity retrieval by 2D C-Trees matching in image databases,” J. of Visual Communication and Image Representation, Vol. 9, No. 1, pp. 87-100, 1998.
[81]A. K. Jain and R. C. Dubes, Algorithms for Clustering Data. Englewood Cliffs, New Jersey: Prentice Hall 1988.
[82]A. K. Jain and A. Vailaya, “Shape-based retrieval: A case study with trademark image databases,” Pattern Recognition, Vol. 31, No. 9, pp. 1369-1390, 1998.
[83]G. Pass, R. Zabih, and J. Miller, “Comparing images using color coherence vectors,” in Proc. of the fourth ACM Multimedia, 1996, pp. 65-78.
[84]R. M. Haralick, K. Shanmugam, and I. Dinstein, “Textural features for image classification,” IEEE Trans. on Systems, Man, and Cybernetics, Vol. SMC-3, No. 6, pp. 610-621, 1973.
[85]M. K. Hu, “Visual pattern recognition by moment invariants,” IRE Trans. on Information Theory, Vol. IT-8, pp. 179-187, 1962.
[86]R. Duda and P. Hart, Pattern Classification and Scene Analysis. New York: Wiley, 1973.
[87]C. G. Looney, Pattern Recognition Using Neural Networks. New York: Oxford, 1997.
[88]J. H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology Control, and Artificial Intelligence. London, England: MIT Press, 1992.
[89]D. E. Goldberg, Genetic Algorithms: Search, Optimization and Machine Learning. Reading, Massachusetts: Addison-Wesley, 1989.
[90]G. Winter, J. P’eriaux, M. Gal’an, and P. Cuesta (Eds.), Genetic Algorithms in Engineering and Computer Science. Chichester, West Sussex, England: John Wiley & Sons, 1995.
[91]Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs. New York: Springer-Verlag, 1992.
[92]M. Mitchell, An Introduction to Genetic Algorithms. London, England: MIT Press, 1996.
[93]M. Gen and R. Cheng, Genetic Algorithms and Engineering Design. New York: John Wiley & Sons, 1997.
[94]W. Siedlecki and J. Sklansky, “A note on genetic algorithms for large-scale feture selection,” Pattern Recognition Letters, Vol. 10, pp. 335-347, 1989.
[95]H. Saito and M. Mori, “Application of genetic algorithms to stereo matching of images,” Pattern Recognition Letters, Vol. 16, pp. 815-821, 1995.
[96]R. M. Haralick, “Statistical and structural approaches to texture,” Proc. of the IEEE, Vol. 67, No. 5, pp. 786-804, 1979.
[97]M. Nadler and E. P. Smith, Pattern Recognition Engineering. New York: John Wiley & Sons, 1993.
[98]R. W. Conners and C. A. Harlow, “Towards a structural textural analyzer based on statistical methods,” Computer Graphics and Image Processing, Vol. 12, No. 3, pp. 224-256, 1980.
[99]R. Y. Wong, “Scene matching with invariant moments,” Computer Graphics and image processing, Vol. 8, pp. 16-24, 1978.
[100]C. C. Chen, “Improved moment invariants for shape discrimination,” Pattern Recognition, Vol. 26, No. 5, pp. 683-686, 1993.
[101]B. M. Mehtre, M. S. Kankanhalli, and W. F. Lee, “Shape measures for content based image retrieval: a comparison,” Information Processing & Management, Vol. 33, No. 3, pp. 319-337, 1997.
[102]J. J. Leou and L. W. Kang, “Fast indexing and searching strategies for image database systems,” in Proc. of 1999 Workshop on Consumer Electronics: Digital Video and Multimedia Communications, Taipei, Taiwan, Republic of China, 1999, pp. 183-188.
[103]P. C. Chen and T. Pavlidis, “Segmentation by texture using a co-occurrence matrix and a split-and-merge algorithm,” Computer Graphics and Image Processing, Vol. 10, No. 2, pp. 172-182, 1979.