Faithful Least-Squares Fitting of Spheres, Cylinders, Cones and Tori for Reliable Segmentation

Gábor Lukács, Ralph R. Martin, A. David MarshallECCV 1998 · DOI

TL;DR

This paper introduces a robust set of least-squares fitting methods for common geometric primitives (spheres, cylinders, cones, and tori) to 3D point cloud data. These methods are designed to be "faithful" to the true geometric distance, ensuring stable fitting even as surface complexity decreases, which is crucial for reliable reverse engineering of mechanical components.

What Problem Does This Paper Address?

The paper tackles a key challenge in reverse engineering: reconstructing 3D solid models from scanned object data, typically captured by laser scanners as point clouds. A critical step in this process is segmenting the point cloud into regions corresponding to simple geometric shapes and then fitting those shapes accurately. While fitting planes is well-understood, fitting more complex primitives like spheres, cylinders, cones, and especially tori, using least-squares methods that are both accurate and robust to noise and varying surface properties, remains a significant problem. Existing methods can be sensitive to parameter choices, suffer from singularities, or provide results that are not "faithful" to the true geometric distance, leading to inaccurate models.

Methods

The core contribution is a set of novel, non-linear least-squares fitting methods for spheres, cylinders, cones, and tori. The key innovation lies in their "faithful" distance functions. Instead of minimizing the squared algebraic distance (which can be unfaithful and lead to biased results), they derive distance functions that approximate the true Euclidean distance and, importantly, share the same zero set and derivatives at the zero set. This is achieved by transforming the distance function to eliminate square roots, often by minimizing a modified squared distance.

For each primitive, the paper defines a parameterization and derives the corresponding faithful distance function. The fitting process then involves minimizing the sum of these squared distances over the segmented point data. The methods are designed to be robust to singularities and to naturally degenerate to simpler shapes (e.g., a sphere fitting becoming a plane fit as curvature decreases), unlike some previous approaches that might diverge.

Datasets

The paper mentions using both simulated and real scanner data.

  • Simulated 3D point data: Described as accurate to five significant digits. Examples are shown in Figures 1 and 2.
  • Real scanner data: Specifically, a depth-map of the "Heriot-Watt" test part captured using a 3D Scanners Replica device is illustrated in Figures 8 and 9.

No new benchmarks are introduced; the focus is on the fitting methods themselves.

Key Insights and Ideas

  • Faithful Distance Functions are Crucial: The paper strongly emphasizes that using distance functions that accurately reflect the true geometric distance is paramount for robust and reliable fitting, especially for complex surfaces or when degenerating to simpler forms.
  • Robustness through Parameterization: The chosen parameterizations and derived distance functions are designed to avoid singularities and behave well as surface properties (like curvature) change, making the methods more general and less prone to failure.
  • Natural Degeneration to Simpler Shapes: A significant advantage highlighted is that as the principal curvatures of the fitted surfaces decrease or become more equal, the methods naturally converge to fits of simpler primitives (e.g., a sphere fitting becoming a plane fit). This is crucial for hierarchical segmentation and model building.
  • Non-linear Fitting for Accuracy: While linear methods exist, the paper advocates for non-linear fitting that accounts for the true geometric distance to achieve higher accuracy, especially when initial estimates are available from a segmentation stage.

Key Results

The paper reports that their fitting methods, when applied to simulated 3D point data accurate to five significant digits, achieved fits accurate to at least four significant digits. Segmentations obtained were consistent with the underlying geometric primitives. Examples of successful segmentation and fitting are shown for a cylinder and sphere (Fig. 2), and a cone, cylinder, and two spheres (Figs. 6 & 7). The methods also demonstrated good performance on less accurate real scanner data (Figs. 8 & 9).

Limitations and Future Work

  • Torus Singularities: While the methods are generally robust, the paper notes that the torus fitting can have singularities, though it suggests these can be overcome by choosing the origin appropriately.
  • Initial Estimates: The paper outlines a method for obtaining initial estimates for the fitting parameters, which is crucial for the non-linear optimization. However, the robustness and efficiency of this initial estimation process are not the primary focus.
  • Full Presentation of Results: The authors mention that space limitations prevent a full presentation of all results, implying that more extensive quantitative evaluations might exist.

Future work is implicitly suggested by the application context: using these fitting methods within a complete reverse engineering system for boundary representation solid models. The authors believe the methods are of general interest to the computer vision and CAD communities.

Summary updated

BibTeX
@inproceedings{lukacs1998faithful,
  author = {Gábor Lukács and Ralph R. Martin and A. David Marshall},
  title = {{Faithful Least-Squares Fitting of Spheres, Cylinders, Cones and Tori for Reliable Segmentation}},
  booktitle = {European Conference on Computer Vision},
  year = {1998},
  doi = {10.1007/bfb0055697},
}

Loading related content...

Figure