Fast computation of optimal polygonal approximations of digital planar closed curves

We face the problem of obtaining the optimal polygonal approximation of a digital planar curve. Given an ordered set of points on the Euclidean plane, an efficient method to obtain a polygonal approximation with the minimum number of segments, such that, the distortion error does not excess a threshold, is proposed. We present a novel algorithm to determine the optimal solution for the min-# polygonal approximation problem using the sum of square deviations criterion on closed curves.Our proposal, which is based on Mixed Integer Programming, has been tested using a set of contours of real images, obtaining significant differences in the computation time needed in comparison to the state-of-the-art methods.     

Moment-based methods for polygonal approximation of digitized curves

Object shape representation plays an important role in the area of image processing, pattern recognition and computer vision. In the past two decades, many algorithms have been suggested for creating approximated polygons. In this study, two new polygonal approximation methods based on the geometric moments and the orthogonal moments defined in terms of Legendre polynomials are proposed. The difference between the moments defined by the initial contour and those of the approximated polygon is taken as the objective function. Each algorithm provides various polygonal approximation results with different number of line segments for different application situations. For a given error bound, we can determine the optimal polygon with a minimum number of line segments. The procedures are applied to some digital curves and better results are obtained in comparison with some known methods.     

Speeding up simplification of polygonal curves using nested approximations

We develop a top-down multiresolution algorithm (TDMR) to solve iteratively the problem of polygonal curve approximation. This algorithm provides nested polygonal approximations of an input curve. We show theoretically and experimentally that, if the simplification algorithm A{\mathcal{A}} used between any two successive levels of resolution satisfies some conditions, the multiresolution algorithm will have a complexity lower than the complexity of A{\mathcal{A}} applied directly on the input curve to provide the crudest polygonal approximation. In particular, we show that if A{\mathcal{A}} has a O(N ²/K) complexity (the complexity of a reduced search dynamic programming solution approach), where N and K are, respectively, the number of segments in the input curve and the number of segments in the crudest approximation, the complexity of MR is in O(N). We experimentally compare the outcomes of TDMR with those of the optimal full search dynamic programming solution and of classical merge and split approaches. The experimental evaluations confirm the theoretical derivations and show that the proposed approach evaluated on 2D coastal maps either leads to a lower complexity or provides polygonal approximations closer to the initial curves.     

遗传算法在曲线多边形近似中的应用

在平面数字曲线的多边形近似中,为克服顶点的检测只依靠部区域,缺 乏全局信息的弱点,文中把多边形近似问题作了寻找在满足一定的近似误差下使顶点数最少,或者使顶点数和近似误差都尽可能少的最优化问题来处理。     

Unsupervised segmentation and approximation of digital curves with rate-distortion curve modeling

This paper considers the problem of unsupervised segmentation and approximation of digital curves and trajectories with a set of geometrical primitives (model functions). An algorithm is proposed based on a parameterized model of the Rate–Distortion curve. The multiplicative cost function is then derived from the model. By analyzing the minimum of the cost function, a solution is defined that produces the best possible balance between the number of segments and the approximation error. The proposed algorithm was tested for polygonal approximation and multi-model approximation (circular arcs and line segments for digital curves, and polynomials for trajectory). The algorithm demonstrated its efficiency in comparisons with known methods with a heuristic cost function. The proposed method can additionally be used for segmentation and approximation of signals and time series.     

Vector Image Segmentation by Piecewise Continuous Approximation

In this article we present an approach to the segmentation problem by a piecewise approximation of the given image with continuous functions. Unlike the common approach of Mumford and Shah in our formulation of the problem the number of segments is a parameter, which can be estimated. The problem can be stated as: Compute the optimal segmentation with a fixed number of segments, then reduce the number of segments until the segmentation result fulfills a given suitability. This merging algorithm results in a multi-objective optimization, which is not only resolved by a linear combination of the contradicting error functions. To constrain the problem we use a finite dimensional vector space of functions in our approximation and we restrict the shape of the segments. Our approach results in a multi-objective optimization: On the one hand the number of segments is to be minimized, on the other hand the approximation error should also be kept minimal. The approach is sound theoretically and practically: We show that for L ²-images a Pareto-optimal solution exists and can be computed for the discretization of the image efficiently.     

