Relaxation‐Based Point Feature Matching for Vector Map Conflation

With the rapid advance of geospatial technologies, the availability of geospatial data from a wide variety of sources has increased dramatically. It is beneficial to integrate / conflate these multi‐source geospatial datasets, since the integration of multi‐source geospatial data can provide insights and capabilities not possible with individual datasets. However, multi‐source datasets over the same geographical area are often disparate. Accurately integrating geospatial data from different sources is a challenging task. Among the subtasks of integration/conflation, the most crucial one is feature matching, which identifies the features from different datasets as presentations of the same real‐world geographic entity. In this article we present a new relaxation‐based point feature matching approach to match the road intersections from two GIS vector road datasets. The relaxation labeling algorithm utilizes iterated local context updates to achieve a globally consistent result. The contextual constraints (relative distances between points) are incorporated into the compatibility function employed in each iteration's updates. The point‐to‐point matching confidence matrix is initialized using the road connectivity information at each point. Both the traditional proximity‐based approach and our relaxation‐based point matching approach are implemented and experiments are conducted over 18 test sites in rural and suburban areas of Columbia, MO. The test results show that our relaxation labeling approach has much better performance than the proximity matching approach in both simple and complex situations.     

一种应用三角形划分的空间对象形状匹配方法

为解决现有空间对象形状相似性匹配准确率较低的问题,提出一种应用三角形划分的形状相似性匹配方法。该方法按形状主方向对面状空间对象进行分割,按串联、并联和组合形式对空间对象进行三角形划分,准确描述面状空间对象的形状特征,度量空间对象间的形状相似性。通过形状数据集匹配、不同年份面状水系图层匹配和矢量地图草图检索,测试本方法的形状检索性能,并和其他空间对象形状匹配方法进行对比。实验结果表明,本方法具有更高的形状检索准确率。三角形划分形状匹配方法具有平移、旋转、尺度不变性和较强的形状描述识别能力。     

An iterative approach based on contextual information for matching multi‐scale polygonal object datasets

Object matching facilitates spatial data integration, updating, evaluation, and management. However, data to be matched often originate from different sources and present problems with regard to positional discrepancies and different levels of detail. To resolve these problems, this article designs an iterative matching framework that effectively combines the advantages of the contextual information and an artificial neural network. The proposed method can correctly aggregate one‐to‐many (1:N) and many‐to‐many (M:N) potential matching pairs using contextual information in the presence of positional discrepancies and a high spatial distribution density. This method iteratively detects new landmark pairs (matched pairs), based on the prior landmark pairs as references, until all landmark pairs are obtained. Our approach has been experimentally validated using two topographic datasets at 1:50 and 1:10k. It outperformed a method based on a back‐propagation neural network. The precision increased by 4.5% and the recall increased by 21.6%, respectively.     

基于邻近模式的多比例尺居民地松弛迭代匹配

空间目标匹配是实现多源空间信息融合、空间对象变化检测与动态更新的重要前提。针对多比例尺居民地匹配问题,提出了一种基于邻近模式的松弛迭代匹配方法。该方法首先利用缓冲区分析与空间邻近关系检测候选匹配目标与邻近模式,同时计算候选匹配目标或邻近模式间的几何相似性得到初始匹配概率矩阵;然后对邻近候选匹配对进行上下文兼容性建模,利用松弛迭代方法求解多比例尺居民地的最优匹配模型,选取匹配概率最大并满足上下文一致的候选匹配目标或邻近模式为最终匹配结果。实验结果表明,所提出的多比例尺居民地匹配方法具有较高的匹配精度,能有效克服形状轮廓同质化与非均匀性偏差问题,并准确识别1:M、M:N的复杂匹配关系。     

A multi‐criteria decision‐making approach for geometric matching of areal objects

We propose a method for geometric areal object matching based on multi‐criteria decision making. To enable this method, we focused on determining the matched areal object pairs that have all relations, one‐to‐one relationships to many‐to‐many relationships, in different spatial data sets by fusing geometric criteria without user invention. First, we identified candidate corresponding areal object pairs with a graph‐based approach in training data. Second, three matching criteria (areal hausdorff distance, intersection ratio, and turning function distance) were calculated in candidate corresponding pairs and these criteria were normalized. Third, the shape similarity was calculated by weighted linear combination using the normalized matching criteria (similarities) with the criteria importance through intercriteria correlation method. Fourth, a threshold (0.738) of the shape similarity estimated in the plot of precision versus recall versus all possible thresholds of training data was applied, and the matched pairs were determined and identified. Finally, we visually validated the detection of similar areal feature pairs and conducted statistical evaluation using precision, recall, and F‐measure values from a confusion matrix. Their values were 0.905, 0.848, and 0.876, respectively. These results validate that the proposed classifier, which detects 87.6% of matched areal pairs, is highly accurate.     

