A Full Bayesian Approach to Curve and Surface Reconstruction

When interpolating incomplete data, one can choose a parametric model, or opt for a more general approach and use a non-parametric model which allows a very large class of interpolants. A popular non-parametric model for interpolating various types of data is based on regularization, which looks for an interpolant that is both close to the data and also smooth in some sense. Formally, this interpolant is obtained by minimizing an error functional which is the weighted sum of a fidelity term and a smoothness term.The classical approach to regularization is: select optimal weights (also called hyperparameters) that should be assigned to these two terms, and minimize the resulting error functional.However, using only the optimal weights does not guarantee that the chosen function will be optimal in some sense, such as the maximum likelihood criterion, or the minimal square error criterion. For that, we have to consider all possible weights.The approach suggested here is to use the full probability distribution on the space of admissible functions, as opposed to the probability induced by using a single combination of weights. The reason is as follows: the weight actually determines the probability space in which we are working. For a given weight , the probability of a function f is proportional to exp(– f² _uu du) (for the case of a function with one variable). For each different , there is a different solution to the restoration problem; denote it by f. Now, if we had known , it would not be necessary to use all the weights; however, all we are given are some noisy measurements of f, and we do not know the correct . Therefore, the mathematically correct solution is to calculate, for every , the probability that f was sampled from a space whose probability is determined by , and average the different f's weighted by these probabilities. The same argument holds for the noise variance, which is also unknown.Three basic problems are addressed is this work: Computing the MAP estimate, that is, the function f maximizing Pr(f/D) when the data D is given. This problem is reduced to a one-dimensional optimization problem. Computing the MSE estimate. This function is defined at each point x as f(x)Pr(f/D) f. This problem is reduced to computing a one-dimensional integral.In the general setting, the MAP estimate is not equal to the MSE estimate. Computing the pointwise uncertainty associated with the MSE solution. This problem is reduced to computing three one-dimensional integrals.     

G2 Surface Interpolation Over General Topology Curve Networks

The basic idea of curve network‐based design is to construct smoothly connected surface patches, that interpolate boundaries and cross‐derivatives extracted from the curve network. While the majority of applications demands only tangent plane (G¹) continuity between the adjacent patches, curvature continuous connections (G²) may also be required. Examples include special curve network configurations with supplemented internal edges, “master‐slave” curvature constraints, and general topology surface approximations over meshes. The first step is to assign optimal surface curvatures to the nodes of the curve network; we discuss different optimization procedures for various types of nodes. Then interpolant surfaces called parabolic ribbons are created along the patch boundaries, which carry first and second derivative constraints. Our construction guarantees that the neighboring ribbons, and thus the respective transfinite patches, will be G² continuous. We extend Gregory's multi‐sided surface scheme in order to handle parabolic ribbons, involving the blending functions, and a new sweepline parameterization. A few simple examples conclude the paper.     

Robust and Efficient Surface Reconstruction From Range Data

We describe a robust but simple algorithm to reconstruct a surface from a set of merged range scans. Our key contribution is the formulation of the surface reconstruction problem as an energy minimisation problem that explicitly models the scanning process. The adaptivity of the Delaunay triangulation is exploited by restricting the energy to inside/outside labelings of Delaunay tetrahedra. Our energy measures both the output surface quality and how well the surface agrees with soft visibility constraints. Such energy is shown to perfectly fit into the minimum s ? t cuts optimisation framework, allowing fast computation of a globally optimal tetrahedra labeling, while avoiding the “shrinking bias” that usually plagues graph cuts methods. The behaviour of our method confronted to noise, undersampling and outliers is evaluated on several data sets and compared with other methods through different experiments: its strong robustness would make our method practical not only for reconstruction from range data but also from typically more difficult dense point clouds, resulting for instance from stereo image matching. Our effective modeling of the surface acquisition inverse problem, along with the unique combination of Delaunay triangulation and minimum s ? t cuts, makes the computational requirements of the algorithm scale well with respect to the size of the input point cloud.     

On Variational Curve Smoothing and Reconstruction

In this paper we discuss and experimentally compare variational methods for curve denoising, curve smoothing and curve reconstruction problems. The methods are based on defining suitable cost functionals to be minimized, the cost being the combination of a fidelity term measuring the “distance” of a curve from the data and a smoothness term measuring the curve’s L ₁-norm or length.     

基于视觉原理的曲线重构算法研究

