摘要
微粒群算法(PSO, Particle Swarm Optimization)是一种新近出现的启发式全局优化算法,由于算法的易实现性和高效性,因此受到了人们的广泛关注。它已成为与遗传算法、禁忌搜索算法以及模拟退火算法并行发展的一种全局优化算法。这种算法的基本思想是源于鸟类的群体行为。其特点是在较为简单的规则指导下,可以保证微粒迅速降落在最优解处。因此,这种方法具有一定的智能性和社会性。
基于PSO的基本思想,本文对PSO算法进行了详细的论述,讨论了算法的优缺点,并对PSO的基本原理进行了详细分析。为了进一步改进算法的性能,本文提出了两种新算法。一种是基于PSO的核模糊聚类算法(Kernel Fuzzy C-means clustering)。通常,传统聚类算法只在数据特征差异较大时才有效,当数据特征差异较小时,传统聚类算法很难取得较好的聚类效果。新算法先用高斯核函数,把输入空间的样本映射到高维特征空间后,再利用微粒群算法的全局搜索、快速收敛的特点,在特征空间中进行聚类,克服了KFCM对初始值和噪声数据敏感、易陷入局部最优的缺点。通过对医学图像的分割,结果表明,新算法在性能上比KFCM聚类算法有较大的改进,具有更好的聚类效果,且算法能够很快地收敛。
另一种是基于PSO与DCT域的鲁棒图像水印算法。数字水印技术是保护多媒体数据版权和图像可靠性认证的一种新技术,本文比较系统地研究了数字水印在图像中的应用问题,提出了一种新的基于PSO与DCT域的鲁棒图像水印方案。实验仿真表明,针对不同的水印图像和不同的载体图像存在不同的优化频带,在优化频带中嵌入水印明显地平衡了鲁棒性和隐蔽性的冲突。攻击实验表明,该算法对压缩、噪声等一般信息处理是鲁棒的。本文还讨论了置乱技术在数字水印中的应用,置乱技术能分散错误比特的分布,提高了数字水印的鲁棒性。
最后,简述了PSO算法在未来在图像处理领域的发展前景及相关应用,据此指出了未来的主要研究工作和方向。
Particle swarm optimization algorithm is a heuristic global optimization algorithm which appeared recently. It has been widely concerned by people because of its feasibility and effectiveness. It has been proven to be a powerful competitor to other heuristic algorithms, such as genetic algorithm, taboo search and simulated annealing algorithm for global optimization problems. The base idea of this theory is from the colony behaviors of birds. The merit of PSO is that it can assure the particles land the best place with some simple rules. So this method has the attribute of intelligence and society partly.
Based on the PSO’s idea, the PSO has been introduced and discussed in detail in this paper. The merits and disadvantages of the PSO are analyzed and then its basal principle is analyzed and researched in this paper. In order to prove algorithm's performance, two novel algorithms are improved. One is Fuzzy clustering algorithm which uses the merits of the global optimizing and higher convergent speed of Particle Swarm Optimization (PSO) algorithm and combines with Kernel Fuzzy C-Means (KFCM) is proposed. In general, traditional clustering algorithms are suitable to implement clustering only if the feature differences of data are large. If the feature differences are small and even cross in the original space, it is difficult for traditional algorithms to cluster correctly. By using Gauss kernel functions, we can map the data in the original space to a high dimensional feature space in which we can perform clustering efficiently. The algorithm eliminates KFCM trapped local optimum, being sensitive to initial data and the noise data. The performance of this modified PSO-KFCM is compared with KFCM. The results of simulation experiments on medical image show the feasibility and effectiveness of the new clustering algorithm.
Another is watermarking scheme on PSO in the DCT domain. Digital watermarking has recently been proposed as a new means to provide copyright protection of multimedia data and image authentication. Along with penetrated analyze of the theory of PSO, an innovative watermarking scheme on PSO in the DCT domain is proposed. Computer simulation indicates this scheme can find an optimized DCT domain frequency bands when we embed an watermarking image into an digital image. Simulation results prove the balance of conflicting between the invisibility and robustness. Attacking experiment results reveal the fact that the scheme is robust to JPEG compression, noise, et al.
Finally, the developing foreground and correlative application engineering technology are introduced. The research trend and PSO in the future are pointed out in some areas.
引文
[1] Kennedy J., Eberhart R.C., Shi Y.. Swarm Intelligence[M]. San Francisco: Morgan Kaufman Publishers, 2001.
[2]徐小慧,张安.基于粒子群优化算法的最佳熵阈值图像分割[J] .计算机工程与应用, 2006, 10(3): 12-15
[3] Du Feng, Shi Wenkang, Chen Liangzhou , et al. Infrared image segmentation with 2-D maximum entropy method based on particle swarm optimization[J]. Pattern reorganization letter, 2005, 26: 597-603
[4] Yin Peng Yeng. Multilevel minimum cross entropy threshold selection based on particle swarm optimization[J]. Applied Mathematics and Computation, 2006, No.06: 057
[5]许磊,张凤鸣.基于PSO的模糊聚类算法[J] .计算机工程与设计, 2006, Vol. 27, No. 21: 4128-4129
[6]冯林,张名举,贺明峰等.用改进的粒子群算法实现多模态刚性医学图像的配准[J] .计算机辅助设计与图形学报, 2004, 9(15): 1269-1274
[7] Kennedy J.. Particle swarm: social adaptation of knowledge [A]. Proc IEEE Int. Conf. on Evolutionary Computation[C] .Indianapolis: IEEE Piscataway, 1997:303-308
[8] Shi Y., Eberhart R. C. Empirical study of particle swarm optimization[A]. Proceedings of the 1999 Congress on Evolutionary Computation[C].Washington DC: IEEE Piscataway, 1999: 1945-1950
[9] Clerk M., Kennedy J.. The particle swarm: explosion, stability, and convergence in a multi-dimensional complex space[J]. IEEE Transactions on Evolutionary Computation, 2002, 6 (1):58-73
[10]彭宇,彭喜元,刘兆庆.微粒群算法参数效能的统计分析[J] .电子学报, 2004,32(2): 209-213
[11] Kennedy J., Eberhart R. C.. Discrete binary version of the particle swarm algorithm[A]. Proceedings of the IEEE International Conference on Systems, Man and Cybernetics[C]. Orlando IEEE, 1997: 4104- 4108
[12] Shi Y, Eberhart R. C.. A modified particle swarm optimizer[A]. IEEE World Congress on Computational Intelligence[C]. Anchorage: IEEE, 1998:69-73
[13] Shi Y, Eberhart R. C.. Fuzzy adaptive particle swarm optimization[A].Proceedings of the IEEE Conference on Evolutionary Computation[C]. Soul: IEEE, 2001:101-106
[14]张丽平,俞欢军,陈德钊等.粒子群优化算法的分析与改进[J] .信息与控制, 2004, 33(5):513-517
[15] Eberhart R. C., Shi Y.. Comparing inertia weights and constriction factors in particle swarm optimization [A] Proceedings of the IEEE Conference on Evolutionary Computation[C].California: IEEE Piscataway, 2000. 84-88
[16] Thiemo K., Jakob S., et al. Particle Swarm Optimization with Spatial Particle Extension[C]. Proceedings of the 2002 Congress on Evolutionary Computation, 2002, Vol.2: 1474-1479
[17] Angeline P.J.. Using selection to improve particle swarm optimization[A].Proceedings of the 1998 International Conference on Evolutionary Computation[C].New York, NY, USA: IEEE,1998: 84-89
[18] Naka S., et al. A hybrid particle swarm optimization for distribution state estimation[J]. IEEE Transactions on Power Systems.2003, 18 (1):60-68
[19] Higashi N., Iba H.. Particle swarm optimization with Gaussian mutation[C].In: Proceedings of the Swarm Intelligence Symposium. SIS’03.IEEE.2003:72-79
[20] Suganthan P. N.. Particle swarm optimizer with neighborhood operator[A]. Proceedings of the IEEE Congress on Evolutionary Computation[C].1999:1958-1961
[21] AI-Kazemi B., Mohan C. K.. Multi-phase generalization of the particle swarm optimization Algorithm[C]. Proceedings of the 2002 Congress on Evolutionary Computation. Vol. 1: 489-494
[22] Merwe V. D. W., Engelbrecht A. P. Data clustering using particle swarm optimization[C]. Proceedings of IEEE Congress on Evolutionary Computation 2003.Piscataway: IEEE Press, 2003: 215-220
[23] Omran M., Salman A., Engelbrecht A. P.. Image classification using particle swarm optimization[C].Proceedings of the 4th Asia-pacific Conference on Simulated Evolution and Learning 2002. Piscataway: IEEE Press, 2002: 370-374
[24] Bhuyan J.N., Raghavan V. V., Elayavalli V. K.. Genetic algorithm for clustering with an ordered representation [A].in Proc. Int. Conf. Genetic Algorithms′91[C], R. K. Belewand L.B. Booker, Eds. San Mateo, CA: Morgan Kaufman, 1991:408-415
[25] Krovi R.. Genetic algorithms for clustering: a preliminary investigation[A]. IEEE In: Proc. of the Twenty- Fifth Hawaii Intl. Conf. on System Sciences, 1992, 4:540-544
[26] Scheunders P.. A comparison of clustering algorithms applied to color image quantization[J].Pattern Recognition Letters, 1997, 18:1379-1384
[27]刘健庄,谢维信.聚类分析的遗传算法方法[J] .电子学报, 1995, Vol. 23 No. 11: 81-83
[28]郑岩,黄荣怀等.基于遗传算法的动态模糊聚类[J] .北京邮电大学学报, 2005, 2: 75-78
[29]陈金山,韦岗.遗传+模糊C-均值混合聚类算法[J] .电子与信息学报, 2002, Vol. 24 No. 2: 210- 215
[30] Babu G. P., Murty M. N.. Clustering with evolution strategies[J].Pattern Recognition, 1994, 27(2): 321-329
[31] Zhang Li, Zhou W. D., Jiao L. C. Kernel clustering algorithm[J].Chinese Computers, 2002, 25 (6): 587- 590
[32] Petitcolas F. A. P., Anderson R. J., Kuhn M.G.. Information Hiding-A Survey[A]. Proceedings of IEEE[C], Vol.87, No.7, July 1999, pp.1062-1078
[33] Cox I. J., Killian J, Leighton F.T.. Secure spread spectrum water marking for multimedia[J]. IEEE Trans on Image processing, 1997, 6(12):1673-1687
[34] Nikolaidis A., Pitas I.. Comparison of different chaotic maps with application to image watermarking[A]. In: IEEE Int. Symposium on Circuits and Systems (ISCAS 2000) [C], Geneva, Switzerland, May 2000, 509~512
[35] Cox I. J., Miller M. L.. The first 50 years of electronic watermarking[J]. Journal of Applied Signal Processing, 2002, 56(2):126-132
[36] Voyatzis G., Ipitas I.. The use of watermarks in protection of digital multimedia products[J]. Proceedings of IEEE, 1999, 87(7):1197-1207
[37]陈明奇,钮心忻,杨义先.数字水印的研究进展和应用[J] .通信学报, 2001, 22(5): 71-79
[38] Kutter M., Jordan F., Bossen F.. Digital signature of color images using amplitude modulation[A].In: Storage and Retrieval for Image and Video Databases V[C].SPIE, 1997, 3022:518-526
[39] Cox I. J., Kilian J., Leighton T.. A Secure, robust watermark for multimedia[A]. Proceedings of First International Information Hiding Workshop[C]. Berlin: Springer-Verlag, 1996: 185-206
[40]钟伟,马希俊,余松煌.一种使用Legendre阵列的图像水印[J] .通信学报, 2001, 22(1):1-6
[41] Tsekeridou S., et al. Statistical analysis of a watermarking system based on Bernoulli chaotic sequences [J]. Signal Processing, 2001, 81 (6):1273-1293
[42]周利军,周源华,支玲.基于m序列的多重图像水印[J] .上海交通大学学报, 2001, 35(9):1317- 1320
[43]杨长生.图像与声音压缩技术[M] .浙江大学出版社, 2000 04:269-301
[44] Dittman J., Stabenan M., Steinmetz R.. Robust MPEG video watermarking technologies[C]. Proceedings of ACM MM'98, Bristol, U. K.: ACM Press, 1998: 71-80
[45] Xia X. G., Boncelet C. G., Arce G. R... A Multi-resolution Watermark for Digital Images [C]. Proc. IEEE Int. Conf. Image Processing, Vol. 1, 1997, p: 548-551
[46] Craver S., Memon N., et al. Resolving Rightful Ownerships with Invisible Watermarking Techniques: Limitations,Attacks and Implications[J]. IEEE Journal on Selected Areas in Communications (Special issue on Copyright and Privacy Protection), 1998, 16:573-586
[47] Christine I., Podilchuk, Zeng W. J.. Image-adaptive watermarking using visual models[J]. IEEE Journal on Selected Areas in Communications, 1998, 16(4):525-539
[48] Zhu W., Xiong Z., Zhang Y. Q. Multi-resolution Watermarking for Images and Video[J]. IEEE Trans on Circuit and System for Video Technology, 1999, 9(4): 545-550
[49] Pitas I.. A Method for Watermark Casting on Digital Image[J]. IEEE Trans. On Circuit and Systems for Video Technology, 1998, Vol. 8, No. 6: 775-780
[50] Pitas I.. A Method for Signature Casting on Digital Images[J]. Proc. Of International Conference on Image processing, 1996, Vol. 3:215-218
[51] Voyatzis G., Pitas I.. Chaotic Watermarks for Embedding in the Spatial Digital Image Domain[C]. Proc. of ICIP'98, 1998:432-436
[52] Wolfgang R. B., Podilchuk C. I., Delp E. J.. Perceptual watermarks for digital images and video[C]. Proceedings of the IEEE, 1999, 87(7):1108-1126
[53] Wolfgang R. B., Delp E. J.. A Watermark for Digital Images[A]. Proceedings of the IEEEInternational Conference on Image Processing[C]. Lausanne, Switzerland, 1996: 219-22
[54] Schyndel R. G. V., Tirkel A. Z., Osborne C. F.. A Digital Watermark[C]. Proc. of IEEE, 1994, p. 86-90
[55] Qu G., Potkonjak M.. Analysis of Watermarking Techniques for Graph Coloring Problem[C]. Proceeding of 1998 IEEE/ACM International Conference on Computer-aided Design, New York: ACM Press, 1998: 190-193
[56] Kankanhalli M. S., Ramakrishnan K. R., Rajmohan. Content based Watermarking of images[C].the 6th, ACM International Multimedia Conference. New York: ACM Press, 1998, p: 61-70
[57] Petitcolas F. A. P., Anderson R. J., Kuhn M. G.. Attacks on copyright marking system[A]. Proc. of 2nd Int Workshop on Information Hiding[C].Berlin: Springe-Verlag, 1998, 1525: 219-239
[58] Fabien A. P., Petitcolas, Anderson R. J.. Evaluation of Copyright Marking Systems[A]. Proc. of IEEE multimedia Systems (ICMCS’99), 1999, Vol. 1:574-579
[59] Cao Hanqiang, Zhu Guangxi, Zhu Yaoting, et al. Embedding a signature in an Image Based on Fractal Compress Transformations[J]. Journal of China Institute of Communications, 1998, Vol. 19, No. 5: 69-74
[60]丁玮,齐东旭.数字图像变换及信息隐藏与伪装技术[J] .计算机学报, 1998, 21(9): 838-843
[61]黄继武, Shi Y Q,姚若河.基于块分类的自适应图像水印算法[J] .中国图像图形学报, 1999, 4 (A) (8): 640-643
[62] Maes M. J. J. J. B., Overveld C. W. A. M.. Digital Watermarking by Geometric Warping[A]. Proceedings of the International Conference on Image Processing (ICIP) [C].Santa Barbara, CA, USA: ICIP, 1998:352- 356
[63]陈青,苏祥芳,王延平.采用小波变换的鲁棒隐形水印算法[J] .通信学报, 2001, 22 (7):61-65
[64]周亚训,叶庆卫,徐特峰.基于小波和余弦变换组合的图像水印方案[J] .电子学报, 2001, 29(12): 1693-1695
[65] Pereira S., Voloshynovskiy S., Pun T.. Optimized wavelet domain watermark embedding strategy using linear programming[J]. In proceedings of SPIE AreoSence, April 2000,Orlando, USA, Wavelet Applications, VII: 26-28
[66]邹建成,铁小匀.数字图像的二维Arnold变换及其周期性[J] .北方工业大学学报, 2000, 12 (1): 10-13