Near-Linear Time Approximation Algorithms for Curve Simplification

We consider the problem of approximating a polygonal curve P under a given error criterion by another polygonal curve P’ whose vertices are a subset of the vertices of P. The goal is to minimize the number of vertices of P’ while ensuring that the error between P’ and P is below a certain threshold. We consider two different error measures: Hausdorff and Frechet. For both error criteria, we present near-linear time approximation algorithms that, given a parameter ε > 0, compute a simplified polygonal curve P’ whose error is less than ε and size at most the size of an optimal simplified polygonal curve with error ε/2. We consider monotone curves in ℝ² in the case of the Hausdorff error measure under the uniform distance metric and arbitrary curves in any dimension for the Frechet error measure under L_p metrics. We present experimental results demonstrating that our algorithms are simple and fast, and produce close to optimal simplifications in practice.     

A new subdivision based approach for piecewise smooth approximation of 3D polygonal curves

This paper presents an algorithm dealing with the data reduction and the approximation of 3D polygonal curves. Our method is able to approximate efficiently a set of straight 3D segments or points with a piecewise smooth subdivision curve, in a near optimal way in terms of control point number. Our algorithm is a generalization for subdivision rules, including sharp vertex processing, of the Active B-Spline Curve developed by Pottmann et al. We have also developed a theoretically demonstrated approach, analysing curvature properties of B-Splines, which computes a near optimal evaluation of the initial number and positions of control points. Moreover, our original Active Footpoint Parameterization method prevents wrong matching problems occurring particularly for self-intersecting curves. Thus, the stability of the algorithm is highly increased. Our method was tested on different sets of curves and gives satisfying results regarding to approximation error, convergence speed and compression rate. This method is in line with a larger 3D CAD object compression scheme by piecewise subdivision surface approximation. The objective is to fit a subdivision surface on a target patch by first fitting its boundary with a subdivision curve whose control polygon will represent the boundary of the surface control polyhedron.     

Data reduction of large vector graphics

Fast algorithm for joint near-optimal approximation of multiple polygonal curves is proposed. It is based on iterative reduced search dynamic programming introduced earlier for the min-εproblem of a single polygonal curve. The proposed algorithm jointly optimizes the number of line segments allocated to the different individual curves, and the approximation of the curves by the given number of segments. Trade-off between time and optimality is controlled by the breadth of the search, and by the numbers of iterations applied.     

基于连接点的二维多角弧匹配

多角弧匹配问题的关键是，其既能反映多角弧的几何性质，又能反映多角弧拓扑结构的特征选取．在分析了多角弧几何形状的基础上，引入了连接点的概念，并用连接点集表示多角弧，这一表示在旋转和平移变换下是不变的。进一步取该连接点集作为匹配的特征集，给出了特征集之间匹配的算法．该算法是将连接点间的距离积分作为测量函数，使二维多角弧的匹配由连接点的匹配来决定．给出的模拟试验结果表明，该算法效果良好，并且对于数值污染具有健壮性。     

Optimum uniform piecewise linear approximation of planar curves

Two-dimensional digital curves are often uniformly approximated by polygons or piecewise linear curves. Several algorithms have been proposed in the literature to find such curves. We present an algorithm that finds a piecewise linear curve with the minimal number of segments required to approximate a curve within a uniform error with fixed initial and final points. We compare our optimal algorithm to several suboptimal algorithms with respect to the number of linear segments required in the approximation and the execution time of the algorithm.     

Maximum error-bounded Piecewise Linear Representation for online stream approximation

