王國(guó)華 趙春燕 彭能舜

摘要： 詳細(xì)介紹了仿射變換的特點(diǎn)?；谌蔷W(wǎng)的仿射變換方法的流程及優(yōu)點(diǎn)。該方法能夠較好地保證空間數(shù)據(jù)的質(zhì)量，尤其是能夠保留屬性要素和空間要素拓?fù)潢P(guān)系。

關(guān)鍵詞： 三角網(wǎng)；仿射變換；數(shù)據(jù)質(zhì)量；地理信息系統(tǒng)

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1006-8228（2012）04-18-03

Design of affine transform algorithm based on triangular networks

Wang Guohua1, Zhao Chunyan2, Peng Nengshun2

（1. Changsha Professional Training College of Aeronautics, ChangSha， Hunan 410124， China；

2. Central South University of Forestry &Technology）

Abstract： It is introduced in this paper the characteristics of affine transformation, based on triangular network procedure and advantages. This method can better guarantee the quality of spatial data, and especially preserve the topological relation of attribute elements and spatial elements.

Key words： triangular network； affine transformation； data quality； GIS

0 引言

數(shù)據(jù)采集是空間信息系統(tǒng)建設(shè)項(xiàng)目中最昂貴的部分，Blakeman、Morse和Hovery的研究結(jié)果表明，GIS中數(shù)據(jù)采集的費(fèi)用通常占總項(xiàng)目費(fèi)用的80%。

GIS的數(shù)據(jù)質(zhì)量問(wèn)題是學(xué)術(shù)界研究的熱點(diǎn)問(wèn)題[1]。GIS的數(shù)據(jù)質(zhì)量包括空間數(shù)據(jù)和屬性數(shù)據(jù)質(zhì)量。其中，引起空間數(shù)據(jù)質(zhì)量的原因較為復(fù)雜。為了保證空間數(shù)據(jù)質(zhì)量需要更多算法進(jìn)行數(shù)據(jù)變換，仿射變換是較常用的一種數(shù)據(jù)變換方式。本文基于三角網(wǎng)進(jìn)行仿射變換，以更進(jìn)一步提高數(shù)據(jù)變換精度。

1 仿射變換

1.1 單仿射變換

單仿射變換也就是基于三點(diǎn)的仿射變換。仿射變換是一種比較簡(jiǎn)單且有效的常用方法，其表達(dá)式如下[2]：

式中(x，y)表示變換前的坐標(biāo)點(diǎn)，（x'，y'）為變換后的坐標(biāo)點(diǎn)對(duì)，三對(duì)待定系數(shù)在坐標(biāo)系空間上的幾何意義為：a1，b2分別確定點(diǎn)(x,y)在X方向和Y方向上的縮放尺度,a2，b1確定旋轉(zhuǎn)尺度，a3，b3分別確定在X方向和Y方向上的平移大小。對(duì)于式中三對(duì)待定系數(shù)，只要知道不在同一直線上的三個(gè)控制點(diǎn)坐標(biāo)即可求得。實(shí)際應(yīng)用時(shí)，人們往往利用四個(gè)以上控制點(diǎn)坐標(biāo)和最小二乘方法求解變換系數(shù)，以提高變換精度。

仿射變換具有以下三個(gè)特點(diǎn)[3]：

① 直線變換后仍為直線；

② 平行線變換后仍為平行線，并保持簡(jiǎn)單的長(zhǎng)度比；

③ 不同方向上的長(zhǎng)度比發(fā)生變化。

在實(shí)際應(yīng)用中，僅僅通過(guò)圖廓的三個(gè)點(diǎn)進(jìn)行控制，往往會(huì)造成第四個(gè)點(diǎn)和其理論值不符，所以人們提出了基于四點(diǎn)的仿射變換，即雙仿射變換。

1.2 雙仿射變換

