基于隨機(jī)Hough變換的圓形目標(biāo)檢測(cè)實(shí)驗(yàn)

張 佳， 程宇龍

(北京理工大學(xué) 自動(dòng)化學(xué)院，北京 100081)

0 引 言

實(shí)驗(yàn)教學(xué)是高等院校教育教學(xué)過程的重要組成部分，也是創(chuàng)新教育最為重要的基礎(chǔ)[1]。目前，高校實(shí)驗(yàn)教學(xué)的一個(gè)重要發(fā)展方向就是開設(shè)綜合性設(shè)計(jì)實(shí)驗(yàn)，以培養(yǎng)學(xué)生分析問題的能力[2]。

1 REVS-50M小型光電跟蹤系統(tǒng)

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

本實(shí)驗(yàn)系統(tǒng)的圖像處理和控制部分從整體上看由計(jì)算機(jī)、電控箱以及伺服轉(zhuǎn)臺(tái)組成。計(jì)算機(jī)主要負(fù)責(zé)系統(tǒng)軟件部分的代碼編寫工作與系統(tǒng)的控制操作。計(jì)算機(jī)通過PCI總線連接至運(yùn)動(dòng)控制器、圖像采集卡與多串口卡，并通過數(shù)據(jù)線與電機(jī)驅(qū)動(dòng)器、相機(jī)和激光測(cè)距儀，從而分別實(shí)現(xiàn)電機(jī)驅(qū)動(dòng)器的控制、圖像采集與顯示以及距離和跟蹤信息的獲取與反饋。其具體控制結(jié)構(gòu)圖如圖1所示。

圖1 光電跟蹤系統(tǒng)組成

圖2所示的手動(dòng)靶標(biāo)，是一個(gè)三軸運(yùn)動(dòng)平臺(tái)，用于模擬目標(biāo)的位置及速度的變化。

圖2 手動(dòng)靶標(biāo)

2 常規(guī)Hough變換圓檢測(cè)

Hough變換利用目標(biāo)的形狀特征而非顏色特征來進(jìn)行檢測(cè)，可以避免由于顏色相近所引起的誤跟蹤。

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

由此可見，采用常規(guī)Hough變換能夠檢測(cè)到圓形手動(dòng)靶標(biāo)，但常規(guī)Hough變換的圖像空間到參數(shù)空間的映射是一到多的映射，計(jì)算量大，需要占用大量?jī)?nèi)存空間，并且受到參數(shù)空間離散化的嚴(yán)重影響，精確度不高。另外這種方法對(duì)所有特征點(diǎn)進(jìn)行平等投票，無法排除噪聲點(diǎn)的干擾，如背景更復(fù)雜就不能達(dá)到很好的效果。

(a)

(b)(c)

圖3 常規(guī)Hough變換圓檢測(cè)結(jié)果

3 隨機(jī)Hough變換圓檢測(cè)

為了克服常規(guī)Hough變換檢測(cè)時(shí)的缺陷，實(shí)驗(yàn)決定改用隨機(jī)Hough變換[12、13]。隨機(jī)Hough變換隨機(jī)選取邊緣點(diǎn)不集中在同一條直線上的3個(gè)點(diǎn)，計(jì)算出對(duì)應(yīng)的圓的參數(shù)并將其映射到參數(shù)空間一個(gè)點(diǎn)，將原來的一到多的映射變?yōu)槎嗟揭坏挠成?，省去了許多計(jì)算量。同時(shí)，隨機(jī)Hough變換采用了動(dòng)態(tài)鏈表結(jié)構(gòu)，只對(duì)有效參數(shù)單元進(jìn)行累計(jì)，大大減輕了內(nèi)存的負(fù)擔(dān)，節(jié)省大量?jī)?nèi)存空間。具體算法步驟如下[14]：

(1) 構(gòu)造邊緣點(diǎn)集D，初始化參數(shù)單元集P=NULL。

(2) 從D中隨機(jī)選取3個(gè)點(diǎn)。

(3) 計(jì)算這3點(diǎn)所確定的圓參數(shù)p，若有解轉(zhuǎn)(4)，否則轉(zhuǎn)(7)。

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

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

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

(7)pc為候選圓的參數(shù)，若該參數(shù)對(duì)應(yīng)的圓上的點(diǎn)數(shù)Value>minValue，則轉(zhuǎn)(8)，否則為虛假圓，從P中去除pc然后轉(zhuǎn)(2)。

(8) 檢測(cè)到參數(shù)為pc的真實(shí)圓，提取圓心和邊緣點(diǎn)，結(jié)束。

其中需要說明以下幾點(diǎn)：

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

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

(1)

(2)

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

(3)

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

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

(4)

由于隨機(jī)采樣會(huì)取到大量無效的點(diǎn)，這些點(diǎn)經(jīng)過計(jì)算得到的圓一定是虛假圓，卻仍然將其插入?yún)?shù)空間鏈表，會(huì)造成大量的無效累積，增加了搜索時(shí)的難度和計(jì)算時(shí)間，嚴(yán)重時(shí)還會(huì)給真圓的定位帶來困難。圓的個(gè)數(shù)越多，隨機(jī)采樣的3點(diǎn)落在同一圓上的概率就越小，導(dǎo)致無效累積增多。

4 隨機(jī)Hough變換的改進(jìn)

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

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

設(shè)當(dāng)前像素點(diǎn)為A5(x0,y0)，圖4給出了該點(diǎn)與其周圍8鄰域像素點(diǎn)的位置關(guān)系。

