Vamos escrever um codec de vídeo - Parte 3: Imagens estáticas

Nas partes anteriores desta série, aprendemos sobre a Transformada Discreta do Cosseno, desde sua definição matemática até sua implementação em exemplos reais. Além disso, vimos como a capacidade do DCT de representar dados no domínio da frequência pode permitir a compactação de dados com perdas.

Agora, estamos dando o próximo passo. Por fim, traçaremos a linha conectando essas matrizes abstratas de números que discutimos e as imagens reais que elas podem representar.

Ao final deste artigo, teremos redescoberto aproximadamente 80% do processo real de compactação de imagens JPEG.

O Matrix

No artigo anterior, apresentamos o 2D-DCT. Agora, vamos ver uma versão ligeiramente ajustada dessa fórmula:

As variáveis u representam o deslocamento horizontal e vertical do valor na matriz 2D codificada v DCT. A função α(x) é igual a 1/sqrt(2) se x == 0 e 1 caso contrário. Por fim, x e y representam a posição do pixel na imagem de origem.

Isso pode não parecer óbvio, mas o mesmo cálculo pode ser representado como uma multiplicação de matrizes na seguinte forma:

Nesta formulação, DCT é a matriz DCT, T denota a transposição da matriz e IMG é a imagem de origem.

Tenha em mente que a complexidade desta operação é proporcional ao tamanho da imagem de origem. Para gerenciar imagens de qualquer tamanho e reduzir o trabalho, limitaremos nossos cálculos a blocos de imagem de 8 por 8 pixels.

Enquanto as imagens reais tendem a ter uma resolução maior, podemos pensar nelas como sendo compostas por muitos blocos 8x8 independentes.

Veja como calculamos a matriz DCT que produz o efeito desejado:

 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)) } }

O valor de dctMatrix é:

 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 você vê, é apenas uma matriz de números. Não há necessidade de recalcular os valores da matriz toda vez que aplicamos a transformação, para que possamos mantê-los em um array constante em nosso código.

Este código executa a multiplicação de matrizes 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 o DCT 8x8 da seguinte forma:

 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 }

O DCT inverso pode ser obtido simplesmente trocando as matrizes DCT regulares e transpostas:

 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 }

A grande imagem

Agora, estamos prontos para aplicar nosso conhecimento em imagens reais. Vamos trabalhar com este:

Imagine que temos o código que carrega essa imagem como um array de números onde cada um representa o brilho de um pixel no local correspondente:

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

Supondo que a imagem tenha 256x256 pixels, os seguintes valores corresponderiam ao canto superior esquerdo:

 -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 conveniência matemática, em vez de expressar o brilho do pixel como um número de 0.0 a 255.0 , subtraímos 128.0 . Em outras palavras, centralizamos o valor em torno de 0.0 em vez de 128.0 .

Em seguida, aplicamos a função dct a cada bloco 8x8 da imagem:

 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

O resultado é esta imagem:

Embora seja quase irreconhecível como uma foto, alguns padrões (como o chapéu) ainda são visíveis. Curiosamente, existem muitos pixels pretos. Na verdade, a maioria dos pixels são pretos. Vamos ampliar um dos blocos 8x8:

Este bloco 8x8 ilustra o que é a representação no domínio da frequência. Valores diferentes de zero tendem a se agrupar no canto superior esquerdo do bloco. A probabilidade de um valor grande diminui significativamente à medida que avançamos para o canto inferior direito.

Isso indica que os valores do canto superior esquerdo carregam mais importância para a imagem.

Podemos demonstrar isso escrevendo uma função de "compressão" que elimina alguns dos valores do canto inferior direito, definindo-os como 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 }

Depois de ajustar nosso loop de processamento:

 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) } }

Obtemos esta imagem:

Reserve um momento para considerar o que aconteceu. Eliminamos 39 dos 64 valores para cada bloco de imagem e ainda produzimos uma imagem muito parecida com a original. Esta é uma taxa de compressão de 60% alcançada apenas multiplicando matrizes e descartando dados de forma determinística!

Quando descartamos 86% dos coeficientes DCT, isso acontece:

Quantização

Seria um desperdício incrível armazenar os coeficientes DCT como números de ponto flutuante, que geralmente requerem 4 bytes de armazenamento. Em vez disso, devemos arredondá-los para o inteiro mais próximo. Para blocos de 8x8, cada valor pode ser representado por um número inteiro de 2 bytes.

Vamos revisitar o bloco que examinamos anteriormente. Sua representação numérica (arredondada) é:

 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, é mais provável que valores maiores ocorram mais perto do canto superior esquerdo. No entanto, nem todo bloco segue esse padrão. Aqui está outro bloco da nossa imagem:

Este bloco não adere à distribuição comum de valores DCT. Se continuarmos a descartar cegamente os valores do canto inferior direito, algumas partes da imagem podem exibir mais artefatos de compactação. Para evitar isso, precisamos decidir quais blocos precisam de mais dados do que outros.

Uma solução simples, porém elegante, aproveita a propriedade de agrupamento que descobrimos anteriormente. Chama-se "quantização". Dividimos nossos valores DCT por diferentes coeficientes. Usaremos uma tabela que contém um valor para cada coeficiente DCT por conveniência:

 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

As posições mais importantes correspondem aos divisores mais baixos e vice-versa. Realizamos a etapa de desquantização multiplicando os dados quantizados pelos coeficientes da tabela.

Essas funções executam as etapas de quantização e desquantização, 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 }

Vamos incorporar quantização e desquantização em nosso código:

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

É assim que o primeiro bloco fica quando quantizado:

 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

E este é o segundo bloco:

 -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

Você notará que há mais valores diferentes de zero no segundo bloco. Assim, a etapa de quantização nos permite armazenar mais dados úteis e descartar o restante.

Conclusão e o que vem a seguir?

Da matemática básica, chegamos à codificação e decodificação de imagens reais. Vimos visualmente como o DCT converte dados arbitrários em um conjunto de frequências e como algumas frequências são mais importantes que outras.

Depois que nos familiarizamos com a compactação básica, introduzimos o conceito de quantização, que reduz ainda mais os requisitos de armazenamento.

Na próxima parte, passaremos para imagens RGB e exploraremos maneiras de compactar ainda mais os dados resultantes.

O código deste artigo pode ser encontrado em https://github.com/petertechstories/image-dct