馬向南，李 航，劉麗麗，劉志偉

（河南科技大學(xué)機(jī)電工程學(xué)院，河南洛陽471003）

0 引言

視覺測量系統(tǒng)中，邊緣檢測提取的準(zhǔn)確性直接影響了最終測量的精度。邊緣檢測的過程是使用數(shù)學(xué)方法提取圖像像元中具有亮度值（灰度）空間方向梯度大的邊、線特征的過程。邊緣檢測和邊緣提取是圖像處理和計(jì)算機(jī)視覺中的基本問題，其目的在于將數(shù)字圖像中亮度變化明顯的點(diǎn)標(biāo)識出來。圖像屬性中的顯著變化通常反映了屬性的重要事件和變化。在邊緣檢測技術(shù)中常用的一種方法就是對提取的輪廓邊緣進(jìn)行擬合。橢圓擬合在數(shù)字圖像處理、計(jì)算機(jī)視覺和模式識別中有著很重要的地位，但是由于在很多實(shí)際圖像中不僅存在噪聲，還存在一些難以剔除的孤立點(diǎn)，因此，找到一種穩(wěn)健、有效、易用的橢圓擬合方法一直很難。

目前，常用的擬合方法有最小二乘擬合［1－3］、Hough變換［4－6］以及Kalman濾波法［8－9］。Hough變換是把離散的邊緣點(diǎn)連接成直線或閉合曲線常用的算法。其原理是利用圖像空間與參數(shù)空間的對應(yīng)關(guān)系，將圖像空間像素點(diǎn)利用某一解析形式轉(zhuǎn)化到參數(shù)空間，通過在參數(shù)空間進(jìn)行簡單的累加統(tǒng)計(jì)來完成檢測任務(wù)，一般而言，使用Hough變換進(jìn)行檢測只限于兩個(gè)參數(shù)的情況，因?yàn)閰?shù)過多會大大增加算法的耗時(shí)和空間復(fù)雜度。Kalman濾波常用在控制論中，是一種經(jīng)典的最優(yōu)濾波。該方法通過狀態(tài)轉(zhuǎn)移方程對狀態(tài)進(jìn)行預(yù)測，再結(jié)合觀測值對預(yù)測進(jìn)行修正，通過這樣的不斷更新修正進(jìn)行狀態(tài)的估計(jì)，最終形成擬合后的橢圓。然而這種方法卻容易受到噪聲和孤立點(diǎn)的影響，最終導(dǎo)致結(jié)果不準(zhǔn)確。

最小二乘擬合是最早的橢圓擬合方法，它是數(shù)據(jù)擬合中的基本方法，其思想為考慮數(shù)據(jù)受隨機(jī)噪聲的影響進(jìn)而追求整體誤差的最小化。這種方法最為直觀、簡單、同時(shí)比較實(shí)用，因此是擬合當(dāng)中最常用的方法。最小二乘法的做法是在假設(shè)測量點(diǎn)產(chǎn)生的隨機(jī)誤差為正態(tài)分布的前提下，采用最大似然估計(jì)方法推出的一個(gè)最優(yōu)估計(jì)解的方法，這種方法的約束條件是使誤差的平方和達(dá)到最小。由于誤差的大小可以直接反映出擬合過程的可信賴度，因此這種方法常被認(rèn)為是最可信賴的方法之一。最小二乘技術(shù)主要是尋找參數(shù)集合，從而最小化數(shù)據(jù)點(diǎn)與橢圓之間的距離度量。這里的距離度量常見的有幾何距離和代數(shù)距離［9］。最小二乘擬合有兩類求解辦法，代數(shù)擬合法和幾何擬合法。

