Interpolación bilineal

Método de interpolación de funciones en una cuadrícula 2D

Ejemplo de interpolación bilineal sobre el cuadrado unitario con los valores z 0, 1, 1 y 0,5 como se indica. Los valores interpolados intermedios se representan mediante colores.

En matemáticas , la interpolación bilineal es un método para interpolar funciones de dos variables (por ejemplo, x e y ) mediante interpolación lineal repetida . Por lo general, se aplica a funciones muestreadas en una cuadrícula rectilínea 2D , aunque se puede generalizar a funciones definidas en los vértices de (una malla de) cuadriláteros convexos arbitrarios .

La interpolación bilineal se realiza mediante interpolación lineal primero en una dirección y luego nuevamente en otra dirección. Aunque cada paso es lineal en los valores muestreados y en la posición, la interpolación en su conjunto no es lineal sino cuadrática en la ubicación de la muestra.

La interpolación bilineal es una de las técnicas básicas de remuestreo en visión por computadora y procesamiento de imágenes , donde también se denomina filtrado bilineal o mapeo de textura bilineal .

Cálculo

Los cuatro puntos rojos muestran los puntos de datos y el punto verde es el punto en el que queremos interpolar.

Supongamos que queremos hallar el valor de la función desconocida f en el punto ( x , y ). Se supone que conocemos el valor de f en los cuatro puntos Q ₁₁ = ( x ₁ ,  y ₁ ), Q ₁₂ = ( x ₁ ,  y ₂ ), Q ₂₁ = ( x ₂ ,  y ₁ ), y Q ₂₂ = ( x ₂ ,  y ₂ ).

Interpolación lineal repetida

Primero hacemos una interpolación lineal en la dirección x . Esto produce

${\displaystyle {\begin{aligned}f(x,y_{1})={\frac {x_{2}-x}{x_{2}-x_{1}}}f(Q_{11})+{\frac {x-x_{1}}{x_{2}-x_{1}}}f(Q_{21}),\\f(x,y_{2})={\frac {x_{2}-x}{x_{2}-x_{1}}}f(Q_{12})+{\frac {x-x_{1}}{x_{2}-x_{1}}}f(Q_{22}).\end{aligned}}}$

Procedemos interpolando en la dirección y para obtener la estimación deseada:

${\displaystyle {\begin{aligned}f(x,y)&={\frac {y_{2}-y}{y_{2}-y_{1}}}f(x,y_{1})+{\frac {y-y_{1}}{y_{2}-y_{1}}}f(x,y_{2})\\&={\frac {y_{2}-y}{y_{2}-y_{1}}}\left({\frac {x_{2}-x}{x_{2}-x_{1}}}f(Q_{11})+{\frac {x-x_{1}}{x_{2}-x_{1}}}f(Q_{21})\right)+{\frac {y-y_{1}}{y_{2}-y_{1}}}\left({\frac {x_{2}-x}{x_{2}-x_{1}}}f(Q_{12})+{\frac {x-x_{1}}{x_{2}-x_{1}}}f(Q_{22})\right)\\&={\frac {1}{(x_{2}-x_{1})(y_{2}-y_{1})}}\left(f(Q_{11})(x_{2}-x)(y_{2}-y)+f(Q_{21})(x-x_{1})(y_{2}-y)+f(Q_{12})(x_{2}-x)(y-y_{1})+f(Q_{22})(x-x_{1})(y-y_{1})\right)\\&={\frac {1}{(x_{2}-x_{1})(y_{2}-y_{1})}}{\begin{bmatrix}x_{2}-x&x-x_{1}\end{bmatrix}}{\begin{bmatrix}f(Q_{11})&f(Q_{12})\\f(Q_{21})&f(Q_{22})\end{bmatrix}}{\begin{bmatrix}y_{2}-y\\y-y_{1}\end{bmatrix}}.\end{aligned}}}$

Nótese que llegaremos al mismo resultado si la interpolación se realiza primero a lo largo de la dirección y y luego a lo largo de la dirección x . ^[1]

