Using simple decomposition for smoothing and feature pointdetection of noisy digital curves

This correspondence presents an algorithm for smoothed polygonal approximation of noisy digital planar curves, and feature point detection. The resulting smoothed polygonal representation preserves the signs of the curvature function of the curve. The algorithm is based on a simple decomposition of noisy digital curves into a minimal number of convex and concave sections. The location of each separation point is optimized, yielding the minimal possible distance between the smoothed approximation and the original curve. Curve points within a convex (concave) section are discarded if their angle signs do not agree with the section sign, and if the resulted deviations from the curve are less than a threshold ε, which is derived automatically. Inflection points are curve points between pairs of convex-concave sections, and cusps are curve points between pairs of convex-convex or concave-concave sections. Corners and points of local minimal curvature are detected by applying the algorithm to respective total curvature graphs. The detection of the feature points is based on properties of pairs of sections that are determined in an adaptive manner, rather than on properties of single points that are based on a fixed-size neighborhood. The detection is therefore reliable and robust. Complexity analysis and experimental results are presented     

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

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

Learning and design of principal curves

Principal curves have been defined as “self-consistent” smooth curves which pass through the “middle” of a d-dimensional probability distribution or data cloud. They give a summary of the data and also serve as an efficient feature extraction tool. We take a new approach by defining principal curves as continuous curves of a given length which minimize the expected squared distance between the curve and points of the space randomly chosen according to a given distribution. The new definition makes it possible to theoretically analyze principal curve learning from training data and it also leads to a new practical construction. Our theoretical learning scheme chooses a curve from a class of polygonal lines with k segments and with a given total length to minimize the average squared distance over n training points drawn independently. Convergence properties of this learning scheme are analyzed and a practical version of this theoretical algorithm is implemented. In each iteration of the algorithm, a new vertex is added to the polygonal line and the positions of the vertices are updated so that they minimize a penalized squared distance criterion. Simulation results demonstrate that the new algorithm compares favorably with previous methods, both in terms of performance and computational complexity, and is more robust to varying data models     

一种基于遗传算法的数字曲线多边形逼近方法

提出了一种基于遗传算法的数字曲线多边形改进逼近方法。该方法针对规则形状数字曲线的多边形逼近问题,以二进制向量序列表示的染色体作为每一个对应的逼近多边形候选解,将简化前后多边形质心偏移误差以及各被替换线段欧氏距离的方差引入到适应函数中,用迭代次数的sigmoid函数作为变异概率来控制遗传算法优化求解过程中的全局和局部搜索特性。实验结果表明,该方法对于保持曲线多边形简化逼近后的形状特征具有较好的效果。     

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.     

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.     

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.     

Numerical Curve Length Calculation Using Polynomial Interpolation

In this paper we present a method and algorithm for computing curve length approximately using a fixed rule resulting from polynomial interpolation of the points on the curve. The method can applied efficiently calculating digital curves by considering the control points of the interpolation as the pixels centers points. In the paper several examples are presented and the calculated lengths are compared to other methods found in the literature and we have shown progress. We provided MATLAB^® code to simulate the algorithm. The advantage of the proposed method is in the approximation of the digital curve with the continuous curve rather than with piecewise linear sections used by most other methods.     

INTEGER analysis of two-dimensional polygonal objects

A consistent modelling scheme for digital images is presented, with the grey-level raster image as input and the list-oriented polygonal image as output. The output information consists of two parts: The metric of the polygonal object, represented by coordinates of marked positions, and the global topology, which takes the form of a two-dimensional topologic order. The central problem, which has to be solved, is to select a digital polygon, approximating a digital arc such that the essential feature of the arc is represented at a predefined precision level. The proposed algorithm uses simple incremental calculations of INTEGER quantities to solve the problem.     

Polygonal approximation of digital planar curves through break point suppression

This paper presents a new algorithm that detects a set of dominant points on the boundary of an eight-connected shape to obtain a polygonal approximation of the shape itself. The set of dominant points is obtained from the original break points of the initial boundary, where the integral square is zero. For this goal, most of the original break points are deleted by suppressing those whose perpendicular distance to an approximating straight line is lower than a variable threshold value. The proposed algorithm iteratively deletes redundant break points until the required approximation, which relies on a decrease in the length of the contour and the highest error, is achieved. A comparative experiment with another commonly used algorithm showed that the proposed method produced efficient and effective polygonal approximations for digital planar curves with features of several sizes.     

