基于改進(jìn)最小二乘的缺陷橢圓定位方法?

何志強(qiáng) 曹 彪 張立新

（海軍航空工程學(xué)院基礎(chǔ)實(shí)驗(yàn)部 煙臺(tái) 264001）

基于改進(jìn)最小二乘的缺陷橢圓定位方法?

何志強(qiáng) 曹 彪 張立新

（海軍航空工程學(xué)院基礎(chǔ)實(shí)驗(yàn)部 煙臺(tái) 264001）

分析形心法、Hough變換法和最小二乘擬合法等典型橢圓中心提取算法在應(yīng)用中對(duì)噪聲過(guò)于敏感、抗干擾性差的不足，提出了一種基于隨機(jī)抽樣一致性方法的改進(jìn)最小二乘橢圓中心提取算法，經(jīng)過(guò)仿真實(shí)驗(yàn)分析表明，該算法與最小二乘法、形心法相比具有更高的定位精度和強(qiáng)魯棒性。

中心定位；橢圓擬合；最小二乘法；RANSAC

1 引言

在基于視覺(jué)的航天器交匯對(duì)接中，物體位姿定和攝像機(jī)的參數(shù)標(biāo)定等是通過(guò)圖像中一系列特征點(diǎn)坐標(biāo)計(jì)算得到［1］。圓形標(biāo)志相對(duì)其他形狀，以噪聲抑制性強(qiáng)、便于識(shí)別和提取而得到廣泛使用。但是在相機(jī)成像過(guò)程中，圓形標(biāo)志經(jīng)過(guò)透視投影變換后，在圖像中呈現(xiàn)橢圓的形狀。所以對(duì)橢圓中心坐標(biāo)準(zhǔn)確提取是相機(jī)標(biāo)定、位姿測(cè)量等應(yīng)用中至關(guān)重要的環(huán)節(jié)，其中心坐標(biāo)提取的準(zhǔn)確性直接影響了最終計(jì)算結(jié)果的精度。因此，準(zhǔn)確提取橢圓中心坐標(biāo)有著重要意義。

目前常見(jiàn)橢圓中心定位算法有重心法、形心法、Hough變換法、高斯曲面擬合法和最小二乘擬合法等［2］。形心法是一種內(nèi)部區(qū)域表示法，以特征標(biāo)志外形為特征。首先進(jìn)行圖像分割，然后進(jìn)行圖像二值化，在提取到二值圖像橢圓輪廓后，在輪廓區(qū)域內(nèi)使用形心法提取橢圓中心。重心法則可以看成是以灰度為權(quán)值的加權(quán)形心法，在灰度圖像中將輪廓區(qū)域內(nèi)各點(diǎn)灰度值作為權(quán)值進(jìn)行加權(quán)平均計(jì)算。不管是形心法還是重心法，都是對(duì)橢圓輪廓區(qū)域進(jìn)行處理，對(duì)區(qū)域內(nèi)噪音敏感。Hough變換法是利用圖像空間上的橢圓與參數(shù)空間點(diǎn)之間的對(duì)偶性，滿(mǎn)足通過(guò)該點(diǎn)的超平面數(shù)目最多即認(rèn)為改點(diǎn)的坐標(biāo)值就是橢圓參數(shù)值，Hough變化雖然具有較強(qiáng)的魯棒性，但隨著模型參數(shù)增加計(jì)算量和存儲(chǔ)量指數(shù)增加，無(wú)法滿(mǎn)足現(xiàn)代檢測(cè)對(duì)實(shí)時(shí)性的要求。高斯曲面擬合法則假設(shè)橢圓的灰度分布滿(mǎn)足二維高斯分布特征［3］，在此基礎(chǔ)上用二維高斯曲面來(lái)擬合橢圓標(biāo)志，對(duì)于不能簡(jiǎn)化為點(diǎn)光源的模型該假設(shè)一般不能成立。最小二乘法屬于曲線擬合算法，提取橢圓輪廓后將輪廓像素點(diǎn)坐標(biāo)帶入?yún)?shù)方程通過(guò)最小化誤差平方和來(lái)找到一組最佳匹配參數(shù)［4～5］。所以這些方法都要求特征橢圓輪廓是完整的，當(dāng)橢圓輪廓存在干擾信號(hào)尤其是當(dāng)橢圓輪廓?dú)埲辈蝗珪r(shí)會(huì)嚴(yán)重影響擬合精度。但是在實(shí)際采集橢圓圖像過(guò)程中由于環(huán)境光照、振動(dòng)等非控制量因素影響會(huì)導(dǎo)致圖片中存在大量噪音，嚴(yán)重影響擬合精度，嚴(yán)重時(shí)甚至?xí)苯訉?dǎo)致擬合結(jié)果失效，所以考慮在橢圓擬合時(shí)如何在包含有誤差的數(shù)據(jù)集中最大程度的得到準(zhǔn)確的參數(shù)模型是本文研究的問(wèn)題。