雙仿射變換實(shí)際上是由兩個(gè)仿射變換組成的（△ABC→△A'B'C'，△ACD→△A'C'D'，見(jiàn)圖1），它可以把任意指定的四邊形一對(duì)一地連續(xù)變換到另一個(gè)指定的四邊形，并能保持組成四邊形的兩個(gè)相鄰三角形的邊界拓?fù)湟恢滦訹4]。

該方法的特點(diǎn)是：每一個(gè)三角形的仿射變換都只利用了三角形三頂點(diǎn)的坐標(biāo)條件，故兩鄰接三角形公共邊界上的點(diǎn)，其變換的象是惟一的，跨接相鄰三角形的曲線不會(huì)出現(xiàn)跳躍現(xiàn)象。當(dāng)區(qū)域較大時(shí)，若將區(qū)域劃分成若干個(gè)較小的鄰接三角形，每個(gè)三角形分別采用仿射變換，則因各三角形鄰邊上變換的象是惟一的，故各三角形所覆蓋區(qū)域中的全部圖形都能拓?fù)涞刈儞Q到相應(yīng)的區(qū)域。該變換能以小區(qū)域內(nèi)簡(jiǎn)單變換模型解決大區(qū)域內(nèi)復(fù)雜圖形的變換，且十分穩(wěn)定和迅速。

該方法雖然保證了第四個(gè)點(diǎn)的精度，但是它只能把整個(gè)圖幅的誤差控制在兩個(gè)三角形內(nèi)，這顯然不能滿足糾正的精度要求。因此，我們提出了構(gòu)建三角網(wǎng)的仿射變換，將誤差盡可能地控制在較小的范圍內(nèi)。

圖1雙仿射變換

2 基于三角網(wǎng)的算法設(shè)計(jì)

雙仿射變換的最大特點(diǎn)就是它能保持圖形邊界的拓?fù)湟恢滦?。空間數(shù)據(jù)的誤差來(lái)源是多方面的，而且分布也是不均勻的。而雙仿射變換僅僅是將整個(gè)區(qū)域分為兩大塊，用不同的變換系數(shù)去糾正，比起單仿射變換，其糾正精度要高，但對(duì)于精度要求越來(lái)越高的GIS 系統(tǒng)而言，還是遠(yuǎn)遠(yuǎn)不夠的。

根據(jù)數(shù)據(jù)的相關(guān)性，一般情況下圖形中某一點(diǎn)的誤差與其附近控制點(diǎn)的誤差接近，離控制點(diǎn)距離越近影響越大，反之，影響越小[5]。因此，可以將這些控制點(diǎn)劃分成一塊塊小區(qū)域，使該區(qū)域的點(diǎn)僅受相應(yīng)區(qū)域上的控制點(diǎn)控制。這樣，通過(guò)附近的控制點(diǎn)就能很好地對(duì)區(qū)域內(nèi)的點(diǎn)進(jìn)行糾正。因此，在雙仿射變換的基礎(chǔ)上，利用其完好的拓?fù)湟恢滦?，本文提出了?gòu)造三角網(wǎng)的仿射變換。

一幅地圖上已知的控制點(diǎn)不止三個(gè)，我們可以選取足夠多的已知控制點(diǎn)，并使其盡可能均勻分布在整幅圖上。然后，將離散的控制點(diǎn)連線，構(gòu)筑成一個(gè)三角網(wǎng)，這樣每一個(gè)三角形就可以建立一個(gè)仿射變換，計(jì)算出自己的變換系數(shù)。當(dāng)進(jìn)行糾正時(shí)，先要判斷該對(duì)象所在的三角形，然后用該組變換系數(shù)進(jìn)行變換，處于三角網(wǎng)外的對(duì)象可以用圖廓點(diǎn)建立的仿射變換進(jìn)行變換，或進(jìn)行外推，用其最鄰近的三角形的系數(shù)進(jìn)行變換。因?yàn)橐环貓D上，每處的變形都是不一樣的，誤差也就有所不同。采用這種方法進(jìn)行糾正，可以將誤差控制在每一個(gè)三角形內(nèi)，在這小范圍內(nèi)可以近似地把各種誤差看作是均勻分布的，得出的變換系數(shù)會(huì)能很好地反映出此范圍的誤差情況，糾正的效果也就會(huì)很好。

