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

(哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150001)

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

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

(哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150001)

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

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

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

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

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

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

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

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

PSO算法可描述如下：

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

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

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

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

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

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

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

(3) 計(jì)算每個(gè)粒子的適應(yīng)度f(wàn)(xin(k))；

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

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

(6) 根據(jù)適應(yīng)度對(duì)群中粒子降序排序，選擇排在前面的粒子(精簡(jiǎn)比例為r)來(lái)形成精簡(jiǎn)的下一代粒子群S(k+1)；

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

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

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

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

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

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

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

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

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

(2) 對(duì)一原始圖像I進(jìn)行邊緣提取，求得邊緣點(diǎn)集E；

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

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

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

(6) 計(jì)算每個(gè)粒子的適應(yīng)度值f(xin(k,ρk,θk))，即

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

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

(9) 根據(jù)適應(yīng)度對(duì)群中粒子降序排序．選擇排在前面的粒子(精簡(jiǎn)比例為r)來(lái)形成精簡(jiǎn)的下一代粒子群S(k+1)；

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

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

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

3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)采用Matlab7.1，在一臺(tái)3.2,GHz、2,G內(nèi)存的Pentium 4 PC機(jī)上運(yùn)行．初始化粒子數(shù)M為100，精簡(jiǎn)比例r為90%．

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

圖1 模擬圖像Fig.1 Synthetic image

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

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

圖4 具有不同等級(jí)斑點(diǎn)噪聲檢測(cè)圖像Fig.4 Images for ellipse detection having speckle noise with different level values

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

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

為比較算法對(duì)不同目標(biāo)的檢測(cè)準(zhǔn)確率，定義檢測(cè)誤差為

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

圖5為本算法對(duì)實(shí)際圖像中直線和圓的檢測(cè)結(jié)果，圖5(c)中背景模糊且有多個(gè)目標(biāo)重疊，本算法將其中的8個(gè)圓全部準(zhǔn)確地檢測(cè)出來(lái)．

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

圖5 本方法對(duì)實(shí)際圖像中直線和圓的檢測(cè)結(jié)果Fig.5 Results on the real images for line and circle detection

4 結(jié) 語(yǔ)

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

本方法從優(yōu)化的角度對(duì)霍夫變換進(jìn)行了改進(jìn)，提高了霍夫變換的檢測(cè)準(zhǔn)確率，并節(jié)省了計(jì)算時(shí)間．大量實(shí)驗(yàn)表明，本方法在高噪聲和復(fù)雜背景下均可獲得較好的性能．本文的方法對(duì)于圖像特定形狀的目標(biāo)檢測(cè)具有較為廣泛而重要的實(shí)用價(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.

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

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

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