用户名: 密码: 验证码:
基于思维进化算法的图像边缘检测
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
边缘检测是图像处理中的重要内容,是图像的最基本特征。所谓边缘,是指图像中灰度发生急剧变化的区域。边缘检测在图像分割、图像检索、模式识别、机器视觉等领域中有重要的应用。
     传统边缘检测算法的主要思路是通过使用2*2或者3*3检测模板作为核与图像中每一个像素点进行卷积运算,求得梯度值;然后选取合适的分割阈值以提取边缘。该方法中存在一定的缺陷:(1)检测模板的系数固定,缺乏可调性。针对不同的图像,检测效果一般,只能检测出图像的大致轮廓,缺乏自适应性。(2)阈值的选取需要靠人工测试选择,存在一定的盲目性。
     针对传统边缘检测算法存在的问题,本文采用一种新的进化理论-思维进化算法,并结合传统边缘算法的思想,提出了基于思维进化算法的图像边缘检测方法。把传统边缘检测问题转换成函数寻优过程,利用思维进化算法的快速寻优特性,在待处理问题的解空间搜索最佳解,即在参数解空间范围内搜索最佳模板系数和最佳分割阈值,实现模板系数和阈值的人工智能选取,大量实验结果证明了该方法的可行性,有效地解决了传统边缘算法存在的缺陷问题。
     基本思维进化算法具有快速的全局收敛能力,但是在解空间收缩的解越接近最佳解时,收敛速度慢,局部搜索能力差,为了提高思维进化算法的局部搜索能力,本文对基本思维进化算法进行了的改进,即引进最速下降法来改进思维进化算法的局部收敛能力。最速下降法在解空间搜索最佳解的过程具有方向性,沿着目标函数负梯度下降方向搜索一维解,又称梯度法,是无约束化中最简单的方法,具有快速的局部收敛特性,采用该方法对思维进化算法进行改进,能够改善思维进化算法的局部收敛特性,加快搜索速度。
     在采用思维进化算法优化模板系数过程中,由于模板系数之间存在相互约束关系,对于约束条件的处理,本文引进罚函数的思想,对于违反约束条件的种群,做出相应的惩罚,根据惩罚项及时调整思维进化算法中的目标函数,降低违反约束条件种群的适应度,使该种群进入下一代进化的机率较少,最终让搜索的解尽量满足约束条件。
     对于阈值的选取,本文结合最大类间方差法,采用改进思维进化算法在求解问题的参数范围内寻找最佳的分割阈值。用改进思维进化算法去寻取最佳阈值将梯度图像分割成两部分(边缘点集合和非边缘点集合),使两部分类间方差取最大值,实现边缘点集合的提取。采用改进思维进化算法优化阈值的策略,一方面可以减少最大类间方差的计算次数,提高计算效率;另一方面可以加快最优解的收敛速度,实现快速达到全局最优解的目的。
