Discussion :

[scarabee10]

Bonsoir,

J'ai quelques soucis de gestion dynamique de la mémoire, mini-purify les a détecté mais je n'arrive pas à les résoudre.

j'ai un programme test, un .h de déclarations des fonctions et un .c où sont définies ces fonctions.

Il s'agit de calculer les transformées en cosinus discrète des coefficients d'une matrice test donnée

Voici mon .h

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#ifndef DCT__H
#define DCT__H
 
typedef struct {
    int** coeff;
    int lignes;
    int colonnes;
} matrice;
 
void initialiser_matrice(matrice m);
int heaviside(int u);
int corps_dct(matrice m,int taille,int x,int y,int u,int v);
int coeff_dct(matrice m, int u, int v);
#endif

Mon .c

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
32
33
34
35
36
37
38
39
40
41
42
 
#include "DCT.h"
#define PI 3.14
 
int heaviside(int u){
	return (u == 0);
}
 
void initialiser_matrice(matrice m){
	m.coeff=0;
	m.lignes=0;
	m.colonnes=0;
}
 
int corps_dct(matrice m,int taille,int i,int j,int u,int v){
	int resultat;
	taille= m.lignes*m.colonnes;
	resultat=(m.coeff[i][j])*cos(((2*i+1)*PI*u)/(2*taille))*cos(((2*j+1)*PI*v)/(2*taille));
 
	return resultat;
}
 
int coeff_dct(matrice m, int u, int v){
	int taille;
	int i, j, temp;
	taille= m.lignes*m.colonnes;
	temp=0;
	/*Facteurs de la double sommation*/
	int a=(2/taille)*(1/sqrt(2));
	int b=heaviside(u)+heaviside(v);
	int c= pow(a,b);
	/*Double sommation*/
	for (i=0; i<=taille-1; i++){
		for(j=0; j<=taille-1; j++){
			temp += corps_dct(m, taille, i, j, u, v);
		}
	}
 
	/*Resultat*/
	temp=temp*c;
	return temp;
}

et mon programme de test

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
32
33
34
35
36
37
38
39
40
41
42
 
int main(){
	matrice t;
	initialiser_matrice(t);
	int i, j;
 
	/*Allocation de mémoire*/
	t.coeff=malloc(8*sizeof(int*));
	for (i=0; i<=8; i++) t.coeff[i]=malloc(8*sizeof(int));
 
	if (t.coeff != NULL){
		t.lignes=8;
		t.colonnes=8;
 
		t.coeff[0][0]=139;
		t.coeff[0][1]=144;
		t.coeff[0][2]=149;
		t.coeff[0][3]=153;
		t.coeff[0][4]=155;
		t.coeff[0][5]=155;
		t.coeff[0][6]=155;
		t.coeff[0][7]=155;
		t.coeff[1][0]=144;
		t.coeff[1][1]=151;
		t.coeff[1][2]=153;
		t.coeff[1][3]=156;
                ...
		t.coeff[7][4]=163;
		t.coeff[7][5]=158;
		t.coeff[7][6]=158;
		t.coeff[7][7]=158;
 
		for (i=0; i<=7; i++){
			for (j=0; j<=7; j++) printf("%d ", coeff_dct(t, i, j));
			printf("\n");
		}
 
		for (i=0; i<=8; i++) free(t.coeff[i]);
		free(t.coeff);
	}
	return EXIT_SUCCESS;
}

Purify me sort que j'ai 371erreurs dont 368 ABR: Array bounds read et 0 fuite mémoire.
les ABR sont localisées dans la définition de la fonction corps_dct et coeff_dct respectivement, au moment d'appeler les valeurs m.coeff[i][j] et au moment d'appeler corps_dct... donc la même erreur en gros.
Et dans mon programme de test, au moment d'appeler coeff_dct.. toujours la même erreur il me semble.

Il doit yavoir un soucis dans mes malloc!
J'attend vos réponses

[jeroman]

1) Dans la fonction initialiser_matrice, tu fais une copie de la matrice et tu initialises donc les valeurs sur elle et non sur celle qui est passée en argument. Il faut passer l'adresse de la matrice :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
void initialiser_matrice(matrice *m)
{
	m->coeff=0;
	m->lignes=0;
	m->colonnes=0;
}
 
