一種基于Hough變換新的亞像素定位算法

陳光靜，陳明貴，肖玉強

（1.西安通信學院電子工程系，陜西西安710106；2.西安電子科技大學機電工程學院，陜西西安710071）

測量的方式、方法正向多樣化發(fā)展，對幾何量測量來說，其測量尺度正在向兩個極端發(fā)展——小尺寸方向和大尺寸方向。小尺寸方向是指新型微米測量和納米測量的研究與應用；大尺寸測量指幾米至幾百米范圍內(nèi)物體的空間位置、尺寸、形狀、運動軌跡等的測量，數(shù)字攝影測量是近幾年發(fā)展起來的一種非接觸測量技術(shù)［1］，已廣泛用于幾何量的測量中，其測量精度的關(guān)鍵技術(shù)之一是亞像素定位算法。本文分析了數(shù)字攝影測量的基本原理，提出了一種基于Hough變換的用于檢測直線和圓的亞像素定位算法，并對亞像素定位算法進行了仿真和實驗，結(jié)果表明亞像素定位精度能達到0.02像素［2］，有效地提高了數(shù)字攝影測量的精度。提下，像點、光心和物點滿足共線方程，即三點共線。精確地確定由像點和光心組成的射線是攝影測量的關(guān)鍵，要做到這一點，就要注意兩個關(guān)鍵因素：1）精確地確定攝影系統(tǒng)的系統(tǒng)參數(shù)，如光心、光軸和焦距；2）精確地提取目標的對應像點的位置。

式（1）就是攝影測量學中最基本的共線方程，其中物點、光心和像點這三點必須在同一條直線上。該表達式反應了空間物點的坐標（xw，yw，zw）和光心坐標T及光軸角度R和對應像點（X，Y）之間的數(shù)學關(guān)系。

根據(jù)共線方程，在攝像機內(nèi)部參數(shù)確定的條件下，利用若干個已知的物點和相應的像點坐標，就可以根據(jù)式（1）求解出攝像機的6個外參數(shù)，即攝像機的光心坐標和光軸方位

1 數(shù)字攝影測量的基本原理

攝像機模型是光學成像幾何關(guān)系的簡化，最簡單的模型為線性模型（或者稱為針孔模型）。在滿足針孔模型假設的前的信息。

2 基于Hough變換的亞像素定位法

對圖像中目標進行定位是基于圖像精密測量的最基本和最重要的任務之一。標志中心的亞像素定位是進行攝像機標定前的必須步驟，其定位精度直接影響著后面的標定精度，是順利進行攝影測量的基礎。

由于標定模板及用定向反光材料制作的標志多是由矩形和圓構(gòu)成的，為了達到對矩形和圓形中心的子像素級精度定位，首先用邊緣檢測算子對矩形和圓形的邊緣進行整像素級精度粗定位，然后對像素級邊緣點進行亞像素級定位，從而確定標志中心的精確位置。

Hough變換是利用圖像全局特性而將邊緣像素連接起來組成區(qū)域封閉邊界的一種方法。在預先知道區(qū)域形狀的條件下，利用Hough變換可以方便地得到邊界曲線而將不連續(xù)的像素邊緣點連接起來，可以直接檢測某些已知形狀的目標，如直線和圓。本文充分利用Hough變換的優(yōu)點，針對其在檢測直線和圓方面的缺點進行改進，提出了用于檢測直線的二次Hough變換法和用于檢測圓的三等分Hough變換法。

2.1 邊緣點粗定位

像素級邊緣點檢測方法主要是用經(jīng)典的邊緣提取算子，如Sobel算子、Prewitt算子、LoG算子和Cany算子等。這些經(jīng)典算子是微分法，都要計算像素點（i，j）處的梯度，因此，本文采用了3×3的卷積模板，如圖1所示。

圖1 邊緣點粗定位采用的卷積模板Fig.1 The unfolding pattern for rude locate of edge-point

其中梯度分量為：

梯度幅值為：

梯度方向為：

2.2 用于檢測直線的二次Hough變換及矩形中心的亞像素定位方法

在利用Hough變換進行直線檢測方面具有并行實現(xiàn)、受噪聲和曲線間斷的影響小等主要優(yōu)點，但也存在很多不足［3-4］。例如：難于找到累加器數(shù)組的局部最大值，精度低，存儲空間較大，計算速度較低。為了解決這些問題，本文在傳統(tǒng)Hough變換的基礎上進行改進，通過使用二次Hough變換的方法來克服存儲空間以及計算精度和速度方面的問題。

