Le calcul de la DCT du tutoriel est-il bon ?

Bonjour à tous,

J’implémente la compression JPEG expliquée dans le tutoriel d’@Antho : https://zestedesavoir.com/articles/1532/la-compression-jpeg/.

L’auteur donne la définition d’une fréquence :

$DCT_{u,v}= \frac 14 \sum_{x=0}^{7}\sum_{y=0}^{7}Pixels_{x,y} \cos{\left[ \dfrac{(2x+1)u\pi}{16} \right]} \cos{\left[ \dfrac{(2y+1)v\pi} {16} \right]}$

Je cherche à utiliser cette définition pour convertir mes valeurs de luminance en fréquences, et c’est là que j’ai un problème.

Quel est le résultat actuel de mon implémentation ?

Quel est le problème ?

Les valeurs que j’ai calculées et qu’on peut voir dans la matrice "DCTed luminance matrix" ne sont pas les mêmes que celles fournies par Anto59290.

Valeurs que j’aurais dû trouver

Note : Les valeurs de luminance que j’utilise sont les mêmes que celles employées par l’auteur. Vous pouvez donc les trouver dans mon screenshot (cf. "Luminance matrix").

Le tutoriel indique ces valeurs de luminances converties en fréquences (méthode DCT) :

Code source d’implémentation (C++) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

for (int u = 0; u < 8; u++) {
    for (int v = 0; v < 8; v++) {

        float b = 0.0f;
        for (int x = 0; x < 8; x++) {

            float a = 0.0f;
            for (int y = 0; y < 8; y++) {
                a += luminance_matrix[x][y] * cos(((2 * x + 1) * u * 3.141) / 16) * cos(((2 * y + 1) * v * 3.141) / 16);
            }
            b += a;
        }

        dct_matrix[u][v] = (float)1 / 4 * b;
    }
}

Voilà voilà… est-ce moi qui ai mal compris comment implémenter cette conversion ou le problème vient-il de la formule écrite par Antho ?

Edit (important) : sujet résolu

La formule du tuto était incorrecte (formule correcte, cf. Wikipédia : )

Implémentation (elle fonctionne)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

for (int u = 0; u < 8; u++) {
    for (int v = 0; v < 8; v++) {

        float b = 0.0f;
        for (int x = 0; x < 8; x++) {

            float a = 0.0f;
            for (int y = 0; y < 8; y++) {
                a += luminance_matrix[x][y] * cos(((2 * x + 1) * u * 3.1415926536) / 16) * cos(((2 * y + 1) * v * 3.1415926536) / 16);
            }
            b += a;
        }

        if (u == 0) {
            if (v == 0) {
                dct_matrix[u][v] = (float)1 / 4 * 0.7071067812 * 0.7071067812 * b;
            }
            else if (v > 0) {
                dct_matrix[u][v] = (float)1 / 4 * 0.7071067812 * b;
            }
        }
        else if (u > 0) {
            if (v == 0) {
                dct_matrix[u][v] = (float)1 / 4 * 0.7071067812 * b;
            }
            else if (v > 0) {
                dct_matrix[u][v] = (float)1 / 4 * b;
            }
        }
    }
}

Résultats (corrects)

Salut ! Alors j’ai peut-être mal compris le sujet, mais : où est-ce que la somme (celle de la formule) apparaît dans ton code ?

Salut,

Je passe en vitesse, il n’est pas impossible qu’il y ai une erreur dans le tutoriel, je vais jeter un coup d’oeil pour dérouler le calcul. Par contre en lisant ton message j’ai l’impression que tu as mal assimilé certaines notions, mes confrères du forum math serait plus à même de répondre à tes interrogations, je note cependant:

DCT(139)=158

Ceci n’a pas de sens pour la DCT dans le JPEG. Sauf erreur de ma part (les maths n’étant pas mon domaine), la DCT est une fonction (linéaire ?) de R^N dans R^N. Donc on ne peut écrire DCT(139) que si N=1, ce qui n’est jamais notre cas (en compression) où N=8.

Ensuite, il n’est pas possible (du point de vue compression) que le premier coefficient de ta matrice de fréquence soit nul (le coefficient DC). Cela voudrait dire que la fréquence continue de ton signal est nulle, ce qui n’arrive jamais avec une image naturelle. Il me semble que le seul cas mathématique pour que ça arrive serait de donner un matrice de 8x8 remplie de zéros ?

Enfin concernant ton code, je ne suis vraiment pas très calé en C++, mais je suis quasiment sur qu’il est faux. Comme noté par @luxera il me semble que tu écrases ton résultat à chaque tour de boucle, c’est comme si tu ne faisait pas de somme, non ?

Pour finir mon pseudo c’est Anto59290, pas Antho, merci

Anto59290

Bonjour Anto59290,

Quand je disais $DCT(139)=158$ c’était sous-entendu $DCT_{0,0} = 158$, car la valeur $139$ se situe bien en coordonnées $(0,0)$

Sinon effectivement vous avez tous deux raison, j’avais oublié de faire les deux sommes… Du coup j’ai corrigé ça, mais le résultat reste toujours faux. Voici le nouveau code (j’ai également mis à jour l’OP) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

for (int u = 0; u < 8; u++) {
    for (int v = 0; v < 8; v++) {

        float b = 0.0f;
        for (int x = 0; x < 8; x++) {

            float a = 0.0f;
            for (int y = 0; y < 8; y++) {
                a += luminance_matrix[x][y] * cos(((2 * x + 1) * u * 3.141) / 16) * cos(((2 * y + 1) * v * 3.141) / 16);
            }
            b += a;
        }

        dct_matrix[u][v] = (float)1 / 4 * b;
    }
}

Si jamais vous trouvez ce qui ne va pas,

Merci encore !

Edit : j’ai de nouveau mis à jour l’OP, pour le rendre plus clair

Il y a très vraisemblablement un "divisé par 2" que j’ai oublié ou qui manque au tutoriel

Edit : en écrivant dct_matrix[u][v] = (float) 1/8*b; à la place de dct_matrix[u][v] = (float) 1/4*b; (soit en "divisant par 2"), j’obtiens bien le $1260$ mais les autres valeurs sont fausses, cf. l’image qui suit.

Trouvé !

Il manque bien quelque chose à ta formule, @Anto59290. Je me suis permis de surligner ça (équation Wikipédia) :

Mon implémentation, qui fonctionne, est disponible dans l’OP