基于隨機采樣的隨機Hough變換快速圓檢測算法*

李建森，項 偲

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

目標檢測是計算機視覺領域中的核心問題之一，自提出以來逐漸成為計算機視覺領域的研究熱點。圓形是構成物體的基本形狀之一，具有圓形形狀的物體存在于各種工農業生產中，如工業制造中的圓形零件檢測、農業生產中的果實定位、人臉識別中的瞳孔檢測等，對圓形目標進行檢測具有重大現實意義以及應用價值。

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

為了進一步提高圓檢測速度，本文提出了一種基于隨機采樣的隨機Hough變換快速檢測算法。該算法主要從減少隨機采樣點和利用圓的幾何特性兩方面來對隨機Hough變換進行改進。通過實驗驗證，本文算法提高了檢測效率，在實際生產中有廣泛的應用價值。

1 隨機Hough變換

隨機Hough變換采用隨機采樣不共線的三個點的方式，計算出對應的圓參數，并且采用多對一的映射方式，判斷候選圓存在的條件是積累次數大于閾值，然后通過證據積累去驗證候選圓的真實性。

在隨機采樣過程中，隨機選取三個邊緣點，設A、B、C這三個點的坐標分別為(x1，y1)，(x2，y2)，(x3，y3)，代入圓方程，由式(1)可得到候選圓的參數(a，b，r)。

其中i=1，2，3。對此圓構成的點進行統計，當統計后的總數達到一定數量后，即認為此候選圓為真圓，否則為假圓。

2 改進算法

在原有隨機Hough變換基礎上，主要從減少隨機采樣點和利用圓幾何特性來對隨機Hough變換進行改進。

2.1 通過隨機采樣兩點和圓幾何特性求取圓心坐標和半徑

傳統RHT算法檢測圓時是通過隨機采樣三個點來確定候選圓的，而這三點位于同一個圓上的概率為

N表示某圖像有N個圓，q表示每個圓上有q個點，m表示還有m個非圓上點。

當隨機采樣的點數越少時，可知位于同一圓上的概率越高，因此減少隨機采樣的點數可以更容易找到圓，即可通過降低隨機采樣的點數來減小無效采樣率。

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

圖1 確定侯選圓

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

2.2 通過統計候選圓上的點數判斷是否真圓

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

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

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

候選圓的圓心坐標為(a，b)，半徑為r，如果邊緣點的坐標(x，y)滿足式(3)則認為點(x，y)為候選圓上的點。

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

3 實驗與結果

為了測試本文算法的性能，分別對合成圖像和實際圖像進行了大量實驗。

首先對圖像進行預處理，消除圖像中的噪聲以及增強圖像的邊緣。然后對預處理后的圖像進行邊緣檢測。本文采用的邊緣檢測算子為Canny算子，因為與其他邊緣檢測算子相比，Canny邊緣檢測算子具有高的檢測率和定位精度。最后用隨機Hough變換算法和本文算法對邊緣圖像進行圓檢測，再分析數據對比結果。

實驗共分為3組。圖3為原圖像，圖4為原圖像經過預處理后得到的邊緣圖像，圖5為邊緣圖像經過本文算法處理后的結果圖。

圖3 原圖像

圖4 邊緣圖像

圖5 本文算法結果

從圖5中可以看出，場景1和場景2中的圓形目標均能較好地檢測出來，但對于場景3這類圓形目標重疊或殘缺的場景，均存在一定的漏檢和錯檢，這也是以后我們將要繼續研究的方向。

由于算法采樣的隨機性，每一次運行的時間均不一樣。為準確對比算法效率，故對測試圖像做50次運算，取其平均值作為算法運行時間。

表1是對圖3中的三個場景，用隨機Hough變換算法和本文算法檢測圖像所耗費的時間對比結果。由實驗結果可知，本文算法耗費時間明顯比隨機Hough變換算法耗費時間少，即本文算法在檢測速度上有顯著提高。

表1 兩種算法所耗費的時間

4 結束語

本文提出了一種基于隨機采樣的隨機Hough變換圓形快速檢測算法，從減少隨機采樣點和利用圓幾何特性來對隨機Hough變換進行改進，在檢測速度上有顯著性提高。但現實中的場景通常都是復雜的，存在如圖像質量一般、光照不均勻、殘缺等問題，這使得圓形目標在實際生產檢測中具有較大的難度，因此對復雜背景下的圓形檢測問題有必要進一步研究，并根據實際應用做出相應的改進。