Ajuste polinomial

Una forma alternativa es escribir la solución del problema de interpolación como un polinomio multilineal.

${\displaystyle f(x,y)\approx a_{00}+a_{10}x+a_{01}y+a_{11}xy,}$

donde los coeficientes se encuentran resolviendo el sistema lineal

${\displaystyle {\begin{aligned}{\begin{bmatrix}1&x_{1}&y_{1}&x_{1}y_{1}\\1&x_{1}&y_{2}&x_{1}y_{2}\\1&x_{2}&y_{1}&x_{2}y_{1}\\1&x_{2}&y_{2}&x_{2}y_{2}\end{bmatrix}}{\begin{bmatrix}a_{00}\\a_{10}\\a_{01}\\a_{11}\end{bmatrix}}={\begin{bmatrix}f(Q_{11})\\f(Q_{12})\\f(Q_{21})\\f(Q_{22})\end{bmatrix}},\end{aligned}}}$

dando el resultado

${\displaystyle {\begin{aligned}{\begin{bmatrix}a_{00}\\a_{10}\\a_{01}\\a_{11}\end{bmatrix}}={\frac {1}{(x_{2}-x_{1})(y_{2}-y_{1})}}{\begin{bmatrix}x_{2}y_{2}&-x_{2}y_{1}&-x_{1}y_{2}&x_{1}y_{1}\\-y_{2}&y_{1}&y_{2}&-y_{1}\\-x_{2}&x_{2}&x_{1}&-x_{1}\\1&-1&-1&1\end{bmatrix}}{\begin{bmatrix}f(Q_{11})\\f(Q_{12})\\f(Q_{21})\\f(Q_{22})\end{bmatrix}}.\end{aligned}}}$

Media ponderada

Visualización geométrica de la interpolación bilineal. El producto del valor en el punto deseado (negro) y el área total es igual a la suma de los productos del valor en cada esquina y el área parcial diagonalmente opuesta a la esquina (colores correspondientes).

La solución también se puede escribir como una media ponderada de f ( Q ​​):

${\displaystyle f(x,y)\approx w_{11}f(Q_{11})+w_{12}f(Q_{12})+w_{21}f(Q_{21})+w_{22}f(Q_{22}),}$

donde los pesos suman 1 y satisfacen el sistema lineal transpuesto

${\displaystyle {\begin{bmatrix}1&1&1&1\\x_{1}&x_{1}&x_{2}&x_{2}\\y_{1}&y_{2}&y_{1}&y_{2}\\x_{1}y_{1}&x_{1}y_{2}&x_{2}y_{1}&x_{2}y_{2}\end{bmatrix}}{\begin{bmatrix}w_{11}\\w_{12}\\w_{21}\\w_{22}\end{bmatrix}}={\begin{bmatrix}1\\x\\y\\xy\end{bmatrix}},}$

dando el resultado

${\displaystyle {\begin{aligned}{\begin{bmatrix}w_{11}\\w_{21}\\w_{12}\\w_{22}\end{bmatrix}}={\frac {1}{(x_{2}-x_{1})(y_{2}-y_{1})}}{\begin{bmatrix}x_{2}y_{2}&-y_{2}&-x_{2}&1\\-x_{2}y_{1}&y_{1}&x_{2}&-1\\-x_{1}y_{2}&y_{2}&x_{1}&-1\\x_{1}y_{1}&-y_{1}&-x_{1}&1\end{bmatrix}}{\begin{bmatrix}1\\x\\y\\xy\end{bmatrix}},\end{aligned}}}$

Lo cual se simplifica a

${\displaystyle {\begin{aligned}w_{11}&=(x_{2}-x)(y_{2}-y)/((x_{2}-x_{1})(y_{2}-y_{1})),\\w_{12}&=(x_{2}-x)(y-y_{1})/((x_{2}-x_{1})(y_{2}-y_{1})),\\w_{21}&=(x-x_{1})(y_{2}-y)/((x_{2}-x_{1})(y_{2}-y_{1})),\\w_{22}&=(x-x_{1})(y-y_{1})/((x_{2}-x_{1})(y_{2}-y_{1})),\end{aligned}}}$

