基于隨機Hough變換的圓形目標檢測實驗

張 佳， 程宇龍

(北京理工大學 自動化學院，北京 100081)

0 引 言

實驗教學是高等院校教育教學過程的重要組成部分，也是創新教育最為重要的基礎[1]。目前，高校實驗教學的一個重要發展方向就是開設綜合性設計實驗，以培養學生分析問題的能力[2]。

1 REVS-50M小型光電跟蹤系統

REVS-50M小型光電跟蹤系統是一個開放的實驗平臺，其中結合了圖像處理[3]、自動控制[4]以及智能控制[5]相關的各項技術。該實驗系統通過對一個三自由度的黑色圓形移動靶標進行圖像處理，采用自動控制或智能控制的方法實現轉臺對靶標的實時跟蹤。在目標檢測部分，原實驗系統采用的是顏色閾值[6-7]的方法檢測手動靶標，當檢測過程中有相近顏色的人或物體進入圖像檢測區域時會引起誤跟蹤[8]。改用常規的Hough變換檢測靶標形狀的方法能夠達到檢測要求，并能避免誤跟蹤的問題。然而常規Hough變換[9-10]的計算量大、精確度不高，并且無法排除噪聲點的干擾。為了克服這些缺點，本實驗引導學生采用隨機Hough變換及其改進方法進行靶標的檢測，得到了比較滿意的實驗結果。

本實驗系統的圖像處理和控制部分從整體上看由計算機、電控箱以及伺服轉臺組成。計算機主要負責系統軟件部分的代碼編寫工作與系統的控制操作。計算機通過PCI總線連接至運動控制器、圖像采集卡與多串口卡，并通過數據線與電機驅動器、相機和激光測距儀，從而分別實現電機驅動器的控制、圖像采集與顯示以及距離和跟蹤信息的獲取與反饋。其具體控制結構圖如圖1所示。

圖1 光電跟蹤系統組成

圖2所示的手動靶標，是一個三軸運動平臺，用于模擬目標的位置及速度的變化。

圖2 手動靶標

2 常規Hough變換圓檢測

Hough變換利用目標的形狀特征而非顏色特征來進行檢測，可以避免由于顏色相近所引起的誤跟蹤。

計算機所獲取的靶標原始圖像如圖3(a)所示。首先用Canny算子對原始圖像進行圖像分割處理[11]，得到圖3(b)中的邊緣圖像，再對此圖像進行Hough變換得到如圖3(c)中的結果。

由此可見，采用常規Hough變換能夠檢測到圓形手動靶標，但常規Hough變換的圖像空間到參數空間的映射是一到多的映射，計算量大，需要占用大量內存空間，并且受到參數空間離散化的嚴重影響，精確度不高。另外這種方法對所有特征點進行平等投票，無法排除噪聲點的干擾，如背景更復雜就不能達到很好的效果。

(a)

(b)(c)

圖3 常規Hough變換圓檢測結果

3 隨機Hough變換圓檢測

為了克服常規Hough變換檢測時的缺陷，實驗決定改用隨機Hough變換[12、13]。隨機Hough變換隨機選取邊緣點不集中在同一條直線上的3個點，計算出對應的圓的參數并將其映射到參數空間一個點，將原來的一到多的映射變為多到一的映射，省去了許多計算量。同時，隨機Hough變換采用了動態鏈表結構，只對有效參數單元進行累計，大大減輕了內存的負擔，節省大量內存空間。具體算法步驟如下[14]：

(1) 構造邊緣點集D，初始化參數單元集P=NULL。

(2) 從D中隨機選取3個點。

(3) 計算這3點所確定的圓參數p，若有解轉(4)，否則轉(7)。

(4) 從P中找一個pc滿足‖p-pc‖≤δ，δ是容許誤差，若找到了則轉(6)，否則轉(5)。

(5) 將p插入P中，令其值為1，轉(7)。

(6) 將pc的值加1，若小于指定的閾值N0轉2，否則轉(7)。

(7)pc為候選圓的參數，若該參數對應的圓上的點數Value>minValue，則轉(8)，否則為虛假圓，從P中去除pc然后轉(2)。

(8) 檢測到參數為pc的真實圓，提取圓心和邊緣點，結束。

其中需要說明以下幾點：

(a) 閾值N0的確定。在隨機采樣中，如果有2～3次計算出的圓參數相同或者相似，那么很有可能該圓就是要找的圓，又因為后面還會進一步驗證候選圓是否為真圓，因此閾值N0取小一些即可，取大了不僅會增加計算量，也沒有什么意義。一般取N0=3。

