基于最小二乘的圓及橢圓檢測算法

1、基于最小二乘原理的圓及橢圓檢測算法*孔 兵 王 昭 譚玉山（西安交通大學(xué)激光與紅外應(yīng)用研究所，西安，, ）摘 要 在光學(xué)測量中，圓或橢圓檢測檢測是經(jīng)常用到的一項關(guān)鍵技術(shù)。檢測算法的精度、速度直接影響了光學(xué)測量的精度及速度，而傳統(tǒng)的檢測算法如重心法、Hough變換法等在檢測精度或速度上存在不足之處。本文首次提出的基于最小二乘原理的圓及橢圓檢測算法，達到亞像素級的定位精度，而且還具有很快的計算速度，可適用于實時的光學(xué)測量。關(guān)鍵詞 最小二乘算法 圖像處理 圓 橢圓中圖分類號 TP391The Circle and Ellipse Detection Algorithm

2、Based on Least Square MethodKONG Bing WANG Zhao TAN Yu-Shan(Institute of Laser & Infrared Technology Application, Xian Jiaotong University, Xian, )AbstractThe circle and ellipse detection is the key technique, which is always used in the optical measurement. The precision and speed of the detection

3、algorithm influence those of the optical measurement system directly. The traditional algorithms such as gravity model, Hough transform are unsatisfactory in some conditions. The circle and ellipse detection algorithm based on the least square method is firstly referred in this paper. The orientatio

4、n precision is in the order of inferior pixels, and the speed is fast with the algorithm. The algorithm is suitable for the real-time optical measurement.Key wordsLSM(least square method), digital image processing, circle, ellipse0引 言激光光斑中心檢測在激光掃描三角法、激光準直儀、激光光斑分析儀等光學(xué)測量、檢測手段中是一項關(guān)鍵技術(shù)1,2，檢測算法的精度、速度直接影響

5、了光學(xué)測量的精度及速度。傳統(tǒng)的光斑中心檢測算法有重心法、中值法，以及Hough變換法1。前兩種算法要求光斑圖像分布比較均勻，否則將會參生較大誤差。后一種算法需逐點投票、記錄，所用時間較多，而且精度也不夠高。然而由于在實際光學(xué)測量中，由于存在的散斑、被測物面反射特性不均勻以及光學(xué)系統(tǒng)的影響，導(dǎo)致光斑信號強度分布極不均勻，而且測量中一般對實時性要求較高，采用上述算法均有其不足之處。本文首次提出了基于最小二乘原理的圓及橢圓檢測算法，可以同時檢測光斑中心及半徑（或長、短軸），達到亞像素級的定位精度，而且還具有毫秒級的計算速度，可適用于實時的光學(xué)測量。1傳統(tǒng)圓檢測算法11 重心法*受自然科學(xué)基金()及西

6、安交通大學(xué)在職博士基金資助以圖1為例進行分析，假設(shè)光斑圖像處于二維平面坐標系中，大小為，光斑圖像是經(jīng)過預(yù)處理后得到二值圖像（下同），圖中較亮的區(qū)域即代表了激光光斑，可表示為圖1 光斑圖像（1）重心法計算的光斑中心為（2）以時間復(fù)雜度來考慮算法的速度，假設(shè)光斑直徑為，以下均做相同的假設(shè)，（2）式是在光斑區(qū)域內(nèi)求和，因此時間復(fù)雜度為3。該算法簡單明了，計算速度較快，在光斑光強比較均勻的情況下（對應(yīng)的圖1中光斑形狀比較規(guī)則）不失為一種好的算法。但是該算法受光斑形狀影響比較大，而且只能獲取光斑的中心不能檢測半徑，在某些需要計算光斑半徑的測量中不能適用。12 Hough變換法采用Hough變換檢測任意曲

7、線的原理如下4：檢測曲線的參數(shù)方程記為（3）其中，為方程參數(shù)，為空間圖像點坐標。對于圖像中任一空間點，可由（3）式變換為參數(shù)空間中的一條曲線。對圖像曲線上個點進行上述變換，在參數(shù)空間得到條曲線，由（3）式可知這條曲線必定經(jīng)過同一點，根據(jù)參數(shù)空間的此點坐標便可確定圖像空間域中的曲線。直線、圓的參數(shù)方程分別為： （4）（5）Hough變換是將空間域內(nèi)每個輪廓點帶入?yún)?shù)方程（3），根據(jù)計算結(jié)果對參數(shù)空間中的量化點按就近原則進行投票，得票最多的點既為所求圖像空間域中曲線對應(yīng)的參數(shù)空間點。由（5）式，圓的參數(shù)空間為，其中表示圓心，表示半徑，因此采用Hough變換可以檢測出激光光斑的中心及半徑。Hough

