粒子群圓檢測算法

李福慶+蘇湛

摘要：

針對基于霍夫變換類圓檢測算法計算量大、耗時長等問題，提出了一種基于粒子群算法的圓檢測算法。該算法通過對圖像進行灰度化、濾波去噪與邊緣檢測等預處理獲取邊緣圖像后，再從中隨機選取兩點之中點作為初始粒子位置，通過設置最大迭代次數與閾值克服粒子陷入局部最優問題及判斷是否檢測到圓。對比粒子群圓檢測算法與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）。endprint

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.endprint

[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.

（責任編輯：何麗）endprint