2. 广东省城市化与地理环境空间模拟重点实验室，广东 广州 510275；
3. 广东省国土资源测绘院，广东 广州 510500
2. Guangdong Key Laboratory for Urbanization and Geo-simulation，Guangzhou 510275, China;
3. Institute of Surveying and Mapping of Land and Resources Department of Guangdong Province, Guangzhou 510500，China
变化信息的建模与检测是空间数据库更新[1]的研究重点。国内外学者提出了对象匹配[2, 3, 4]、拓扑联动及空间叠加等变化信息检测方法。文献[2, 3]通过计算对象间距离、形状或方向差异等多项指标检测变化信息。算法中阈值与权重主要由人工设置，自动化程度有待进一步提高。文献[5]提出了基于概率理论的多指标匹配模型，避免了精确阈值的人为确定，但是在双向匹配过程中出现了重复计算，如何提高效率值得进一步研究。基态-修正模型[6]、时空快照模型[7] 等分类模型以事件为驱动，通过拓扑及语义关系确定目标的变化类型，在地籍数据库更新中得到应用[8, 9]，变化信息的判断规则与专题应用联系紧密，通用型有待加强。通过专家系统、神经网络或snake模型从遥感影像中提取变化信息是另一种研究思路[10, 11]。这类方法的实时性强、变化检测的效率高，但变化信息的描述能力有待提高，如何与后续的更新处理结合仍需深入研究。
目前，变化信息的检测方法侧重于对多项评价指标的统计分析以获取变化信息。需要反复进行试验得出合理的权重及阈值参数，工作效率较低，并容易受到人为的影响。模式识别技术的自学习、自组织能力可用于挖掘空间数据隐含的特征，在制图综合[12]、空间特征分析[13]、遥感图像变化信息提取[14]等领域得到了广泛应用。因此，本文结合模式识别的理论与方法，提出基于神经网络决策树的变化信息识别方法，融合了决策树实现效率高和神经网络自适应的特征，通过样本的训练，自适应地调整模型参数与阈值，避免人为多次试验，提高了工作效率。
2 变化信息特征空间矢量数据的变化信息检测需要对新旧数据的几何信息、语义信息及拓扑信息进行判别[15]，从而确定信息的变化类型。本文从实体几何类型、尺度特征、特征差异、更新类型等方面定义变化信息的特征空间。
式(1)中，Scale记录尺度信息，可划分为同级比例尺的更新或不同比例尺数据的更新；Time Span表示时间跨度；Geometry Type表示数据的几何类型；Change Characteristics为新旧数据间几何、语义及空间关系的变化特征。Update Type是从对象的特征差异中所提取的变化类型：新增、消失、合并(多个旧要素合并成一个新要素)、分解(一个旧要素分解成多个新要素)、聚合(多个旧要素聚合成多个新要素)、形状变化、属性变化等；Update Operation则是针对不同变化类型进行的处理。具体如图 1所示。
|
| 图 1 变化信息特征空间 Fig. 1 Feature space of change information |
本文的研究重点是面向同一尺度数据的变化信息识别。更新场景的定义与更新数据的比例尺、几何特征及图层内容相关。通过神经网络训练所构建模型，可应用于相同的更新场景中。方法的总体思路如下：
(1) 通过数据叠加，选取新旧对象组合作为训练样本。
(2)计算样本数据的变化特征指标。
(3)把指标作为输入层，更新分类信息作为输出层，进行神经网络训练，获取模型的阈值与权重矩阵。
(4)通过对全体数据的叠加操作获取更新对象组合，并进行指标计算。
(5)把数据的变化特征指标作为输入量，使用(3)中建立的神经网络模型进行模式判别，获取变化信息的分类结果。
|
|
| 图 1 基于神经网络决策树的矢量数据变化信息识别方法 Fig. 1 Change information recognition of vector data based on neural network decision tree |
变化特征指标的选取需要全面地反映新旧对象之间的距离、空间关系、几何及语义等特征的差异。按照不同的几何类型，指标的选取情况如表 1所示。
其中，距离指标对于点、面要素可通过计算质心的欧氏距离来实现，线要素可视为点的组合，通过Hausdoff距离衡量线要素的远近程度。空间关系的指标主要表现为要素重叠度。几何特征的差异可通过周长、面积、长度的相似程度或傅立叶描述子[17]、转向函数[18]等指标进行描述。方向特征则以线要素的首尾节点连线方向或面要素的最小面积包络矩形的长轴方向确定。语义特征由要素属性值的差异程度确定，本文参考文献[20]提出的对象属性匹配算法进行计算。匹配特征指标反映了新旧对象1∶0、1∶n、m∶n等多种匹配情况。
3.2.2 基于层次检索的变化特征提取方法在变化信息检测中，全要素逐一匹配的方法[9]相对于变化较少的区域运算效率低。基于R树和R+树的空间索引具有动态更新、深度平衡特点，可提高要素的查询效率[21, 22]。然而，该方法 “自下而上”地构建索引，需要对各分割空间内的要素进行逐一匹配，难以快速过滤不变的要素。本文提出的方法通过计算区域内要素的“节点-弧段”特征，对可能发生变化的区域进行“自上而下”地剖分，不考虑没有发生变化的区域，有助于提高计算的效率。
3.2.2.1 基于四叉树的变化区域检索基于四叉树的变化区域检索操作步骤为：
(1) 遍历所有更新数据中的对象，计算最小外包矩形作为四叉树的根节点
(2) 计算范围内的数据变化特征，本文在文献[23]提出的NVQ(number of vertices queried)模型的基础上，综合考虑节点数与弧段数，提出区域要素变化特征评估模型
式(2)中，Ofeas、Nfeas为区域范围内的原数据和更新数据的要素集合，FCI(Ofeas,Nfeas)用于衡量要素的整体变化情况。Ovts、 Nvts为新旧要素的结点集合。Oegs、Negs为相应的弧段集合，对于面图层，则为边界弧段的集合。VCI(Ovts,Nvts)和ECI(Oegs,Negs)分别用于衡量区域内新旧数据集的节点与弧段的变化程度。PCI (Ofeas,Nfeas)用于表示新旧区域要素的重心偏移程度。ω1、ω2、ω3表示各指标所占的权重，取值在0～1之间。对于点图层，不存在弧段变化特征的计算，故ω2应设为0。式(3)中函数Cnt( )用于计算节点集的数量，式(4)中的函数Len( )计算弧段集的总长度。式(5)中(Xofeas,Yofeas)为旧区域的重心坐标，(Xnfeas，Ynfeas)为新区域的重心坐标，Area( )用于计算区域的面积。
(3) 判断区域范围内数据变化特征情况，若FCI(Ofeas,Nfeas)的计算结果小于阈值，则视为没有发生变化的区域，无需进行变化特征提取。若大于阈值，说明该区域存在变化信息需要分割。分割的方法为：提取区域内新旧要素重心的X、Y坐标并计算其均值，最后以其为中心沿x轴、y轴方向把原区域分划为4个子区域。
(4) 重复步骤(2)、(3)，直到所划分的子区域内的要素数目少于指定的数值就结束剖分。并把该区域范围记录在链表内，以备下一步对象的匹配(见图 3)。
|
| 图 3 基于四叉树的变化区域检索 Fig. 3 Searching of change region based on quad-tree |
对于存在变化对象的区域，本文通过新旧要素交互迭代检索的方法进行匹配，避免对同一数据集的重复检索[24]。算法思路为：历遍原要素集合Ofeas(Ofea1，Ofea2，Ofea3，…，Ofeam),创建要素Ofeai的缓冲区Buffer(Ofeai)，并搜索与该区域重叠的新要素。若不存在，则为1∶0匹配；若存在新要素Nfeaj，则创建新要素Nfeaj的缓冲区，重新搜索阈值重叠的原要素。如此交替进行，即可识别出1∶1、m∶1、1∶n、m∶n等多种要素匹配情况。对于原要素与新要素0∶1的匹配情况，则历遍新要素集，搜索出与原要素无任何重叠的新要素。通过缓冲距离设置，可识别出不同的新旧要素组合，为变化信息的识别提供基础。
3.2.2.3变化特征指标计算与归一化处理按照表 1中的指标，对要素组进行变化特征计算。对于1∶1的匹配情况，可直接计算新旧要素指标的差值。对于1∶n、m∶1、m∶n等要素匹配情况，则根据不同的指标，对多要素的特征计算结果进行求和或平均值的处理，再计算指标差值。为了消除量纲差异，可采取线性函数转换、对数函数转换等归一化处理方法，把变化特征指标中的绝对值变成相对值关系，以获得更好的识别效果。
3.3基于神经网络决策树的变化信息识别 3.3.1面向变化信息识别的神经网络决策树结构算法通过在决策树的非叶节点中设置神经网络，以实现自适应的模式分类[25, 26, 27]。在变化信息的识别中，对于“消失”、 “新增”的类别，本文借鉴分裂节点(split node)[25]概念，在决策树中按匹配特征直接判断。对于难以直接判断的类型(如分解、合并、聚合、几何变化、语义变化)，本文通过构建不同的神经网络节点(P1、P2、P3)进行识别(见图 4)。神经网络节点的输入层为对象组合的距离特征、几何特征等变化特征指标(见表 1)，输出层为变化信息的分类。激活函数选用Sigmoidal函数，隐藏层与输出层的节点输出可分别表示为
式(6)表示隐藏层，oj为隐藏层的第j个节点的输出，M为输入节点数，bi为偏置值(bias)，wij是输入-隐藏的权重值，xi是第i个输入节点的值。式(7)表示输出层，yk为输出层的第k个节点的输出，N为隐藏节点数,bj为偏置值(bias)，wjk是隐藏-输出的权重值，oj是第j个输入节点的值。
|
| 图 4 面向变化信息识别的神经网络决策树结构 Fig. 4 Neural network decision tree architecture of change information recognition |
训练方法以每一个新旧对象组的变化特征指标作为一个样本，设Ω={ω1,ω2,…,ωM}为问题集(M=6,为变化特征指标)，训练集表示为Tr={tr1,tr2,…,trq}，q表示训练样本的数目。通过基于判断规则的变化检测与人工检查相结合方法可生成大量的训练数据。神经网络决策树的训练步骤如下：
(1) 初始化神经网络节点中的输入-隐藏权重矩阵W1及隐藏-输出权重矩阵W2。
(2) 把训练样本集Tr加入神经网络决策树根节点。通过分裂节点中的规则剔除0∶1匹配和1∶0匹配的样本，只保留需要神经网络训练的样本。并根据1∶1匹配判断规则，把样本分为两个子集Tr1，Tr2。
(3) 分别遍历训练集Tr1、Tr2,分别对应神经网络节点P1、P2(见图 4)进行神经网络训练，按式(6)、式(7)计算网络输出值。对于发生变化的要素，在Tr1中分出样本集Tr3，对节点P3进行神经网络训练。
(4) 结束遍历子样本集后，进行误差计算和自适应的权重矩阵与偏置值调整。设在神经网络节点Pi中，输出节点数目为N(N为分类数)，对于第k个样本，误差可表示为
式(8)中，i为分类数；y是神经网络的输出矩阵；ta是样本的目标矩阵，表示分类的信息。当样本k属于第i类时，taki的值就为1，否则就为0。于是，样本集的整体误差可通过误差平方和的均值来表示
式(10)中，
在表示子样本集的整体误差；qcnt表示子样本的数目。
为提高神经网络的训练速度，学者们提出了在偏移量和权重的调整可考虑把上一次的调整量纳入模型[28]，具体为
式(11)中，η为学习效率；δj（n）为本次迭代的误差；α为动量因子；wij(n－1)为上一次调整量。增加动量项有助于降低误差曲面局部调整的敏感性，从而限制网络陷入局部极小。
(5) 若样本的整体误差值小于阈值或迭代次数大于上限，则结束迭代并输出权重矩阵与偏置值。否则，回到(3)，继续进行神经网络训练。
3.3.2 .2变化信息识别方法变化信息的识别把新旧对象组的变化特征指标作为一个样本，加至神经网络决策树的根节点。在分裂节点处对其匹配特征指标进行分类判断。若样本进入神经网络节点，则根据训练所得到的权重与偏置值进行识别，计算网络的输出向量。最后通过判别函数分析输出向量yk，若yki的值最接近1，则样本k属于第i类。
4 试验分析为验证模型与方法的效率，本文在Windows环境下，以Visual Studio 2008为开发平台，集成ArcGIS Engine10.0开发包，研制了变化信息识别原型系统。本文以1∶2000矢量地形图数据为例，进行同比例尺变化信息识别的试验，实现了变化特征指标提取，神经网络决策树训练与识别等算法(见图 5)。
|
| 图 5 基于神经网络决策树的变化信息识别试验 Fig. 5 An experiment of change information recognition based on neural network decision tree |
本文按照表 1所列出的变化特征指标分别对点、线、面等不同几何类型的空间对象进行试验。选择长度相似度、形状系数[19]作为线要素、面要素的几何特征指标。在更新数据中点要素670个(变化率为32.84%)，线要素1308个(变化率为8.72%)，面要素1101个(变化率为12.08%)，变化率为发生变化的要素与全部要素的比值。本文进行算法试验，对遍历要素检索，四叉树层次检索及R树索引检索等方法进行对比分析，结果如图 6所示。
试验表明，四叉树层次检索方法与遍历要素的检索方法相比，在变化比率较低的情况下，可大幅度提高变化信息的检索速度。添加R树索引后，遍历要素的检索速度得到了提高。然而，由于基于R树索引的检索难以过滤掉不变的信息，仍需对要素进行逐一匹配，运算量较大，因此，速度改善不如四叉树层次检索明显。对于点要素，由于在变化特征模型无需衡量弧段的变化情况。因此，计算效率提高得最明显。线要素、面要素需要综合计算节点变化情况和弧段变化情况(见式(2))。但是，由于减少了对不变数据的匹配与指标计算，仍可实现明显的效率提高。
|
| 图 6 变化特征指标提取试验对比 Fig. 6 Experimental results and comparison of change characteristics index calculation |
对于线要素和面要素，空间分割容易造成具有n∶m匹配特征的新旧要素分布在不同的空间区域，产生对匹配准确率的影响。因此，本文在新旧要素进行匹配的时候，把边界区域外的重叠要素也添加到新旧要素组中，实现顾及要素聚集的四叉树检索，从而保证匹配的准确率。
4.2 变化信息识别试验分析按照图 4的神经网络决策树算法，选取31个训练样本进行神经网络训练，本文所选取的是BP神经网络，试验把隐藏节点数设为8，学习效率预设为0.15，动量因子设为0.075，最大迭代次数设为20000。训练结束后进行变化信息模式识别试验，按照几何类型，更新数据分别选取670个点要素、1308个线要素及1101个面要素。与基于目标匹配判断规则的方法(参考文献24)相比较，试验结果如图 7所示。
|
| 图 7 变化信息识别试验对比 Fig. 7 Experimental results and comparison of change information recognition |
从图 7中可以看出，基于神经网络决策树的变化信息识别方法比判定规则识别准确率更高，对于线要素与面要素，识别准确率的提高更明显。模式识别方法在分析多要素变化的情况比传统方法更具优势，通过在训练数据中对变化类型进行明确的区分，应用在变化识别过程中，就能够较准确地识别合并、分解、聚合等各种变化情况。针对不同更新场景，分别通过神经网络的训练，可以对数据的变化信息进行识别，避免人为地设置阈值。
5 结 论本文以矢量数据变化信息的自动识别为切入点，提出了基于神经网络决策树的识别方法。试验表明该方法提高了分类的准确度且计算效率高。
(1)本文提出的基于层次检索的变化特征提取方法，通过四叉树分割快速定位到变化区域，检索存在重叠关系的新旧对象组，提高了运算效率。同时，该方法有助于过滤未发生变化的数据区域，使信息识别更具有针对性。
(2)基于神经网络决策树的变化信息识别方法具备了决策树逻辑性强，易于实现的优点，同时兼顾了神经网络的自适应特征。在保证运算效率的前提下，可提高分类的准确度。此外，该方法还可以减少人工的干预，有助于提升矢量数据更新的自动化水平，具有实用价值。
本文主要是以单一的要素为操作单元，实现要素级的变化信息识别。在实际应用中，更多情况是以多要素组合的地理实体作为更新的单元。因此，需要把要素级的变化信息映射为面向地理实体的变化信息，这将是本文下一步研究的方向。此外，为进一步提高识别的精度，下一步的研究工作还包括：① 改进变化区域的检索方法，使用基于不规则网格的划分方式，把具有集聚特征的新旧对象组更有效地划分在同一区域，避免被区域边界分割；② 引入粒子群算法等优化算法对神经网络的权重矩阵和阈值进行优化，以更好地寻找全局最优和实现快速收敛，提高变化信息的识别精度与效率；③ 从地理事件的角度，探讨空间对象到地理实体的变化信息映射机制，研究基于地理实体的变化信息识别模式。
| [1] | JIAN C L, HUANG M L. Research on Geographic Information Database Incremental Updating Method [C]//Proceedings of International Conference on Audio Language and Image Processing. Shanghai: [s.n.], 2010:985-989. |
| [2] | PATRICK R, ANTOINE B. Automated Matching of Building Feature of Differing Levels of Detail: A Case Study [C]//Proceedings of 24th International Cartographic Conference. Santiago: [s.n.], 2009. |
| [3] | ZHANG Xinchang, GUO Taisheng, TANG Tie. An Adaptive Method for Incremental Updating of Vector Data [J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(4): 613-619.(张新长,郭泰圣,唐铁. 一种自适应的矢量数据增量更新方法研究 [J]. 测绘学报,2012,41(4):613-619.) |
| [4] | ZHANG Qiaoping,LI Deren, GONG Jianya. Areal Feature Matching among Urban Geographic Databases [J]. Journal of Remote Sensing, 2004, 8(2): 107-112. (张桥平,李德仁,龚健雅. 城市地图数据库面实体匹配技术 [J]. 遥感学报,2004, 8(2):107-112.) |
| [5] | TONG Xiaohua, DENG Susu, SHI Wenzhong. A Probabilistic Theory-based Matching Method [J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(2): 210-217.(童小华,邓愫愫,史文中. 基于概率的地图实体匹配方法 [J]. 测绘学报, 2007, 36(2):210-217.) |
| [6] | LIN Y, LIU W Z, CHEN J. Model Spatial Database Incremental Updating Based on Base State with Amendment [J]. Procedia Earth and Planetary Science, 2009, 1:1173-1179. |
| [7] | CHEN Jun, LIN Yan, LIU Wanzeng et al. Formal Classification of Spatial Incremental Changes for Updating [J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(1): 108-114. (陈军,林艳,刘万增,等. 面向更新的空间目标快照差分类与形式化描述 [J]. 测绘学报, 2012, 41(1): 108-114.) |
| [8] | ZHANG Feng, LIU Nan, LIU Renyi, et al. Research of Cadastral Data Modeling and Database Updating Based on Spatio-temperal Process [J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(3): 303-309. (张丰,刘男,刘仁义,等. 面向对象的地籍时空过程表达与数据更新模型研究[J]. 测绘学报, 2010, 39(3): 303-309.) |
| [9] | FAN Y T, YANG J Y, ZHU D H. An Event-based Change Detection Method of Cadastral Database Incremental Updating [J]. Mathematical and Computer Modeling,2010, 51: 1343-1350. |
| [10] | BALTSAVIAS E, ZHANG C S. Automatic Updating of Road Databases from Aerial Images [J]. International Journal of Applied Earth Observation and Geoinformation, 2005, 6: 199-213. |
| [11] | IOANNIDIS C, PSALTIS C, POTSIOU C. Towards a Strategy for Control of Suburban Informal Buildings through Automatic Change Detection [J]. Computer, Environment and Urban Systems, 2009, 33(1): 64-74. |
| [12] | BALBOA J L G, LPEZ F J A. Sinuosity Pattern Recognition of Road Features for Segmentation Purposes in Cartographic Generalization [J]. Pattern Recognition, 2009, 42: 2150-2159. |
| [13] | HEINZLE F, HEINRICH K, SESTER M. Pattern Recognition in Road Networks on Example of Circular Road Detection [J]. Geographic Information Science, Lecture Notes in Computer Science, 2006, 4197: 153-167. |
| [14] | GHOSH S, PATRA S, GHOSH A. An Unsupervised Context-sensitive Change Detection Technique based on Modified Self-organizing Feature Map Neural Network [J]. International Journal of Approximate Reasoning, 2009, 50: 37-50. |
| [15] | XU Feng, DENG Min, ZHAO Binbin et al. A Detail Investigation on the Method of Object Matching [J]. Journal of Geo-information Science, 2009, 11(5): 657-663. (徐枫,邓敏,赵彬彬,等. 空间目标匹配方法的应用分析[J]. 地球信息科学学报, 2009, 11(5): 657-663.) |
| [16] | DENG M, LI Z L, CHEN X Y. Extended Hausdorff Distance for Spatial Objects in GIS [J]. International Journal of Geographical Information Science, 2007, 21(4): 459-475. |
| [17] | ZHANG D, LU G. A Comparative Study on Shape Retrieval Using Fourier Descriptors with Different Shape Signatures [J]. Journal of Visual Communication and Image Representation, 2003, 14(1):41-60. |
| [18] | ARKIN E, CHEW P, HUTTENLOCHER D, et al. An Efficiently Computable Metric for Comparing Polygon Shapes [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1991, 13(3):209-216. |
| [19] | LI Xinbi, JIANG Na, KONG Jie. A Change Detection Method of Polygon Features Based on Geometrical Characteristic [J]. Geomatics & Spatial Information Technology, 2011, 34(3): 177-180. (李新滨,江娜,孔杰.一种基于几何特征的面状要素变化检测方法[J]. 测绘与空间地理信息, 2011,34(3):177-180.) |
| [20] | COBB M A, CHUNG M J, FOLEY III H, et al. A Rule-based Approach for the Conflation of Attributed Vector Data [J]. GeoInformatica, 1998, 2(1):7-35. |
| [21] | GONG Jun, ZHU Qing, ZHANG Yeting, et al. An Efficient 3D R-Tree Extension Method Concerned with Levels of Detail [J]. Acta Geodaetica et Cartographica Sinica. 2011, 40(2): 249-255.(龚俊,朱庆,张叶廷,等. 顾及多细节层次的三维R树索引扩展方法, 2011, 40(2):249-255.) |
| [22] | DENG Hongyan, WU Fang, ZHAI Renjian, et al. R-Tree Index Structure for Multi-Scale Representation of Spatial Data [J]. Chinese Journal of Computers, 2009, 32(1): 177-184. (邓红艳,武芳,翟仁健,等. 一种用于空间数据多尺度表达的R树索引结构,2009, 32(1): 177-184.) |
| [23] | CHENG C X, LU F, CAI J. A Quantitative Scale-setting Approach for Building Multi-scale Spatial Databases [J]. Computer&Geosciences, 2009, 35: 2204-2209. |
| [24] | YING Shen, LI Lin, LIU Wanzeng, et al. Change-only Updating Based on Object Matching in Version Databases [J].Geomatics and Information Science of Wuhan University, 2009, 34(6): 752-755.(应申,李霖,刘万增,等. 版本数据库基于目标匹配的变化信息提取与数据更新 [J].武汉大学学报:信息科学版,2009,34(6): 752-755.) |
| [25] | MICHELONI C, RANI A, KUMAR A,et al. A Balance Neural Tree for Pattern Classification [J]. Neural Network, 2012, 27: 81-90. |
| [26] | FORESTI G L, PIERONI G. Exploiting Neural Trees in Range Image Understanding [J]. Pattern Recognition Letters, 1998, 19:869-878. |
| [27] | MAJI P. Efficient Design of Neural Network Tree Using a Single Splitting Criterion [J]. Neurocomputing, 2008,71: 787-800. |
| [28] | WANG Ting, JIANG Wenhui, XIAO Nanfeng. Numerical Recognition Based on Improved BP Neural Network [J]. Electronic Design Engineering, 2011, 19(3): 108-112. (王婷,江文辉,肖南峰. 基于改进BP神经网络的数字识别,2011,19(3):108-112.) |