張英濤，黃劍華，唐降龍，劉家鋒

(哈爾濱工業(yè)大學計算機科學與技術學院，哈爾濱 150001)

一種基于精簡粒子群優(yōu)化的霍夫變換算法

張英濤，黃劍華，唐降龍，劉家鋒

(哈爾濱工業(yè)大學計算機科學與技術學院，哈爾濱 150001)

為了提高現有霍夫變換算法的準確率及計算效率，提出了一種基于精簡粒子群優(yōu)化的霍夫變換算法．該方法將霍夫變換后解的參數作為粒子位置，將霍夫變換的累加數組值作為粒子的適應度值，每一次迭代更新粒子的位置和速度，并將所得粒子群的適應度值按降序排列，保留“強壯”粒子，組成精簡粒子群．實驗結果表明，基于精簡粒子群優(yōu)化的霍夫變換算法不僅可以提高霍夫變換的計算速度，而且可以獲得較高的計算準確率，特別是對于復雜背景圖像和高噪聲圖像也同樣適用．

霍夫變換；精簡粒子群優(yōu)化；圖像處理；曲線檢測

霍夫變換算法是檢測圖像中特定形狀的基本方法[1-2]，由于其對隨機噪聲不敏感，對不完整邊緣具有魯棒性，而且適用于并行處理，因此被廣泛應用于計算機視覺和模式識別等領域[3-4]．標準霍夫變換(standard Hough transform，SHT)可用于直線、圓以及橢圓檢測；廣義霍夫變換(generalized Hough transform，GHT)可用于檢測任意形狀．從1962年霍夫變換方法首次被提出至今，該方法經歷了不斷的改進和發(fā)展，如分層霍夫變換(Hierarehieal HT，HHT)[5]、概率霍夫變換(probabilistic HT，PHT)[6]、自適應霍夫變換(adaptive HT，AHT)[7]、模糊霍夫變換(fuzzy HT，FHT)[8]和擴展霍夫變換(extended HT，EHT)[9]．

然而霍夫變換計算量大、耗時，很難達到實時處理要求[10]，因此許多學者致力于研究檢測準確率高且快速的霍夫變換方法．Galambos等[11]使用梯度信息減小計算量，以加速算法．Matas等[12]提出一種改進的概率霍夫變換，采用隨機取點映射、映射和直線檢測交替進行，運算過程可在所有待處理點完成向參數空間的映射或被歸類到某一直線上后停止．這時，只有小部分待處理點完成映射，其余點即作為被檢測到的直線上的點，從待處理點集中去除，而不必進行向參數空間的映射，減少了運算開銷．Duquenoy等[13]提出一種偽線性方法，應用欠采樣技術及預先最大檢測技術來加速計算．文獻[14]提出一種嚴格的隨機霍夫變換方法，用小的隨機樣本集取代全部樣本集進行預處理，減少錯誤選擇點．

筆者提出一種精簡粒子群優(yōu)化(reduced particle swarm optimization，RPSO)算法，并與霍夫變換相結合，將霍夫變換后解的參數作為粒子位置，用霍夫變換的累加數組值作為粒子的適應度值，迭代更新粒子的位置和速度，把所得粒子群的適應度值按降序排列，保留“強壯”粒子，組成精簡粒子群．在實驗部分分別給出了基于精簡粒子群優(yōu)化的霍夫變換算法對各種不同類型噪聲的模擬圖像及實際圖像檢測直線、圓及橢圓的結果．實驗結果表明，所提算法不僅可提高霍夫變換的計算速度，而且可以獲得較高的計算準確率，特別是對于復雜背景圖像和高噪聲圖像，可以獲得較好的性能．

1 精簡粒子群優(yōu)化算法

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

粒子群優(yōu)化算法(particle swarm optimization，PSO)是一種基于群體的演化算法，它利用自然選擇和遺傳學的思想，通過模擬生物群落系統(tǒng)的進化機制來完成加速和改善隨機搜索的算法．最早的PSO算法模擬一些簡單的社會群落生物，如鳥群、魚群等模型，由Kennedy等[15]于1995年提出．

PSO算法可描述如下：

