徐勝舟，胡懷飛

(1中南民族大學(xué)計算機(jī)科學(xué)學(xué)院，武漢430074;2中南民族大學(xué)生物醫(yī)學(xué)工程學(xué)院，武漢430074)

由于我國國土遼闊，地形復(fù)雜，平原少，丘陵及山區(qū)較多，氣象條件復(fù)雜［1］，而無人直升機(jī)巡線效率高，因此得到了越來越多的重視.無人機(jī)巡線的首要任務(wù)便是識別電力線.另一方面，直升機(jī)飛行過程中容易與電力線發(fā)生碰撞，這對直升機(jī)的安全構(gòu)成了威脅.通過機(jī)載攝像頭把直升機(jī)前方的航道狀況記錄下來，利用圖像處理的方法實現(xiàn)電力線的自動檢測是一個具有挑戰(zhàn)性和現(xiàn)實意義的課題.

電力線在圖像中表現(xiàn)為近似直線，直線檢測是計算機(jī)視覺和模式識別中最重要的任務(wù)之一.直線檢測的方法有很多，Hough變換［2］(HT)是其中最經(jīng)典的算法，其基本原理是利用點和線之間的對偶性.它把直線上點的坐標(biāo)變換到過點的直線系數(shù)域，巧妙地利用了共線和直線相交的關(guān)系，使直線檢測問題轉(zhuǎn)化為計數(shù)問題.其優(yōu)點是受圖像中的間隙和噪聲影響較小;缺點在于，Hough變換采用從圖像域“投票”到參數(shù)域的窮盡式搜索模式，其計算量大，占用內(nèi)存資源多［3］.另外，重復(fù)計算出的直線會很多，且難以判斷哪些直線被重復(fù)計算［4］.因此，許多學(xué)者致力于研究提高Hough變換檢測效率和精度的方法［5］，于是有了快速 Hough變換、多分辨率Hough變換、概率Hough變換［6］、隨機(jī)Hough變換等改進(jìn)算法［7］.也有學(xué)者將Hough變換后解的參數(shù)作為粒子位置［8］，采用一種精簡粒子群優(yōu)化算法對粒子進(jìn)行優(yōu)化，該方法在復(fù)雜背景和高噪聲圖像的檢測中取得了較好效果.

本文基于Hough變換的“投票”思想并結(jié)合粒子群優(yōu)化算法，提出一種基于混沌粒子群(CPSO)的直線檢測算法，并將其應(yīng)用于電力線檢測.該方法可以有效減少重復(fù)計算，提高計算速度，且能獲得更好的檢測性能.

1 系統(tǒng)設(shè)計

圖1是一幅從實景拍攝的視頻中獲取的電力線紅外圖像(大小為384×288像素，256灰階).從圖1中可見:電力線在圖像中表現(xiàn)為長而連續(xù)的線，且接近水平方向，可近似看作直線.于是電力線檢測問題可以轉(zhuǎn)化為尋找圖中的直線.另外，從圖中也可發(fā)現(xiàn)電力線檢測的難點:圖像的背景相當(dāng)復(fù)雜，天空、山體、電線桿及樹木等背景對電力線的灰度有較大影響;根據(jù)紅外成像原理，近處電力線在圖像中的信號強(qiáng)度較強(qiáng)(電力線的寬度有多個像素)，而遠(yuǎn)處電力線則較弱.因此，在檢測過程中，既要求直線檢測算法能夠保持高敏感度，同時要利用待檢測目的特點盡可能地去除干擾物.

圖1 電力線紅外圖像Fig.1 Infrared image of power lines

基于以上分析，本文設(shè)計出一種基于混沌粒子群優(yōu)化算法的電力線檢測方法:首先從視頻中提取紅外圖像并對其進(jìn)行邊緣檢測得到二值的邊緣圖像;然后用每個粒子代表一條直線，以該直線上的像素數(shù)目作為對應(yīng)粒子的適應(yīng)度，采用混沌粒子群優(yōu)化算法對粒子進(jìn)行迭代優(yōu)化;迭代結(jié)束后判斷群體最佳粒子的適應(yīng)度值是否大于預(yù)先設(shè)定的閾值，如果是則從候選邊緣點中取出與最佳粒子共線的邊緣點，繼續(xù)檢測下一條電力線，否則圖像中已沒有符合要求的電力線，算法結(jié)束.具體的算法流程圖如圖2所示.

