Method for fitting a parametric representation to a set of objects

Abstract

Described is a method for fitting a parametric representation to digital data. A vector distance field is generated to represent a set of objects and a parametric representation for the set of objects is initialized. A fitting error is determined from the vector distance field representation. The fitting error indicates the accuracy of the fit of the parametric representation to the set of objects. The parametric representation is adjusted and the fitting error is again determined in an iterative manner until an acceptable fitting error is achieved. The method has numerous technical advantages such as robustness, speed, simplicity relative to standard approaches, and the ability to manage constraints such as maintaining corners and enforcing continuity.

1 . A method for fitting a parametric representation to a set of objects, comprising:
 generating a vector distance field representation of the set of objects;   initializing a parametric representation to fit the set of objects;   determining a fitting error from the vector distance field representation, the fitting error indicating an accuracy of the fit of the parametric representation to the set of objects; and   adjusting the parametric representation to reduce the fitting error.   
   
   
       2 . The method of  claim 1  wherein the parametric representation comprises a parametric curve. 
   
   
       3 . The method of  claim 2  wherein the parametric curve comprises one of a line segment, a quadratic Bezier curve, a cubic Bezier curve and an nth order polynomial curve. 
   
   
       4 . The method of  claim 1  wherein the parametric representation comprises a parametric surface patch. 
   
   
       5 . The method of  claim 4  wherein the parametric surface patch comprises one of a triangle, a polygon, a Bezier patch, a NURBs patch and an nth order curved parametric patch. 
   
   
       6 . The method of  claim 1  wherein the parametric representation comprises an n-dimensional parametric shape. 
   
   
       7 . The method of  claim 6  wherein the n-dimensional parametric shape comprises one of a circle, an ellipse, a rectangular region, a sphere, a rectilinear solid, an ellipsoid, a super-ellipsoid and an n-dimensional solid. 
   
   
       8 . The method of  claim 1  wherein the parametric representation approximates a path corresponding to the set of objects. 
   
   
       9 . The method of  claim 1  wherein the parametric representation approximates a boundary corresponding to the set of objects. 
   
   
       10 . The method of  claim 1  wherein the parametric representation approximates a two-dimensional region corresponding to the set of objects. 
   
   
       11 . The method of  claim 1  wherein the parametric representation approximates a surface corresponding to the set of objects. 
   
   
       12 . The method of  claim 1  wherein the parametric representation approximates a volume corresponding to the set of objects. 
   
   
       13 . The method of  claim 1  wherein the parametric representation approximates an n-dimensional solid corresponding to the set of objects. 
   
   
       14 . The method of  claim 1  wherein the parametric representation approximates a medial axis corresponding to the set of objects. 
   
   
       15 . The method of  claim 1  wherein the parametric representation approximates a medial surface corresponding to the set of objects. 
   
   
       16 . The method of  claim 1  wherein the set of objects comprises one of a set of points, a set of line segments and a set of curves. 
   
   
       17 . The method of  claim 1  wherein the set of objects comprises a boundary representation. 
   
   
       18 . The method of  claim 17  wherein the boundary representation comprises one of a set of triangles, a set of quadrilaterals, a set of parametric patches, a set of Bezier patches and a set of NURBs patches. 
   
   
       19 . The method of  claim 1  wherein an object in the set of objects is represented by an implicit function. 
   
   
       20 . The method of  claim 1  wherein an object in the set of objects is represented by an analytic function. 
   
   
       21 . The method of  claim 1  wherein an object in the set of objects is represented by sampled data. 
   
   
       22 . The method of  claim 21  wherein the sampled data is represented as one of an image, a sampled volume and an adaptively sampled distance field. 
   
   
       23 . The method of  claim 1  wherein the vector distance field representation is an analytic function. 
   
   
       24 . The method of  claim 1  wherein the vector distance field representation is a procedure. 
   
   
       25 . The method of  claim 1  wherein the vector distance field representation is a regularly sampled vector distance field. 
   
   
       26 . The method of  claim 1  wherein the vector distance field representation is an adaptively sampled vector distance field. 
   
   
       27 . The method of  claim 1  wherein the vector distance field representation comprises a scalar distance field representation, the method further comprising determining a vector distance from the scalar distance field representation. 
   
   
       28 . The method of  claim 27  wherein the determining a vector distance from the scalar distance field representation comprises determining the vector distance from a derivative of the scalar distance field representation. 
   
   
       29 . The method of  claim 28  wherein the derivative is determined using an analytic function. 
   
   
       30 . The method of  claim 28  wherein the derivative is determined using a procedure. 
   
   
       31 . The method of  claim 28  wherein the scalar distance field representation is a sampled distance field and the derivative is determined using a gradient operator. 
   
   
       32 . The method of  claim 31  wherein the gradient operator is a central differences operator. 
   
   
       33 . The method of  claim 1  wherein the fitting error is a function of a set of measurements between the parametric representation and the set of objects. 
   
   
       34 . The method of  claim 33  wherein the set of measurements comprises one of a set of signed scalar distances, a set of unsigned scalar distances and a set of squared scalar distances. 
   
   
       35 . The method of  claim 33  wherein the set of measurements comprises a set of partial derivatives of the vector distance field. 
   
   
       36 . The method of  claim 33  wherein the measurements are determined from the vector distance field representation. 
   
   
       37 . The method of  claim 33  wherein the function samples the measurements at a set of points on the parametric representation. 
   
   
       38 . The method of  claim 33  wherein the function samples the measurements at a set of points near the parametric representation. 
   
   
       39 . The method of  claim 33  wherein the function samples the measurements at a set of points offset from the parametric representation. 
   
   
       40 . The method of  claim 1  wherein the adjusting comprises changing a set of parameters in the parametric representation. 
   
   
       41 . The method of  claim 40  wherein adjusting a parameter in the set of parameters comprises changing the parameter by a function of the derivative of the fitting error with respect to the parameter. 
   
   
       42 . The method of  claim 40  wherein adjusting a parameter in the set of parameters constrains the parameter according to at least one constraint. 
   
   
       43 . The method of  claim 42  wherein the at least one constraint comprises a geometric constraint. 
   
   
       44 . The method of  claim 43  wherein the geometric constraint is one of a point, a line, a curve and a surface. 
   
   
       45 . The method of  claim 42  wherein the at least one constraint comprises one of a function of a normal vector of the parametric representation, a function of a tangent vector of the parametric representation and a function of a curvature of the parametric representation. 
   
   
       46 . The method of  claim 1  wherein the determining and the adjusting are repeated until terminated by a user. 
   
   
       47 . The method of  claim 1  wherein the adjusting is iterated to reduce the fitting error. 
   
   
       48 . The method of  claim 47  wherein the adjusting is terminated when a maximum number of iterations have been performed. 
   
   
       49 . A computer program product for fitting a parametric representation to a set of objects, the computer program product comprising a computer useable medium having embodied therein program code comprising:
 program code for generating a vector distance field representation of the set of objects;   program code for initializing a parametric representation to fit the set of objects;   program code for determining a fitting error from the vector distance field representation, the fitting error indicating an accuracy of the fit of the parametric representation to the set of objects; and   program code for adjusting the parametric representation to reduce the fitting error.   
   
   
       50 . An apparatus for fitting a parametric representation to a set of objects, comprising:
 means for generating a vector distance field representation of the set of objects;   means for initializing a parametric representation to fit the set of objects;   means for determining a fitting error from the vector distance field representation, the fitting error indicating an accuracy of the fit of the parametric representation to the set of objects; and   means for adjusting the parametric representation to reduce the fitting error.