De acuerdo con el resultado obtenido por interpolación lineal repetida, el conjunto de pesos también puede interpretarse como un conjunto de coordenadas baricéntricas generalizadas para un rectángulo.

Forma matricial alternativa

Combinando lo anterior, tenemos

${\displaystyle {\begin{aligned}f(x,y)\approx {\frac {1}{(x_{2}-x_{1})(y_{2}-y_{1})}}{\begin{bmatrix}f(Q_{11})&f(Q_{12})&f(Q_{21})&f(Q_{22})\end{bmatrix}}{\begin{bmatrix}x_{2}y_{2}&-y_{2}&-x_{2}&1\\-x_{2}y_{1}&y_{1}&x_{2}&-1\\-x_{1}y_{2}&y_{2}&x_{1}&-1\\x_{1}y_{1}&-y_{1}&-x_{1}&1\end{bmatrix}}{\begin{bmatrix}1\\x\\y\\xy\end{bmatrix}}.\end{aligned}}}$

En el cuadrado unitario

Si elegimos un sistema de coordenadas en el que los cuatro puntos donde se conoce f son (0, 0), (0, 1), (1, 0) y (1, 1), entonces la fórmula de interpolación se simplifica a

${\displaystyle f(x,y)\approx f(0,0)(1-x)(1-y)+f(0,1)(1-x)y+f(1,0)x(1-y)+f(1,1)xy,}$

o equivalentemente, en operaciones matriciales:

${\displaystyle f(x,y)\approx {\begin{bmatrix}1-x&x\end{bmatrix}}{\begin{bmatrix}f(0,0)&f(0,1)\\f(1,0)&f(1,1)\end{bmatrix}}{\begin{bmatrix}1-y\\y\end{bmatrix}}.}$

Aquí también reconocemos los pesos:

${\displaystyle {\begin{aligned}w_{11}&=(1-x)(1-y),\\w_{12}&=(1-x)y,\\w_{21}&=x(1-y),\\w_{22}&=xy.\end{aligned}}}$

Alternativamente, el interpolante en el cuadrado unitario se puede escribir como

${\displaystyle f(x,y)=a_{00}+a_{10}x+a_{01}y+a_{11}xy,}$

dónde

${\displaystyle {\begin{aligned}a_{00}&=f(0,0),\\a_{10}&=f(1,0)-f(0,0),\\a_{01}&=f(0,1)-f(0,0),\\a_{11}&=f(1,1)-f(1,0)-f(0,1)+f(0,0).\end{aligned}}}$

En ambos casos, el número de constantes (cuatro) corresponde al número de puntos de datos donde se da f .

Propiedades

Comparación de la interpolación bilineal 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.

Como sugiere el nombre, el interpolante bilineal no es lineal; pero es lineal (es decir, afín) a lo largo de líneas paralelas a la dirección x o y , equivalentemente si x o y se mantienen constantes. A lo largo de cualquier otra línea recta, el interpolante es cuadrático . Aunque la interpolación no es lineal en la posición ( x e y ), en un punto fijo es lineal en los valores de interpolación, como se puede ver en las ecuaciones (matriciales) anteriores.

El resultado de la interpolación bilineal es independiente de qué eje se interpola primero y cuál segundo. Si hubiéramos realizado primero la interpolación lineal en la dirección y y luego en la dirección x , la aproximación resultante sería la misma.

El interpolante es un polinomio bilineal , que también es una función armónica que satisface la ecuación de Laplace . Su gráfico es un parche de superficie de Bézier bilineal .

Inversa y generalización

En general, el interpolante asumirá cualquier valor (en la envoltura convexa de los valores de los vértices) en un número infinito de puntos (formando ramas de hipérbolas ^[2] ), por lo que la interpolación no es invertible.

