摘要
图象特征表示是研究从图象中提取与组织特征,它是图象研究领域最基本最重要的工作,可以被用于图象数据库索引与查找、图象识别、图象压缩等各个方面。图象特征表示也属于人工智能的研究范畴,是人工智能中知识表示的一个复杂而有代表性的特例。因为图象是数学意义上的函数或矩阵,所以图象特征表示与各种数学运算方法有关,诸多的数学工具都被用于图象特征的提取与组织。迭代与分形是一种新的数学理论方法,基于迭代分形的图象特征表示的研究近年已经开始。
本文使用迭代与分形理论方法研究图象特征表示。主要工作,一是对函数迭代方面的内容进行研究,归纳并且发现了迭代分形覆盖特性与相关的混沌变化规律等;二是对图象的分形表示方法进行研究,给出了一个原图象索引查找方法,在理论研究方面,发现了图象集合的分形维数方面的规律;三是基于迭代方法,提出了两种图象特征表示方法。
本文的创新工作是:
1、对相关的函数迭代特性进行研究,提出了IFS(Iterated Function System,迭代函数系统)迭代分形覆盖的相交交点数目变化曲线(CIPN,The Curve of the Intersection Points Number)的概念,给出了CIPN的生成算法,研究了CIPN的变化特性。这些结果可以作为图象分形特征表示新方法的理论基础;另外,研究小波函数迭代的混沌分岔特性,给出了当其参数变化时出现的分岔图的一些规律性结论。这些结论对构造图象特征的迭代表示方法有很重要的参考价值。
2、基于分形方法,利用分形的二叉树结构,分别把图象的逐次分块重量与分块重心作为二叉树的节点,然后定义两种距离,构造类似R-树的最小包围盒,实现原图象的查找。这种方法对污染破损、变形等图象具有较好的查找效果;Korn等(2001)指出,使用R树结构对高维空间点集进行索引时,搜索时间复杂性取决于该点集的分形维数。基于分形维数理论,本文对图象构成的点集与其特征点集的分形维数进行分析,证明了奇异值特征点集与小波分解系数构成的点集的分形维数小于图象点集的分形维数,得到了序列图象作为高维点集时的分形维数远小于它所在空间的维数等结论。该结论说明,在使用图象特征对图象集合进行索引时,查找效率是比较高的。
3、基于IFS迭代覆盖,提出了一种图象特征表示方法。首先对图象的各种特征进行提取,再将提取得到的特征向量作为二元二次迭代式的系数组成迭代式,然后进行随机迭代,根据迭代出来点的分布特性对图象进行分类。由于二元二次迭代式收敛性不好,本文用乘以小波函数的方法来控制迭代的发散。与2003年著名学者Han等使用的方法
This paper is concern that image representation methods and theory on the fractal structure and iterate procedure. Meanwhile it shows some new experimental plans and theoretical results. The main assignments are as follows:
Study the Iterated Function System (IFS), study the covering properties when we draw the fractal graphs by the computers using the same iterated codes, give some meaningful experimental results and analyze some theoretical questions; When all the formula in the IFS are multiplied by a constant α, the behaviors of the system will be changed. The bifurcation diagram of a wavelet function is discussed. Its diagram shows specially that not only from period to chaotic state but also from the chaotic state to period. Above property of the IFS is used in the next parts of the paper.
Study the fractal representation method, give the exchange method of Hilbert alignment and the structure of binary tree. Use the structure of binary tree and the weight center to index the image, define two kinds of distances, index and search the image database. This index methods have a good search effect to the images which are polluted, damaged and deformed. Analyze the fractal dimensions of the image set and the feature set, prove that the fractal dimensions of some image feature sets are less than that of the image set at the high dimension space, give the conclusion that the fractal dimension of the image sequence is far less than the space dimension.
A new representation algorithm based on the iterated functions is applied to classify the football match images, the neighborhood and the learning factor of the SOF NN is used to enhance the robustness of the algorithm. In addition, a new scheme that employs the image as weight matrix is introduced to build a chaos neural network which has improved from the Hopfield neural network. In the network, each artificial neuron accumulates the stimulus effect which bases on the image weight matrix. So it is possible for the neural network to recall the embedded memories and associate the temporal image.
Although the fractal and iterated representation methods are all in the elementary period, they has already shown the potential. At the end of the paper, some existed questions of the fractal and iterated representation and the work in the next step are discussed.
引文
[1] 周洞汝,胡宏斌.视频数据库管理系统导论.北京:科学出版社,2000.
[2] 精英科技.视频压缩与音频编码技术.北京:国电力出版社,2001.
[3] 章毓晋.图像处理和分析.北京:清华大学出版社.
[4] 寿天德.视觉信息处理的脑机制.上海:上海科技教育出版社,1997.
[5] 郭爱克.计算神经科学.上海:上海科技教育出版社,2000.
[6] Tan Kian-lee, Beng Chin Ooi, Lay Foo Thiang. Indexing shapes in image databases using the centroid-radii model. Data&Knowledge Engineering. 2000,32:271-289.
[7] Sharlee Climer, Sanjiv K Bhatia. Image database indexing using JPEG coefficients. Pattern Recognition. 2002,35:2479-2488.
[8] Lin Tsong-Wuu. Compressed quadtree representations for storing similar images. Image and vision computing. 1997,15:833-843.
[9] Alfredo Ferro, Giovanni Gallo, Rosalba Giugno et al. Best-match retrieval for structured images. IEEE Transaction on Pattern Analysis and Machine Intelligence. 2001,23(7):707-718.
[10] Euripides G M Petrakis, Christos Falouts, Lin King-Ip. ImageMap: An Image Indexing Method Based on spatial Similarity. IEEE Transaction on Knowledge and Data Engineering. 2002,14(5):979—987.
[11] Aditya Vailaya, Mario A T Figueiredo, Anil K Jain et al. Image classification for content-based indexing. IEEE Transaction on Image Processing.2001,10(1): 117-129.
[12] Kakarala R, Ogunbona P. Signal analysis using a multi-resolution form of the singular value decomposition. IEEE Transaction on Image Processing. 2001,10(5): 724-735.
[13] Simone Santini, Amarnath Gupta, Ramesh Jain. Emergent Semantics through Interaction in Image databases. IEEE Transaction on Knowledge and Data Engineering. 2001,13(3):337-351.
[14] Chert Jau-Yuen, Charles A Bouman, John C Dalton. Hierarchical Browsing and Search of Large Image Databases. IEEE Transaction on Image Processing.2000,9(3):442-455.
[15] Chung Kuo_liang, Yao_hong Tsai, and Hu Fei_Ching. Space Filling Approach for Fast Window Query on Compressed Image. IEEE Transactions on Image Processing. 2000,9(12):2109-2116.
[16] Bongki Moon, H V Jagadish, Christos Faloutsos et al. Analysis of the Clustering Properties of the Hilbert Space_Filling Curve. IEEE Trans on Knowledge and Data Engineering. 2001,13(1):124-141.
[17] Jose Angel Gonzalez Rodpiguez. A Tutorial and Recipe For Moving Fractal Trees. Computer & Graphics. 1988,22(2-3):301-305.
[18] Kom F, Pagel B U, Faloutsos C. On the "Dimensionality Curse" and the "Self-Similarity Blessing". IEEE Trans on Knowledge and Data Engineering. 2001,13(1): 96-111.
[19] Nappi M, Polese G, Tortora G. FIRST: Fractal indexing and retrieval system for image databases. Image and Vision Computing. 1998,16(5): 1019-1031.
[20] Jean Michel, Marie-Julie-Hassane Essafi. Digital image indexing and retrieval by content using the fractal transform for multimedia databases.1092-9959/97IEEE E-mail {jmmjulie,hessafi} @ gaap. saclay, cea.fr.
[21] Teewoon tan, Hong Yan. Object recognition based on fractal neighbor distance. Signal Processing.2001,81: 2105-2129.
[22] Teewoon tan, Hong Yan. The fractal neighbor distance measure. Patter Recognition. 2002,35:1371-1387.
[23] Abhijit S. Pandya, Robert B.Macy. Pattern Recognition with Neural Networks in C++. Newyork: IEEE PRESS
[24] Taiga Yamasaki, Yoshinori Kataoka, Katsuro Kameyama et al. Neural networks handling sequential patterns. Information Sciences. 2004,159:141-154.
[25] Han Min, Cheng Lei, Meng Hua. Application of four-layer neural network on information extraction. Neural Networks. 2003,16:547-553.
[26] Thomas A.Garrity.All the Mathematics You Missed But Need to Know for Graduate School北京:清华大学出版社.
[27] 王东生,曹磊.混沌分形及其应用.合肥:中国科学技术大学出版社,1995.
[28] 陈士华,陆君安.混沌动力学初步.武汉:武汉水利电力大学出版社,1998.
[29] 肯尼思 法尔科内.曾文曲,王向阳,陆夷译.分形几何中的技巧.沈阳:东北大学出版社,1999.
[30] 金以文,鲁世杰.分形几何原理及其应用.杭州:浙江大学出版社,1998.
[31] 沙震,阮火军.分形与拟合.杭州:浙江大学出版社,2005.
[32] 杨建刚.人工神经网络实用教程.杭州:浙江大学出版社,2001.
[33] 焦李成.神经网络系统理论.西安:西安电子科技大学出版社,1990.
[34] Stefan Wermter, Jim Austim. Emergent Neural Computational Architectures. Based on Neuroseienee, —Towards Neuroseienee inspired computing. Berlin: Springer press. 2001,296-310.
[35] Chen Guanrong, Yaobin, Charles K Chui. A symmetric image encryption scheme based on 3D chaotic cat maps. Chaos, Solitons and fractals. 2004, 21:749-761.
[36] M Field. Designer chaos. Computer-Aided Design. 2001,33:349-365.
[37] Li Chunguang, Chen Cuanrong. Chaos in the fractional order Chen system and its control. Chaos, Solitons and Fractals.2004,22:549-554.
[38] 陈关荣,吕金虎.Lorenz系统族的动力学分析、控制与同步.北京:科学出版社,2003.
[39] 王兴元.复杂非线性系统中的混沌.北京:电子工业出版社,2003.
[40] K.Yao, W.Y.Su, S.P.Zhou. On the connection between the order of fractional calculus and the dimensions of a fractal function. Chaos, Solitons and Fractals. 2005,23:621-629.
[41] Nicolangelo Iannella, Lars Kindermann. Finding iterative roots with a spiking neural network. Information Processing Letters. 2005,95:545-551.
[42] Christophe Abraham, Gerard Biau, and Benoit Cadre. On Lyspunov exponent and sensitivity. J.Math.Anal.Appl.2004,299:395-404.
[43] Zhong Li, Guanrong Chen, Wolfgang A Halang. Homoclinic and heteroclinic orbits in a modified Lorenz system. Information Sciences. 2004,165:235-245.
[44] Li Chunguang, Chen Guanrong. Chaos and hyperchaos in the fractional-order Rossler equations. Physica A. 2004, 341:55-61.
[45] Liu Chongxin, Liu Tao, Liu Ling et al. A new chaotic attractor. Chaos, Solitons and Fractals. 2004, 22:1031-1038.
[46] 孙继广.矩阵扰动分析.北京:科学出版社,2001.
[47] 程正兴.小波分析算法与应用.西安:西安交通大学出版社,1998.
[48] 徐长发,李国宽.实用小波方法.武汉:华中科技大学出版社,2001.
[49] 谭宁,徐健学,杨红军等.引起神经元“非周期敏感现象”的分岔机制.生物物理学报,2003,19(4):397.
[50] 戴栋,马西奎,李小峰.一类具有两个边界的分段光滑系统中边界碰撞分岔现象及混沌.物理学报,2003,52(11):2729.
[51] 马少娟,徐伟,李伟等.基于Chebyshev多项式逼近的随机van der Pol系统的倍周期分岔分析.物理学报,2005,54(8):3508
[52] Chen Guan-rong, Fang Jin-qing, Hong Yi-Guang, Qin Hua-shu. Acta Physica Sinica 1999 080416-07
[53] Sun Zheng-ce, Xu Jian-xue. The Influence of weak parametric periodic perturbation on safe basin and the control of the fraetal erosion basin. Chinese Physics, 2001, 10(5): 0599.
[54] Li Yue, Yang Bao-Jun, Du Li-Zhi, Yuan Ye. Chaos-based weak sinusoidal signal detection approach under colored noise background. Chinese Physics, 2003, 12(3): 0714-07.
[55] 马文麒,杨承辉.一类耦合非线性振子同步混沌Hopf分岔及其电路仿真.物理学报,2005,54(3):1064.
[56] Yuzuru Sato, Makoyo Taiji, Takashi Ikegami. NP-Completeness of KSAT and multifractals. Computer Physics Communications 1999,121:51-53.
[57] Harry R lewis, Chfistos H Papadimitfiou. Elements of the theory of computation 2nd Ed. Prentice-Hall, Ine, 199
[58] 张鸣华.可计算理论.北京:清华大学出版社,1984.
[59] 陈志平,徐宗本.计算机数学-计算复杂性理论与NPC、NP难问题的求解.北京:科学出版社,2001.
[60] M Mezard, G parisi, R zeechina. Analytic and Algorithmic Solution of Random Satisfiability Problems. Science.2002, 297(8):812-815.
[61] Asaki Saito, Kunihiko Kaneko. Inaccessibility and undecidability in computation, geometry, and dynamical systems. Physiea D. 2001, 1551-33.
[62] T Bozkaya and M Ozsoyoglu. Indexing Large Metric Spaces for Similarity Search Queries. ACM Trans on Database Systems. 1999, 24(3):341-404.
[63] W A Burkhard, R M Keller. Some Approaches to Best-Match File Searching. Comm. ACM. 1973,16(4):230-236.
[64] S Brin. Near Neighbor Search in Large Metric Spaces. Proc.21st int'l Conf. Very Large Data Bases. 1995,574-584.
[65] P Ciaccia, M Patella and P zezula. M-Tree: An Efficient Access Method for Similarity Search in Metric Spaces. Proc.23th Intl Conf. Very Large Data Bases. 1997, 426-435.
[66] D Shasha, T L Wang. New Techniques for Best-Match Retrieval. ACM Trans. Information Systems. 1990,8 (2):140-158.
[67] J K Uuhlmann. Satisfying General Proximity/Similarity Queries with Metric. Information Processing Letters.1991,40:175-179.
[68] P Yianilos. Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces, Proc. Third Ann. ACM-S1AM Symp. Discrete Algorithms, 1993, 311-321.
[69] J M Gutierrez, M A Rodriguez. A new exact method for obtaining the Multi-fractal spectrum of multi-scaled multinomial measures and 1FS invariant measures. Chaos, Solitons and fractal. 2000,11:675-683.
[70] T K Truong, C M Kung, J H Jeng et al. Fast fractal image compression using spatial correlation. Chaos, Solitons and Fractals.2004,22:1071-1076.
[71] J K Chen, Y F Huang, Y H Chin. A Study of Concurrent Operations on R-Trees. Information Sciences. 1997,263-300.
[72] K Oflazer. Error-Tolerant Retrieval of R-Trees. IEEE Trans on Pattern Analysis and Machine Intelligence. 1997,19(12).
[73] Vincent A Billock, Gonzalo C de Guzman, J A Scott Kelso. Fractal time and 1/f spectra dynamic images and human vision. Physica D. 2001,148:136-146.
[74] Mykola Lysetskiy, Jacek M Zurada. Bifurcating neuron: computation and learning. Neural Networks, 2004,17:225-232.
[75] Ryu Nishimoto, Jun Tani. Learning to generate combinatorial action sequences, utilizing thinitial sensitivity of deterministic dynamical systems. Neural Networks. 2004,17:925-933.
[76] Mykola Lysetskiy, Jacek M Zurada. Bifurcating neuron: computation and learning. Neural Networks.2004,17:225-232.
[77] Eduardo Fernandez, Herbert F Jelinek. Use of Fractal Theory in Neuroscince: Methods, Advantages, and Potential Problems. Methods. 2001,24:309-321.
[78] F T Arecchi. Chaotic neuron dynamics, synchronization and feature binding. Physica A. 2004,338:218-237.
[79] H Ahammer, T T Devaney, H A Tritthart. How much resolution is enough? Influence of downscaling the pixel resolution of digital images on the generalised dimensions. Physica D, 2003,181:147-156
[80] Camillo Gentile, Octavia Camps, Mario Sznaier. Segmentation for Robust Tracking in the Presence of Severe Occlusion IEEE Transactions on Image Process. 2004,13(2):166-178.
[81] Chen Maoyin, Zhou Donghua, Yun Shang. A simple time-delayed method to control chaotic systems. Chaos, Solitons and Fractals. 2004,22:1117-1125.
[82] G Du, T S Yeo. A novel multi-fractal estimation method and its application to remote image segmentation. IEEE Transaction on Geoscience and Remote Sensing. 2002,40(4).
[83] Vito latora et al. The rate of entropy increase at the edge of chaos. Physics letter A 2000,273:97-103.
[84] J Almeida, Dperalta-Salas, M Romera. Can two chaotic systems give rise to order? Physica D. 2005,200:124-132.
[85] M T Yassen. Chaos synchronization between two different chaotic systems using active control. Chaos, Solitons and Fractals. 2005,23:131-140.
[86] Li Damei, Lu Jun-an, Wu Xiaoqun et al. Estimating the bounds for the Lorenz family of chaotic system. Chaos, Solitons and Fractals. 2005,23:529-534.
[87] Minoru Yoshimoto, Shigeru Kurosawa. Chaos control using noise. Materials Science and Engineering. 2000,12:63-66.
[88] A Palacios, H Juarez. Cryptography with cycling chaos. Physics Letters A. 2002,303:345-351.
[89] Li Damei, Lu Jun-an, Wu Xiaoqun. Linearly coupled synchronization of the unified chaotic systems and the Lorenz systems. Choas, Solitons and Fractals. 2005, 23:79-85.
[90] Huang Debin. Simple adaptive-feedback controller for identical chaos synchronization. Physical Review E. 2005,7:1037203.
[91] Ju H Park. Adaptive synchronization of hyperchaotic Chen system with uncertain parameters. Chaos, Solitons and Fractals. 2005, 26:959-964.
[92] Ju H Park. Adaptive synchronization of Rossler system with uncertain parameters. Chaos, Solitons and Fractals. 2005, 25:333-338.
[93] Claudio M. Privitera and Lawrence W. Stark. Algorithms for Defining Visual Regions-of-Interest: Comparison with Eye Fixations. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2000, 22(9):970-981.
[94] Camillo Gentile, Octavia Camps, Mario Sznaier. Segmentation for Robust Tracking in the Presence of Severe Occlusion. IEEE Trans on Image Process. 2004,13(2): 166-178.
[95] Chert Xilin, Yang Jie, Zhang Jiang et al. Automatic Detection and Recognition of Signs From Natural Scenes. IEEE Trans on Image Processing. 2004,13(1): 87-99.
[96] M Hoetter, Differential Estimation of the Global Motion Parameters Zoom and Pan, Signal Processing, 1989,16: 249-265.
[97] Y Gong, T S Lira, H C Chua etc Automatic Parsing of TV Soccer Program, Second International Conference on Multimedia Computing and Systems, May 1995. 167-174.
[98] A E Jacquin. Image coding based on a fractal theory of iterated contractive image transformations. IEEE Trans. on Image Process. 1992, 1(1):18-30.
[99] Nicolas Vanden broueke, Iudovic Macaire, and Jack-Gerard. Postaire Color image segmentation by pixel classification in an adapted hybrid color space. Application to soccer image analysis. Computer Vision and Image Understanding. 2003, 90:190-216.
[100] 陈桂明,张明照,戚红雨.应用MATLAB语言处理数字信号与数字图象.北京:科学出版社,2000.
[101] Stephen J Chapman.MATLAB Programming for Engineers.北京:科学出版社,2003.
[102] 王晓丹,吴崇明.基于MATLAB的系统分析与设计——图象处理.西安:西安电子科技大学出版社,2000.
[103] 郑南宁.计算机视觉与模式识别.北京:国防工业出版社,1998.
[104] 周开利,康耀红.神经网络模型及其MATLAB仿真程序设计.北京:清华大学出版社,2005.
[105] 施阳,李俊.MATLAB语言工具箱——TOOLBOX实用指南.西安:西北工业大学出版社,1998.
[106] 飞思科技产品研发中心.MATLAB6.5辅助神经网络分析与设计.北京:电子工业出版社,2003