algorithm - ¿Dónde puedo encontrar una buena lectura sobre la interpolación bicúbica y el remuestreo de Lanczos?
image-processing resampling (3)
El principio de funcionamiento básico de ambos algoritmos es bastante simple. Ambos son filtros de convolución. Un filtro de convolución que para cada valor de salida mueve el punto de origen de las funciones de convolución para centrarse en la salida y luego multiplica todos los valores en la entrada con el valor de la función de convolución en esa ubicación y los suma.
Una propiedad de la convolución es que la integral de la salida es el producto de las integrales de las dos funciones de entrada. Si considera las imágenes de entrada y salida, entonces la integral significa brillo promedio y si desea que el brillo permanezca igual, la integral de la función de convolución debe sumar uno.
Una forma de entenderlos es pensar en la función de convolución como algo que muestra la cantidad de píxeles de entrada que influyen en el píxel de salida en función de su distancia.
Las funciones de convolución generalmente se definen de modo que sean cero cuando la distancia sea mayor que algún valor, de modo que no tenga que considerar cada valor de entrada para cada valor de salida.
Para la interpolación de lanczos, la función de convolución se basa en la función sinc (x) = sin (x * pi) / x , pero solo se toman los primeros lóbulos. Generalmente 3:
lanczos(x) = {
0 if abs(x) > 3,
1 if x == 0,
else sin(x*pi)/x
}
Esta función se llama el núcleo del filtro.
Para volver a muestrear con lanczos, imagina que superpones la salida y la entrada entre sí, con puntos que indican dónde están las ubicaciones de los píxeles. Para cada ubicación de píxeles de salida, toma un cuadro + - 3 píxeles de salida desde ese punto. Para cada píxel de entrada que se encuentra en ese cuadro, calcule el valor de la función lanczos en esa ubicación con la distancia desde la ubicación de salida en las coordenadas de píxel de salida como parámetro. Luego, debe normalizar los valores calculados escalando para que sumen 1. Después de eso, multiplique cada valor de píxel de entrada con el valor de escala correspondiente y agregue los resultados para obtener el valor del píxel de salida.
Debido a que la función lanzos tiene la propiedad de separabilidad y, si está redimensionando, la cuadrícula es regular, puede optimizar esto haciendo la convolución horizontal y verticalmente por separado y precalcular los filtros verticales para cada fila y los filtros horizontales para cada columna.
La convolución bicúbica es básicamente la misma, con una función diferente de kernel de filtro.
Para obtener más detalles, hay una explicación bastante buena y completa en el libro Procesamiento de imágenes digitales , sección 16.3.
Además, image_operations.cc y convolver.cc en skia tienen una implementación bastante bien comentada de la interpolación de lanczos.
Quiero implementar los dos algoritmos de remuestreo de imagen mencionados anteriormente (bicúbico y Lanczos) en C ++. Sé que hay docenas de implementaciones existentes por ahí, pero todavía quiero hacer las mías. Quiero hacerlo en parte porque quiero entender cómo funcionan, y en parte porque quiero darles algunas capacidades que no se encuentran en las implementaciones principales (como el soporte configurable de varias CPUs y el informe de progreso).
Intenté leer Wikipedia, pero las cosas son un poco demasiado secas para mí. Tal vez hay algunas explicaciones más agradables de estos algoritmos? No pude encontrar nada en SO o Google.
Añadido: Parece que nadie me puede dar un buen enlace sobre estos temas. ¿Alguien puede al menos intentar explicarlos aquí?
Me gustaría sugerir el siguiente artículo para una comprensión básica de los diferentes métodos de interpolación de imágenes interpolación de imágenes a través de la convolución . Si quieres probar más métodos de interpolación, el imageresampler es un buen proyecto de código abierto para empezar.
En mi opinión, la interpolación de imágenes puede entenderse desde dos aspectos, uno es desde la perspectiva de ajuste de función y el otro desde la perspectiva de convolución. Por ejemplo, la interpolación spline explicada en la interpolación de imágenes mediante convolución se explica bien desde la perspectiva de ajuste de función en la interpolación cúbica .
Además, la interpolación de imágenes siempre está relacionada con una aplicación específica, por ejemplo, zoom de imagen, rotación de imagen, etc. De hecho, para una aplicación específica, la interpolación de imágenes se puede implementar de manera inteligente. Por ejemplo, la rotación de la imagen se puede implementar a través de un método de tres cizallas , y durante cada operación de cizallamiento se pueden implementar diferentes algoritmos de interpolación de una dimensión.
Si bien lo que dice Ants Aasma describe la diferencia, no creo que sea particularmente informativo sobre por qué podrías hacer tal cosa.
En cuanto a los enlaces, estás haciendo una pregunta muy básica en el procesamiento de imágenes, y cualquier libro de texto de introducción decente sobre el tema lo describirá. Si recuerdo bien, Gonzales y Woods están decentes, pero estoy lejos de mis libros y no puedo verificar.
Ahora, en lo que respecta a los detalles, debería ayudar pensar en lo que está haciendo fundamentalmente. Tiene una red cuadrada de medidas para las que desea interpolar nuevos valores. En el caso simple de muestrear, imaginemos que desea una nueva medición entre cada una de las que ya tiene (por ejemplo, el doble de resolución).
Ahora no obtendrá el valor "correcto", porque en general no tiene esa información. Así que hay que estimarlo. ¿Como hacer esto? Una forma muy sencilla sería interpolar linealmente. Todo el mundo sabe cómo hacer esto con dos puntos, simplemente trace una línea entre ellos y lea el nuevo valor fuera de la línea (en este caso, en el punto medio).
Ahora, una imagen es bidimensional, por lo que realmente desea hacer esto en las direcciones izquierda-derecha y arriba-abajo. Utilice el resultado para su estimación y listo, tiene interpolación "bilineal".
El principal problema con esto es que no es muy preciso, aunque es mejor (y más lento) que el enfoque del "vecino más cercano", que también es muy local y rápido.
Para abordar el primer problema, desea algo mejor que un ajuste lineal de dos puntos, desea ajustar algo a más puntos de datos (píxeles) y algo que puede ser no lineal. Un buen intercambio de precisión y costo computacional es algo que se llama spline cúbico. Por lo tanto, esto le dará una línea de ajuste suave, y nuevamente se aproximará a su nueva "medición" por el valor que toma en el medio. Haga esto en ambas direcciones y obtendrá una interpolación "bicúbica".
Así que eso es más preciso, pero aún pesado. Una forma de abordar el problema de la velocidad es usar una convolución, que tiene la bonita propiedad de que en el dominio de Fourier, es solo una multiplicación, por lo que podemos implementarla con bastante rapidez. Pero no necesita preocuparse por la implementación para comprender que el resultado de la convolución en cualquier punto es una función (su imagen) que se integra en el producto, otra función de soporte típicamente más pequeña (la parte que no es cero) denominada kernel ), después de que el núcleo se haya centrado sobre ese punto en particular. En el mundo discreto, estas son solo sumas de los productos.
Resulta que puedes diseñar un núcleo de convolución que tiene propiedades como la spline cúbica, y usarlo para obtener un "bicúbico" rápido.
El remuestreo de Lancsoz es una cosa similar, con propiedades ligeramente diferentes en el núcleo, lo que principalmente significa que tendrán diferentes artefactos característicos. Puede consultar los detalles de estas funciones del kernel con la suficiente facilidad (estoy seguro de que wikipedia las tiene, o cualquier texto de introducción). Las implementaciones utilizadas en los programas de gráficos tienden a ser altamente optimizadas y, a veces, tienen supuestos especializados que los hacen más eficientes pero menos generales.