基于Hough變換的三次方Bezier曲線檢測算法研究

孫文赟， 韓 斌

（江蘇科技大學電氣與信息工程學院，江蘇 張家港 215600）

經典Hough變換[1]常用于直線（段）、圓（弧）、橢圓和拋物線的檢測，Ballard[2]提出的廣義Hough變換(Generalized Hough Transform，簡稱GHT)可用于檢測任意形狀，隨后出現了大量對GHT的改進，文獻[3-4]使用對偶點方法降低GHT的復雜度，文獻[5]使用模糊推論系統提高GHT的精確度。在應用方面，文獻[6]提出一種改進型廣義 Hough變換并用于茄子果實位姿識別。

Bezier曲線于1962年由Pierre Bezier發現并用于汽車設計，是目前計算機圖形學中相當重要的參數曲線，也應用于工程圖紙和測量曲線的矢量化等領域[7-8]。

在GHT的基礎上，本文針對Bezier曲線的特點，提出了一種使用 Hough變換的三次方Bezier曲線檢測算法。只需給出待檢測三次方Bezier曲線的大致繪制圖案，算法根據所給出的待檢圖形的數字圖像建立曲線模型，然后在復雜圖像中檢測該形狀曲線出現的位置、大小和方向。算法由待檢圖形建模和曲線檢測兩個部分組成。

1 待檢曲線建模

1.1 點陣圖像的矢量化

所需檢測曲線圖像是像素點陣圖，需將其矢量化以便用于檢測，目前已經有一些關于點陣圖矢量化的研究成果[9]，并投入應用領域。這些算法大多使用最小二乘法擬合曲線，其中，文獻[9]提出的算法具有代表性。該算法首先提取模板圖像的骨架并使用八方向鏈碼的方法追蹤曲線，得到規格點序列 {Qi|i= 0,1,2…n-1}。使用最小二乘 法 對{Qi}擬合使Qi=(Xi,Yi)的 均 方 誤 差 最 小 ， 求 出d0,d1,d2,d3。最終三次方Bezier曲線的4個控制點由公式計算得到。

1.2 待檢曲線的規格化

本文將待檢Bezier曲線規格化，以使得其具有平移、縮放和旋轉不變特征。

圖1 二次方Bezier曲線

定義1 將二次方Bezier曲線經過平移、旋轉、縮放，使首尾的兩個控制點為(0,0)和(0,1)，中間控制點(a,b)即反映了原曲線的形狀特征，稱此變換為Bezier曲線的規格化。

二次方 Bezier曲線的規格化及其逆變換的計算方法為

其中：R()、S()、T()為標準旋轉縮放、平移變換

二次方Bezier曲線的形狀特征

三次方的情況類似，使用首末兩個控制點確定變換的形式，第2、第3兩個控制點經變換得到(a,b)、(c,d)表示圓曲線的形狀特征。

2 曲線檢測

2.1 R函數

圖1(b)所示的規格化Bezier曲線，邊緣點到參考點的距離|r|與邊緣點到參考點連線交切線的夾角φ有確定關系

式(6)即R函數。R函數不受平移、縮放、旋轉影響，僅由形狀決定，是曲線特征的另一種表示方式，使用R函數可以方便地確定參考點，且比原本曲線特征參數表示簡便、規范。所以，我們需先將待檢測的圖形轉換成R函數表示。

規格化三次方Bezier曲線對應的R函數的計算方法及其推導過程如下：

三次方Bezier曲線的參數方程為

整理得關于t的三次多項式

整理得關于t的四次方程

此即為式(6)所對應的R函數。

2.2 使用R函數的Hough變換

與所有Hough變換算法類似，本文算法的主要思想是先投票再統計：使用一個三維累加器數組A，對于每個邊緣點嘗試各種s和φ，通過R函數求得參考點可能的位置，對其投票，所有投票結束后統計最大值，最大值所在位置即(x0,y0)、s。投票部分的偽代碼為：

上述偽代碼中：

①處S為曲線大小s的最大值，從規格化曲線的定義可知，曲線的大小為其在圖像中初始點和終止點的距離，所以s≤S≤圖像對角線長度。

②處使用±是無法避免的，這是因為邊緣方向有二義性，可以理解為一對相差π的角度，從而導致推測的參考點不唯一。

③處使用模糊模板進行投票，以克服輸入圖像噪聲干擾和輸入方向不精確的問題[5]。templateN×N(i,j)為寬度為N的正方形模板，理想的模板是二維高斯函數

當s變化時，投票點靠近／遠離邊緣點，投票點的誤差隨之變小／變大，調整窗口的大小，以適應不同情況，窗口的大小可按下式計算

其中，θe是允許的誤差夾角，較小時可取tan(θe)≈θe，常數E為曲線位置可能存在的絕對誤差，表示向上取奇數操作。

