Escribamos un códec de video - Parte 3: imágenes fijas

En las partes anteriores de esta serie, aprendimos sobre la transformada discreta del coseno, desde su definición matemática hasta su implementación en ejemplos reales. Además, hemos visto cómo la capacidad de DCT para representar datos en el dominio de la frecuencia puede permitir la compresión de datos con pérdida.

Ahora, estamos dando el siguiente paso. Finalmente dibujaremos la línea que conecta estas matrices abstractas de números que hemos estado discutiendo y las imágenes reales que pueden representar.

Al final de este artículo, habremos redescubierto aproximadamente el 80 % del proceso real de compresión de imágenes JPEG.

La matriz

En el artículo anterior, presentamos el 2D-DCT. Ahora, veamos una versión ligeramente modificada de esa fórmula:

Las variables u y v representan el desplazamiento horizontal y vertical del valor en la matriz 2D codificada con DCT. La función α(x) es igual a 1/sqrt(2) si x == 0 y 1 en caso contrario. Por último, x e y representan la posición del píxel en la imagen de origen.

Esto puede no parecer obvio, pero el mismo cálculo se puede representar como una multiplicación de matrices de la siguiente forma:

En esta formulación, DCT es la matriz DCT, T denota transposición de matriz e IMG es la imagen de origen.

Tenga en cuenta que la complejidad de esta operación es proporcional al tamaño de la imagen de origen. Para administrar imágenes de cualquier tamaño y reducir el trabajo, limitaremos nuestros cálculos a bloques de imagen de 8 por 8 píxeles.

Si bien las imágenes reales tienden a tener una resolución más alta, podemos pensar que están compuestas por muchos bloques independientes de 8x8.

Así es como calculamos la matriz DCT que produce el efecto deseado:

 var dctMatrix: [Float] = Array(repeating: 0.0, count: 8 * 8) for i in 0 ..< 8 { for j in 0 ..< 8 { let a: Float if i == 0 { a = sqrt(1.0 / 8.0) } else { a = sqrt(2.0 / 8.0) } dctMatrix[j * 8 + i] = a * cos((2.0 * Float(j) + 1) * Float(i) * Float.pi / (2.0 * 8)) } }

El valor de dctMatrix es:

 0.35 0.49 0.46 0.42 0.35 0.28 0.19 0.10 0.35 0.42 0.19 -0.10 -0.35 -0.49 -0.46 -0.28 0.35 0.28 -0.19 -0.49 -0.35 0.10 0.46 0.42 0.35 0.10 -0.46 -0.28 0.35 0.42 -0.19 -0.49 0.35 -0.10 -0.46 0.28 0.35 -0.42 -0.19 0.49 0.35 -0.28 -0.19 0.49 -0.35 -0.10 0.46 -0.42 0.35 -0.42 0.19 0.10 -0.35 0.49 -0.46 0.28 0.35 -0.49 0.46 -0.42 0.35 -0.28 0.19 -0.10

Como puede ver, es solo una serie de números. No es necesario volver a calcular los valores de la matriz cada vez que aplicamos la transformación, por lo que podemos mantenerlos en una matriz constante en nuestro código.

Este código realiza la multiplicación de matrices de 8x8:

 func matrixMul8x8(m1: [Float], m2: [Float], result: inout [Float]) { for i in 0 ..< 8 { for j in 0 ..< 8 { var acc: Float = 0.0 for k in 0 ..< 8 { acc += m1[i * 8 + k] * m2[k * 8 + j] } result[i * 8 + j] = acc } } }

Calculamos la DCT 8x8 de la siguiente manera:

 func dct(_ block: [Float]) -> [Float] { var tmpBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) var resultBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) matrixMul8x8(m1: dctMatrixT, m2: block, result: &tmpBlock) matrixMul8x8(m1: tmpBlock, m2: dctMatrix, result: &resultBlock) return resultBlock }

La DCT inversa se puede obtener simplemente intercambiando las matrices DCT regulares y transpuestas:

 func idct(_ block: [Float]) -> [Float] { var tmpBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) var resultBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) matrixMul8x8(m1: dctMatrix, m2: block, result: &tmpBlock) matrixMul8x8(m1: tmpBlock, m2: dctMatrixT, result: &resultBlock) return resultBlock }

