Search

Polyline and building simplification remain challenging in cartography. Most proposed algorithms are geometric-based and rely on specific rules. In this study, we propose a deep learning approach to simplify polylines and buildings based on a graph autoencoder (GAE). The model receives the coordinates of line vertices as inputs and obtains a simplified representation by reconstructing the original inputs with fewer vertices through pooling, in which the graph convolution based on graph Fourier transform is used for the layer-by-layer feature computation. By adjusting the loss functions, constraints such as area and shape preservation and angle-characteristic enhancement are flexibly configured under a unified learning framework. Our results confirmed the applicability of the GAE approach to the multi-scale simplification of land-cover boundaries and contours by adjusting the number of output nodes. Compared with existing Douglas‒Peukcer, Fourier transform, and Delaunay triangulation approaches, the GAE approach was superior in achieving morphological abstraction while producing reasonably low position, area, and shape changes. Furthermore, we applied it to simplify buildings and demonstrated the potential for preserving the diversified characteristics of different types of lines. [ABSTRACT FROM AUTHOR]

ABSTRACTPolyline simplification is crucial for cartography and spatial database management. In recent decades, various rule-based algorithms for vector polyline simplification have been proposed. However, most existing algorithms lack parameter self-adaptive capabilities and require repeated manual parameter adjustments when applied to different polylines. While deep-learning-based methods have recently been introduced for raster polyline image simplification, they cannot achieve end-to-end simplification when the input data and output results are vector polylines. This paper proposes a new deep-learning-based method for vector polyline simplification by integrating both the vector and raster features of the polyline. Specifically, a deep separable convolutional residual neural network was first used to extract the convolutional features of each image. Then, the region proposal network was modified to generate proposal boxes using vector coordinates, and these proposal boxes were used to locate the convolutional feature maps of bends. Finally, convolutional feature maps were fed into a binary classification network to identify unimportant vertices that should be omitted for vector polyline simplification. The experimental results indicated that the proposed method can exploit raster and vector features to achieve automatic and effective polyline simplification without prior map generalization knowledge and manual settings of rules and parameters. The polyline simplification results of the proposed method have a higher compression ratio of coordinate points and lower shape deformation and deviation than the results generated by the classic Wang and Müller (WM) algorithm and Support Vector Machine (SVM) based algorithm, which shows the potential of the proposed method for future applications in map generalization.

The present paper presents techniques for polyline simplification based on an artificial neural network within the constraints of generalization knowledge. The proposed method measures polyline shape characteristics that influence polyline simplification using abstracted descriptors and then introduces these descriptors into the artificial neural network as input properties. In total, 18 descriptors categorized into three types are presented in detail. In a second approach, map simplification principles are abstracted as controllers, imposed after the output layer of the trained artificial neural network to make the polyline simplification comply with these principles. This study worked with three controllers – a basic controller and two knowledge-based controllers. These descriptors and controllers abstracted from generalization knowledge were tested in experiments to determine their efficacy in polyline simplification based on the artificial neural network. The experimental results show that the utilization of abstracted descriptors and controllers can constrain the artificial neural network-based polyline simplification according to polyline shape characteristics and simplification principles. [ABSTRACT FROM AUTHOR]

Maps obtained from various sensors or surveying instruments provide important geographic information for users. Buildings are critical components of various city-area maps. In this paper, we present a constrained building boundary simplification method based on the partial total least squares (PTLS) method. Simplification of building boundaries may cause some data quality problems, such as geometric displacements, right angles changed into non-right angles, and area inconsistency at different scales. Therefore, in this paper, a linear fitting model based on the PTLS method is constructed for building boundaries with the aim of reducing the total positional difference. Furthermore, end-point, right-angle, and area constraints are constructed at the same time to maintain the right angles and areas of the building. The simplification results are obtained by solving the proposed constrained model by using the PTLS method with constraints. The proposed method was applied in a building boundary simplification experiment. The results showed that the proposed method maintains the right angles and areas of buildings and reduces the geometric displacements of buildings after the simplification. [ABSTRACT FROM AUTHOR]

Discretization is the process of converting continuous values into discrete values. It is a preprocessing step of several machine learning and data mining algorithms and the quality of discretization may drastically affect the performance of these algorithms. In this study we propose a discretization algorithm, namely line fitting-based discretization (lFIT), based on the Ramer-Douglas-Peucker algorithm. It is a static, univariate, unsupervised, splittingbased, global, and incremental discretization method where intervals are determined based on the Ramer-Douglas- Peucker algorithm and the quality of partitioning is assessed based on the standard error of the estimate. To evaluate the performance of the proposed method, a set of experiments are conducted on ten benchmark datasets and the achieved results are compared to those obtained by eight state-of-the-art discretization methods. Experimental results show that lFIT achieves higher predictive accuracy and produces less number of inconsistency while it generates larger number of intervals. The obtained results are also validated through Friedman's test and Holm's post hoc test which revealed the fact that lFIT produces discretization schemes that statistically comply both with supervised and unsupervised discretization methods. [ABSTRACT FROM AUTHOR]