(b) 圓參數的求解。圓的任意兩條弦的中垂線相交于圓心，可以利用此性質求解圓參數[]。假設隨機選取到三點坐標為(x1,y1),(x2,y2),(x3,y3)，則可以得到兩條弦的中垂線所在直線方程如下：

(1)

(2)

式(1)與式(2)聯立可得圓心坐標(a,b)，從而由下式可求得半徑r：

(3)

(c) 確認候選圓為真圓的方法。對圖像中的邊緣點，求它們到圓心的距離d，如果d近似等于半徑r，即|d-r|<ε，則認為該邊緣點在圓上。為了避免開平方運算，提高算法執行速度，將|d-r|<ε改寫為下式，其中(xi,yi)為當前邊緣點坐標，(a,b)為圓心坐標：

(r-ε)2<(xi-a)2+(yi-b)2<(r+ε)2

(4)

由于隨機采樣會取到大量無效的點，這些點經過計算得到的圓一定是虛假圓，卻仍然將其插入參數空間鏈表，會造成大量的無效累積，增加了搜索時的難度和計算時間，嚴重時還會給真圓的定位帶來困難。圓的個數越多，隨機采樣的3點落在同一圓上的概率就越小，導致無效累積增多。

4 隨機Hough變換的改進

4.1 利用梯度信息減少無效累積

為了減少隨機Hough變換時的無效累積，可以在計算圓參數之前先利用3個點的梯度信息計算判斷這3點是否位于同一個圓上，如果3點不在同一個圓上，那么則繼續隨機選取3點，直到選到的3點位于同一個圓上才進行累積，這樣便能節省許多計算和搜索鏈表的時間。

設當前像素點為A5(x0,y0)，圖4給出了該點與其周圍8鄰域像素點的位置關系。

圖4 當前像素A5和周圍像素的位置關系

設A5點的梯度在x方向和y方向分別為Gx和Gy，其梯度方向角為θ，下面用Sobel邊緣算子來計算梯度：

Gx=(A3+2A6+A9)-(A1+2A4+A7)

(5)

Gy=(A7+2A8+A9)-(A1+2A2+A3)

(6)

由此得過A5點沿梯度方向的斜率kt：

kt=tanθ=Gy/Gx

(7)

因此得到過A5且沿梯度方向的直線方程為：

y-y0=kt(x-x0)

(8)

設通過隨機采樣得到的3點為A，B，C，則對A，B和C通過上述方法分別計算出其所在沿梯度方向的直線方程LA、LB、LC，并聯立LA，LB得交點坐標為(x,y)。如果該點到LC：y=Kx+B的距離D滿足下式：

(9)

則認為該三點符合要求，從而繼續計算其對應的圓的參數，在參數空間中進行搜索和累積。式(9)中的σ為考慮到圖像的數字化誤差而設置的容許誤差。

4.2 判斷候選圓為真圓時的改進算法

(1) 在驗證候選圓上的點的時候，可以只靠慮位于該圓內切正方形和外接正方形之間的區域，位于此區域外的其他點可以不予考慮。因為候選圓上的點只可能位于這個區域內。這樣，便可直接排除很多邊緣點，節省了時間。

圖5 候選圓的內切外接正方形示意圖

如圖5所示，只需驗證位于陰影區域的點，計算邊界坐標時，考慮到數字化誤差，應留一個小余量δ。若圓心坐標為(a,b)，半徑為r，得到如下方程：

(13)

因此要驗證的邊緣點坐標(x,y)應滿足：

(14)

(2) 若尚未驗證的點數為t，當前有效計數為Value1，只要出現t+Value1minValue，則可確定當前候選圓為真實圓，也不需再對剩余點集進行計算。這樣減少了很多距離計算，節省了時間。

5 實驗結果及分析

圖6中，(a)為原始圖像，用Canny算子進行圖像分割之后得到(b)，之后對其進行改進的隨機Hough變換，得到(c)中的圓形，即完成了對黑色圓形靶標的檢測，從(d)中可以看到白色十字架準確而穩定地定位在圓心位置。

(a)(b)(c)(d)

圖6 隨機Hough變換檢測圓形的結果

表1中給出了常規Hough變換和改進的隨機Hough變換兩種算法的執行時間和圓半徑的檢測精度對比。

