基于隨機(jī)采樣的隨機(jī)Hough變換快速圓檢測(cè)算法*

李建森，項(xiàng) 偲

(黃山學(xué)院 信息工程學(xué)院，安徽 黃山245041)

目標(biāo)檢測(cè)是計(jì)算機(jī)視覺(jué)領(lǐng)域中的核心問(wèn)題之一，自提出以來(lái)逐漸成為計(jì)算機(jī)視覺(jué)領(lǐng)域的研究熱點(diǎn)。圓形是構(gòu)成物體的基本形狀之一，具有圓形形狀的物體存在于各種工農(nóng)業(yè)生產(chǎn)中，如工業(yè)制造中的圓形零件檢測(cè)、農(nóng)業(yè)生產(chǎn)中的果實(shí)定位、人臉識(shí)別中的瞳孔檢測(cè)等，對(duì)圓形目標(biāo)進(jìn)行檢測(cè)具有重大現(xiàn)實(shí)意義以及應(yīng)用價(jià)值。

Hough變換是圓形檢測(cè)的常用方法[1-4]，其原理是把圖像中的曲線(xiàn)檢測(cè)問(wèn)題變成參數(shù)空間中的峰值問(wèn)題，對(duì)參數(shù)空間中的點(diǎn)進(jìn)行累加統(tǒng)計(jì)，其中累加最大值的參數(shù)就是所求圓的參數(shù)。Hough變換方法具有可靠性和精度高等優(yōu)點(diǎn)，但其缺點(diǎn)同樣明顯，所需存儲(chǔ)空間要求大，計(jì)算時(shí)間長(zhǎng)，這使Hough變換很難應(yīng)用在實(shí)際檢測(cè)中。為解決Hough變換所需存儲(chǔ)空間大和計(jì)算量大的問(wèn)題，提出了各種改進(jìn)方案，隨機(jī)Hough變換(Randomized Hough Transform，RHT)是針對(duì)Hough變換最常用的一種改進(jìn)算法[5-8]。該算法隨機(jī)選取圖像空間中不在一條直線(xiàn)上的三點(diǎn)，將這三點(diǎn)映射成參數(shù)空間中的一點(diǎn)，從而解決了Hough變換一到多映射產(chǎn)生巨大運(yùn)算量的問(wèn)題。但對(duì)復(fù)雜背景圖像而言，隨機(jī)采樣仍然會(huì)導(dǎo)致大量的無(wú)效采樣以及無(wú)效積累，這會(huì)大大降低計(jì)算效率[9-10]。

為了進(jìn)一步提高圓檢測(cè)速度，本文提出了一種基于隨機(jī)采樣的隨機(jī)Hough變換快速檢測(cè)算法。該算法主要從減少隨機(jī)采樣點(diǎn)和利用圓的幾何特性?xún)煞矫鎭?lái)對(duì)隨機(jī)Hough變換進(jìn)行改進(jìn)。通過(guò)實(shí)驗(yàn)驗(yàn)證，本文算法提高了檢測(cè)效率，在實(shí)際生產(chǎn)中有廣泛的應(yīng)用價(jià)值。

1 隨機(jī)Hough變換

隨機(jī)Hough變換采用隨機(jī)采樣不共線(xiàn)的三個(gè)點(diǎn)的方式，計(jì)算出對(duì)應(yīng)的圓參數(shù)，并且采用多對(duì)一的映射方式，判斷候選圓存在的條件是積累次數(shù)大于閾值，然后通過(guò)證據(jù)積累去驗(yàn)證候選圓的真實(shí)性。

在隨機(jī)采樣過(guò)程中，隨機(jī)選取三個(gè)邊緣點(diǎn)，設(shè)A、B、C這三個(gè)點(diǎn)的坐標(biāo)分別為(x1，y1)，(x2，y2)，(x3，y3)，代入圓方程，由式(1)可得到候選圓的參數(shù)(a，b，r)。

其中i=1，2，3。對(duì)此圓構(gòu)成的點(diǎn)進(jìn)行統(tǒng)計(jì)，當(dāng)統(tǒng)計(jì)后的總數(shù)達(dá)到一定數(shù)量后，即認(rèn)為此候選圓為真圓，否則為假圓。

2 改進(jìn)算法

在原有隨機(jī)Hough變換基礎(chǔ)上，主要從減少隨機(jī)采樣點(diǎn)和利用圓幾何特性來(lái)對(duì)隨機(jī)Hough變換進(jìn)行改進(jìn)。

2.1 通過(guò)隨機(jī)采樣兩點(diǎn)和圓幾何特性求取圓心坐標(biāo)和半徑

傳統(tǒng)RHT算法檢測(cè)圓時(shí)是通過(guò)隨機(jī)采樣三個(gè)點(diǎn)來(lái)確定候選圓的，而這三點(diǎn)位于同一個(gè)圓上的概率為

N表示某圖像有N個(gè)圓，q表示每個(gè)圓上有q個(gè)點(diǎn)，m表示還有m個(gè)非圓上點(diǎn)。

當(dāng)隨機(jī)采樣的點(diǎn)數(shù)越少時(shí)，可知位于同一圓上的概率越高，因此減少隨機(jī)采樣的點(diǎn)數(shù)可以更容易找到圓，即可通過(guò)降低隨機(jī)采樣的點(diǎn)數(shù)來(lái)減小無(wú)效采樣率。

在邊緣圖像上隨機(jī)采樣兩點(diǎn)(x1，y1)和(x2，y2)，假設(shè)這兩點(diǎn)均在候選圓上，根據(jù)圓的幾何特性可知，在這兩點(diǎn)形成的線(xiàn)段的垂直線(xiàn)上一定有圓上的第三點(diǎn)(x3，y3)，如圖1所示。

