Interpolación bicúbica

Extensión de la interpolación de splines cúbicos

Comparación de la interpolación bicúbica con algunas interpolaciones unidimensionales y bidimensionales. Los puntos
negros y rojos / amarillos / verdes / azules corresponden al punto interpolado y a las muestras vecinas, respectivamente.
Sus alturas sobre el suelo corresponden a sus valores.

En matemáticas , la interpolación bicúbica es una extensión de la interpolación spline cúbica (un método de aplicación de la interpolación cúbica a un conjunto de datos) para interpolar puntos de datos en una cuadrícula regular bidimensional . La superficie interpolada (es decir, la forma del núcleo, no la imagen) es más suave que las superficies correspondientes obtenidas por interpolación bilineal o interpolación del vecino más cercano . La interpolación bicúbica se puede lograr utilizando polinomios de Lagrange , splines cúbicos o algoritmos de convolución cúbica.

En el procesamiento de imágenes , la interpolación bicúbica suele elegirse en lugar de la interpolación bilineal o del vecino más cercano en el remuestreo de imágenes , cuando la velocidad no es un problema. A diferencia de la interpolación bilineal, que solo tiene en cuenta 4 píxeles (2×2), la interpolación bicúbica considera 16 píxeles (4×4). Las imágenes remuestreadas con interpolación bicúbica pueden tener diferentes artefactos de interpolación , según los valores b y c elegidos.

Cálculo

Interpolación bicúbica en el cuadrado que consta de 25 cuadrados unitarios unidos entre sí. Interpolación bicúbica según la implementación de Matplotlib . El color indica el valor de la función. Los puntos negros son las ubicaciones de los datos prescritos que se interpolan. Observe cómo las muestras de color no son radialmente simétricas. ${\displaystyle [0,4]\times [0,4]}$

Interpolación bilineal en el mismo conjunto de datos que el anterior. Las derivadas de la superficie no son continuas en los límites de los cuadrados.

Interpolación del vecino más cercano en el mismo conjunto de datos que el anterior.

Supóngase que los valores de la función y las derivadas , y son conocidos en los cuatro vértices , , y del cuadrado unitario. La superficie interpolada puede entonces escribirse como ${\displaystyle f}$ ${\displaystyle f_{x}}$ ${\displaystyle f_{y}}$ ${\displaystyle f_{xy}}$ ${\displaystyle (0,0)}$ ${\displaystyle (1,0)}$ ${\displaystyle (0,1)}$ ${\displaystyle (1,1)}$ $${\displaystyle p(x,y)=\sum \limits _{i=0}^{3}\sum _{j=0}^{3}a_{ij}x^{i}y^{j}.}$$

El problema de interpolación consiste en determinar los 16 coeficientes . Al hacer coincidir los valores de la función con los de la función se obtienen cuatro ecuaciones: ${\displaystyle a_{ij}}$ ${\displaystyle p(x,y)}$

1. ${\displaystyle f(0,0)=p(0,0)=a_{00},}$
2. ${\displaystyle f(1,0)=p(1,0)=a_{00}+a_{10}+a_{20}+a_{30},}$
3. ${\displaystyle f(0,1)=p(0,1)=a_{00}+a_{01}+a_{02}+a_{03},}$
4. ${\displaystyle f(1,1)=p(1,1)=\textstyle \sum \limits _{i=0}^{3}\sum \limits _{j=0}^{3}a_{ij}.}$

Asimismo, ocho ecuaciones para las derivadas en las direcciones y : ${\displaystyle x}$ ${\displaystyle y}$

1. ${\displaystyle f_{x}(0,0)=p_{x}(0,0)=a_{10},}$
2. ${\displaystyle f_{x}(1,0)=p_{x}(1,0)=a_{10}+2a_{20}+3a_{30},}$
3. ${\displaystyle f_{x}(0,1)=p_{x}(0,1)=a_{10}+a_{11}+a_{12}+a_{13},}$
4. ${\displaystyle f_{x}(1,1)=p_{x}(1,1)=\textstyle \sum \limits _{i=1}^{3}\sum \limits _{j=0}^{3}a_{ij}i,}$
5. ${\displaystyle f_{y}(0,0)=p_{y}(0,0)=a_{01},}$
6. ${\displaystyle f_{y}(1,0)=p_{y}(1,0)=a_{01}+a_{11}+a_{21}+a_{31},}$
7. ${\displaystyle f_{y}(0,1)=p_{y}(0,1)=a_{01}+2a_{02}+3a_{03},}$
8. ${\displaystyle f_{y}(1,1)=p_{y}(1,1)=\textstyle \sum \limits _{i=0}^{3}\sum \limits _{j=1}^{3}a_{ij}j.}$

