How to achieve consistency for 3D city models

Consistency is a crucial prerequisite for a large number of relevant applications of 3D city models, which have become more and more important in GIS. Users need efficient and reliable consistency checking tools in order to be able to assess the suitability of spatial data for their applications. In this paper we provide the theoretical foundations for such tools by defining an axiomatic characterization of 3D city models. These axioms are effective and efficiently supported by recent spatial database management systems and methods of Computational Geometry or Computer Graphics. They are equivalent to the topological concept of the 3D city model presented in this paper, thereby guaranteeing the reliability of the method. Hence, each error is detected by the axioms, and each violation of the axioms is in fact an error. This property, which is proven formally, is not guaranteed by existing approaches. The efficiency of the method stems from its locality: in most cases, consistency checks can safely be restricted to single components, which are defined topologically. We show how a 3D city model can be decomposed into such components which are either topologically equivalent to a disk, a sphere, or a torus, enabling the modeling of the terrain, of buildings and other constructions, and of bridges and tunnels, which are handles from a mathematical point of view. This enables a modular design of the axioms by defining axioms for each topological component and for the aggregation of the components. Finally, a sound, consistent concept for aggregating features, i.e. semantical objects like buildings or rooms, to complex features is presented.     

How to Get 3-D for the Price of 2-D—Topology and Consistency of 3-D Urban GIS

This article deals with topological concepts and models which are necessary to represent three-dimensional urban objects in a geographical information system (GIS). Depending on the shape and the representation of features, several classes with increasing topological complexity are identified and described. This complexity has strong impacts on the models and tools which are required to represent, manage and edit the data. One specific model we call 2.8-D map is identified, which covers many 3-D applications in GIS. It is a slight extension of a 2-D or 2.5-D model and preserves the algorithmic and conceptual simplicity of the 2-D case as much as possible. The model is described in a formal way. Integrity axioms are given, which detect errors in corresponding data sets safely and guarantee the consistency of 2.8-D maps in a mathematically sound and provable way. These axioms are effectively and efficiently checkable by automatic procedures. The model extends digital terrain models (2.5-D) by allowing for vertical walls and projections like balconies or ledges. The conceptual simplicity is due to the two-dimensional topology of the model. Thus bridges and tunnels are special cases; it is shown how to detect and handle these cases efficiently. Based on this model, thematic objects and their aggregation structures are defined in a consistent way.     

Provably correct and complete transaction rules for updating 3D city models

The shapes of our cities change very frequently. These changes have to be reflected in data sets representing urban objects. However, it must be assured that frequent updates do not affect geometric-topological consistency. This important aspect of spatial data quality guarantees essential assumptions on which users and applications of 3D city models rely: viz. that objects do not intersect, overlap or penetrate mutually, or completely cover one another. This raises the question how to guarantee that geometric-topological consistency is preserved when data sets are updated. Hence, there is a certain risk that plans and decisions which are based on these data sets are erroneous and that the tremendous efforts spent for data acquisition and updates become vain. In this paper, we solve this problem by presenting efficient transaction rules for updating 3D city models. These rules guarantee that geometric-topological consistency is preserved (Safety) and allow for the generation of arbitrary consistent 3D city models (Completeness). Safety as well as completeness is proven with mathematical rigor, guaranteeing the reliability of our method. Our method is applicable to 3D city models, which define—besides the terrain surface—complex spatial objects like buildings with rooms and storeys as interior structures, as well as bridges and tunnels. Those objects are represented as aggregations of solids, and their surfaces are complex from a topology point of view. 3D GIS models like CityGML, which are widely used to represent cities, provide the means to define semantics, geometry and topology, but do not address the problem of maintaining consistency. Hence, our approach complements CityGML.     

Persistence-based handle and tunnel loops computation revisited for speed up

Loops in surfaces associated with topological features such as handles and tunnels are important entities in many applications including surface parameterization, feature identification, and topological simplification. Recently, a persistent homology based algorithm has been proposed to compute them. The algorithm has several advantages including its simplicity, combinatorial nature and independence from computing other extra structures. In this paper, we propose changes to this loop computation algorithm based on some novel observations. These changes reduce the computation time of the algorithm dramatically. In particular, our experimental results show that the suggested changes achieve considerable speed up for large data sets without sacrificing loop qualities.     