Edge detection plays key role in image processing. It is one of the most important features of images, which is defined as a region where there is a sudden change of pixels' gray level. Edge detection has many important applications in the fields of image segmentation, image retrieval, pattern recognition, machine vision.
     The main idea of the traditional Edge detection method is that computing each pixel gradient values by convolution operation between each pixel and 2*2 or 3*3 mask as convolute core. Then, picking up the edge points based on the appropriate threshold, if gradient value of one point is greater than the selected threshold, this point is regarded as edge point, or else it is not the edge point. However, this method exist two shortcomings: one is that coefficients of the detection mask are changeless and lock of flexibility; another one is that threshold selection need repetitious testes by experiments, The key point to this method is how to select appropriate threshold. Threshold will directly affect detection precision.
     In order to improve shortcomings of the traditional edge detection method, this paper is proposed a new type of optimization algorithm- Mind Evolutionary Algorithm(MEA) to pick up edges points called edge detection based on mind evolutionary algorithm. Edge detection problem can be converted to function optimization process, so MEA can be used to solve the traditional method existed problems. MEA can quickly search the optimal coefficients of mask and threshold in whole solution space, that is, optimal coefficients of mask and threshold is selected based on artificial intelligence method. A lot of experimental results proved that the new method proposed in this paper is feasible and effective.
     The simple mind evolutionary algorithm has the high the convergence rate of global optimal solution, when the solution is coming to optimal solution, the speed of searching is decreasing, that is the convergence rate of local optimal solution is low, In order to solution this problem, steepest descent method is introduced in this paper to advance MEA’s local convergence ability. Steepest descent method in the solution space searching process for optimal solution has the searching direction, which is along the negative direction of fitness function gradient descent to search one-dimensional solution; it is the simplest method of nonrestraint optimization, the paper is made use of fast local convergence property of steepest descent method to improve MEA’s performance, experimental results proved that this method can speed up the MEA whole search speed.
     In the process of optimizing the mask coefficients, due to coefficients with mutual constraint relations, this paper is adopted penalty function to deal with constraints. The appropriate punishment is added to fitness function for populations which violate the constraints, reducing the fitness values of violative populations according to punishment, the probability of violative populations entering to next evolutionary generation is decreased greatly, the purpose of this operation is that the optimal solution meets the constraint as possible as it can.
     The optimal point or the required corresponding threshold is then determined based on improved mind evolutionary algorithm, searching the optimal threshold at scope of the whole gray level combined with Ostu’s threshold method which is proposed based on the principle of least squares whit a widespread application. The method main idea is that dividing the image histogram into two parts (edge points and non-edge points) according to the selected threshold so that the measure of class separability of two parts has the maximum value. The test results illustrate that threshold optimization based on improved MEA can reduce the amount of calculation of Ostu’s method.
