基于遗传算法的图像分割研究
|
摘要
遗传算法具有简单、鲁棒性好和本质并行的突出优点。其在应用领域取得的巨大成功，引起了广大学者的关注。在图像分割领域，遗传算法常用来帮助确定分割阈值。
本文讨论了目前遗传算法应用于图像分割的现状，给出了几种遗传分割算法的原理、过程、实验结果及分析；
介绍了图像边缘检测、图像阈值分割的各种算法，并给出了对比分析；对遗传算法的基本概念和研究进展进行了综述，提出了一种新的遗传分割算法，得到了理想的结果。
本文提出的遗传分割算法充分考虑了图像数据本身的特殊性，从提高全局搜索能力和收敛速度出发，加入了3个新的操作策略。算法在初始化种群阶段引入了“优生”算子，以及改进的变异操作使算法的收敛速度大大提高；在形成新种群阶段引入新的算子避免了局部早熟，提高了全局收敛能力。本文以基于坐标的阈值分割方法为基础进行二维整数编码，采用窗口交叉方法，以文献[23]给出的评价方法构造适应度函数。实验结果表明，本文提出的遗传分割算法明显优于传统分割算法。
本文所有程序均是用VC++6．0在Win98环境下编译完成。实验图片源于实际拍摄的图片及网上收集的图片。
Genetic algorithm (GA) has the virtue of simpleness, robustness and parallel in essence. It has been applied perfectly in the engineering field, which appeals to many scholars in the world. In the image segmentation field, GA is usually used to get the threshold of image segmentation.
The status of GA applied in the image segmentation field recently is presented, and the theories, steps, results and analyses of several GAs applied in the image segmentation are given.
Algorithms and analyses about edge detection and threshold selection of the image segmentation are presented. An overview of the basic theories and the recent development is given, and a new genetic algorithm applied in image segmentation (GAS) is presented.
Considering image data is often very massive, GAS introduces three new measures in order to solve the problem of global convergence and improves the convergence speed. Introduction of prepotency operator in the initialize population step and the improved mutation operator accelerate the convergence process, and the introduction of new operator in forming new population step avoid converging in local optimum, and promote the ability of global convergence. Coding based upon image threshold segmentation related with coordinates, using windows crossover method, designing evaluation function based upon the equations given in literature [23], GAS gets much better results than traditional algorithm.
Programs were all compiled in the Win98 by VC++6.0. All photos were collected from Internet and personal photos.
本文讨论了目前遗传算法应用于图像分割的现状，给出了几种遗传分割算法的原理、过程、实验结果及分析；
介绍了图像边缘检测、图像阈值分割的各种算法，并给出了对比分析；对遗传算法的基本概念和研究进展进行了综述，提出了一种新的遗传分割算法，得到了理想的结果。
本文提出的遗传分割算法充分考虑了图像数据本身的特殊性，从提高全局搜索能力和收敛速度出发，加入了3个新的操作策略。算法在初始化种群阶段引入了“优生”算子，以及改进的变异操作使算法的收敛速度大大提高；在形成新种群阶段引入新的算子避免了局部早熟，提高了全局收敛能力。本文以基于坐标的阈值分割方法为基础进行二维整数编码，采用窗口交叉方法，以文献[23]给出的评价方法构造适应度函数。实验结果表明，本文提出的遗传分割算法明显优于传统分割算法。
本文所有程序均是用VC++6．0在Win98环境下编译完成。实验图片源于实际拍摄的图片及网上收集的图片。
Genetic algorithm (GA) has the virtue of simpleness, robustness and parallel in essence. It has been applied perfectly in the engineering field, which appeals to many scholars in the world. In the image segmentation field, GA is usually used to get the threshold of image segmentation.
The status of GA applied in the image segmentation field recently is presented, and the theories, steps, results and analyses of several GAs applied in the image segmentation are given.
Algorithms and analyses about edge detection and threshold selection of the image segmentation are presented. An overview of the basic theories and the recent development is given, and a new genetic algorithm applied in image segmentation (GAS) is presented.
Considering image data is often very massive, GAS introduces three new measures in order to solve the problem of global convergence and improves the convergence speed. Introduction of prepotency operator in the initialize population step and the improved mutation operator accelerate the convergence process, and the introduction of new operator in forming new population step avoid converging in local optimum, and promote the ability of global convergence. Coding based upon image threshold segmentation related with coordinates, using windows crossover method, designing evaluation function based upon the equations given in literature [23], GAS gets much better results than traditional algorithm.
Programs were all compiled in the Win98 by VC++6.0. All photos were collected from Internet and personal photos.
引文
[1]Nikhil R Pal, Sanker K Pal. A review on image segmentation techniques. Pattern Recognition, 1993; 26(9): 1277～1294
[2]章毓晋．图像分割[M]．科学出版社．2001
[3]王爱民，沉兰荪．图像分割研究综述．测控技术，2000，19(5)，1～6
[4]赵荣椿，迟耀斌，朱重光．图像分割技术进展．中国体视学与图像分析．1998；3(2)：121～128
[5]阮秋琦．数字图像处理学[M]，北京，电子工业出版社，2001
[6]Kenneth R Castleman. Digital Image Processing[M]，电子工业出版社，1998
[7]何斌，马天予，王运坚，朱红莲．Visual C++数字图像处理[M]．北京：人民邮电出版社，2001
[8]Dubes R C, et al. MRF model-based algorithms for image segmentation. Proceeding of 3rd ICIPIA, 1990, 808～814
[9]崔屹．图像处理与分析—数学形态学方法及应用[M]．北京：科学出版社，2000
[10]黄建军，赵荣春．基于模糊ART的图像分割．电子学报．29(5)：718～721
[11]Wang J P. Stochastic relaxation on partitions with connected components and its application to image segmentation. IEEE-PAMI, 1998, 20(8): 619～636
[12]Brink A B. Gray level thresholding of image using a correlation criterion. Patter Recognition letters, 1989,9:335～341
[13]Mardia K V and Hainsworth T J. A spatial thresholding method for image segmentation. IEEE Trans, Pattern Analysis and Machine Intelligence, 1988, 10:919～927
[14]付忠良．图像阈值选取方法的构造．中国图像图形学报．2000；5(6)：466～469
[15]靳宏磊，朱蔚萍，李立源，陈维南．二维灰度直方图的最佳分割方
法．模式识别与人工智能，1999；12(3)：329～333
[16]刘文萍，吴立德．图像分割中阈值选取方法比较研究．模式识别与人工智能．1997；10(3)：271～277
[17]谌海新，沈振康，夏放怀．一种基于目标特征的多门限图像分割方法．电子学报，1999；27(3)：32～36
[18]侯格贤，毕笃彦，吴成柯．图像分割质量评价方法研究．中国图像图形学报．2000；5(1)：39～43
[19]Lee S U, Chung S Y. A comparative performance study of several global thresholding techniques for segmentation. Computer Vision Graphics and Image Processing. 1990; 52:171～190
[20]Bengiovanni G. Image segmentation by a multi resolution approach. Pattern Recognition, 1993; 26(12): 1827
[21]贺前华，韦岗，陆以勤．基因算法研究进展．电子学报．1998；26(10)：118～122
[22]Zhang Y J. A survey on evaluation methods for image segmentation. Pattern Recognition. 1996; 29(8): 1335～1346
[23]薛景浩，章毓晋，林行刚．二维遗传算法用于图像动态分割．自动化学报，2000；26(5)：749～753
[24]郑宏，潘励．基于遗传算法的图像阈值的自动选取．中国图像学报，1999；4(4)：317～330
[25]王培珍，杜培明，陈维男．一种多阈值图像自动分割的混合遗传算法．中国图像图形学报．2000；5(1)：44～47
[26]吴成柯，刘靖，侯格贤．图像分割的多参量遗传算法．自动化学报．1998；24(3)：410～413
[27]Goldberg D E. Genetic Algorithms in Search, Optimization & Machine Learning. Addison Wesley Publishing, 1989.
[28]陈国良等．遗传算法及其应用[M]．人民邮电出版社，1996
[29]Z．米凯利维茨．演化程序—遗传算法和资料编码的结合[M]．北京：科学出版社
[30]Rudolph G. Convergence Properties of Canonical Genetic Algorithms. IEEE Trans. Neural Networks. 1994. 5(1), 96～101
[31] Grefenstette J J. Optimization of Control Parameters for Genetic Algorithms. IEEE Trans. SMC. 1986, 16(1), 122～126.
[32] Qi X, Palmieri F. Theoretical Analysis of Evolutionary Algorithms with an Infinite Population Size in Continuous Space Part Ⅰ: Basic Properties of Selection and Mutation. IEEE Trans. Neural Networks, 1994, 102～109.
[33] 恽为民，席裕庚．遗传算法的收敛性和计算效率的分析，控制理论与应用，1996，13(4)，455～460
[34] Hollstien R B. Artificial Genetic Adaptation In Computer Control Systems. Doctoral Dissertation. University of Michigan, 1971.
[35] 王小平，曹立明．遗传算法—理论、应用与软件实现[M]．西安：西安交通大学出版社，2002
[36] 张卫丰，徐宝文，周晓宇，管宇，许蕾．基于遗传算法的搜索引擎调度．微电子学与计算机．2001；(4)：34～38
[37] 张军英，许进，保铮．遗传交叉运算的可达性研究．自动化学报．2002；28(1)：120～125
[38] Gunter Rudolph Convergence analysis of canonical genetic algorithms. IEEE Trans, Neural Networksv. 1994; 5(1):96～101
[39] 辛绯等．遗传算法的适应度函数研究．系统工程与电子技术．1998，11：58～62
[40] 郑志军，郑守淇．进行神经网络中的变异操作数研究．软件学报．2002；13(4)：726～731
[41] Zhang Y J. Segmentation evaluation and comparison; a study of various algorithms. SPIE, 1993, 2094:801～812
[42] 孟庆春，贾培发．关于Genetic算法的研究及应用现状．清华大学报(自然科学版)，1995，35(5)．
[43] Yanowitz S D, Bruckstein A M. A new method for image segmentation. CVGIP, 1989, 46:82～95
[44] 刘大有等．遗传程序设计方法综述．计算机研究与发展，2001；38(2)：213～222
[45] Bhandarkar S M, and Zhang Hui. Image Segmentation Using Evolutionary Computation, 1999; 3(1): 1～21
[46] 张晓缋，方浩，戴冠中．遗传算法的编码机制研究．信息与控制，1999；26(2)：134～139
[47] 丁承民，张传生，刘辉．遗传算法纵横谈．信息与控制，1997，26(1)
[48] 席裕庚，柴大佑，遗传算法综述，控制理论与应用，1996，13(6)，697～708
[49] Fogel David D, Evolutionary Computation---Toward a New Philosophy of Machine Intelligence, IEEE Press, 1995.
[50] 丁承民，张传生，利用正交试验法优化配置遗传算法控制参数，西安交通大学电子与资讯工程学院资讯工程研究所研究报告，1996．
[2]章毓晋．图像分割[M]．科学出版社．2001
[3]王爱民，沉兰荪．图像分割研究综述．测控技术，2000，19(5)，1～6
[4]赵荣椿，迟耀斌，朱重光．图像分割技术进展．中国体视学与图像分析．1998；3(2)：121～128
[5]阮秋琦．数字图像处理学[M]，北京，电子工业出版社，2001
[6]Kenneth R Castleman. Digital Image Processing[M]，电子工业出版社，1998
[7]何斌，马天予，王运坚，朱红莲．Visual C++数字图像处理[M]．北京：人民邮电出版社，2001
[8]Dubes R C, et al. MRF model-based algorithms for image segmentation. Proceeding of 3rd ICIPIA, 1990, 808～814
[9]崔屹．图像处理与分析—数学形态学方法及应用[M]．北京：科学出版社，2000
[10]黄建军，赵荣春．基于模糊ART的图像分割．电子学报．29(5)：718～721
[11]Wang J P. Stochastic relaxation on partitions with connected components and its application to image segmentation. IEEE-PAMI, 1998, 20(8): 619～636
[12]Brink A B. Gray level thresholding of image using a correlation criterion. Patter Recognition letters, 1989,9:335～341
[13]Mardia K V and Hainsworth T J. A spatial thresholding method for image segmentation. IEEE Trans, Pattern Analysis and Machine Intelligence, 1988, 10:919～927
[14]付忠良．图像阈值选取方法的构造．中国图像图形学报．2000；5(6)：466～469
[15]靳宏磊，朱蔚萍，李立源，陈维南．二维灰度直方图的最佳分割方
法．模式识别与人工智能，1999；12(3)：329～333
[16]刘文萍，吴立德．图像分割中阈值选取方法比较研究．模式识别与人工智能．1997；10(3)：271～277
[17]谌海新，沈振康，夏放怀．一种基于目标特征的多门限图像分割方法．电子学报，1999；27(3)：32～36
[18]侯格贤，毕笃彦，吴成柯．图像分割质量评价方法研究．中国图像图形学报．2000；5(1)：39～43
[19]Lee S U, Chung S Y. A comparative performance study of several global thresholding techniques for segmentation. Computer Vision Graphics and Image Processing. 1990; 52:171～190
[20]Bengiovanni G. Image segmentation by a multi resolution approach. Pattern Recognition, 1993; 26(12): 1827
[21]贺前华，韦岗，陆以勤．基因算法研究进展．电子学报．1998；26(10)：118～122
[22]Zhang Y J. A survey on evaluation methods for image segmentation. Pattern Recognition. 1996; 29(8): 1335～1346
[23]薛景浩，章毓晋，林行刚．二维遗传算法用于图像动态分割．自动化学报，2000；26(5)：749～753
[24]郑宏，潘励．基于遗传算法的图像阈值的自动选取．中国图像学报，1999；4(4)：317～330
[25]王培珍，杜培明，陈维男．一种多阈值图像自动分割的混合遗传算法．中国图像图形学报．2000；5(1)：44～47
[26]吴成柯，刘靖，侯格贤．图像分割的多参量遗传算法．自动化学报．1998；24(3)：410～413
[27]Goldberg D E. Genetic Algorithms in Search, Optimization & Machine Learning. Addison Wesley Publishing, 1989.
[28]陈国良等．遗传算法及其应用[M]．人民邮电出版社，1996
[29]Z．米凯利维茨．演化程序—遗传算法和资料编码的结合[M]．北京：科学出版社
[30]Rudolph G. Convergence Properties of Canonical Genetic Algorithms. IEEE Trans. Neural Networks. 1994. 5(1), 96～101
[31] Grefenstette J J. Optimization of Control Parameters for Genetic Algorithms. IEEE Trans. SMC. 1986, 16(1), 122～126.
[32] Qi X, Palmieri F. Theoretical Analysis of Evolutionary Algorithms with an Infinite Population Size in Continuous Space Part Ⅰ: Basic Properties of Selection and Mutation. IEEE Trans. Neural Networks, 1994, 102～109.
[33] 恽为民，席裕庚．遗传算法的收敛性和计算效率的分析，控制理论与应用，1996，13(4)，455～460
[34] Hollstien R B. Artificial Genetic Adaptation In Computer Control Systems. Doctoral Dissertation. University of Michigan, 1971.
[35] 王小平，曹立明．遗传算法—理论、应用与软件实现[M]．西安：西安交通大学出版社，2002
[36] 张卫丰，徐宝文，周晓宇，管宇，许蕾．基于遗传算法的搜索引擎调度．微电子学与计算机．2001；(4)：34～38
[37] 张军英，许进，保铮．遗传交叉运算的可达性研究．自动化学报．2002；28(1)：120～125
[38] Gunter Rudolph Convergence analysis of canonical genetic algorithms. IEEE Trans, Neural Networksv. 1994; 5(1):96～101
[39] 辛绯等．遗传算法的适应度函数研究．系统工程与电子技术．1998，11：58～62
[40] 郑志军，郑守淇．进行神经网络中的变异操作数研究．软件学报．2002；13(4)：726～731
[41] Zhang Y J. Segmentation evaluation and comparison; a study of various algorithms. SPIE, 1993, 2094:801～812
[42] 孟庆春，贾培发．关于Genetic算法的研究及应用现状．清华大学报(自然科学版)，1995，35(5)．
[43] Yanowitz S D, Bruckstein A M. A new method for image segmentation. CVGIP, 1989, 46:82～95
[44] 刘大有等．遗传程序设计方法综述．计算机研究与发展，2001；38(2)：213～222
[45] Bhandarkar S M, and Zhang Hui. Image Segmentation Using Evolutionary Computation, 1999; 3(1): 1～21
[46] 张晓缋，方浩，戴冠中．遗传算法的编码机制研究．信息与控制，1999；26(2)：134～139
[47] 丁承民，张传生，刘辉．遗传算法纵横谈．信息与控制，1997，26(1)
[48] 席裕庚，柴大佑，遗传算法综述，控制理论与应用，1996，13(6)，697～708
[49] Fogel David D, Evolutionary Computation---Toward a New Philosophy of Machine Intelligence, IEEE Press, 1995.
[50] 丁承民，张传生，利用正交试验法优化配置遗传算法控制参数，西安交通大学电子与资讯工程学院资讯工程研究所研究报告，1996．
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |