基于混沌粒子群优化算法的电力线检测

徐胜舟，胡怀飞

(1中南民族大学计算机科学学院，武汉430074;2中南民族大学生物医学工程学院，武汉430074)

由于我国国土辽阔，地形复杂，平原少，丘陵及山区较多，气象条件复杂［1］，而无人直升机巡线效率高，因此得到了越来越多的重视.无人机巡线的首要任务便是识别电力线.另一方面，直升机飞行过程中容易与电力线发生碰撞，这对直升机的安全构成了威胁.通过机载摄像头把直升机前方的航道状况记录下来，利用图像处理的方法实现电力线的自动检测是一个具有挑战性和现实意义的课题.

电力线在图像中表现为近似直线，直线检测是计算机视觉和模式识别中最重要的任务之一.直线检测的方法有很多，Hough变换［2］(HT)是其中最经典的算法，其基本原理是利用点和线之间的对偶性.它把直线上点的坐标变换到过点的直线系数域，巧妙地利用了共线和直线相交的关系，使直线检测问题转化为计数问题.其优点是受图像中的间隙和噪声影响较小;缺点在于，Hough变换采用从图像域“投票”到参数域的穷尽式搜索模式，其计算量大，占用内存资源多［3］.另外，重复计算出的直线会很多，且难以判断哪些直线被重复计算［4］.因此，许多学者致力于研究提高Hough变换检测效率和精度的方法［5］，于是有了快速 Hough变换、多分辨率Hough变换、概率Hough变换［6］、随机Hough变换等改进算法［7］.也有学者将Hough变换后解的参数作为粒子位置［8］，采用一种精简粒子群优化算法对粒子进行优化，该方法在复杂背景和高噪声图像的检测中取得了较好效果.

本文基于Hough变换的“投票”思想并结合粒子群优化算法，提出一种基于混沌粒子群(CPSO)的直线检测算法，并将其应用于电力线检测.该方法可以有效减少重复计算，提高计算速度，且能获得更好的检测性能.

1 系统设计

图1是一幅从实景拍摄的视频中获取的电力线红外图像(大小为384×288像素，256灰阶).从图1中可见:电力线在图像中表现为长而连续的线，且接近水平方向，可近似看作直线.于是电力线检测问题可以转化为寻找图中的直线.另外，从图中也可发现电力线检测的难点:图像的背景相当复杂，天空、山体、电线杆及树木等背景对电力线的灰度有较大影响;根据红外成像原理，近处电力线在图像中的信号强度较强(电力线的宽度有多个像素)，而远处电力线则较弱.因此，在检测过程中，既要求直线检测算法能够保持高敏感度，同时要利用待检测目的特点尽可能地去除干扰物.

图1 电力线红外图像Fig.1 Infrared image of power lines

基于以上分析，本文设计出一种基于混沌粒子群优化算法的电力线检测方法:首先从视频中提取红外图像并对其进行边缘检测得到二值的边缘图像;然后用每个粒子代表一条直线，以该直线上的像素数目作为对应粒子的适应度，采用混沌粒子群优化算法对粒子进行迭代优化;迭代结束后判断群体最佳粒子的适应度值是否大于预先设定的阈值，如果是则从候选边缘点中取出与最佳粒子共线的边缘点，继续检测下一条电力线，否则图像中已没有符合要求的电力线，算法结束.具体的算法流程图如图2所示.

图2 电力线检测流程Fig.2 Detection process of power line

2 边缘检测

尽管目前已有很多不同的边缘检测方法，但没有一种方法能够适用于所有的图像.Sobel算子是一组方向算子，其中一个是垂直方向的，用来检测水平边缘，另一个是水平方向的，用来检测垂直边缘.它不是简单求平均再差分，而是加强了中心像素上下左右4个方向上像素的权重.由于电力线接近于水平方向，因此本文采用垂直方向的Sobel算子来进行检测.

图3是采用垂直方向的Sobel算子对图1进行边缘检测后得到的二值图像，图中白色像素点即为后续电力线提取过程中的边缘候选点.很显然，图中比较长的几条直线(近似)对应着电力线.另外，由于采用的是Sobel垂直方向算子，因此电线杆等垂直方向的直线被去掉了，但山峰线、远处地平线等仍对电力线的检测造成一定的干扰.

图3 Sobel算子边缘检测结果Fig.3 Edge detection result by Sobel

3 电力线提取

由于电力线在图像中表征为长而连续的线，其提取过程可转化为寻找图像中由一定数量的边缘点像素构成的直线.本文提出一种基于混沌粒子群优化算法的直线检测方法，并用来对电力线进行提取.

3.1 Hough 变换

利用Hough变换提取直线是一种变换域提取直线的方法，它巧妙地利用了共线和直线相交的关系，使直线的提取问题转化为计数问题.平面Oxy上的一条直线可以表示为:

