Medial axis computation for planar free-form shapes

We present a simple, efficient, and stable method for computing—with any desired precision—the medial axis of simply connected planar domains. The domain boundaries are assumed to be given as polynomial spline curves. Our approach combines known results from the field of geometric approximation theory with a new algorithm from the field of computational geometry. Challenging steps are (1) the approximation of the boundary spline such that the medial axis is geometrically stable, and (2) the efficient decomposition of the domain into base cases where the medial axis can be computed directly and exactly. We solve these problems via spiral biarc approximation and a randomized divide & conquer algorithm.     

Area-Based Medial Axis of Planar Curves

A new definition of affine invariant medial axis of planar closed curves is introduced. A point belongs to the affine medial axis if and only if it is equidistant from at least two points of the curve, with the distance being a minimum and given by the areas between the curve and its corresponding chords. The medial axis is robust, eliminating the need for curve denoising. In a dynamical interpretation of this affine medial axis, the medial axis points are the affine shock positions of the affine erosion of the curve. We propose a simple method to compute the medial axis and give examples. We also demonstrate how to use this method to detect affine skew symmetry in real images.     

Computation of medial axis and offset curves of curved boundaries in planar domain

In this paper, we begin our research from the generating theory of the medial axis. The normal equidistant mapping relationships between two boundaries and its medial axis have been proposed based on the moving Frenet frames and Cesaro’s approach of the differential geometry. Two pairs of adjoint curves have been formed and the geometrical model of the medial axis transform of the planar domains with curved boundaries has been established. The relations of position mapping, scale transform and differential invariants between the curved boundaries and the medial axis have been investigated. Based on this model, a tracing algorithm for the computation of the medial axis has been generated. In order to get the accurate medial axis and branch points, a Two_Tangent_Points_Circle algorithm and a Three_Tangent_Points_Circle algorithm have been generated, which use the results of the tracing algorithm as the initial values to make the iterative process effective. These algorithms can be used for the computation of the medial axis effectively and accurately. Based on the medial axis transform and the envelope theory, the trimmed offset curves of curved boundaries have been investigated. Several numerical examples are given at the end of the paper.     

Rational adaptive blends among obstacles in 3D by contour method

In this paper we will continue in investigating ‘contour method’ and its using for the computation of rational parameterizations of canal surfaces without a need of sum of squares (SOS) decomposition. Further approaches for constructing flexible smooth transitions between canal surfaces will be presented. Mainly, we focus on one particular application of recently introduced rational envelope curves, newly constructed over an arbitrary planar rational curve in space. Using this type of curves significantly simplifies the previous methods discussed in Bizzarri (2015), and mainly new situations, which could not have been handled with the previous setup, are successfully solved, now. Especially a method for constructing rational adaptive blends which bypass a given obstacle (or more given obstacles when needed) is thoroughly discussed and its functionality is demonstrated on a number of examples. The designed approach works not only for simple obstacles represented by one-dimensional medial axis transforms but also for more general obstacles described by two-dimensional medial surface transforms.     

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     

基于优化DRG的三维人体点云骨架提取方法

针对离散Reeb图（Discrete Reeb Graph,DRG）描述人体骨架时分支部位骨架线偏离中轴的问题,采用了能量函数最小化的方法对DRG曲线进行优化。将人体模型的DRG曲线作为初始骨架,定义其能量函数,在点云模型的距离场梯度的作用下,迭代地调整偏离中轴目标段的曲线位置使其逐渐逼近中轴,能量函数最小时得到优化的骨架。将该算法应用于同一模特四个不同姿势和四个不同模特同一姿势的人体点云模型,并与基于拉普拉斯算子的点云收缩的骨架提取方法进行了比较。结果表明,该算法能够很好地适应各种不同姿势和体型,模型分叉部位的特征得到更加完善的描述,得到的骨架曲线更接近模型的中轴。     

Efficient Shape Modeling: <Emphasis Type="BoldItalic">⋮</Emphasis>-Entropy,Adaptive Coding,and Boundary Curves -vs- Blum’s Medial Axis

We propose efficiency of representation as a criterion for evaluating shape models, then apply this criterion to compare the boundary curve representation with the medial axis. We estimate the ⋮-entropy of two compact classes of curves. We then construct two adaptive encodings for non-compact classes of shapes, one using the boundary curve and the other using the medial axis, and determine precise conditions for when the medial axis is more efficient. Finally, we apply our results to databases of naturally occurring shapes, determining whether the boundary or medial axis is more efficient. Along the way we construct explicit near-optimal boundary-based approximations for compact classes of shapes, construct an explicit compression scheme for non-compact classes of shapes based on the medial axis, and derive some new results about the medial axis.     

Medial axis of a planar region by offset self-intersections