Given a time series data stream, the generation of error-bounded Piecewise Linear Representation (error-bounded PLR) is to construct a number of consecutive line segments to approximate the stream, such that the approximation error does not exceed a prescribed error bound. In this work, we consider the error bound in \(L_\infty \) norm as approximation criterion, which constrains the approximation error on each corresponding data point, and aim on designing algorithms to generate the minimal number of segments. In the literature, the optimal approximation algorithms are effectively designed based on transformed space other than time-value space, while desirable optimal solutions based on original time domain (i.e., time-value space) are still lacked. In this article, we proposed two linear-time algorithms to construct error-bounded PLR for data stream based on time domain, which are named OptimalPLR and GreedyPLR, respectively. The OptimalPLR is an optimal algorithm that generates minimal number of line segments for the stream approximation, and the GreedyPLR is an alternative solution for the requirements of high efficiency and resource-constrained environment. In order to evaluate the superiority of OptimalPLR, we theoretically analyzed and compared OptimalPLR with the state-of-art optimal solution in transformed space, which also achieves linear complexity. We successfully proved the theoretical equivalence between time-value space and such transformed space, and also discovered the superiority of OptimalPLR on processing efficiency in practice. The extensive results of empirical evaluation support and demonstrate the effectiveness and efficiency of our proposed algorithms.     

An Optimal Algorithm for the Straight Segment Approximation of Digital Arcs

In this paper, we define the straight segment approximation problem (SSAP) for a given digital arc as that of locating a minimum subset of vertices on the arc such that they form a connected sequence of digital straight segments. Sharaiha (Ph.D. thesis, Imperial College, London, 1991) introduced the compact chord property, and proved its equivalence to Rosenfeld′s chord property (IEEE Trans. Comput. C-23, 1974, 1264-1269). The SSAP is now constrained by the compact chord property, which offers a more convenient geometric representation than the chord property. We develop an O(n²) optimal algorithm for the solution of the SSAP using integer arithmetic. A relaxation of the problem is also presented such that the optimal number of vectors can be reduced according to a user definition. The original algorithm is adapted for the optimal solution of the relaxed problem. An extension to the relaxed problem is also addressed which finds a minimum level of relaxation such that the optimal number of vectors cannot be reduced.     

CIM algorithm for approximating three-dimensional polygonal curves

The polygonal approximation problem is a primary problem in computer graphics,pattern recognition,CAD/CAM,etc.In R^2,the cone intersection method(CIM) is one of the most efficient algorithms for approximating polygonal curves,With CIM Eu and Toussaint,by imposing an additional constraint and changing the given error criteria,resolve the three-dimensional weighted minimum number polygonal approximation problem with the parallel-strip error criterion(PS-WMN)under L2 norm.In this paper,without any additional constraint and change of the error criteria,a CIM solution to the same problem with the line segment error criterion(LS-WMN)is presented,which is more frequently encountered than the PS-WMN is .Its time complexity is O(n^3),and the space complexity is O(n^2) .An approximation algorithm is also presented,which takes O(n^2) time and O(n) space.Results of some examples are given to illustrate the efficiency of these algorithms.     

Optimal Spline Approximation via ℓ0‐Minimization

Splines are part of the standard toolbox for the approximation of functions and curves in ?^d. Still, the problem of finding the spline that best approximates an input function or curve is ill‐posed, since in general this yields a “spline” with an infinite number of segments. The problem can be regularized by adding a penalty term for the number of spline segments. We show how this idea can be formulated as an ?₀‐regularized quadratic problem. This gives us a notion of optimal approximating splines that depend on one parameter, which weights the approximation error against the number of segments. We detail this concept for different types of splines including B‐splines and composite Bézier curves. Based on the latest development in the field of sparse approximation, we devise a solver for the resulting minimization problems and show applications to spline approximation of planar and space curves and to spline conversion of motion capture data.     

Optimized polygonal approximation by dominant point deletion