圖2 電力線檢測流程Fig.2 Detection process of power line

2 邊緣檢測

盡管目前已有很多不同的邊緣檢測方法，但沒有一種方法能夠適用于所有的圖像.Sobel算子是一組方向算子，其中一個是垂直方向的，用來檢測水平邊緣，另一個是水平方向的，用來檢測垂直邊緣.它不是簡單求平均再差分，而是加強(qiáng)了中心像素上下左右4個方向上像素的權(quán)重.由于電力線接近于水平方向，因此本文采用垂直方向的Sobel算子來進(jìn)行檢測.

圖3是采用垂直方向的Sobel算子對圖1進(jìn)行邊緣檢測后得到的二值圖像，圖中白色像素點即為后續(xù)電力線提取過程中的邊緣候選點.很顯然，圖中比較長的幾條直線(近似)對應(yīng)著電力線.另外，由于采用的是Sobel垂直方向算子，因此電線桿等垂直方向的直線被去掉了，但山峰線、遠(yuǎn)處地平線等仍對電力線的檢測造成一定的干擾.

圖3 Sobel算子邊緣檢測結(jié)果Fig.3 Edge detection result by Sobel

3 電力線提取

由于電力線在圖像中表征為長而連續(xù)的線，其提取過程可轉(zhuǎn)化為尋找圖像中由一定數(shù)量的邊緣點像素構(gòu)成的直線.本文提出一種基于混沌粒子群優(yōu)化算法的直線檢測方法，并用來對電力線進(jìn)行提取.

3.1 Hough 變換

利用Hough變換提取直線是一種變換域提取直線的方法，它巧妙地利用了共線和直線相交的關(guān)系，使直線的提取問題轉(zhuǎn)化為計數(shù)問題.平面Oxy上的一條直線可以表示為:

其中θ是直線法線與x軸的夾角，ρ是直線到坐標(biāo)系原點的距離.可以發(fā)現(xiàn)，平面Oxy中的一條直線與平面Oθρ中的一點一一對應(yīng)，平面Oxy中的一點與平面Oθρ中的一條曲線一一對應(yīng)，而且，平面Oxy中的共線點所對應(yīng)的Oθρ的曲線相交于一點.因此，對Oxy平面中的每一點，給出它在Oθρ平面中對應(yīng)的曲線，凡是這條曲線經(jīng)過的位置，對應(yīng)的計數(shù)加1，于是計數(shù)陣列元素的數(shù)值等于共線的點數(shù).統(tǒng)計共線的點數(shù)，即可提取相應(yīng)直線.

3.2 粒子群優(yōu)化算法

粒子群優(yōu)化算法(PSO)是一種模仿諸如鳥群、魚群的群體捕食行為的智能優(yōu)化算法.PSO的基本思想是通過群體中個體(粒子)之間的協(xié)作和信息共享來尋找最優(yōu)解.也就是說，每個粒子可以從群體中所有其他粒子的環(huán)境信息和以往的經(jīng)驗中獲益，并結(jié)合自身的環(huán)境信息和以往經(jīng)驗來動態(tài)調(diào)整自身位置.根據(jù)計算出的適應(yīng)度，群體中的每個個體移動到它所認(rèn)為的最好位置.

由于兩點決定一條直線，而每個粒子代表一條直線，因此，粒子可以用兩個像素點的4個坐標(biāo)值來表示.假設(shè)初始種群由個粒子構(gòu)成，每個粒子的位置和速度分別表示為:Xi=(xi1，xi2，xi3，xi4)T和 Vi=(vi1，vi2，vi3，vi4)T，其中，i=1，2，…，N，而xi1，xi2分別為第i個粒子的第1個點的橫坐標(biāo)和縱坐標(biāo)，xi3，xi4分別為第i個粒子的第2個點的橫坐標(biāo)和縱坐標(biāo)，xi1，xi2，xi3，xi4則分別為第 i個粒子的兩個點在橫縱坐標(biāo)方向上的飛行速度.每個粒子在4維搜索空間中運動.粒子的適應(yīng)度值為與該粒子共線的邊緣點的數(shù)目.在本文中，通過計算邊緣點到直線的距離來判斷該點是否在直線上，即與粒子共線.對于第i個粒子，其先前所到達(dá)過的最佳位置，即適應(yīng)度值最高的位置，記作個體最佳位置 Pi=(pi1，pi2，pi3，pi4)T.而對于整個群體，其先前所到達(dá)過的最佳位置記作群體最佳位置 Pg=(pg1，pg2，pg3，pg4)T.每個粒子的位置和速度按照下面的式(2)和式(3)進(jìn)行更新:

