基于最小二乘法橢圓擬合的改進型快速算法*

朱森榮 劉杰徽

（1.海軍工程大學(xué)兵器工程學(xué)院 武漢 430033）（2.重慶前衛(wèi)科技集團有限公司技術(shù)中心 重慶 401121）

1 引言

橢圓擬合在圖像識別、特征提取中有著特別重要的意義。而最小二乘法是數(shù)據(jù)擬合的最常用方法，受隨機噪聲的影響整體最小[1]，是電子羅盤校準(zhǔn)算法中應(yīng)用最常用的算法之一，廣泛應(yīng)用于航空、航天、航海、水中兵器、石油鉆井等領(lǐng)域[2]。

在實際應(yīng)用過程中往往通過大量的數(shù)據(jù)進行擬合，計算量偏大，而單片機的算力每秒只有幾萬次浮點運算能力，而橢圓擬合需要快速而且大量的浮點運算資源，如果需要在單片機上進行曲線擬合的話就會大大影響系統(tǒng)的性能，因而需要進一步研究快速算法，在計算資源嚴(yán)重缺乏的單片機上算法的簡化顯得尤為重要[3]。

本文給予最小二乘法進行了一些簡單的改進，引入樣本點分組原理，再對樣本點進行隨機抽取，并且通過Matlab仿真驗證可以一定程度上減少算法的復(fù)雜度，提升算法的實時性。

2 最小二乘橢圓擬合方法介紹

橢圓的代數(shù)表達式如下：

表達式中有5個未知數(shù)，分別為A、B、C、D、E。

最小二乘法是由最大似然法推出的一個最優(yōu)估計技術(shù)，它可使測量誤差的平方和最小，也就是所有離散點到曲線的代數(shù)誤差之和最小[4]，因此也被視為從一組測量值中求出一組未知量的最可信賴的方法之一[5]。

平面內(nèi)某點（x0，y0）到方程（fx，y）=0所代表曲線的代數(shù)距離就是f(x0，y0)，對離散樣本點進行最小二乘處理，即目標(biāo)函數(shù)如下

根據(jù)橢圓的幾何知識，可以計算出橢圓的五個參數(shù)：位置參數(shù)（θ，x0，y0）和形狀參數(shù)（a，b）。

算法步驟如下[6]：

1）在總的樣本空間隨機選取N個樣本點；

2）利用最小二乘法求解橢圓參數(shù)A、B、C、D、E；

3）計算所有樣本點的匹配度；

4）重復(fù)步驟1）～3）一定次數(shù)（根據(jù)樣本點個數(shù)、匹配精度和運行時間等綜合因素進行調(diào)整），選取最高匹配度的擬合參數(shù)。

3 改進型橢圓擬合方法

根據(jù)數(shù)據(jù)樣本每個點在橢圓上位置的不同對橢圓擬合參數(shù)估計的貢獻是不同的[7]，導(dǎo)致樣本點的選取對橢圓的擬合會產(chǎn)生一定的偏差，尤其是樣本點相對集中會使擬合結(jié)果的曲率和方向都明顯變化，使得匹配度大大下降，樣本點的選取成為了關(guān)鍵。

本方法在進行最小二乘法擬合之前在空間上對樣本進行若干個區(qū)域的均勻劃分（區(qū)域個數(shù)與單次擬合的樣本點的個數(shù)相同）。本文改進的最小二乘法也是在隨機N樣本點橢圓擬合的基礎(chǔ)上進行改進，其計算步驟如下。

1）根據(jù)曲線擬合所需的點數(shù)進行樣本點分區(qū)，均勻分成N個區(qū)域，如圖1所示。

圖1 樣本點分區(qū)

2）每個區(qū)域進行隨機選取樣本點，得到N個樣本點。

3）采用最小二乘法求解A、B、C、D、E個參數(shù)。

4）根據(jù)求解的橢圓參數(shù)求出橢圓的焦點坐標(biāo)F0（x0，y0），F(xiàn)1(x1，y1)和橢圓上的點到焦點F0，F(xiàn)1的距離之和L。

5）根據(jù)橢圓的定義，求解所有樣本點到焦點F1，F(xiàn)2的距離與L差的絕對值，與自定義的閾值進行比較，大于則判定為不匹配點，小于等于則判定為匹配點，得出這組參數(shù)的一個匹配百分比[8]。

6）重復(fù)2）～5）步驟一定次數(shù)（根據(jù)樣本點個數(shù)、匹配精度和運行時間等進行調(diào)整），選取匹配度最高的橢圓參數(shù)（A、B、C、D、E）。

4 仿真應(yīng)用結(jié)果分析

4.1 算法對對匹配度的影響

通過Matlab重復(fù)400次的仿真分析擬合結(jié)果來看，如圖2所示經(jīng)過本算法的改進高匹配度出現(xiàn)頻次明顯提高，最高匹配度存在一定程度的提升，滿足算法最基本的匹配度要求。

圖2 匹配度

4.2 匹配度的提升分析

由于樣本點是隨機取樣，匹配度波動很大，很難直觀的給出總體的評價。而移動平均法可以消除隨機波動的影響，顯示出匹配度的發(fā)展趨勢[9]，移動平均計算公式如下：

Ft為對下一個周期的匹配度；n為移動平均的周期個數(shù)；At-1為當(dāng)前匹配次數(shù)的匹配度；At-2，At-3和At-n表示前兩次、前三次直至前n次的匹配度值[10]；

在經(jīng)過20為周期的移動平均法計算[11]，如圖3所示，改進型最小二乘法擬合的系數(shù)匹配度整體上看明顯高于普通型。

圖3 均值匹配度

從本次仿真的結(jié)果來看，改進型最小二乘法在樣本點選取階段就可以一定程度排除匹配度較小的樣本點組合。在樣本點個數(shù)、匹配精度等條件相同的情況下，可以用較小的的擬合次數(shù)達到普通型的效果。

5 結(jié)語

普通型最小二乘法在樣本點選取時是隨機的，當(dāng)隨機的樣本點相對集中時，擬合的誤差就會相對較大，出現(xiàn)低匹配度的概率就會增加，浪費了算力資源。改進的最小二乘法恰好規(guī)避了這部分樣本點組合，增加了高匹配度擬合結(jié)果出現(xiàn)的概率，可以適當(dāng)減少重復(fù)擬合的次數(shù)，節(jié)省了算力資源，特別是在一些圖像識別領(lǐng)域兼顧了實時性和準(zhǔn)確性之間的矛盾[12]。