(...)
 
initialiser_matrice(&t);

2)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
	t.coeff=malloc(8*sizeof(int*));
	for (i=0; i<=8; i++) t.coeff[i]=malloc(8*sizeof(int));

Tu réserves 8 pointeurs de pointeurs sur int, mais tu alloues ensuite 9 pointeurs sur int et non 8. Ce qui est susceptible de crasher le programme. Il faut utiliser l'opérateur < et non <=.

3) Même problème lors de la libération de mémoire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

for (i=0; i<=8; i++) free(t.coeff[i]);

Il faut modifier l'opérateur <= par <.

4) Je ne sais pas comment se calcule le DCT, mais dans la fonction coeff_dct, il y a un truc qui cloche :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
taille= m.lignes*m.colonnes;
(...)
for (i=0; i<=taille-1; i++){
	for(j=0; j<=taille-1; j++){
		temp += corps_dct(m, taille, i, j, u, v);
	}
}

Dans la fonction corps_dct :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

resultat=(m.coeff[i][j])*cos(((2.0*i+1.0)*PI*u)/(2.0*taille))*cos(((2.0*j+1.0)*PI*v)/(2.0*taille));

vu que i et j ne sont pas compris entre 0 et 7 inclus mais entre 0 et taille (=8*8), ça crashe donc le programme.

[scarabee10]

1) Dans la fonction initialiser_matrice, tu fais une copie de la matrice et tu initialises donc les valeurs sur elle et non sur celle qui est passée en argument. Il faut passer l'adresse de la matrice :
Je m'étais trompé, ce n'est pas un pointeur vers matrice mais bien une variabe de type matrice

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
void initialiser_matrice(matrice m)
{
	m.coeff=0;
	m.lignes=0;
	m.colonnes=0;
}
 
(...)
 
initialiser_matrice(t);

2)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
	t.coeff=malloc(8*sizeof(int*));
	for (i=0; i<=7; i++) t.coeff[i]=malloc(8*sizeof(int));

Tu réserves 8 pointeurs de pointeurs sur int, mais tu alloues ensuite 9 pointeurs sur int et non 8. Ce qui est susceptible de crasher le programme. Il faut utiliser l'opérateur < et non <=.

3) Même problème lors de la libération de mémoire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

for (i=0; i<=7; i++) free(t.coeff[i]);

Il faut modifier l'opérateur <= par <.

4) Je ne sais pas comment se calcule le DCT, mais dans la fonction coeff_dct, il y a un truc qui cloche :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
taille= m.lignes*m.colonnes;
(...)
for (i=0; i<=m.lignes-1; i++){
	for(j=0; j<=m.colonnes-1; j++){
		temp += corps_dct(m, taille, i, j, u, v);
	}
}

Dans la fonction corps_dct :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

resultat=(m.coeff[i][j])*cos(((2.0*i+1.0)*PI*u)/(2.0*taille))*cos(((2.0*j+1.0)*PI*v)/(2.0*taille));

vu que i et j ne sont pas compris entre 0 et 7 inclus mais entre 0 et taille (=8*8), ça crashe donc le programme.

------------------------------
J'ai réglé mes petites erreurs, qui n'en étaient pas unes, puisque j'avais déjà corrigé la version de chez moi, j'ai posté la version non corrigée par mégarde. Donc bref, mes soucis sont toujours les mêmes!
Au sujet du calcul de la fonction coeff_dct... je vous mets un aperçu de la formule mathématique du calculs des coefficients de la DCT.



Merci et bonne soirée,

[jeroman]

J'ai réglé mes petites erreurs, qui n'en étaient pas unes, puisque j'avais déjà corrigé la version de chez moi, j'ai posté la version non corrigée par mégarde. Donc bref, mes soucis sont toujours les mêmes!

Dans ce cas, la première chose à faire est de reposter ton code corrigé, car c'est impossible de savoir ce que tu as modifié ou non et ça va être difficile de t'aiguiller.

Ensuite :