Y cuatro ecuaciones para la derivada parcial mixta : ${\displaystyle xy}$

1. ${\displaystyle f_{xy}(0,0)=p_{xy}(0,0)=a_{11},}$
2. ${\displaystyle f_{xy}(1,0)=p_{xy}(1,0)=a_{11}+2a_{21}+3a_{31},}$
3. ${\displaystyle f_{xy}(0,1)=p_{xy}(0,1)=a_{11}+2a_{12}+3a_{13},}$
4. ${\displaystyle f_{xy}(1,1)=p_{xy}(1,1)=\textstyle \sum \limits _{i=1}^{3}\sum \limits _{j=1}^{3}a_{ij}ij.}$

Las expresiones anteriores han utilizado las siguientes identidades: $${\displaystyle p_{x}(x,y)=\textstyle \sum \limits _{i=1}^{3}\sum \limits _{j=0}^{3}a_{ij}ix^{i-1}y^{j},}$$ $${\displaystyle p_{y}(x,y)=\textstyle \sum \limits _{i=0}^{3}\sum \limits _{j=1}^{3}a_{ij}x^{i}jy^{j-1},}$$ $${\displaystyle p_{xy}(x,y)=\textstyle \sum \limits _{i=1}^{3}\sum \limits _{j=1}^{3}a_{ij}ix^{i-1}jy^{j-1}.}$$

Este procedimiento produce una superficie en el cuadrado unitario que es continua y tiene derivadas continuas. La interpolación bicúbica en una cuadrícula regular de tamaño arbitrario se puede lograr juntando dichas superficies bicúbicas, asegurándose de que las derivadas coincidan en los límites. ${\displaystyle p(x,y)}$ ${\displaystyle [0,1]\times [0,1]}$

Agrupar los parámetros desconocidos en un vector y dejar que el sistema de ecuaciones anterior se pueda reformular en una matriz para la ecuación lineal . ${\displaystyle a_{ij}}$ $${\displaystyle \alpha =\left[{\begin{smallmatrix}a_{00}&a_{10}&a_{20}&a_{30}&a_{01}&a_{11}&a_{21}&a_{31}&a_{02}&a_{12}&a_{22}&a_{32}&a_{03}&a_{13}&a_{23}&a_{33}\end{smallmatrix}}\right]^{T}}$$ $${\displaystyle x=\left[{\begin{smallmatrix}f(0,0)&f(1,0)&f(0,1)&f(1,1)&f_{x}(0,0)&f_{x}(1,0)&f_{x}(0,1)&f_{x}(1,1)&f_{y}(0,0)&f_{y}(1,0)&f_{y}(0,1)&f_{y}(1,1)&f_{xy}(0,0)&f_{xy}(1,0)&f_{xy}(0,1)&f_{xy}(1,1)\end{smallmatrix}}\right]^{T},}$$ ${\displaystyle A\alpha =x}$

Invertir la matriz da como resultado la ecuación lineal más útil , donde α permite calcularla de forma rápida y sencilla. ${\displaystyle A^{-1}x=\alpha }$ $${\displaystyle A^{-1}=\left[{\begin{smallmatrix}{\begin{array}{rrrrrrrrrrrrrrrr}1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0\\-3&3&0&0&-2&-1&0&0&0&0&0&0&0&0&0&0\\2&-2&0&0&1&1&0&0&0&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0\\0&0&0&0&0&0&0&0&-3&3&0&0&-2&-1&0&0\\0&0&0&0&0&0&0&0&2&-2&0&0&1&1&0&0\\-3&0&3&0&0&0&0&0&-2&0&-1&0&0&0&0&0\\0&0&0&0&-3&0&3&0&0&0&0&0&-2&0&-1&0\\9&-9&-9&9&6&3&-6&-3&6&-6&3&-3&4&2&2&1\\-6&6&6&-6&-3&-3&3&3&-4&4&-2&2&-2&-2&-1&-1\\2&0&-2&0&0&0&0&0&1&0&1&0&0&0&0&0\\0&0&0&0&2&0&-2&0&0&0&0&0&1&0&1&0\\-6&6&6&-6&-4&-2&4&2&-3&3&-3&3&-2&-1&-2&-1\\4&-4&-4&4&2&2&-2&-2&2&-2&2&-2&1&1&1&1\end{array}}\end{smallmatrix}}\right],}$$ ${\displaystyle \alpha }$