利用松弛标记法进行空间场景匹配

相似性度量是地理学中的关键组成部分,被广泛应用于空间检索、空间信息整合及空间数据挖掘中。因为空间场景中实体个数的差异及空间对象间的关系难以精确相等,若执行空间场景的完全精确匹配,可能会使得检索结果为空。顾及尺度差异,从空间场景中进行空间语义理解,建立了多尺度空间场景的形式化描述模型,并提取场景中稳定的特征构建空间场景特征矩阵。建立场景间的初始匹配概率矩阵后,基于松弛标记法迭代更新概率矩阵,直到矩阵收敛于一全局最小值并确定匹配的实体对,从而进行空间场景相似性评估。采用武汉居民地域数据进行场景匹配实验,并对不同邻域搜索半径下的匹配时间及精确度进行对比与分析,实验结果表明,基于松弛标记法的空间场景匹配方法具有较高的精确度。     

A geometric-based approach for road matching on multi-scale datasets using a genetic algorithm

Object matching is used in various applications including conflation, data quality assessment, updating, and multi-scale analysis. The objective of matching is to identify objects referring to the same entity. This article aims to present an optimization-based linear object-matching approach in multi-scale, multi-source datasets. By taking into account geometric criteria, the proposed approach uses real coded genetic algorithm (RCGA) and sensitivity analysis to identify corresponding objects. Moreover, in this approach, any initial dependency on empirical parameters such as buffer distance, threshold of spatial similarity degree, and weights of criteria is eliminated and, instead, the optimal values for these parameters are calculated for each dataset. Volunteered geographical information (VGI) and authoritative data with different scales and sources were used to assess the efficiency of the proposed approach. According to the results, in addition to an efficient performance in various datasets, the proposed approach was able to appropriately identify the corresponding objects in these datasets by achieving higher F-Score.     

中误差和邻近关系的多尺度面实体匹配算法研究

地图目标匹配作为空间数据整合和更新的一个不可缺少的过程,有重要的研究意义。中误差是一种衡量地图精度和质量的数值指标,其范围作为制图和综合的重要的标准之一,常用其大小评价空间数据的质量,不同比例尺或来源的地图数据均有不同的中误差大小和阈值。面状要素在很多地图中占有很大的比例,本文将中误差引入面实体匹配的过程,结合相邻面实体邻近聚集算法,提出一种基于中误差和邻近关系的面实体匹配算法,可以有效解决多尺度空间数据匹配的阈值大小和多对多关系难确定的问题,实验结果表明该方法具有良好的稳定性和可靠性。     

顾及尺度变化和数据更新的道路网匹配算法

道路网数据匹配是地理空间数据库进行变化探测和数据更新的重要前提,不同比例尺下的道路网之间的匹配是一个非常重要的部分。本文总结和分析了道路网匹配的已有算法,针对不同比例尺道路网之间的匹配可能存在的问题和难点,设计了一个融合多种匹配技术的算法。在考虑不同比例尺下道路网数据的特点基础上,改进了空间场景结构的评价方法;分析了stroke匹配算法在不同比例尺道路网数据下的局限性,提出了一种可针对不同比例尺下道路数据存在变化与更新的stroke部分匹配算法。试验表明,文中所提出的方法能够适应不同比例尺下道路网的匹配,匹配效果较好,运行效率较高。     

A building polygonal object matching method based on minimum bounding rectangle combinatorial optimization and relaxation labeling