The medial axis (MA) of a planar region is the locus of those maximal disks contained within its boundary. This entity has many CAD/CAM applications. Approximations based on the Voronoi diagram are efficient for linear-arc boundaries, but such constructions are more difficult if the boundary is free. This paper proposes an algorithm for free-form boundaries that uses the relation between MA and offsets. It takes the curvature information from the boundary in order to find the self-intersections of successive offset curves. These self-intersection points belong to the MA and can be interpolated to obtain an approximation in Bézier form. This method also approximates the medial axis transform by using the offset distance to each self-intersection.     

Continuous point projection to planar freeform curves using spiral curves

We present an efficient algorithm for projecting a continuously moving query point to a family of planar freeform curves. The algorithm is based on the one-sided Hausdorff distance from the trajectory curve (of the query point) to the planar curves. Using a bounding volume hierarchy (BVH) of the planar curves, we estimate an upper bound [`(h)]\overline{h} of the one-sided Hausdorff distance and eliminate redundant curve segments when they are more than distance [`(h)]\overline{h} away from the trajectory curve. Recursively subdividing the trajectory curve and repeating the same elimination procedure to the BVH of the remaining curves, we can efficiently determine where to project the moving query point. The explicit continuous point projection is then interpreted as a curve reparameterization problem, for which we propose a few simple approximation techniques. Using several experimental results, we demonstrate the effectiveness of the proposed approach.     

Parameter synthesis of higher kinematic pairs

We describe a parameter synthesis algorithm for planar mechanical systems comprised of higher kinematic pairs in which each part translates along a fixed axis or rotates around a fixed point. This is an important class of systems and is not addressed by prior synthesis research. Kinematic function is computed from the CAD models of the parts and is represented graphically as configuration spaces. Design flaws appear as incorrectly shaped contact curves, as incorrectly placed intersection points, and as incorrect curve sequences. The designer reshapes the faulty curves with the keyboard mouse. The synthesis algorithm computes new parameter values that realize the changes without harmful side effects, using a novel form of constrained optimization. The algorithm has been tested on industrial applications.     

Efficient offset trimming for deformable planar curves using a dynamic hierarchy of bounding circular arcs

We present an efficient algorithm for computing a family of trimmed offsets for planar freeform curves under deformation. The algorithm is based on a dynamic bounding volume hierarchy (BVH) for the untrimmed offsets of a given planar curve, which can be generated efficiently using a hierarchy of recursive bisections of the given curve. The proposed algorithm is effective for deformable planar curves. At each time frame, we segment the input curve into monotone spiral pieces (Barton and Elber, 2011), which is the only pre-processing needed for the dynamic BVH construction. To speed up the on-line generation of dynamic BVH, we employ the bounding circular arcs (BCA) of Meek and Walton (1995) that can be computed very efficiently using the position and tangent information at the endpoints of each monotone spiral curve segment. Using several experimental results, we demonstrate the performance improvement of our algorithm over the previous biarc-based algorithm of Kim et al. (2012).     

Generating subdivision surfaces from profile curves

The construction of freeform models has always been a challenging task. A popular approach is to edit a primitive object such that its projections conform to a set of given planar curves. This process is tedious and relies very much on the skill and experience of the designer in editing 3D shapes. This paper describes an intuitive approach for the modeling of freeform objects based on planar profile curves. A freeform surface defined by a set of orthogonal planar curves is created by blending a corresponding set of sweep surfaces. Each of the sweep surfaces is obtained by sweeping a planar curve about a computed axis. A Catmull-Clark subdivision surface interpolating a set of data points on the object surface is then constructed. Since the curve points lying on the computed axis of the sweep will become extraordinary vertices of the subdivision surface, a mesh refinement process is applied to adjust the mesh topology of the surface around the axis points. In order to maintain characteristic features of the surface defined with the planar curves, sharp features on the surface are located and are retained in the mesh refinement process. This provides an intuitive approach for constructing freeform objects with regular mesh topology using planar profile curves.     

Efficient planar object tracking and parameter estimation usingcompactly represented cubic B-spline curves

In this paper, we consider the problem of matching 2D planar object curves from a database, and tracking moving object curves through an image sequence. The first part of the paper describes a curve data compression method using B-spline curve approximation. We present a new constrained active B-spline curve model based on the minimum mean square error (MMSE) criterion, and an iterative algorithm for selecting the “best” segment border points for each B-spline curve. The second part of the paper describes a method for simultaneous object tracking and affine parameter estimation using the approximate curves and profiles. We propose a novel B-spline point assignment algorithm which incorporates the significant corners for interpolating corresponding points on the two curves to be compared. A gradient-based algorithm is presented for simultaneously tracking object curves, and estimating the associated translation, rotation and scaling parameters. The performance of each proposed method is evaluated using still images and image sequences containing simple objects     

边界简化与多目标优化相结合的高质量四边形网格生成