曲线和曲面的重构是逆向工程中的重要问题,特别是按照计算机图形学中点线面的发展规律,曲线重构更是其中很重要的一步,为后面的曲面重构奠定了研究基础。论文研究和实现了一种曲线重构算法,该算法将人类的视觉具有的接近性和连续性融入到了曲线重构算法中。实验结果表明了该算法的有效性。     

Curve Reconstruction with Many Fewer Samples

We consider the problem of sampling points from a collection of smooth curves in the plane, such that the Crust family of proximity‐based reconstruction algorithms can rebuild the curves. Reconstruction requires a dense sampling of local features, i.e., parts of the curve that are close in Euclidean distance but far apart geodesically. We show that ε < 0.47‐sampling is sufficient for our proposed HNN‐Crust variant, improving upon the state‐of‐the‐art requirement of ε < ‐sampling. Thus we may reconstruct curves with many fewer samples. We also present a new sampling scheme that reduces the required density even further than ε < 0.47‐sampling. We achieve this by better controlling the spacing between geodesically consecutive points. Our novel sampling condition is based on the reach, the minimum local feature size along intervals between samples. This is mathematically closer to the reconstruction density requirements, particularly near sharp‐angled features. We prove lower and upper bounds on reach ρ‐sampling density in terms of lfs ε‐sampling and demonstrate that we typically reduce the required number of samples for reconstruction by more than half.     

On the Curve Reconstruction in Riemannian Manifolds

In this article we extend the computational geometric curve reconstruction approach to the curves embedded in the Riemannian manifold. We prove that the minimal spanning tree, given a sufficiently dense sample, correctly reconstructs the smooth arcs which can be used to reconstruct closed and simple curves in Riemannian manifolds. The proof is based on the behavior of the curve segment inside the tubular neighborhood of the curve. To take care of the local topological changes of the manifold, the tubular neighborhood is constructed in consideration with the injectivity radius of the underlying Riemannian manifold. We also present examples of successfully reconstructed curves and show applications of curve reconstruction to ordering motion frames.     

支持向量回归模型在曲线光顺拟合中的改进

几何逆向工程中的光顺曲线重构问题本质上属于回归问题。支持向量回归机是求解回归问题的新的十分有效的方法。论文研究用支持向量回归机处理光顺曲线的重构问题。鉴于后者有着对于光顺性的特殊要求,已有的支持向量机并不适用。通过修正惩罚因子对支持向量机加以改造,即根据测量数据点的分布情况,利用各测量点圆率的特性确定对应的惩罚因子,从而实现了自由曲线的光顺重构。数值试验表明新方法可以剔除输入数据中不光顺点的影响,并在给定的精度条件下有效地逼近曲线,达到较好的拟合效果。     

基于e1范数最小化的非流形曲线族重构

从散乱点集重构曲线族在计算机视觉、逆向工程和医学图像处理等方面有着广泛的应用,非流形曲线族重构是其中的难点问题.文中在压缩传感理论基础上,提出一种基于e1范数最小化的非流形曲线族重构方法.该方法首先将散乱点集的法矢和位置信号表示为稀疏形式,通过e1范数优化方法,重建法矢信号和位置信号;之后,根据重建的法矢和位置计算点集的双边权,在此基础上构建最小生成树(Minimum Spanning Tree,MST)来重构曲线族;最后通过后处理过程,完成对重构曲线族的开闭处理.实验表明,该算法能处理包含开、闭曲线,流形、非流形曲线,以及具有尖锐特征的曲线等复杂情况的曲线族,并且对噪声较鲁棒.     

Adapting Feature Curve Networks to a Prescribed Scale

Feature curves on surface meshes are usually defined solely based on local shape properties such as dihedral angles and principal curvatures. From the application perspective, however, the meaningfulness of a network of feature curves also depends on a global scale parameter that takes the distance between feature curves into account, i.e., on a coarse scale, nearby feature curves should be merged or suppressed if the surface region between them is not representable at the given scale/resolution. In this paper, we propose a computational approach to the intuitive notion of scale conforming feature curve networks where the density of feature curves on the surface adapts to a global scale parameter. We present a constrained global optimization algorithm that computes scale conforming feature curve networks by eliminating curve segments that represent surface features, which are not compatible to the prescribed scale. To demonstrate the usefulness of our approach we apply isotropic and anisotropic remeshing schemes that take our feature curve networks as input. For a number of example meshes, we thus generate high quality shape approximations at various levels of detail.     

Image Interpolation Through Surface Reconstruction