首先，求解最小值的式子在幾何變換下是變化的；另外，代數(shù)擬合沒有考慮在橢圓上不同位置的點(diǎn)對橢圓方程參數(shù)估計(jì)的影響，使用這種方法可能使擬合出的橢圓產(chǎn)生偏差。幾何擬合法可以彌補(bǔ)這些不足，但是由于目標(biāo)函數(shù)的表達(dá)非常復(fù)雜，所以求解過程工作量很大，而且不易實(shí)現(xiàn)［8］。因此，本文對代數(shù)擬合法進(jìn)行了改進(jìn)，旨在解決代數(shù)擬合中各參數(shù)貢獻(xiàn)不同的問題，彌補(bǔ)傳統(tǒng)的最小二乘擬合在本文所給出的圖像中進(jìn)行擬合時(shí)的不足。

1 引入歸一化的最小二乘擬合算法

歸一化是一種簡化計(jì)算法，即將有量綱的表達(dá)式經(jīng)過變換，化為無量綱的表達(dá)式，成為純量。將這種方法應(yīng)用于橢圓擬合中，可以弱化橢圓上位置不同的點(diǎn)對橢圓方程參數(shù)估計(jì)貢獻(xiàn)的差別，減小擬合出的橢圓產(chǎn)生偏差的可能性。因此，本文將歸一化方法應(yīng)用到了橢圓的最小二乘擬合中。該算法步驟為：

（1）將要處理的圖像調(diào)入系統(tǒng)。

（2）用canddy算法對圖像進(jìn)行邊緣檢測。

（3）搜索連續(xù)點(diǎn)，并將搜索結(jié)果作為潛在邊緣的點(diǎn)集。

（4）判斷點(diǎn)集是否滿足控制條件，若滿足轉(zhuǎn)入下一步，否則轉(zhuǎn)入步驟（3）。

（5）將符合條件的點(diǎn)集進(jìn)行坐標(biāo)歸一化處理。

（6）利用最小二乘算法對歸一化后的坐標(biāo)點(diǎn)進(jìn)行橢圓擬合。

（7）判斷擬合結(jié)果是否滿足精度要求，滿足，轉(zhuǎn)入下一步，否則轉(zhuǎn)入步驟（3）。

（8）對擬合結(jié)果進(jìn)行反歸一化處理，對橢圓參數(shù)進(jìn)行求解。

本算法旨在檢測并擬合輸入圖像中所有滿足控制條件的橢圓。其核心思想是在canny邊緣檢測的基礎(chǔ)上，增加控制條件進(jìn)行判斷，將符合要求的準(zhǔn)橢圓轉(zhuǎn)換到歸一化坐標(biāo)系，再利用傳統(tǒng)的最小二乘算法進(jìn)行擬合。其流程圖如圖1所示。

本文采用兩種控制條件：橢圓周長的范圍（nMax：橢圓最大周長；nMin：橢圓最小周長）和在歸一化坐標(biāo)系下的擬合度（th_GOF：觀測值到擬合曲線的均方根誤差閾值）。更改控制條件可以選擇輸入圖像中不同的橢圓。

由于采用了歸一化的方法，本算法較傳統(tǒng)的擬合方法有著獨(dú)特的優(yōu)勢：

（1）將不同位置不同尺度下的橢圓都轉(zhuǎn)換到歸一化坐標(biāo)系下進(jìn)行擬合，相比于不歸一化，其數(shù)值計(jì)算更加穩(wěn)定，且所有橢圓可在同一尺度下進(jìn)行擬合度的比較。

圖1 算法流程圖

（2）采用二次曲線擬合點(diǎn)集求解亞像素級的橢圓幾何中心，比灰度重心法、高斯曲面擬合法等方法更準(zhǔn)確。

（3）Hough變換檢測橢圓法需要對圖像中任意一對邊緣點(diǎn)確定其是否為橢圓的最遠(yuǎn)點(diǎn)，需要占用大量的空間，且非常慢，因而很少用于實(shí)際檢測中。本算法以連續(xù)點(diǎn)集為考察對象，相比于Hough變換法計(jì)算速度更快捷，因此，具有較強(qiáng)的實(shí)用性。

2 實(shí)驗(yàn)結(jié)果及分析

2.1 求解結(jié)果

