自由搜索算法的改进及其在图像分割中的应用
|
摘要
自由搜索算法是近年来提出的一种较新的群体智能优化算法,其算法自身还有很大的研究空间,因此对自由搜索算法进行有效的改进仍然是目前学者研究的一个热点。本文提出一种基于灾变策略的自由搜索改进算法。该算法在群体进行下一轮搜索之前进行一次灾变判断,符合灾变条件的个体将进行相应的灾变操作,将重新初始化下一轮搜索起点。从自然界规律上说该算法较基本的自由搜索算法具有更优秀的全局搜索能力。将本文算法和现有的两种性能最好的自由搜索改进算法(自适应搜索算法和基于粗细粒交叉的自由搜索算法)进行仿真对比,通过对三个基准函数的优化测试,仿真结果表明本文提出的算法在收敛精度和收敛速度上都要优于现有的两种改进算法。
基于最大熵的阈值法图像分割的关键是找到一组合适的阈值向量,使得分割后图像的总熵最大,而总熵恰恰是一个以阈值为自变量的多维函数,在以往的阈值搜索中,存在精度不高的缺陷,鉴于自由搜索算法具有强大的搜索能力,本文提出了基于改进自由搜索算法(即基于灾变策略的自由搜索算法)的最大熵阈值图像分割算法,通过比较本文算法和目前在基于最大熵的阈值法图像分割中应用较好的改进粒子群算法的仿真结果,本文提出的算法可以获得更大的熵值和统一度量标准u值,验证了该改进算法在图像分割中应用的有效性,拓宽了自由搜索算法的应用领域。
Free Search (FS) is a new swarm intelligent algorithm put forward few years ago. There is wider research space for algorithm itself. So proposing efficient improvement of FS is still a hot topic among the researchers now. A novel improved free search algorithm is proposed in this paper, which is based disaster policy. In this algorithm, the individual will make a judge of the disaster, the ones who match the condition will be initialized starting point of the next research cycle. According to the natural, the new algorithm has more powerful global searching ability. The simulation results showed that, compared with other improved FS algorithms(adaptation search algorithm and the FS based cross operator) proposed before, it is improved virtually on convergence precision and speed by using the FS algorithm based disaster policy to optimize 3 typical benchmarks.
Finding a suitable combination of thresholds is the key to threshold image segmentation based on maximum entropy. The entropy is the function of the threshold, it couldn't reach precision high enough by other optimization algorithm. In this paper, Free Search was proposed to improve the method to serve the problem. By the experiment of the Lena and Pepper image, The simulation results showed that, the improved method can select optimal threshold, which can achieve more perfect segmentation effect. It is effective to use the improved algorithm in the image segmentation, whose application field is widened.
基于最大熵的阈值法图像分割的关键是找到一组合适的阈值向量,使得分割后图像的总熵最大,而总熵恰恰是一个以阈值为自变量的多维函数,在以往的阈值搜索中,存在精度不高的缺陷,鉴于自由搜索算法具有强大的搜索能力,本文提出了基于改进自由搜索算法(即基于灾变策略的自由搜索算法)的最大熵阈值图像分割算法,通过比较本文算法和目前在基于最大熵的阈值法图像分割中应用较好的改进粒子群算法的仿真结果,本文提出的算法可以获得更大的熵值和统一度量标准u值,验证了该改进算法在图像分割中应用的有效性,拓宽了自由搜索算法的应用领域。
Free Search (FS) is a new swarm intelligent algorithm put forward few years ago. There is wider research space for algorithm itself. So proposing efficient improvement of FS is still a hot topic among the researchers now. A novel improved free search algorithm is proposed in this paper, which is based disaster policy. In this algorithm, the individual will make a judge of the disaster, the ones who match the condition will be initialized starting point of the next research cycle. According to the natural, the new algorithm has more powerful global searching ability. The simulation results showed that, compared with other improved FS algorithms(adaptation search algorithm and the FS based cross operator) proposed before, it is improved virtually on convergence precision and speed by using the FS algorithm based disaster policy to optimize 3 typical benchmarks.
Finding a suitable combination of thresholds is the key to threshold image segmentation based on maximum entropy. The entropy is the function of the threshold, it couldn't reach precision high enough by other optimization algorithm. In this paper, Free Search was proposed to improve the method to serve the problem. By the experiment of the Lena and Pepper image, The simulation results showed that, the improved method can select optimal threshold, which can achieve more perfect segmentation effect. It is effective to use the improved algorithm in the image segmentation, whose application field is widened.
引文
[1]高济,何钦铭.人工智能基础(第二版)[M].北京：高等教育出版社,2000.
[2]任伟建,陈建玲等.蚁群算法综述[J].2007中国控制与决策学术年会论文集.2005,33(8)：357-361.
[3]Kennedy J, Eberhart R. C. Particle swarm optimization. Proceedings of IEEE International Conference on Neural Networks. Australia:IEEE Service Center,1995:1942-1948.
[4]李晓磊.一种新型的智能优化算法——人工鱼群算法[D]。杭州：浙江大学.2003.
[5]张铃,程军盛.松散的脑袋——群体智能的数学模型[J].模式识别与人工智能.2003,16(1)：1-5.
[6]周晖,李丹美,邵世煌,袁从明.一种新的群集算法——自由搜索[J].东华大学学报.2007(5)：579-583.
[7]王斌,张展羽.基于自由搜索的灌区优化配水模型研究[J].水利学报.2008,11(39)：1239-1243.
[8]周晖,许晨等.群体智能优化算法在WSN节点定位中的应用[J].计算机工程.2008,10(20)：18-20.
[9]Otsu N. A threshold selection method from gray-level histograms[J]. IEEE Trans.Systems Man and Cybernetics,1979,9(1):62-66.
[10]Kittler J, Illingworth J. Minimum error thresholding[J]. Pattern Recognition,1986,19(1):41-47.
[11]Kapur J N, Sahoo PK, Wong A K C. A new method for gray level picture thresholding using the entropy of the histogram[J]. Computer Vision, Graphics and Image Process,1985,29(3):273-285.
[12]Kittler J, Illingworth J. On threshold selection using clustering criteria[J]. IEEE Trans. Systems, Man and Cybernetics,1985,15(5):652-655.
[13]Pun T. Entropic thresholding, a new method[J]. Computer Graphics and Image Process,1981,16(3):210-239.
[14]Doyle W. Operations useful Journal of the ACM for similarity-invariant pattern recognition[J],1962:9(2):259-267.
[15]于新文.几种图像分割算法在棉铃虫图像处理中的应用[J].中国农业大学学报,2001,6(5)：69-75.
[16]Rosenfeld A, Torre P.Histogram concavity analysis as an aid in threshold selection[J].IEEE Trans.Systems Man and Cybernetics,1983, 13(3):231-235.
[17]Tsai W H. Moment-preserving thresholding:A new approach[J]. Computer Vision, Graphics and Image Processing,1985,29(3):377-393.
[18]吴薇.图像处理中的模糊技术[J].现代电子技术,2001,3：28-30.
[19]Abutaleb A S. Automatic thresholding of gray-level pictures using two-dimensional entropies[J]. Pattern Recognition,1989,47(1):22-32.
[20]Pal N R, Pal S K. Entropic thresholding[J].Signal Process,1989,16:97-108.
[21]Brink A D. Thresholding of digital images using two-dimensional entropies[J].Pattern Recognition,1992,25(8):803-808.
[22]Penev K. Adaptive computing in support of traffic management [J].Adaptive Computing in Design and Manufacturing,2004:295-306.
[23]Kalin Penev. Guy Lirtlefair. Free search-acomparalive analysis[J]. Information Sciences,2005.172(1-2):173-193.
[24]周晖,邵世煌,徐晨.自由搜索和微粒群算法的比较研究[J].微电子学与计算机.2009,5：9-12.
[25]CARLOS A,SEBASTIAN I,A Particle Swarm Optimization Algorithm for Part Machine Grouping[J] Robotics and Computer-Integrated Manufacturing,2006,22:468-474.
[26]周晖,李丹美等.基于粗细粒交叉的自由搜索算法[J].控制与决策.2008,9：1068-1072.
[27]沈大旺,张慧.遗传算法综述[J]黑龙江科技信息.2008,9：79-95.
[28]宋松柏,吕宏兴.灌溉渠道轮灌配水优化模型与遗传算法求解[J].农业工程学报.2004,20(2)：40-44.
[29]陈南祥,李跃鹏.徐晨光.基于多目标遗传算法的水资源优化配置[J].水利 学报.2006,37(3)308-313.
[30]胡敬鹏.都江堰灌区渠首水资源优化配置研究[D].成都：四川人学.2006.
[31]吴泽宁.基于生态经济的区域水质水量统一优化配置研究[D].南京：河海大学.2004.
[32]张国华,张展羽,邵光成等.基于粒子群优化算法的灌溉渠道配水优化模型研究[J].水利学报.2006,37(8)：1004-1008.
[33]李远华.节水灌溉理论与技术[M].武汉：武汉水利电力人学出版社.1999.
[34]Akyildiz I F, Su W, Sankarasubramaniam Y, et al. Wireless Sensor Networks:A Survey[J]. Computer Networks,2002,38(4):393-422.
[35]段渭军,王建刚,王福豹.无线传感器网络节点定位系统与算法的研究和发展[J].信息与控制,2006,35(2)：239-245.
[36]程波,顾幸生.灾变合作型协同进化算法及其在job shop调度中的应用[J].华东理工大学学报：自然科学版,2007,33(5)：704-707.
[37]金希东,李治.遗传-灾变算法及其在非线性控制系统中的应用[J].系统仿真学报.1997,9(2)：111-114.
[38]杜长海,黄席樾等.改进的FS算法选取支持向量回归机参数及应用[J].计算机应用技术.2009,7：2520-2523.
[39]N. Otsu. A threshold selection method from gray-level histogram. IEEE Trans. On Systems, Man and Cybernetic,1979,9(l):62-66.
[40]N. R. Pal, S. K. Pal. Entropic thresholding. Signal Process,1989,16:97-108.
[41]M. I. Sezan. A peak detection algorithm and its application to histogram-based image data reduction. Computer Vision, Graphics and Image Processing,1990,49:36-51.
[42]朱雪龙.应用信息论基础[M].北京：清华大学出版社,2001.
[43]T. Pun. A new method for grey-level picture thresholding using the entropy of the histogram. Signal Processing,1980,2(3):223-237.
[44]T. Pun. Entropic thresholding:a new approach. Computer Vision Graphics and Image Processing,1981,16:210-239.
[45]A. K. C. Wong, J.N. Kapur, P. K. Sahoo. A new method for gray-level picture thresholding using the entropy of the histogram. Computer Vision, Graphics and Image Processing,1985,29(3):273-285.
[46]M. Portes de Albuquerque, I. A. Esquef, A. R. Gesualdi Mello. Image thresholding using Tsallis entropy. Pattern Recognition Letters,2004,25(9): 1059-1065.
[47]C. H. Li and C. K. Lee. Minimum cross entropy thresholding. Pattern Recognition 1993,26(4):617-625.
[48]A. D. Brink, N. E. Pendock. Minimum cross-entropy thresholding selection. Pattern Recognition,1996,29:179-188.
[49]A. S. Abutaleb. Automatic thresholding of gray-level pictures using two-dimensional entropy. Computer Vision Graphics and Image Processing, 1989,47(1):22-32.
[50]P. Sahoo, C Wikins, J. Yeager. Thresholding selection using Renyi's entropy.Pattern Recognition,1997,30:71-84.
[51]P. K. Sahoo, G. Arora. A thresholding method based on two-dimensional Renyi's entropy. Pattern Recognition,2004,37(6):1149-1161.
[52]H. D. Cheng, J. R. Chen, J. G.Threshold selection based on fuzzy c-partition entropy approach. Pattern Recognition,1998,31(7):857-870.
[53]L. A. Zadeh. Fuzzy sets. Information Control,1965,18:338-353.
[54]肖高超.改进型粒子群优化算法及其在图像分割中的应用[D].桂林：广西师范大学,2008.
[2]任伟建,陈建玲等.蚁群算法综述[J].2007中国控制与决策学术年会论文集.2005,33(8)：357-361.
[3]Kennedy J, Eberhart R. C. Particle swarm optimization. Proceedings of IEEE International Conference on Neural Networks. Australia:IEEE Service Center,1995:1942-1948.
[4]李晓磊.一种新型的智能优化算法——人工鱼群算法[D]。杭州：浙江大学.2003.
[5]张铃,程军盛.松散的脑袋——群体智能的数学模型[J].模式识别与人工智能.2003,16(1)：1-5.
[6]周晖,李丹美,邵世煌,袁从明.一种新的群集算法——自由搜索[J].东华大学学报.2007(5)：579-583.
[7]王斌,张展羽.基于自由搜索的灌区优化配水模型研究[J].水利学报.2008,11(39)：1239-1243.
[8]周晖,许晨等.群体智能优化算法在WSN节点定位中的应用[J].计算机工程.2008,10(20)：18-20.
[9]Otsu N. A threshold selection method from gray-level histograms[J]. IEEE Trans.Systems Man and Cybernetics,1979,9(1):62-66.
[10]Kittler J, Illingworth J. Minimum error thresholding[J]. Pattern Recognition,1986,19(1):41-47.
[11]Kapur J N, Sahoo PK, Wong A K C. A new method for gray level picture thresholding using the entropy of the histogram[J]. Computer Vision, Graphics and Image Process,1985,29(3):273-285.
[12]Kittler J, Illingworth J. On threshold selection using clustering criteria[J]. IEEE Trans. Systems, Man and Cybernetics,1985,15(5):652-655.
[13]Pun T. Entropic thresholding, a new method[J]. Computer Graphics and Image Process,1981,16(3):210-239.
[14]Doyle W. Operations useful Journal of the ACM for similarity-invariant pattern recognition[J],1962:9(2):259-267.
[15]于新文.几种图像分割算法在棉铃虫图像处理中的应用[J].中国农业大学学报,2001,6(5)：69-75.
[16]Rosenfeld A, Torre P.Histogram concavity analysis as an aid in threshold selection[J].IEEE Trans.Systems Man and Cybernetics,1983, 13(3):231-235.
[17]Tsai W H. Moment-preserving thresholding:A new approach[J]. Computer Vision, Graphics and Image Processing,1985,29(3):377-393.
[18]吴薇.图像处理中的模糊技术[J].现代电子技术,2001,3：28-30.
[19]Abutaleb A S. Automatic thresholding of gray-level pictures using two-dimensional entropies[J]. Pattern Recognition,1989,47(1):22-32.
[20]Pal N R, Pal S K. Entropic thresholding[J].Signal Process,1989,16:97-108.
[21]Brink A D. Thresholding of digital images using two-dimensional entropies[J].Pattern Recognition,1992,25(8):803-808.
[22]Penev K. Adaptive computing in support of traffic management [J].Adaptive Computing in Design and Manufacturing,2004:295-306.
[23]Kalin Penev. Guy Lirtlefair. Free search-acomparalive analysis[J]. Information Sciences,2005.172(1-2):173-193.
[24]周晖,邵世煌,徐晨.自由搜索和微粒群算法的比较研究[J].微电子学与计算机.2009,5：9-12.
[25]CARLOS A,SEBASTIAN I,A Particle Swarm Optimization Algorithm for Part Machine Grouping[J] Robotics and Computer-Integrated Manufacturing,2006,22:468-474.
[26]周晖,李丹美等.基于粗细粒交叉的自由搜索算法[J].控制与决策.2008,9：1068-1072.
[27]沈大旺,张慧.遗传算法综述[J]黑龙江科技信息.2008,9：79-95.
[28]宋松柏,吕宏兴.灌溉渠道轮灌配水优化模型与遗传算法求解[J].农业工程学报.2004,20(2)：40-44.
[29]陈南祥,李跃鹏.徐晨光.基于多目标遗传算法的水资源优化配置[J].水利 学报.2006,37(3)308-313.
[30]胡敬鹏.都江堰灌区渠首水资源优化配置研究[D].成都：四川人学.2006.
[31]吴泽宁.基于生态经济的区域水质水量统一优化配置研究[D].南京：河海大学.2004.
[32]张国华,张展羽,邵光成等.基于粒子群优化算法的灌溉渠道配水优化模型研究[J].水利学报.2006,37(8)：1004-1008.
[33]李远华.节水灌溉理论与技术[M].武汉：武汉水利电力人学出版社.1999.
[34]Akyildiz I F, Su W, Sankarasubramaniam Y, et al. Wireless Sensor Networks:A Survey[J]. Computer Networks,2002,38(4):393-422.
[35]段渭军,王建刚,王福豹.无线传感器网络节点定位系统与算法的研究和发展[J].信息与控制,2006,35(2)：239-245.
[36]程波,顾幸生.灾变合作型协同进化算法及其在job shop调度中的应用[J].华东理工大学学报：自然科学版,2007,33(5)：704-707.
[37]金希东,李治.遗传-灾变算法及其在非线性控制系统中的应用[J].系统仿真学报.1997,9(2)：111-114.
[38]杜长海,黄席樾等.改进的FS算法选取支持向量回归机参数及应用[J].计算机应用技术.2009,7：2520-2523.
[39]N. Otsu. A threshold selection method from gray-level histogram. IEEE Trans. On Systems, Man and Cybernetic,1979,9(l):62-66.
[40]N. R. Pal, S. K. Pal. Entropic thresholding. Signal Process,1989,16:97-108.
[41]M. I. Sezan. A peak detection algorithm and its application to histogram-based image data reduction. Computer Vision, Graphics and Image Processing,1990,49:36-51.
[42]朱雪龙.应用信息论基础[M].北京：清华大学出版社,2001.
[43]T. Pun. A new method for grey-level picture thresholding using the entropy of the histogram. Signal Processing,1980,2(3):223-237.
[44]T. Pun. Entropic thresholding:a new approach. Computer Vision Graphics and Image Processing,1981,16:210-239.
[45]A. K. C. Wong, J.N. Kapur, P. K. Sahoo. A new method for gray-level picture thresholding using the entropy of the histogram. Computer Vision, Graphics and Image Processing,1985,29(3):273-285.
[46]M. Portes de Albuquerque, I. A. Esquef, A. R. Gesualdi Mello. Image thresholding using Tsallis entropy. Pattern Recognition Letters,2004,25(9): 1059-1065.
[47]C. H. Li and C. K. Lee. Minimum cross entropy thresholding. Pattern Recognition 1993,26(4):617-625.
[48]A. D. Brink, N. E. Pendock. Minimum cross-entropy thresholding selection. Pattern Recognition,1996,29:179-188.
[49]A. S. Abutaleb. Automatic thresholding of gray-level pictures using two-dimensional entropy. Computer Vision Graphics and Image Processing, 1989,47(1):22-32.
[50]P. Sahoo, C Wikins, J. Yeager. Thresholding selection using Renyi's entropy.Pattern Recognition,1997,30:71-84.
[51]P. K. Sahoo, G. Arora. A thresholding method based on two-dimensional Renyi's entropy. Pattern Recognition,2004,37(6):1149-1161.
[52]H. D. Cheng, J. R. Chen, J. G.Threshold selection based on fuzzy c-partition entropy approach. Pattern Recognition,1998,31(7):857-870.
[53]L. A. Zadeh. Fuzzy sets. Information Control,1965,18:338-353.
[54]肖高超.改进型粒子群优化算法及其在图像分割中的应用[D].桂林：广西师范大学,2008.