在n維解空間，粒子可表示為xi＝(xi1，xi2，…，xin)，即粒子在搜尋空間中的位置，是問題的一個解，粒子速度可表示為vi＝(vi1，vi2，…，vin)，則粒子尋優(yōu)公式可表示為

式中：Pinbest、Pngbest分別為粒子群的個體最優(yōu)位置和群體最優(yōu)位置的n維向量；rand1、rand2是兩個0～1間的隨機數；c1、c2為加速度系數；w為慣性因子；k為優(yōu)化迭代次數．

1.2 精簡粒子群優(yōu)化算法

精簡粒子群優(yōu)化(RPSO)算法是一種改進型的粒子群優(yōu)化(PSO)算法．其基本思想是：在PSO算法中，M個粒子被初始化．在每次迭代中，粒子的速度和位置都相應更新，計算該位置的適應度，并根據適應度把群中粒子按降序排列，每次選擇排在前面的粒子(精簡比例為r)作為精簡粒子群，其余粒子被淘汰．該過程進行迭代，直到達到最大迭代次數或者錯誤率小于預先設定的最小閾值．這種改進能夠有效降低傳統(tǒng)PSO算法的計算時間，且提高解的精度．

精簡粒子群優(yōu)化的具體過程描述如下：

(1) 選擇1個具有M個粒子的種群，命名為初始種群S(1)＝{P1，P2，…，PM}，初始化每個粒子的位置xin；

(2) 隨機初始化每個粒子的飛行速度vin；

(3) 計算每個粒子的適應度f(xin(k))；

(4) 在1k+次迭代中，比較每一個粒子的最佳位置適應度和當前位置適應度，根據適應度更新每個粒子的位置Pin(k+1)，即

(5) 選擇當前全局最佳適應度的位置為k+1次全局最佳位置Pngbest(k+1)；

(6) 根據適應度對群中粒子降序排序，選擇排在前面的粒子(精簡比例為r)來形成精簡的下一代粒子群S(k+1)；

(7) 更新k+1代中每個粒子的速度vin(k+1)；

(8) 更新k+1代種群S(k+1)中每個粒子的位置；

返回第(3)步，重復以上過程直到迭代結束．

慣性因子w用于調整算法全局和局部搜索能力的平衡．w值較大，有利于跳出局部極小點，從而找到全局最優(yōu)解；w值較小，則有利于算法收斂．因此，為進一步優(yōu)化算法，采用一種自適應調整w值的策略．令w=1.5Mk/kM,其中Mk為第k次迭代時粒子群的數量．這使得算法在前期有較高的探索能力，而在后期有較高的開發(fā)能力以加快收斂速度．加速度系數c1、c2設為常數2．

2 基于精簡粒子群優(yōu)化的霍夫變換算法

將RPSO算法與霍夫變換相結合，提出了基于精簡粒子群優(yōu)化的霍夫變換算法．把霍夫變換后的解參數當作粒子的位置，使用RPSO算法尋找最優(yōu)解，將霍夫變換的累加數組值作為適應度值．“精簡粒子群”的選擇有助于提高運算速度，找到精確的最優(yōu)解．

式(4)為極坐標中表示一條直線的參數方程．

圖像空間中的點(,)x y經霍夫變換映射到參數空間中的一條正弦曲線，圖像空間中共直線的點映射到參數空間中的正弦曲線的交點就對應原直線的2個參數ρ和θ．下面以采用極坐標的直線檢測為例，說明基于精簡粒子群優(yōu)化的霍夫變換算法的具體過程．

(1) 選擇一個具有M個粒子的種群，命名為初始種群S(1)＝{P1，P2，…，PM}，為霍夫變換參數ρ和θ賦初值0ρ、0θ，并將2 維累加數組A初始化為零；

(2) 對一原始圖像I進行邊緣提取，求得邊緣點集E；

(3) 在邊緣點集E中隨機選取兩個點1pt、2pt，使用這兩個點計算直線的參數，并使用所得參數值初始化該粒子在粒子群中的位置xin；

(4) 重復步驟(3)直至粒子群中所有粒子值初始化完畢；

(5) 隨機初始化每個粒子在粒子群中的速度vin；

(6) 計算每個粒子的適應度值f(xin(k,ρk,θk))，即