圖1 確定侯選圓

由這三點(diǎn)確定候選圓參數(shù)(a，b，r)，(a，b)是候選圓的圓心，r是半徑。

2.2 通過(guò)統(tǒng)計(jì)候選圓上的點(diǎn)數(shù)判斷是否真圓

傳統(tǒng)方法為統(tǒng)計(jì)候選圓上點(diǎn)的數(shù)量。對(duì)于圖像中的邊緣點(diǎn)，求它們到圓心的距離d，如果d近似等于半徑r，即|d－r|＜ε(ε為實(shí)際計(jì)算時(shí)留的一些小余量)，則認(rèn)為該邊緣點(diǎn)在圓上。由于圖像中所有的邊緣點(diǎn)都要計(jì)算其到圓心的距離，大大降低了檢測(cè)速度，故本文對(duì)其進(jìn)行了改進(jìn)[11]。

由圖2可知，候選圓上的點(diǎn)僅可能位于該候選圓的外切正方形與內(nèi)接正方形之間的區(qū)域中(圖2中的陰影部分)，不在該區(qū)域內(nèi)的點(diǎn)肯定不在候選圓上，不再計(jì)算它們到圓心的距離，而通過(guò)減少計(jì)算邊緣點(diǎn)到圓心距離的次數(shù)的方式減少計(jì)算量，從而大幅縮減驗(yàn)證耗時(shí)。

圖2 候選圓上的點(diǎn)所在位置(陰影部分)

候選圓的圓心坐標(biāo)為(a，b)，半徑為r，如果邊緣點(diǎn)的坐標(biāo)(x，y)滿(mǎn)足式(3)則認(rèn)為點(diǎn)(x，y)為候選圓上的點(diǎn)。

令真實(shí)圓的閾值Mmin=λ×2πr(其中λ為比例系數(shù)，r為候選圓半徑)。在驗(yàn)證點(diǎn)到圓心的距離時(shí)，若尚未驗(yàn)證的點(diǎn)數(shù)為t，當(dāng)前有效計(jì)數(shù)為M1，那么只要出現(xiàn)t+M1＜Mmin，便可確定當(dāng)前候選圓為假圓，不需再對(duì)剩余點(diǎn)集進(jìn)行計(jì)算；若當(dāng)前已經(jīng)有M1＞Mmin，則可確定當(dāng)前候選圓為真實(shí)圓，也不需再對(duì)剩余點(diǎn)集進(jìn)行計(jì)算。這樣也減少了很多的距離計(jì)算，節(jié)省了時(shí)間。

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

為了測(cè)試本文算法的性能，分別對(duì)合成圖像和實(shí)際圖像進(jìn)行了大量實(shí)驗(yàn)。

首先對(duì)圖像進(jìn)行預(yù)處理，消除圖像中的噪聲以及增強(qiáng)圖像的邊緣。然后對(duì)預(yù)處理后的圖像進(jìn)行邊緣檢測(cè)。本文采用的邊緣檢測(cè)算子為Canny算子，因?yàn)榕c其他邊緣檢測(cè)算子相比，Canny邊緣檢測(cè)算子具有高的檢測(cè)率和定位精度。最后用隨機(jī)Hough變換算法和本文算法對(duì)邊緣圖像進(jìn)行圓檢測(cè)，再分析數(shù)據(jù)對(duì)比結(jié)果。

實(shí)驗(yàn)共分為3組。圖3為原圖像，圖4為原圖像經(jīng)過(guò)預(yù)處理后得到的邊緣圖像，圖5為邊緣圖像經(jīng)過(guò)本文算法處理后的結(jié)果圖。

圖3 原圖像

圖4 邊緣圖像

圖5 本文算法結(jié)果

從圖5中可以看出，場(chǎng)景1和場(chǎng)景2中的圓形目標(biāo)均能較好地檢測(cè)出來(lái)，但對(duì)于場(chǎng)景3這類(lèi)圓形目標(biāo)重疊或殘缺的場(chǎng)景，均存在一定的漏檢和錯(cuò)檢，這也是以后我們將要繼續(xù)研究的方向。

由于算法采樣的隨機(jī)性，每一次運(yùn)行的時(shí)間均不一樣。為準(zhǔn)確對(duì)比算法效率，故對(duì)測(cè)試圖像做50次運(yùn)算，取其平均值作為算法運(yùn)行時(shí)間。

表1是對(duì)圖3中的三個(gè)場(chǎng)景，用隨機(jī)Hough變換算法和本文算法檢測(cè)圖像所耗費(fèi)的時(shí)間對(duì)比結(jié)果。由實(shí)驗(yàn)結(jié)果可知，本文算法耗費(fèi)時(shí)間明顯比隨機(jī)Hough變換算法耗費(fèi)時(shí)間少，即本文算法在檢測(cè)速度上有顯著提高。

表1 兩種算法所耗費(fèi)的時(shí)間

4 結(jié)束語(yǔ)

本文提出了一種基于隨機(jī)采樣的隨機(jī)Hough變換圓形快速檢測(cè)算法，從減少隨機(jī)采樣點(diǎn)和利用圓幾何特性來(lái)對(duì)隨機(jī)Hough變換進(jìn)行改進(jìn)，在檢測(cè)速度上有顯著性提高。但現(xiàn)實(shí)中的場(chǎng)景通常都是復(fù)雜的，存在如圖像質(zhì)量一般、光照不均勻、殘缺等問(wèn)題，這使得圓形目標(biāo)在實(shí)際生產(chǎn)檢測(cè)中具有較大的難度，因此對(duì)復(fù)雜背景下的圓形檢測(cè)問(wèn)題有必要進(jìn)一步研究，并根據(jù)實(shí)際應(yīng)用做出相應(yīng)的改進(jìn)。