Sin embargo, cuando la interpolación bilineal se aplica a dos funciones simultáneamente, como cuando se interpola un campo vectorial , entonces la interpolación es invertible (bajo ciertas condiciones). En particular, esta inversa se puede utilizar para encontrar las "coordenadas cuadradas unitarias" de un punto dentro de cualquier cuadrilátero convexo (considerando las coordenadas del cuadrilátero como un campo vectorial que se interpola bilinealmente en el cuadrado unitario). Usando este procedimiento, la interpolación bilineal se puede extender a cualquier cuadrilátero convexo, aunque el cálculo es significativamente más complicado si no es un paralelogramo. ^[3] El mapa resultante entre cuadriláteros se conoce como transformación bilineal , deformación bilineal o distorsión bilineal .

Alternativamente, se puede utilizar una función proyectiva entre un cuadrilátero y el cuadrado unitario, pero el interpolante resultante no será bilineal.

En el caso especial en que el cuadrilátero es un paralelogramo , existe una aplicación lineal al cuadrado unitario y la generalización se sigue fácilmente.

La extensión obvia de la interpolación bilineal a tres dimensiones se llama interpolación trilineal .

Aplicación en el procesamiento de imágenes

En la visión artificial y el procesamiento de imágenes , se utiliza la interpolación bilineal para remuestrear imágenes y texturas. Se utiliza un algoritmo para asignar la ubicación de un píxel de la pantalla a un punto correspondiente en el mapa de texturas . Se calcula un promedio ponderado de los atributos (color, transparencia, etc.) de los cuatro texels circundantes y se aplica al píxel de la pantalla. Este proceso se repite para cada píxel que forma el objeto que se está texturizando. ^[4]

Cuando es necesario ampliar una imagen, cada píxel de la imagen original debe moverse en una dirección determinada en función de la constante de escala. Sin embargo, cuando se amplía una imagen mediante un factor de escala no integral, hay píxeles (es decir, agujeros ) a los que no se les asignan valores de píxel adecuados. En este caso, a esos agujeros se les deben asignar valores RGB o de escala de grises adecuados para que la imagen de salida no tenga píxeles sin valor.

La interpolación bilineal se puede utilizar cuando no es posible realizar una transformación perfecta de la imagen con coincidencia de píxeles, de modo que se puedan calcular y asignar valores de intensidad adecuados a los píxeles. A diferencia de otras técnicas de interpolación, como la interpolación del vecino más próximo y la interpolación bicúbica , la interpolación bilineal utiliza valores de solo los 4 píxeles más cercanos, ubicados en direcciones diagonales a partir de un píxel determinado, para encontrar los valores de intensidad de color adecuados para ese píxel.

La interpolación bilineal considera el vecindario 2 × 2 más cercano de valores de píxeles conocidos que rodean la ubicación calculada del píxel desconocido. Luego, toma un promedio ponderado de estos 4 píxeles para llegar a su valor interpolado final. ^{[5] [6]}

Ejemplo de interpolación bilineal en valores de escala de grises

Ejemplo

Como se ve en el ejemplo de la derecha, el valor de intensidad en el píxel calculado en la fila 20.2, columna 14.5 se puede calcular interpolando primero linealmente entre los valores en las columnas 14 y 15 en cada fila 20 y 21, dando

${\displaystyle {\begin{aligned}I_{20,14.5}&={\frac {15-14.5}{15-14}}\cdot 91+{\frac {14.5-14}{15-14}}\cdot 210=150.5,\\I_{21,14.5}&={\frac {15-14.5}{15-14}}\cdot 162+{\frac {14.5-14}{15-14}}\cdot 95=128.5,\end{aligned}}}$

y luego interpolando linealmente entre estos valores, obtenemos

${\displaystyle I_{20.2,14.5}={\frac {21-20.2}{21-20}}\cdot 150.5+{\frac {20.2-20}{21-20}}\cdot 128.5=146.1.}$

