正交幾何橢圓擬合與代數擬合及橢圓定義的迭代擬合的比較分析

張彥軍

0 引言

數字圖像處理，又稱為計算機圖像處理，是指將圖像信號轉換成數字信號，并利用計算機對其進行處理的過程。也即圖像與圖像之間的數學變換，對圖像信息進行加工以滿足人的視覺心理或者應用需求的行為。

目前，天文學上用于擬合星像邊緣獲得其幾何中心位置的方法并不多，常用的有代數擬合方法[1]和橢圓定義的迭代擬合方法[2]。它們都具備其獨特之處，如代數方法，其執行效率很高，但當天文圖像邊緣檢測離散點偏離的比較大（例如大氣抖動、小區域的飽和等），其精確度就不夠理想。相比之下，橢圓定義的迭代擬合方法就具有很高的精度。因此，本課題的研究目的、意義就是應用邊緣提取算法對天文圖像的邊緣進行提取和處理的同時，考慮到一般擬合算法的缺陷（例如，可能剔除一些正常的邊緣點），充分地應用正交的概念及最小二乘（LS）原理和方法的優點，對橢圓進行正交幾何擬合，并對這些方法的擬合結果進行比較分析。理論上來說，正交概念可以提高其判斷邊緣點的標準，對邊緣點處理都是公平的，沒有進行強制加權，所以正交幾何橢圓擬合可以適當的彌補其它擬合算法的缺陷。

1 橢圓擬合相關算法

1.1 代數擬合方法

在文獻[1]中對代數擬合方法有詳細地描述。假設一般形式的橢圓方程為:

這里, 常數項已經歸一化為 1。顯然, 直接應用上述方程對邊緣檢測后的離散點進行最小二乘原理，就可以得到方程中的各系數。也即，對應于求目標函數

求最小值來確定各系數。再由極值原理，欲使 F 為最小，必有：

由此可得以下正規方程組,進而應用求解線性方程組的算法（如全主元高斯消去法），就可以得出方程系數A、B、C、D、E的值，從而可導出橢圓各估計參量：橢圓幾何中心xcyc,橢圓長軸的傾角θ，橢圓半長軸a和半短軸b.1.2橢圓定義的迭代擬合文獻[2]對橢圓定義的迭代擬合方法進行了闡述。在代數擬合方法的基礎上，假設橢圓上任一邊緣點為P(x,y)，橢圓兩焦點位置為F1(x1,y1)和F2(x2,y2)，焦距為 2c.而我們知道，理想橢圓上的點到兩焦點距離之和為常數(2a)，實際中，由于不可避免的誤差影響，理論上，對所有橢圓邊緣的離散點進行最小二乘擬合就可求得橢圓的5個待求參量的估計。

我們可以將代數擬合方法中求得的結果作為初始值,則觀測方程應用于所有邊緣的離散點進行最小二乘擬合,并逐步迭代可最終獲得所有待求參數 （x1,y1;x2,y2;a）。在迭代過程中我們可采用如下準則：

(1) 每次橢圓擬合后剔除殘差v的絕對值(σ為每一次迭代擬合后單位權標準誤差)的邊緣離散點。

(2) 如果相鄰兩次迭代擬合時每一橢圓焦點位置的偏差絕對值均不大于0. 001 像素,則迭代過程終止。

實際中, 我們可以發現，上述迭代通常只需 3～5次即可收斂。最后, 我們可以得到橢圓中心的測量位置

2 正交幾何橢圓擬合算法的原理及其思想

我們已經詳細介紹了幾種橢圓擬合方法，如代數擬合方法與橢圓定義的迭代擬合方法，但它們都相應地存在一些缺陷，如：代數擬合方法的精度不夠理想。而對于橢圓定義的迭代擬合方法，其邊緣點可能被不情愿地進行了加權，致使在迭代的過程中，剔除了一些正常的邊緣點，從而影響到橢圓中心定位的精度。針對以上問題，將闡述一種嚴格的、健壯的橢圓幾何擬合無參算法 正交幾何擬合算法。此算法是基于通過給定點到符合其幾何特征的相關點的坐標描述，此時，從給定點到幾何特征擬合點之間的連線是最短的。理論上，正交幾何擬合方法，充分應用正交的概念和最小二乘原理，克服了以上各方法的缺點，從而期望得到更好的精度與執行效率。

對于正交幾何擬合方法，在Ahn等人的文獻[3]中有詳細描述，在此，對其主要內容做個集中說明。在橢圓的幾何擬合中，橢圓的擬合相關點只是通過正交關聯條件表示出。當給定點的幾何特征相關點顯式或隱式得知時，都可以得出在這些點的Jacob矩陣，且可以應用非線性最小二乘迭代方法解之。

2.1 非線性最小二乘擬合

假定待測量a（a1, ...,aq）和觀測量X（X1,...Xp）(p≥q)的關系如下：

其中，F表示為a的非線性可連續微分的觀測函數向量，e表示為零平均值誤差向量。X對a的非線性最小二乘估計就必須最小化其性能因子，表示如下：

2.2 橢圓的正交幾何擬合

對于橢圓，在一個平面上，可以用以下5個參數唯一的表示 它：中心坐標Xc,Yc， 半軸長a,b(a≥b), 和傾角α(-π/2 < α≤π/2)。

由于橢圓存在一旋轉角α，在此方法中引入了一個臨時坐標系xy，其坐標系旋轉角也為α。對于橢圓擬合，引入臨時坐標系與正交相'關條件一樣，都是為了得到給定點在原來橢圓上相關點Xi的Jacob矩陣。

引入坐標系xy和坐標系XY之間的變換關系表示為：

