Source-linked AI summary
StretchDenoise: Parametric Curve Reconstruction with Guarantees by Separating Connectivity from Residual Uncertainty of Samples
Stefan Ohrhallinger, Michael Wimmer
TL;DR
Closed-curve reconstruction from noisy samples must preserve features that Gaussian smoothing can oversmooth while accounting for acquisition noise extent. A two-pass pipeline uses FITCONNECT connectivity to order samples and then optimizes a parameter-free curve with angle regularization, balanced signed distances, and bounded vertex motion. The method typically reduces input noise by a factor of 2-3.
Problem
Closed-curve reconstruction from noisy samples must preserve features that Gaussian smoothing can oversmooth while accounting for acquisition noise extent.
Method
A two-pass pipeline uses FITCONNECT connectivity to order samples and then optimizes a parameter-free curve with angle regularization, balanced signed distances, and bounded vertex motion.
Results
The method typically reduces input noise by a factor of 2-3.
Takeaways & Limitations
The approach preserves features emerging over the local noise extent while supporting fast practical denoising and applications such as sensed-data silhouettes.
Takeaways & Limitations
The least-squares angle objective rounds sharp corners, especially at incident corners of straight segments, and sharp-corner detection is left for future work.
Abstract
from arXiv · showhide
We reconstruct a closed denoised curve from an unstructured and highly noisy 2D point cloud. Our proposed method uses a two- pass approach: Previously recovered manifold connectivity is used for ordering noisy samples along this manifold and express these as residuals in order to enable parametric denoising. This separates recovering low-frequency features from denoising high frequencies, which avoids over-smoothing. The noise probability density functions (PDFs) at samples are either taken from sensor noise models or from estimates of the connectivity recovered in the first pass. The output curve balances the signed distances (inside/outside) to the samples. Additionally, the angles between edges of the polygon representing the connectivity become minimized in the least-square sense. The movement of the polygon's vertices is restricted to their noise extent, i.e., a cut-off distance corresponding to a maximum variance of the PDFs. We approximate the resulting optimization model, which consists of higher-order functions, by a linear model with good correspondence. Our algorithm is parameter-free and operates fast on the local neighborhoods determined by the connectivity. We augment a least-squares solver constrained by a linear system to also handle bounds. This enables us to guarantee stochastic error bounds for sampled curves corrupted by noise, e.g., silhouettes from sensed data, and we improve on the reconstruction error from ground truth. Open source to reproduce figures and tables in this paper is available at: https://github.com/stefango74/stretchdenoise
1. Introduction
StretchDenoise addresses noisy closed-curve reconstruction by separating connectivity recovery from residual denoising, preserving features while avoiding oversmoothing. It uses noise-aware constraints and a parameter-free two-pass formulation with stochastic guarantees.
- Motivation: Closed-curve reconstruction supports applications including silhouette extraction from noisy sensed depth images for subsequent color-data segmentation.The application depends on obtaining clear contours after reconstruction and denoising.
- Motivation: Existing methods can oversmooth features and ignore known noise extent, limiting stochastic guarantees for noisy curve reconstruction.The problem arises from a mutual dependence between estimating connectivity and estimating high-frequency noise.
- Two-pass approach: The first pass recovers manifold connectivity and orders samples along it, expressing their Hausdorff distances as residuals from the low-frequency curve.FITCONNECT supplies a polygon, normals, and local sample neighborhoods for this ordering.
- Two-pass approach: The second pass moves polygon vertices within sensor- or connectivity-derived error bounds while straightening the curve and balancing inside/outside sample distances.Balancing signed distances helps avoid area shrinking.
- Contributions: The method contributes a parameter-free denoising approach with stochastic guarantees and a bounded constrained least-squares solver.The solver handles both linear constraints and bounds.
2. Related Work
Prior work reconstructs or denoises curves using graphs, smoothing, geometric simplification, or probabilistic models, but important limitations remain. StretchDenoise builds on connectivity recovery while explicitly incorporating noise extents into denoising guarantees.
- Curve reconstruction from noisy samples: Existing reconstruction methods struggle with open-curve restrictions, non-uniform sampling, noisy normals, gaps, intersections, or dense simple cases.The cited methods use neighborhood graphs, screened Poisson reconstruction, convex-hull transformations, Delaunay simplification, or moving balls.
- Curve reconstruction from noisy samples: FITCONNECT recovers manifold connectivity under arbitrarily high noise by fitting increasingly large circular neighborhoods and eliminating samples redundant for connectivity.It determines local inside/outside information and increases neighborhood size until fits become consistent.
- Guarantees for curve reconstruction: Prior guarantees establish reconstructability under local-feature-size or probabilistic noise models, but one cited algorithm has O(N^3) complexity and assumes uniform sampling and normal perturbations.These assumptions limit direct practicality for the broader noisy-sample setting.
- Curve denoising: Curve-denoising methods based on region thinning or Gaussian kernels can mishandle varying sampling density, while known noise extents from sensed data are generally not considered.StretchDenoise uses specified noise extents to provide a stochastic reconstruction-distance guarantee.
- Constrained optimization techniques: The paper formulates denoising as constrained least squares with both linear equalities and bounds, motivating a specialized solver variant.Standard equality-constrained methods and linear programming do not directly solve the resulting model.
3. Problem Definition
The method starts from a FITCONNECT polygon with ordered local neighborhoods, normals, and maximum noise extents. It then optimizes a curve that straightens locally, balances signed sample distances, and remains within probabilistic noise bounds.
- Input and connectivity: FITCONNECT supplies polygon vertices, ordered sample neighborhoods, normals, and maximum noise extents for a noisy closed curve.Redundant samples in noisy clusters are eliminated during connectivity recovery.
- Noise model and guarantee: A cut-off radius r contains a sample with probability Π determined by a user-defined maximum allowed σ, providing the stochastic basis for the reconstruction guarantee.The signed-distance formulation and vertex bounds together define the constrained denoising problem.
- Denoising goals: The denoising objective minimizes polygon angles in least squares to eliminate high-frequency noise where no feature exceeds the noise extent.This regularizes the curve toward locally straighter segments.
- Denoising goals: Setting the mean signed distance to zero balances samples inside and outside the polygon and prevents area shrinking.Signed distance is positive on or outside the polygon and negative inside it.
- Denoising goals: Bounding vertices within discs of radius r_i keeps the reconstructed curve within the maximum permitted distance from samples and preserves recovered features.The radii may come from FITCONNECT or an external sensor noise model.
- Assumption: The approach assumes the input connectivity is free of outlier points because FITCONNECT does not connect points too far from the curve.Outliers introduced by sensing errors are therefore outside the modeled input.
4. Denoising Algorithm
The denoising model restricts polygon vertices to normal-direction motion, linearizing angle and sample-distance terms while retaining noise bounds. It solves this bounded model locally to avoid global computational cost and directional shifts.
- Adapted Model: Restricting each vertex to move along its normal converts the higher-order optimization into a linear model with fast solving and little expected deviation from the exact minimum.Free movement would make the objective and constraints higher-order and could cause local-minimum issues; normal-direction motion is justified because the polygon is mostly tangential to the normals.
- Adapted Model: Angle penalties approximate each vertex angle by weighted distance to the opposite baseline, while a vertex displacement also affects adjacent angles through normal dot products.The resulting angle system is expressed in the displacement scalars x and has sparse local dependencies.
- Adapted Model: Sample-to-edge balance linearizes distance changes from vertex motion, using clamped sample positions along incident edges to weight each displacement.The approximation uses vertex-normal distance as an upper bound on Hausdorff distance, preventing displacement values from diverging.
- Adapted Model: The adapted optimization combines least-squares minimization, a linear equality system, and lower and upper displacement bounds.Bounds represent noise cut-off radii at vertices; anisotropic PDFs could also be accommodated.
- Our Augmented Solver: The augmented solver handles bound violations by clamping offending variables, eliminating their matrix columns, updating constraints, and iterating until all variables satisfy bounds.It augments constrained least squares because standard approaches do not directly solve the paper’s multi-row bound-constrained problem.
- Solving Locally: Local subsets are solved separately because global optimization is super-quadratic and can create undesirable directional shifts; subsets grow while a line intersects all vertex noise discs.This preserves enough scale to remove noise while remaining local, and straight segments can be denoised without losing features.
5. Results
Across synthetic and comparative evaluations, StretchDenoise reduces reconstruction error, preserves features relative to noise extent, and efficiently straightens curves while balancing sample distances.
- Improvements over prior work: Adding more noisy samples improves reconstruction quality, with the reconstruction approaching the original curve in the limit.
- Approximation quality and run time: StretchDenoise produces smaller total angle sums and generally reduced signed distances without large absolute imbalances, while denoising remains mostly linear.Connectivity recovery dominates runtime and is linear in principle but quadratic within noise clusters.
- Comparison with noisy reconstruction algorithms: Compared with Robust HPR, the method yields better connectivity and substantially better denoising on noisy point sets.
- Guarantees: Features recovered by FITCONNECT are preserved when they protrude beyond the local noise extent, whereas submerged features merge into a single curved segment.
- Guarantees: The reconstructed curve stays within specified sample noise extents, providing a stochastic ground-truth proximity guarantee when cut-off radii come from sensor PDFs.
Silhouettes with estimated noise
For sensed 3D-object silhouettes, the method uses estimated or sensor-derived noise extents, but silhouette extraction and corner geometry constrain the reconstruction.
- Silhouettes with estimated noise: For real silhouettes without sensor error information, FITCONNECT estimates the noise extent, supplemented by a minimum uniform extent of 1mm.The minimum is used because sparse or straight regions may otherwise be interpolated rather than recognized as noisy.
- Silhouettes with estimated noise: When extents are computed from range-image properties, extracted silhouettes can deviate from object boundaries because of the silhouette extraction algorithm.
- Silhouettes with estimated noise: Curves containing straight segments are rounded at incident corners because the objective minimizes all polygon angles in the least-squares sense.The same objective makes intermediate straight edges curvy while reducing sharp corner angles.
6. Conclusion
The two-pass method reconstructs highly noisy curves with stochastic distance guarantees while retaining features beyond local noise extent. It runs efficiently enough for practical use and supports extensions to 3D surfaces and open curves.
- The method reconstructs curves within a stochastically guaranteed distance to the original while retaining features emerging over the local noise extent.The error bound is expressed in terms of input noise supplied by sensor properties or estimated through FITCONNECT.
- Adding more noisy samples improves reconstruction quality, with the reconstruction approaching the original curve in the limit.
- Compared with Robust HPR, the method produces better connectivity and substantially stronger denoising on point sets that Robust HPR fails to close.
- The denoising algorithm runs fast enough for practical use, although it is not optimized.The authors provide open-source code for verification and reproduction.
- The framework is intended to extend to 3D surface reconstruction and could incorporate sharp-corner detection and open-curve handling.These are identified as extensions beyond the demonstrated closed-curve setting.