Weighted least squares subdivision schemes for noisy data on triangular meshes

Technical Summary: Weighted Least Squares Subdivision Schemes for Noisy Data on Triangular Meshes

Problem Statement
The paper addresses the challenge of approximating bivariate scalar functions from noisy samples defined on triangular meshes. While subdivision schemes are well-established for generating smooth surfaces from initial data, standard schemes often struggle with noisy input, potentially amplifying errors or failing to converge to a smooth limit. Existing methods for noisy data, such as local linear regression (LLR), Moving Least Squares (MLS), and Radial Basis Functions (RBF), are typically designed for scattered data or tensor-product grids and do not inherently possess the multiresolution properties or the structural adaptability of subdivision schemes for general triangular meshes, particularly those containing extraordinary vertices or irregular topologies.

Methodology
The authors propose a new family of linear, non-uniform subdivision schemes specifically designed for triangular meshes. The core methodology involves defining refinement rules based on weighted least squares (WLS) approximation of first-degree polynomials.

1. Refinement Rules: At each subdivision step $k$, new data values $z^{k+1}_\ell$ associated with new vertices (either existing vertices or midpoints of edges) are computed by fitting a local linear polynomial to a subset of neighboring data points. This subset, termed an $L$-ball, is defined by a Euclidean distance threshold $2^{-k}L$ around the target vertex.
2. Weighted Least Squares Formulation: The polynomial $p(x,y) = a_0 + a_1x + a_2y$ is determined by minimizing the weighted sum of squared errors: $\min \sum w_i (p(v_i) - z_i)^2$. The value of the new vertex is the evaluation of this polynomial at the vertex location.
3. Coefficients and Stencils: The refinement rule is expressed as a linear combination of neighboring values $z^{k+1}_\ell = \sum \alpha^{k+1,\ell}_j z^k_j$. The coefficients $\alpha$ are derived explicitly using Cramer's rule applied to the normal equations of the WLS problem. These coefficients depend on the geometry of the local stencil and the chosen weight function $W$, which typically decays with distance (e.g., constant, hat, or Gaussian functions).
4. Handling Irregularity: The scheme is designed to work on any triangular grid, including those with extraordinary vertices (valence $\neq 6$) and finite boundaries. The rules are geometry-dependent, making the scheme non-uniform and level-dependent in general cases, though it becomes uniform and stationary on regular, uniform grids.

Key Contributions and Theoretical Results
The paper provides a rigorous analysis of the proposed schemes, establishing several theoretical properties:

• Polynomial Reproduction: The schemes exactly reproduce linear polynomials ($\Pi_1$). If the initial data lies on a plane, the limit surface is that same plane.
• Approximation Order: The schemes achieve a second-order approximation ($O(h^2)$) for $C^2$ functions with bounded derivatives, provided the scheme converges.
• Denoising Capabilities: The authors prove that if the refinement coefficients are non-negative, the variance of the noise decreases with each iteration. Specifically, the variance of the noise at step $k+1$ is bounded by a factor $\theta < 1$ times the initial variance, provided the stencil size is sufficient.
• Convergence: For uniform grids (where vertices form a lattice), the authors prove that the coefficients are positive and sum to one. This guarantees the convergence of the subdivision scheme to a continuous limit function.
• 0-Homogeneity: The scheme is shown to be 0-homogeneous with respect to the simultaneous scaling of the grid and the parameter $L$, ensuring scale invariance.

Numerical Results
The paper presents extensive numerical experiments to validate the theoretical claims and compare performance:

• Continuity on Irregular Grids: Numerical tests on irregular, non-uniform triangulations with extraordinary vertices demonstrate that the limit surfaces appear smooth, suggesting continuity even where rigorous theoretical proof is complex.
• Comparison with State-of-the-Art: The proposed scheme is compared against four established methods for scattered data: Moving Least Squares (MLS), Shepard method, Least Squares Radial Basis Functions (RBF), and Least Squares Tensor Product B-Splines (TPBS).
  • The results indicate that the new subdivision scheme achieves error metrics ($L_2$ and $L_\infty$) comparable to these advanced local linear regression methods.
  • The performance is sensitive to the choice of the parameter $L$ and the weight function $W$.
• Geometric Data Application: The authors demonstrate an extension of the method to 3D geometric data (noisy surfaces in $\mathbb{R}^3$). By utilizing local parametrizations (projecting 3D points onto a local tangent plane), the scheme successfully refines noisy spherical data, reducing noise while preserving the underlying geometry.

Significance and Claims
The paper claims that this work introduces one of the few subdivision techniques specifically tailored for refining noisy data on triangular meshes. Its significance lies in bridging the gap between statistical smoothing methods (like WLS regression) and geometric subdivision schemes.

Key advantages highlighted by the authors include:

• Multiresolution Context: Unlike standard regression methods, the subdivision nature allows for multiresolution representation and decomposition, which is crucial for applications requiring hierarchical data processing.
• Local Support and Efficiency: The method maintains local support, making it computationally efficient for large datasets.
• Topological Flexibility: It handles irregular topologies and extraordinary vertices without requiring special boundary procedures or global parametrization.
• Noise Robustness: The scheme effectively mitigates noise and outliers without prior knowledge of the noise distribution, performing similarly to advanced regression techniques while retaining the structural benefits of subdivision.

The authors conclude that while the theoretical analysis for general non-regular grids (specifically convergence and smoothness at extraordinary points) remains a challenge for future work, the numerical evidence strongly supports the scheme's practical utility and theoretical soundness on uniform grids.