2.1 算法流程圖

基于三角網(wǎng)的仿射變換算法的基本依據(jù)是：⑴誤差是不可避免的；⑵誤差是分布不均勻的。

給出以下該算法的主要步驟是。

①對(duì)糾正區(qū)域進(jìn)行分區(qū)：這部分主要是通過(guò)糾正區(qū)域的已知控制點(diǎn)，建立三角網(wǎng)進(jìn)行分區(qū)。

②計(jì)算小區(qū)域的糾正系數(shù)：仿射變換的糾正系數(shù)的求得需要3個(gè)控制點(diǎn)，可利用三角形的三個(gè)頂點(diǎn)計(jì)算得出。

③糾正對(duì)象與小區(qū)域匹配：每一個(gè)糾正對(duì)象要與三角網(wǎng)格匹配，判斷每一個(gè)糾正對(duì)象到底屬于哪一個(gè)三角網(wǎng)格。

④糾正每一個(gè)對(duì)象：利用相應(yīng)的糾正系數(shù)進(jìn)行糾正，并重畫(huà)圖形。

算法的流程圖如圖2所示。

在基于三角網(wǎng)的仿射變換中，三角網(wǎng)的構(gòu)建是最關(guān)鍵的?？稍谄矫嫔险乙恍╇x散點(diǎn)，將其中最靠近的三點(diǎn)連成三角形，從而構(gòu)成三角形網(wǎng)。需要自動(dòng)聯(lián)結(jié)三角網(wǎng)時(shí)，應(yīng)盡可能地確保每個(gè)三角形是銳角三角形或邊長(zhǎng)近似相等，已獲得最佳效果。

建立三角網(wǎng)的基本步驟：以確定第一個(gè)三角形，到三角形的擴(kuò)展。算法流程圖如圖3。

[在圖上選取控制點(diǎn)且盡可能分布均勻][構(gòu)建三角網(wǎng)][計(jì)算機(jī)各三角形的仿射變換參數(shù)] [讀取元素判斷在第幾號(hào)三角形][用I號(hào)三角形變換參數(shù)進(jìn)行糾正][外推最近三角形，并進(jìn)行糾正][圖形重畫(huà)] [是否糾正完][圖形輸出]

圖2基于三角網(wǎng)的仿射變換流程

[輸入離散數(shù)據(jù)點(diǎn)并刪除其中的重復(fù)點(diǎn)][確定第一個(gè)三角形，將三個(gè)頂點(diǎn)分別送入ver(1,1),ver(1,2),ver(1,3)][L=1,K=1由K號(hào)三角形向外擴(kuò)展][取K號(hào)三角形的第一條邊往外擴(kuò)展，N1=ver(K,1),N2=ver(K,2),N3=ver(K,3)

即沿N1N2這條邊向外擴(kuò)展] [該邊是否已擴(kuò)展][計(jì)算直線方程判別系數(shù)

將N3代入方程，記下符號(hào)M1][L=L+1,Ver(L,3)=0][將離散點(diǎn)坐標(biāo)代入判別式，找到符號(hào)與M1不同，且與N1，N2形成夾角最大的點(diǎn)K1作為第L號(hào)三角形的第三個(gè)頂點(diǎn)，記Ver（L，3）=K] [Ver（L，3）=0] [L號(hào)三角形是否與前面三角形重復(fù)][寫(xiě)出ver(L,1),ver(L,2),ver(L,3)] [K號(hào)三角形是否擴(kuò)展完] [K

的下一條邊擴(kuò)展][是][是] [否][否] [是]

圖3三角網(wǎng)構(gòu)建算法

2.2 算法處理結(jié)果

實(shí)驗(yàn)數(shù)據(jù)是我國(guó)福建地區(qū)1：10萬(wàn)地形圖。

