基于矩的数字图像多边形逼近方法

提出了两种基于矩的数字图像的多边形逼近方法。通过比较原始图形和近似图形之间几体矩或Legendre矩的偏差的大小,选择一个最佳的近似结果,进一步可以得到一个顶点数递减的近似多边形序列。与现存的方法比较,这种方法有效地避免了逼近这结果依赖于起始点的选取的缺陷。     

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

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

基于小波惟一描述子的多边形逼近方法

提出了一种基于小波惟一描述子的多边形逼近方法。对提取的多边形采用小波描述子,通过比较原始多边形和逼近多边形之间小波惟一描述子偏差的大小,选择一个最佳的逼近结果,以得到一个顶点数递减的近似多边形序列。与现有方法比较,本文方法既考虑了轮廓的整体信息,又考虑了轮廓的局部信息,因而具有更好的鲁棒性。将该方法与面积法及勒让德矩方法进行了比较,实验结果表明,采用该方法得到的逼近结果具有更好的效果及可靠性。     

Error-bounded biarc approximation of planar curves

Presented in this paper is an error-bounded method for approximating a planar parametric curve with a G¹ arc spline made of biarcs. The approximated curve is not restricted in specially bounded shapes of confined degrees, and it does not have to be compatible with non-uniform rational B-splines (NURBS). The main idea of the method is to divide the curve of interest into smaller segments so that each segment can be approximated with a biarc within a specified tolerance. The biarc is obtained by polygonal approximation to the curve segment and single biarc fitting to the polygon. In this process, the Hausdorff distance is used as a criterion for approximation quality. An iterative approach is proposed for fitting an optimized biarc to a given polygon and its two end tangents. The approach is robust and acceptable in computation since the Hausdorff distance between a polygon and its fitted biarc can be computed directly and precisely. The method is simple in concept, provides reasonable accuracy control, and produces the smaller number of biarcs in the resulting arc spline. Some experimental results demonstrate its usefulness and quality.     

Matching polygon fragments

Many computer vision systems model objects using polygons. If objects occlude each other or do not appear entirely in view, we need to match a polygon scene fragment with the polygon representation of the model objects. In this paper we present a way to match polygon fragments. Using polygon moments and cross moments we can compute a dissimilarity measure between two fragments. In addition, we also find the coordinate transform that maps one fragment onto the other. These polygon moments can be conputed by using just the end points of the line segments.

If the dissimilarity measure is less than a small number, then we can preliminarily conclude fragments. Otherwise the polygon fragments are dissimilar and are not considered any further. In computing the dissimilarity measure, we will also find a coordinate transform that maps one fragment to another. By using this coordinate transform, we can develop confirmation tests for determining whether the scene polygon fragments really belong to an occluded object.     

一种基于补偿法则的矩的快速算法

由于不变矩对图像的平移放大旋转的不敏感性，因此在模式识别、图像分类、场景匹配等图像处理和分析领域获得越来越广泛的应用．但是，求矩运算过程复杂、计算量大、使它的应用受到限制．基于Delta方法，提出了一种新的基于补偿法则的矩的快速算法．对任意二值图像分解为多条线段，图像的矩就等于所有线段的矩的和．对每一线段，将其左方(或上方)填满．每一线段的矩就等于填充后的线段的矩减去填充线段的矩．这样做的好处在于：一幅图像所有可能横(竖)线段的数目由N^2减少为N．引入一组N大小的数组，将求矩过程中大量重复计算的数据一次计算后存人数组，需要时查数组即得．从而极大地减少了计算量．由于填充后线段规格一致，便于用统一的公式计算且有利于编程．和已有的某些算法仅适用于无凹图像和矩计算结果是近似的相比，该算法计算结果准确，适用于任意复杂的二值图像．列出了已有矩算法运算量的评估，比较而言，所讨论的算法的计算量和用时都优于其他算法．     

折线链节点标注技术

