Scale- and orientation-invariant scene similarity metrics for image queries

In this paper we extend our previous work on shape-based queries to support queries on configurations of image objects. Here we consider spatial reasoning, especially directional and metric object relationships. Existing models for spatial reasoning tend to rely on pre-identified cardinal directions and minimal scale variations, assumptions that cannot be considered as given in our image applications, where orientations and scale may vary substantially, and are often unknown. Accordingly, we have developed the method of varying baselines to identify similarities in direction and distance relations. Our method allows us to evaluate directional similarities without a priori knowledge of cardinal directions, and to compare distance relations even when query scene and database content differ in scale by unknown amounts. We use our method to evaluate similarity between a user-defined query scene and object configurations. Here we present this new method, and discuss its role within a broader image retrieval framework.     

Algebraic approach to spatial reasoning

Abstract

A simple, exemplary system is described that performs reasoning about the spatial relationships between members of a set of spatial objects. The main problem of interest is to make sound and complete inferences about the set of all spatial relationships that hold between the objects, given prior information about a subset of the relationships. The spatial inferences are formalized within the framework of relation algebra and procedurally implemented in terms of constraint satisfaction procedures. Although the approach is general, the particular example employs a new ‘complete’ set of topological relationships that have been published elsewhere. In particular, a relation algebra for these topological relations is developed and a computational implementation of this algebra is described. Systems with such reasoning capabilities have many applications in geographical analysis and could be usefully incorporated into geographical information systems and related systems.     

Cardinal directions: a comparison of direction relation matrix and objects interaction matrix

How to express and reason with cardinal directions between extended objects such as lines and regions is an important problem in qualitative spatial reasoning (QSR), a common subfield of geographical information science and Artificial Intelligence (AI). The direction relation matrix (DRM) model, proposed by Goyal and Egenhofer in 1997, is one very expressive relation model for this purpose. Unlike many other relation models in QSR, the set-theoretic converse of a DRM relation is not necessarily representable in DRM. Schneider et al. regard this as a serious shortcoming and propose, in their work published in ACM TODS (2012), the objects interaction matrix (OIM) model for modelling cardinal directions between complex regions. OIM is also a tiling-based model that consists of two phases: the tiling phase and the interpretation phase. Although it was claimed that OIM is a novel concept, we show that it is not so different from DRM if we represent the cardinal direction of two regions a and b by both the DRM of a to b and that of b to a. Under this natural assumption, we give methods for computing DRMs from OIMs and vice versa, and show that OIM is almost the same as DRM in the tiling phase, and becomes less precise after interpretation. Furthermore, exploiting the similarity between the two models, we prove that the consistency of a complete basic OIM network can be decided in cubic time. This answers an open problem raised by Schneider et al. regarding efficient algorithms for reasoning with OIM.     

地理空间关系确定性描述与集成推理

地理要素的空间关系在GIS空间数据建模、空间分析、地图自动综合等方面起着重要作用,研究如何快速判断要素间空间关系是否发生变化,从而有效维护空间关系具有重要的科学意义。对目前有关地理空间关系确定性描述及其集成推理的研究成果进行综合分析与分类,分析其适应性与特点,并就该研究方向存在和需要解决的问题进行分析。     

A qualitative model for the simulation of traffic behaviours in a multi-lane environment

Qualitative modelling of spatial relationships has often been considered as a contextindependent task that aims at a reasoning model in generic form. Despite the primary interest in these models, there is still a sufficiently large scope for context-dependent reasoning in space and time. This paper proposes a qualitative spatial reasoning model, oriented to the modelling and simulation of several cars acting in a multi-lane circuit, which can be considered as an illustrative example of a constrained frame of reference. The modelling objects of interest are individual cars whose cardinal relationships to external cars and actions are modelled. This dynamic system is analysed, and a set of interrelationships is identified at different levels of abstraction, together with inference rules that model the displacement of several cars in a circuit. The potential of this model is illustrated and calibrated using an agent-based prototype.     

地理空间中的空间关系表达和推理

针对地理空间中的应用,归纳了在空间关系的表达与推理中不同于人工智能领域研究的一些特点:在人工智能领域,更注重建立形式化的推理系统;而在地理信息科学中,则需更关注地理空间的特点以及地物的地理语义。该文基于地理空间和地理现象的本质且顾及地理空间认知,总结了地理空间中空间关系表达和推理的特点,具体包括空间的有限性、地球的球面特征、地物的地理语义、地物形状的复杂性、面状地物、特殊的空间关系、空间关系的层次性与尺度相应原则、不确定性、三维与时态特性九方面;进而介绍了地理空间关系表达的两个应用,即地理信息检索和基于对象的图像分析。该文的探讨可为地理信息科学中的相关研究提供方向性指导。     

Information-associated join indices for spatial range search

Abstract