其中，t代表迭代次數(shù)，r1和r2是正態(tài)分布的介于0和1之間的隨機(jī)數(shù).內(nèi)部權(quán)重w用來控制先前的歷史速度對當(dāng)前的影響程度，其在權(quán)衡個體最優(yōu)和群體最優(yōu)上起到一定的作用.c1和c2是學(xué)習(xí)因子，也稱加速因子，其使粒子具有自我學(xué)習(xí)和向群體中優(yōu)秀個體學(xué)習(xí)的能力，從而使每個粒子從自身的歷史最優(yōu)值向整個群體中的歷史最優(yōu)值靠近.實驗中學(xué)習(xí)因子和權(quán)重取經(jīng)驗值:c1=c2=1.5，w=0.7 .

PSO算法由于其簡單、容易實現(xiàn)并具有可靠的收斂性而被廣泛應(yīng)用，但有時易早熟而陷入局部最優(yōu)解.為此，混沌粒子群優(yōu)化算法［9］被提出.

3.3 混沌粒子群優(yōu)化算法

本文設(shè)計了一種簡單而有效的混沌粒子群優(yōu)化算法.該算法引入了混沌變量，產(chǎn)生一個混沌序列.假設(shè)混沌粒子的位置為 CX=(cx1，cx2，cx3，cx4)T，對Logistic方程:

迭代K－1次來獲得K個混沌粒子.用混沌序列中擁有最優(yōu)適應(yīng)值的粒子替代當(dāng)前粒子群中的最差粒子.這種改進(jìn)能有效降低傳統(tǒng)PSO算法的計算時間，且提高解的精度.

具體的電力線提取算法如下.

1)從候選邊緣點中隨機(jī)選擇2個點P1(x1，x2)和 P2(x3，x4)，以這兩點的橫縱坐標(biāo)值 x1，x2，x3，x4作為粒子的位置向量X的4個分量，即X=(x1，x2，x3，x4)T;

2)重復(fù)步驟1)，初始化由N個粒子組成初始種群;

3)隨機(jī)初始化初始種群中每個粒子的運動速度 Vi=(vi1，vi2，vi3，vi4)T，(i=1，2，…，N);

4)計算粒子的適應(yīng)度值.對每一個粒子，根據(jù)其位置向量得到一直線方程.遍歷其它候選邊緣點，統(tǒng)計位于直線之上的邊緣點數(shù)目并將其作為該粒子的適應(yīng)度值，計算公式如下:

5)將每個粒子的當(dāng)前位置的適應(yīng)度值與其歷史最佳位置的適應(yīng)度值相比較，取較大者所對應(yīng)的位置作為該粒子新的歷史最佳位置;

6)從所有粒子中選擇適應(yīng)度最高/低的粒子作為群體最佳/差粒子;

7)根據(jù)公式(2)更新每個粒子的運動速度;

8)根據(jù)公式(3)更新每個粒子的位置;

9)采用方程(4)產(chǎn)生一序列混沌粒子，并用混沌粒子中擁有最優(yōu)適應(yīng)值的粒子替代當(dāng)前粒子群中的最差粒子;

10)轉(zhuǎn)步驟4)，繼續(xù)進(jìn)行迭代直至達(dá)到最大迭代次數(shù);

11)判斷群體最佳粒子的適應(yīng)度是否高于所設(shè)定的閾值，如果是，則該粒子的兩個點所決定的一條直線即為電力線所在直線，去掉候選邊緣點中所有在此直線上的像素點，轉(zhuǎn)步驟1)，繼續(xù)檢測下一條直線;否則，即認(rèn)為當(dāng)前已沒有符合條件的電力線，檢測完畢.

圖4 電力線檢測結(jié)果Fig.4 Result of power line detection

4 實驗結(jié)果及分析

從紅外攝像頭采集的視頻中提取電力線圖像，并利用這些圖像對本文所提出的算法的性能進(jìn)行實驗驗證.實驗工具采用Matlab R2008，在一臺Intel i3 2.3GHz，內(nèi)存4GB的PC機(jī)上完成.