第一次Hough變換主要用于直線位置的粗定位。進行第一次Hough變換的時候可以很好地去除噪聲的干擾。

第二次Hough變換主要用于直線的精確定位，通過對第一次Hough變換后得到的步長進行進一步細分。經(jīng)過第二次Hough變換可以快速得到直線的參數(shù)，且具有較高的定位精度。

利用二次Hough變換得到其參數(shù)空間坐標系中的參數(shù)，這些參數(shù)點對應它們在圖像坐標系中的特征直線。根據(jù)參數(shù)坐標，得到（ρ，θ），由極坐標方程

從而可以寫出直線方程

2.3 用于檢測圓的三等分Hough變換及圓心的亞像素定位方法

對于圖像存在噪聲和邊緣不連續(xù)性等干擾，Hough變換具有較強的魯棒性，長期以來成為圓檢測的主要方法，被認為是高效的匹配濾波工具，但傳統(tǒng)Hough變換存在以下幾個主要的缺點[5-7]：1）計算量大，占用內(nèi)存大；2）檢測性能受參數(shù)離散間隔制約；3）存在多個圓或橢圓時檢測性能不佳。為克服上述缺點，本文對傳統(tǒng)Hough變換進行改進，提出了圓的三等分Hough變換檢測方法。

圓的方程可表示為：

假定圓心O點坐標為（x0，y0），圓的半徑為R，已知圓上a，b，c三點的坐標分別為（xa，ya）、（xb，yb）、（xc，yc），三點與圓心之間所成的夾角∠aob、∠boc、∠coa均為120°，則圓心坐標為：

圓的半徑為

這里，取半徑為

在由x0、y0、R所組成三維參量空間中，映射到參量空間中的圓心和半徑為式（4）和式（5）所確定的一些點。對這些點進行統(tǒng)計累積，每選取的一組點，它所確定的圓心坐標和半徑的累積值增加1。當對所有隊列中的點進行完這種操作后，具有最大累積值的點作為圓的參數(shù)。

3 仿真及實驗

為了驗證本文提出的直線與圓的亞像素定位算法的精度及可靠性，選擇含有正方形和圓形標志的模板為測量對象，共進行了兩方面的實驗，1）用計算機仿真直線和圓，對理想邊緣加入誤差進行模擬計算；2）用數(shù)碼相機拍攝實際標志模板的圖像，然后進行處理。

3.1 計算機仿真模擬

3.1.1 正 方形標志仿真

正方形標志仿真用來驗證直線定位算法的有效性。表1是定位中心的試驗數(shù)據(jù)（表中為部分結(jié)果），其中D=（xw-x）2+（yw-y）2體現(xiàn)了該算法的精度。

表1 正方形標志定位中心仿真數(shù)據(jù)Tab.1 Location center simulation data of square indicator

從上表可看出，直線定位算法對正方形標志中心的定位精度在0.003 mm以內(nèi)，說明直線定位算法具有很好的定位效果，能把誤差控制在有效范圍內(nèi)。

3.1.2 圓 形標志仿真實驗

本文在模板成像實驗中，實際標志圖像的邊緣點進行橢圓最小二乘擬合后，各點相對于擬合橢圓邊界均有偏差值，將這些偏差值當作實際誤差加入到模擬橢圓的邊緣點上，然后進行擬合，從而可以計算加入實際誤差（或噪聲）的中心定位精度。

這里采用了LoG算子粗定位邊緣點及其亞像素邊緣點的實際擬合偏差。圖2（a）的實際邊緣點數(shù)為48個，粗定位邊緣點擬合后各點偏差的均方根（RMS）為0.380像素，亞像素擬合后的RMS為0.148像素；圖2（b）的實際邊緣點數(shù)為40個，粗定位邊緣點擬合后各點偏差的RMS為0.441像素，亞像素擬合后的RMS為0.146像素。模擬橢圓的圓心坐標為（40，40），加入實際偏差后的中心計算結(jié)果見表2。

表2 圓形標志定位中心仿真數(shù)據(jù)Tab.2 Location center simulation data of circle indicator

從上表可看出，粗定位邊緣對標志中心的定位精度在0.02～0.1像素，亞像素邊緣對標志中心的定位精度優(yōu)于0.02像素。

