Polygonal approximation

1. Introduction
2. Heuristic algorithms
3. Optimal algorithms for min-e problem
4. Iterative reduced search
5. Optimal algorithms for min-# problem
6. Approximation of closed contours
7. Multiple-object polygonal approximation
8. References
9. List of publications

3.1 Introduction

3.1.1 Problem formulation

An open N-vertex polygonal curve P in 2-dimensional space is represented as the ordered set of vertices P={p₁, …, p_N}={(x₁, y₁), …, (x_N, y_N)}. The output coarser curve Q consists of (M+1) vertices: Q={q₁, …, q_M+1}, where the set of vertices q_m is a subset of P and M<N. The end points of Q are the end points of P: q₁ = p₁, q_M+1 = p_N. The approximation linear segment (q_m, q_m+1) of Q for curve segment {p_i, …, p_j} of P is defined by the end points p_i and p_j: q_m = p_i and q_m+1 = p_j. Thus, (q_m, q_m+1) = (p_i, p_j).

As it was stated in [147, 119] there are two types of optimization problems connected with polygonal approximation problems:

3.1.2 Error measures

Figure 3.1.1: Distance d_k from the point p_k to the linear segment (p_i, p_j).

The distance d_k(i, j) from curve vertex p_k=(x_k, y_k) to the corresponding approximation linear segments (p_i, p_j) is defined as follows (see Fig. 3.1.1):

(3.1.1)

(3.1.2)

The additive error measure L_p for curve segment {p_i, p_j} is defined by the sum of distances d(k; i, j) for all vertices in the segment as follows:

(3.1.3)

For L_¥ the approximation error i s defined as the maximum deviation of input curves from approximation linear segment:

(3.1.4)

Approximation error E_p(P) of the input curve P by Q with additive error measure L_p (where p<¥) is defined as the sum of approximation errors for all segments:

(3.1.5)

For error measure L¥ , the approximation error for the curve P is defined as the maximum of distances for all segments:

(3.1.6)

The error measure L₂ (integral square error, or ISE) is perhaps among the most widely used criteria for approximation min-eproblem. The error e₂(p_i, p_j) with measure L₂ can be calculated in O(1) time using stored arrays of coordinates cumulatives.

In most cases the error measure L_¥ is used in algorithms for min-# problem for practical reasons. In [119] different error criteria with measure L¥ are given, including the most popular parallel-strip (or infinite beam) criterion [269], that is maximum distance between the line connecting p_i and p_j and the points of the curve segment {p_i, …, p_j} (see Fig. 3.1.2, left). The segment distance (or tolerance zone) criterion is defined as maximum distance between the line segment (p_i, p_j) and the points of the curve segment {p_i, …, p_j} (see Fig. 3.1.2, right). In some algorithms, other error measures are in use for min-# problem: integral square error L₂ [233, 243], and local integral square error (LISE) [52], or more complicated objective functions [212]. However, using error measure L₂ for min-# problem is not efficient in practice, especially in the case of multiple objects, because of its additive nature.

Since optimal algorithms are computationally expensive to be used (usually between O(N²) and O(N³)), faster sub-optimal algorithms have been developed, often running in linear time. In order to evaluate the quality of sub-optimal algorithms, Rosin [224] introduced two measures. Fidelity (F) measures how well the suboptimal polygon fits the curve relative to the optimal polygon in terms of the approximation error. Efficiency measures how compact the suboptimal polygonal presentation of the curve is. They are defined as follows:

where M is the number of segments for an algorithm under question, M_min is the number of segments for min-# solution, E is approximation error for an approximation algorithm, and E_min is the approximation error of the optimal solution for the min-e problem.

3.1.3 Motivation

Important problems such as polygonal approximation have been explored very intensively for the last 30 years. The min-# and min-e problems can be solved as an optimization task by dynamic programming or methods based on graph theory. Moreover, many heuristic algorithms have proposed. Optimal algorithms of complexity O(N²)- O(N³) are very slow, whereas faster heuristic algorithms lack of optimality. Thus, development of efficient (fast and optimal or near-optimal) algorithms for large input data is still an open problem.

Introducing into practice more efficient algorithms for min-# problem we can reduce storage demands or transmission time for the same tolerance level. With more efficient algorithms for min-e problem, we can reduce approximation error for the same amount of stored or transmitted data. Taking into account that nowadays polygonal approximation in vectorization, map service, CAD and GIS applications, the efficient solution of this problem is still of great practical importance (see Figs. 3.1.3-3.1.7).

At first we provide a short survey of heuristic algorithms for min-# and min-e approximation problems in Section 3.2. Then we explore optimal algorithms for min-e problems in Section 3.3. To bridge the gap between slow optimal and fast heuristic non-optimal algorithms we introduce paradigms of bounding corridor and iterated reduced search [P4]. Then we study optimal algorithms for min-# problem and present algorithm with joint using of different error measures based on the reduced search [P5]. Furthermore, we consider min-e and min-# problems for the case of closed contours and provide cyclical DP algorithm with analysis of the state space [P6]. Finally, we extend the proposed iterative reduced search approach to the case of min-e problem for multiple objects [P7].

a) b)
Figure 3.1.5: Min-e approximation of multiple-object vector data: vector map of "Europe"; 365 objects with 160,000 vertices (a); fragment of the vector map after 20:1 data reduction (b).

Figure 3.1.7: Min-e approximation of 5000-vertex digitized path in 3-D space by M=100 linear segments.