针对传统多边形位置关系计算比较烦琐,以及简单多边形的理论难以拓展到一般多边形的问题,提出标注节点状态的方法.通过定义11种位置来描述折线链上每个节点的状态,再采用"线段端点与线段"和"线段端点与邻折线"的标注方法来实现任意折线链的标注,同时利用两线段分割预处理使相交仅发生在端点处,从而使算法更高效;然后给出折线链基本位置关系的节点特征,并且探讨了三维顶点的标注方法.该方法的标注原理简单、方法实用,算法空间和时间复杂度分别为O(n)和O(n2).实验结果表明,该方法对任意形状的折线链都能实现稳定标注;通过搜索节点状态特征可以求解折线链间的相互关系,还可以实现一般折线链的碰撞检测、相交区域计算以及多边形简单化分解等.     

Assessing the behaviour of polygonal approximation algorithms

In a recent paper, we described a method for assessing the accuracy of polygonal approximation algorithms (IEEE Trans. PAMI 19(6) (1997) 659). Here, we develop several measures to assess the stability of such approximation algorithms under two classes of variations, namely perturbations of the data and changes in the algorithms’ scale parameters. In order to quantify the former, a break-point stability index is defined and tested. For the latter, two indices are introduced; (1) a monotonicity index is applied to analyse the change in the approximation error or the number of line segments against increasing scale, and (2) a consistency index quantifies the variation in results produced at the same scale by an algorithm (but with different input parameter values). Finally, the previously developed accuracy figure of merit is calculated and averaged over 21 test curves for different parameter values to obtain more reliable scores.     

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.     

连接不相交线段成简单多边形(链)的算法及其实现

提出一个如何连接平面上n条线段与一个简单多边形或者简单多边形链的实际问题，并证明了连接平面上线段集S成一简单多边形链的一个充分条件——S中有一条线段连接凸壳CH（S）中不相领顶点。提出了连接平面上线段集S成一简单多边形或者简单多边形链的算法，其基本思想是首先农层计算线段集S的凸壳，并将这些凸壳改变为简单多边形；然后计算各多边形之间的交点，进而删去这些交点；最后俣并若干个简单多边形为一个简单多边形。当S中线段数目n较大时，用分治思想设计分治算法，较好地求解了这个问题。利用计算机求解这个问题具有实际应用价值。     

Adaptive polygonalization of implicitly defined surfaces