3.2 實際模板成像實驗

3.2.1 正 方形標志成像實驗

采用普通數(shù)碼相機（Panasonic DMC-LZ8）對標定模板中的正方形進行拍攝照片，由于畸變的存在，實際正方形成像后呈長方形。但由于正方形和長方形中心的定位方法基本一樣，所以成像后的長方形中心即可近似認為是原模板中對應正方形的中心。表3是定位中心的實驗數(shù)據(jù)（表中為部分結(jié)果），其中D=（xw-x）2+（yw-y）2體現(xiàn)了該實驗算法的精度。

表3 正方形標志定位中心實驗數(shù)據(jù)Tab.3 Location center experiment data of square indicator

從上表可看出，直線定位算法對正方形標志中心的定位精度在0.005 mm以內(nèi)，精度較仿真實驗略低，但仍能說明直線定位算法具有很高的定位精度。

3.2.2 圓 形標志成像實驗

采用普通數(shù)碼相機對RRT標志拍攝照片（圖2），圖2（a）近似為理想的“二值”圓，圖2（b）是偏離攝影光軸的標志影像，呈橢圓形且相對于圖2（a）其反差較小。

圖2 定向反光標志的“準二值影像”Fig.2 The quasi-two-value image of directional glisten indicator

為了驗證算法的精度，進行了以下兩方面的實驗：1）用不同算子粗定位的像素級邊緣點擬合橢圓中心；2）對相同圖像用亞像素精度的像素邊緣點擬合橢圓中心。

實驗1）中，邊緣點粗定位分別采用了閾值分割法、Sobel算子以及LoG算子，粗定位邊緣點和相應的亞像素邊緣點擬合的標志中心結(jié)果見表4。

表4 圓形標志定位中心實驗數(shù)據(jù)Tab.4 Location center experiment data of circle indicator

從上表可看出，不同的粗定位算法得到的結(jié)果是不一樣的，標志影像質(zhì)量較好時差異較?。▓A形標志X和Y分量差值為0.07像素和0.04像素），而標志影像質(zhì)量不是很好時差異較大（橢圓標志X和Y分量差值均為0.1像素）；當采用亞像素邊緣擬合標志中心時，不同的算法其結(jié)果差異很小，最大只有0.02像素，這與實驗1）的結(jié)果是一致的。

由于攝影是透視成像，越是處在像片邊緣的圓形標志，其成像后橢圓度越高。對不同橢圓度的標志圖像進行了處理，在適當曝光確保成像質(zhì)量的前提下，其結(jié)果與上述實驗是一致的。

4 結(jié)論

針對直線邊緣檢測和圓邊緣檢測，分別采用二次Hough變換法和三等分Hough變換法，通過使用二次Hough變換的方法，克服了直線邊緣計算精度低和速度慢的問題，通過使用三等分Hough變換法，克服了傳統(tǒng)Hough變換法圓邊緣檢測性能受參數(shù)離散間隔制約及精度低的問題。仿真和實驗表明新算法的亞像素定位精度能達到0.02像素以內(nèi)，由此見，采用新的亞像素算法可有效提高了數(shù)字攝影測量的精度。

[1]于起峰，陸宏偉，劉肖琳.基于圖像的精密測量與運動測量[M].北京：科學出版社，2002.

[2]肖玉強.基于數(shù)字攝影測量的大尺寸精密測試技術(shù)研究[D].西安：西安電子科技大學，2010.

[3]李強兵，劉文予.基于Hough變換的快速矩形檢測算法[J].微計算機信息，2007，23（11-1）：248-250.

LI Qiang-bing，LIU Wen-yu.The quick rectangle detection algorithm based on Hough transform[J].Control&Automation，2007，23（11-1）:248-250.

[4]劉良江，王耀南.一種基于Hough變換的圓的檢測方法[M].湖南：湖南大學，2007.

[5]Edmundson K，Baker L.Photogrammetric measurement of the arecibo primary reflector surface the coordinate measurement systems committee conf[J].Albuquerque，NM，2001，（8）：l3-l7.

[6]Jensen K，Anastassiou D.Subpixel edge localization and the interpolation of still images[J].IEEE Trans.on IP，1995，4（3）:285-295

[7]Beghdadi A，Negrate A L.Contrast enhancement technique based on local detection of edge[J].Computer Vision，Graphics and Image Processing，1989，46（2）:162-174