Puede haber otra forma matricial concisa para 16 coeficientes: o donde $${\displaystyle {\begin{bmatrix}f(0,0)&f(0,1)&f_{y}(0,0)&f_{y}(0,1)\\f(1,0)&f(1,1)&f_{y}(1,0)&f_{y}(1,1)\\f_{x}(0,0)&f_{x}(0,1)&f_{xy}(0,0)&f_{xy}(0,1)\\f_{x}(1,0)&f_{x}(1,1)&f_{xy}(1,0)&f_{xy}(1,1)\end{bmatrix}}={\begin{bmatrix}1&0&0&0\\1&1&1&1\\0&1&0&0\\0&1&2&3\end{bmatrix}}{\begin{bmatrix}a_{00}&a_{01}&a_{02}&a_{03}\\a_{10}&a_{11}&a_{12}&a_{13}\\a_{20}&a_{21}&a_{22}&a_{23}\\a_{30}&a_{31}&a_{32}&a_{33}\end{bmatrix}}{\begin{bmatrix}1&1&0&0\\0&1&1&1\\0&1&0&2\\0&1&0&3\end{bmatrix}},}$$ $${\displaystyle {\begin{bmatrix}a_{00}&a_{01}&a_{02}&a_{03}\\a_{10}&a_{11}&a_{12}&a_{13}\\a_{20}&a_{21}&a_{22}&a_{23}\\a_{30}&a_{31}&a_{32}&a_{33}\end{bmatrix}}={\begin{bmatrix}1&0&0&0\\0&0&1&0\\-3&3&-2&-1\\2&-2&1&1\end{bmatrix}}{\begin{bmatrix}f(0,0)&f(0,1)&f_{y}(0,0)&f_{y}(0,1)\\f(1,0)&f(1,1)&f_{y}(1,0)&f_{y}(1,1)\\f_{x}(0,0)&f_{x}(0,1)&f_{xy}(0,0)&f_{xy}(0,1)\\f_{x}(1,0)&f_{x}(1,1)&f_{xy}(1,0)&f_{xy}(1,1)\end{bmatrix}}{\begin{bmatrix}1&0&-3&2\\0&0&3&-2\\0&1&-2&1\\0&0&-1&1\end{bmatrix}},}$$ $${\displaystyle p(x,y)={\begin{bmatrix}1&x&x^{2}&x^{3}\end{bmatrix}}{\begin{bmatrix}a_{00}&a_{01}&a_{02}&a_{03}\\a_{10}&a_{11}&a_{12}&a_{13}\\a_{20}&a_{21}&a_{22}&a_{23}\\a_{30}&a_{31}&a_{32}&a_{33}\end{bmatrix}}{\begin{bmatrix}1\\y\\y^{2}\\y^{3}\end{bmatrix}}.}$$

Extensión a rejillas rectilíneas

