Técnicas de interpolación weno y su aplicación al procesamiento de imágenes

Abstract

Un problema común en la teoría de aproximación es la reconstrucción de una función a partir de un conjunto de valores discretos de datos que dan información sobre la función misma. Esta información por lo general viene dada como valores puntuales o medias en celda de la función sobre un conjunto finito de puntos o celdas, respectivamente. La función es aproximada por un interpolante, es decir, por otra función cuyos valores puntuales o medias en celda coinciden con los de la función original. Este interpolante puede ser construido por interpolación lineal. En este caso la exactitud de la aproximación cerca de una singularidad está limitada y depende del orden de la singularidad, de modo que si construimos el polinomio interpolador basándonos en un stencil que cruza la singularidad obtendremos una aproximación insatisfactoria. Esto significa que aumentar el grado del polinomio producirá regiones más grandes de mala aproximación alrededor de las singularidades. Para aumentar la exactitud la solución es escoger los puntos de forma que el stencil quede dentro de la parte suave de la función, siempre que esto sea posible. Esta es la idea que hay detrás de la técnica de interpolación ENO (Esencialmente No Oscilatoria), introducida por Harten et al., que es un procedimiento no lineal con el que la región de poca exactitud queda reducida al intervalo que contiene la singularidad, siempre y cuando las singularidades estén suficientemente bien separadas. Liu et al. introdujeron una mejora sobre la técnica ENO, llamada weighted ENO (ENO ponderado), que consiste en reconstruir un polinomio que interpola los valores puntuales de la solución de una ley de conservación hiperbólica a partir de las medias en celda de la solución débil. En la interpolación WENO se asignan a cada celda todos los stencils que la contienen, y el polinomio interpolador se calcula como combinación lineal convexa de todos los polinomios correspondientes a estos stencils. La clave es asignar los pesos más convenientes a la combinación. Estos pesos deben ser elegidos de forma que en la combinación los polinomios interpoladores en los stencils que cruzan una singularidad tengan una contribución casi nula. En las regiones suaves se utiliza la información proporcionada por todas las celdas contenidas en los stencils del proceso de selección ENO, y el resultado es un mayor orden de exactitud. En este trabajo se ha integrado la técnica WENO en el entorno de multirresolución de Harten, y se ha adaptado a los contextos de medias en celda y valores puntuales. En ambos casos se proponen nuevas medidas para la suavidad de una función. Además, en el contexto de valores puntuales se propone una modificación en la definición de los pesos WENO, que mejora el orden de la aproximación en presencia de singularidades. En la definición de los pesos WENO se introduce un ε positivo para evitar que el denominador se anule y se suele tomar ε constante. En esta tesis se propone tomar ε=h2, lo que permite demostrar que si la función es suave en al menos r+1 puntos y tiene una discontinuidad dentro del stencil de 2r puntos, entonces obtenemos al menos una aproximación de orden r+1, es decir, como mínimo obtenemos el mismo orden que el interpolante ENO, y en las zonas suaves de la función el orden de la aproximación es óptimo incluso en presencia de puntos críticos en los que se anulen las dos primeras derivadas. Las técnicas de interpolación WENO se comparan, mediante diferentes experimentos numéricos, con las técnicas de interpolación lineal, ENO y ENO-SR, para poder concluir qué método proporciona la mayor exactitud en cada caso.

A common problem in approximation theory is to reconstruct a function from a discrete set of data which gives information on the function itself. This information will usually come in the form of point-values or cell-averages of the function, which is then approximated by an interpolant, that is, another function whose values at a given set of points or cell-averages are equal to those of the original one. This interpolant can be built through linear interpolation, but in this case the accuracy of the approximation in the presence of a singularity is limited by the order of the singularity, so that any stencil crossing it will result in a poor approximation. In order to improve the accuracy of the approximation we need to choose stencils that avoid crossing singularities, whenever this is possible. That is the idea behind the ENO (essentially non-oscillatory) technique, introduced by Harten et al. WENO (weighted ENO) was introduced by Liu et al. as an improvement upon ENO. The idea is to assign to each subinterval all the stencils containing it, and construct the interpolating polynomial as a linear convex combination of the corresponding polynomials. In this way we use all the information provided by the nodes contained in the candidate stencils in the ENO selection process, and this should give a higher order of accuracy in smooth regions of the function. The key point is the assignment of weights to the convex combination. In this work we have incorporated WENO to Harten's multiresolution framework, and adapted it to the context of cell-averages and point-values. Moreover, for point-values we propose a modification in the definition of the weights, producing a higher order of accuracy in the presence of singularities. We also compare the WENO technique with other interpolation techniques through numerical experimentation.