基于三角网的仿射变换算法设计

王国华 赵春燕 彭能舜

摘要： 详细介绍了仿射变换的特点。基于三角网的仿射变换方法的流程及优点。该方法能够较好地保证空间数据的质量，尤其是能够保留属性要素和空间要素拓扑关系。

关键词： 三角网；仿射变换；数据质量；地理信息系统

中图分类号：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