3170428
Fitting B-spline curves to point clouds by curvature-based squared distance minimization
Computing a curve to approximate data points is a problem encountered frequently in many applications in computer graphics, computer vision, CAD/CAM, and image processing. We present a novel and efficient method, called squared distance minimization (SDM), for computing a planar B-spline curve, closed or open, to approximate a target shape defined by a point cloud, that is, a set of unorganized, possibly noisy data points. We show that SDM significantly outperforms other optimization methods used currently in common practice of curve fitting. In SDM, a B-spline curve starts from some properly specified initial shape and converges towards the target shape through iterative quadratic minimization of the fitting error. Our contribution is the introduction of a new fitting error term, called the squared distance (SD) error term, defined by a curvature-based quadratic approximant of squared distances from data points to a fitting curve. The SD error term faithfully measures the geometric distance between a fitting curve and a target shape, thus leading to faster and more stable convergence than the point distance (PD) error term, which is commonly used in computer graphics and CAGD, and the tangent distance (TD) error term, which is often adopted in the computer vision community. To provide a theoretical explanation of the superior performance of SDM, we formulate the B-spline curve fitting problem as a nonlinear least squares problem and conclude that SDM is a quasi-Newton method which employs a curvature-based positive definite approximant to the true Hessian of the objective function. Furthermore, we show that the method based on the TD error term is a Gauss-Newton iteration, which is unstable for target shapes with high curvature variations, whereas optimization based on the PD error term is the alternating method that is known to have linear convergence.
772940
Fitting subdivision surfaces to unorganized point data using SDM
We study the reconstruction of smooth surfaces from point clouds. We use a new squared distance error term in optimization to fit a subdivision surface to a set of unorganized points, which defines a closed target surface of arbitrary topology. The resulting method is based on the framework of squared distance minimization (SDM) proposed by Pottmann et al. Specifically, with an initial subdivision surface having a coarse control mesh as input, we adjust the control points by optimizing an objective function through iterative minimization of a quadratic approximant of the squared distance function of the target shape. Our experiments show that the new method (SDM) converges much faster than the commonly used optimization method using the point distance error function, which is known to have only linear convergence. This observation is further supported by our recent result that SDM can be derived from the Newton method with necessary modifications to make the Hessian positive definite and the fact that the Newton method has quadratic convergence.
2900427
Reconstructing B-spline Curves from Point Clouds--A Tangential Flow Approach Using Least Squares Minimization
We present a novel algorithm based on least-squares minimization to approximate point cloud data in 2D plane with a smooth B-spline curve. The point cloud data may represent an open curve with self intersection and sharp corner. Unlike other existing methods, such as the moving least-squares method and the principle curve method, our algorithm does not need a thinning process. The idea of our algorithm is intuitive and simple - we make a B-spline curve grow along the tangential directions at its two end-points following local geometry of point clouds. Our algorithm generates appropriate control points of the fitting B-spline curve in the least squares sense. Although presented for the 2D case, our method can be extended in a straightforward manner to fitting data points by a B-spline curve in higher dimensions
181647
Geometric modeling with conical meshes and developable surfaces
In architectural freeform design, the relation between shape and fabrication poses new challenges and requires more sophistication from the underlying geometry. The new concept of conical meshes satisfies central requirements for this application: They are quadrilateral meshes with planar faces, and therefore particularly suitable for the design of freeform glass structures. Moreover, they possess a natural offsetting operation and provide a support structure orthogonal to the mesh. Being a discrete analogue of the network of principal curvature lines, they represent fundamental shape characteristics. We show how to optimize a quad mesh such that its faces become planar, or the mesh becomes even conical. Combining this perturbation with subdivision yields a powerful new modeling tool for all types of quad meshes with planar faces, making subdivision attractive for architecture design and providing an elegant way of modeling developable surfaces.
12158249
Bisingular maps on the sphere and the projective plane
Abstract A map is bisingular if each edge is either a loop or an isthmus (i.e., on the boundary of the same face). In this paper we study the number of rooted bisingular maps on the plane or projective plane and also we present formulae for such maps with up to three or more parameters: the root valency, the number of isthmus, the number of essential loops, and the number of planar loops.
18963770
A quasi-Monte Carlo method for computing areas of point-sampled surfaces
A novel and efficient quasi-Monte Carlo method for computing the area of a point-sampled surface with associated surface normal for each point is presented. Our method operates directly on the point cloud without any surface reconstruction procedure. Using the Cauchy-Crofton formula, the area of the point-sampled surface is calculated by counting the number of intersection points between the point cloud and a set of uniformly distributed lines generated with low-discrepancy sequences. Based on a clustering technique, we also propose an effective algorithm for computing the intersection points of a line with the point-sampled surface. By testing on a number of point-based models, experiments suggest that our method is more robust and more efficient than those conventional approaches based on surface reconstruction.
1369726
Adaptive Data Fusion for Energy Efficient Routing in Wireless Sensor Networks
While in-network data fusion can reduce data redundancy and, hence, curtail network load, the fusion process itself may introduce significant energy consumption for emerging wireless sensor networks with vectorial data and/or security requirements. Therefore, fusion-driven routing protocols for sensor networks cannot optimize over communication cost only - fusion cost must also be accounted for. In our prior work, while a randomized algorithm termed MFST is devised toward this end, it assumes that fusion shall be performed at any intersection node whenever data streams encounter. In this paper, we design a novel routing algorithm, called adaptive fusion Steiner tree (AFST), for energy efficient data gathering. Not only does AFST jointly optimize over the costs for both data transmission and fusion, but also AFST evaluates the benefit and cost of data fusion along information routes and adaptively adjusts whether fusion shall be performed at a particular node. Analytically and experimentally, we show that AFST achieves better performance than existing algorithms, including SLT, SPT, and MFST
17413518
Enhancing the Effectiveness of Clustering with Spectra Analysis
For many clustering algorithms, such as K-Means, EM, and CLOPE, there is usually a requirement to set some parameters. Often, these parameters directly or indirectly control the number of clusters, that is, k, to return. In the presence of different data characteristics and analysis contexts, it is often difficult for the user to estimate the number of clusters in the data set. This is especially true in text collections such as Web documents, images, or biological data. In an effort to improve the effectiveness of clustering, we seek the answer to a fundamental question: How can we effectively estimate the number of clusters in a given data set? We propose an efficient method based on spectra analysis of eigenvalues (not eigenvectors) of the data set as the solution to the above. We first present the relationship between a data set and its underlying spectra with theoretical and experimental results. We then show how our method is capable of suggesting a range of k that is well suited to different analysis contexts. Finally, we conclude with further empirical results to show how the answer to this fundamental question enhances the clustering process for large text collections.
13883054
Dynamic Programming via Static Incrementalization
Dynamic programming is an important algorithm design technique. It is used for solving problems whose solutions involve recursively solving subproblems that share subsubproblems. While a straightforward recursive program solves common subsubproblems repeatedly and often takes exponential time, a dynamic programming algorithm solves every subsubproblem just once, saves the result, reuses it when the subsubproblem is encountered again, and takes polynomial time. This paper describes a systematic method for transforming programs written as straightforward recursions into programs that use dynamic programming. The method extends the original program to cache all possibly computed values, incrementalizes the extended program with respect to an input increment to use and maintain all cached results, prunes out cached results that are not used in the incremental computation, and uses the resulting incremental program to form an optimized new program. Incrementalization statically exploits semantics of both control structures and data structures and maintains as invariants equalities characterizing cached results. The principle underlying incrementalization is general for achieving drastic program speedups. Compared with previous methods that perform memoization or tabulation, the method based on incrementalization is more powerful and systematic. It has been implemented and applied to numerous problems and succeeded on all of them.