任選一幅地形圖掃描后，在CorelDRAW軟件中矢量化，將其導(dǎo)出為dxf格式的數(shù)據(jù)，轉(zhuǎn)入MapInfo，即可得到所需要的一幅矢量地形圖（見(jiàn)圖4）。

打開(kāi)一幅地形圖，運(yùn)行糾正程序AffineConvert.mbp，新建一個(gè)控制點(diǎn)文件，即生成一個(gè)新的圖層用于采集控制點(diǎn)，點(diǎn)擊菜單“由方里網(wǎng)構(gòu)建三角格網(wǎng)”，彈出一對(duì)話框，輸入該圖幅的西南角和東北角地理坐標(biāo)后，系統(tǒng)自動(dòng)計(jì)算出各個(gè)方里網(wǎng)點(diǎn)的理論坐標(biāo)值，然后進(jìn)行圖上坐標(biāo)的采集，完成控制點(diǎn)的選取，生成三角網(wǎng)。結(jié)果如圖5所示（為了清晰的顯示效果，將等高線隱藏）。

圖4變換前的地形圖

圖5生成的三角網(wǎng)

圖6變換前后的地形圖疊加效果

生成三角網(wǎng)后，就開(kāi)始進(jìn)行變換。將變換前后的圖疊加在一起，為了能清楚地顯示糾正前后的效果，插圖將等高線等地物隱藏。從圖上我們可以大體上看出，圖形進(jìn)行了X、Y方向的拉伸及旋轉(zhuǎn)變化。將圖上用黑框圈出的部分放大，可以看到詳細(xì)的糾正前后的變化（見(jiàn)圖6）。

基于三角網(wǎng)的仿射變換方法有以下優(yōu)點(diǎn)：

⑴ 經(jīng)過(guò)仿射變換后的數(shù)據(jù)可靠性高，數(shù)據(jù)不會(huì)丟失，而且空間要素之間的拓?fù)湟恢滦缘玫搅撕芎玫谋３諿6]；

⑵ 同一圖層上的不同的空間地物類型 (點(diǎn)、線或面狀 )在轉(zhuǎn)換過(guò)程中不存在GIS系統(tǒng)間數(shù)據(jù)格式轉(zhuǎn)換時(shí)所出現(xiàn)的數(shù)據(jù)丟失現(xiàn)象；

⑶ 轉(zhuǎn)換結(jié)果保留了原數(shù)據(jù)的屬性結(jié)構(gòu)，幾何屬性值隨圖形空間數(shù)據(jù)的變化而更新，其他屬性值則保留不變。

3 結(jié)束語(yǔ)

⑴ 基于三角網(wǎng)的仿射變換方法能夠較好地保證空間數(shù)據(jù)的質(zhì)量，尤其是保留了空間要素的拓?fù)潢P(guān)系和屬性要素；

⑵ 對(duì)于空間數(shù)據(jù)矢量化過(guò)程引起的誤差等數(shù)據(jù)質(zhì)量問(wèn)題，基于三角網(wǎng)的仿射變換方法有較好處理效果。

參考文獻(xiàn)：

[1] 江聰世.空間數(shù)據(jù)的誤差處理[M],科學(xué)出版社,2003.

[2] 林曉圓,趙健,謝瑜,等.圖像擬仿射變換的DWT水印算法[J].計(jì)算機(jī)工程與應(yīng)用,2011.47(12):84~89

[3] 朱桂斌,曹長(zhǎng)修.基于仿射變換的數(shù)字圖像置亂加密算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2003.15(6):21~25

[4] 何冰.基于仿射變換的圖像置亂改進(jìn)新算法[J].計(jì)算機(jī)與數(shù)字工程,2011.257(3):121~124

[5] 鄧曙光,劉剛.一種TIN生成算法的改進(jìn)與實(shí)現(xiàn)[J].計(jì)算機(jī)時(shí)代,2006.1:1~2

[6] 陳建勛,劉俊.山峽區(qū)間等雨量線生成算法的研究[J].計(jì)算機(jī)時(shí)代,2005.7:25~26