隨機(jī)抽樣一致性（Random sample consensus，RANSAC）方法是基于已知參數(shù)模型來(lái)判別數(shù)據(jù)點(diǎn)是否為有效數(shù)據(jù)［6～8］，RANSAC算法屬于強(qiáng)魯棒性算法，可以容忍超過(guò)半數(shù)的離群數(shù)據(jù)，大量理論和實(shí)際應(yīng)用說(shuō)明該方法可以有效解決上述問(wèn)題［9］。本文分析比較了形心法、最小二乘擬合法等典型橢圓中心提取算法在應(yīng)用中對(duì)噪聲敏感，抗干擾性差的不足等問(wèn)題，故本文根據(jù)RANSAC算法的強(qiáng)魯棒性特點(diǎn)，提出了一種基于RANSAC的缺陷橢圓中心提取算法，經(jīng)過(guò)仿真實(shí)驗(yàn)分析表明，該算法能夠保持橢圓中心提取精度同時(shí)還具有很強(qiáng)的魯棒性。

2 基本概念和算法模型

2.1 最小二乘法橢圓模型

如圖1中所示，平面上任一橢圓可以由橢圓長(zhǎng)軸b短軸a，中心坐標(biāo)(xc，yc)和長(zhǎng)半軸與軸夾角θ共5個(gè)獨(dú)立參數(shù)來(lái)唯一確定［10］。則橢圓方程可以表示為：

圖1 橢圓方程

令式（3）取得最小值為約束條件，則有：

由式（4）有

將式（5）寫(xiě)成矩陣形式表示為

則式（6）可變?yōu)?/p>

參數(shù)向量X可由下式解出

2.2 基于RANSAC改進(jìn)最小二乘算法

RANSAC算法主要根據(jù)隨機(jī)表決的原理，來(lái)計(jì)算模型參數(shù)［11～12］。

令參數(shù)向量 X=(A，B，C，D，E)，d 為擬合誤差范圍，u為閾值，N為最大迭代次數(shù)。圖2所示為算法流程圖。

本文算法步驟如下：

1）隨機(jī)抽取一組觀測(cè)樣本數(shù)據(jù)t，本文中抽取8個(gè)數(shù)據(jù)點(diǎn)以保證一定的亢余。

2）將樣本數(shù)據(jù)帶入本文式（8）中，得到參數(shù)方程解X。

3）計(jì)算所有數(shù)據(jù)點(diǎn)與 X的擬合殘差delta（i），記錄殘差絕對(duì)值小于d的樣本數(shù)目，記為K1。由多次實(shí)驗(yàn)確定文中d=4時(shí)可以取得較好擬合效果。

圖2 算法流程圖

4）重復(fù)以上步驟N次，得到K1K2…KN，取N=100。其中N根據(jù)參考文獻(xiàn)12中估計(jì)式估計(jì)得到。

5）取 K=max{K1K2…KN}對(duì)應(yīng)的參數(shù)方程解Xj，j∈(1，2…N)即為求得最優(yōu)解。

3 仿真實(shí)驗(yàn)及分析

目前沒(méi)有表征橢圓缺陷變形的一般的為驗(yàn)證算法是否有效，首先用計(jì)算機(jī)生成中心坐標(biāo)已知的不同形狀橢圓并在橢圓中加入不同類(lèi)型的缺陷，如輪廓缺失、輪廓突出、邊緣不平整等［13～15］。如圖3所示，所有橢圓的理想中心坐標(biāo)已知，橢圓1為無(wú)缺陷的理想橢圓，橢圓2～橢圓5為含有一種缺陷的橢圓，橢圓6、7、8為含有兩種或以上缺陷的橢圓圖像。對(duì)圖3中橢圓圖片分別使用形心法、最小二乘法和本文算法來(lái)提取橢圓中心坐標(biāo)，得到表1。