引文
[1] L.G.Roberts. Machine Perception of Three Dimension Solids[J]. In Optical and Electro-Optimal Information Processing.J.T.Tippett etal,Eds.MA:MTT Press, Cambridge , 1965,159-197
    [2] J.M.S Prewitt. Object Enhancement and Extraction[M]. In Picture Processing and Psychopictorics, B.S.Lipkin and A.Rosenfeld, Eds.Academic Press, New York,1970
    [3] R.A.Kirsch. Computer Determination of the Constituent Structure of Biological Images[J]. Computers and Biomedical Research ,4,3,1971,315-328
    [4] L.Sobel. Camera Models and machine Perception[D]. theses,Stanford University, Standford,CA.1970.
    [5] D.C.Marr, E.Hildreth. Theory of edge Detection. Proc[J]. Roy. Soc. London, vol. B275, pp.187-217,1980
    [6] John Canny,Member. A Computational Approach to Edge Detection. IEEE Trans. Pattern Analysis and Machine Intelligence[J], vol. PAMI-8, No.I, pp. 679-697, 11, 1986
    [7]贾东立.基于遗传算法的图像边缘检测研究[D].西南交通大学:硕士学位论文, 2005.5
    [8] Bittencourt J.R, Osorio F.S. Adaptive fitters for image processing based on artificial neural network[J]. Brazilian Symposium on Computer Graphics and Image Processing, 2000,(2):336-337
    [9] Pal SK, King RA. On edge detection of X-ray image using fuzzy sets[J]. IEEE trans. Partt. Anal. and Machine Intell.1983,5(1):69-77
    [10]冈萨雷斯.数字图像处理(MATLAB)[M].北京:电子工业出版社, 2005.9
    [11] I.E.Abdou, W.K.Pratt. Quantitative design and evaluation of Enhancement thresholding edge detector [J], Processing of the IEEE,1979,67(5):753-763
    [12] E.D.Micheli, B.Caprile.P.Ottonello, Vtorre. Localization and noise in edgedetection[J], IEEE Trans. Pattern Analysis and Machine Intelligence, 1989, 11(10): 1106-1117.
    [13] W.K.Pratt. Digital Image Processing, Wiley[M]. New York, second edition,1991,176-189
    [14]孙兆林MATLAB6.x图像处理[M]北京:清华大学出版社2002.5
    [15]阎平凡,张长水.人工神经网络与模拟进化计算[M].北京:清华大学出版社2005.9
    [16] Rechenberg I. Cybernetic Solution Path of an Experiment Problem[J]. Roy Aircr, establ, Libr.Trans1222, Hants, U.K.Farnboroungh,1965
    [17] Beyer, H.-G, Toward a Theory of Evolution Strategies[J]: Self-Adaption. Evolutionary Computation,1996,3(3):311-347
    [18] Schwefel H.P. Numerical Optimiazation of Computer Models[J]. Chicheater. Wiley, 1981
    [19] Fogel L J. Artificial Intelligence through Simulated Evolution[J]. New York:John Wiley,1966.
    [20] Holland J H. Adaptation in Nature and Artificial Systems[M].The University of Michigan Press,MIT Press,1975
    [21] De Jong K. An analysis of the behavior of a class of genetic adaptive systems[D]. University of Michigan,1975.
    [22]陈国良.遗传算法及其应用[M].人民邮电出版社,1996
    [23]王小平,曹立明.《遗传算法—理论、应用与软件实现》[M].西安交通大学出版社. 2002
    [24]雷英杰,张善文. MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社, 2005.4
    [25] Liu Juan, Cai Zixin, Liu Jiangqin. Premature convergence in genetic algorithm:analysis and prevention based on chaos operator[C].Intelligent Control and Automation,2000. Proceedings of the 3rd World Congress on.Voll(28):495-499
    [26] Determan J, Foster J A. Using chaos in genetic algorithms[C]. Evolutionary computer,1999,CEC 99. Proceedings of the 1999 Congress on Vol 3:2094-2102
    [27] Cheng yi Sun and Yan Sun. Mind-Evolution-Based Machine Learning: Framework and The Implementation of Optimization[C]. Proc.of IEEE Int.Conf.on Intelligent Engineering Systems(INES’98), Edts.P.KoPacek, Sept.17-19,1998, Vienna,Austria, IEEE Inc. pp.355-359
    [28]孙承意,谢克明,程明琦.基于思维进化机器学习的框架及新进展[J].太原理工大学学报,vol.3o,No.5,1999年9月.pp.453-457
    [29] Sun Chengyi,SunYan and Xie Keming.Mind-evolution-based machine learning And applications[C]. Proc.3rd world Congress on Intelligent Control and Automation(WCICA2000),Hefei,P.R.China.Press of University of Science and Technology of China,IEEECatalog Number: 00EX393, ISBN:0-7803-5995-X. June28-July, 2,2000, pp.129-131.
    [30]孙承意,王皖贞,贾鸿雁.思维进化计算的产生与进展[C]. 2001年中国智能自动化会议(CIAC200l),昆明,2001年8月13-16,pp.80-86
    [31] Sun Chengyi, Zhang Jianqing and Wang Junli. The analysis of efficiency of Similartaxis searching[C]. Joint 9th IFAS world Congress and 20th NAFIPS International Conference,Canada,July25-28,2001,pp.35-40
    [32] Fogel D.B. An introduction to simulated evolutionary optimization[J]. 1994,IEEE Trans.on Neural Networks,5(l):3-14
    [33]曾建潮,孙承意.具有二进制编码的思维进化方法[J].航空计算技术,1999,vol.29,No.4, pp.42-45
    [34]曾建潮,查凯.基于思维进化机器学习的自适应趋同策略[J].计算机工程与科学,2000,vol.22, No.4,94-96
    [35] Chengyi Sun and Yan Sun. The Performance of a Modified MEBML System in Noisy Environment[C]. Proc. of 1999 IEEE Int. Conf. on Systems, Man, and Cybernetucs, (SMC’99),vol.5, pp.613-617, Oct. 12-15, 1999, Tokyo, Japan.
    [36]介婧,曾建潮.基于引导的思维进化算法[J].计算机工程与科学,2002,vol.24,No.1,pp.66-69
    [37] Lijun Wei, Yan Sun and Chengyi Sun. A More Efficient Similartaxis Strategy of MEBML[C]. in Proc. Of IASTED Inter. Conf. on Modeling and Simulation (IASTED MS’99), Edts. M. H. Hanza, IASTED/Acta Press, Anaheim, California,pp.1-5, May 5-8,1999, Pittsburgh, Pennsylvania, USA
    [38]王川龙,孙承意.基于思维进化的智能算法的收敛性研究[J].计算机研究与发展,2000,vol.37, No. 7,pp. 838-842.
    [39] Chengyi Sun, Xiaohong Qi and Ou Li. Pareto-MEC for Multi-Objective Optimization[C]. in Proceedings of 2003 IEEE International Conference on Systems, Man and Cybernetics, IEEE SMC2003,pp.321-328,Oct.5-8, Hyatt Regency, Washington, DC, USA.
    [40] Liai Wang Chengyi Sun. Multimodal Optimization Performance of MEC by Two-level MEC[C],(in china). 2003 Chinese Intelligent Conference(CIAC2003), pp.1031-1037, Dec 15-17. 2003, the Chinese University of HongKong, HongKong, China.
    [41] Jianqing Zhang, Chengyi Sun and Junli Wang. MEC for Solving Multi-modal Prombles, (in Chinese) [C]. Progress of Artificial Intelligence in China 2001-Proc. of 9th Conference of Chinese Association on Artificial Intelligence(CAAI-9), pp.162-167, 1-3, Dec.2001, BUPT Publishing House, Beijing, P. R.China
    [42]介婧,曾建潮.基于思维进化计算求解约束优化问题的新算法[J].计算机工程与应用,2003,Vol.39,No.4, pp. 66-68
    [43]查凯,曾建潮.求解Job-shop调度问题的思维进化算法[J].小型微型计算机系统. 2002,Vol.23.No. 8. pp. 1000-1002
    [44]曹俊琴.一种基于思维进化算法的神经网络求解机器人逆运动学问题[D].太原理工大学硕士学位论文,2005.4
    [45]孙承意.贾美丽. MEC的主从式并行方案[J].计算机工程与应用,2002,pp. 150-152.
    [46]袁亚湘,孙文瑜.最优化理论与方法[M].科学出版社,1999
    [47] Chen, L. P. and Jiao, B. C. Convergence properties of the preconvex part of Non-Quasi-Nowton’s family[J]. Mathermatica Numerica,2000,22(3):369-378
    [48] Dai,Y.H. and Yuan,Y. A nonlinear conjugate gradient with a strong global convergence property[J]. SIAM Journal of Optimization,2000,10:177-182.
    [49]刑军.基于Sobel算子数字图像处理的边缘检测[J].微机发展,Vol.15, No.9,2005.9
    [50]宋培华,陆宗其.基于Log-Prewitt算子的边缘检测算法[J].小型微型计算机系统.Vol.23 ,No.11, 2002.11
    [51] Demigny D. An Optimal Linear Filtering for Edge Dection[J]. IEEE Transaction on image processing,2002,11(7):728-737
    [52]李宏贵,李兴国.一种基于δ函数的边缘图像检测算法[J].中国图形图像学报,2003,8A(2):188-192.
    [53]李辉.基于改进遗传算法的图像分割[D].吉林省:东北师范大学, 2004,5
    [54]陈宏希.基于边缘保持平滑滤波的Canny算子边缘检测[J].兰州交通大学学报,Vol.25 No.12006.2
    [55]陈彦燕,王元庆.常用边缘检测算法的定量比较[J].计算机工程VOl.34 No.17 2008.9
    [56]耿茵茵,蔡安妮.自动图像阈值分割算法.计算机工程与应用[J], 2002.17:119-122
    [57]王培珍,杜培明.一种用于多阈值图像自动分割的混合遗传算法[J].中国图像图形学报, 2000,5(1),35-37
    [58]常青,王立.基于遗传算法的图像阈值选取.计算机工程与应用[J], 2002.22:35-37
    [59] Sapa A.D, Bevilacqua V.Devy M. Improving a Genetic Algorithm Segmentation by Means of a fast Edge Detection Technique[J]. Image Processing,2001 International conference,2002,754-757
    [60]王阳萍,何欣.智能图像处理技术在车型识别中的应用研究[J].兰州交通大学学报,2004, 23 (4):65-67
    [61] Otsu N, THRESHOLD A Selection method from gray-level histograms[J].IEEE Trans,1979,SMC 9(1):62-66

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700