Classification and Concept Consistency

Abstract

This article investigates the extent to which undergraduates consistently use a single mechanism as a basis for classifying mathematical objects. We argue that the concept image/concept definition distinction focuses on whether students use an accepted definition but does not necessarily capture the more basic notion that there should be a fixed basis for classification. We examine students’ classifications of real sequences before and after exposure to definitions of increasing and decreasing; we develop an abductive plausible explanations method to estimate the consistency within the participants’ responses and suggest that this provides evidence that many students may lack what we call concept consistency.     

Wire frame: A reliable approach to build sealed engineering geological models

The technique of 3D geological modeling (3DGM) is an effective tool for representing complex geological objects. In order to improve the accuracy of geological models applied in numerical simulation methods such as finite elements and finite differences, we can use 3DGM as a modeling tool. To do this, however, 3DGM must provide the ability to model geological and artificial objects in a unified way, and its geological model must be seamless for mesh generation. We present the concept of a sealed engineering geological model (SEGM), and describe its topological representation. Three kinds of conditions: geometric continuity, topological consistency and geological consistency, which must be satisfied by SEGM, are discussed in detail. A new method for constructing an SEGM based on a wire frame is proposed. It includes three main components: wire frame construction, interface modification and reconstruction, and block tracing. Building a unitary wire frame, which is composed of many simple arcs and connects all interfaces seamlessly, is the key of this method. An algorithm, involving two intersections computations and partition of simple arcs, is proposed for building a wire frame. Additionally, we also propose a local iterative algorithm for computing fault traces. As an example, we build an SEGM for the dam area of a hydraulic engineering project in the HuNan province of China.     

面向对象分类方法在铁尾矿堆快速提取中的应用研究

以黄石市大冶铁矿区为例,利用面向对象分类方法进行铁尾矿堆信息快速提取试验研究。首先,根据WorldView-2影像特点,充分利用其丰富的光谱特征及精确的空间形状特征进行图像分割,突出影像对象边缘、重现地物实际存在情况;其次,分析影像对象的光谱、形状、纹理、拓扑关系等特征信息,建立分类规则进行分类,提取出尾矿堆信息。为了进一步提高分类精度,可以利用eCognition软件RS/GIS数据集成功能,在面向对象分类结果上进行目视解译。试验证明,面向对象分类方法适用于提取矿区尾矿堆信息,是高分辨率遥感影像自动分类的理想选择。     

Topological simplification of isosurfaces in volumetric data using octrees

Volumetric data, such as output from CT scans or laser range scan processing methods, often have isosurfaces that contain topological noise—small handles and holes that are not present in the original model. Because this noise can significantly degrade the performance of other geometric processing algorithms, we present a volumetric method that removes the topological noise and patches holes in undefined regions for a given isovalue. We start with a surface completely inside the isosurface of interest and a surface completely outside the isosurface. These surfaces are expanded and contracted, respectively, on a voxel-by-voxel basis. Changes in topology of the surfaces are prevented at every step using a local topology test. The result is a pair of surfaces that accurately reflect the geometry of the model but have simple topology. We represent the volume in an octree format for improved performance in space and time.     

Enhancing accuracy and expressive power of range query answers over incomplete spatial databases via a novel reasoning approach

Modern spatial database applications built on top of distributed and heterogeneous spatial information sources such as conventional spatial databases underlying Geographical Information Systems (GIS), spatial data files and spatial information acquired or inferred from the Web, suffer from data integration and topological consistency problems. This more-and-more conveys in incomplete information, which makes answering range queries over incomplete spatial databases a leading research challenge in spatial database systems research. A significant instance of this setting is represented by the application scenario in which the geometrical information on a sub-set of spatial database objects is incomplete whereas the spatial database still stores topological relations among these objects (e.g., containment relations). Focusing on the spatial database application scenario above, in this paper we propose and experimentally assess a novel technique for efficiently answering range queries over incomplete spatial databases via integrating geometrical information and topological reasoning. We also propose I-SQE (Spatial Query Engine for Incomplete Information), an innovative query engine implementing this technique. Our proposed technique results not only effective but also efficient against both synthetic and real-life spatial data sets, and it finally allows us to enhance the quality and the expressive power of retrieved answers by meaningfully taking advantages from the amenity of representing spatial database objects via both the geometrical and the topological level.     

