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

張彥軍

0 引言

數(shù)字圖像處理，又稱為計(jì)算機(jī)圖像處理，是指將圖像信號(hào)轉(zhuǎn)換成數(shù)字信號(hào)，并利用計(jì)算機(jī)對(duì)其進(jìn)行處理的過(guò)程。也即圖像與圖像之間的數(shù)學(xué)變換，對(duì)圖像信息進(jìn)行加工以滿足人的視覺(jué)心理或者應(yīng)用需求的行為。

目前，天文學(xué)上用于擬合星像邊緣獲得其幾何中心位置的方法并不多，常用的有代數(shù)擬合方法[1]和橢圓定義的迭代擬合方法[2]。它們都具備其獨(dú)特之處，如代數(shù)方法，其執(zhí)行效率很高，但當(dāng)天文圖像邊緣檢測(cè)離散點(diǎn)偏離的比較大（例如大氣抖動(dòng)、小區(qū)域的飽和等），其精確度就不夠理想。相比之下，橢圓定義的迭代擬合方法就具有很高的精度。因此，本課題的研究目的、意義就是應(yīng)用邊緣提取算法對(duì)天文圖像的邊緣進(jìn)行提取和處理的同時(shí)，考慮到一般擬合算法的缺陷（例如，可能剔除一些正常的邊緣點(diǎn)），充分地應(yīng)用正交的概念及最小二乘（LS）原理和方法的優(yōu)點(diǎn)，對(duì)橢圓進(jìn)行正交幾何擬合，并對(duì)這些方法的擬合結(jié)果進(jìn)行比較分析。理論上來(lái)說(shuō)，正交概念可以提高其判斷邊緣點(diǎn)的標(biāo)準(zhǔn)，對(duì)邊緣點(diǎn)處理都是公平的，沒(méi)有進(jìn)行強(qiáng)制加權(quán)，所以正交幾何橢圓擬合可以適當(dāng)?shù)膹浹a(bǔ)其它擬合算法的缺陷。

1 橢圓擬合相關(guān)算法

1.1 代數(shù)擬合方法

在文獻(xiàn)[1]中對(duì)代數(shù)擬合方法有詳細(xì)地描述。假設(shè)一般形式的橢圓方程為:

這里, 常數(shù)項(xiàng)已經(jīng)歸一化為 1。顯然, 直接應(yīng)用上述方程對(duì)邊緣檢測(cè)后的離散點(diǎn)進(jìn)行最小二乘原理，就可以得到方程中的各系數(shù)。也即，對(duì)應(yīng)于求目標(biāo)函數(shù)

求最小值來(lái)確定各系數(shù)。再由極值原理，欲使 F 為最小，必有：

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

我們可以將代數(shù)擬合方法中求得的結(jié)果作為初始值,則觀測(cè)方程應(yīng)用于所有邊緣的離散點(diǎn)進(jìn)行最小二乘擬合,并逐步迭代可最終獲得所有待求參數(shù) （x1,y1;x2,y2;a）。在迭代過(guò)程中我們可采用如下準(zhǔn)則：

(1) 每次橢圓擬合后剔除殘差v的絕對(duì)值(σ為每一次迭代擬合后單位權(quán)標(biāo)準(zhǔn)誤差)的邊緣離散點(diǎn)。

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

實(shí)際中, 我們可以發(fā)現(xiàn)，上述迭代通常只需 3～5次即可收斂。最后, 我們可以得到橢圓中心的測(cè)量位置

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

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

對(duì)于正交幾何擬合方法，在Ahn等人的文獻(xiàn)[3]中有詳細(xì)描述，在此，對(duì)其主要內(nèi)容做個(gè)集中說(shuō)明。在橢圓的幾何擬合中，橢圓的擬合相關(guān)點(diǎn)只是通過(guò)正交關(guān)聯(lián)條件表示出。當(dāng)給定點(diǎn)的幾何特征相關(guān)點(diǎn)顯式或隱式得知時(shí)，都可以得出在這些點(diǎn)的Jacob矩陣，且可以應(yīng)用非線性最小二乘迭代方法解之。

2.1 非線性最小二乘擬合

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

其中，F(xiàn)表示為a的非線性可連續(xù)微分的觀測(cè)函數(shù)向量，e表示為零平均值誤差向量。X對(duì)a的非線性最小二乘估計(jì)就必須最小化其性能因子，表示如下：

2.2 橢圓的正交幾何擬合

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

