Écrivons un codec vidéo - Partie 3 : Images fixes

Dans les parties précédentes de cette série, nous avons découvert la transformée en cosinus discrète, de sa définition mathématique à sa mise en œuvre dans des exemples réels. De plus, nous avons vu comment la capacité de DCT à représenter les données dans le domaine fréquentiel peut permettre une compression des données avec perte.

Maintenant, nous passons à l'étape suivante. Nous allons enfin tracer la ligne reliant ces tableaux abstraits de nombres dont nous avons discuté et les images réelles qu'ils peuvent représenter.

À la fin de cet article, nous aurons redécouvert environ 80 % du processus réel de compression d'image JPEG.

La matrice

Dans l'article précédent, nous avons présenté le 2D-DCT. Maintenant, regardons une version légèrement ajustée de cette formule :

Les variables u et v représentent le décalage horizontal et vertical de la valeur dans le tableau 2D codé DCT. La fonction α(x) vaut 1/sqrt(2) si x == 0 et 1 sinon. Enfin, x et y représentent la position du pixel dans l'image source.

Cela peut ne pas sembler évident, mais le même calcul peut être représenté comme une multiplication matricielle sous la forme suivante :

Dans cette formulation, DCT est la matrice DCT, T désigne la transposition de la matrice et IMG est l'image source.

Gardez à l'esprit que la complexité de cette opération est proportionnelle à la taille de l'image source. Pour gérer des images de toute taille et réduire le travail, nous limiterons nos calculs à des blocs d'images de 8 x 8 pixels.

Alors que les images réelles ont tendance à avoir une résolution plus élevée, nous pouvons les considérer comme étant composées de nombreux blocs 8x8 indépendants.

Voici comment nous calculons la matrice DCT qui produit l'effet désiré :

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

La valeur de dctMatrix est :

 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

Comme vous le voyez, c'est juste un tableau de nombres. Il n'est pas nécessaire de recalculer les valeurs de la matrice chaque fois que nous appliquons la transformation, nous pouvons donc les conserver dans un tableau constant dans notre code.

Ce code effectue une multiplication matricielle 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 } } }

Nous calculons le DCT 8x8 comme suit :

 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 }

Le DCT inverse peut être obtenu simplement en échangeant les matrices DCT régulières et transposées :

 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 }

La grande image

Maintenant, nous sommes prêts à appliquer nos connaissances à des images réelles. Travaillons avec celui-ci :

Imaginez que nous ayons le code qui charge cette image sous la forme d'un tableau de nombres où chacun représente la luminosité d'un pixel à l'emplacement correspondant :

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

En supposant que l'image mesure 256 x 256 pixels, les valeurs suivantes correspondraient au coin supérieur gauche :

 -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

Pour des raisons mathématiques, au lieu d'exprimer la luminosité des pixels sous la forme d'un nombre compris entre 0.0 et 255.0 , nous soustrayons 128.0 . En d'autres termes, nous centrons la valeur autour de 0.0 plutôt que de 128.0 .

Ensuite, nous appliquons la fonction dct à chaque bloc 8x8 de l'image :

 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

Le résultat est cette image :

Même s'il est à peine reconnaissable en photo, certains motifs (comme le chapeau) sont encore visibles. Fait intéressant, il y a beaucoup de pixels noirs. En fait, la plupart des pixels sont noirs. Zoomons sur l'un des blocs 8x8 :

Ce bloc 8x8 illustre ce qu'est la représentation dans le domaine fréquentiel. Les valeurs non nulles ont tendance à se regrouper dans le coin supérieur gauche du bloc. La probabilité d'une valeur élevée diminue considérablement à mesure que nous nous déplaçons vers le coin inférieur droit.

Cela indique que les valeurs en haut à gauche ont plus d'importance pour l'image.

Nous pouvons le démontrer en écrivant une fonction de "compression" qui élimine certaines des valeurs en bas à droite en les mettant à 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 }

Après avoir ajusté notre boucle de traitement :

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

On obtient cette image :

Prenez un moment pour réfléchir à ce qui s'est passé. Nous avons éliminé 39 des 64 valeurs pour chaque bloc d'image et avons toujours produit une image qui ressemble beaucoup à l'original. Il s'agit d'un taux de compression de 60 % obtenu simplement en multipliant les matrices et en supprimant les données de manière déterministe !

Lorsque nous éliminons 86 % des coefficients DCT, cela se produit :

Quantification

Il serait extrêmement inutile de stocker les coefficients DCT sous forme de nombres à virgule flottante, qui nécessitent généralement 4 octets de stockage. Au lieu de cela, nous devrions les arrondir à l'entier le plus proche. Pour les blocs 8x8, chaque valeur peut être représentée par un nombre entier de 2 octets.

Reprenons le bloc que nous avons examiné plus tôt. Sa représentation numérique (arrondie) est :

 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

Comme nous l'avons confirmé visuellement auparavant, les valeurs plus élevées sont plus susceptibles de se produire plus près du coin supérieur gauche. Cependant, tous les blocs ne suivent pas ce modèle. Voici un autre bloc de notre image :

Ce bloc n'adhère pas à la distribution commune des valeurs DCT. Si nous continuons à ignorer aveuglément les valeurs en bas à droite, certaines parties de l'image peuvent afficher davantage d'artefacts de compression. Pour éviter cela, nous devons décider quels blocs ont besoin de plus de données que d'autres.

Une solution simple mais élégante capitalise sur la propriété de regroupement que nous avons découverte précédemment. C'est ce qu'on appelle la "quantification". Nous divisons nos valeurs DCT par différents coefficients. Nous utiliserons un tableau contenant une valeur pour chaque coefficient DCT pour plus de commodité :

 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

Les positions les plus importantes correspondent aux diviseurs inférieurs, et vice versa. Nous effectuons l'étape de déquantification en multipliant les données quantifiées par les coefficients du tableau.

Ces fonctions effectuent respectivement les étapes de quantification et déquantification :

 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 }

Incorporons la quantification et la déquantification dans notre code :

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

Voici à quoi ressemble le premier bloc lorsqu'il est quantifié :

 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

Et voici le deuxième bloc :

 -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

Vous remarquerez qu'il y a plus de valeurs non nulles dans le deuxième bloc. Ainsi, l'étape de quantification nous permet de stocker plus de données utiles et d'éliminer le reste.

Conclusion et quelle est la suite ?

Des mathématiques de base, nous avons fait notre chemin vers l'encodage et le décodage d'images réelles. Nous avons vu visuellement comment le DCT convertit des données arbitraires en un ensemble de fréquences et comment certaines fréquences sont plus importantes que d'autres.

Après nous être familiarisés avec la compression de base, nous avons introduit le concept de quantification, qui réduit encore les besoins de stockage.

Dans la partie suivante, nous passerons aux images RVB et explorerons les moyens de compresser encore plus les données résultantes.

Le code de cet article se trouve sur https://github.com/petertechstories/image-dct