Reconstructing an HR （high-resolution） image which preserves the image intrinsic structures from its LR （low-resolution） counterpart is highly challenging. This paper proposes a new surface reconstruction algorithm applied to image interpolation. The interpolation surface for the whole image is generated by putting all the quadratic polynomial patches together. In order to eliminate the jaggies of the edge, a new weight fimction containing edge information is incorporated into the patch reconstruction procedure as a constraint. Extensive experimental results demonstrate that our method produces better results across a wide range of scenes in terms of both quantitative evaluation and subjective visual quality.     

Surface Reconstruction Using Alpha Shapes

We describe a method for reconstructing an unknown surface from a set of data points. The basic approach is to extract the surface as a polygon mesh from an α-shape. Even though alpha shapes are generalized polytopes having complicated internal structures, we show that manifold surfaces, with or without boundaries, can be efficiently generated, and these surfaces completely describe the α-shapes to the extent that they are visible from outside. Unlike the original α-shapes, the polygonal surfaces can be easily simplified to yield compact models suitable for a variety of geometric modeling applications such as surface fitting.     

Streaming Surface Reconstruction Using Wavelets

We present a streaming method for reconstructing surfaces from large data sets generated by a laser range scanner using wavelets. Wavelets provide a localized, multiresolution representation of functions and this makes them ideal candidates for streaming surface reconstruction algorithms. We show how wavelets can be used to reconstruct the indicator function of a shape from a cloud of points with associated normals. Our method proceeds in several steps. We first compute a low‐resolution approximation of the indicator function using an octree followed by a second pass that incrementally adds fine resolution details. The indicator function is then smoothed using a modified octree convolution step and contoured to produce the final surface. Due to the local, multiresolution nature of wavelets, our approach results in an algorithm over 10 times faster than previous methods and can process extremely large data sets in the order of several hundred million points in only an hour.     

Rational B-Splines for Curve and Surface Representation

Nonuniform, rational B-splines, capable of representing both precise quadric primitives and free-form curves and surfaces, offer an efficient mathematical form for geometric modeling systems.     

Crawl through Neighbors: A Simple Curve Reconstruction Algorithm

Given a planar point set sampled from an object boundary, the process of approximating the original shape is called curve reconstruction. In this paper, a novel non‐parametric curve reconstruction algorithm based on Delaunay triangulation has been proposed and it has been theoretically proved that the proposed method reconstructs the original curve under ε‐sampling. Starting from an initial Delaunay seed edge, the algorithm proceeds by finding an appropriate neighbouring point and adding an edge between them. Experimental results show that the proposed algorithm is capable of reconstructing curves with different features like sharp corners, outliers, multiple objects, objects with holes, etc. The proposed method also works for open curves. Based on a study by a few users, the paper also discusses an application of the proposed algorithm for reconstructing hand drawn skip stroke sketches, which will be useful in various sketch based interfaces.     

基于场表示的平面无序点集曲线重建算法

由无序离散点集重建出曲线曲面模型,在反求工程与计算机视觉中都有着广泛的应用。针对平面无序带噪声的曲线重建问题,通过模拟带电粒子在空间中形成场分布的现象,构造了一个反映平面点集形状与分布稠密程度的场函数,以场函数曲面的脊线在平面上的投影作为平面无序点集的重建曲线。为求得重建曲线,可先在平面上选取一条适当初始曲线,由初始曲线沿着场函数的梯度方向运动,其极限位置便为重建曲线。大量实例证明,这种方法简单可行,可获得满意的重建曲线;同时,对于带插值约束条件以及分布不均匀的点集,也可以获得满意的结果。     

基于控制顶点扰动的平面二次曲线重构

基于控制顶点扰动的思想提出了一种新的曲线重构算法,用于构造一条分段二次B样条曲线来逼近平面上的散乱数据点．逐个输入数据点后,通过对控制顶点进行扰动来求取新的控制顶点．重构曲线的最终控制网格可通过求解一个非线性优化问题获得．一系列实验表明：该算法在经过少数几步迭代后很快就能收敛．该算法几何直观性强、操作简单,对平面上具有不同形状和不均匀采样误差的散乱数据都能得到很好的重构效果     

四边曲面重建中的边界优化算法

文中针对Floater“保形参数化”方法存在的局限性,研究了四边曲面重建中,边界曲折程度的评定方法。通过比较边界上网格点的曲率值,构造形式上的四边拓扑曲面;通过对边界网格的优化剖分,获得相对平滑的边界曲线。与Floater算法相比,提出了曲折边界的平滑剖分方法,改善了重建曲面边界上的扭曲变形,为Floater重建算法在工程CAD模型中的推广提供了实用途径。