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

1、基于最小二乘原理地圓及橢圓檢測(cè)算法孔兵王昭譚玉山西安交通大學(xué)激光與紅外應(yīng)用研究所，西安，710049, ）摘要在光學(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è)量.b5E2RGbCAP 關(guān)鍵詞最小二乘算法 圖像處理圓橢圓中圖分類號(hào)TP391The Circle and Ellipse Detection AlgorithmBased on Leas

2、t Square MethodKONG Bing WANG Zhao TAN Yu-Shan（Institute of Laser & Infrared Technology Application, Xi an Jiaotong University? XianqFDPW an, 710049AbstractAbstractThe circle and ellipse detecti on is the key tech niq ue，which is always used in theoptical measureme nt. The precisi on and speed of th

3、e detecti on algorithm in flue nce those of the optical measurement systemdirectly. The traditional algorithms such as gravity model， Hough tran sform are un satisfactory in some con diti ons. The circle and ellipse detecti on algorithm based on the least square method is firstly referred in this pa

4、per. The orientation precision is in the order of inferior pixels，and the speed is fast with the algorithm. The algorithm is suitable for the realtime optical measureme nt.DXDiTa9E3dKeyKey wordswords LSM（least square method，digital image processing，circle，ellipse RTCrpUDGiT0引言激光光斑中心檢測(cè)在激光掃描三角法、激光準(zhǔn)直儀、

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

6、地計(jì)算速度，可適用 于實(shí)時(shí)地光學(xué)測(cè)量.5PCzVD7HxA1傳統(tǒng)圓檢測(cè)算法1 1. 1 1重心法以圖1為例進(jìn)行分析，假設(shè)光斑圖像處于二維平面坐標(biāo)系中，大小為尸_1,光斑圖像是經(jīng)過(guò)預(yù)處理后得到二值圖像 下同），圖中較亮地區(qū)域即代表了激光光斑，可表示為jLBHrnAlLg*受自然科學(xué)基金（60077031及西安交通大學(xué)在職博士基金資助 嚴(yán)工| 1）圖1光斑圖像以時(shí)間復(fù)雜度來(lái)考慮算法地速度光斑區(qū)域內(nèi)求和，因此時(shí)間復(fù)雜度為3)5)重心法計(jì)算地光斑中心為K |)，假設(shè)光斑直徑為，以下均做相同地假設(shè),2）式是在叵 .該算法簡(jiǎn)單明了 ，計(jì)算速度較快,在光斑光強(qiáng)比較均勻地情況下 對(duì)應(yīng)地圖1中光斑形狀比較規(guī)則）

7、不失為一種好地算法但是該算法受光斑形狀影響比較大，而且只能獲取光斑地中心不能檢測(cè)半徑，在某些需要計(jì)算光斑半徑地測(cè)量中不能適用.XHAQX74J0X1 1. 2 2 HoughHough變換法采用Hough變換檢測(cè)任意曲線地原理如下：檢測(cè)曲線地參數(shù)方程記為其中， 尸廠|為方程參數(shù)，F(xiàn) 為空間圖像點(diǎn)坐標(biāo).對(duì)于圖像中任一空間點(diǎn)，可由3）式變換為參數(shù)空間.r_中地一條曲線.對(duì)圖像曲線上 個(gè)點(diǎn)進(jìn)行上述變換，在參數(shù)空間得到條曲線，由3 ）式可知這條曲線必定經(jīng)過(guò)同一點(diǎn)1，根據(jù)參數(shù)空間地此點(diǎn)坐標(biāo)便可確定圖像空間域中地曲線1 .直線、圓地參數(shù)方程分別為：LDAYtRyKfEHough變換是將空間域內(nèi)每個(gè)輪廓點(diǎn)帶

8、入?yún)?shù)方程3），根據(jù)計(jì)算結(jié)果對(duì)參數(shù)空間.一中地量化點(diǎn)按就近原則進(jìn)行投票，得票最多地點(diǎn)既為所求圖像空間域中曲線對(duì)應(yīng)地參數(shù)空間點(diǎn).Zzz6ZB2Ltk由5）式，圓地參數(shù)空間為丄，其中I表示圓心，表示半徑，因此采用Hough變換可以檢測(cè)出激光光斑地中心及半徑.dvzfvkwMI1Hough變換需要對(duì)參數(shù)空間離散化，限制了檢測(cè)精度，另外參數(shù)空間得票最多地點(diǎn)未必唯一,選擇不同地點(diǎn)得到地圖像空間曲線差異比較大.圓地Hough變換由于對(duì)每一個(gè)邊界點(diǎn)都需要在三維參數(shù)空間內(nèi)逐點(diǎn)投票、記錄，時(shí)間復(fù)雜度為刁,計(jì)算時(shí)間比較長(zhǎng)，而且占 用計(jì)算機(jī)內(nèi)存比較大，因此在實(shí)用中受到了限制.rqyn14ZNXI2基于最小二乘原理地

9、圓及橢圓檢測(cè)算法2. 1圓檢測(cè)算法基于圓擬合地激光光斑中心檢測(cè)算法，根據(jù)最小二乘原理 殘差平方和最小）用圓來(lái)逼近激光光斑輪廓.圓地方程為：EmxvxOtOco在此，取殘差為:1 X 13)14）及半徑）檢測(cè)算法III ,較為復(fù)雜地開(kāi)殘差平方和函數(shù)為:根據(jù)最小二乘原理，應(yīng)有將10 ）式簡(jiǎn)化整理得:其中各參數(shù)可用下式表示：=12）對(duì)11）式消掉二次項(xiàng)后整理為:由上式便可推出參數(shù)地表達(dá)式,結(jié)合11 ）式得圓參數(shù)為:由14）式可以看出，根據(jù)最小二乘原理地圓擬合推導(dǎo)出地光斑中心雖然形式復(fù)雜，但僅對(duì)邊界點(diǎn)循環(huán)一次就可計(jì)算出各參數(shù),時(shí)間復(fù)雜度為其中，F(xiàn)I ,表示所有邊界地集合-I表示圖像邊界點(diǎn)坐標(biāo)8)9)1

10、1)習(xí)后計(jì)算半徑時(shí)僅計(jì)算一次，因此整個(gè)算法地計(jì)算速度將根方運(yùn)算只是在計(jì)算出中心參數(shù)會(huì)很快.SixE2yXPq52. 2橢圓檢測(cè)算法橢圓方程標(biāo)準(zhǔn)形式為：15)將其變形為：殘差平方和函數(shù)為：由最小二乘原理有一即將10 )式簡(jiǎn)化整理得:其中,17)16):1655 16600YujCfmUCw2Paul J, Frederick W, David L, Randy T. Nova laser alignment control system. SPIE, 1984, 483:54 64eUts8ZQVRd3嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)，北京:清華大學(xué)出版社，1997圖2圓形光斑檢測(cè)迭代檢測(cè)出地橢圓，圖c為經(jīng)過(guò)兩次迭代檢測(cè)出地橢圓，圖d為經(jīng)過(guò)三次迭代檢測(cè)出地橢圓檢測(cè)地中心，長(zhǎng)、短軸，與理想中心變差，以及計(jì)算時(shí)間如表1所示，由此可見(jiàn)，采用最小二乘法檢測(cè)橢圓并