El panorama

Ahora, estamos listos para aplicar nuestro conocimiento a imágenes reales. Trabajemos con este:

Imagina que tenemos el código que carga esta imagen como una matriz de números donde cada uno representa el brillo de un píxel en la ubicación correspondiente:

 func loadImage(width: Int, height: Int) -> [Float] { ... }

Suponiendo que la imagen es de 256x256 píxeles, los siguientes valores corresponderían a la esquina superior izquierda:

 -2.00 3.00 -7.00 -6.00 -3.00 -5.00 -13.00 -9.00 -2.00 4.00 -7.00 -6.00 -3.00 -5.00 -13.00 -9.00 -3.00 -1.00 -8.00 -7.00 -6.00 -8.00 -14.00 -12.00 -7.00 -13.00 -9.00 -15.00 -15.00 -12.00 -23.00 -22.00 -18.00 -17.00 -11.00 -15.00 -11.00 -14.00 -20.00 -20.00 -21.00 -19.00 -20.00 -20.00 -18.00 -17.00 -19.00 -19.00 -16.00 -17.00 -20.00 -19.00 -17.00 -21.00 -24.00 -21.00 -19.00 -18.00 -20.00 -22.00 -19.00 -25.00 -20.00 -22.00

Por conveniencia matemática, en lugar de expresar el brillo de los píxeles como un número de 0.0 a 255.0 , restamos 128.0 . En otras palabras, centramos el valor alrededor de 0.0 en lugar de 128.0 .

Luego, aplicamos la función dct a cada bloque de 8x8 de la imagen:

 let values: [Float] = loadImage() // convert RGB to -128.0 ... 128.0 var destinationValues: [Float] = Array(repeating: 0.0, count: values.count) for j in 0 ..< height / 8 { for i in 0 ..< width / 8 { let block = extractBlock(values: values, width: width, x: i * 8, y: j * 8) let resultBlock: [Float] = dct(block) storeBlock(values: &destinationValues, width: width, block: resultBlock, x: i * 8, y: j * 8) } } storeImage(destinationValues) // convert back to RGB

El resultado es esta imagen:

Aunque apenas se reconoce como una foto, algunos patrones (como el sombrero) todavía son visibles. Curiosamente, hay muchos píxeles negros. De hecho, la mayoría de los píxeles son negros. Hagamos zoom en uno de los bloques de 8x8:

Este bloque de 8x8 ilustra de qué se trata la representación en el dominio de la frecuencia. Los valores distintos de cero tienden a agruparse en la esquina superior izquierda del bloque. La probabilidad de un valor grande disminuye significativamente a medida que avanzamos hacia la esquina inferior derecha.

Esto indica que los valores de la parte superior izquierda tienen más importancia para la imagen.

Podemos demostrar esto escribiendo una función de "compresión" que elimine algunos de los valores de la parte inferior derecha al establecerlos en 0.0 :

 func compress(_ block: [Float], level: Int) -> [Float] { var resultBlock: [Float] = block for y in 0 ..< 8 { for x in 0 ..< 8 { if x >= 8 - level || y >= 8 - level { resultBlock[y * 8 + x] = 0.0 } } } return resultBlock }

Después de ajustar nuestro ciclo de procesamiento:

 for j in 0 ..< height / 8 { for i in 0 ..< width / 8 { var block = extractBlock(values: values, width: width, x: i * 8, y: j * 8) block = dct(block) block = compress(block, level: 3) block = idct(block) storeBlock(values: &destinationValues, width: width, block: block, x: i * 8, y: j * 8) } }

Obtenemos esta imagen:

Tómese un momento para considerar lo que ha sucedido. Hemos eliminado 39 de los 64 valores para cada bloque de imagen y aún producimos una imagen que se parece mucho a la original. ¡Esta es una relación de compresión del 60% lograda simplemente multiplicando matrices y descartando datos de forma determinista!

Cuando descartamos el 86% de los coeficientes DCT, sucede esto:

cuantización

Sería un desperdicio increíble almacenar los coeficientes DCT como números de punto flotante, que normalmente requieren 4 bytes de almacenamiento. En cambio, debemos redondearlos al entero más cercano. Para bloques de 8x8, cada valor se puede representar mediante un número entero de 2 bytes.