1) D'après la formule que tu as posté, il y a effectivement des problèmes avec ton algorithme car ton calcul n'est pas cohérent avec l'équation.

a) Par exemple, lorsque tu as un calcul du genre :
A*(B) puissance X , cela ne correspond pas à (A*B) puissance X.
Le (B) correspond à ce qui est entre parenthèses au début de l'équation de la DCT :
A=2.0/N
B=1.0/sqrt(2.0)
Or, tu calcules comme si tout était entre parenthèses, comme si on avait (A*B) puissance X :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
int a=(2/taille)*(1/sqrt(2));
int b=heaviside(u)+heaviside(v);
int c= pow(a,b);

b) Par rapport au calcul juste au-dessus, tu utilises taille (qui vaut 64) au lieu de 8.

2) De plus, tu calcules tout en entier, ce qui aggrave la chose. Il faut calculer en double, puis arrondir à l'entier (si j'ai bien compris le système DCT ?) une fois que tu envoies le résultat de l'équation complètement calculée.

3) Lorsque tu accèdes à ta matrice de pixels, il faut faire attention à l'ordre des indices. En C, il y a un ordre précis.
Je suppose que dans ta matrice, il s'agit de la forme : coeff[ligne][colonne] ? Or, dans corps_dct, tu inverses i et j dans coeff.

4) Tu envoie la variable taille dans corps_dct pour la recalculer juste après, ce qui n'est pas cohérent. De plus, pour le calcul, on n'a pas besoin de cette valeur. Tu peux donc supprimer cette variable de la liste des arguments. ^^

5) Ne pas oublier de rajouter le suffixe .0 aux nombres à virgule. Ca évite bien des soucis et des bugs.

6) Pour calculer une DCT, il faut une matrice d'une longueur égale à sa hauteur (si j'ai bien tout compris), ce qui correspond en tout cas à N*N dans l'équation qui est donnée en pièce jointe. Il y a donc moyen d'optimiser le code.

[scarabee10]

Bonjour, j'ai suivi vos instructions.. maintenant j'ai une matrice 8*8 qui s'affiche.. mais c'est pas les bonnes valeurs, je suspect une erreur de manipulation des double et des int..

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
#define PI 3,14159265
 
int heaviside(int u){
	return (u == 0);
}
 
void initialiser_matrice(matrice m){
	m.coeff=0;
	m.hauteur=0;
	m.largeur=0;
}
 
int corps_dct(matrice m, int i,int j,double u,double v){
	int resultat=0, taille;
	double a1=0, a2=0, a3=0, a4=0, b1=0, b2=0, b3=0, b4=0;
        taille= m.hauteur;
 
        a1=(2.0*i+1.0)*PI*u;
	a2=2.0*taille;
	b1=(2.0*j+1.0)*PI*v;
	b2=2.0*taille;
	a3=a1/a2;
	b3=b1/b2;
	a4=cos(a3);
	b4=cos(b3);
	resultat=(m.coeff[j][i])*a4*b4;
 
	return resultat;
}
 
int coeff_dct(matrice m, double u, double v){
	int taille;
	int i, j, temp=0;
	taille= m.hauteur;
	/*Facteurs de la double sommation*/
	double a=2.0/taille;
	double b=1.0/sqrt(2.0);
	double c=heaviside(u)+heaviside(v);
	double d= pow(b,c);
	/*Double sommation*/
	for (i=0; i<=m.hauteur-1; i++){
 	        for(j=0; j<=m.largeur-1; j++){
			temp += corps_dct(m, i, j, u, v);
		}
	}
	temp=a*d*temp;
	return temp;
}

[jeroman]

Salut,

J'ai corrigé ton code. Fais un test pour vérifier si les valeurs générées sont bonnes.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#define PI 3.14159265 /* un point, pas une virgule !  */
 
typedef struct
{
    int** coeff;
    int hauteur;
    int largeur;
} matrice;
 
int heaviside(int u){
	return (u != 0); /* != */
}
 
 /* faut passer l'adresse de la matrice sinon elle est modifiée seulement en local */
void initialiser_matrice(matrice *m){
	m->coeff=NULL;
	m->hauteur=0;
	m->largeur=0;
}
 
