Weighted least squares subdivision schemes for noisy data on triangular meshes

Résumé technique : Schémas de subdivision par moindres carrés pondérés pour données bruitées sur des maillages triangulaires

Énoncé du problème
L'article traite du défi que représente l'approximation de fonctions scalaires bivariées à partir d'échantillons bruités définis sur des maillages triangulaires. Bien que les schémas de subdivision soient bien établis pour générer des surfaces lisses à partir de données initiales, les schémas standards peinent souvent face à des données bruitées, pouvant amplifier les erreurs ou échouer à converger vers une limite lisse. Les méthodes existantes pour les données bruitées, telles que la régression linéaire locale (LLR), les moindres carrés mobiles (MLS) et les fonctions de base radiale (RBF), sont typiquement conçues pour des données éparses ou des grilles de produits tensoriels et ne possèdent pas intrinsèquement les propriétés de multirésolution ou l'adaptabilité structurelle des schémas de subdivision pour des maillages triangulaires généraux, particulièrement ceux contenant des sommets extraordinaires ou des topologies irrégulières.

Méthodologie
Les auteurs proposent une nouvelle famille de schémas de subdivision linéaires et non uniformes, spécifiquement conçus pour les maillages triangulaires. La méthodologie centrale repose sur la définition de règles de raffinement basées sur l'approximation par moindres carrés pondérés (WLS) de polynômes de premier degré.

1. Règles de raffinement : À chaque étape de subdivision $k$, les nouvelles valeurs de données $z^{k+1}_\ell$ associées aux nouveaux sommets (qu'il s'agisse de sommets existants ou de milieux d'arêtes) sont calculées en ajustant un polynôme linéaire local à un sous-ensemble de points de données voisins. Ce sous-ensemble, nommé $L$-ball, est défini par un seuil de distance euclidienne $2^{-k}L$ autour du sommet cible.
2. Formulation des moindres carrés pondérés : Le polynôme $p(x,y) = a_0 + a_1x + a_2y$ est déterminé en minimisant la somme pondérée des carrés des erreurs : $\min \sum w_i (p(v_i) - z_i)^2$. La valeur du nouveau sommet est l'évaluation de ce polynôme au niveau de l'emplacement du sommet.
3. Coefficients et stencils : La règle de raffinement est exprimée comme une combinaison linéaire de valeurs voisines $z^{k+1}_\ell = \sum \alpha^{k+1,\ell}_j z^k_j$. Les coefficients $\alpha$ sont dérivés explicitement en utilisant la règle de Cramer appliquée aux équations normales du problème WLS. Ces coefficients dépendent de la géométrie du stencil local et de la fonction de poids $W$ choisie, qui décroît généralement avec la distance (fonctions constantes, en chapeau ou gaussiennes).
4. Gestion de l'irrégularité : Le schéma est conçu pour fonctionner sur n'importe quel grille triangulaire, y compris celles possédant des sommets extraordinaires (valence $\neq 6$) et des frontières finies. Les règles sont dépendantes de la géométrie, ce qui rend le schéma non uniforme et dépendant du niveau dans les cas généraux, bien qu'il devienne uniforme et stationnaire sur des grilles régulières et uniformes.

Contributions clés et résultats théoriques
L'article fournit une analyse rigoureuse des schémas proposés, établissant plusieurs propriétés théoriques :

• Reproduction de polynômes : Les schémas reproduisent exactement les polynômes linéaires ($\Pi_1$). Si les données initiales reposent sur un plan, la surface limite est ce même plan.
• Ordre d'approximation : Les schémas atteignent une approximation de second ordre ($O(h^2)$) pour les fonctions $C^2$ ayant des dérivées bornées, à condition que le schéma converge.
• Capacités de débruitage : Les auteurs prouvent que si les coefficients de raffinement sont non négatifs, la variance du bruit diminue à chaque itération. Plus précisément, la variance du bruit à l'étape $k+1$ est bornée par un facteur $\theta < 1$ fois la variance initiale, à condition que la taille du stencil soit suffisante.
• Convergence : Pour les grilles uniformes (où les sommets forment un réseau), les auteurs prouvent que les coefficients sont positifs et somment à un. Cela garantit la convergence du schéma de subdivision vers une fonction limite continue.
• 0-homogénéité : Le schéma est démontré comme étant 0-homogène par rapport à la mise à l'échelle simultanée de la grille et du paramètre $L$, assurant l'invariance d'échelle.

Résultats numériques
L'article présente des expériences numériques approfondies pour valider les affirmations théoriques et comparer les performances :

• Continuité sur les grilles irrégulières : Des tests numériques sur des triangulation irrégulières et non uniformes avec des sommets extraordinaires démontrent que les surfaces limites paraissent lisses, suggérant une continuité même là où la preuve théorique rigoureuse est complexe.
• Comparaison avec l'état de l'art : Le schéma proposé est comparé à quatre méthodes établies pour les données éparses : les moindres carrés mobiles (MLS), la méthode de Shepard, les fonctions de base radiale par moindres carrés (RBF) et les B-splines de produit tensoriel par moindres carrés (TPBS).
  • Les résultats indiquent que le nouveau schéma de subdivision atteint des métriques d'erreur ($L_2$ et $L_\infty$) comparables à ces méthodes avancées de régression linéaire locale.
  • La performance est sensible au choix du paramètre $L$ et de la fonction de poids $W$.
• Application aux données géométriques : Les auteurs démontrent une extension de la méthode aux données géométriques 3D (surfaces bruitées dans $\mathbb{R}^3$). En utilisant des paramétrages locaux (projection des points 3D sur un plan tangent local), le schéma parvient à raffiner des données sphériques bruitées, réduisant le bruit tout en préservant la géométrie sous-jacente.

Signification et revendications
L'article affirme que ce travail introduit l'une des rares techniques de subdivision spécifiquement adaptées au raffinement de données bruitées sur des maillages triangulaires. Sa signification réside dans le fait qu'il comble le fossé entre les méthodes de lissage statistique (comme la régression WLS) et les schémas de subdivision géométriques.

Les principaux avantages mis en avant par les auteurs sont :

• Contexte de multirésolution : Contrairement aux méthodes de régression standard, la nature de la subdivision permet une représentation et une décomposition multirésolution, ce qui est crucial pour les applications nécessitant un traitement hiérarchique des données.
• Support local et efficacité : La méthode maintient un support local, ce qui la rend efficace sur le plan computationnel pour les grands ensembles de données.
• Flexibilité topologique : Elle gère les topologies irrégulières et les sommets extraordinaires sans nécessiter de procédures de bord particulières ou de paramétrage global.
• Robustesse au bruit : Le schéma atténue efficacement le bruit et les valeurs aberrantes sans connaissance préalable de la distribution du bruit, performant de manière similaire aux techniques de régression avancées tout en conservant les avantages structurels de la subdivision.

Les auteurs concluent que, bien que l'analyse théorique pour les grilles non régulières générales (spécifiquement la convergence et la lissité aux points extraordinaires) reste un défi pour les travaux futurs, les preuves numériques soutiennent fortement l'utilité pratique et la validité théorique du schéma sur les grilles uniformes.