A method for finding an adaptive polygonal approximation of an implicitly defined surface is presented. For algebraic surfaces, the method yields an approximation guaranteed accurate to within some user-specified tolerance of the actual surface. This polygonalization can then be rendered using standard shaded polygon drawing techniques. A method for eliminating or improving the aspect ratios of the `skinny' polygons that often arise in traditional polygonalization methods is also presented. This method has proved particularly useful in the creation of polygonalization for finite-element analysis     

Minimizing the total projection of a set of vectors, with applications to layered manufacturing

In layered manufacturing (LM), a three-dimensional polyhedral solid is built as a stack of two-dimensional slices. Each slice (a polygon) is built by filling its interior with a sequence of parallel line segments (of some small non-zero width), in a process called hatching. A critical step in hatching is choosing a direction which minimizes the number of segments. In this paper, this problem is approximated as the problem of finding a direction which minimizes the total projected length of a certain set of vectors. Efficient algorithms are proposed for the latter problem, using techniques from computational geometry. Experimental and theoretical analyses show that this approach yields results that approximate closely the optimal solution to the hatching problem. Extensions of these results to several related problems are also discussed.     

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.     

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.     

Polygonal extrusion

A sweeping operation called polygonal extrusion is defined to improve the modeling power of CSG-based modeling. It is assumed that a 2D cross-sectional polygon (sweeping polygon) moves in space while its containing plane is kept orthogonal to the tangent direction of the trajectory curve, a planar polygonal chain having no self-intersections. The objective of the paper is to compute the boundary of the swept volume of the sweeping polygon as a set of polygons (or triangles). The most significant challenge to accomplishing this objective is the problem of trimming the swept volume. To solve the trimming problem, 2D-curve offsetting methods are employed. Two algorithms are presented for polygonal extrusion that are based on different offsetting methods, the Voronoi diagram and PWID offset. The proposed algorithms have been implemented and tested with various examples. Published online: 28 January 2003     

基于顶点编码的多边形窗口线裁剪高效算法

从多边形窗口线裁剪的本质特征出发，首次提出窗口顶点编码的新概念。以被裁剪直线为参照系，将多边形窗口划分为正区、负区和近零区三类区域，从而快速完成多边形窗口顶点编码。通过窗口顶点编码与传统的线段编码相结合，无须求交即可快速排除大部分窗外线段；进一步可以直接得到与直线相交的窗口边，加快了求交进程。更有意义的是，通过窗口顶点编码还可以准确判断并高效处理如下两类特殊相交情况：裁剪直线通过多边形的顶点、裁剪直线通过多边形的边。实验结果表明，新算法提高了裁剪效率并具有很好的稳定性。     

一种新的快速计算Legendre矩的方法

正交矩在模式识别，图像分析等领域有成功的应用，但由于正交矩的复杂性，有关正交矩的快速算法研究尚未得到很好的解决，该文提出一种 新的快速计算Ｌegendre矩的方法，该方法把基于像素点的二维Ｌegendre矩转换为线段的形式来计算，在计算出所有线段的积分后，使用扩展的Ｈatamian滤波方法来计算一维的Ｌegendre矩。结果显示新的算法有效地降低了计算的复杂度，并且，该方法能用于处理任意形状的物体。     

Cubic Bézier approximation of a digitized curve

In this paper we present an efficient technique for piecewise cubic Bézier approximation of digitized curve. An adaptive breakpoint detection method divides a digital curve into a number of segments and each segment is approximated by a cubic Bézier curve so that the approximation error is minimized. Initial approximated Bézier control points for each of the segments are obtained by interpolation technique i.e. by the reverse recursion of De Castaljau's algorithm. Two methods, two-dimensional logarithmic search algorithm (TDLSA) and an evolutionary search algorithm (ESA), are introduced to find the best-fit Bézier control points from the approximate interpolated control points. ESA based refinement is proved to be better experimentally. Experimental results show that Bézier approximation of a digitized curve is much more accurate and uses less number of points compared to other approximation techniques.     

An efficient evolutionary algorithm for accurate polygonal approximation

An optimization problem for polygonal approximation of 2-D shapes is investigated in this paper. The optimization problem for a digital contour of N points with the approximating polygon of K vertices has a search space of C(N, K) instances, i.e., the number of ways of choosing K vertices out of N points. A genetic-algorithm-based method has been proposed for determining the optimal polygons of digital curves, and its performance is better than that of several existing methods for the polygonal approximation problems. This paper proposes an efficient evolutionary algorithm (EEA) with a novel orthogonal array crossover for obtaining the optimal solution to the polygonal approximation problem. It is shown empirically that the proposed EEA outperforms the existing genetic-algorithm-based method under the same cost conditions in terms of the quality of the best solution, average solution, variance of solutions, and the convergence speed, especially in solving large polygonal approximation problems.     

基于遗传算法的多边形逼近3D数字曲线

首先对3D数字曲线进行简单的数据压缩．通过对该曲线上的点列进行二进制编码定义来表示数字曲线的染色体．二进制串中的每一个位称为基因，每一个逼近多边形和染色体形成1-1映射．目标函数使给定曲线和逼近多边形之间的均方差最小．构造了解决该问题的选择、交叉、变异三个算子．所得最优染色体中基因值为1的基因对应数字曲线的分界点．实验结果表明，该方法能够得到精确的逼近结果．