目的 高质量四边形网格生成是计算机辅助设计、等几何分析与图形学领域中一个富有挑战性的重要问题。针对这一问题,提出一种基于边界简化与多目标优化的高质量四边形网格生成新框架。方法 首先针对亏格非零的平面区域,提出一种将多连通区域转化为单连通区域的方法,可生成高质量的插入边界;其次,提出"可简化角度"和"可简化面积比率"两个阈值概念,从顶点夹角和顶点三角形面积入手,将给定的多边形边界简化为粗糙多边形;然后对边界简化得到的粗糙多边形进行子域分解,并确定每个子域内的网格顶点连接信息;最后提出四边形网格的均匀性和正交性度量目标函数,并通过多目标非线性优化技术确定网格内部顶点的几何位置。结果 在同样的离散边界下,本文方法与现有方法所生成的四边网格相比,所生成的四边网格顶点和单元总数目较少,网格单元质量基本类似,计算时间成本大致相同,但奇异点数目可减少70% 80%,衡量网格单元质量的比例雅克比值等相关指标均有所提高。结论 本文所提出的四边形网格生成方法能够有效减少网格中的奇异点数目,并可生成具有良好光滑性、均匀性和正交性的高质量四边形网格,非常适用于工程分析和动画仿真。     

Computing a compact spline representation of the medial axis transform of a 2D shape

We present a full pipeline for computing the medial axis transform of an arbitrary 2D shape. The instability of the medial axis transform is overcome by a pruning algorithm guided by a user-defined Hausdorff distance threshold. The stable medial axis transform is then approximated by spline curves in 3D to produce a smooth and compact representation. These spline curves are computed by minimizing the approximation error between the input shape and the shape represented by the medial axis transform. Our results on various 2D shapes suggest that our method is practical and effective, and yields faithful and compact representations of medial axis transforms of 2D shapes.     

由整体到局部的平面曲线部分匹配算法

在基于曲线匹配的检索系统中,提高曲线的匹配速度和精度具有重要的意义.提出一种平面曲线的部分匹配算法,该算法分为整体搜索和局部匹配2个阶段.首先整体搜索确定候选的匹配区域,然后在局部进行精确匹配和验证.对于特征点较少的曲线,根据曲率极值点将曲线划分为多条曲线段,采用局部线性搜索法实现曲线的部分匹配.实验结果说明了算法的有效性.     

Multiple View Geometry of General Algebraic Curves

We introduce a number of new results in the context of multi-view geometry from general algebraic curves. We start with the recovery of camera geometry from matching curves. We first show how one can compute, without any knowledge on the camera, the homography induced by a single planar curve. Then we continue with the derivation of the extended Kruppa's equations which are responsible for describing the epipolar constraint of two projections of a general algebraic curve. As part of the derivation of those constraints we address the issue of dimension analysis and as a result establish the minimal number of algebraic curves required for a solution of the epipolar geometry as a function of their degree and genus.We then establish new results on the reconstruction of general algebraic curves from multiple views. We address three different representations of curves: (i) the regular point representation in which we show that the reconstruction from two views of a curve of degree d admits two solutions, one of degree d and the other of degree d(d – 1). Moreover using this representation, we address the problem of homography recovery for planar curves, (ii) dual space representation (tangents) for which we derive a lower bound for the number of views necessary for reconstruction as a function of the curve degree and genus, and (iii) a new representation (to computer vision) based on the set of lines meeting the curve which does not require any curve fitting in image space, for which we also derive lower bounds for the number of views necessary for reconstruction as a function of curve degree alone.     

Curvature-based blending of closed planar curves

A common way of blending between two planar curves is to linearly interpolate their signed curvature functions and to reconstruct the intermediate curve from the interpolated curvature values. But if both input curves are closed, this strategy can lead to open intermediate curves. We present a new algorithm for solving this problem, which finds the closed curve whose curvature is closest to the interpolated values. Our method relies on the definition of a suitable metric for measuring the distance between two planar curves and an appropriate discretization of the signed curvature functions.     

一种参数三次样条曲线光顺优化算法

论文给出了一种基于修改因子和修改角度的平面参数三次样条曲线的优化 光顺算法,该算法通过求解一个带有修改因子 和修改角度 的目标函数得到光顺后的型值 点,插值光顺后的型值点得到光顺曲线。目的是使曲线的曲率变化均匀的同时,使光顺后的 曲线与原曲线的偏差尽量小,此算法简单易行,计算量较小。     

平面碎片匹配算法的研究

在分析平面曲线的几何特性的基础上,提出了一种基于曲率等不变量的平面非规则边界曲线匹配的算法,该方法通过提取平面非规则曲线的角点和匹配角点来寻找初始匹配点,同时利用对应点的曲率相等或者等价的几何特性来匹配平面非规则曲线,并且在理论和实验上对方法的可行性进行了证明。