Mining multiple-level spatial association rules for objects with a broad boundary

Spatial data mining, i.e., mining knowledge from large amounts of spatial data, is a demanding field since huge amounts of spatial data have been collected in various applications, ranging from remote sensing to geographical information systems (GIS), computer cartography, environmental assessment and planning. The collected data far exceeds people's ability to analyze it. Thus, new and efficient methods are needed to discover knowledge from large spatial databases. Most of the spatial data mining methods do not take into account the uncertainty of spatial information. In our work we use objects with broad boundaries, the concept that absorbs all the uncertainty by which spatial data is commonly affected and allows computations in the presence of uncertainty without rough simplifications of the reality. The topological relations between objects with a broad boundary can be organized into a three-level concept hierarchy. We developed and implemented a method for an efficient determination of such topological relations. Based on the hierarchy of topological relations we present a method for mining spatial association rules for objects with uncertainty. The progressive refinement approach is used for the optimization of the mining process.     

Ontology-based topological representation of remote-sensing images

This article proposes an ontology-based topological representation of remote-sensing images. Semantics, especially related to the topological relationships between the objects represented, are not explicit in remote-sensing images and this fact limits spatial analysis. Our aim is to provide an explicit ontological definition of the topological relations between objects in the image using the Quadtree data structure for spatial indexing. This structure is explicitly defined in an ontology allowing the automatic interpretation of the representations obtained, taking into account the topological relations and increasing the spatial analytical capabilities. This representation has been validated by a case study of semantic retrieval based on the normalized difference vegetation index (NDVI), taking into account the topological relations between NDVI regions in images. In the experiments, we compare the effectiveness of results from eight queries using four traditional supervised image classification algorithms and the proposal representation. The experimental results show the feasibility of the proposal, supporting the concept of the image retrieval process providing a semantic complement to remote-sensing images. The proposed representation contributes to incorporation of semantics into geographical data, especially to remote-sensing images, and it can be used to develop applications in the Geospatial Semantic Web.     

Developing GIS Applications with Objects: A Design Patterns Approach

In this paper we present an object-oriented approach for designing GIS applications; it combines well known software engineering practices with the use of design patterns as a conceptual tool to cope with recurrent problems appearing in the GIS domain. Our approach allows the designer to decouple the conceptual definition of application objects from their spatial representation. In this way, GIS applications can evolve smoothly, because maintenance is achieved by focusing on different concerns at different times. We show that our approach is also useful to support spatial features in conventional applications built with object-oriented technology. The structure of this paper is as follows: We first introduce design patterns, an efficient strategy to record design experience; then we discuss the most common design problems a developer of GIS applications must face. The core of our method is then presented by explaining how the use of decorators helps in extending objects to incorporate spatial attributes and behavior. Next, we analyze some recurrent design problems in the GIS domain and present some new patterns addressing those problems. Some further work is finally discussed.     

Topological Active Models optimization with Differential Evolution

The Topological Active Model is an active model focused on segmentation tasks. It provides information about the surfaces and the inside of the detected objects in the scene. The segmentation process turns into a minimization task of the energy functions which control the model deformation. In this work we propose a new optimization method of the segmentation model that uses Differential Evolution as an alternative evolutionary method that minimizes the decisions of the designer with respect to others such as genetic algorithms. Moreover, we hybridized Differential Evolution with a greedy search to integrate the advantages of global and local searches at the same time that the segmentation speed is improved. We also included in the local search the possibility of topological changes to perform a better adjustment in complex surfaces, topological changes that introduce the necessary mechanism to divide the mesh in the case of the presence of several objects in the scene.     

Geometry-aware domain decomposition for T-spline-based manifold modeling

This paper presents a new and effective method to construct manifold T-splines of complicated topology/geometry. The fundamental idea of our novel approach is the geometry-aware object segmentation, by which an arbitrarily complicated surface model can be decomposed into a group of disjoint components that comprise branches, handles, and base patches. Such a domain decomposition simplifies objects of arbitrary topological type into a family of genus-zero/one open surfaces, each of which can be conformally parameterized into a set of rectangles. In contrast to the conventional decomposition approaches, our method can guarantee that the cutting locus are consistent on the parametric domain. As a result, the resultant T-splines of decomposed components are automatically glued and have high-order continuity everywhere except at the extraordinary points. We show that the number of extraordinary points of the domain manifold is bounded by the number of segmented components. Furthermore, the entire mesh-to-spline data conversion pipeline can be implemented with full automation, and thus, has potential in shape modeling and reverse engineering applications of complicated real-world objects.     