Volunteered geographic information (VGI) is an emerging phenomenon where anyone can create geographic information and share it with others. Compared with traditional authoritative geospatial data, it has several advantages, such as enriched data, instant updates, and low cost. The object matching method is widely used in VGI quality assessment and data updates. However, VGI matching faces certain challenges, such as the levels of detail that vary from object to object, the uneven distribution of data quality, and the automated matching requirement. To resolve these problems, this article proposes a new matching method that effectively combines the advantages of minimum bounding rectangle combinatorial optimization (MBRCO) and relaxation labeling. The proposed method (1) avoids setting the similarity threshold and weights and does not require training samples. This process is realized based on contextual information and optimization. (2) It overcomes the disadvantage that the MBRCO algorithm cannot distinguish adjacent buildings with similar shapes. Our approach is experimentally validated using two publicly available spatial datasets: OpenStreetMap and AutoNavi map. The experimental studies show that the proposed automatic matching method outperforms all the threshold-based MBRCO methods and achieves high accuracy with a precision of 97.8% and a recall of 99.2%.     

A spatial contextual immune genetic algorithm to building cartographic displacement

In map generalization, displacement is the most frequently used operator to reduce the proximity conflicts caused by reducing scales or other generalization operations. Building displacement can be formalized as a combinatorial optimization problem, and a heuristic or intelligent search algorithm can be borrowed to obtain the solution. In this way, we can explicitly resolve minimum distance conflicts and control positional accuracy during the displacement. However, maintaining spatial relations and patterns of buildings can be challenging. To address spatial conflicts as well as preserve the significant spatial relations and patterns of buildings, we propose a new spatial contextual displacement algorithm based on an immune genetic algorithm. To preserve important spatial relations and global patterns of map objects and avoid topology errors, displacement safety zones are constructed by overlapping the Voronoi tessellation and buffer areas of the buildings. Additionally, a strategy to shift the buildings in a building group synchronously is used to maintain local building patterns. To demonstrate the effectiveness of our algorithm, two data sets with different building densities were tested. The results indicate that the new algorithm has obvious advantages in preventing topology errors and preserving spatial relations and patterns.     

Object based image analysis for remote sensing

Remote sensing imagery needs to be converted into tangible information which can be utilised in conjunction with other data sets, often within widely used Geographic Information Systems (GIS). As long as pixel sizes remained typically coarser than, or at the best, similar in size to the objects of interest, emphasis was placed on per-pixel analysis, or even sub-pixel analysis for this conversion, but with increasing spatial resolutions alternative paths have been followed, aimed at deriving objects that are made up of several pixels. This paper gives an overview of the development of object based methods, which aim to delineate readily usable objects from imagery while at the same time combining image processing and GIS functionalities in order to utilize spectral and contextual information in an integrative way. The most common approach used for building objects is image segmentation, which dates back to the 1970s. Around the year 2000 GIS and image processing started to grow together rapidly through object based image analysis (OBIA - or GEOBIA for geospatial object based image analysis). In contrast to typical Landsat resolutions, high resolution images support several scales within their images. Through a comprehensive literature review several thousand abstracts have been screened, and more than 820 OBIA-related articles comprising 145 journal papers, 84 book chapters and nearly 600 conference papers, are analysed in detail. It becomes evident that the first years of the OBIA/GEOBIA developments were characterised by the dominance of ‘grey’ literature, but that the number of peer-reviewed journal articles has increased sharply over the last four to five years. The pixel paradigm is beginning to show cracks and the OBIA methods are making considerable progress towards a spatially explicit information extraction workflow, such as is required for spatial planning as well as for many monitoring programmes.     

面状居民地匹配的空间认知特点研究

对匹配空间认知过程的理解和形式化表达是设计匹配算法的基础和出发点,同时又是检验匹配结果正确与否的落脚点.以面状居民地为例,分析了人在进行同名对象匹配时的心理历程和视觉思维特点.基于相似性理论,建立了居民地匹配过程中的相似性认知模式.通过设计不同层次的问卷调查,获取并分析了知识背景不同的制图人员在不同的匹配场景下对面状居...     

Evaluating data stability in aggregation structures across spatial scales: revisiting the modifiable areal unit problem

ABSTRACT

Socioeconomic and health analysts commonly rely on areally aggregated data, in part because government regulations on confidentiality prohibit data release at the individual level. Analytical results from areally aggregated data, however, are sensitive to the modifiable areal unit problem (MAUP). Levels of aggregation as well as the arbitrary and modifiable sizes, shapes, and arrangements of zones affect the validity and reliability of findings from analyses of areally aggregated data. MAUP, long acknowledged, remains unresolved. We present an exploratory spatial data analytical approach (ESDA) to understand the scalar effects of MAUP. To characterize relationships between data aggregation structures and spatial scales, we develop a method for statistically and visually exploring the local indicators of spatial association (LISA) exhibited between a variable and itself across varying levels of aggregation. We demonstrate our approach by analyzing the across-scale relationships of aggregated 2010 median income for the State of Pennsylvania and 2005–2009 cancer diagnosis rates for the State of New York between county–tract, tract–block group, and county–block group level US census designated enumeration units. This method for understanding the relationship between MAUP and spatial scale provides guidance to researchers in selecting the most appropriate scales to aggregate, analyze, and represent data for problem-specific analyses.     