Repasemos el bloque que examinamos anteriormente. Su representación numérica (redondeada) es:

 209 -296 -49 43 -38 22 -6 1 39 24 -37 11 -4 -3 2 6 -15 16 -17 0 13 -4 0 5 16 4 2 4 -6 4 -3 -5 -11 4 -1 3 1 -3 6 3 6 -2 2 4 -2 -2 -4 -1 -6 1 0 1 -1 0 3 -1 0 0 0 0 -1 -1 -2 1

Como confirmamos visualmente antes, es más probable que ocurran valores más grandes más cerca de la esquina superior izquierda. Sin embargo, no todos los bloques siguen este patrón. Aquí hay otro bloque de nuestra imagen:

Este bloque no se adhiere a la distribución común de valores DCT. Si continuamos descartando ciegamente los valores de la parte inferior derecha, algunas partes de la imagen pueden mostrar más artefactos de compresión. Para evitar eso, debemos decidir qué bloques necesitan más datos que otros.

Una solución simple pero elegante aprovecha la propiedad de agrupamiento que descubrimos anteriormente. Se llama "cuantización". Dividimos nuestros valores DCT por diferentes coeficientes. Usaremos una tabla que contiene un valor para cada coeficiente DCT por conveniencia:

 16.50 11.50 10.50 16.50 24.50 40.50 51.50 61.50 12.50 12.50 14.50 19.50 26.50 58.50 60.50 55.50 14.50 13.50 16.50 24.50 40.50 57.50 69.50 56.50 14.50 17.50 22.50 29.50 51.50 87.50 80.50 62.50 18.50 22.50 37.50 56.50 68.50 109.50 103.50 77.50 24.50 35.50 55.50 64.50 81.50 104.50 113.50 92.50 49.50 64.50 78.50 87.50 103.50 121.50 120.50 101.50 72.50 92.50 95.50 98.50 112.50 100.50 103.50 99.50

Las posiciones más importantes corresponden a los divisores más bajos y viceversa. Realizamos el paso de descuantificación multiplicando los datos cuantificados por los coeficientes de la tabla.

Estas funciones realizan pasos de cuantificación y descuantificación respectivamente:

 func quantize(_ block: [Int], table: [Float]) -> [Int] { var result: [Int] = Array(repeating: 0, count: block.count) for i in 0 ..< block.count { result[i] = Int(round(Float(block[i]) / table[i])) } return result } func dequantize(_ block: [Int], table: [Float]) -> [Float] { var result: [Float] = Array(repeating: 0, count: block.count) for i in 0 ..< block.count { result[i] = Float(block[i]) * table[i] } return result }

Incorporemos la cuantificación y la descuantificación en nuestro código:

 block = dct(block) var iblock = rounded(block) iblock = quantize(iblock, table: testTable) block = dequantize(iblock, table: testTable) block = idct(block)

Así es como se ve el primer bloque cuando se cuantifica:

 13 -26 -5 3 -2 1 0 0 3 2 -3 1 0 0 0 0 -1 1 -1 0 0 0 0 0 1 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 0 0 0 0 0 0 0 0 0 0 0 0

Y este es el segundo bloque:

 -5 18 -10 0 1 1 1 0 0 3 1 -2 0 1 0 0 -4 0 1 0 1 1 0 0 -1 0 0 -2 0 0 0 0 0 1 -1 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 0 0

Notará que hay más valores distintos de cero en el segundo bloque. Así, el paso de cuantificación nos permite almacenar más datos útiles y descartar el resto.

Conclusión y ¿Qué sigue?

Desde las matemáticas básicas, hemos llegado a codificar y decodificar imágenes reales. Vimos visualmente cómo la DCT convierte datos arbitrarios en un conjunto de frecuencias y cómo algunas frecuencias son más importantes que otras.

Una vez que nos familiarizamos con la compresión básica, presentamos el concepto de cuantificación, que reduce aún más los requisitos de almacenamiento.

En la siguiente parte, pasaremos a las imágenes RGB y exploraremos formas de comprimir aún más los datos resultantes.

El código de este artículo se puede encontrar en https://github.com/petertechstories/image-dct