由于橢圓存在一旋轉(zhuǎn)角α，在此方法中引入了一個(gè)臨時(shí)坐標(biāo)系xy，其坐標(biāo)系旋轉(zhuǎn)角也為α。對(duì)于橢圓擬合，引入臨時(shí)坐標(biāo)系與正交相'關(guān)條件一樣，都是為了得到給定點(diǎn)在原來(lái)橢圓上相關(guān)點(diǎn)Xi的Jacob矩陣。

引入坐標(biāo)系xy和坐標(biāo)系XY之間的變換關(guān)系表示為：

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

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

其12個(gè)點(diǎn)在橢圓上的分布圖，如圖1所示：

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

取定橢圓上全部12個(gè)點(diǎn)。(如圖1)

圖1 均勻分布12點(diǎn)橢圓

取定橢圓上半部分7個(gè)點(diǎn)。(如圖2a)

圖2a

取定橢圓下半部分7個(gè)點(diǎn)。(如圖2b)

圖2b

取定橢圓左半部分7個(gè)點(diǎn)。(如圖2c)

圖2c

取定橢圓右半部分7個(gè)點(diǎn)。(如圖2d)

圖2d

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

圖2e

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

圖2f

當(dāng)取定的是橢圓上點(diǎn)，而未加任何噪聲時(shí)（也即沒(méi)有任何偏差的情況），通過(guò)實(shí)驗(yàn)可以知道，不管是代數(shù)擬合方法，橢圓定義的迭代擬合方法，還是正交幾何擬合方法，以上各種方法的誤差都精確為0，這也符合了理論上的推導(dǎo)。

為了便于比較，下一步就為它們?cè)黾釉肼?，在此選定正態(tài)分布的隨機(jī)噪聲。其均差μ=0，方差σ=1.5，且設(shè)定噪聲范圍為（-0.5～0.5）。正態(tài)分布的隨機(jī)噪聲可參考文獻(xiàn)[6]。

當(dāng)給這些觀測(cè)點(diǎn)分別增加隨機(jī)噪聲后，可得到以上 7種情況的實(shí)驗(yàn)結(jié)果數(shù)據(jù)表：

表1 橢圓上均勻分布的12個(gè)點(diǎn)

表2 橢圓上半部分的7個(gè)點(diǎn)

表3 橢圓下半部分的7個(gè)點(diǎn)

橢圓 方法 定義 擬合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迭代次數(shù) 3 3

表4 橢圓左半部分的7個(gè)點(diǎn)

表5 橢圓右半部分的7個(gè)點(diǎn)

表6 橢圓x軸左右兩邊附近3點(diǎn)共6個(gè)點(diǎn)

表7 橢圓y軸左右兩邊附近3點(diǎn)共6個(gè)點(diǎn)

其中，由于橢圓定義的迭代擬合和正交幾何擬合方法，都是在代數(shù)擬合方法基礎(chǔ)上進(jìn)行處理的，將代數(shù)擬合的結(jié)果作為其迭代的初始值，因此，它們只需要經(jīng)過(guò)不到3次的迭代就可以達(dá)到所要求的精度（即相鄰兩次迭代擬合時(shí)每一橢圓焦點(diǎn)位置的偏差絕對(duì)值均不大于0.001像素）。通過(guò)對(duì)上面數(shù)據(jù)表的比較，可以發(fā)現(xiàn)，代數(shù)擬合方法、橢圓定義的迭代擬合方法、正交幾何擬合方法對(duì)橢圓擬合的精度都較好，誤差也并不是很大。究其原因，可能是由于所選觀測(cè)點(diǎn)是均勻分布的，且增加的噪聲也是均勻的。但相對(duì)來(lái)說(shuō)，正交幾何擬合方法的結(jié)果更好些，其迭代次數(shù)也要少些。因此，可以增加觀測(cè)點(diǎn)個(gè)數(shù)、增大隨機(jī)噪聲及增大觀測(cè)點(diǎn)分布的隨機(jī)性。取觀測(cè)點(diǎn)個(gè)數(shù)n=20，各參數(shù)的預(yù)設(shè)值為a=10，b=8，xc=6，yc=5，θ=π/10≈0.31415，同時(shí)增大隨機(jī)噪聲范圍為（-2.5～2.5），考慮第6種情況對(duì)以上3種方法進(jìn)行比較?？梢缘玫揭韵碌臄?shù)據(jù)，如表8所示：

表8 橢圓x軸左右兩邊附近5點(diǎn)共10個(gè)點(diǎn)

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

5 總結(jié)

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

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

[2]彭青玉, 木星土星邊緣的橢圓擬合,[j]云南天文臺(tái)臺(tái)刊, 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語(yǔ)言數(shù)值算法》,[M]北京，海洋出版社, 1993-8.