最小二乘改進算法及其在橢圓擬合中的應用

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

（河南科技大學機電工程學院，河南洛陽471003）

0 引言

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

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

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

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

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

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

（1）將要處理的圖像調入系統。

（2）用canddy算法對圖像進行邊緣檢測。

（3）搜索連續點，并將搜索結果作為潛在邊緣的點集。

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

（5）將符合條件的點集進行坐標歸一化處理。

（6）利用最小二乘算法對歸一化后的坐標點進行橢圓擬合。

（7）判斷擬合結果是否滿足精度要求，滿足，轉入下一步，否則轉入步驟（3）。

（8）對擬合結果進行反歸一化處理，對橢圓參數進行求解。

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

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

由于采用了歸一化的方法，本算法較傳統的擬合方法有著獨特的優勢：

（1）將不同位置不同尺度下的橢圓都轉換到歸一化坐標系下進行擬合，相比于不歸一化，其數值計算更加穩定，且所有橢圓可在同一尺度下進行擬合度的比較。

圖1 算法流程圖

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

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

2 實驗結果及分析

2.1 求解結果

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

首先對邊緣進行檢測，然后需要對準橢圓點進行歸一化處理：

經過本算法處理后，可以得到由一系列連續的點組成一個橢圓。對參數進行反歸一化處理后可以得到各參數在絕對坐標系中的坐標值。

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

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

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

經過計算，含歸一化的最小二乘擬合算法對本文中給定的二值圖擬合的不確定度的大小如圖2所示。圖2中，橫坐標表示了點的編號，在這里共選取了82個點。縱坐標表示了產生的不確定度的大小，其含義為觀測點與擬合出的橢圓邊界的幾何距離，當點位于擬合橢圓之內時，距離為負；而當點位于擬合橢圓以外時，則距離為正。

圖2 歸一化最小二乘算法擬合結果的誤差及標準差分布圖

2.2 實驗對比

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

表2 最小二乘算法擬合結果

通過對比可以發現：兩種方法在長短軸的差別較大，由于擬合偏差不太大，所以也用其擬合不確定度來評價，其不確定度大小如圖3所示。圖3中，橫坐標表示點的編號，在這里共選取了82個點。縱坐標表示產生的不確定度的大小，其含義為觀測點到擬合出的橢圓邊界的幾何距離，當點位于擬合橢圓之內時，距離為負；而當點位于擬合橢圓以外時，則距離為正。

圖3 最小二乘算法擬合結果的誤差及標準差分布圖

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

3 結束語

由于傳統最小二乘法把所有樣本點都近似為準確值，因此擬合出的橢圓誤差比較大。為了提高橢圓擬合的精度，本文利用歸一化處理對傳統的最小二乘擬合算法進行了改進。經過兩種方法對比，本文中的算法在求取最優橢圓的過程中能夠將雜質點的影響降低，提高準確度的同時也增強了系統的魯棒性。另外，不同點之間的貢獻度也得到了體現，因此可以減小可能帶來的偏差。本文當中的算法所需要的運行時間也較短，在樣本點為200～600個時，運算時間能夠控制在20 ms以內，因此完全能夠滿足實時系統要求。

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

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

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

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

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

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

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

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

［9］ 曹芳.計算機視覺中的各點異性回歸技術［D］.上海：上海海事大學，2004.

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

［11］ 來雪梅，王雪萍，張海燕.實驗數據的擬合及其不確定度表示［J］.中北大學學報：自然科學版，2009（5）：481－484.

［12］ 倪驍驊.形狀誤差測量結果不確定度的研究及應用［D］.合肥：合肥工業大學，2002.