8、變換需要對參數(shù)空間離散化，限制了檢測精度，另外參數(shù)空間得票最多的點未必唯一，選擇不同的點得到的圖像空間曲線差異比較大。圓的Hough變換由于對每一個邊界點都需要在三維參數(shù)空間內(nèi)逐點投票、記錄，時間復(fù)雜度為，計算時間比較長，而且占用計算機內(nèi)存比較大，因此在實用中受到了限制。2 基于最小二乘原理的圓及橢圓檢測算法21 圓檢測算法基于圓擬合的激光光斑中心檢測算法，根據(jù)最小二乘原理（殘差平方和最小）用圓來逼近激光光斑輪廓。圓的方程為：（6）在此，取殘差為：（7）其中，表示所有邊界的集合，表示圖像邊界點坐標。殘差平方和函數(shù)為：（8）根據(jù)最小二乘原理5，應(yīng)有（9）即（10）將（10）式簡化整理得：（11）

9、其中各參數(shù)可用下式表示：（12）對（11）式消掉二次項后整理為：（13）由上式便可推出參數(shù)的表達式，結(jié)合（11）式得圓參數(shù)為：（14）由（14）式可以看出，根據(jù)最小二乘原理的圓擬合推導(dǎo)出的光斑中心（及半徑）檢測算法雖然形式復(fù)雜，但僅對邊界點循環(huán)一次就可計算出各參數(shù)，時間復(fù)雜度為，較為復(fù)雜的開根方運算只是在計算出中心參數(shù)后計算半徑時僅計算一次，因此整個算法的計算速度將會很快。22 橢圓檢測算法橢圓方程標準形式為：（15）將其變形為：（16）其中 同樣取殘差（17）殘差平方和函數(shù)為：（18）由最小二乘原理有（19）即（20）將（10）式簡化整理得：（21）其中，（22）將（21）式消掉二次項a2，

10、及三次項cb2得（23）其中，（24）記，（23）式化為：（25）由上式可解得的值，也就計算出的值，進而由（21）式計算的值（26）由也就可以計算橢圓長、短軸的值（27）同樣，僅對邊界點循環(huán)一次就可計算出橢圓各參數(shù)，時間復(fù)雜度為，算法具有很快的計算速度。3 通過迭代法進一步提高檢測精度獲得圓或橢圓的參數(shù)后，便可根據(jù)（7）式或（17）式獲得各邊界點殘差，只要去掉殘差較大的邊界點，保留殘差較小的邊界點，重新按照（14）式或（25）、（26）、（27）式計算圓或橢圓的參數(shù)，經(jīng)多次迭代便可進一步提高檢測精度。在此可設(shè)定平均殘差平方和作為閾值，平均殘差平方和由下式求取(28)其中，殘差平方和由（8）式或

11、（18）式求取。圖2 圓形光斑檢測4 實驗生成一幅人工圖像，圖中的圓邊界加入了干擾，原始中心為（344，288），如圖2中小十字A所示，半徑為199。在Pentium II266MHz計算機上分別對重心法及本方法進行了比較，重心法獲取的中心坐標位置為（336.7,289.6 ），如圖2中小十字線B所示，不能檢測半徑，所用計算時間為11ms?；趫A擬合的方法采用上述思想進行了兩次迭代，檢測的中心坐標為(341.0,287.9)，如圖2中灰十字線C所示，半徑為195.2，用灰色標記出檢測出的圓，計算時間為3.3ms。生成另一幅人工圖像，圖中的橢圓邊界同樣加入了干擾，原始中心為（244，220），在

12、圖3中以小十字所示，長短軸分別為。圖a為沒有經(jīng)過迭代直接根據(jù)最小二乘法檢測出的橢圓，圖b為經(jīng)過一次迭代檢測出的橢圓，圖c為經(jīng)過兩次迭代檢測出的橢圓，圖d為經(jīng)過三次迭代檢測出的橢圓。檢測的中心，長、短軸，與理想中心變差，以及計算時間如表1所示，由此可見，采用最小二乘法檢測橢圓并經(jīng)23次迭代便可獲較高的檢測精度。(a)無迭代(b)一次迭代(c)兩次迭代(d)三次迭代圖3 橢圓形光斑檢測表1 橢圓檢測結(jié)果迭代次數(shù)中心長、短軸與理想中心偏差計算時間(ms)0233.8199.0180.2111.011.394.41236.2202.9187.7111.77.845.62241.8203.8195.33242.5204.0196.2111.21.547.85結(jié)論相對于重心法、Hough變換法，本文提出的基于圓及橢圓擬合的光斑檢測算法除了光斑中心和半徑（長、短軸）可同時檢測外，還具有更快的計算速度及檢測精度，可用于實時的光學(xué)測量及檢測。參考文獻1 楊耀權(quán), 施仁, 于希寧, 高鏜年. 用Hough變換提高激光光斑中心定位精度的算法. 光學(xué)學(xué)報, 1999, 19(12):165516602 Paul J, Frederick W, David L, Randy T. Nova