interpolación bicúbica

Extensión de la interpolación spline cúbica

Comparación de la interpolación bicúbica con algunas interpolaciones unidimensionales y bidimensionales. Los puntos
negro y rojo / amarillo / verde / azul 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 para aplicar 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 mediante 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 a menudo se elige 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 sólo 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. 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 sobre los límites del cuadrado.

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

Supongamos que los valores de la función y las derivadas , y se conocen en las cuatro esquinas , , y del cuadrado unitario. La superficie interpolada se puede escribir 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 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 uniendo dichas superficies bicúbicas, asegurando 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. ${\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 la ecuación lineal más útil , donde ${\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:

$${\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}}.}$$

Ampliación a rejillas rectilíneas

A menudo, las aplicaciones requieren interpolación bicúbica utilizando datos en una cuadrícula rectilínea, en lugar de la unidad cuadrada. En este caso, las identidades para y se convierten ${\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 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 encontrar cualquiera de las derivadas individuales, o , usando ese método, encuentre la pendiente entre los dos puntos circundantes en el eje apropiado. Por ejemplo, para calcular uno de los puntos, busque los puntos a la izquierda y a la derecha del punto objetivo 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 encontrar la derivada cruzada , toma la derivada en ambos ejes, uno a la vez. Por ejemplo, primero se puede usar el procedimiento para encontrar las derivadas de los puntos por encima y por debajo del punto objetivo, luego usar el procedimiento con esos valores (en lugar de, como es habitual, los valores de para esos puntos) para obtener el valor de para el punto objetivo. (O se puede hacerlo en la dirección opuesta, primero calculando y luego a partir de esos. 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, los puntos faltantes se pueden aproximar mediante varios métodos. Un método simple y común es asumir que la pendiente desde el punto existente hasta el punto objetivo continúa sin cambios adicionales y utilizar 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:

$${\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 usamos la notación matricial para el caso común , podemos expresar la ecuación de una manera más amigable: ${\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, se aplica primero una 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 aparente nitidez de la línea de la izquierda. La interpolación bicúbica provoca un exceso, lo que aumenta la acutancia .

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 exceso (halo). Esto puede causar recorte y es un artefacto (ver también artefactos de timbre ), pero aumenta la acutancia (nitidez aparente) y puede ser deseable.

Ver también

• Portal de matemáticas

• Antialiasing 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 spline
• interpolación tricúbica
• Interpolación de convolución cúbica direccional

Referencias

1. R. Claves (1981). "Interpolación de convolución cúbica para procesamiento de imágenes digitales". Transacciones IEEE sobre acústica, voz y procesamiento de señales . 29 (6): 1153-1160. Código Bib : 1981ITASS..29.1153K. CiteSeerX  10.1.1.320.776 . doi :10.1109/TASSP.1981.1163711.

enlaces externos

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