基于三角網的仿射變換算法設計

王國華 趙春燕 彭能舜

摘要： 詳細介紹了仿射變換的特點。基于三角網的仿射變換方法的流程及優點。該方法能夠較好地保證空間數據的質量，尤其是能夠保留屬性要素和空間要素拓撲關系。

關鍵詞： 三角網；仿射變換；數據質量；地理信息系統

中圖分類號：TP391文獻標識碼：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 引言

數據采集是空間信息系統建設項目中最昂貴的部分，Blakeman、Morse和Hovery的研究結果表明，GIS中數據采集的費用通常占總項目費用的80%。

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

1 仿射變換

1.1 單仿射變換

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

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

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

① 直線變換后仍為直線；

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

③ 不同方向上的長度比發生變化。

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

1.2 雙仿射變換

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

該方法的特點是：每一個三角形的仿射變換都只利用了三角形三頂點的坐標條件，故兩鄰接三角形公共邊界上的點，其變換的象是惟一的，跨接相鄰三角形的曲線不會出現跳躍現象。當區域較大時，若將區域劃分成若干個較小的鄰接三角形，每個三角形分別采用仿射變換，則因各三角形鄰邊上變換的象是惟一的，故各三角形所覆蓋區域中的全部圖形都能拓撲地變換到相應的區域。該變換能以小區域內簡單變換模型解決大區域內復雜圖形的變換，且十分穩定和迅速。

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

圖1雙仿射變換

2 基于三角網的算法設計

雙仿射變換的最大特點就是它能保持圖形邊界的拓撲一致性。空間數據的誤差來源是多方面的，而且分布也是不均勻的。而雙仿射變換僅僅是將整個區域分為兩大塊，用不同的變換系數去糾正，比起單仿射變換，其糾正精度要高，但對于精度要求越來越高的GIS 系統而言，還是遠遠不夠的。

根據數據的相關性，一般情況下圖形中某一點的誤差與其附近控制點的誤差接近，離控制點距離越近影響越大，反之，影響越小[5]。因此，可以將這些控制點劃分成一塊塊小區域，使該區域的點僅受相應區域上的控制點控制。這樣，通過附近的控制點就能很好地對區域內的點進行糾正。因此，在雙仿射變換的基礎上，利用其完好的拓撲一致性，本文提出了構造三角網的仿射變換。

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

2.1 算法流程圖

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

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

①對糾正區域進行分區：這部分主要是通過糾正區域的已知控制點，建立三角網進行分區。

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

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

④糾正每一個對象：利用相應的糾正系數進行糾正，并重畫圖形。

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

在基于三角網的仿射變換中，三角網的構建是最關鍵的。可在平面上找一些離散點，將其中最靠近的三點連成三角形，從而構成三角形網。需要自動聯結三角網時，應盡可能地確保每個三角形是銳角三角形或邊長近似相等，已獲得最佳效果。

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

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

圖2基于三角網的仿射變換流程

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

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

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

的下一條邊擴展][是][是] [否][否] [是]

圖3三角網構建算法

2.2 算法處理結果

實驗數據是我國福建地區1：10萬地形圖。

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

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

圖4變換前的地形圖

圖5生成的三角網

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

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

基于三角網的仿射變換方法有以下優點：

⑴ 經過仿射變換后的數據可靠性高，數據不會丟失，而且空間要素之間的拓撲一致性得到了很好的保持[6]；

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

⑶ 轉換結果保留了原數據的屬性結構，幾何屬性值隨圖形空間數據的變化而更新，其他屬性值則保留不變。

3 結束語

⑴ 基于三角網的仿射變換方法能夠較好地保證空間數據的質量，尤其是保留了空間要素的拓撲關系和屬性要素；

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

參考文獻：

[1] 江聰世.空間數據的誤差處理[M],科學出版社,2003.

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

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

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

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

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