Spatial join indices are join indices constructed for spatial objects. Similar to join indices in relational database systems, spatial join indices improve efficiency of spatial join operations. In this paper, a spatial-information-associated join indexing mechanism is developed to speed up spatial queries, especially, spatial range queries. Three distance-associated join index structures: basic, ring-structured and hierarchical, are developed and studied. Such join indexing structures can be further extended to include orientation information for flexible applications, which leads to zone-structured and other spatial-information-associated join indices. Our performance study and analysis show that spatial-information-associated join indices substantially improve the performance of spatial queries and that different structures are best suited for different applications.     

多尺度地图空间相似关系基本问题研究

基于多尺度地图数据库建设中地图自动综合的终止判断条件,引出多尺度地图空间相似关系问题。基于集合论给出空间相似关系的定义,论述空间相似关系的5个性质,即反身性、对称性、非传递性、多尺度自相似性与尺度依赖性;并从图形相似和属性相似的角度论述多尺度地图空间相似关系的分类体系。该成果是研究地图自动综合和地图空间相似查询等的基础。     

A Review of “The Power of Place”

Two qualitative case studies, one focusing on K-12 teachers and the other on middle school students, explore key factors associated with using Geographic Information Systems in the classroom. In both studies, access to appropriate hardware is a critical barrier. Time is another critical barrier—time to learn the GIS software and time in the curriculum to incorporate GIS as a learning experience. In both case studies, learning the technology at the expense of learning spatial analysis was a danger, suggesting the need for conscious focus on the goal of using GIS to learn how to “do geography.”     

Integrative representation and inference of qualitative locations about points,lines, and polygons

Qualitative knowledge representation of spatial locations and relations is popular in many text-based media, for example, postings on social networks, news reports, and encyclopedia, as representing qualitative spatial locations is indispensable to infer spatial knowledge from them. However, an integrative model capable of handling direction-based locations of various spatial objects is missing. This study presents an integrative representation and inference framework about direction-based qualitative locations for points, lines, and polygons. In the framework, direction partitions of different types of reference objects are first unified to create a partition consisting of cells, segments, and corners. They serve as a frame of reference to locate spatial objects (e.g., points, lines, and polygons). Qualitative relations are then defined to relate spatial objects to the elements in a cell partition, and to form the model of qualitative locations. Last, based on the integrative representation, location-based reasoning mechanism is presented to derive topological relations between objects from their locations, such as point–point, line–line, point–line, point–polygon, line–polygon, and polygon–polygon relations. The presented model can locate any type of spatial objects in a frame of reference composed of points, lines, and polygons, and derive topological relations between any pairs of objects from the locations in a unified method.     

Spatial Thinking by Young Children: Neurologic Evidence for Early Development and “Educability”

Abstract

The human brain appears to have several “regions” that are structured to do different kinds of spatial thinking, according to a large and rapidly growing body of research in a number of disciplines. Building on a previous review of research with older children and adults, this article summarizes the research on spatial thinking by young children. Three conclusions: brain structures for spatial reasoning are fully functional at a very early age, adult intervention can enhance both use and representational ability, and practice in early grades is an important, perhaps even essential, part of the scaffold for later learning.     

A metaheuristic approach for efficient and effective sketch-to-metric map alignment

Sketching as a natural mode for human communication and creative processes presents opportunities for improving human–computer interaction in geospatial information systems. However, to use a sketch map as user input, it must be localized within the underlying spatial data set of the information system, the base metric map. This can be achieved by a matching process called qualitative map alignment in which qualitative spatial representations of the two input maps are used to establish correspondences between each sketched object and one or more objects in the metric map. The challenge is that, to the best of our knowledge, no method for matching qualitative spatial representations suggested so far is applicable in realistic scenarios due to excessively long runtimes, incorrect algorithm design or the inability to use more than one spatial aspect at a time. We address these challenges with a metaheuristic algorithm which uses novel data structures to match qualitative spatial representations of a pair of maps. We present the design, data structures and performance evaluation of the algorithm using real-world sketch and metric maps as well as on synthetic data. Our algorithm is novel in two main aspects. Firstly, it employs a novel system of matrices known as local compatibility matrices, which facilitate the computation of estimates for the future size of a partial alignment and allow several types of constraints to be used at the same time. Secondly, the heuristic it computes has a higher accuracy than the state-of-the-art heuristic for this task, yet requires less computation. Our algorithm is also a general method for matching labelled graphs, a special case of which is the one involving complete graphs whose edges are labelled with spatial relations. The results of our evaluation demonstrate practical runtime performance and high solution quality.     

Spatial strategies for parallel spatial modelling

Abstract

Abstract. To achieve high levels of performance in parallel geoprocessing, the underlying spatial structure and relations of spatial models must be accounted for and exploited during decomposition into parallel processes. Spatial models are classified from two perspectives, the domain of modelling and the scope of operations, and a framework of strategies is developed to guide the decomposition of models with different characteristics into parallel processes. Two models are decomposed using these strategies: hill-shading on digital elevation models and the construction of Delaunay Triangulations. Performance statistics are presented for implementations of these algorithms on a MIMD computer.     

