En la
primera parte de esta publicación, hablé sobre cómo el uso repetido de los filtros de halfpel estándar crea imágenes distorsionadas, y luego mostré un nuevo filtro que no tiene este problema.
Estaba un poco más borroso y esto no sería adecuado para todos. Sin embargo, era mejor que sus alternativas; de hecho, este filtro se usó en la versión original de
Bink 2 . Debido a la carga de trabajo constante, nunca logré volver a él de nuevo y examinarlo con más detalle.
Pero ahora que he
encontrado tiempo para volver a este filtro y escribir un artículo al respecto, finalmente debería hacer una pregunta: ¿hay un filtro
menos borroso que aún conserva la propiedad de "estabilidad infinita"?
Advertencia de spoiler: la respuesta correcta es "probablemente no" y "definitivamente ahí". Pero antes de llegar a por qué hay dos respuestas a esta pregunta y qué significan, mejor preparemos un banco de pruebas.
Ajuste de compensación
Cuando trabajé inicialmente en este problema, no tenía idea de lo que estaba buscando. Ni siquiera sabía que
existía algo así como un filtro de halfpel "infinitamente estable", por lo que no creé un sistema en su búsqueda. Estaba buscando algo que resistiera las "muchas" iteraciones de filtro sin distorsión de imagen. Todas las imágenes de la primera parte reflejan esta metodología: la imagen se desplaza de derecha a izquierda medio píxel a la vez, es decir, si aplica el filtro 100 veces, la imagen resultante se desplazará 50 píxeles.
Ahora que sabemos lo que
realmente estamos buscando, podemos ser un poco más precisos. Aplicando el filtro halfpel dos veces, cambiamos la imagen exactamente un píxel. Es decir, si simplemente
movemos la imagen un píxel hacia atrás , entonces permanecerá en el mismo espacio. Gracias a esto, la prueba se verá mucho más hermosa, porque no solo podremos aplicar el filtro varias veces, sin temor a que la imagen se "arrastre" fuera de la pantalla, sino que también podremos encontrar la
diferencia de la imagen con versiones anteriores y el original.
Esto nos permitirá probar los filtros automáticamente. Simplemente aplicamos el filtro muchas veces y vemos una de dos cosas: convergencia a una imagen sin cambios, lo que indica que el filtro es infinitamente estable, o una desviación significativamente grande de la imagen original, lo que indica que el filtro está "roto". Para estas pruebas, elegí el error promedio por canal 64 (de 255), o el error máximo en cualquiera de los canales al 255 completo como "significativamente grande". Si alguna de estas condiciones es cierta, asumiremos que el filtro "se rompió" ".
Volver a probar los filtros de la primera parte
Entonces, ahora entendemos mejor cómo probar estos filtros, así que echemos un vistazo a los filtros de la primera parte. Comencemos con un bilineal, que, por supuesto, no es muy interesante:
Esta es una imagen después de 244 iteraciones. Como es de esperar, la imagen se "rompe" gradualmente debido al promedio constante de píxeles. Pero incluso gradualmente alcanza el límite del error promedio.
Aquí está h.264:
Para romper la imagen, 78 iteraciones son suficientes para él. El filtro HEVC con 8 muestras se comporta un poco mejor, pero aún se rompe después de 150 iteraciones:
Lanczos con 6 cortes de muestras después de 166 iteraciones:
Esos son todos nuestros filtros rotos. Todo lo que queda es mi filtro entero:
Como era de esperar, no fue
el único
en romper. Converge en una imagen infinitamente estable después de 208 iteraciones.
Lo que sabemos es bastante notable aquí: al menos para una amplia gama de imágenes de prueba, este filtro es
infinitamente estable , es decir, nunca creará un artefacto, sin importar cuántas veces se use.
Esto nos lleva de vuelta a la pregunta original: ¿es realmente el mejor? Y ya sabes las respuestas, porque al principio del artículo también escribí: "probablemente no" y "definitivamente sí".
Primero veamos primero la parte "probablemente no".
Filtros enteros
Entonces, en la primera parte de la publicación, mencioné que el núcleo del filtro que encontré era "el mejor de los detectados", y esta es su peculiaridad. Y aquí está la característica:
Cuando estaba buscando este filtro,
de hecho, no estaba buscando el
mejor filtro. Estaba buscando el mejor filtro
que se pueda expresar con un número muy pequeño de cambios enteros, sumas y restas . Puede parecer extraño, pero tómate tu tiempo.
Es posible que haya notado que cuando mostré los coeficientes de h.264, HEVC y el filtro bilineal, así como mi filtro, los escribí como numeradores enteros sobre denominadores enteros, como este:
MyKernel[] = {1.0/32.0, -4.0/32.0, 19.0/32.0, 19.0/32.0, -4.0/32.0, 1.0/32.0};
Pero en el caso de la ventana sinc, actué de manera diferente y lo escribí así:
LanczosKernel[] = {0.02446, -0.13587, 0.61141, 0.61141, -0.13587, 0.02446};
La razón de esto es que el sinc en ventana se infiere realmente de una función matemática continua que no tiene nada que ver con fracciones enteras ordinarias. Cuando se usa este filtro, se usan números de coma flotante (con la mayor precisión posible) que corresponden a los valores de la función sinc. Si se esfuerza por aplicarlos con precisión, no debe redondearlos a fracciones comunes, ya que esto agregará un error.
Los códecs de video tradicionalmente no pueden permitirse realizar tales operaciones. Las operaciones de punto flotante en tareas "pesadas" como la compensación de movimiento son simplemente imposibles de usar en equipos especializados o de baja potencia. Esto es
especialmente cierto si estamos hablando de códecs estándar de la industria que deberían ejecutarse en una amplia gama de dispositivos, incluidos chips integrados de bajo costo y bajo costo.
Además, incluso si los ejecuta en la CPU, los conjuntos de instrucciones modernos se basan en SIMD, es decir, las operaciones de enteros en la CPU aún se pueden realizar más rápido: puede colocar dos enteros de 16 bits en el espacio de un flotante de 32 bits, esencialmente duplicando el rendimiento de las operaciones, por lo tanto, si consideramos el número exacto de ciclos por operación, un punto flotante no siempre es la opción más rápida.
Ahora puede ver por qué esta característica era importante. Como solo necesitaba operaciones enteras simples de 16 bits, busqué los núcleos que se pueden expresar como enteros pequeños sobre divisores en el poder de dos a 64 y no más. Este es un conjunto de filtros mucho más limitado en comparación con si estuviera considerando
cualquier conjunto de 6 coeficientes de coma flotante.
Del mismo modo, por razones de eficiencia, no consideré ningún
otro número de muestras. La única opción era 6 o menos, por lo que ni siquiera probé versiones con 8 o 10 muestras.
Así llegamos a la primera respuesta: "probablemente no". Si nos adherimos a estas restricciones, lo más probable es que no encontremos un mejor filtro que pueda aplicarse infinitas veces sin degradación. El núcleo del filtro de la primera parte es
probablemente el mejor que podemos encontrar, aunque debe admitirse que no puedo probarlo exhaustivamente.
Pero, ¿qué pasa si
no necesitamos adherirnos a tales restricciones?
Versión de punto flotante
Si nos deshacemos de las limitaciones específicas de la versión original de
Bink 2 (que ahora está bastante desactualizada, desde entonces se han lanzado muchas revisiones) y utilizamos coeficientes arbitrarios de punto flotante, ¿cómo podemos mejorar los resultados?
Bueno, dado que sabemos que mi núcleo entero nunca se degrada, y sabemos que Lanczos es más agudo, pero se degrada, es lógico que podamos encontrar un lugar
entre los dos conjuntos de coeficientes donde comienza la degradación. Entonces escribí un programa que me ayudó a encontrar este punto en particular, y esto es lo que encontré:
MyFloatKernel6[] = {0.027617, -0.130815, 0.603198, 0.603198, -0.130815, 0.027617};
Este núcleo requiere 272 iteraciones para converger, pero es infinitamente estable y se ve
mucho más nítido que mi filtro entero:
De hecho, es casi indistinguible del original:
Casi ... pero no del todo. Si observa de cerca, aún puede ver desenfoque y atenuación en áreas de alto contraste. La forma más fácil de ver esto es en el ojo de un "dinosaurio" naranja y en áreas de luz brillante detrás del bambú.
Es decir, un filtro de punto flotante de 6 muestras es definitivamente mejor, pero no es perfecto. ¿Se puede mejorar todavía?
Aumentar el ancho del filtro
Inicialmente, se seleccionó un filtro con 6 muestras por las mismas razones que las fracciones con enteros pequeños: estaba buscando un filtro extremadamente eficiente. Pero ahora estamos investigando y ya hemos pasado a números de coma flotante, entonces, ¿por qué no considerar un filtro más amplio?
Combinando nuestro filtro entero de 6 muestras con los Lanczos de 6 muestras, obtuvimos un muy buen filtro. ¿Por qué no lo combinamos con los Lanczos de 8 muestras?
El Lanczos de 8 muestras se ve así:
Lanczos8[] = {-0.01263, 0.05976, -0.16601, 0.61888, 0.61888, -0.16601, 0.05976, -0.01263};
Al igual que los Lanczos de 6 muestras, es muy inestable y se derrumba después de 178 iteraciones:
Si buscamos un mejor filtro entre un filtro entero de 6 muestras y un Lanczos de 8 muestras, encontraremos este filtro de 8 muestras bastante notable:
MyFloatKernel8[] = {-0.010547, 0.052344, -0.156641, 0.614844, 0.614844, -0.156641, 0.052344, -0.010547};
Como filtro infinitamente estable, funciona increíblemente bien. Converge después de 202 iteraciones (la convergencia es más rápida que mis dos filtros), y se parece tanto al original que es difícil distinguir cuál de ellos es cuál:
Aquí está el original para referencia nuevamente:
En comparación con mi filtro entero original, hay una mejora significativa.
¿Cómo funcionan los filtros infinitamente estables?
Iba a terminar esta publicación algo como esto:
"No sé exactamente cómo funciona todo. En otras áreas donde he trabajado con las transformaciones infinitamente aplicables, sé cómo se realizan las matemáticas límite y se crea un análisis útil. En primer lugar, se trata del análisis de la superficie límite para las superficies de subdivisión, donde se calculan los valores propios y los vectores propios de la matriz de subdivisión, después de lo cual es posible llevar con precisión el límite a un grado infinito. Pero no tengo experiencia en realizar un análisis de este tipo para los filtros halfpel, porque no dejan píxeles en su lugar, sino que los desplazan de lado ".
Ese era mi plan. Pero entre la redacción de la primera y la segunda parte, envié los resultados del filtro mejorado a
Fabien Giessen y
Charles Bloom . No es sorprendente que supieran las matemáticas necesarias para el estudio analítico de este problema. Resultó que para los filtros realmente hay un análisis de valores propios y vectores, pero no funciona de esa manera.
Pero se
puede hacer fácilmente; de hecho, está integrado en los programas CAM como un proceso trivial de un solo paso y realmente podemos ver los valores propios de los filtros. No nos da respuestas completas, porque aquí el hecho de
redondear (o truncar) a 8 bits (o 10 bits, o 12 bits) después de cada filtrado es importante, porque el truncamiento afecta el método de acumular errores en comparación con el álgebra infinitamente precisa.
Desafortunadamente, dado que esta no es mi área de especialización, ni siquiera puedo obtener una visión general de este análisis. Le pregunté a Fabien y Charles si podían escribir publicaciones con la buena información que me enviaron por correo (ambos tienen blogs técnicos:
el blog ryg y los
comentarios de cbloom ), y Fabien escribió una
excelente serie de artículos sobre los fundamentos matemáticos de los filtros estables . Si estás interesado en la estructura teórica de lo que está sucediendo en mis dos publicaciones, ¡te recomiendo leer esta serie!