|
|
|
Imai and Iri [119] wrote that the closed curve min-# (resp. min-e ) problem can be solved by solving the N ordinary open curve min-# (resp. min-e ) problems. If complexity of algorithm for open curve min-# problem is O(N2), the complexity for closed contour approximation is O(N3) time. Perez and Vidal [194] also wrote that the complexity of the straightforward min-e algorithm for closed contour is (N-M) times that of the algorithm for open curve. Taking into account the complexity of modified full-search DP algorithm [194, P4] for closed contours min-e problem it gives time complexity of O(M(N-M)3).
It was shown in [37] that the min-# problem for closed curve can be solved in S(N) time, where S(N) is the time for solving the all-pairs shortest path problem for a graph of N vertices.
There also exist a number of heuristic approaches for selecting the starting point. Sato [238] chooses the farthest point from the center of gravity as a starting point. Ray and Ray [212] in their formulation of the approximation problem specify neither the error nor number of line segments as cost function, but a ratio of the local L1 error measure to the length of the segments. For the case of the closed contours they proposed to extend the sequential search beyond the current starting point until to the first approximation vertex to revise the choice of the starting point.
Pikaz and Dinstein [197] considered min-# problem with city-block error metrics, and proposed an algorithm based on the shortest path problem, including the search of optimal starting point by an algorithm of complexity O(N2). Zhu and Seneviratne [320] considered the approximation problem with L¥ metrics, and proposed an O(N2) time algorithm for open curves. An iterative procedure for optimizing the choice of the starting point was also suggested for the case of closed curve. Schroeder and Laurent [243] in near-optimal algorithm for min-# problem perform preliminary approximation until the first approximation vertex is reached, and use this vertex as a new starting point for the second iteration.
Horng and Li [111] proposed a two-step method to select the starting point: at the first step, optimal approximation with any starting point is performed. At the second step, the approximation is performed again using the ë M/2û-th vertex as the new starting point.
To sum up, the proposed heuristic approaches for closed curves are sub-optimal whereas the optimal choice of the starting point is time consuming. Thus, the problem has not been solved satisfactory. One of the heuristic approaches is to perform preliminary approximation using one of the approximation vertices as a new starting point for final approximation [212, 197, 320, 111]. With this approach for starting point selection it is possible to obtain good results but, in general, the optimality of solution cannot be guaranteed (see Fig. 3.6.2).
|
|
|
In the mentioned heuristic algorithms after the first iteration, however, the search starts from scratch and loses the information of the previous run. The idea of the approach we proposed in [P6] is to extend dynamic programming search in special state space beyond the last vertex of contour in cyclic way until the last point will be reached again. Solutions for sub-tasks in the state space are analyzed to find the best possible starting point.
We call two states on the sub-path in state space conjugate if the sub-path with the states corresponds to approximation of the input contour with the same start and end points. Approximation error for the sub-path is defined as the difference of the cost function values of the conjugate states. To find the optimal starting point we have to find two conjugate states, which provide minimum of the approximation error E(m) for sub-path defined for all goal states in the state space (see Fig. 3.6.3). As we know, in DP algorithm for open curve solutions are constructed under the condition qM+1=pN. Propagating DP search in state space cyclically beyond the end point of P, we remove the restriction and make the approximation vertex qM+1 "free". Then we analyze solutions of all relevant sub-tasks with the free vertex qM+1 to find the best location for the starting point. If the original starting point gives the optimal solution, the correspondent path to goal state (N,M) is limited by conjugate states.
Generally speaking, global optimality of the found starting point cannot be guaranteed. Moreover, the sub-path with conjugate states may be does not exist in the state space W 2. Sometimes it happens in the case of coarse approximation when the number of vertices is big (N ~ 1000) and the number of vertices is relatively small (M < 10). We can extend DP search cyclically to the next runs along the curve in attempt to find better solution in the state space W k, where k³ 3. Anyway, the state space contains solution for the original starting point which can be use.
3.6.4 Min-# approximation of closed contours
To solve the min-# problem for closed curves, we have to find approximation of the closed contour P by another closed contour Q with minimal number of line segments with an approximation error within given error tolerance level: D(P)£ e. The approximation error D(P) with measure L¥is given as the maximum Euclidean distance from the vertices of P to the approximation linear segments.
To solve the min-# problem a digraph is constructed on the vertices of the input contour P. In the digraph, a pair of vertices pi and pj are connected with an edge if the approximation error of the curve segment between the vertices is less than a given error tolerance: d(pi,pj)£e. The optimal solution is then a given by solving the shortest path in the digraph. This can be solved by using DP algorithm for the shortest path problem in the digraph.
To find the optimal approximation for closed contour we shall follow the approach introduced in [P6]: perform approximation of the wrapped double-size closed contour P2 and then analyze the state space. In the case of min-# problem, the analysis of the space is reduced to the analysis of the solutions for the relevant sub-problems: we have to found the part of the approximation polygonal curve Q2, which have the same start and end points (see Fig. 3.6.4). As in the previous case, the initial approximation of the input curve can be extended cyclically to find better solution. Even if such a solution with less number of segments is not found, the obtained solution for the original starting point anyway can be used.
We have introduced a new approach for min-e and min-# approximation of closed contours based on dynamic programming method for open curves. It performs approximation of the cyclically extended double-size contour and then makes analysis of the state space to select the best starting point. The processing time is double of that of the approximation of the corresponding open curve. The time complexity of the algorithms is defined by the complexity of approximation algorithms for open curves in use. For solving the min-e problem the suggested method can be used along with iterative reduced search algorithm with time complexity between O(N) and O(N2).
