Multiple object min-# problem: Given K polygonal curves P1, P2, …, PK, approximate it by set of K another polygonal curves Q1, Q2, …, QK with the minimum total number of segments M so that the approximation error does not exceed a given maximum tolerance e.
Multiple object min-e problem: Given K polygonal curves P1, P2, …, PK, approximate it by set of K another polygonal curves Q1, Q2, …, QK with a given total number of segments M so that the total approximation error is minimized.
Solution for the multiple-object min-# problem depends on the error measure in use. In the case of L¥ error measure, the problem reduces to the single-object min-# problem as the optimization can be solved for every object independently [244]. In the case of additive error measures (L1, L2, etc.), on the other hand, the problem is not trivial. Fortunately, in practical applications we mostly have to deal with error measure L¥ because the use of additive error measures (L1 or L2) is not practical in the case of min-# problem.
The case of min-e approximation of multiple objects (with any error measure) is more complicated. The optimal approximation cannot be obtained by solving the approximation of each individual objects separately because the given total number of approximation segments should be optimally distributed among all objects. For example, uniform allocation of the segments can assign too many segments to the less complicated objects and, respectively, lacking the segments for more complicated objects. This situation is illustrated in Fig. 3.7.2.
The multiple-object min-e problem can be formulated as the following optimization task for the total approximation error E(P1, …, PK, K) for K objects {P1, …, PK}:
where e2(qk,m, qk,m+1) is approximation error with measure L2 of curve segment {pi, …, pj} of Pk by the correspondent line segment (qk,m, qk,m+1) of Qk; M is a given total number of segments and Mk is the number of segments in object Pk.
Shuster and Katsaggelos considered problem of lossy encoding of object boundaries in rate-distortion sense [244]. The digitized contour is approximated by polygon Q, which leads to the smallest distortion for a given rate (number of bits). Actually, the case when the rate is proportional to the number of line segments corresponds to the multiple-object min-e problem. Schuster and Katsaggelos [244] considered two different classes of distortion measures: L¥ and L2. For the first class (measure L¥ ), they used scheme based on the shortest path algorithm for a weighted directed acyclic graph. For the second class (measure L2) they proposed two algorithms.
The first algorithm is based on the Lagrangian multipliers method, which uses the DP algorithm for the shortest path in a directed acyclic graph. The time complexity of the Lagrangian approach for a fixed multiplier l is the same as for the base shortest path algorithm. The shortest path algorithm is invoked several times by the bisection algorithm to find the optimal l * and, hence, the time complexity is a function of the number of required iterations. Thus, the complexity of the first algorithm is O(N2 log N) because it is defined by the complexity of the shortest path algorithm and the number of bisection iterations. Since the Lagrangian multiplier method can only find solutions on the convex hull of the operational rate-distortion functions, they also proposed a tree-pruning based algorithm. This method is a one pass variant algorithm with the complexity of O(N2), but the efficiency of the pruning scheme cannot be guaranteed in general.
Algorithms with the complexity of higher than O(N2) can be used for relatively small input. This can be suitable for the encoding of object contours for MPEG-4 standard [132] but it can be too slow in the case of large vector maps.
a)
b)Because the time and space complexity of the full search algorithm is high, the iterative reduced search approach was generalized to the problem under consideration. We follow the main idea of the reduced search by reducing the search space by a given preliminary solution for the approximation, and then perform the search in the reduced space iteratively (see Fig. 3.7.3). Main difference to the full search is that a smaller search area is needed, which makes the algorithm faster. The iterative reduced search algorithm has time complexity of O(N)- O(N2). This is significantly smaller than the O(N3) of the full search, or the O(N2log(N)) of [244]. The reduced search approach is also applicable for very large data sets with reasonable memory requirements. Although the optimality of the algorithm cannot be guaranteed in general, the experiments indicate that the method is capable of finding the optimal solution even in the case of very large data sets (see Fig. 3.7.4). The algorithm can also be tuned for obtaining very fast sub-optimal solutions by reducing the number of iterations and corridor width.
a)
b)