本文提出的算法采用Matlab得以實(shí)現(xiàn)，實(shí)驗(yàn)結(jié)果是在一臺安裝有Matlab 7.0的機(jī)器上運(yùn)行的。由于一般的圖片很大，Matlab程序遍歷圖像搜索橢圓耗時(shí)較長，為提高圖像的檢測效率，在算法開始前對圖像進(jìn)行預(yù)處理。方法為提取感興趣區(qū)域，只在該區(qū)域檢測橢圓，因此提高了檢測的目標(biāo)性，從而提升了檢測速度。

首先對邊緣進(jìn)行檢測，然后需要對準(zhǔn)橢圓點(diǎn)進(jìn)行歸一化處理：

經(jīng)過本算法處理后，可以得到由一系列連續(xù)的點(diǎn)組成一個(gè)橢圓。對參數(shù)進(jìn)行反歸一化處理后可以得到各參數(shù)在絕對坐標(biāo)系中的坐標(biāo)值。

根據(jù)擬合出的方程的參數(shù)可以求得擬合橢圓的特征參數(shù)，如表1所示。

表1 含歸一化過程的最小二乘算法擬合結(jié)果

不確定度這一概念通常用來表述由于測量誤差存在而對測量值不能肯定的程度，同時(shí)也可以用于表述可信賴度，它可以作為擬合準(zhǔn)確度的一個(gè)評價(jià)指標(biāo)。不確定度愈小，說明擬合結(jié)果具有越高的可信賴度，擬合精度也就越高。隨著不確定度的數(shù)值變得越大，測量結(jié)果的可信賴度也隨之降低，相應(yīng)的擬合精度也就越低。不確定度可以廣泛應(yīng)用于直線、圓及橢圓擬合結(jié)果的評價(jià)中［10－12］。本文引入了不確定度的概念作為擬合精度的評價(jià)指標(biāo)。一方面利用這一概念可以方便將可信賴度量化；另一方面也方便了不同方法之間的可對比性。

經(jīng)過計(jì)算，含歸一化的最小二乘擬合算法對本文中給定的二值圖擬合的不確定度的大小如圖2所示。圖2中，橫坐標(biāo)表示了點(diǎn)的編號，在這里共選取了82個(gè)點(diǎn)。縱坐標(biāo)表示了產(chǎn)生的不確定度的大小，其含義為觀測點(diǎn)與擬合出的橢圓邊界的幾何距離，當(dāng)點(diǎn)位于擬合橢圓之內(nèi)時(shí)，距離為負(fù)；而當(dāng)點(diǎn)位于擬合橢圓以外時(shí)，則距離為正。

圖2 歸一化最小二乘算法擬合結(jié)果的誤差及標(biāo)準(zhǔn)差分布圖

2.2 實(shí)驗(yàn)對比

為進(jìn)一步評估歸一化引入最小二乘擬合算法后的優(yōu)越性，本文采用傳統(tǒng)最小二乘法在同樣的條件下進(jìn)行邊界提取和最小二乘擬合，利用同樣的方法對擬合參數(shù)進(jìn)行求解可以得到擬合橢圓的特征參數(shù)，如表2所示。

表2 最小二乘算法擬合結(jié)果

通過對比可以發(fā)現(xiàn)：兩種方法在長短軸的差別較大，由于擬合偏差不太大，所以也用其擬合不確定度來評價(jià)，其不確定度大小如圖3所示。圖3中，橫坐標(biāo)表示點(diǎn)的編號，在這里共選取了82個(gè)點(diǎn)?？v坐標(biāo)表示產(chǎn)生的不確定度的大小，其含義為觀測點(diǎn)到擬合出的橢圓邊界的幾何距離，當(dāng)點(diǎn)位于擬合橢圓之內(nèi)時(shí)，距離為負(fù)；而當(dāng)點(diǎn)位于擬合橢圓以外時(shí)，則距離為正。

圖3 最小二乘算法擬合結(jié)果的誤差及標(biāo)準(zhǔn)差分布圖