Combined object-based classification and manual interpretation–synergies for a quantitative assessment of parcels and biotopes

Recent technical advances in remote sensing data capture and spatial resolution lead to a widening gap between increasing data availability on the one hand and insufficient methodology for semi-automated image data processing and interpretation on the other hand. At the interface of GIS and remote sensing, object-based image analysis methodologies are one possible approach to close this gap. With this, methods from either side are integrated to use both the capabilities of information extraction from image data and the power to perform spatial analysis on derived polygon data. However, dealing with image objects from various sources and in different scales implies combining data with inconsistent boundaries. A landscape interpretation support tool (LIST) is introduced which seeks to investigate and quantify spatial relationships among image objects stemming from different sources by using the concept of spatial coincidence. Moreover, considering different categories of object fate, LIST enables a change categorization for each polygon of a time series of classifications. The application of LIST is illustrated by two case-studies, using Landsat TM and ETM as well as CIR aerial photographs: the first showing how the tool is used to perform object quantification and change analysis; the latter demonstrating how superior aggregation capabilities of the human brain can be combined with the fine spatial segmentation and classification. Possible fields of application are identified and limitations of the approach are discussed.     

VGI数据与地形图数据的自动融合研究

随着科学技术的不断发展，志愿者地理信息（volunteered geographic information，VGI）已经成为地理空间数据中最为重要的来源之一。为了充分利用志愿者地理信息，需要进行VGI与传统地形图数据的匹配与融合。开发了一种全新的数据自动匹配与融合算法，其目的是将ATKIS道路网数据（由德国联邦测绘局所采集的官方数据）与AOSD数据（由大量志愿者携带定位仪器进行户外徒步或骑行所获取的轨迹数据）匹配并融合起来，从而丰富传统地理信息数据的内容，并实现数据的增值。考虑到ATKIS数据与AOSD数据在空间表达上的差异很大，所开发的算法包括了道路要素的智能化分割、道路要素匹配、道路网数据融合以及融合后道路网内部要素间的匹配运算与数据集成等4个过程。大量实地数据的测试结果表明，该算法具有匹配成功率高、准确率高、运算速度快等优点。     

Building Displacement Based on the Topological Structure

Map data at smaller scales than their source can result in spatial conflict, whereby map symbols become too close, or overlaid. Server map generalisation operators may be applied to solve this problem, including displacement. In this paper, we show how an optimisation algorithm, the snake algorithm, was used to displace multiple objects in order to resolve spatial conflicts and maintain important spatial relationships between objects during displacement. Two principles based on the snake algorithm are proposed in this paper. First, the truss structure mirroring spatial proximity relationships between buildings and between building and road is formed based on the weighted proximity graph derived from constrained Delaunay triangulations (CDT) in each map partition. In the weighted proximity graph, each connecting line is determined as a snake and as an element unit to assemble the global stiffness matrix in snake algorithm. Second, a buffer method that calculates force between a building and a road (or other linear features) or between pair of buildings is adopted in the snake algorithm. This avoids the imbalance phenomenon caused by different force calculation methods during the displacement. The feasibility of the approach is demonstrated in obtaining real geographic data. Finally, the results are cartographically usable and in particular, the spatial relationships between objects are preserved.     

Spatial‐Scene Similarity Queries

Assessing spatial scenes for similarity is difficult from a cognitive and computational perspective. Solutions to spatial‐scene similarity assessments are sensible only if corresponding elements in the compared scenes are identified correctly. This matching process becomes increasingly complex and error‐prone for large spatial scenes as it is questionable how to choose one set of associations over another or how to account quantitatively for unmatched elements. We develop a comprehensive methodology for similarity queries over spatial scenes that incorporates cognitively motivated approaches about scene comparisons, together with explicit domain knowledge about spatial objects and their relations for the relaxation of spatial query constraints. Along with a sound graph‐theoretical methodology, this approach provides the foundation for plausible reasoning about spatial‐scene similarity queries.