基于最小二乘的圓及橢圓檢測(cè)算法

1、基于最小二乘原理的圓及橢圓檢測(cè)算法*孔 兵 王 昭 譚玉山（西安交通大學(xué)激光與紅外應(yīng)用研究所，西安，, ）摘 要 在光學(xué)測(cè)量中，圓或橢圓檢測(cè)檢測(cè)是經(jīng)常用到的一項(xiàng)關(guān)鍵技術(shù)。檢測(cè)算法的精度、速度直接影響了光學(xué)測(cè)量的精度及速度，而傳統(tǒng)的檢測(cè)算法如重心法、Hough變換法等在檢測(cè)精度或速度上存在不足之處。本文首次提出的基于最小二乘原理的圓及橢圓檢測(cè)算法，達(dá)到亞像素級(jí)的定位精度，而且還具有很快的計(jì)算速度，可適用于實(shí)時(shí)的光學(xué)測(cè)量。關(guān)鍵詞 最小二乘算法 圖像處理 圓 橢圓中圖分類號(hào) 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引 言激光光斑中心檢測(cè)在激光掃描三角法、激光準(zhǔn)直儀、激光光斑分析儀等光學(xué)測(cè)量、檢測(cè)手段中是一項(xiàng)關(guān)鍵技術(shù)1,2，檢測(cè)算法的精度、速度直接影響

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

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

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

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

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

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

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

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