(7) 在k+1次迭代中，使用式(3)比較每一個粒子的最佳位置適應度和當前位置適應度，根據適應度更新每個粒子的位置Pin(k+1)；

(8) 選擇當前全局最佳適應度的位置為k+1次全局最佳位置Pngbest(k+1)；

(9) 根據適應度對群中粒子降序排序．選擇排在前面的粒子(精簡比例為r)來形成精簡的下一代粒子群S(k+1)；

(10) 根據式(4)更新k+1代中每個粒子的速度vin(k+1)；

(11) 更新k+1代種群S(k+1)中每個粒子的位置；

(12) 返回第(6)步，重復以上過程直到迭代結束．

3 實驗結果

實驗采用Matlab7.1，在一臺3.2,GHz、2,G內存的Pentium 4 PC機上運行．初始化粒子數M為100，精簡比例r為90%．

為驗證所提出算法的有效性，本節(jié)給出了模擬圖像及實際圖像檢測的結果．圖1為512 512×的模擬圖像，其中包含2個直徑分別為50像素、80像素的圓；1個長軸半徑和短軸分別為160像素、120像素的橢圓；1個420 420×像素的正方形．圖2～圖4所示的3組模擬圖像，分別加入不同程度的高斯白噪聲、椒鹽噪聲及斑點噪聲，用來測試本算法在各種噪聲條件下的性能．圖4所用的斑點噪聲模型在文獻[16]中有詳細描述．圖5為本算法對實際圖像的檢測結果．

圖1 模擬圖像Fig.1 Synthetic image

圖2 含有不同等級高斯噪聲的檢測圖像(噪聲均值為0)Fig.2 Images for line detection with Gaussian noise，whose mean m＝0 and standard deviations σ having different values

圖3 含有不同等級椒鹽噪聲的檢測圖像Fig.3 Images for circle detection having salt and pepper noise with different level values

圖4 具有不同等級斑點噪聲檢測圖像Fig.4 Images for ellipse detection having speckle noise with different level values

表1 本文所提出算法和RHT算法對圖2處理結果的比較Tab.1 Comparisons of processing the images in Fig.2 between the proposed approach and RHT

表2 本文所提出算法和RHT算法對圖3處理結果的比較Tab.2 Comparisons of processing the images in Fig.3 between the proposed approach and RHT

為比較算法對不同目標的檢測準確率，定義檢測誤差為

式中：lE、cE、eE分別為檢測直線、圓、橢圓誤差，即定義誤差為所有檢測參數與實際參數差的絕對值累加和；ρd、θd、xd、yd、Rd、bd為檢測值；ρt、θt、xt、yt、Rt、bt為實際值．表1～表3分別為圖2～圖4的檢測結果，用以作為本文提出算法與Regularized HT[1]及限制隨機霍夫變換算法(RRHT)[14]的性能比較．由表1～表3的結果對比可知，本算法具有較高效率，比其他算法快得多(＞45%)，并且可以獲得較精確的檢測結果；特別是在噪聲級別較高的圖像中，檢測準確率優(yōu)于Regularized HT及RRHT算法．

圖5為本算法對實際圖像中直線和圓的檢測結果，圖5(c)中背景模糊且有多個目標重疊，本算法將其中的8個圓全部準確地檢測出來．

表3 本文所提出算法和RHT算法對圖4處理結果的比較Tab.3 Comparisons of processing the images in Fig.4 between the proposed approach and RHT

圖5 本方法對實際圖像中直線和圓的檢測結果Fig.5 Results on the real images for line and circle detection

4 結 語

本文首先介紹精簡粒子群優(yōu)化(RPSO)算法，并將其與霍夫變換相結合，提出了基于精簡粒子群優(yōu)化的霍夫變換算法，最后以檢測直線為例給出霍夫變換具體過程．

本方法從優(yōu)化的角度對霍夫變換進行了改進，提高了霍夫變換的檢測準確率，并節(jié)省了計算時間．大量實驗表明，本方法在高噪聲和復雜背景下均可獲得較好的性能．本文的方法對于圖像特定形狀的目標檢測具有較為廣泛而重要的實用價值．

［1］ Aggarwal N，Karl W C. Line detection in images through regularized Hough transform[J]. IEEE Transactions on Image Processing，2006，15(3)：582-591.