圖3 仿真橢圓圖像

表1 橢圓中心坐標(biāo)

將各算法提取的中心定位坐標(biāo)與標(biāo)準(zhǔn)值相減并取絕對(duì)值得到各算法絕對(duì)誤差的絕對(duì)值為σ，并分別用σ1、σ2和σ3表示形心法、最小二乘法和本文算法的絕對(duì)誤差。圖像上任一像素點(diǎn)P的綜合像素誤差應(yīng)該滿(mǎn)足以下公式：

根據(jù)表1中數(shù)據(jù)整理可得到誤差數(shù)據(jù)表2和誤差分布圖4。

表2 絕對(duì)誤差數(shù)據(jù)

由圖4可以看出，在理想橢圓圖形中本文算法和形心法及最小二乘法具有同數(shù)量級(jí)的定位精度。在缺陷橢圓圖形中，本文算法定位誤差略有變大但不超過(guò)0.15個(gè)像素，而形心法和最小二乘法的定位誤差隨缺陷不同而有較大變化。最大定位誤差出現(xiàn)在圖3中的8號(hào)橢圓中，形心法和最小二乘法的定位誤差分別是4.8像素、3.7像素，對(duì)應(yīng)的本文算法定位誤差小于0.14像素，具有亞像素級(jí)定位精度且定位結(jié)果不隨橢圓缺陷的不同而變化，具有較好的魯棒性。

圖4 絕對(duì)誤差分布

4 結(jié)語(yǔ)

對(duì)橢圓中心定位算法研究分析發(fā)現(xiàn)主要算法都存在抗干擾性不足的問(wèn)題，提出了一種基于隨機(jī)約束一致性的改進(jìn)最小二乘法算法，仿真實(shí)驗(yàn)結(jié)果分析表明該算法定位精度可達(dá)到亞像素級(jí)并且還具有一定魯棒性。

［1］吳亮，王智靈.一種新的基于橢圓模型的魯棒估計(jì)方法［J］.數(shù)據(jù)采集與處理，2010，25（3）：407-412.WU Liang，WANG Zhiling.A new robust estimation method based on elliptic model［J］.Data acquisition and processing，2010，25（3）：407-412.

［2］周紅鋒，任樸生.光學(xué)測(cè)量中光斑圖像的處理及測(cè)量精度研究［J］.雞西大學(xué)學(xué)報(bào)，2014，14（5）：61-63.ZHOU Hongfeng，REN Chengsheng.Study on the processing and measurement accuracy of spot image in optical measurement［J］.Journal of Jixi University，2014，14（5）：61-63.

［3］陳天飛，趙吉賓.基于射影變換圓陣靶標(biāo)中心像點(diǎn)的計(jì)算［J］.儀器儀表學(xué)報(bào)，2015，36（4）：895-900.CHEN Tianfei，ZHAO Jibin.The projective transformation of circular array target center image point calculation based on［J］.Chinese Journal of scientific instrument，2015，36（4）：895-900.

［4］Fitzgibbon A，Pilu M，F(xiàn)isher R B.Direct least square fitting of ellipse［J］.Pattern Analysis and Machine Intelligence，1999，21（5）：476-480.

［5］林潤(rùn)芝，楊學(xué)友，鄒劍，等.面向大尺寸檢測(cè)CCD圖像中心提取精度的研究［J］.傳感器與微系統(tǒng)，2010，29（12）：51-53.LIN Runzhi，YANG Xueyou，ZOU Jian，et al.Research on the extraction accuracy of CCD image center for large size measurement［J］.Sensors and Microsystems，2010，29（12）：51-53.

［6］高晶，吳育峰，吳昆，等.基于角點(diǎn)檢測(cè)的圖像匹配算法［J］.儀器儀表學(xué)報(bào)，2013，34（8）：1717-1724.GAO Jing，WU Yufeng，WU Kun，et al.Image matching algorithm based on corner detection［J］.Chinese Journal of scientific instrument，2013，34（8）：1717-1724.

［7］張麗敏，朱楓，郝穎明，等.基于圓特征和異面點(diǎn)特征的位姿測(cè)量［J］.光子學(xué)報(bào)，2015，44（11）：20021-20025.ZHANG Limin，ZHU Feng，HAO Yingming，et al.Pose measurement based on circular features and different point features［J］.Journal of photonics，2015，44（11）：20021-20025.

