One year later Dunham [73] published min-# algorithm that uses DP approach for optimal approximation with least number of segments for error measure L¥ . He used modified scan-along algorithm of [290] and [250] with cone intersection to reduce DP search. The complexity of the algorithm is O(N3) in the worst case.
About the same time Imai and Iri [117-119] present a unified approach for the problem by formulating it in terms of graph theory. At first, a directed acyclic graph Ge (P) = (V, Ee ) is constructed (see Fig. 3.5.1, left). Nodes V are vertices of the curve P = {p1, …, pN} and edges Ee are the approximation line segments Ee = {(pi, pj): 1£ i<j£ N | D(pi, pj) £ e }. Two nodes pi and pj of Ge(P) are connected with an edge (pi, pj), iff the correspondent approximation error (maximum deviation) D(pi, pj) is at most the prescribed error tolerance e: D(pi, pj) £ e .
Figure 3.5.1: Graph Ge(P) constructed on digitized curve P for error tolerance e =10 (left); min-# approximation solution for e =10 as the shortest path in the graph Ge(P) (right).
Solving min-# problem consists of finding the shortest path from p1 to pN in digraph Ge(P) (see Fig. 3.5.1, right). Since the graph is acyclic, this path can be found in time proportional to the number of edges [64, 55]. The brute-force method of constructing Ge(P) is to check for each pair of vertices pi and pj whether the error D(pi, pj) is within error tolerance e. There are O(N2) pairs of vertices and checking the error, corresponding to a pair, take s O(N) time. This brute-force method for the graph Ge(P) construction takes O(N3), while finding the shortest path in G takes no more than O(N2) time. Thus, the bottlenck in th e computation of min-# approximation is the construction of the graph Ge(P). The main efforts of researchers have concentrated on the problem of how to reduce complexity of the graph construction.
Melkman and O’Rourke [165] studied the 2-D min-# and min-eproblems. Their version of Imai-Iri’s algorithms takes O(N2logN) for min-# problem, and O(N2log2N) for min-e problem. Space complexity is O(N2) in both cases. Thus, the graph construction was reduced from O(N3) to O(N2logN). They proposed cone-intersection algorithm to reduce the complexity of the graph constuction. This algorithm is analog of that of Sklansky and Gonzalez [250].
Chan and Chin [37] reduced the time complexity to O(N2 ) for min-# problem, and O(N2logN) for min-e problem using the parallel-strip criterion They improved complexity of constructing graph G to O(N2). They have also shown that for close d polygonal curve the min-# problem can be solved in S(N) time, where S(N) denotes the time complexity for solving all-pairs shortest path problem of Ge(P). They also presented algorithm of linear time complexity for min-# problem for the convex curves (see Table 3.5.1).
Table 3.5.1: Summary of the time complexities of the polygonal algorithms of Chan and Chin [37].
|
Shape type |
General |
Convex |
||
|
|
Open |
Closed |
Open |
Closed |
|
Min-# problem |
O(N2) |
S(N) |
O(N) |
O(N2) |
|
Min-e problem |
O(N2logN) |
S(N)logN |
O(N2) |
O(N2) |
Based on the infinite beam criterion, Toussaint [269] solved the min-# problem in O(N2logN) time and O(N2) space. Imai and Iri gave an O(N2log2N) time and O(N2) space for the min-e problem. Eu and Toussaint [77] published another algorithm for min-# problem under the infinite beam criterion that was claimed to take O(N2) time, and O(N2logN)) for min-e problem. The space complexity is O(N2). Eu and Toussaint [77] also used the infinte beam criterion based on L1 and L¥ distance metrics. Using L2 distance metric, the min-# problem can be solved in O(N3) time, and min-eproblem in O(N3logN)) time.
Ray and Ray [212] determined least number of segments with the minimum possible error by maximizing an objective function comprised of the length of line segments and the sum of absolute errors between the line segments and the digital curve (L1 error measure).
Pikaz and Dinstein [197] found min-# approximation of the polygonal curve where the city-block metric is used to measure distance between the approximation and the input curve. For the city-block the distance the complexity of the algorithm is O(N2).
Chen and Daescu [40, 41] presented a number of efficient algorithms for the 2-D min-# and min-e problems in the same time bounds as [37, 77], but using only O(N) space in comparison with O(N2). Also they applied the technique to a special case of the 3-D min-# and min-e problems.
Zhu and Seneviratne [320] have shown that cone-intersection algorithm [250] has the problem that some peaks will disappear from the curve when the cone angle is the only evaluation factor and introduced modification to Sklansky and Gonzalez method. Based on the modified algorithm for they proposed new version of the algorithm for min-# problem.
Katsaggelos et al. [132] used polygonal approximation for lossy encoding with minimum rate and given distortion bounds. Actually, Katsaggelos et al. solved more general problem, than just a min-# one. In this case, the techniques based on geometrical computations, cannot be used. Because of the brute-force method applied for construction of the graph Ge (P), time complexity of their algorithm is O(N3).
Hosur and Ma [114] following the approach of Katsaggelos et al. for min-# problem proposed cone intersection method for reducing the graph construction time, which actually has been introduced early in [250] and have already been used in other algorithms for min-# problem [187, 73].
Recently Agarwal et al. [6] proposed min-# algorithm for Hausdorff and Frechet error measure of O(N4/3+d) time complexity, where d>0. Barequet et al. [22] presented agorithms for approximating polygonal curves in 3D and higher dimensional spaces under the tolerance zone criterion.
Table 3.5.2: Summary of min-# and min-e results from [22].
|
Metric |
3 dimensions |
d³ 4 dimensions |
||
|
min-# |
min-e |
min-# |
min-e |
|
|
L2 |
O(N2logN) |
O(N2log3N) |
O(N3-2/(ë d/2û +1)polylogN) |
O(N73polylogN)* |
|
L1 & L¥ |
O(N2) |
O(N2logN) |
O(N2) |
O(N2logN) |
With DP algorithm of Perez and Vidal the min-# problem for measure L2 can be solved in O(N3) time (see also [274]). Salloti proposed fast optimal algorithm for the problem based on the A*-search algorithm, and he introduced for min-e problem with L2 measure [230, 231]. Using the heuristic error estimations to stop the search, he reduced complexity of Perez-Vidal algorithm from O(N3) to O(N2) time.
3.5.2 Problem of multiple solutions
As we can see, the error measure L¥is widely used in heuristic and optimal algorithms for min-# problem. The error measure L¥ is preferred to other measures for obvious reasons. But careful study of these min-# algorithms based on the error measure L¥ shows that all the algorithms suffer from an essential drawback, namely visible distortion of approximation curve (see Fig. 3.5.2, left)
|
|
|
Firstly, the drawback was noted by Papakonstantinou [188] who has been studying problem of data reduction of ECG signals by polygonal approximation with minimum number of line segments for measure L¥ . As it was mentioned above, he wrote, that so called optimal solution is not unique. Actually, the number of the equivalent optimal solutions (having the same minimal number of line segments) can be extremely large (see Fig. 3.5.3). The reason of the effect is as follows: with the error measure L¥we can control only the maximum deviation, but not the deviations for all the vertices of the approximated curve. Formally, the solutions satisfy the constraint on maximum deviation, but the solutions have visible shape distortion.
To overcome the problem, Papakonstantinou proposed how to select the best one among the formally optimal solutions, with the minimal integral square error. In other word, he proposed to use error measures L¥ and L2 jointly to obtain solution, which satisfies the condition on maximum deviation D(P) £ e and provides minimum to the approximation error E(P) with measure L2. The complexity of the modified min-# algorithm is defined by the complexity of the base algorithm but the processing time is bigger because of L2-optimization. The proposed method provides good results. It is easy to understand why the effect has been discovered by studying approximation of ECG signals. For smooth curves the distortion effect is small, whereas for curves with sharp corners, such as ECG signals, the effect is clearly visible.
Haugland et al. [97, 179] attacked the problem by joint use of measures L¥ and L2 from another side. They solved problem of ECG data reduction with a given data compression ratio by algorithm for min-eproblem with measure L2. Proximity of the approximation curve to the input one is measured by the sum of squared errors, but the deviation (error value) for every individual vertex is beyond the control of the algorithm. To overcome the problem, they proposed modified version of the base DP algorithm for min-e problem, introducing additional check if the local deviation less than the tolerance level. To reduce the processing time for the computation of the L¥ approximation error, a fast algorithm based on convex hull construction has been used.
Authors formulated a new version of min-e problem using two conditions: a) the number of segments should be less than a given value: M£ M0, and b) the maximum deviation should be below the tolerance level: D(P)£ e. As we can see, the conditions are contradictious: if the given number of segments M0 is too small, the constraint on maximum deviation cannot be satisfied with any number of segments. The problem can be solved with constraint on the maximum error, or on the number of segments, but not on both of them.
Pikaz and Dinstein in [197] solved min-# problem as the shortest path on digraph with city-block distance metrics. The obtained polygonal approximation is minimal with respect to the number of vertices under a given maximal error. As in the mentioned above case, there might be several different polygonal approximations with the same minimal number of vertices. Pikaz and Dinstein offered to select solution that is optimal according to the criterion of minimal maximal distance between the approximation and the original curve. Although the proposed method allows reducing the maximum deviation, the local deviations (smaller than tolerance level) are still out of control.
3.5.3 Selection of the best solution with reduced search
In [P5] we apply the iterative reduced search for solving the min-# problem. At first, the initial solution approximation for a given error tolerance e is obtained with any algorithm for min-# problem, then a bounding corridor is constructed along the reference path, and finally the solution is searched in the bounding corridor (see Figs. 3.5.2, right, and 3.5.4, right).
Experiments have shown, that although the integral squared error E(P) is reduced after L2-optimization, the maximum deviation D(P) can be bigger than a given tolerance level in a few outliers. The problem can be solved by additional iterations with reduced search to increase the number of linear segments M. Another solution is to perform L2-optimization with L¥ constraints on the approximation error by cost of higher time complexity because of L¥ approximation error calculation.
|
|
|
In high quality vectorization tasks, the increase of the maximum deviation is about 10% and takes place for outliers only. In our opinion, in practical applications, the given constraint of maximum deviation e can be treated in non-strong way. In other words, to reduce processing time we can use the iterative reduced search to optimize location of vertices. The obtained approximation points satisfies the given constraint on the deviation, excluding may be a few outliers.
3.5.4 Summary
We have proposed to use iterative reduced search approach to improve the quality of min-# approximation solutions obtained. The initial min-# solution can be found with any algorithm with L¥ error measure. Then we optimize location of the approximation vertices with L2 error measure using iterative reduced search. The proposed algorithm is tailored for high-quality vectorization of digitized curves.