通過圖2和圖3的對比可以看出：兩種方法擬合出結(jié)果的不確定度走勢相同，但大小上存在差異，改進(jìn)后的最小二乘擬合在誤差控制上的能力要優(yōu)于傳統(tǒng)的最小二乘擬合。因此，采用歸一化后進(jìn)行最小二乘擬合在工程中對圖像數(shù)據(jù)進(jìn)行擬合處理具有精度優(yōu)勢。由于采用了歸一化處理，算法的魯棒性同時(shí)得到了保證，經(jīng)測試，在上文中給定的電腦配置上對給定的圖像進(jìn)行處理，程序的運(yùn)行和處理時(shí)間能夠控制在20 ms內(nèi)，完全滿足性能的需求，故該算法具有實(shí)際意義。

3 結(jié)束語

由于傳統(tǒng)最小二乘法把所有樣本點(diǎn)都近似為準(zhǔn)確值，因此擬合出的橢圓誤差比較大。為了提高橢圓擬合的精度，本文利用歸一化處理對傳統(tǒng)的最小二乘擬合算法進(jìn)行了改進(jìn)。經(jīng)過兩種方法對比，本文中的算法在求取最優(yōu)橢圓的過程中能夠?qū)㈦s質(zhì)點(diǎn)的影響降低，提高準(zhǔn)確度的同時(shí)也增強(qiáng)了系統(tǒng)的魯棒性。另外，不同點(diǎn)之間的貢獻(xiàn)度也得到了體現(xiàn)，因此可以減小可能帶來的偏差。本文當(dāng)中的算法所需要的運(yùn)行時(shí)間也較短，在樣本點(diǎn)為200～600個(gè)時(shí)，運(yùn)算時(shí)間能夠控制在20 ms以內(nèi)，因此完全能夠滿足實(shí)時(shí)系統(tǒng)要求。

［1］ 安新源，周宗潭，胡德文.橢圓擬合的非線性最小二乘方法［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45（18）：188－190.

［2］ 閆蓓，王斌，李媛.基于最小二乘法的橢圓擬合改進(jìn)算法［J］.北京航空航天大學(xué)學(xué)報(bào)，2008（3）：295－298.

［3］ 呂洪赫，姚振杰，易衛(wèi)東.基于對稱性的最小二乘擬合隨機(jī)橢圓檢測算法［J］.電子測量技術(shù)，2011（5）：37－41.

［4］ 陳立，萬鵬，何濤，等.基于Hough變換的亞像素橢圓檢測［J］.湖北工業(yè)大學(xué)學(xué)報(bào)，2005（5）：132－134.

［5］ 程軍濤，段明德，劉鑫，等.摩托車覆蓋件的逆向設(shè)計(jì)［J］.河南科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，30（5）：21－23.

［6］ 楊蘇.基于局部分析的Hough變換形狀檢測關(guān)鍵技術(shù)研究［D］.秦皇島：燕山大學(xué)，2009.

［7］ 夏菁.橢圓擬合方法的比較研究［D］.廣州：暨南大學(xué)，2007.

［8］ 華瑞娟.多橢圓擬合的算法研究［D］.廣州：暨南大學(xué)，2010.

［9］ 曹芳.計(jì)算機(jī)視覺中的各點(diǎn)異性回歸技術(shù)［D］.上海：上海海事大學(xué)，2004.

［10］ 雷賢卿，李言，李濟(jì)順，等.截面最小二乘圓心位置的余弦回歸提取法［J］.河南科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，27（1）：13－17.

［11］ 來雪梅，王雪萍，張海燕.實(shí)驗(yàn)數(shù)據(jù)的擬合及其不確定度表示［J］.中北大學(xué)學(xué)報(bào)：自然科學(xué)版，2009（5）：481－484.

［12］ 倪驍驊.形狀誤差測量結(jié)果不確定度的研究及應(yīng)用［D］.合肥：合肥工業(yè)大學(xué)，2002.