Streets are essential entities of urban terrain and their automatized extraction from airborne sensor data is cumbersome because of a complex interplay of geometric, topological and semantic aspects. Given a binary image, representing the road class, centerlines of road segments are extracted by means of skeletonization. The focus of this paper lies in a well-reasoned representation of these segments by means of geometric primitives, such as straight line segments as well as circle and ellipse arcs. We propose the fusion of raw segments based on similarity criteria; the output of this process are the so-called chains which better match to the intuitive perception of what a street is. Further, we propose a two-step approach for chain-wise generalization. First, the chain is pre-segmented using circlePeucker and finally, model selection is used to decide whether two neighboring segments should be fused to a new geometric entity. Thereby, we consider both variance-covariance analysis of residuals and model complexity. The results on a complex data-set with many traffic roundabouts indicate the benefits of the proposed procedure. [ABSTRACT FROM AUTHOR]

As a basic and significant operator in map generalization, polyline simplification needs to work across scales. Perkal’sε-circle rolling approach, in which a circle with diameterεis rolled on both sides of the polyline so that the small bend features can be detected and removed, is considered as one of the few scale-driven solutions. However, the envelope computation, which is a key part of this method, has been difficult to implement. Here, we present a computational method that implements Perkal’s proposal. To simulate the effects of a rolling circle, Delaunay triangulation is used to detect bend features and further to construct the envelope structure around a polyline. Then, different connection methods within the enveloping area are provided to output the abstracted result, and a strategy to determine the best connection method is explored. Experiments with real land-use polygon data are implemented, and comparison with other algorithms is discussed. In addition to the scale-specificity inherited from Perkal’s proposal, the results show that the proposed algorithm can preserve the main shape of the polyline and meet the area-maintaining constraint during large-scale change. This algorithm is also free from self-intersection. [ABSTRACT FROM AUTHOR]

This paper proposes a new method for rapid prediction of wildfire spread, which employs computational wildfire simulations by FARSITE and assimilates the simulation results with actual observation data by means of an ensemble Kalman filter. To expedite data assimilation, the wildfire perimeter is represented by a two-dimensional polyline simplification algorithm. In addition, to facilitate the data assimilation, a new process is developed to relate the prediction results with the actual observation data. The proposed method is tested and demonstrated by an example wildfire spread scenario generated based on actual climate, topography, and vegetation. The results confirm that the polyline simplification algorithm can drastically reduce the computational time required for data assimilation while maintaining the accuracy of predictions. The proposed method is expected to serve as a core algorithm for near-real-time prediction and data-driven updating of wildfire spread. • A new rapid prediction algorithm is developed for wildfire spread using EnKF and FARSITE. • The proposed algorithm simplifies the wildfire perimeter by applying polyline simplification. • To apply EnKF, a new method of reconstructing simplified perimeters is also proposed. • The algorithm significantly reduces computation time while maintaining prediction accuracy. • The proposed method is successfully demonstrated by wildfire spread scenarios. [ABSTRACT FROM AUTHOR]

Polyline simplification is an important task in map generalization. Several solutions have been developed in order to perform this task automatically, but the vast majority of them consider that the objective line to simplify is lying on the plane. One of the most widely used methods is the so-called Douglas–Peucker algorithm, which is fast and in most cases produces good results. However, the Douglas–Peucker method was defined in its original form in order to be applied to polylines contained in the Euclidean 2D space, and it can lead to inconsistent results such as self-intersections. In this work, a robust (results without self-intersections) variation of the Douglas–Peucker for polylines on the surface of the sphere is presented. It produces correct results regardless of the morphology of the original line and the tolerance parameter size. The algorithm is coded in standard C99 and it can be compiled for serial or parallel execution via OpenMP. Both, the algorithm itself and a program implementing it are distributed as free software. The solution validity was tested using the GSHHG geography database, which can be obtained free through the Web. Results about output accuracy, execution speed, and parallel implementation scalability are presented. [ABSTRACT FROM AUTHOR]

Abstract: Line simplification is an important task in map generalization, in traditional paper series as well as in geographic information systems and web map server services. Using the adequate method an accurate representation of the original elements should be obtained by suppression of redundant information while maintaining the shape of the original elements according to the new scale. To that effect one of the most widely used algorithms is the so-called Douglas–Peucker algorithm. It can lead to inconsistent results such as self-intersections or intersections with other elements, so the operator's supervision is necessary following the automatic treatment. In this piece of work a robust and easy-to-implement variation of the Douglas–Peucker algorithm for individual line simplification in two dimensions is presented. The robustness of the new algorithm is based on the concept of intersection of segments and it can be easily implemented in parallel. The new algorithm brings about correct results regardless of tolerance and morphology of the original line or polygon. The algorithm is coded in standard C99 and it can be compiled for serial or parallel execution via OpenMP. Both the algorithm itself and a program that implements it are distributed as free software. The validity of the solution was tested using the GSHHG geography database that can be obtained free through the Web. Results about accuracy of the output, execution speed and scalability of the parallel implementation are presented. [Copyright &y& Elsevier]

In this work we introduce an algorithm to approximate the external shape of an irregular polyline containing some cycles and interlacements. The output consists of a counterclockwise closed walk still containing only some cycles that, with the addition of one more step, can be 'opened' in a suitable way to produce a Hamiltonian circuit. Moreover, the time cost of the algorithm is explained and the data structures introduced are described. The proposed algorithm applies to the polyline described by all the input data points as well as the polyline returned using a simplification/reduction method. We also describe how the entire algorithm, or some part of it, can be applied to the output of some well-known reduction methods to solve particular problems which may arise. We carried out a first implementation of the algorithm in MATLAB for its capability to provide both numerical and graphical tools within the same programming language as well as specific features offered by its Toolboxes and by the community of its users. We shall refer to it when reporting some of the results. [ABSTRACT FROM AUTHOR]