A menudo, las aplicaciones requieren una interpolación bicúbica utilizando datos en una cuadrícula rectilínea, en lugar del cuadrado unitario. En este caso, las identidades para y se convierten en donde es el espaciado de la celda que contiene el punto y similar para . En este caso, el enfoque más práctico para calcular los coeficientes es dejar que luego se resuelva con como antes. A continuación, las variables de interpolación normalizadas se calculan como donde y son las coordenadas y de los puntos de la cuadrícula que rodean el punto . Luego, la superficie de interpolación se convierte en ${\displaystyle p_{x},p_{y},}$ ${\displaystyle p_{xy}}$ $${\displaystyle p_{x}(x,y)=\textstyle \sum \limits _{i=1}^{3}\sum \limits _{j=0}^{3}{\frac {a_{ij}ix^{i-1}y^{j}}{\Delta x}},}$$ $${\displaystyle p_{y}(x,y)=\textstyle \sum \limits _{i=0}^{3}\sum \limits _{j=1}^{3}{\frac {a_{ij}x^{i}jy^{j-1}}{\Delta y}},}$$ $${\displaystyle p_{xy}(x,y)=\textstyle \sum \limits _{i=1}^{3}\sum \limits _{j=1}^{3}{\frac {a_{ij}ix^{i-1}jy^{j-1}}{\Delta x\Delta y}},}$$ ${\displaystyle \Delta x}$ ${\displaystyle x}$ ${\displaystyle (x,y)}$ ${\displaystyle \Delta y}$ ${\displaystyle \alpha }$ $${\displaystyle x=\left[{\begin{smallmatrix}f(0,0)&f(1,0)&f(0,1)&f(1,1)&\Delta xf_{x}(0,0)&\Delta xf_{x}(1,0)&\Delta xf_{x}(0,1)&\Delta xf_{x}(1,1)&\Delta yf_{y}(0,0)&\Delta yf_{y}(1,0)&\Delta yf_{y}(0,1)&\Delta yf_{y}(1,1)&\Delta x\Delta yf_{xy}(0,0)&\Delta x\Delta yf_{xy}(1,0)&\Delta x\Delta yf_{xy}(0,1)&\Delta x\Delta yf_{xy}(1,1)\end{smallmatrix}}\right]^{T},}$$ ${\displaystyle \alpha =A^{-1}x}$ ${\displaystyle A}$ $${\displaystyle {\begin{aligned}{\overline {x}}&={\frac {x-x_{0}}{x_{1}-x_{0}}},\\{\overline {y}}&={\frac {y-y_{0}}{y_{1}-y_{0}}}\end{aligned}}}$$ ${\displaystyle x_{0},x_{1},y_{0},}$ ${\displaystyle y_{1}}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle (x,y)}$ $${\displaystyle p(x,y)=\sum \limits _{i=0}^{3}\sum _{j=0}^{3}a_{ij}{\overline {x}}^{i}{\overline {y}}^{j}.}$$

Encontrar derivadas a partir de valores de funciones

Si se desconocen las derivadas, normalmente se aproximan a partir de los valores de la función en puntos vecinos a las esquinas del cuadrado unitario, por ejemplo, utilizando diferencias finitas .

Para hallar cualquiera de las derivadas simples, o , utilizando ese método, encuentre la pendiente entre los dos puntos circundantes en el eje apropiado. Por ejemplo, para calcular para uno de los puntos, encuentre para los puntos a la izquierda y a la derecha del punto de destino y calcule su pendiente, y de manera similar para . ${\displaystyle f_{x}}$ ${\displaystyle f_{y}}$ ${\displaystyle f_{x}}$ ${\displaystyle f(x,y)}$ ${\displaystyle f_{y}}$

Para hallar la derivada cruzada , se toma la derivada en ambos ejes, uno a la vez. Por ejemplo, primero se puede utilizar el procedimiento para hallar las derivadas de los puntos por encima y por debajo del punto de destino, y luego utilizar el procedimiento sobre esos valores (en lugar de, como es habitual, los valores de para esos puntos) para obtener el valor de para el punto de destino. (O se puede hacer en la dirección opuesta, calculando primero y luego a partir de ellos. Los dos dan resultados equivalentes). ${\displaystyle f_{xy}}$ ${\displaystyle f_{x}}$ ${\displaystyle x}$ ${\displaystyle f_{y}}$ ${\displaystyle f}$ ${\displaystyle f_{xy}(x,y)}$ ${\displaystyle f_{y}}$ ${\displaystyle f_{x}}$

En los bordes del conjunto de datos, cuando faltan algunos de los puntos circundantes, se pueden aproximar los puntos faltantes mediante varios métodos. Un método simple y común es suponer que la pendiente desde el punto existente hasta el punto objetivo continúa sin cambios adicionales y usar esto para calcular un valor hipotético para el punto faltante.

Algoritmo de convolución bicúbica

La interpolación spline bicúbica requiere la solución del sistema lineal descrito anteriormente para cada celda de la cuadrícula. Se puede obtener un interpolador con propiedades similares aplicando una convolución con el siguiente núcleo en ambas dimensiones: donde normalmente se establece en −0,5 o −0,75. Tenga en cuenta que y para todos los números enteros distintos de cero . $${\displaystyle W(x)={\begin{cases}(a+2)|x|^{3}-(a+3)|x|^{2}+1&{\text{for }}|x|\leq 1,\\a|x|^{3}-5a|x|^{2}+8a|x|-4a&{\text{for }}1<|x|<2,\\0&{\text{otherwise}},\end{cases}}}$$ ${\displaystyle a}$ ${\displaystyle W(0)=1}$ ${\displaystyle W(n)=0}$ ${\displaystyle n}$

