摘 要：形状识别是地图空间认知的重要内容之一，结合有效的形状特征向量提取方法和空间认知实验的神经网络方法是提高形状识别的有效途径。本文构建了一种融合了圆形度、偏心率和矩形度等宏观形状特征参量的傅里叶形状描述子作为形状特征向量的神经网络建筑多边形状识别器。首先，利用傅里叶变换和计算几何方法提取建筑多边形的傅里叶形状描述子和圆形度、偏心率和矩形度参量，并组成形状特征向量；然后，通过样本数据的训练实现了建筑多边形与形状模板之间匹配的神经网络识别器。结果表明，该方法相对以往的方法大幅度提高了精度(达到98.7%)，而且特征提取算法不受多边形点数不一致的限制。对武汉、郑州两大城市的真实建筑物数据进行形状识别，该方法具有较好的识别效果。
关键词:傅里叶形状描述子;神经网络;模板匹配;建筑多边形形状识别;
Fourier descriptor- based high-precision neural network building shape recognition
method
LIU Pengcheng
HUANG Xin MA Hongran
YANG Ming
Key Laboratory for Geographical Process Analysis & Simulation, Central China Normal University
School of Urban and Environmental sciences, Central China Normal University School of
Resource and Environment Sciences, Wuhan University
Abstract：
Shape recognition is one of the important contents of map spatial cognition, and neural network combined with spatial cognitive experiment and its effective shape feature vector extraction are effective ways to improve shape recognition. In this paper, a neural network building-polygon shape recognizer is constructed, which integrates the Fourier descriptors of macro shape parameters such as roundness, eccentricity and rectangularity as shape feature vectors. Firstly, the Fourier shape descriptors, circularity, eccentricity and rectangularity parameters of building polygons are extracted by Fourier transform and computational geometry methods, and the shape feature vectors are formed; Then, the neural network recognizer matching between building polygon and shape template is realized through the training of sample data. The results show that this method greatly improves the accuracy (98.7%) compared with the previous methods, and the feature extraction algorithm is not limited by the inconsistency of polygon points. The shape recognition of real building data in Wuhan and Zhengzhou is carried out, and its information entropy is calculated. This method has good recognition effect.
Keyword：
Fourier shape descriptor; neural network; shape temple match; building-polygon shape recognition;
引言
形状是物体最直观、有效且稳定的特征，是识别要素的重要途径，地图要素形状的描述和识别是地图空间认知的基本内容[1,2]，具有重要的应用价值。在地图综合领域，同一要素综合前后形状的相似性是评价综合算法优劣的一个重要指标。对建筑多边形形状的识别是近年来形状识别领域比较活跃的方向，相关应用包括建筑多边形的化简[3,4,5,6]、地图匹配[7]、变化检测等。建筑多边形作为人造要素，在地图的形态时常呈现出几种特定的模式，因而常常研究其与特定形状模板之间的匹配：如文献[3]针对丹麦的农村房屋特点,利用一系列的英文字母模板来替代相似的建筑多边形并制作示意性地图；文献[4,6]给出了构建形状模版的原则并利用形状模板的精确匹配进行建筑多边形的化简。形状相似性判断是跨尺度建筑多边形的匹配依据之一，文献[7]基于形状相似性进行跨尺度多边形的匹配，从而进行不同尺度下建筑多边形的溯源。形状相似性度量是建筑物多边形识别与匹配的重要依据，其计算主要包括两个步骤[8,9]：第一步是提取形状特征向量：圆形度、偏心率、矩形度等作为单一数值的几何形状特征无法对形状进行准确表达[10]，链码[11,12]、傅里叶形状描述子[1,13,14,15,16]、距离转角[17]、形状树[18]等形状特征以一维向量来描述二维形状，并能一定程度的还原形状，可以建立形状相似性的解析表达式，现已被广泛使用。第二步是设计计算模型：形状特征向量的欧氏距离和夹角距离方法常被采用[19,20]。文献[16]采用傅里叶形状描述子的欧氏距离度量建筑多边形形状相似性，并比较了欧氏距离法和转角函数法的适宜对象。
人对形状认知是大脑逻辑思维和形象思维的结合，任何模型的形状相似性的识别结果都需要通过人类的认知来检验。近年来兴起的深度学习方法结合了人类认知的非线型特点，已经逐步应用到地图要素形状识别领域，如文献[7]通过图卷积神经网络对建筑多边形形状相似性进行了有效的尝试，该方法在节点数量归一化处理以及节点属性计算过程的复杂度偏高。在形状识别的深度学习中，提取有效的形状特征向量是关键的一环，特征向量既不能太复杂，又要辨识度高。傅里叶形状描述子满足上述两个条件，而且其向量长度与建筑多边形点数无关，还可以根据精度需要进行调节；傅里叶形状描述子通过傅里叶变换实现形模互转，已有成熟的数学模型。考虑到傅里叶形状描述子在识别形状时容易受到局部形状的扰动，因而将圆形度、偏心度和矩形度三个宏观形状特征参量补充到形状特征向量中，建立神经网络模型，在有监督的学习训练下建立建筑多边形与形状模板的匹配。实验证明该方法相比现有的形状识别方法具有较高识别精度，且模型的复杂度低。
1 形状特征向量提取
1.1傅里叶形状描述子
建筑多边形是由一组首尾点重合的坐标串组成的闭合多边形。在平面直角坐标系中，在多边形的边界线上任取点P0(x0,y0)作为起点，再顺时针定义边界顶点P1，P2，……，PN，由此构成闭合建筑物边界轮廓（P0与PN重合）,如图1所示。
图中边界上任意点P的坐标值(X(s),Y(s))均可表达为起点P0到P点的边界总长度s的分段函数[21]，具体表达式为：
X(s)=xi+xi+1−xiSi+1−Si(s−Si)(1)
Y(s)=yi+yi+1−yiSi+1−Si(s−Si)(2)
其中，(xi,yi)为边界顶点Pi的坐标；Si为起点P0到边界顶点Pi的线段长度和；Si≤s≤Si+1；0≤i≤N−1；N为建筑物边界顶点个数。
将平面坐标系中的要素引入复平面中，可以得到点P在复数域的坐标表达式为：
P(s)=X(s)+j∙Y(s)(3)
其中j2=−1，显然函数P(s)为以建筑物周长L为周期的周期函数[21]，故可以使用傅里叶级数来表示：
P(s)=∑+∞n=−∞Fnej2nπsL=∑+∞n=−∞Fn(cos2nπsL+j∙sin2nπsL)(4)
各阶次傅里叶系数Fn的表达式为：
Fn=1L∑N−1i=0∫Si+1Si∙{xi+xi+1−xiSi+1−Si(s−Si)+j[yi+yi+1−yiSi+1−Si(s−Si)]}∙e−j2nπsLds(5)
傅里叶级数的各项系数Fn均为复数，取Fn的模向量构成傅里叶级数模向量F[22]，如式(6)。
F=(||F1||,||F2||,…,||Fn||,…)(6)
为了使傅里叶级数模向量F具有旋转、尺度和平移不变性，对其进行归一化处理，将模向量F中的每一项均除以第一项（系数F1的模）[22],考虑到处理后第一项的值均为1，则去除第1项后得到形状的傅里叶形状描述子，如公式（7）。
D=(||F2||||F1||,||F3||||F1||,…,||Fn||||F1||,…)=(d1,d2,…,dn,…)(7)
式（7）中，傅里叶形状描述子Ｄ的长度K趋于无限大，在形状识别中根据实际精度需要进行截断[21]。
1.2宏观形状特征参量
为降低局部形状扰动对傅里叶形状描述子在形状识别中的影响，将圆形度、偏心率和矩形度三个宏观形状特征参量的建筑多边形纳入到形状识别的特征向量，通过计算几何获取这些参数。
1）圆形度（Circularity）
圆形度反映物体接近圆形的程度，是无量纲的形状特征描述，使用多边形的面积S和周长P计算得到，计算公式如式 (8) 所示。
C=4πSP2(8)
式中C为圆形度，C∈(0,1]。在所有多边形中，圆的圆形度最大，值为1，正方形的圆形度为π/4。圆形度越接近于1，表明物体形状越接近于标准圆。
2）偏心率（Eccentricity）
偏心率又称为伸长度，用来反映多边形形状相对圆形的偏平程度（如图2）。偏心率有多种计算公式，本文采用多边形形状轮廓的最小外接矩形（MBR）的长度A和宽度B之比，计算公式如式(9)所示。E=AB(9)
式中E为偏心率，E∈[1,+∞) 。在所有多边形中，圆和正方形的偏心率最小，值为1，形状越偏平值越大。
3）矩形度（Rectangularity）
矩形度表示形状在其最小外接矩形中的填充程度,定义为物体的面积S0与物体最小外接矩形（MBR）的面积SR之比，计算公式如式 (10) 所示。
R=S0SR(10)
式中R为矩形度，R∈(0,1]，在所有多边形中，矩形的矩形度为1，圆形的矩形度为π/4，利用矩形度可以区分矩形、圆形和不规则形状。
2. 建筑多边形形状识别神经网络的构建
2.1特征向量长度设置
上节式（7）的傅里叶形状描述子是长度趋于无穷大的向量，其前面分量对应于低频信息，描述形状的轮廓信息，后面的分量对应于高频信息，描述形状的细节信息[23]。在形状度量中，可以根据实际精度需要保留傅里叶形状描述子前面一定长度的分量，舍弃后面的细节信息[24]。本文按照文献[16]的方法，通过傅里叶形状描述子还原的建筑多边形与原建筑物多边形的重叠度来确定傅里叶形状描述子的长度K。具体过程是：设原建筑多边形区域为CO，傅里叶形状描述子拟合区域为CF，CO和CF重叠区为Co∩F，定义傅里叶形状描述子的近似度（A_degree）为式(11)。
A_degree=2*Area(Co∩F)Area(Co)+Area(CF)(11)
式中Area(Co)、Area(CF)、Area(Co∩F)分别对应CO、CF、Co∩F的面积，A_degree∈(0,1], 其值越大傅里叶形状描述子的精度越高。随着K的增大，A_degree不断增大，拟合形状不断逼近原始要素。选择A_degree达到设定阈值（如0.98）所对应的傅里叶形状描述子为作为形状特征向量。图3是部分建筑多边形的傅里叶形状描述子的拟合实验，左边黑色的图形为原要素，蓝色部分为傅里叶形状描述子长度为K的拟合图形，红色为数字为傅里叶形状描述子的近似度，可以看出当K=50时，傅里叶形状描述子的近似度大于0.98，说明此时拟合的多边形形状已经按设定阈值还原了原要素。
本文所设计的神经网络输入的特征向量包含了长度为50的傅里叶形状描述子以及3个宏观形状特征参量，如图4所示。
2.2形状识别神经网络的设计
本文的目标是构建形状模板相似性识别的神经网络模型，其输入层为上节得到的形状特征向量，输出层采用one-hot编码，因而该模型的输入层神经元的个数为53，而输出层神经元的个数为建筑物形状模板的个数（本文为10）。神经网络模型的隐藏层的层数、各项参数，以及激活函数需经反复试验，以求最高的识别精度和收敛速度，最终构建了如图5所示的神经网络形状识别器，其包含1层输入层、4层隐藏层和1层输出层，输入层神经元的个数为53，中间3层隐藏层神经元的个数均为80，权重初始值使用标准差为2n−√的高斯分布（其中n为各层神经元的个数），ReLU函数为各层激活函数，使用Adam法对模型进行优化，交叉熵函数作为损失函数，学习率为0.01。使用softmax函数激活输出层，输出层的各位置的值分别对应被识别为各形状模板的概率，概率最大值对应索引作为最终预测结果。
3 建筑多边形的形状识别实验及实践应用
3.1形状识别实验及方法对比
本文使用文献[25]提供的已知正确标签值的5000个建筑物多边形数据作为实验数据，对数据进行旋转、镜像等操作，生成6250个多边形样本数据。从数据提取10个稳定的且频繁重复出现的建筑物形状，进行边界简化作为建筑物模板，构建建筑物形状模板库。模板的构建遵循抽象性、正交性、代表典型性、简单清晰等原则，且综合考虑了建筑物模板形状特征要具备易区分性，最终确定了10个建筑物形状模板，形如英文字母“LZOYTEUF”，属于常见的中国城市建筑物形状类型，大部分具有直角转角和对称的特点。建筑物形状模板及其对应的标签值具体如表1所示。
在具体的实验操作中，将6250个多边形样本按照8:2的比例将其划分为训练数据集和测试数据集，即随机抽取5000个作为训练样本，剩余1250个为测试集。图6为神经网络模型在训练和测试过程中精度的动态变化图，观察可知当训练的epoch到达2000时，训练精度和测试精度分别为98.7%、96.4%。为了验证3个宏观形状特征参量值在识别中作用，只用单一的傅里叶形状描述子（长度为50）作为神经网络的输入向量进行训练，发现其拟合精度和测试精度下降为86.5%和83.6%，说明3个宏观形状特征参量值可以提高神经网络的精度。
同时将1000个测试样本采用欧氏距离法和转角函数法进行了形状识别对比研究，表2为实验中部分结果数据。表中每个测试数据均采用三种方法与建筑物形状模板进行匹配，其中第1行对应傅里叶形状描述子的欧氏距离（缩写“ED”）的结果，每列分别是与各形状模板的傅里叶形状描述子间的欧氏距离，最小距离（加粗）对应匹配的模板。第2行对应转角函数法（缩写“TA”）,计算测试样本与每个模板的转角函数值，最小值（加粗）对应匹配模板。第3行是本文的神经网络方法（缩写“NN”），每列为测试样本匹配为各个模板的概率值，最大（加粗）为匹配结果。表2的最后1列为识别正确性判断。
表4统计了实验中三种方法的测试精度，其中，本文神经网络方法的形状识别精度高达98.7%，转角函数法的精度为79.5%，而傅里叶形状描述子的欧氏距离法只能达到17.2%。从分析结果来看，形状局部扰动直接影响了傅里叶形状描述子的欧氏距离判断精度，而以傅里叶形状描述子和宏观形状特征参量为输入值的神经网络精度最好。
3.2模型的实践应用
为证明本文方法在形状识别上的普适性和可行性，在OpenStreetMap网站（http://www.openstreetmap.org/）下载武汉市、郑州市两个城市的建筑物矢量数据，利用训练好的神经网络中对城市中各个建筑物多边形识别，表4为两个城市建筑多边形的分类结果，图7给出了部分识别结果的示意图。从识别结果来看，基本与人的认知基本相符，有少部分“O”型被错误识别为“I”型，但对于这部分多边形，人也无法准确地进行类别的划分。有些边界复杂的多边形被识别为“F”型，针对该问题需要后期补充形状模板的类型。
4 总结与讨论
将神经网络方法应用于建筑多边形的形状识别是一种有效结合人的认知实验、数学模型、计算机拟合的方法，其中样本标签属于认知实验，形状特征提取属于数学模型，而神经网络的训练中参数调整属于计算机的逼近和拟合。本文提取傅里叶形状描述子、圆形度、偏心率和矩形度作为神经网络的输入特征向量，构建了建筑多边形形状识别的神经网络方法，实验证明该方法比经典的傅里叶形状描述子欧氏距离法、转角函数法识别精度高。本文所选用的形状特征向量中，傅里叶形状描述子有经典的提取模型，能够将二维延展的要素形状转化为一维的傅里叶级数模向量，可以根据拟合精度的要求控制模向量的长度，不需要通过建筑多边形的节点加密来保证不同多边形的模向量长度，并且傅里叶形状描述子能基本还原建筑多边形的形状，说明其形状描述上具有科学性。另外，由于傅里叶形状描述子是多边形频谱的能量反映，多边形中任何的微小变化都将会引起所有频率的幅值变化，这样容易造成傅里叶形状描述子在形状识别中不稳定，本文将圆形度、偏心率和矩形度等宏观形状特征参量纳入形状特征向量能起到抑制作用。在后面的工作中，我们将本方法实际应用到城市建筑物形状识别工作中，并将进一步的探索其他要素（如自然要素）形状识别问题。
[1] 艾廷华,帅赟,李精忠．基于形状相似性识别的空间查询[J]．测绘学报,2009,38(4):356-362. DOI: 10.3321/j.issn:1001-1595.2009.04.012.
[2] 晏雄锋,袁拓,杨敏,孔博,刘鹏程.建筑物形状特征分析表达与自适应化简方法[J].测绘学报,2022,51(2):269-278. DOI: 10.11947/j.AGCS.2022.20210302.
[3] RAINSFORD D,MACKANESS W．Template Matching in Support of Generalization of Rural Buildings[M]∥ RICHARDSON D E,VAN OOSTEROM P．Advances in Spatial Data Handling．Berlin:Springer,2002:137-151.
[4] 刘鹏程,艾廷华,胡晋山,等．基于原型模板形状匹配的建筑多边形化简[J]．武汉大学学报(信息科学版),2010, 35(11):1369-1372．
[5] WANG Zeshen,LEE D．Building simplification based on pattern recognition and shape analysis[C]∥Proceedings of the 9th International Symposium on Spatial Data Handling．Beijing:[s．n．],2000:58-72．
[6] 晏雄锋, 艾廷华, 杨敏. 居民地要素化简的形状识别与模板匹配方法[J]. 测绘学报, 2016, 45(7): 874-882. DOI: 10.11947/j.AGCS.2016.20150162.
[7] 安晓亚. 空间数据几何相似性度量理论方法与应用研究[J]. 测绘学报, 2013,42(1):157.
[8] HAN M, ZHENG D . Shape Recognition Based on Fuzzy Shape Context[J]. Acta Automatica Sinica, 2012, 38(1):68-75. DOI:10.3724/SP.J.1004.2012.00068.
[9] GUO W, YU A, SUN Q, et al. A Multisource Contour Matching Method Considering the Similarity of Geometric Features[J]. The Journal of Geodesy and Geoinformation Science, 2020,3(3):76-87.DOI: 10.11947/j.JGGS.2020.0308.
[10] 吴绍根,聂为清,路利军,刘娅琴.典型的基于区域的形状表示方法比较[J].中国图象图形学报,2018,23(8):1242-1253. DOI:10.11834/jig.180016.
[11] FREEMAN H. On the encoding of arbitrary geometric configurations[J]. IRE Trans on Electron Comput,1961,10(2):260-268. DOI:10.1109/tec.1961.5219197.
[12] FREEMAN H. Computer Processing of Line Drawing Images[J].ACM Computing Surveys,1974,6(1):57-97. DOI:10.1145/356625.356627.
[13] ZAHNC. T., and R. Z. Roskies. Fourier descriptors for plane closed curves[J]. IEEE Transactions on Computers, 2009, C-21 (3): 269–281. DOI:10.1109/TC.1972.5008949.
[14] MOELLERING H , RAYNER J N . The harmonic analysis of spatial shapes using dual axis Fourier shape analysis (DAFSA)[J]. Geographical Analysis, 2010, 13(1):64-77. DOI:10.1109/TSMC.1977.4309681.
[15] 刘鹏程. 形状识别在地图综合中的应用研究[J]. 测绘学报, 2012,41(2):316.
[16] Ai T , Cheng X , Liu P , et al. A shape analysis and template matching of building features by the Fourier transform method[J]. Computers Environment & Urban Systems, 2013, 41(sep.):219-233. DOI:10.1016/j. compenvurbsys.2013.07.002.
[17] ARKIN E,CHEW L,HUTTENLOCHE R D,et al.An efficiently computable metric foe comparing polygonal shapes[J].IEEE Transaction on Pattern Analysis and Machine Intelligence,1991,13(3):209-216. DOI:10.1109/34.75509.
[18] Attalla E , Siy P . Robust shape similarity retrieval based on contour segmentation polygonal multiresolution and elastic matching[J]. Pattern Recognition, 2005, 38(12):2229-2241.DOI:10.1016/j.patcog.2005.02.009.
[19] DING X , WU H , ZHANG H , et al. Review on shape matching[J]. Acta Automatica Sinica, 2001, 27(5):678-694.
[20] 周瑜,刘俊涛,白翔.形状匹配方法研究与展望[J].自动化学报,2012,38(6):889-910. DOI: 10.3724/SP.J.1004.2012.00889.
[21] 刘鹏程,艾廷华,杨敏.基于傅里叶级数的等高线网络渐进式传输模型[J].测绘学报,2012,41(2):284-290.
[22] 刘鹏程,罗静,艾廷华,李畅.基于线要素综合的形状相似性评价模型[J].武汉大学学报(信息科学版),2012,37(1):114-117.
[23] 刘鹏程,肖天元,肖佳,艾廷华.曲线多尺度表达的Head-Tail信息量分割法[J].测绘学报,2020,49(7):921-933. DOI: 10.11947/j.AGCS.2020.20200004.
[24] 刘鹏程,肖天元,艾廷华,杨敏.基于傅里叶能量度量的曲线多尺度表达[J].中国矿业大学学报,2020,49(3):587-594.
[25] YAN, X.. AI, T., YANG, M.. et al. Graph convolutional autoencoder model for the shape coding and cognition of buildings in maps. International Journal of Geographical Information Science, 2020,35(3): 490-512. DOI:10.1080/13658816 .2020. 1768260.