Este algoritmo reduce parte de la distorsión visual causada por el cambio de tamaño de una imagen a un factor de zoom no integral, a diferencia de la interpolación del vecino más cercano, que hará que algunos píxeles parezcan más grandes que otros en la imagen redimensionada.

Una simplificación de términos

Este ejemplo es de datos tabularizados de Presión (columnas) vs. Temperatura (filas) como una búsqueda en relación con alguna Variable

El siguiente cálculo estándar por partes tiene 18 operaciones requeridas.

${\displaystyle {\begin{aligned}I_{T_{1},P_{1}-P_{2}}&={\frac {P_{2}-P_{x}}{P_{2}-P_{1}}}\cdot V_{11}+{\frac {P_{x}-P_{1}}{P_{2}-P_{1}}}\cdot V_{12}=V_{1x},\\I_{T_{2},P_{1}-P_{2}}&={\frac {P_{2}-P_{x}}{P_{2}-P_{1}}}\cdot V_{21}+{\frac {P_{x}-P_{1}}{P_{2}-P_{1}}}\cdot V_{22}=V_{2x},\\I_{P_{x},T_{1}-T_{2}}&={\frac {T_{2}-T_{x}}{T_{2}-T_{1}}}\cdot V_{1x}+{\frac {T_{x}-T_{1}}{T_{2}-T_{1}}}\cdot V_{2x}=V_{xx}\end{aligned}}}$

Todo esto se puede simplificar desde las 18 operaciones individuales iniciales a 16 operaciones individuales como tales;

${\displaystyle V_{xx}={\frac {((P_{2}-P_{x})\cdot V_{11}+(P_{x}-P_{1})\cdot V_{12})\cdot (T_{2}-T_{x})+((P_{2}-P_{x})\cdot V_{21}+(P_{x}-P_{1})\cdot V_{22})\cdot (T_{x}-T_{1})}{(P_{2}-P_{1})\cdot (T_{2}-T_{1})}}.}$

Lo anterior tiene dos operaciones repetidas.

${\displaystyle (P_{2}-P_{x}),(P_{x}-P_{1}).}$

A estas dos repeticiones se les pueden asignar variables temporales mientras se calcula una única interpolación, lo que reducirá el número de cálculos a 14 operaciones, que es el número mínimo de pasos necesarios para producir la interpolación deseada. Al realizar esta interpolación en 14 operaciones en lugar de 18, resulta un 22 % más eficiente.

La simplificación de términos es una buena práctica para la aplicación de la metodología matemática a aplicaciones de ingeniería y puede reducir los requisitos computacionales y energéticos de un proceso.

Véase también

• Interpolación bicúbica
• Interpolación trilineal
• Interpolación de splines
• Remuestreo de Lanczos
• Interpolación escalonada
• Coordenadas baricéntricas : para interpolar dentro de un triángulo o tetraedro

Referencias

1. Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (1992). Recetas numéricas en C: el arte de la computación científica (2.ª ed.). Nueva York, NY, EE. UU.: Cambridge University Press. pp. 123-128. ISBN 0-521-43108-5.
2. Monasse, Pascal (10 de agosto de 2019). "Extracción de las líneas de nivel de una imagen bilineal". Procesamiento de imágenes en línea . 9 : 205–219. doi : 10.5201/ipol.2019.269 . ISSN  2105-1232.
3. Quilez, Inigo (2010). "Interpolación bilineal inversa". iquilezles.org . Archivado desde el original el 2010-08-13 . Consultado el 2024-02-17 .
4. Definición de interpolación bilineal (artículo popular en www.pcmag.com.
5. Khosravi, MR (19 de marzo de 2021). "BL-ALM: un filtro de reconstrucción guiado por bordes escalable y ciego para el monitoreo ambiental inteligente a través de redes ecológicas IoMT-UAV". Transacciones IEEE sobre comunicaciones y redes ecológicas . 5 (2): 727–736. doi :10.1109/TGCN.2021.3067555. S2CID  233669511.
6. "Tutorial web: Interpolación de imágenes digitales".