粒子群圆检测算法
李福庆+苏湛
摘要：
针对基于霍夫变换类圆检测算法计算量大、耗时长等问题，提出了一种基于粒子群算法的圆检测算法。该算法通过对图像进行灰度化、滤波去噪与边缘检测等预处理获取边缘图像后，再从中随机选取两点之中点作为初始粒子位置，通过设置最大迭代次数与阈值克服粒子陷入局部最优问题及判断是否检测到圆。对比粒子群圆检测算法与Open CV 3.0中霍夫变换圆检测算法实验数据，结果表明，粒子群圆检测算法在同样检测背景下，检测效果相同，所需时间最短。
关键词：
粒子群算法；霍夫变换；圆检测；适应度；惯性因子；收敛因子
DOIDOI：10.11907/rjdk.172238
中图分类号：TP312
文献标识码：A文章编号文章编号：16727800（2018）001006004
Abstract：In this paper， a circle detection algorithm based on particle swarm optimization （PSO） is proposed to solve the problems of large computation and long time consuming in Hough transform based circle detection algorithm. Firstly， preprocessing to obtain the edge image by grayscale image， filter denoising and edge detection. Then， the midpoint between the two points is randomly selected from the obtained edge image as the position of the initial particle. By setting the maximum number of iterations and the threshold to overcome the problem of local optimum particle and determine whether the circle is detected. Finally， the experimental results of particle swarm circle detection algorithm and Hough transform circle detection algorithm in OpenCV 3.0 are compared. The contrast experiment shows that the algorithm has the same detection effect and the shortest time required under the same detection background.
Key Words：particle swarm optimization （PSO）； hough transform； circle detection； fitness； inertia factor； convergence factor
0引言
圓检测快速高效，广泛应用于胚胎检测、焊盘检测、油桶检测、虹膜检测等方面[14]。最常用且经典的圆检测算法有霍夫变换（HT）[5]与最小二乘法[6]，其中霍夫变换有很高的鲁棒性，为最受欢迎圆检测算法之一。但霍夫变换检测需耗费大量存储空间构建三维累加器存储圆的半径与中心等特征参数，计算量大、速度慢制约了它的推广[78]。虽然现在有许多改进算法，但改进后HT亦需进行参数空间累计，计算量与存储空间有较大提升需求[911]。相对霍夫变换算法，智能算法中启发式优化算法结合圆特征，能够快速检测最佳目标圆，运算量小，不需要耗费更多内存空间。如AyalaRamirez等[12]使用了遗传算法，Cuevas等[13]使用了人工免疫系统（AIS）。上述方法各有优点，但有共同缺点为运算复杂。尤其是GA与AIS等算法，需要完成交叉变异免疫等操作，相对于圆检测显得臃肿，文献[12，13]实验数据也证明了这一点。I Habibie等[14]使用标准粒子群算法，提出了将粒子群算法与霍夫变换融合算法用于胚胎检测。周冬跃等[15]加入惯性因子粒子群算法，提出了一种基于粒子群优化算法的快速圆检测方法。虽然取得了较好效果，但改进的粒子群算法远不止以上2种，粒子群圆检测算法还有很大研究空间。
本文提出的算法在现有成果基础上，分别用标准粒子群算法、Shi等[16]加入惯性因子的改进粒子群算法、Clerc等[17]加入收敛因子的改进粒子群算法，全面分析与仿真粒子群圆检测算法性能。实验证明，Clerc等提出加入收敛因子的粒子群算法能用最少时间检测最佳圆。
算法步骤如下：
Step 1：初始化参数。本次实验，使用5～50个粒子，即N≥5，N≤50 每次运动每个粒子都有对应位置、速度与目标值。用一个结构体定义粒子属性，用2个数组分别记录每次粒子所停留位置的对应目标值，设置学习因子c1与c2默认值为2，最大速度为200。初始化粒子位置。
Step 2：开始迭代至少1次，故检测设置迭代次数是否大于0；如小于等于0，重新设置迭代次数。
Step 3：通过设置不同学习因子、惯性因子与收缩因子，对比Kennedy、Shi及Clerc等人提出的标准PSO与改进PSO区别。
Step 4：使用Kennedy 的算法用式（1）、式（2）；使用Shi的算法用式（3）、式（5）；使用Clerc的算法用式（6）、式（7）、式（2）。
Step 5：计算适应度函数M。
Step 6：用Step 4、Step 5设置所有粒子。如设置完毕进行下一步，如没有，则重复执行Step 4、Step 5。
Step 7：找出每个粒子历史最佳位置，记录该位置与其对应目标值。
Step 8：在整个粒子群体中找出历史最佳位置，记录该位置与该位置所对应目标值。
Step 9：判断是否检测到圆，如果检测到圆，执行Step 11；否则执行下一步。
Step 10：判断是否达到最大迭代次数，如达到了最大迭代次数，则重新初始化粒子，可有效跳出局部最优；如没有，则执行Step 3-Step 9。
Step 11：结束。
2实验结果与数据分析
2.1圆检测实验
算法程序在VS2013与Open CV 3.0 下开发，性能测试计算机配置为Intel Core（TM） i32310M CPU@ 2.10 GHz、32位Windows7系统、3G内存。原图为尺寸780*780、水平分辨率与垂直分辨率为72 dpi、位深度24的JPEG图像。对比本文算法与OpenCV3.0中霍夫变换圆检测算法，圆检测实验如图2所示，不同粒子个数在3种粒子群算法下迭代次数与运行时间如表1所示，本文算法与OPenCV3.0中迭代次数如图3所示，运行时间对比如图4所示。
为了验证本文算法，与OpenCV3.0中霍夫变换圆检测函数作对比。图2（a）为原图，图2（b）为OpenCV3.0的圆检测效果图，图2（c）为本文算法圆检测效果图，实验表明，这2种算法均能对圆进行有效检测。
2.2粒子个数N选取实验
实验分别选取N∈{5，10，15，20，30，40，50}进行实验。用Iter_1与PSO_1表示标准粒子群算法迭代次数与运行时间，Iter_2与PSO_2表示 Shi的改进粒子群算法迭代次数与运行时间，Iter_3与PSO_3表示 Clerc的改进粒子群算法迭代次数与运行时间。每更新一次粒子个数，实验重复进行5次，其中，当N分别取5、10、15、20、30、40与50时，最大迭代次数itermax∈{30，25，20，10}可使粒子有效跳出局部最优。实验数据见表1，迭代次数折线图如图3所示。实验表明：如果迭代次数大于最大迭代次数则表示在迭代过程中陷入局部最优，通过本文算法Step 10可有效跳出局部最优，找到全局最佳粒子；如果小于最大迭代次数则表明在迭代过程中没有陷入局部最优。粒子个数越多，则迭代次数越少，鲁棒性越高。
2.3运行时间对比
实验2.2每更新一次粒子，对应的5次粒子群圆检测算法平均运行时间与OPenCV3.0中霍夫變换圆检测运行时间对比如图4所示。横轴为粒子个数，纵轴为时间，单位为秒。Average表示本次实验所有35组粒子对应的3种粒子群算法平均运行时间与OPenCV3.0中霍夫变换圆检测平均运行时间对比。实验表明，本文提出的粒子群圆检测算法在同等检测效果前提下，执行效率远高于OPenCV3.0中霍夫变换圆检测算法，其中PS0_3效率最高。
3结语
本文在现有粒子群算法基础上，提出了粒子群圆检测算法，介绍了粒子群算法原理与实现流程，将本文算法与OpenCV3.0中霍夫变换检测算法在准确性、运行时间方面作了对比，详细分析了实验数据。结果表明，本文提出的算法与OpenCV3.0中霍夫变换检测算法能检测到同样背景的圆，且耗时最短，适用于实时性要求较高场合。
参考文献：
[1]SATWIKA I P， HABIBIE I， MA' SUM M A， et al.Particle swarm optimation based 2dimensional randomized hough transform for fetal head biometry detection and approximation in ultrasound imaging[C]. IEEE International Conference on Advanced Computer Science and Information Systems， 2015：468473.
[2]OK A O， BASEKI E.Circular oil tank detection from panchromatic satellite images： a new automated approach[J].IEEE Geoscience & Remote Sensing Letters， 2015，12（6）：13471351.
[3]CUEVAS E， WARIO F， OSUNAENCISO V， et al.Fast algorithm for multiplecircle detection on images using learning automata[J].Iet Image Processing， 2012，6（8）：11241135.
[4]CUEVAS E， WARIO F， ZALDIVAR D， et al.Circle detection on images using learning automata[J].Let Computer Vision， 2013，6（6）：121132.
[5]ZHOU B.Using vector quantization of hough transform for circle detection[C].IEEE International Conference on Machine Learning and Applications，2016：447450.
[6]CHI H.A Discussions on the leastsquare method in the course of error theory and data processing[C]. IEEE International Conference on Computational Intelligence and Communication Networks， 2016.
[7]APRINALDI， HABIBIE I， RAHMATULLAH R， et al.ArcPSO： ellipse detection method using particle swarm optimization and arc combination[C].IEEE International Conference on Advanced Computer Science and Information Systems， 2015：408413.
[8]SATWIKA I P， HABIBIE I， MA' SUM M A， et al.Particle swarm optimation based 2dimensional randomized hough transform for fetal head biometry detection and approximation in ultrasound imaging[C]. IEEE International Conference on Advanced Computer Science and Information Systems， 2015：468473.
[9]XU L， OJA E， KULTANEN P.A new curve detection method： randomized hough transform （RHT） [J].Pattern Recognition Letters， 1990，11（5）：331338.
[10]KIRYATI N， ELDAR Y， BRUCKSTEIN A M.A probabilistic hough transform[J].Pattern Recognition， 1991，24（4）：303316.
[11]HAN J H， KOCZY L T， POSTON T.Fuzzy hough transform[J].Pattern Recognition Letters， 1994，15（7）：649658.
[12]AYALARAMIREZ V， GARCIACAPULIN C H， PEREZGARCIA A， et al.Circle detection on images using genetic algorithms[J].Pattern Recognition Letters， 2006，27（6）：652657.
[13]CUEVAS E， OSUNAENCISO V， WARIO F， et al.Automatic multiple circle detection based on artificial immune systems[J].Expert Systems With Applications an International Journal， 2012，39（1）：713722.
[14]HABIBIE I， BOWOLAKSONO A， RAHMATULLAH R， et al.Automatic detection of embryo using particle swarm optimization based hough transform[C].IEEE International Symposium on MicroNanomechatronics and Human Science， 2014：16.
[15]周冬躍，陈健明，林福民，等.一种基于粒子群优化算法的快速圆检测方法[J].光电子激光， 2016， 27（9）：949956.
[16]SHI Y， EBERHART R C.A modified particle swarm optimizer[C].Proceeding of IEEE International Conference on Evolutionary Computaion，1998：6973.
[17]M CLERC AND J KENNEDY.The particle swarmexplosion， stability， and convergence in a multidimensional complex space.[J].IEEE Transactions on Evolutionary Computation， 2002，6（1）：5873.
[18]KENNEDY J，EBERHART R C.Particle swarm optimization [C]. Proceeding of IEEE International Conference on Neural Networks， 1995：19421948.
[19]张选平，杜玉平，秦国强，等.一种动态改变惯性权的自适应粒子群算法[J].西安交通大学学报，2005（10）：58.
（责任编辑：何丽）
摘要：
针对基于霍夫变换类圆检测算法计算量大、耗时长等问题，提出了一种基于粒子群算法的圆检测算法。该算法通过对图像进行灰度化、滤波去噪与边缘检测等预处理获取边缘图像后，再从中随机选取两点之中点作为初始粒子位置，通过设置最大迭代次数与阈值克服粒子陷入局部最优问题及判断是否检测到圆。对比粒子群圆检测算法与Open CV 3.0中霍夫变换圆检测算法实验数据，结果表明，粒子群圆检测算法在同样检测背景下，检测效果相同，所需时间最短。
关键词：
粒子群算法；霍夫变换；圆检测；适应度；惯性因子；收敛因子
DOIDOI：10.11907/rjdk.172238
中图分类号：TP312
文献标识码：A文章编号文章编号：16727800（2018）001006004
Abstract：In this paper， a circle detection algorithm based on particle swarm optimization （PSO） is proposed to solve the problems of large computation and long time consuming in Hough transform based circle detection algorithm. Firstly， preprocessing to obtain the edge image by grayscale image， filter denoising and edge detection. Then， the midpoint between the two points is randomly selected from the obtained edge image as the position of the initial particle. By setting the maximum number of iterations and the threshold to overcome the problem of local optimum particle and determine whether the circle is detected. Finally， the experimental results of particle swarm circle detection algorithm and Hough transform circle detection algorithm in OpenCV 3.0 are compared. The contrast experiment shows that the algorithm has the same detection effect and the shortest time required under the same detection background.
Key Words：particle swarm optimization （PSO）； hough transform； circle detection； fitness； inertia factor； convergence factor
0引言
圓检测快速高效，广泛应用于胚胎检测、焊盘检测、油桶检测、虹膜检测等方面[14]。最常用且经典的圆检测算法有霍夫变换（HT）[5]与最小二乘法[6]，其中霍夫变换有很高的鲁棒性，为最受欢迎圆检测算法之一。但霍夫变换检测需耗费大量存储空间构建三维累加器存储圆的半径与中心等特征参数，计算量大、速度慢制约了它的推广[78]。虽然现在有许多改进算法，但改进后HT亦需进行参数空间累计，计算量与存储空间有较大提升需求[911]。相对霍夫变换算法，智能算法中启发式优化算法结合圆特征，能够快速检测最佳目标圆，运算量小，不需要耗费更多内存空间。如AyalaRamirez等[12]使用了遗传算法，Cuevas等[13]使用了人工免疫系统（AIS）。上述方法各有优点，但有共同缺点为运算复杂。尤其是GA与AIS等算法，需要完成交叉变异免疫等操作，相对于圆检测显得臃肿，文献[12，13]实验数据也证明了这一点。I Habibie等[14]使用标准粒子群算法，提出了将粒子群算法与霍夫变换融合算法用于胚胎检测。周冬跃等[15]加入惯性因子粒子群算法，提出了一种基于粒子群优化算法的快速圆检测方法。虽然取得了较好效果，但改进的粒子群算法远不止以上2种，粒子群圆检测算法还有很大研究空间。
本文提出的算法在现有成果基础上，分别用标准粒子群算法、Shi等[16]加入惯性因子的改进粒子群算法、Clerc等[17]加入收敛因子的改进粒子群算法，全面分析与仿真粒子群圆检测算法性能。实验证明，Clerc等提出加入收敛因子的粒子群算法能用最少时间检测最佳圆。
算法步骤如下：
Step 1：初始化参数。本次实验，使用5～50个粒子，即N≥5，N≤50 每次运动每个粒子都有对应位置、速度与目标值。用一个结构体定义粒子属性，用2个数组分别记录每次粒子所停留位置的对应目标值，设置学习因子c1与c2默认值为2，最大速度为200。初始化粒子位置。
Step 2：开始迭代至少1次，故检测设置迭代次数是否大于0；如小于等于0，重新设置迭代次数。
Step 3：通过设置不同学习因子、惯性因子与收缩因子，对比Kennedy、Shi及Clerc等人提出的标准PSO与改进PSO区别。
Step 4：使用Kennedy 的算法用式（1）、式（2）；使用Shi的算法用式（3）、式（5）；使用Clerc的算法用式（6）、式（7）、式（2）。
Step 5：计算适应度函数M。
Step 6：用Step 4、Step 5设置所有粒子。如设置完毕进行下一步，如没有，则重复执行Step 4、Step 5。
Step 7：找出每个粒子历史最佳位置，记录该位置与其对应目标值。
Step 8：在整个粒子群体中找出历史最佳位置，记录该位置与该位置所对应目标值。
Step 9：判断是否检测到圆，如果检测到圆，执行Step 11；否则执行下一步。
Step 10：判断是否达到最大迭代次数，如达到了最大迭代次数，则重新初始化粒子，可有效跳出局部最优；如没有，则执行Step 3-Step 9。
Step 11：结束。
2实验结果与数据分析
2.1圆检测实验
算法程序在VS2013与Open CV 3.0 下开发，性能测试计算机配置为Intel Core（TM） i32310M CPU@ 2.10 GHz、32位Windows7系统、3G内存。原图为尺寸780*780、水平分辨率与垂直分辨率为72 dpi、位深度24的JPEG图像。对比本文算法与OpenCV3.0中霍夫变换圆检测算法，圆检测实验如图2所示，不同粒子个数在3种粒子群算法下迭代次数与运行时间如表1所示，本文算法与OPenCV3.0中迭代次数如图3所示，运行时间对比如图4所示。
为了验证本文算法，与OpenCV3.0中霍夫变换圆检测函数作对比。图2（a）为原图，图2（b）为OpenCV3.0的圆检测效果图，图2（c）为本文算法圆检测效果图，实验表明，这2种算法均能对圆进行有效检测。
2.2粒子个数N选取实验
实验分别选取N∈{5，10，15，20，30，40，50}进行实验。用Iter_1与PSO_1表示标准粒子群算法迭代次数与运行时间，Iter_2与PSO_2表示 Shi的改进粒子群算法迭代次数与运行时间，Iter_3与PSO_3表示 Clerc的改进粒子群算法迭代次数与运行时间。每更新一次粒子个数，实验重复进行5次，其中，当N分别取5、10、15、20、30、40与50时，最大迭代次数itermax∈{30，25，20，10}可使粒子有效跳出局部最优。实验数据见表1，迭代次数折线图如图3所示。实验表明：如果迭代次数大于最大迭代次数则表示在迭代过程中陷入局部最优，通过本文算法Step 10可有效跳出局部最优，找到全局最佳粒子；如果小于最大迭代次数则表明在迭代过程中没有陷入局部最优。粒子个数越多，则迭代次数越少，鲁棒性越高。
2.3运行时间对比
实验2.2每更新一次粒子，对应的5次粒子群圆检测算法平均运行时间与OPenCV3.0中霍夫變换圆检测运行时间对比如图4所示。横轴为粒子个数，纵轴为时间，单位为秒。Average表示本次实验所有35组粒子对应的3种粒子群算法平均运行时间与OPenCV3.0中霍夫变换圆检测平均运行时间对比。实验表明，本文提出的粒子群圆检测算法在同等检测效果前提下，执行效率远高于OPenCV3.0中霍夫变换圆检测算法，其中PS0_3效率最高。
3结语
本文在现有粒子群算法基础上，提出了粒子群圆检测算法，介绍了粒子群算法原理与实现流程，将本文算法与OpenCV3.0中霍夫变换检测算法在准确性、运行时间方面作了对比，详细分析了实验数据。结果表明，本文提出的算法与OpenCV3.0中霍夫变换检测算法能检测到同样背景的圆，且耗时最短，适用于实时性要求较高场合。
参考文献：
[1]SATWIKA I P， HABIBIE I， MA' SUM M A， et al.Particle swarm optimation based 2dimensional randomized hough transform for fetal head biometry detection and approximation in ultrasound imaging[C]. IEEE International Conference on Advanced Computer Science and Information Systems， 2015：468473.
[2]OK A O， BASEKI E.Circular oil tank detection from panchromatic satellite images： a new automated approach[J].IEEE Geoscience & Remote Sensing Letters， 2015，12（6）：13471351.
[3]CUEVAS E， WARIO F， OSUNAENCISO V， et al.Fast algorithm for multiplecircle detection on images using learning automata[J].Iet Image Processing， 2012，6（8）：11241135.
[4]CUEVAS E， WARIO F， ZALDIVAR D， et al.Circle detection on images using learning automata[J].Let Computer Vision， 2013，6（6）：121132.
[5]ZHOU B.Using vector quantization of hough transform for circle detection[C].IEEE International Conference on Machine Learning and Applications，2016：447450.
[6]CHI H.A Discussions on the leastsquare method in the course of error theory and data processing[C]. IEEE International Conference on Computational Intelligence and Communication Networks， 2016.
[7]APRINALDI， HABIBIE I， RAHMATULLAH R， et al.ArcPSO： ellipse detection method using particle swarm optimization and arc combination[C].IEEE International Conference on Advanced Computer Science and Information Systems， 2015：408413.
[8]SATWIKA I P， HABIBIE I， MA' SUM M A， et al.Particle swarm optimation based 2dimensional randomized hough transform for fetal head biometry detection and approximation in ultrasound imaging[C]. IEEE International Conference on Advanced Computer Science and Information Systems， 2015：468473.
[9]XU L， OJA E， KULTANEN P.A new curve detection method： randomized hough transform （RHT） [J].Pattern Recognition Letters， 1990，11（5）：331338.
[10]KIRYATI N， ELDAR Y， BRUCKSTEIN A M.A probabilistic hough transform[J].Pattern Recognition， 1991，24（4）：303316.
[11]HAN J H， KOCZY L T， POSTON T.Fuzzy hough transform[J].Pattern Recognition Letters， 1994，15（7）：649658.
[12]AYALARAMIREZ V， GARCIACAPULIN C H， PEREZGARCIA A， et al.Circle detection on images using genetic algorithms[J].Pattern Recognition Letters， 2006，27（6）：652657.
[13]CUEVAS E， OSUNAENCISO V， WARIO F， et al.Automatic multiple circle detection based on artificial immune systems[J].Expert Systems With Applications an International Journal， 2012，39（1）：713722.
[14]HABIBIE I， BOWOLAKSONO A， RAHMATULLAH R， et al.Automatic detection of embryo using particle swarm optimization based hough transform[C].IEEE International Symposium on MicroNanomechatronics and Human Science， 2014：16.
[15]周冬躍，陈健明，林福民，等.一种基于粒子群优化算法的快速圆检测方法[J].光电子激光， 2016， 27（9）：949956.
[16]SHI Y， EBERHART R C.A modified particle swarm optimizer[C].Proceeding of IEEE International Conference on Evolutionary Computaion，1998：6973.
[17]M CLERC AND J KENNEDY.The particle swarmexplosion， stability， and convergence in a multidimensional complex space.[J].IEEE Transactions on Evolutionary Computation， 2002，6（1）：5873.
[18]KENNEDY J，EBERHART R C.Particle swarm optimization [C]. Proceeding of IEEE International Conference on Neural Networks， 1995：19421948.
[19]张选平，杜玉平，秦国强，等.一种动态改变惯性权的自适应粒子群算法[J].西安交通大学学报，2005（10）：58.
（责任编辑：何丽）