3 正交幾何橢圓擬合、代數擬合及橢圓定義的迭代擬合實例分析比較

在文獻[3]中對正交幾何擬合算法進行了評估，對于給定的同一組初始值，Gander等人的算法[4]需要經過71次迭代后，精度可以達到 1.1×10-6，而正交幾何擬合方法僅需要21次。并且由于圓幾何擬合的結果可以作為正并幾何擬合的初始值，但不能作為Gander算法的合理初始值。這些充分地說明了正交幾何擬合方法的健壯性與穩定性。下面通過將此方法與天文圖像定位現有擬合方法（代數擬合方法與橢圓定義的迭代擬合方法）做分析比較，以此來說明此方法的可行性與實用性。為方便起見，取定橢圓上均勻分布的12個點，并假設各參數的預設值為：

其12個點在橢圓上的分布圖，如圖1所示：

為了能更全面的比較與分析，我們將分以下7種情況進行考慮：

取定橢圓上全部12個點。(如圖1)

圖1 均勻分布12點橢圓

取定橢圓上半部分7個點。(如圖2a)

圖2a

取定橢圓下半部分7個點。(如圖2b)

圖2b

取定橢圓左半部分7個點。(如圖2c)

圖2c

取定橢圓右半部分7個點。(如圖2d)

圖2d

取定橢圓x軸左右兩邊附近3點共6個點。(如圖2e)

圖2e

取定橢圓y軸上下兩邊附近3點共6個點。(如圖2f)

圖2f

當取定的是橢圓上點，而未加任何噪聲時（也即沒有任何偏差的情況），通過實驗可以知道，不管是代數擬合方法，橢圓定義的迭代擬合方法，還是正交幾何擬合方法，以上各種方法的誤差都精確為0，這也符合了理論上的推導。

為了便于比較，下一步就為它們增加噪聲，在此選定正態分布的隨機噪聲。其均差μ=0，方差σ=1.5，且設定噪聲范圍為（-0.5～0.5）。正態分布的隨機噪聲可參考文獻[6]。

當給這些觀測點分別增加隨機噪聲后，可得到以上 7種情況的實驗結果數據表：

表1 橢圓上均勻分布的12個點

表2 橢圓上半部分的7個點

表3 橢圓下半部分的7個點

橢圓 方法 定義 擬合Xc 6.07 0.07 6.06 0.06 6.06 0.06 Yc 5.05 0.05 5.05 0.05 5.06 0.06 a 10.01 0.01 9.99 0.01 10.00 0.00 θ 0.62 0.10 0.61 0.09 0.61 0.09 b 7.74 0.26 7.75 0.25 7.75 0.25迭代次數 3 3

表4 橢圓左半部分的7個點

表5 橢圓右半部分的7個點

表6 橢圓x軸左右兩邊附近3點共6個點

表7 橢圓y軸左右兩邊附近3點共6個點

其中，由于橢圓定義的迭代擬合和正交幾何擬合方法，都是在代數擬合方法基礎上進行處理的，將代數擬合的結果作為其迭代的初始值，因此，它們只需要經過不到3次的迭代就可以達到所要求的精度（即相鄰兩次迭代擬合時每一橢圓焦點位置的偏差絕對值均不大于0.001像素）。通過對上面數據表的比較，可以發現，代數擬合方法、橢圓定義的迭代擬合方法、正交幾何擬合方法對橢圓擬合的精度都較好，誤差也并不是很大。究其原因，可能是由于所選觀測點是均勻分布的，且增加的噪聲也是均勻的。但相對來說，正交幾何擬合方法的結果更好些，其迭代次數也要少些。因此，可以增加觀測點個數、增大隨機噪聲及增大觀測點分布的隨機性。取觀測點個數n=20，各參數的預設值為a=10，b=8，xc=6，yc=5，θ=π/10≈0.31415，同時增大隨機噪聲范圍為（-2.5～2.5），考慮第6種情況對以上3種方法進行比較。可以得到以下的數據，如表8所示：

表8 橢圓x軸左右兩邊附近5點共10個點

從上表中可以發現，相比橢圓定義的迭代擬合，正交幾何擬合要理想得多，其迭代次數也更少。而對于代數方法，其結果似乎更理想，但代數方法的思想是一次性定位各參數，從理論上，如果偏差達到一定域值時，其精度肯定是達不到的。當再一次把噪聲增大些，如（-5～5）或者更大時，橢圓定義的迭代擬合有時會出現發散的情況，而正交幾何擬合方法則不會。因此正交幾何擬合方法是非常健壯與穩定的，也是可行的。

5 總結

在一幅天文圖像中，存在著大量的信息數據，需要從圖像中獲取出這些信息數據，并對它們進行處理，因此就要求具有很高的執行效率和精度。所以，就可以放心的將正交幾何擬合方法應用到天文圖像中去。

[1]Stone R.C., Digital centering algorithms for the sun,moon, and planets,[j]AJ. , 1990, Vol99, No1: 424-430.

[2]彭青玉, 木星土星邊緣的橢圓擬合,[j]云南天文臺臺刊, 2003, No4: 43-48.

[3]Ahn S.J., Rauh W., Warnecke H., et al. Least-square orthogonal distances fitting of circle, sphere, ellipse, hyperbola, and parabola.[j]Pattern Recognition, 2001,Vol34: 2283-2303.

[4]Gander W., Golub G.H., Strebel R., Least-squares fitting of circles and ellipses,[j]BIT, 1994, No34: 558-578.

[5]H., Orthogonal distance fitting by circles and ellipses with given area, Computing.[j]Stat., 1997, No12:343-354.

[6]張圣華編著, 《C語言數值算法》,[M]北京，海洋出版社, 1993-8.