其中θ是直线法线与x轴的夹角，ρ是直线到坐标系原点的距离.可以发现，平面Oxy中的一条直线与平面Oθρ中的一点一一对应，平面Oxy中的一点与平面Oθρ中的一条曲线一一对应，而且，平面Oxy中的共线点所对应的Oθρ的曲线相交于一点.因此，对Oxy平面中的每一点，给出它在Oθρ平面中对应的曲线，凡是这条曲线经过的位置，对应的计数加1，于是计数阵列元素的数值等于共线的点数.统计共线的点数，即可提取相应直线.

3.2 粒子群优化算法

粒子群优化算法(PSO)是一种模仿诸如鸟群、鱼群的群体捕食行为的智能优化算法.PSO的基本思想是通过群体中个体(粒子)之间的协作和信息共享来寻找最优解.也就是说，每个粒子可以从群体中所有其他粒子的环境信息和以往的经验中获益，并结合自身的环境信息和以往经验来动态调整自身位置.根据计算出的适应度，群体中的每个个体移动到它所认为的最好位置.

由于两点决定一条直线，而每个粒子代表一条直线，因此，粒子可以用两个像素点的4个坐标值来表示.假设初始种群由个粒子构成，每个粒子的位置和速度分别表示为:Xi=(xi1，xi2，xi3，xi4)T和 Vi=(vi1，vi2，vi3，vi4)T，其中，i=1，2，…，N，而xi1，xi2分别为第i个粒子的第1个点的横坐标和纵坐标，xi3，xi4分别为第i个粒子的第2个点的横坐标和纵坐标，xi1，xi2，xi3，xi4则分别为第 i个粒子的两个点在横纵坐标方向上的飞行速度.每个粒子在4维搜索空间中运动.粒子的适应度值为与该粒子共线的边缘点的数目.在本文中，通过计算边缘点到直线的距离来判断该点是否在直线上，即与粒子共线.对于第i个粒子，其先前所到达过的最佳位置，即适应度值最高的位置，记作个体最佳位置 Pi=(pi1，pi2，pi3，pi4)T.而对于整个群体，其先前所到达过的最佳位置记作群体最佳位置 Pg=(pg1，pg2，pg3，pg4)T.每个粒子的位置和速度按照下面的式(2)和式(3)进行更新:

其中，t代表迭代次数，r1和r2是正态分布的介于0和1之间的随机数.内部权重w用来控制先前的历史速度对当前的影响程度，其在权衡个体最优和群体最优上起到一定的作用.c1和c2是学习因子，也称加速因子，其使粒子具有自我学习和向群体中优秀个体学习的能力，从而使每个粒子从自身的历史最优值向整个群体中的历史最优值靠近.实验中学习因子和权重取经验值:c1=c2=1.5，w=0.7 .

PSO算法由于其简单、容易实现并具有可靠的收敛性而被广泛应用，但有时易早熟而陷入局部最优解.为此，混沌粒子群优化算法［9］被提出.

3.3 混沌粒子群优化算法

本文设计了一种简单而有效的混沌粒子群优化算法.该算法引入了混沌变量，产生一个混沌序列.假设混沌粒子的位置为 CX=(cx1，cx2，cx3，cx4)T，对Logistic方程:

迭代K－1次来获得K个混沌粒子.用混沌序列中拥有最优适应值的粒子替代当前粒子群中的最差粒子.这种改进能有效降低传统PSO算法的计算时间，且提高解的精度.

具体的电力线提取算法如下.

1)从候选边缘点中随机选择2个点P1(x1，x2)和 P2(x3，x4)，以这两点的横纵坐标值 x1，x2，x3，x4作为粒子的位置向量X的4个分量，即X=(x1，x2，x3，x4)T;

2)重复步骤1)，初始化由N个粒子组成初始种群;

3)随机初始化初始种群中每个粒子的运动速度 Vi=(vi1，vi2，vi3，vi4)T，(i=1，2，…，N);

4)计算粒子的适应度值.对每一个粒子，根据其位置向量得到一直线方程.遍历其它候选边缘点，统计位于直线之上的边缘点数目并将其作为该粒子的适应度值，计算公式如下:

5)将每个粒子的当前位置的适应度值与其历史最佳位置的适应度值相比较，取较大者所对应的位置作为该粒子新的历史最佳位置;

6)从所有粒子中选择适应度最高/低的粒子作为群体最佳/差粒子;

7)根据公式(2)更新每个粒子的运动速度;

8)根据公式(3)更新每个粒子的位置;

9)采用方程(4)产生一序列混沌粒子，并用混沌粒子中拥有最优适应值的粒子替代当前粒子群中的最差粒子;

10)转步骤4)，继续进行迭代直至达到最大迭代次数;