/* la fonction doit renvoyer un type double */
double corps_dct(matrice m, int i,int j,double u,double v){
	double resultat=0.0; /* resultat doit être de type double */
    int taille;
	double a1=0.0, a2=0.0, a3=0.0, a4=0.0, b1=0.0, b2=0.0, b3=0.0, b4=0.0;
    taille= m.hauteur;
 
    a1=(2.0*i+1.0)*PI*u;
	a2=2.0*taille;
	b1=(2.0*j+1.0)*PI*v;
	b2=2.0*taille;
	a3=a1/a2;
	b3=b1/b2;
	a4=cos(a3);
	b4=cos(b3);
	resultat=(m.coeff[j][i])*a4*b4;
	return resultat;
}
 
int coeff_dct(matrice m, double u, double v){
	int taille;
	int i, j;
    double temp=0.0; /* temp doit être de type double */
	taille= m.hauteur;
	/*Facteurs de la double sommation*/
	double a=2.0/taille;
	double b=1.0/sqrt(2.0);
	double c=heaviside(u)+heaviside(v);
	double d= pow(b,c);
	/*Double sommation*/
	for (i=0; i<=m.hauteur-1; i++){
 	        for(j=0; j<=m.largeur-1; j++){
			temp += corps_dct(m, i, j, u, v);
		}
	}
	temp=a*d*temp;
	return temp;
}

Corrections :

1) Dans la fonction heaviside, j'avais oublié de te préciser qu'il y avait aussi un problème. Il faut en fait utiliser l'opérateur != et non ==.
Si la valeur est différente de zéro, la condition est donc vraie et donc la fonction renvoie 1.
Si la valeur est égale à zéro, elle n'est donc pas différente de zéro, le résultat du test est donc faux, ce qui renvoie 0.

2) Dans les fonctions corps_dct et coeff_dct, tu travaillais toujours avec le type entier. Il faut utiliser des double. Par contre, dans la fonction coeff_dct, seul le résultat final doit être renvoyé en entier (si j'ai bien compris le principe de la DCT... (?)).

3) Dans la fonction initialiser_matrice, tu n'avais toujours pas corrigé le type de l'argument... même si le problème des données fausses ne vient pas de là.
En passant l'argument par copie, tu ne modifies que l'objet local. Une fois qu'on quitte la fonction, l'objet est perdu. Pour modifier l'objet envoyé à la fonction, il faut lui passer son adresse et travailler dessus.

[diogene]

Pour une fonction qui s'appelle "heaviside", on attend plutôt :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
int heaviside(int u){
	return (u >= 0); 
}

[scarabee10]

Pour une fonction qui s'appelle "heaviside", on attend plutôt :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
int heaviside(int u){
	return (u >= 0); 
}

Il ya eu rectification de mon sujet delta(x) devant être égale à 1 uniquement si x=0 et nulle sinon, alors si on est encore dans le cadre de heaviside ou pas, aucune idée. L'essentiel c'est que mon code corresponde.

@Jeroman:
J'ai essayé d'optimiser mon code.. en ajoutant une fonction afficher_dct, au lieu de la coder dans mon programme test, je n'ai plus qu'à l'appeler, et une fonction dct qui renvoie la matrice modifiée en sortie, j'en aurais besoin pour les prochaines étapes de compression (codage de Huffman entre autres).

J'ai également ajouté un module quantification, qui se charge de la division entière des coeff de la matrice en sortie de la DCT par un facteur de quantification (histoire de perte de qualité de l'image ...). Ca marche, les résultats de la quantification sont bons, relativement, puisque les valeurs renvoyées par la DCT sont toujours fausses.. mais chose bizarre, à plus ou moins 1 ou -1 et ya même des valeurs corrects. J'ai épluché les fonctions qui calculent les coeff, je ne vois vraiment pas d'où peut venir l'erreur.

