Weighted least squares subdivision schemes for noisy data on triangular meshes

Resumen Técnico: Esquemas de Subdivisión de Mínimos Cuadrados Ponderados para Datos con Ruido en Mallas Triangulares

Planteamiento del Problema
El artículo aborda el desafío de aproximar funciones escalares bivariables a partir de muestras con ruido definidas sobre mallas triangulares. Aunque los esquemas de subdivisión están bien establecidos para generar superficies suaves a partir de datos iniciales, los esquemas estándar suelen tener dificultades con la entrada con ruido, pudiendo amplificar errores o no converger a un límite suave. Los métodos existentes para datos con ruido, como la regresión lineal local (LLR), los Mínimos Cuadrados Móviles (MLS) y las Funciones de Base Radial (RBF), están típicamente diseñados para datos dispersos o rejillas de producto tensorial y no poseen inherentemente las propiedades de multirresolución o la adaptabilidad estructural de los esquemas de subdivisión para mallas triangulares generales, particularmente aquellas que contienen vértices extraordinarios o topologías irregulares.

Metodología
Los autores proponen una nueva familia de esquemas de subdivisión lineales y no uniformes diseñados específicamente para mallas triangulares. La metodología central implica definir reglas de refinamiento basadas en la aproximación de mínimos cuadrados ponderados (WLS) de polinomios de primer grado.

1. Reglas de Refinamiento: En cada paso de subdivisión $k$, los nuevos valores de los datos $z^{k+1}_\ell$ asociados con nuevos vértices (ya sean vértices existentes o puntos medios de aristas) se calculan ajustando un polinomio lineal local a un subconjunto de puntos de datos vecinos. Este subconjunto, denominado $L$-bola, se define por un umbral de distancia euclidiana $2^{-k}L$ alrededor del vértice objetivo.
2. Formulación de Mínimos Cuadrados Ponderados: El polinomio $p(x,y) = a_0 + a_1x + a_2y$ se determina minimizando la suma ponderada de los errores al cuadrado: $\min \sum w_i (p(v_i) - z_i)^2$. El valor del nuevo vértice es la evaluación de este polinomio en la ubicación del vértice.
3. Coeficientes y Estenciles: La regla de refinamiento se expresa como una combinación lineal de valores vecinos $z^{k+1}_\ell = \sum \alpha^{k+1,\ell}_j z^k_j$. Los coeficientes $\alpha$ se derivan explícitamente utilizando la regla de Cramer aplicada a las ecuaciones normales del problema WLS. Estos coeficientes dependen de la geometría del estencil local y de la función de peso $W$ elegida, que típicamente decae con la distancia (por ejemplo, funciones constantes, de tipo "hat" o gaussianas).
4. Manejo de la Irregularidad: El esquema está diseñado para trabajar en cualquier rejilla triangular, incluyendo aquellas con vértices extraordinarios (valencia $\neq 6$) y fronteras finitas. Las reglas dependen de la geometría, lo que hace que el esquema sea no uniforme y dependiente del nivel en general, aunque se vuelve uniforme y estacionario en rejillas regulares y uniformes.

Contribuciones Clave y Resultados Teóricos
El artículo proporciona un análisis riguroso de los esquemas propuestos, estableciendo varias propiedades teóricas:

• Reproducción de Polinomios: Los esquemas reproducen exactamente polinomios lineales ($\Pi_1$). Si los datos iniciales se encuentran sobre un plano, la superficie límite es ese mismo plano.
• Orden de Aproximación: Los esquemas logran una aproximación de segundo orden ($O(h^2)$) para funciones $C^2$ con derivadas acotadas, siempre que el esquema converja.
• Capacidades de Reducción de Ruido (Denoising): Los autores demuestran que si los coeficientes de refinamiento son no negativos, la varianza del ruido disminuye con cada iteración. Específicamente, la varianza del ruido en el paso $k+1$ está acotada por un factor $\theta < 1$ multiplicado por la varianza inicial, siempre que el tamaño del estencil sea suficiente.
• Convergencia: Para rejillas uniformes (donde los vértices forman una red), los autores demuestran que los coeficientes son positivos y suman uno. Esto garantiza la convergencia del esquema de subdivisión hacia una función límite continua.
• 0-Homogeneidad: Se demuestra que el esquema es 0-homogéneo con respecto al escalado simultáneo de la rejilla y el parámetro $L$, lo que asegura la invarianza de escala.

Resultados Numéricos
El artículo presenta extensos experimentos numéricos para validar las afirmaciones teóricas y comparar el rendimiento:

• Continuidad en Rejillas Irregulares: Las pruebas numéricas en triangulaciones irregulares y no uniformes con vértices extraordinarios demuestran que las superficies límite parecen suaves, lo que sugiere continuidad incluso donde la prueba teórica rigurosa es compleja.
• Comparación con el Estado del Arte: El esquema propuesto se compara con cuatro métodos establecidos para datos dispersos: Mínimos Cuadrados Móviles (MLS), método de Shepard, Mínimos Cuadrados de Funciones de Base Radial (RBF) y Mínimos Cuadrados de B-Splines de Producto Tensorial (TPBS).
  • Los resultados indican que el nuevo esquema de subdivisión logra métricas de error ($L_2$ y $L_\infty$) comparables a estos métodos avanzados de regresión lineal local.
  • El rendimiento es sensible a la elección del parámetro $L$ y la función de peso $W$.
• Aplicación a Datos Geométricos: Los autores demuestran una extensión del método a datos geométricos en 3D (superficies con ruido en $\mathbb{R}^3$). Utilizando parametrizaciones locales (proyectando puntos 3D sobre un plano tangente local), el esquema refina con éxito datos esféricos con ruido, reduciendo el ruido mientras preserva la geometría subyacente.

Significancia y Reivindicaciones
El artículo afirma que este trabajo introduce una de las pocas técnicas de subdivisión diseñadas específicamente para refinar datos con ruido en mallas triangulares. Su significancia radica en cerrar la brecha entre los métodos de suavizado estadístico (como la regresión WLS) y los esquemas de subdivisión geométricos.

Las principales ventajas destacadas por los autores incluyen:

• Contexto de Multirresolución: A diferencia de los métodos de regresión estándar, la naturaleza de la subdivisión permite la representación y descomposición de multirresolución, lo cual es crucial para aplicaciones que requieren procesamiento de datos jerárquicos.
• Soporte Local y Eficiencia: El método mantiene un soporte local, lo que lo hace computacionalmente eficiente para grandes conjuntos de datos.
• Flexibilidad Topológica: Maneja topologías irregulares y vértices extraordinarios sin requerir procedimientos de frontera especiales o parametrización global.
• Robustez al Ruido: El esquema mitiga eficazmente el ruido y los valores atípicos sin conocimiento previo de la distribución del ruido, desempeñándose de manera similar a las técnicas de regresión avanzadas mientras retiene los beneficios estructurales de la subdivisión.

Los autores concluyen que, si bien el análisis teórico para rejillas generales no regulares (específicamente la convergencia y la suavidad en puntos extraordinarios) sigue siendo un desafío para trabajos futuros, la evidencia numérica respalda fuertemente la utilidad práctica y la solidez teórica del esquema en rejillas uniformes.