Real Time Fitting of Hand-Sketched Pressure Brushstrokes

A method is described for fitting the outline of hand-sketched pressure brushstrokes with Bézier curves. It combines the brush-trajectory model, in which a stroke is generated by dragging a brush along a given trajectory, with a fast curve fitting algorithm. The method has been implemented for a vector-based drawing program in which the user draws with a cordless pressure-sensitive stylus on a digitizing tablet. From the trajectory followed by the stylus, its associated pressure data, and a specified brush, a stroke of variable width is computed and displayed in real time. First, the digitized trajectory is fitted, thus removing noise. Then, from polygonal approximations of the fitted trajectory and the brush outline, a polygonal approximation of the stroke outline is computed. Working with polygonal approximations reduces computations to simple geometric operations and greatly simplifies the treatment of dynamic, pressure-controlled brushes. Last, the polygonal approximation of the stroke outline is fitted. The result is a closed piecewise Bézier curve approximating the brushstroke outline to within an arbitrary error tolerance. Several examples of hand-sketched drawings realized with this method are presented.     

Fast polygonal approximation of digitized curves

We describe a new technique for fast “scan-along” computation of piecewise linear approximations of digital curves in 2-space. Our method is derived from earlier work on the theory of minimum-perimeter polygonal approximations of digitized closed curves.We demonstrate the specialization of this technique to the case where the error is measured as the largest Hausdorff-Euclidean distance between the approximation and the given digitized curve. We illustrate the application of this procedure to the boundaries of the images of a lung and a rib in chest radiographs.     

Length Estimation in 3-D Using Cube Quantization

Estimators for the original length of a continuous 3-D curve given its digital representation are developed. The 2-D case has been extensively studied. The few estimators that have been suggested for 3-D curves suffer from serious drawbacks, partly due to incomplete understanding of the characteristics of digital representation schemes for 3-D curves.The selection and thorough understanding of the digital curve representation scheme is crucial to the design of 3-D length estimators. A comprehensive study on the digitization of 3-D curves was recently carried out. It was shown that grid intersect quantization and other 3-D curve discretization schemes that lead to 26-directional chain codes do not satisfy several fundamental requirements, and that cube quantization, that leads to 6-directional chain codes, should be preferred.The few 3-D length estimators that have been suggested are based on 26-directional chain coding that naturally provides a classification of the chain links, which is necessary for accurate length estimation. Cube quantization is mathematically well-behaved but the symmetry and uniformity of the 6-directional digital chain elements create a challenge in their classification for length estimation.In this paper length estimators for 3-D curves digitized using cube quantization are developed. Simple but powerful link classification criteria for 6-directional digital curves are presented. They are used to obtain unbiased length estimators, with RMS errors as low as 0.57% for randomly oriented straight lines.     

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.     

On recursive, O(N) partitioning of a digitizedcurve into digital straight segments

A simple online algorithm for partitioning of a digital curve into digital straight-line segments of maximal length is given. The algorithm requires O(N) time and O(1) space and is therefore optimal. Efficient representations of the digital segments are obtained as byproducts. The algorithm also solves a number-theoretical problem concerning nonhomogeneous spectra of numbers     

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

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

曲线的整数型生成算法

本文提出了一个用光栅显示器或数字化绘图仪等显示设备中选择曲线上最佳点的通过算法，该算法由几部分组成，分别对应曲线的不同走向段，其最大的特点是可以根据实际曲线的走向，在算法的各部分实现自动跳动，由此算法可生成所有常用曲线，本文给出Ｂｅｚｉｅｒ曲线和Ｂ样条曲线的生成算法，这些算法选择距离实际曲线最近的网格点，并且只有整数运算。     

An adaptive method for detecting dominant points

In this paper, we propose an adaptive method for the polygonal approximation of a digitized curve. Instead of setting a fixed length of support region in advance, the new method will compute the suitable length of support region for each point to find the best approximated curvature. The dominant points are identified as the points with local maximum curvatures. In addition, the break point detection is conducted to reduce the computations. The experimental results show that the proposed method can approximate the curves effectively.