WEI Zhiwei, GUO Qingsheng, CHENG Lu, et al. Shape similarity measurement based on DNA alignment for buildings with multiple orthogonal features[J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(12): 1683-1693. DOI: 10.11947/j.AGCS.2021.20200227
阅读全文：http://xb.sinomaps.com/article/2021/1001-1595/2021-12-1683.htm 引 言矢量图形之间的形状相似性计算是矢量图形匹配、分类和查询的基础[1]，已广泛应用于GIS领域，如基于图形相似性的同名实体匹配[2]、基于模板的居民地化简[3]和基于图形形状的空间查询[4-5]等。建筑物是矢量地图的基础地理要素之一，其形状相似性计算对建筑物图形数据处理具有重要意义。 图形形状相似性计算有赖于对图形形状的定量描述，如基于图形轮廓，可以用傅里叶级数拟合图形轮廓[6-7]、用曲率尺度空间表达图形轮廓的曲率变化[8]、用序列编码图形轮廓的局部特征[1, 9]等；基于图形区域，有基于矩的形状描述方法[10]，也可以描述图形的面积、延展度[11]等；基于图形结构，可以用骨架线作为图形的结构化表达[12]。其中，用序列编码图形轮廓的局部特征，能较好地分析图形的轮廓形态；同时，匹配序列中基础元素度量图形间形状相似性较为形象直观，是矢量图形形状相似性计算常采用的方法[1]。用序列编码图形需确定编码的基础元素，并描述基础元素的特征。如基于特征点编码图形，可以描述特征点的角度、相对于邻近点的可变形势、邻近点相对于该点的切线距离函数等[13-15]；基于边编码图形，可以描述边的方向、长度等[16]；基于弧段编码图形，可以描述弧段的弓高弦长比、弧长弦长比等[17]。但是，建筑物图形通常相对简单，节点较少，基于特征点或边编码的图形相似结果离散程度高、区分度小。另外，建筑物多具有直角表达的形态特征，即几何转折明显且无连续弯曲，不适宜用弧段编码建筑物图形。 DNA序列是生物信息学研究的重要对象，有成熟的计算DNA序列间相似性的方法，如经典的NW算法和SW算法[18]。因此，本文充分考虑建筑物图形多直角表达的形态特征，将建筑物图形编码成类似DNA的序列，利用NW算法和SW算法计算建筑物图形编码序列间相似程度。 1 DNA序列比对的NW算法和SW算法DNA序列比对是生物信息学中基因组测序的关键技术之一，通过匹配DNA序列中碱基获取不同DNA序列间相似程度[18]。其中，NW算法和SW算法是DNA序列比对时常用的两种基于动态规划原理的优化方法：NW算法旨在找到两序列在全局上的最佳匹配，可获取两序列比对的全局最大相似性(GsF)；SW算法旨在找到两序列相似性最大的片段，可获取两序列比对的局部最大相似性(LsF)[18]。 首先，DNA序列比对需匹配DNA序列中碱基。依据DNA在自然界的复制规律，DNA中碱基存在匹配(match)、误匹配(mismatch)和空缺(gap)3种匹配关系[18]，定义见表 1。例如，给定DNA序列Qm={A, G, C, A, C, T}，Qn={A, G, T, A, T}，比对序列Qm、Qn可能存在如表 1的匹配关系；其中，匹配对(A, A)、(G, G)、(A, A)、(T, T)为match关系，(C, T)为mismatch关系，(C, -)为gap关系。 表 1 DNA序列比对举例 Tab. 1 An example for pairwise DNA sequence alignments
表选项 在AE10.2基础上利用C#语言二次开发实现本文方法，试验平台为一台CPU为Intel(R) Core(TM) i5-8265U CPU @1.60 GHz、内存为8 GB、操作系统为Windows 10(64位)的计算机。试验参数设置如下：式(5)中取w1=0.8、w2=0.2；式(6)中取d=-0.8，取e=-0.5。 依据形状数据库中建筑物(Bi)与典型建筑物图形(T1-T6)的形状相似性(GLs)，确定Bi最相似的典型建筑物(GLs越大表示图形间形状越相似)，并与人的视觉认知进行比对，结果统计见表 5。其中，tp表示结果中与人视觉感知一致的建筑物数目，fp表示结果中不被认为是视觉感知相似的建筑物数目，fn表示结果中遗漏的与人视觉感知相似的建筑物数目。由表 5可知，依据GLs正确识别177个，错误识别17个，识别准确率为91.2%。其中，针对不同类型的典型建筑物图形，识别准确率均达到80.8%以上，且对于阶梯形(T5)和十字形(T6)两类典型建筑物，准确率均达到100%。试验结果一定程度上说明，本文方法在基于形状的建筑物图形检索与匹配上具有较好的性能。 表 5 基于形状的建筑物空间查询结果 Tab. 5 The results of shape query based on proposed approach
tp
fp
fn
查全率=tp/(tp+fp)/(%)
查准率=tp/(tp+fn)/(%)
方形(T1)
29
1
1
96.7
96.7
L形(T2)
42
10
10
80.8
80.8
T形(T3)
18
3
3
85.7
85.7
C形(T4)
44
3
3
93.6
93.6
阶梯形(T5)
29
0
0
100
100
十字形(T6)
15
0
0
100
100
合计
177
17
17
91.2
91.2
表选项 3.2 讨论 3.2.1 方法对比 为验证本文方法的有效性，分别基于转角函数(Ts)[9]和多级弦长函数的傅里叶形状描述子(Fs)[7]计算了建筑物间形状相似性，并与本文方法进行对比，结果见表 6。其中，基于转角函数计算图形间形状相似性对于起始点的选择较为敏感，本文基于转角函数(Ts)计算建筑物间形状相似性时也参考了文献[3]的策略。不同方法的试验耗时为：基于GLs耗时为9.73 s，基于Ts耗时为3.31 s，基于Fs耗时为0.48 s。 表 6 基于Ts和Fs的建筑物空间查询结果 Tab. 6 The results of shape query based on Ts and Fs
tp
fp
fn
查全率=tp/(tp+fp)/(%)
查准率=tp/(tp+fn)/(%)
方形(T1)
基于Ts
28
2
2
93.3
93.3
基于Fs
27
3
3
90.0
90.0
L形(T2)
基于Ts
28
24
24
53.8
53.8
基于Fs
8
44
44
15.4
15.4
T形(T3)
基于Ts
12
9
9
57.1
57.1
基于Fs
13
8
8
61.9
61.9
C形(T4)
基于Ts
37
10
10
78.7
78.7
基于Fs
26
21
21
55.3
55.3
阶梯形(T5)
基于Ts
4
25
25
13.8
13.8
基于Fs
21
8
8
72.4
72.4
十字形(T6)
基于Ts
7
8
8
46.7
46.7
基于Fs
5
10
10
33.3
33.3
合计
基于Ts
116
78
78
59.8
59.8
基于Fs
100
94
94
51.5
51.5
表选项 对比表 5和表 6可知，基于本文方法(GLs)耗时最大，但是其准确率也最高，均明显高于基于Ts的识别准确率(59.8%)和基于Fs的识别准确率(51.5%)；基于Fs的耗时最小，但是其识别准确率(51.5%)也最低。同时，基于Ts在识别阶梯形(T5)和十字形(T6)建筑物的准确率为13.8%和46.7%；基于Fs在识别L形(T2)和十字形(T6)建筑物的准确率为15.4%和33.3%；均低于50%，准确率较低。 同时，选择3个典型建筑物图形对比分析3种不同方法，结果见表 7。对于建筑物1，基于GLs和Fs均获得了与视觉认知一致的结果，而基于Ts获得的结果与视觉认知不一致，这是因为Ts相对于GLs没有有效考虑到连续直角构成的特殊结构，这些特殊结构在识别建筑物图形时具有较明显的视觉含义[23]。对于建筑物2，基于GLs获得了与视觉认知一致的结果，而基于Ts和Fs获得的结果均与视觉认知不一致，这是因为Ts相对于GLs在对比局部结构时，没有有效考虑到局部结构比对时可能存在的gap情况。Fs由于是基于图形轮廓从整体上利用傅里叶描述子表达图形形状，当图形间复杂程度接近时Fs相对不敏感，即表 7中建筑物2与各模板相似程度均较大。同时，Fs无法有效顾及建筑物图形多直角表达的形态特征[3]。对于建筑物3，基于Fs获得了与视觉认知一致的结果，而基于Ts和GLs获得的结果均与视觉认知不一致，这是因为基于GLs的识别是以比对连续直角构成的特殊结构组成的序列为基础，若建筑物不具备多直角表达的形态特征，且两建筑物复杂程度差异过大时，GLs往往取值较低，见表 7。因此，GLs相比于Fs更适宜多直角表达的简单图形间的形状相似性计算。其中，前文对Ordnance Survey开源提供的制图比例尺1∶10 000的街道层次地图中765 961个建筑物图形外轮廓角度特征进行统计分析显示，其中直角占比为96.06%，呈现出明显的多直角表达形态特征，因而，建筑物形状相似性计算较适宜使用GLs。而Fs则相对更适宜非多直角表达的复杂图形间的形状相似性计算，如面状湖泊、河流等。 表 7 典型建筑物分析 Tab. 7 Analysis for typical building