圖4是對圖3進(jìn)行直線檢測的結(jié)果，其中圖4(a)采用的是經(jīng)典的Hough變換(HT)算法，而圖4(b)則采用的是本文提出的基于混沌粒子群優(yōu)化算法(CPSO)的檢測方法.圖5(a)是從視頻中隨機(jī)選取的另外一幅圖像，圖5(c)和圖5(d)則分別是采用HT和CPSO方法的檢測結(jié)果.

為進(jìn)一步對算法進(jìn)行定量分析和對比，我們還利用文獻(xiàn)［8］中的RPSO算法分別對圖4和圖5中的電力線進(jìn)行電力線檢測，表1給出了具體的檢測結(jié)果.對于檢測效率，HT檢測算法分別用時202ms和321ms，RPSO方法分別為 157ms和 231ms，而CPSO算法則為86ms和128ms，顯然，CPSO算法的檢測效率明顯高于另兩種算法.HT采用從圖像域“投票”到參數(shù)域的窮盡式搜索模式，而CPSO和RPSO則只需從待檢測邊緣點中隨機(jī)選取少量種子點來完成直線搜索，因此可以有效提高搜索效率.RPSO算法判斷一個待檢測點是否與已知點共線時采用的是經(jīng)典HT中通過計算和比較參數(shù)θ和ρ的方式，而本文的CPSO算法則采用了簡化的點到直線距離來進(jìn)行判斷，進(jìn)一步提高計算效率.

圖5 電力線檢測結(jié)果Fig.5 Result of power line detection

對于檢測質(zhì)量，圖5中HT算法漏檢了圖像上方最遠(yuǎn)處的電力線，而CPSO算法則將圖中可見的電力線都檢測出來了(RPSO算法的檢測結(jié)果與CPSO近似).另外，從結(jié)果可見，HT算法的檢測結(jié)果似乎“更粗，更完整”，事實上，這正是該算法重復(fù)計算的結(jié)果:HT算法在圖4和圖5中分別檢測出21條和36條直線，CPSO算法則分別為5條和8條，而在實際圖像中人眼可分辨的電力線數(shù)目分別為4條和8條，即CPSO算法大大減少了HT算法中存在的重復(fù)計算現(xiàn)象.

表1 本文算法與Hough變換算法檢測結(jié)果對比Tab.1 Comparison of detection results by Hough transform and our method

究其原因，HT算法在實際計算中所考慮的變換參數(shù)值及值是離散的，某直線上的部分像素有可能也同時被認(rèn)為是與它成一微小夾角的另一直線上的點，這樣重復(fù)計算出的直線就會很多，且難以判斷哪些直線被重復(fù)計算.而本文提出的CPSO檢測算法，則在每次檢測出一條直線后就將該直線從邊緣候選點中去掉，這樣就有效的避免了檢測下一條直線時的重復(fù)計算.

5 結(jié)語

本文基于Hough變換的統(tǒng)計思想并結(jié)合粒子群優(yōu)化算法，提出了一種基于混沌粒子群優(yōu)化算法的直線檢測算法并將其應(yīng)用于電力線檢測.對實際圖像中的電力線的檢測結(jié)果表明，所提出的算法與Hough變換相比不僅可以提高計算速度，且能獲得更好的檢測性能.

［1］鄭天茹，王濱海，劉 俍，等.電力巡線無人直升機(jī)障礙規(guī)避系統(tǒng)［J］.山東電力技術(shù)，2012，185(1):14-17.

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

［3］劉 進(jìn)，馬 梁，劉忠訓(xùn)，等.基于隨機(jī)Hough變換的零基線正弦曲線檢測［J］.計算機(jī)工程，2010，36(15):1-4.

［4］劉桂雄，申柏華，馮云慶，等.基于改進(jìn)的 Hough變換圖像分割方法［J］.光學(xué)精密工程，2002，10(3):257-260.

［5］朱院娟，郭斯羽，朱志杰，等.結(jié)合LTS和Hough變換的直線檢測方法［J］.計算機(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］張英濤，黃劍華，唐降龍，等.一種基于精簡粒子群優(yōu)化的霍夫變換算法［J］.天津大學(xué)學(xué)報，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.