11)判断群体最佳粒子的适应度是否高于所设定的阈值，如果是，则该粒子的两个点所决定的一条直线即为电力线所在直线，去掉候选边缘点中所有在此直线上的像素点，转步骤1)，继续检测下一条直线;否则，即认为当前已没有符合条件的电力线，检测完毕.

图4 电力线检测结果Fig.4 Result of power line detection

4 实验结果及分析

从红外摄像头采集的视频中提取电力线图像，并利用这些图像对本文所提出的算法的性能进行实验验证.实验工具采用Matlab R2008，在一台Intel i3 2.3GHz，内存4GB的PC机上完成.

图4是对图3进行直线检测的结果，其中图4(a)采用的是经典的Hough变换(HT)算法，而图4(b)则采用的是本文提出的基于混沌粒子群优化算法(CPSO)的检测方法.图5(a)是从视频中随机选取的另外一幅图像，图5(c)和图5(d)则分别是采用HT和CPSO方法的检测结果.

为进一步对算法进行定量分析和对比，我们还利用文献［8］中的RPSO算法分别对图4和图5中的电力线进行电力线检测，表1给出了具体的检测结果.对于检测效率，HT检测算法分别用时202ms和321ms，RPSO方法分别为 157ms和 231ms，而CPSO算法则为86ms和128ms，显然，CPSO算法的检测效率明显高于另两种算法.HT采用从图像域“投票”到参数域的穷尽式搜索模式，而CPSO和RPSO则只需从待检测边缘点中随机选取少量种子点来完成直线搜索，因此可以有效提高搜索效率.RPSO算法判断一个待检测点是否与已知点共线时采用的是经典HT中通过计算和比较参数θ和ρ的方式，而本文的CPSO算法则采用了简化的点到直线距离来进行判断，进一步提高计算效率.

图5 电力线检测结果Fig.5 Result of power line detection

对于检测质量，图5中HT算法漏检了图像上方最远处的电力线，而CPSO算法则将图中可见的电力线都检测出来了(RPSO算法的检测结果与CPSO近似).另外，从结果可见，HT算法的检测结果似乎“更粗，更完整”，事实上，这正是该算法重复计算的结果:HT算法在图4和图5中分别检测出21条和36条直线，CPSO算法则分别为5条和8条，而在实际图像中人眼可分辨的电力线数目分别为4条和8条，即CPSO算法大大减少了HT算法中存在的重复计算现象.

表1 本文算法与Hough变换算法检测结果对比Tab.1 Comparison of detection results by Hough transform and our method

究其原因，HT算法在实际计算中所考虑的变换参数值及值是离散的，某直线上的部分像素有可能也同时被认为是与它成一微小夹角的另一直线上的点，这样重复计算出的直线就会很多，且难以判断哪些直线被重复计算.而本文提出的CPSO检测算法，则在每次检测出一条直线后就将该直线从边缘候选点中去掉，这样就有效的避免了检测下一条直线时的重复计算.

5 结语

本文基于Hough变换的统计思想并结合粒子群优化算法，提出了一种基于混沌粒子群优化算法的直线检测算法并将其应用于电力线检测.对实际图像中的电力线的检测结果表明，所提出的算法与Hough变换相比不仅可以提高计算速度，且能获得更好的检测性能.

［1］郑天茹，王滨海，刘 俍，等.电力巡线无人直升机障碍规避系统［J］.山东电力技术，2012，185(1):14-17.

［2］Hough P V C.Method and means for recognizing complex patterns:US Patent，3069654［P］.1962.

［3］刘 进，马 梁，刘忠训，等.基于随机Hough变换的零基线正弦曲线检测［J］.计算机工程，2010，36(15):1-4.

［4］刘桂雄，申柏华，冯云庆，等.基于改进的 Hough变换图像分割方法［J］.光学精密工程，2002，10(3):257-260.

［5］朱院娟，郭斯羽，朱志杰，等.结合LTS和Hough变换的直线检测方法［J］.计算机工程，2012，38(14):206-210.

［6］Gao K，Wang Y，Ni G.An improved linear target detection method based on probabilistic hough transform in a remote sensing image［J］，Mechanical Engineering and Technology，2012，125(4):433-440.

［7］Dube D，Zell A.Real-time plane extraction from depth images with the Randomized Hough Transform［C］//IEEE.International Conference on Computer Vision.Barcelona:IEEE，2011:1084-1091.

［8］张英涛，黄剑华，唐降龙，等.一种基于精简粒子群优化的霍夫变换算法［J］.天津大学学报，2011，44(002):162-167.

［9］Liu B，Wang L，Jin Y H，et al.Improved particle swarm optimization combined with chaos［J］.Chaos，Solitons ＆ Fractals，2005，25(5):1261-1271.