Vector Map Simplification Using Poyline Curvature

Our method performs on all polylines in a vector map and segment polylines by feature points that reflects the object shape. Then it simplifies the segments so that the area difference is minimized. The detail process of our simplification is as follows.

We extract feature points using DP, SF, and TF algorithms. Figure 2 shows parameters for three algorithms; the maximum perpendicular distance d_max for DP algorithm, the angle tolerance ϴ for sector bound for SF algorithm, and the length threshold l_th and orientation angle threshold ∆ϴ_th of a segment line for TF algorithm. Given a polyine L in any layer, let us consider that L consists of N vertices, L = {υ₀, υ₁,…, υ_N−1}, and a vertex has two coordinate values υ_i = {x_i, y_i}. We generate three simplified polylines of a polyline L using DP, SF, TF algorithms.

Fig. 2. Parameters for DP, SF, and TF algorithms.

Download Original Figure

We define feature points F_L for a polyline L as vertices that exist in three simplified polylines L_DP, L_SF, L_TF ; $F_L = \text{{}{\dot{v}}_k|k\in [1,N_F]\}$ for ${\dot{v}}_k\ne v_0,v_{N-1}$ and ${\dot{v}}_k\in L_{DP}$ and ${\dot{v}}_k\in L_{SF}$ and ${\dot{v}}_k\in L_{TF}$. We use feature points as break points for segmenting polyline. Thus, a polyline L is segmented to N_F sections S = {S_k|k ∈[0, N_F − 1]} using N_F feature points. A section S_k consists of k − 1th feature point ${\dot{v}}_{k-1}$ and kth feature point ${\dot{v}}_k$ and middle vertices between two feature points;

Our method simplifies a polyline L as a unit of segmented section S_k using DP, SF, and TF algorithms. Thus, we assign one among three algorithms to a section S_k using the minimum area difference (MAD) and then simplify a section S_k by an assigned algorithm. The minimum area difference (MAD) measures how different the simplified polyline is with the original polyline. We explain how to calculate MAD for a section in next subsection.

We use the weighting factor α for controlling the simplification intensity and for generating vector maps with different precisions. Thus, we set parameters for three algorithms by the weighting factor and initial parameters.

where α ≥ −1

Let us look at how to compute MAD for a polyline, which is used for simplifying vertices while preserving the shape of original polyline. A section S_k = {υ_l, υ_l+1,⋯, υ_l+Nk} likes a sub-polyline with the start vertex and end vertex of feature points. The process for computing MAD, MAD_k, of a section is as follows.

Since A_k for an original polyline is always higher than ${\text{A}}_{\text{k}}^{\text{DP}}\text{,}{\text{A}}_{\text{K}}^{\text{SF}}\text{,}{\text{A}}_{\text{K}}^{\text{TF}}$ for simplified polylines, the differences ${\text{e}}_{\text{K}}^{\text{DP}}\text{,}{\text{e}}_{\text{K}}^{\text{SF}}\text{,}{\text{e}}_{\text{k}}^{\text{TF}}$ are over zero. Define MAD_k for S_k as the minimum among $e_K^{DP},e_K^{SF},e_k^{TF}.$

δ₀ and ε₀ are initial distance threshold for DP and SF and l_th,0 and ∆ϴ₀ are initial length threshold and initial angle threshold for TF. In this paper, we set δ₀, ε₀, l_th,0 to 1[m] and set ∆ϴ₀ to 5°.

The weighting factor α can control the compression ratio and the number of simplified vertices. If α = –1, a polyline do not be simplified. If α increases from -1, the simplified vertices increase while the data capacity decrease. However, the increased α produces the degradation of shape.

We separate the data of vertices in a simplified polyline L^′ to two parts; integer parts V^I and fractional parts V^R. Fractional parts are converted to integer types by the reciprocal number of the precision c that indicates the precision level of map data. Thus, two data of integer part and fractional part of a vertex υ′_j can be defined by

for all j ∈ [0, M − 1].

The integer part of vertex data represents the primary position of vector map. Therefore, our method compresses V^I with lossless using the bounding box of object MBR. We firstly compute the first-order derivative vector of integer part on the left-top point MBR_min of MBR