圖4 當(dāng)前像素A5和周圍像素的位置關(guān)系

設(shè)A5點(diǎn)的梯度在x方向和y方向分別為Gx和Gy，其梯度方向角為θ，下面用Sobel邊緣算子來計(jì)算梯度：

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

(5)

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

(6)

由此得過A5點(diǎn)沿梯度方向的斜率kt：

kt=tanθ=Gy/Gx

(7)

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

y-y0=kt(x-x0)

(8)

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

(9)

則認(rèn)為該三點(diǎn)符合要求，從而繼續(xù)計(jì)算其對(duì)應(yīng)的圓的參數(shù)，在參數(shù)空間中進(jìn)行搜索和累積。式(9)中的σ為考慮到圖像的數(shù)字化誤差而設(shè)置的容許誤差。

4.2 判斷候選圓為真圓時(shí)的改進(jìn)算法

(1) 在驗(yàn)證候選圓上的點(diǎn)的時(shí)候，可以只靠慮位于該圓內(nèi)切正方形和外接正方形之間的區(qū)域，位于此區(qū)域外的其他點(diǎn)可以不予考慮。因?yàn)楹蜻x圓上的點(diǎn)只可能位于這個(gè)區(qū)域內(nèi)。這樣，便可直接排除很多邊緣點(diǎn)，節(jié)省了時(shí)間。

圖5 候選圓的內(nèi)切外接正方形示意圖

如圖5所示，只需驗(yàn)證位于陰影區(qū)域的點(diǎn)，計(jì)算邊界坐標(biāo)時(shí)，考慮到數(shù)字化誤差，應(yīng)留一個(gè)小余量δ。若圓心坐標(biāo)為(a,b)，半徑為r，得到如下方程：

(13)

因此要驗(yàn)證的邊緣點(diǎn)坐標(biāo)(x,y)應(yīng)滿足：

(14)

(2) 若尚未驗(yàn)證的點(diǎn)數(shù)為t，當(dāng)前有效計(jì)數(shù)為Value1，只要出現(xiàn)t+Value1minValue，則可確定當(dāng)前候選圓為真實(shí)圓，也不需再對(duì)剩余點(diǎn)集進(jìn)行計(jì)算。這樣減少了很多距離計(jì)算，節(jié)省了時(shí)間。

5 實(shí)驗(yàn)結(jié)果及分析

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

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

圖6 隨機(jī)Hough變換檢測(cè)圓形的結(jié)果

表1中給出了常規(guī)Hough變換和改進(jìn)的隨機(jī)Hough變換兩種算法的執(zhí)行時(shí)間和圓半徑的檢測(cè)精度對(duì)比。

表1 兩種方法比較

可以看出，改進(jìn)的隨機(jī)Hough變換能夠更精確地檢測(cè)出圓形移動(dòng)靶標(biāo)的位置，并且具有較好快速性。

6 結(jié) 語

本實(shí)驗(yàn)針對(duì)原小型光電跟蹤系統(tǒng)在圖像檢測(cè)部分產(chǎn)生誤跟蹤的問題，設(shè)計(jì)了利用形狀特征檢測(cè)目標(biāo)的實(shí)驗(yàn)。逐步引導(dǎo)學(xué)生采用Hough變換、隨機(jī)Hough變換以及改進(jìn)的隨機(jī)Hough變換的方法對(duì)圓形進(jìn)行檢測(cè)，分析每種方法的優(yōu)點(diǎn)及缺陷，從而引出一種更為合適的解決方法。在實(shí)驗(yàn)過程中，鍛煉了學(xué)生分析問題、解決問題的能力，提高了學(xué)生的創(chuàng)新能力，獲得了良好的教學(xué)效果。

[1] 鄭蓓蓉. 改革實(shí)驗(yàn)教學(xué) 培養(yǎng)創(chuàng)新人才[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ì)算機(jī)專業(yè)綜合性實(shí)驗(yàn)探索與研究[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] 蔣 偉，楊庭庭，劉亞威,等. 數(shù)字圖像處理研究性實(shí)驗(yàn)教學(xué)的改革與實(shí)踐--基于分?jǐn)?shù)階偏微分的圖像邊緣檢測(cè)[J]. 實(shí)驗(yàn)技術(shù)與管理, 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] 孫 潔. “自動(dòng)控制原理”實(shí)驗(yàn)教學(xué)改革的實(shí)踐[J]. 電氣電子教學(xué)學(xué)報(bào), 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] 羅 兵，甘俊英，張建民. 智能控制技術(shù)[M]．北京：清華大學(xué)出版社，2011.

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

[7] 張 培. 復(fù)雜背景下交通標(biāo)志的顏色分割[D]. 武漢理工大學(xué)，2012.

[8] 張 佳，竇麗華，陳 杰. 基于光電跟蹤系統(tǒng)的系列實(shí)驗(yàn)開發(fā)[J]. 實(shí)驗(yàn)室科學(xué), 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變換的圓檢測(cè)方法[J]. 計(jì)算機(jī)工程與設(shè)計(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]. 科技創(chuàng)新導(dǎo)報(bào), 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] 陳燕新，戚飛虎. 基于隨機(jī)Hough變換的快速圓檢測(cè)方法[J]. 上海交通大學(xué)學(xué)報(bào), 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] 岳 健, 項(xiàng)學(xué)智. 一種改進(jìn)的 Hough 圓檢測(cè)算法[J]. 應(yīng)用科技, 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.