An algorithm for polygonal approximation based on dominant point (DP) deletion is presented in this paper. The algorithm selects an initial set of DPs and starts eliminating them one by one depending upon the error associated with each DP. The associated error value is based on global measure. A local optimization of few neighboring points is performed after each deletion. Although the algorithm does not guarantee an optimal solution, the combination of local and global optimization is expected to produce optimal results. The algorithm is extensively tested on various shapes with varying number of DPs and error threshold. In general, optimal results were observed for about 96% of the times. A good comparative study is also presented in this paper     

基于多边形边界约简的启发式在线时间序列表示算法

提出了一种新颖的可在线计算的时间序列启发式算法。算法具有多边形约简算法相同的优良的近似质量，并可在固定数据缓冲区空间内在线运算。用启发式搜索方法自动获取最佳分段数。在随机时间序列上仿真试验证明算法有很高的逼近质量和较低的计算复杂性。     

Fast polygonal approximation of digital curves using relaxed straightness properties

Several existing DSS (digital straight line segment) recognition algorithms can be used to determine the digital straightness of a given one-pixel-thick digital curve. Because of the inherent geometric constraints of digital straightness, these algorithms often produce a large number of segments to cover a given digital curve representing a real-life object=image. Thus, a curve segment, which is not exactly digitally straight, but appears to be visually straight, is fragmented into multiple DSS when these algorithms are run. In this paper, a new concept of approximate straightness is introduced by relaxing certain conditions of DSS, and an algorithm is described to extract those segments from a digital curve. The number of such segments required to cover the curve is found to be significantly fewer than that of the exact DSS-cover. As a result, the data set required for representing a curve also reduces to a large extent. The extracted set of segments can further be combined to determine a compact polygonal approximation of a digital curve based on certain approximation criteria and a specified error tolerance. The proposed algorithm involves only primitive integer operations and thus runs very fast compared to those based on exact DSS. The overall time complexity becomes linear in the number of points present in the representative set. Experimental results on several digital curves demonstrate the speed, elegance and efficacy of the proposed method.     

New Results on Path Approximation

In this paper we give bounds on the complexity of some algorithms for approximating 2-D and 3-D polygonal paths with the infinite beam measure of error. While the time/space complexities of the algorithms known for other error measures are well understood, path approximation with infinite beam measure seems to be harder due to the complexity of some geometric structures that arise in the known approaches. Our results answer some open problems left in previous work. We also present a more careful analysis of the time complexity of the general iterative algorithm for infinite beam measure and show that it could perform much better in practice than in the worst case. We then propose a new approach for path approximation that consists of a breadth first traversal of the path approximation graph, without constructing the graph. This approach can be applied to any error criterion in any constant dimension. The running time of the new algorithm depends on the size of the output: if the optimal approximating path has m vertices, the algorithm performs F(m) iterations rather than n–1 in the previous approaches, where F(m) \le n–1 is the number of vertices of the path approximation graph that can be reached with at most m–2 edges. This is the first output sensitive path approximation algorithm.     

New Results on Path Approximation

In this paper we give bounds on the complexity of some algorithms for approximating 2-D and 3-D polygonal paths with the infinite beam measure of error. While the time/space complexities of the algorithms known for other error measures are well understood, path approximation with infinite beam measure seems to be harder due to the complexity of some geometric structures that arise in the known approaches. Our results answer some open problems left in previous work. We also present a more careful analysis of the time complexity of the general iterative algorithm for infinite beam measure and show that it could perform much better in practice than in the worst case. We then propose a new approach for path approximation that consists of a breadth first traversal of the path approximation graph, without constructing the graph. This approach can be applied to any error criterion in any constant dimension. The running time of the new algorithm depends on the size of the output: if the optimal approximating path has m vertices, the algorithm performs F(m) iterations rather than n–1 in the previous approaches, where F(m) \le n–1 is the number of vertices of the path approximation graph that can be reached with at most m–2 edges. This is the first output sensitive path approximation algorithm.