Este enfoque fue propuesto por Keys, quien demostró que produce convergencia de tercer orden con respecto al intervalo de muestreo de la función original. ^[1] ${\displaystyle a=-0.5}$

Si utilizamos la notación matricial para el caso común , podemos expresar la ecuación de una manera más amigable: para entre 0 y 1 para una dimensión. Tenga en cuenta que para la interpolación de convolución cúbica unidimensional se requieren 4 puntos de muestra. Para cada consulta, se ubican dos muestras a su izquierda y dos muestras a su derecha. Estos puntos están indexados de −1 a 2 en este texto. La distancia desde el punto indexado con 0 hasta el punto de consulta se denota aquí por . ${\displaystyle a=-0.5}$ $${\displaystyle p(t)={\tfrac {1}{2}}{\begin{bmatrix}1&t&t^{2}&t^{3}\end{bmatrix}}{\begin{bmatrix}0&2&0&0\\-1&0&1&0\\2&-5&4&-1\\-1&3&-3&1\end{bmatrix}}{\begin{bmatrix}f_{-1}\\f_{0}\\f_{1}\\f_{2}\end{bmatrix}}}$$ ${\displaystyle t}$ ${\displaystyle t}$

Para dos dimensiones aplicadas primero una vez y otra vez en : ${\displaystyle x}$ ${\displaystyle y}$ $${\displaystyle {\begin{aligned}b_{-1}&=p(t_{x},f_{(-1,-1)},f_{(0,-1)},f_{(1,-1)},f_{(2,-1)}),\\[1ex]b_{0}&=p(t_{x},f_{(-1,0)},f_{(0,0)},f_{(1,0)},f_{(2,0)}),\\[1ex]b_{1}&=p(t_{x},f_{(-1,1)},f_{(0,1)},f_{(1,1)},f_{(2,1)}),\\[1ex]b_{2}&=p(t_{x},f_{(-1,2)},f_{(0,2)},f_{(1,2)},f_{(2,2)}),\end{aligned}}}$$ $${\displaystyle p(x,y)=p(t_{y},b_{-1},b_{0},b_{1},b_{2}).}$$

Uso en gráficos por computadora

La mitad inferior de esta figura es una ampliación de la mitad superior, que muestra cómo se crea la nitidez aparente de la línea de la izquierda. La interpolación bicúbica provoca un sobreimpulso, lo que aumenta la agudeza .

El algoritmo bicúbico se utiliza con frecuencia para escalar imágenes y vídeos para su visualización (consulte remuestreo de mapas de bits ). Conserva los detalles finos mejor que el algoritmo bilineal común .

Sin embargo, debido a los lóbulos negativos del núcleo, se produce un sobreimpulso (aureola). Esto puede provocar recortes y es un artefacto (consulte también artefactos de anillado ), pero aumenta la agudeza (nitidez aparente) y puede ser deseable.

Véase también

• Portal de matemáticas

• Anti-aliasing espacial
• Superficie de Bézier
• Interpolación bilineal
• Spline cúbico de Hermite , el análogo unidimensional del spline bicúbico
• Remuestreo de Lanczos
• Interpolación de vecinos naturales
• Filtro de sincronización
• Interpolación de splines
• Interpolación tricúbica
• Interpolación de convolución cúbica direccional

Referencias

1. R. Keys (1981). "Interpolación de convolución cúbica para procesamiento de imágenes digitales". IEEE Transactions on Acoustics, Speech, and Signal Processing . 29 (6): 1153–1160. Bibcode :1981ITASS..29.1153K. CiteSeerX  10.1.1.320.776 . doi :10.1109/TASSP.1981.1163711.

Enlaces externos

• Aplicación de la interpolación a muestras de elevación
• Teoría de interpolación
• Explicación e implementación en Java/C++ de la interpolación (bi)cúbica
• Función de la hoja de cálculo de Excel para la interpolación bicúbica de Lagrange