and the average derivative vector $\overline{\Delta v^I}$. Then we compute the second-order derivative vector ${\Delta }^2{v}_j^I$ as follows.

All integer parts V^I are converted to the magnitudes and signs of the second-order derivative vectors ${\Delta }^2{\upsilon }_j^I;\left\{\text{sign}\left({\Delta }^2{\upsilon }_j^I\right),\left|{\Delta }^2{\upsilon }_j^I\right|\right\}.$

The fractional part represents the detail precision of vector map. This part is sensitive to small deviation unlike integer part and is little correlated to each other. We separates fractional parts to precision data as a unit of 8-bit and rearranges precision data by precision levels. Example, the data of nth. precision level for ${\upsilon }_j^R$ can be defined as

This compression enables the vertex data to be transmitted or stored to different precision levels or preferred precision levels.

From the above processes, the integer part V^I and fractional part V^R for a polyline L can be converted to data for compressing. The coded data for a polyline has the structure of a polyline label (object index), a size of coded data, a number of vertices, a MBR coordinate value, and a payload, as shown in Figure 3. A MBR is for easy access to a polyline. A payload is the coded data of integer part and fractional part. Since the compression and recovery are performed as the unit of a polyline object, our method makes the random access of polyline objects easy.

Fig. 3. Structure of coded polyline data.

Download Original Figure

Our experiment evaluated the subject quality between the original map and compressed map. Figures 4(a),4(b) show full layers of original maps and compressed maps. From these figure, we know that though about 29% and 20% vertices are removed in compressed vector maps, there are no visually difference between original vector map and compressed vector map. From these figures, we know that it is very difficult to discriminate visually between original layer and compressed layer. We investigated the degradation of quality in enlarged maps. The quantitative criteria for evaluating quality in the enlargement has not been provided yet. Therefore, we enlarged two of original map and compressed map to arbitrary scales and looked the discrimination of two enlarged maps. From these results, we know that the degradation of compressed map comes into sight from about 2,356x. Thus, it should be enlarged our compressed map to large scale to see the degradation of quality.

Fig. 4. Structure of coded polyline data.

Download Original Figure

Our method in α = 0 has the same parameters of three simplification algorithms as Park’s method. We compared our method in α = 0 to Park’s method. The simplification rates for layers of our method are lower 0.1%-10.08% than those of Park’s method. Thus, our method simplifies vertices of layers more higher 0.1%-10.08% than Park’s method. Moreover, our method simplifies vertices in a map higher 4% than Park’s method. Layers of facility and administrative boundary are simplified to about 94%-99% because there are a number of simple polylines. However, layers of river and road are simplified to about 63%-74% because there are a number of complex polylines.

We measured simplification rate r and mean area difference Ᾱ of our method on different weighting factors from -1.0 to 1.0. The measurement results are shown in Figures 5(a) and 5(b). As α increases, r decreases while Ᾱ increases. When α = 1, r decreases about 57%-65% while Ᾱ increases about 9.88[m²]-12.14[m²]. However, when α = −0.4, r increases about 92%-94% while Ᾱ increases about 0.25[m²]-0.40[m²]. From these results, we verified that our method can control the simplification rate and mean area difference varying the weighting factor. This enables users to receive simplified vector maps on different GIS applications.

Fig. 5. Structure of coded polyline data.

Download Original Figure

We compared the compression efficiency of our method to that of Jang’s SEC method. Hereby, we experimented two ways of our method for comparing with Jang’s method. The first way is to do only the process of lossless compression that preserves data of all precision levels in fractional part. This way passes over the simplification. The second way is to do the simplification with α = 1 and lossless compression. The compression efficiency of our lossless compression has slightly higher 0.43%-3.60% than that of Jang’s method. Furthermore, the compression efficiency of our simplification and lossless compression has higher about 3.89%-16.58% than that of Jang’s method and higher about 3.47%-13.84% than that of only lossless compression. When looking at the results on layers, layers of river and tributary that has a number of polylines are compressed to high rate. However, layer of facility that has a few of polylines is compressed to low rate. It is natural that the polyline based compression method depends on the number of polylines on layers.