Stable recovery of planar regions with algebraic boundaries in Bernstein form

Costanza Conti, Mariantonia Cotronei, Demetrio Labate, Wilfredo Molina

Introduction

Reconstructing the geometry of objects from discrete, noisy samples is a fundamental challenge in computer vision and image processing. Whether analyzing medical scans or industrial parts, the goal is often to recover a smooth mathematical representation of a shape's boundary. This paper introduces a numerically stable method for reconstructing binary images of shapes with algebraic boundaries. By shifting the mathematical representation from the standard power basis to the Bernstein basis, the authors transform a traditionally unstable "moment-based" reconstruction problem into a robust linear system that is significantly faster than previous iterative methods.

The Problem of Instability

Algebraic domains are regions where the boundary is defined by the zero-set of a polynomial. A common approach to recovering these boundaries involves using "image moments"—statistical descriptors that characterize a shape's distribution. However, high-order moments in the standard power basis ($x^i y^j$) are notoriously sensitive to noise. Even minimal grain in an image can cause calculated moments to fluctuate wildly, leading to boundary reconstructions that are distorted or completely unrecognizable.

Previous attempts to mitigate this instability relied on complex, iterative "regularization" techniques. While effective at smoothing the results, these methods are computationally expensive and require manual tuning of parameters for different noise levels, making them difficult to deploy in automated pipelines.

The Bernstein-Moment Reconstruction (BMR) Approach

The core innovation of this research is Bernstein-Moment Reconstruction (BMR). The authors demonstrate that the instability of moment-based reconstruction is not an inherent property of the data, but rather a byproduct of the chosen mathematical basis. By representing the boundary polynomial using bivariate Bernstein polynomials defined over a triangular domain, they achieve natural noise dampening.

Methodology

The BMR process involves three key components:

  1. Stokes’ Theorem Integration: A generalized version of Stokes’ Theorem is used to link the moments of the image's interior directly to the coefficients of the polynomial defining its boundary.
  2. Refinable Sampling Kernels: To process discrete image samples, the method employs kernels (such as B-splines or Daubechies scaling functions) that can perfectly reproduce polynomials. This allows for the direct calculation of "Bernstein moments."
  3. Linear System Solution: Because the Bernstein basis provides inherent stability, the problem can be solved as a direct system of linear equations ($G \mathbf{b} = 0$) using a simple Moore-Penrose pseudo-inverse. This eliminates the need for the "guess and check" loops found in iterative solvers.
The embedding of a rectangular image region Ω into a triangular domain for Bernstein basis representation.

The use of a triangular domain, as shown above, is central to defining the bivariate Bernstein polynomials. The rectangular image region Ω is embedded within this triangle to facilitate the change of basis.

Experimental Validation

The researchers evaluated BMR against the conventional power-basis method (CMR) and the state-of-the-art Regularized Moment Reconstruction (RMR) using both synthetic and hand-drawn data.

Performance and Speed

BMR demonstrated a massive leap in efficiency. In tests involving 100 images, BMR completed the reconstruction in approximately 22.6 seconds, compared to 359.6 seconds for RMR—a 16x speedup.

Accuracy and Robustness

Using the Dice Similarity Coefficient (where 1.0 represents a perfect match), BMR consistently outperformed CMR. While CMR failed at moderate noise levels (30-50 dB), BMR maintained high fidelity. Crucially, BMR matched or exceeded the accuracy of RMR without requiring the manual tuning of regularization parameters. The method also proved resilient to heavy down-sampling, successfully recovering complex shapes from grids as small as $9 \times 9$ pixels.

Conclusion and Future Directions

The shift to the Bernstein basis offers a parameter-free, robust solution to a long-standing problem in geometric reconstruction. By choosing a basis with "limited growth" properties, the authors have made high-order moment reconstruction practical for real-world, noisy data.

Future work may focus on automating the selection of the polynomial degree ($n$), which currently requires a search strategy. Additionally, exploring other stable representations, such as the Chebyshev basis, could further refine the approach for specific geometric applications.

Summary updated

Abstract

We present a new method for the stable reconstruction of a class of binary images from a small number of measurements. The images we consider are characteristic functions of algebraic domains, that is, domains defined as zero loci of bivariate polynomials, and we assume to know only a finite set of uniform samples for each image. The solution to such a problem can be set up in terms of linear equations associated to a set of image moments. However, the sensitivity of the moments to noise makes the numerical solution highly unstable. To derive a robust image recovery algorithm, we represent algebraic polynomials and the corresponding image moments in terms of bivariate Bernstein polynomials and apply polynomial-generating, refinable sampling kernels. This approach is robust to noise, computationally fast and simple to implement. We illustrate the performance of our reconstruction algorithm from noisy samples through extensive numerical experiments. Our code is released open source and freely available.
BibTeX
@article{conti2021stable,
  author = {Costanza Conti and Mariantonia Cotronei and Demetrio Labate and Wilfredo Molina},
  title = {{Stable recovery of planar regions with algebraic boundaries in Bernstein form}},
  journal = {Adv. Comput. Math},
  year = {2021},
  doi = {10.1007/s10444-021-09843-0},
}
Figure