［8］尹玄武，王貴錦，施陳博，等.基于RANSAC和灰度一致性的PET瓶胚口缺陷檢測(cè)［J］.計(jì)算機(jī)應(yīng)用研究，2012，29（9）：3525-3527.YIN Xuanwu，WANG Guijin，SHI Shi，et al.Detection of PET bottle mouth defects based on RANSAC and gray level coherence［J］.Computer Application Research，2012，29（9）：3525-3527.

［9］張虎，達(dá)飛鵬，邢德奎.光學(xué)測(cè)量中橢圓圓心定位算法研究［J］.應(yīng)用光學(xué)，2008，29（6）：905-911.ZHANG Hu，DA Feipeng，XING Dekui.Optical measurement of ellipse center location algorithm of［J］.Applied Optics，2008，29（6）：905-911.

［10］解則曉，顧賓.一種圓形標(biāo)記點(diǎn)的快速提取算法［J］.光學(xué)技術(shù)，2013，39（5）：393-397.XIE Zexiao，GU Bing.Rapid extraction algorithm［J］.Optical Technology of a Circular Marker，2013，39（5）：393-397.

［11］李江濤，倪國(guó)強(qiáng)，王強(qiáng)，等.一種快速準(zhǔn)確識(shí)別圓形目標(biāo)的新算法［J］.激光與紅外，2007，3（6）：575-578.LI Jiangtao，NI Guoqiang，WANG Qiang，et al.A new algorithm for fast and accurate identification of circular targets［J］.Laser and Infrared，2007，3（6）：575-578.

［12］王軍華，李丁，劉勝鵬.基于改進(jìn)RANSAC的消防機(jī)器人雙目障礙檢測(cè)［J］.計(jì)算機(jī)工程與應(yīng)用，2017，53（2）：236-240.WANG Junhua，LI Ding，LIU Shengpeng.Improved RANSAC estimation based fire-fighting robot obstacle detection using binocular vision［J］.Computer engineering and application，2017，53（2）：236-240.

［13］安新源，周宗潭，胡德文.橢圓擬合的非線性最小二乘方法［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45（18）：188-190.Xin an source，ZHOU Zongtan，HU Dewen.Nonlinear least square method for ellipse fitting［J］.Computer Engineering and Applications，2009，45（18）：188-190.

［14］譚燕，鄒崢嶸.近景攝影測(cè)量圓形標(biāo)志與其橢圓構(gòu)像的 中 心 偏 差 估 計(jì)［J］.測(cè) 繪 科 學(xué) ，2009，34（6）：250-251.TAN Yan，ZOU Zhengrong.Estimation of the central deviation of circular symbols and their ellipses in close range photogrammetry［J］.Journal of Surveying and Mapping Science，2009，34（6）：250-251.

［15］張廣軍，魏振忠.結(jié)構(gòu)光三維視覺(jué)檢測(cè)中光條橢圓中心定位方法與仿真研究［J］.儀器儀表學(xué)報(bào)，2003，24（6）：589-593.ZHANG Guangjun，WEI Zhenzhong.Research on the method and Simulation of light strip ellipse center positioning in structured light 3D vision inspection［J］.Chinese Journal of scientific instrument，2003，24（6）：589-593.

A Defect Ellipse Locating Method Based on Least Squares

HE ZhiqiangCAO BiaoZHANG Lixin
（Department of Basic Science，Naval Aeronautical and Astronautical University，Yantai 264001）

In this paper，an improved elliptic ellipse center extraction algorithm based on stochastic sampling consistency method is proposed，which is too sensitive to noise and has poor anti-jamming performance in typical ellipse center extraction algorithms such as centroid method，Hough transform method and least squares fitting method.Simulation results show that the proposed algorithm has higher accuracy and strong robustness compared with the least square method and the centroid method.

central location，ellipse fitting，least square method，RANSAC

TP242.6

10.3969/j.issn.1672-9722.2017.11.007

Class Number TP242.6

2017年5月12日，

2017年6月29日

何志強(qiáng)，男，碩士研究生，助理工程師，研究方向：機(jī)器視覺(jué)、模式識(shí)別、虛擬現(xiàn)實(shí)。