基于三角網(wǎng)的仿射變換算法設(shè)計

王國華 趙春燕 彭能舜

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

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

中圖分類號：TP391文獻(xiàn)標(biāo)識碼：A文章編號：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è)項目中最昂貴的部分，Blakeman、Morse和Hovery的研究結(jié)果表明，GIS中數(shù)據(jù)采集的費用通常占總項目費用的80%。

GIS的數(shù)據(jù)質(zhì)量問題是學(xué)術(shù)界研究的熱點問題[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 單仿射變換

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

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

仿射變換具有以下三個特點[3]：

① 直線變換后仍為直線；

② 平行線變換后仍為平行線，并保持簡單的長度比；

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

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

1.2 雙仿射變換

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

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

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

圖1雙仿射變換

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

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

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

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

2.1 算法流程圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 算法處理結(jié)果

實驗數(shù)據(jù)是我國福建地區(qū)1：10萬地形圖。

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

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

圖4變換前的地形圖

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

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

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

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

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

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

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

3 結(jié)束語

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

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

參考文獻(xiàn)：

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

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

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

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

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

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