④處使用一個關于s的增函數w(s)作為投票權值調節因子，解決當s較小時投票的集中程度大，影響判斷的問題，經多次實驗調整，取w(s)=s0.7625合適。

③、④兩處可先用A[s][x0][y0]++替代，待投票完成后對累加器A中各層進行平滑濾波并調節權值，從而避免大量浮點數累加，降低算法復雜度，且結果不變。

Hough投票的時間、空間復雜度分別為

其中，W、H為長寬，N為邊緣點數量，S為曲線大小s的最大值，Φ為角度分割數量。這也是整個算法的時間、空間復雜度。

Hough變換利用曲線邊緣方向忽視其自身旋轉，降低Hough空間的維數，達到減少存儲空間并降低計算量的目的，但帶來的曲線方向無法直接求出其副作用。

2.3 計算曲線方向

在已知曲線特征、位置和大小的基礎上，使用模糊匹配法求其方向。使用一個一維累加器數組B，對已知(x0,y0)、s的Bezier曲線嘗試不同的旋轉角度，“繪制”空間域上假設曲線，使用一個中心元素最大、外圍元素較小的窗口在假設曲線上滑動，與實際曲線進行模糊比較，并根據吻合程度對當前角度投票，所有投票結束后統計最大值，其位置即θ。

關于θ的投票數是所有在對應假設曲線上的滑動窗口的吻合程度總和，即

窗口模板的取值方法與前文相同。當窗口靠近或遠離參考點(x0,y0)時，調整窗口的大小N，使得所有窗口可以恰好覆蓋實際曲線可能存在的圓形區域，窗口的寬度的取值為

其中，(xwc,ywc)是窗口的中心位置，常數Δθ為角度變化的步長，較小時可取 tan(Δθ)≈ Δθ。

3 實驗結果與分析

本文選用尺寸為800×600的機械制圖掃描圖像進行三次方Bezier曲線檢測算法的實驗，編寫程序對其進行若干步驟的處理，得到了正確結果。

實驗步驟的數據流程圖如圖2所示，首先提取掃描圖像的邊緣并裁剪某個曲線部分，提取曲線特征得到各種參數，根據形狀參數使用此算法在圖中找出曲線的位置、大小和角度。結果表明，算法的誤差在允許的范圍內。

使用GHT方法，建立大小為100的離散R表代替連續的R函數，其它保持不變，得到另一組結果，對比表1中兩種方法，本文改進方法的精確度優于GHT方法。

圖2 實驗步驟的數據流程圖

表1 實驗結果數據

4 結 論

廣義Hough變換[2]中使用到的R表與本文的R函數類似，區別在于：（1）R表使用采樣的方法記錄離散、有限的邊緣點到參考點的關系；（2）R表存儲的是r向量，本文R函數僅返回其模值。和廣義 Hough變換相比，本文算法對特征的描述更加精確，廣義 Hough變換方法可以檢測包括Bezier曲線在內的任意形狀，但當邊緣像素和參考點的距離較遠時，臨近邊緣像素的φ近似，查表法將會得到相同的r，最終導致對參考點的投票分散，而本文使用比R表精確的R函數方法不會出現這類問題。

[1]Hough P V C. Method and means for recognizing complex patterns: U S, 3069654 [P]. 1962-12-18.

[2]Ballard D H. Generalizing the hough transform to detect arbitrary shapes [J]. Pattern Recognition, 1982,13: 111-122.

[3]Ser P K, Siu W C. Non-analytic object recognition using the hough transform with the matching technique [J]. Computers and Digital Techniques, 1994,141(1): 11-16.

[4]劉宏申, 程 健, 高尚義. 對偶點廣義 Hough變換算法的改進[J]. 計算機工程與設計, 2009, 30(2):423-425.

[5]Izadinia H, Sadeghi F, Ebadzadeh M M. Fuzzy generalized hough transform invariant to rotation and scale in noisy environment [C]//Proceedings of the 18th International Conference on Fuzzy Systems.Piscataway NJ, USA: IEEE Press, 2009: 153-158.

[6]姚立健, 丁為民, 張培培, 等. 基于改進型廣義Hough 變換的茄子果實位姿識別方法[J]. 農業工程學報, 2009, 25(12): 128-132.

[7]Yuan Huaqiang, Ye Yangdong, Deng Jianguang, et al.A fingerprint feature extraction algorithm based on curvature of Bezier curve [J]. Progress in Natural Science, 2007, 17(11): 1376-1381.

[8]殷明霞, 劉群輝, 桂幸民. 利用Bezier樣條曲線進行葉輪機可視化設計[J]. 航空動力學報, 2006, 21(1):156-160.

[9]余學軍, 彭立中. 二值圖像曲線輪廓提取的新算法[J].中國圖象圖形學報, 2002, 7A(3): 272-275.