表1 兩種方法比較

可以看出，改進的隨機Hough變換能夠更精確地檢測出圓形移動靶標的位置，并且具有較好快速性。

6 結 語

本實驗針對原小型光電跟蹤系統在圖像檢測部分產生誤跟蹤的問題，設計了利用形狀特征檢測目標的實驗。逐步引導學生采用Hough變換、隨機Hough變換以及改進的隨機Hough變換的方法對圓形進行檢測，分析每種方法的優點及缺陷，從而引出一種更為合適的解決方法。在實驗過程中，鍛煉了學生分析問題、解決問題的能力，提高了學生的創新能力，獲得了良好的教學效果。

[1] 鄭蓓蓉. 改革實驗教學 培養創新人才[J]. 中國高教研究，2002(2):87-88.

ZHENG Pei-rong. Reform experimental teaching and cultivate innovative talents[J]. China Higher Education Research, 2002(2):87-88.

[2] 何麗麗. 高校計算機專業綜合性實驗探索與研究[J]. 科技信息, 2011(15):13-13.

HE Li-li. Comprehensive experimental exploration and research of college computer science[J]. Science & Technology Information, 2011(15):13-13.

[3] 蔣 偉，楊庭庭，劉亞威,等. 數字圖像處理研究性實驗教學的改革與實踐--基于分數階偏微分的圖像邊緣檢測[J]. 實驗技術與管理, 2013,30(6): 124-128.

JIANG Wei, YANG Ting-ting, LIU Ya-wei,etal. Reform and practice of research-style experimental teaching by digital image processing: Image edge detection based on fractional-order partial differential[J]. Experimental Technology and Management, 2013, 30(6): 124-128.

[4] 孫 潔. “自動控制原理”實驗教學改革的實踐[J]. 電氣電子教學學報, 2009, 31(6):69-70.

SUN Jie. Experimental teaching reform of automatic control theory[J]. Journal of Electrical & Electronic Education, 2009, 31(6):69-70.

[5] 羅 兵，甘俊英，張建民. 智能控制技術[M]．北京：清華大學出版社，2011.

[6] 李云紅, 屈海濤. 數字圖像處理[M]. 北京：北京大學出版社，2012.

[7] 張 培. 復雜背景下交通標志的顏色分割[D]. 武漢理工大學，2012.

[8] 張 佳，竇麗華，陳 杰. 基于光電跟蹤系統的系列實驗開發[J]. 實驗室科學, 2012(6):40-43.

ZHANG Jia, DOU Li-hua, CHEN Jie. Development of serial experimental courses based on optical tracking system[J]. Laboratory Science, 2012(6):40-43.

[9] Hough PVC. Method and mean s for recognizing complex patterns: United States, 3069654[P]. 1962-12-18.

[10] 朱桂英，張瑞林. 基于Hough變換的圓檢測方法[J]. 計算機工程與設計，2008，29(6):1462-1464.

ZHU Gui-ying, ZHANG Rui-lin. Circle detection using Hough transform[J]. Computer Engineering and Design, 2008，29(6):1462-1464.

[11] 焦玉斌，徐艷蕾，陳喜龍. 圖像分割研究綜述[J]. 科技創新導報, 2009(13):11-11.

JIAO Yu-bin, XU Yan-lei, CHEN Xi-long. Summary of image segmentation[J]. Science and Technology Innovation Herald, 2009(13):11-11.

[12] Xu L, Oja E, Kutanen P. A new curve detection method: randomized Hough transform(RHT)[J]. Pattern recognition letters, 1990, 11(5): 331-338.

[13] 陳燕新，戚飛虎. 基于隨機Hough變換的快速圓檢測方法[J]. 上海交通大學學報, 1998,32(10):17-20.

CHEN Yan-xin, Qi Fei-hu. Fast Circle Detection Using Randomized Hough Transform[J]. Journal of Shanghai Jiaotong University, 1998,32(10):17-20.

[14] Jiang L. Efficient randomized Hough transform for circle detection using novel probability sampling and feature points[J]. Optik-International Journal for Light and Electron Optics, 2012，123(20):1834-1840.

[15] 岳 健, 項學智. 一種改進的 Hough 圓檢測算法[J]. 應用科技, 2006, 33(6): 74-76.

YUE Jian, XIANG Xue-zhi. An improved algorithm of hough circle detection[J]. Applied Science and Technology, 2006, 33(6): 74-76.