Automatic vectorization of segmented road networks by geometrical and topological analysis of high resolution binary images

In this paper, a new method in order to achieve the geometrical and topological definition of extracted road networks is presented. Starting from a raster binary image where a road network is depicted, this algorithm seeks the automatic raster – vector conversion based on skeleton extraction and graph theory and using GIS database if it is available. The last goal of this method is to provide a numerical structured file which includes the geometric definition for all roads as well as the topologic relations between them. The applied technique comprises six steps. In the first step, the quality of the binary image is improved through a noise cleaning process. In the second step, parallel edges of road network are smoothed by means a generalization process. In the third step, skeleton is extracted applying a known and efficient method which some years ago was published. The fourth step consists in constructing the graph and generating the different cartographic objects which compose the road network. In this phase, GIS information can be used in order to improve the result. In the fifth step, objects are numerically adjusted by means of polynomial adjustment in the opened objects case, and using a reiterative polygonal adjustment in the sharp objects case. In the last step, mathematical morphology is applied to validate topologically the geometrical adjustment. For it, the junction nodes are analyzed for changing automatically their coordinates in order to achieve a topologically correct road network vectorization. Finally, objects are structured according to cartographic criteria and a numerical file with the vectorized road network is provided. Experimental results show the validity of this approach.     

形状自适应的二维水印方法

通过对空间数据的拓扑一致性问题的分析,给出了一种基于拓扑的空间数据模型,在此基础上提出了一种空间拓扑规则发现机制.利用所得的空间拓扑规则,判断空间数据是否具有拓扑不一致性,进而采取相应的策略进行拓扑一致性维护,以提高空间数据的质量.     

Affine-invariant geodesic geometry of deformable 3D shapes

Natural objects can be subject to various transformations yet still preserve properties that we refer to as invariants. Here, we use definitions of affine-invariant arclength for surfaces in R³ in order to extend the set of existing non-rigid shape analysis tools. We show that by re-defining the surface metric as its equi-affine version, the surface with its modified metric tensor can be treated as a canonical Euclidean object on which most classical Euclidean processing and analysis tools can be applied. The new definition of a metric is used to extend the fast marching method technique for computing geodesic distances on surfaces, where now, the distances are defined with respect to an affine-invariant arclength. Applications of the proposed framework demonstrate its invariance, efficiency, and accuracy in shape analysis.     

一个基于对象代理模型的多表现地理信息系统

文中提出了一种基于对象代理模型的实现多表现GIS的新方法。通过地理对象的代理对象来定义多表现,因此代理对象可以用来表示对象的视角多样性和角色多样性。通过对象更新迁移可以支持动态分类和系统一致性维护。另外,对象及其代理对象之间的双向指针使得跨类查询变得非常容易,从而可以扩展查询的范围。文中实现了一个基于对象代理模型的多表现GIS原型,性能测试表明该方法比传统的方法更加有效。     

TopoPlan: a topological path planner for real time human navigation under floor and ceiling constraints

In this article we present TopoPlan, a topological planner dedicated to real-time humanoid path-planning and motion adaptation to floor and ceiling constraints inside complex static environments. This planner analyzes unstructured 3D triangular meshes in order to automatically determine their topology. The analysis is based on a prismatic spatial subdivision which is analyzed, taking into account humanoid characteristics, in order to extract navigable surfaces and precisely identify environmental constraints such as floors, ceilings, walls, steps and bottlenecks. The technique also provides a lightweight roadmap computation covering all accessible free space. We demonstrate the properties of our topological planner within the context of two reactive motion control processes: an on-the-fly trajectory optimization and foot print generation process that correctly handles climbing of complex staircases, and a reactive ceiling adaptation process that handles beam avoidance and motion adaptation to irregular floors and ceilings. We further show that the computation cost of these processes is compatible with the real time animation of several dozens of virtual humans.