J'ai ajouté deux fonctions de gestion dynamique de la mémoire, allouer_matrice et liberer_matrice, pour rendre mon code plus lisible. Seulement dans ma fonction: Matrice dct(matrice m); j'alloue une matrice result, et je ne sais pas comment la libérer correctement. Si je le fais avant le return ça bug et après ça ne compte pas. Du coup j'ai des fuits mémoires d'après Purify.. mais ce n'est pas de là d'où viennent les mauvaises valeurs.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
double corps_dct(matrice m, int i,int j,double u,double v){
	double resultat=0.0;
	double a1=0.0, a2=0.0, a3=0.0, a4=0.0, b1=0.0, b2=0.0, b3=0.0, b4=0.0;
 
	a1=(2.0*i+1.0)*PI*u;
	a2=2.0*m.hauteur;    /** Hauteur==Largeur **/
	b1=(2.0*j+1.0)*PI*v;
	b2=2.0*m.hauteur;   
	a3=(a1)/(a2);
	b3=(b1)/(b2);
	a4=cos(a3);
	b4=cos(b3);
	resultat=(m.coeff[i][j])*a4*b4;
 
	return resultat;
}
 
int coeff_dct(matrice m, double u, double v){
	int i, j;
	double temp=0.0;
	/*Facteurs de la double sommation*/
	double a=2.0/m.hauteur;  /** Hauteur==Largeur**/
	double b=1.0/sqrt(2.0);
	double c=heaviside(u)+heaviside(v);
	double d= pow(b,c);
        /*Double sommation*/
	for (i=0; i<m.hauteur; i++){
		for(j=0; j<m.largeur; j++){
			temp += corps_dct(m, i, j, u, v);
		}
	}
	temp=a*d*temp;
	return temp;
}
matrice dct(matrice m){
	matrice result;
	int i, j;
	initialiser_matrice(&result);
	result=allouer_matrice(m.hauteur, m.largeur);
	for (i=0; i<=m.hauteur-1; i++){
		for (j=0; j<m.largeur; j++) result.coeff[i][j]= coeff_dct(m, i, j);
	}
	return result;
}
 
void afficher_dct(matrice m){
	int i, j;
	for (i=0; i<m.hauteur; i++){
		for (j=0; j<m.largeur; j++) printf("%4d ", coeff_dct(m, i, j));
		printf("\n");
	}
}

Merci...

[jeroman]

Salut !

Bon, j'ai finalement trouvé le problème
En comparant l'équation donnée en pièce jointe avec celle trouvée sur wikipédia, j'ai vu qu'il y a une grosse erreur.

En effet, dans la pièce jointe, il est écrit :
F(u,v) = 2/N * (1/racine(2)) puissance (delta(u)+delta(v)) * ...
avec : delta(x) -> {
0 si x=0
1 si x>0 }

Or, sur Wikipedia, cette partie est formulée différemment, bien qu'identique au final (on va garder les mêmes variables pour pas s'embrouiller) :

F(u,v) = 2/N * C(u)* C(v) * ...
avec : C(x) -> {
1/racine(2) si x=0
1 si x>0
}

Admettons que u et v valent 0.

Avec la version pièce jointe, cela nous donne donc :
2/N * (1/racine(2)) puissance 0 = 2/N

Mais avec la version Wiki, cela donne :
2/N * 1/racine(2) * 1/racine(2)

Admettons maintenant que u et v valent 1.

Avec la version pièce jointe, cela nous donne donc :
2/N * (1/racine(2)) puissance 2 = 2/N * 1/racine(2) * 1/racine(2)

Mais avec la version Wiki, cela donne :
2/N

En clair, la formule de la pièce jointe présente une erreur.

Le "delta" est donc faux. Ce n'est donc pas :

delta(x) -> {
0 si x=0
1 si x>0 }

mais :

delta(x) -> {
1 si x=0
0 si x>0 }

Dans la fonction heaviside, il faut donc bien utiliser l'opérateur d'égalité.

Après, l'histoire du +1 ou -1 est lié à l'arrondi.
Dans coeff_dct, je te propose de virer le return à la fin en le remplaçant par :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
    if (temp>0.0) return (int)(temp+0.5);
	else return (int)(temp-0.5);

J'ai essayé chez moi, la matrice DCT générée correspond bien à celle de Wiki.

[scarabee10]

Super, ça marche.
Merci pour votre patience.

a+