Image‐based quality assessment of road databasesX

In this paper an approach to the automatic quality assessment of existing geo‐spatial data is presented. The necessary reference information is derived automatically from up‐to‐date digital remotely sensed images using image analysis methods. The focus is on the quality assessment of roads as these are among the most frequently changing objects in the landscape. In contrast to existing approaches for quality control of road data, the data to be assessed and the objects extracted from the images are modelled and processed together. A geometric‐topologic relationship model for the roads and their surroundings is defined. Context objects such as rows of trees support the quality assessment of road vector data as they may explain gaps in road extraction. The extraction and explicit incorporation of these objects in the assessment of a given road database give stronger support for or against its correctness.

During the assessment existing relations between road objects from the database and extracted objects are compared to the modelled relations. The certainty measures of the objects are integrated into this comparison. Normally, more than one extracted object gives evidence for a road database object; therefore, a reasoning algorithm which combines evidence given by the extracted objects is used. If the majority of the total evidence argues for the database object and if a certain amount of this database object is covered by extracted objects, the database object is assumed to be correct, i.e. it is accepted, otherwise it is rejected. The procedure is embedded into a two‐stage graph‐based approach which exploits the connectivity of roads and results in a reduction of false alarms. The algorithms may be incorporated into a semi‐automatic environment, where a human operator only checks those objects that have been rejected.

The experimental results confirm the importance of the employed advanced statistical modelling. The overall approach can reliably assess the roads from the given database, using road and context objects which have been automatically extracted from remotely sensed imagery. Sensitivity analysis shows that in most cases the chosen two‐stage graph‐approach reduces the number of false decisions. Approximately 66% of the road objects have been accepted by the developed approach in an extended test area, 1% has been accepted though incorrect. Those false decisions are mainly related to the lack of modelling road junction areas.     

A scale-explicit model for checking directional consistency in multi-resolution spatial data

Multi-resolution spatial data always contain the inconsistencies of topological, directional, and metric relations due to measurement methods, data acquisition approaches, and map generalization algorithms. Therefore, checking these inconsistencies is critical for maintaining the integrity of multi-resolution or multi-source spatial data. To date, research has focused on the topological consistency, while the directional consistency at different resolutions has been largely overlooked. In this study we developed computation methods to derive the direction relations between coarse spatial objects from the relations between detailed objects. Then, the consistency of direction relations at different resolutions can be evaluated by checking whether the derived relations are compatible with the relations computed from the coarse objects in multi-resolution spatial data. The methods in this study modeled explicitly the scale effects of direction relations induced by the map generalization operator – merging, thus they are efficient for evaluating consistency. The directional consistency is an essential complement to topological and object-based consistencies.     

Indexing large geographic datasets with compact qualitative representation

This paper develops a new mechanism to efficiently compute and compactly store qualitative spatial relations between spatial objects, focusing on topological and directional relations for large datasets of region objects. The central idea is to use minimum bounding rectangles (MBRs) to approximately represent region objects with arbitrary shape and complexity and only store spatial relations that cannot be unambiguously inferred from the relations of corresponding MBRs. We demonstrate, both in theory and practice, that our approach requires considerably less construction time and storage space, and can answer queries more efficiently than the state-of-the-art methods.     

基于场所的GIS研究

探讨从地理空间认知出发,实现基于场所的GIS（PB—GIS）的相关问题。PB—GIS以场所为核心,显式表达地理空间知识,并遵循特定规则进行定性空间推理,从而服务于空间行为决策。比较PB—GIS与基于坐标的GIS（CB—GIS）之间的差异和适合解决的问题,并描述定性空间推理的特点及其在PB—GIS中的应用。在分析实现PB—GIS的关键技术基础上,采用三层架构设计了一个PB-GIS的概念体系结构。     

Computing the fuzzy topological relations of spatial objects based on induced fuzzy topology

For modeling the topological relations between spatial objects, the concepts of a bound on the intersection of the boundary and interior, and the boundary and exterior are defined in this paper based on the newly developed computational fuzzy topology. Furthermore, the qualitative measures for the intersections are specified based on the α‐cut induced fuzzy topology, which are (A_α∧?A)(x)<1?α and ((A^c)_α∧?A)(x)<1?α. In other words, the intersection of the interior and boundary or boundary and exterior are always bounded by 1?α, where α is a value of a level cutting. Specifically, the following areas are covered: (a) the homeomorphic invariants of the fuzzy topology; (b) a definition of the connectivity of the newly developed fuzzy topology; (c) a model of the fuzzy topological relations between simple fuzzy regions in GIS; and (d) the quantitative values of topological relations can be calculated.