［2］ Hahn K，Jung S，Han Y，et al. A new algorithm for ellipsedetection by curve segments[J]. Pattern Recognition Letter，2008，29(13)：1836-1841.

［3］ Bonci A，Leo T，Longhi S. A bayesian approach to the Hough transform for line detection[J]. IEEE Transactions on Systems，Man，and Cybernetics，2005，35(6)：945-955.

［4］ Leemans V，Destain M F. Application of the Hough transform for seed row localisation using machine vision[J]. Biosystems Engineering，2006，94(3)：325-336.

［5］ Guerra C，Hambrush S. Parallel algorithm for line detection on a mesh[J]. J Parallel Distributed Computing，1989，6：l-19.

［6］ Kiryati N，Eldar Y，Bruckstein A M. A probabilistic Hough transform[J]. Pattern Recognition，1991，24(4)：303-316.

［7］ Atiquzzaman M. Multiresolution Hough transform：An efficient method of detecting patterns in images[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，1992，14(11)：1090-1095.

［8］ Han J H，Koczy L T，Poston T. Fuzzy Hough transform [J]. Pattern Recognition Letters，1994，15(7)：649-658.

［9］ Cha J，Cofer R H，Kozaitis S P. Extended Hough transform for linear feature detection[J]. Pattern Recognition，2006，39(6)：1034-1043.

［10］ Xu L. A unified perspective and new results on RHT computing，mixture based learning，and multi-learner based problem solving[J]. Pattern Recognition，2007，40 (8)：2129-2153.

［11］ Galambos C，Kittler J，Matas J. Using gradient information to enhance the progressive probabilistic Hough transform[C]// Proceedings of the International Conference on Pattern Recognition. Barcelona，Spain，2000：560-563.

［12］ Matas J，Galambos C，Kittler J. Progressive probabilistic Hough transform[C]// Proceedings of British Machine Vision Conference. Southampton，UK，1998：256-265.

［13］ Duquenoy E，Taleb-Ahmed A. Applying the Hough transform pseudo-linearity property to improve computing speed[J]. Pattern Recognition Letters，2006，27(16)：1893-1904.

［14］ Cheng Z，Liu Y. Efficient technique for ellipse detection using restricted randomized Hough transform[C]// Proceedings of International Conference on Information Technology. Las Vegas，USA，2004：714-718.

［15］ Kennedy J，Eberhart R C. Particle swarm optimization [C]// Proceedings of IEEE International Conference on Neural Networks. Perth，Australia，1995：1942-1948.

［16］ Yue Y，Croitoru M M，Bidani A，et al. Nonlinear multiscale wavelet diffusion for speckle suppression and edge enhancement in ultrasound images[J]. IEEE Transactions on Medical Imagings，2006，25(3)：297-311.

A Hough Transform Algorithm Based on Reduced Particle Swarm Optimization

ZHANG Ying-tao，HUANG Jian-hua，TANG Xiang-long，LIU Jia-feng
(School of Computer Science and Technology，Harbin Institute of Technology，Harbin 150001，China)

To improve the accuracy and efficiency of existing Hough transform algorithms，a novel Hough transformation algorithm based on reduced particle swarm optimization(RPSO) is presented. The parameters of the solution after Hough transformation are employed as particle positions，and an accumulation array in Hough transformation is utilized as a fitness function of RPSO algorithm. Velocities and positions are updated accordingly，and position fitness values are calculated and sorted in a list with the descending order. “Stronger” particles whose fitness values are in the higher positions of the list are selected and the reduced particle swarm is then obtained. The experimental results show that the proposed approach can detect curves more accurately with less computational time，especially for images with complex background or with high level noise.

Hough transform；reduced particle swarm optimization；image processing；curve detection

TP391.4

A

0493-2137(2011)02-0162-06

2009-09-28；

2009-12-24.

國家自然科學基金資助項目(60873142，30670546)；黑龍江省青年基金資助項目(QC08C20)；哈爾濱工業(yè)大學創(chuàng)新基金資助項目(HIT.NSRIF.2008.48).

張英濤（1975— ），女，博士，講師.

張英濤，yingtao@hit.edu.cn.