Discussion :

[biloubi]

Bonjour,

Pour un projet, je dois écrire un algorithme de réduction des niveaux de gris dans une image par programmation dynamique à l'aide d'un histogramme. Le problème est que je sèche pas mal .

J'ai déjà essayé une première solution (peut-on vraiment la qualifier de programmation dynamique ?), qui consiste à prendre les k premières valeurs de l'histogramme (k étant le nombre de niveaux à fournir) comme niveaux, le dernier étant constitué de tous les niveaux restants, de calculer l'erreur, de la stocker dans un tableau, puis de faire avancer le maximum d'une unité, de considérer le dernier niveau comme tous les niveaux restants de l'histogramme et de diviser ce que l'on a déjà considéré en minimisant l'erreur au sens des moindres carrés. Le problème, ici, c'est qu'il faut une formule de récurrence pour l'erreur (sans quoi cette approche n'est pas vraiment de la DP ).

Voici le code (en C) déjà écrit (je ne mets pas le calcul d'histogramme) :

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
// calcule le niveau de gris minimisant l'erreur sur l'intervalle [i,j] de l'histogramme 
uint16_t MinEGrayLevel ( unsigned* histo , uint16_t i, uint16_t j) {
	if (i>j){
		uint16_t temp = i;
		i=j;
		j=temp;
	}
 
	uint16_t sumNum = 0; // sum[i] (h[i]*i)
	uint16_t sumDenom = 0; // sum[i] (h[i])
	for (int k=i;k<=j;k++){
 
 
		sumNum = sumNum + (histo[k]*k);
		sumDenm = sumDenm + (histo[k]);
	}	
	uint16_t minLevelGray = (sumNum / sumDenm) + 0.5;
	return minLevelGray;
}	
 
// la fonction renvoie l'erreur minimale et la stocke au besoin
int minimizeErrorAtRight(const size_t*tab, unsigned tab_length, int j, int k, int ** Memo, int** position){
	if (Memo[j,k]!= -1){
		return Memo[j,k];
	}
 
	if (k=1){
		position[j,k] = MinGrayLevel (tab, 0, j);
		int error = computeError(tab, 0, j, position[j,k]);
		Memo [j,k] = error;
		return error;
	}
 
	if (j=0){
		return 0;
	}
 
	int error = minimizeErrorAtRight (tab, tab_length, j-1, k-1, Memo, position);
 
 
}

Pourriez-vous me débloquer ?

Merci d'avance !

[pseudocode]

J'ai déjà essayé une première solution (peut-on vraiment la qualifier de programmation dynamique ?), qui consiste à prendre les k premières valeurs de l'histogramme (k étant le nombre de niveaux à fournir) comme niveaux, le dernier étant constitué de tous les niveaux restants, de calculer l'erreur, de la stocker dans un tableau, puis de faire avancer le maximum d'une unité, de considérer le dernier niveau comme tous les niveaux restants de l'histogramme et de diviser ce que l'on a déjà considéré en minimisant l'erreur au sens des moindres carrés. Le problème, ici, c'est qu'il faut une formule de récurrence pour l'erreur (sans quoi cette approche n'est pas vraiment de la DP ).

Hum... il ne me semble pas évident de "rediviser" successivement le début de l'histogramme à chaque étape, tout en minimisant l'erreur quadratique moyenne.

Vu l'énoncé de ton problème, je te suggère de regarder l'algorithme de Lloyd Max.

[biloubi]

OK, , je me documente !

[biloubi]

Cet algorithme pourrait fonctionner, mais il utilise des propriétés géométriques de l'image. Or, il faut minimiser l'erreur des moindres carrés à partir de l'histogramme de l'image.

[pseudocode]

Cet algorithme pourrait fonctionner, mais il utilise des propriétés géométriques de l'image. Or, il faut minimiser l'erreur des moindres carrés à partir de l'histogramme de l'image.

Des propriétés géométriques ? ?

Tu es sûr d'avoir regardé l'algorithme de Lloyd ?

[biloubi]

Je me suis mal expliqué. L'algorithme de Lloyd Max utilise l'image tandis nous, nous devons utiliser l'histogramme correspondant à cette image.

[pseudocode]

Je me suis mal expliqué. L'algorithme de Lloyd Max utilise l'image tandis nous, nous devons utiliser l'histogramme correspondant à cette image.

?

L'algorithme de Lloyd Max utilise justement l'histogramme de l'image, il minimise justement l'erreur quadratique moyenne, et il s'implémente justement par de la programmation dynamique...

Je ne sais pas d'où vient l'énoncé de ton projet, mais je parierais que son auteur avait en tête cet algorithme.

[romit]

J'ai le même problème, sans doute le même projet.

L'algorithme de Lloyd Max ne m'a pas aidé malheureusement.

Là où je bloque dans le problème c'est également sur l'équation de récurrence.

Nous disposons d'un histogramme des valeurs des pixels de l'image.
Nous avons écrit une fonction permettant de calculer pour un sous intervalle de l'histogramme la valeur qui les remplacerait toutes en minimisant l'erreur.

Et nous sommes donc capables pour un sous intervalle de l'histogramme de récupérer l'erreur minimale qu'on aurait en remplaçant toutes les couleurs de ce sous-intervalle par une seule valeur.

Là où je bloque c'est l'étape suivante, on doit trouver l'équation de récurrence qui permet d'avoir pour un nombre de couleurs de bases et le nouveau nombre de couleurs, l'erreur minimale (Par récurrence, donc).

Càd: Trouver ErreurMinimale(h, j) (j étant le nombre de couleurs après la réduction des couleurs allant de 0 à h-1 dans l'histogramme). Et ce par récurrence.

Je bloque réellement là dessus, impossible pour moi de trouver cette équation de récurrence

[pseudocode]

Là où je bloque c'est l'étape suivante, on doit trouver l'équation de récurrence qui permet d'avoir pour un nombre de couleurs de bases et le nouveau nombre de couleurs, l'erreur minimale (Par récurrence, donc).

Càd: Trouver ErreurMinimale(h, j) (j étant le nombre de couleurs après la réduction des couleurs allant de 0 à h-1 dans l'histogramme). Et ce par récurrence.

ErreurMinimale(h, j) = ErreurMinimale(h0) + ErreurMinimale(h1) + ... + ErreurMinimale(hj-1)

avec hi = histogramme dans le i-ème sous intervalle [Ti, Ti+1].

Le but étant de trouver les bornes des intervalles T0=0, T1, T2, ..., Tj=255 qui séparent l'histogramme en "j" bandes.

Ceci étant exactement ce que fait l'algorithme de Lloyd Max, que vous semblez ne pas aimer.

[romit]

Merci beaucoup, c'est déjà plus clair.

Mais je ne comprends pas bien ça:

ErreurMinimale(h1)

h et j sont censées être deux variables distinces et ErreurMinimale une "fonction" à deux paramètres. Fonction qui dépend du nombre de couleurs de l'image de base et le nouveau nombre de couleur après la réduction

[pseudocode]

Le plus simple, c'est de repartir de l'erreur quadratique moyenne sur un intervalle. C'est la moyenne des "erreurs" au carré.

EQM(intervalle k) = E [ (Pi - Rk)² ] = Somme{ (Pi - Rk)² } / NmbDePixelsDansL'intervalle

avec Pi les valeurs des pixels qui sont dans le k-ième intervalle
et Rk la valeur de remplacement de l'intervalle.

On peut connaitre le nombre (et la valeur) des pixels qui sont dans le k-ième intervalle depuis l'histogramme. Il y a exactement histo[i] pixels qui ont la valeur "i".

EQM(intervalle k) 
= Somme{ Histo[i]*(i-Rk)² } / NmbDePixelsDansL'intervalle
= Somme{ Histo[i]*(i-Rk)² } / Somme{ Histo[i] }

pour i variant entre les 2 bornes du k-ième intervalle.


Si on réunit deux intervalles

EQM(intervalles 1 et 2) 
= ( Somme{ Histo[i]*(i-R1)² } + Somme{ Histo[j]*(j-R2)² } ) / NmbDePixelsDansLesDeuxIntervalles
= ( Somme{ Histo[i]*(i-R1)² } + Somme{ Histo[j]*(j-R2)² } ) / (Somme{ Histo[i] } + Somme{ Histo[j] })

pour i variant entre les 2 bornes du 1er intervalle
et j variant entre les 2 bornes du 2nd intervalle.


On peut alors réécrire cette formule pour faire apparaitre l'EQM de chaque intervalle.

EQM(intervalles 1 et 2)  = w1*EQM(intervalles 1)  + w2*EQM(intervalles 2)

avec w1 = Somme{ Histo[i] }/(Somme{ Histo[i] } + Somme{ Histo[j] })
et w2 = Somme{ Histo[j] }/(Somme{ Histo[i] } + Somme{ Histo[j] })

c'est a dire des coefficients de pondération sur la quantité relative de pixels dans chaque intervalle.

[romit]

Désolé pour le retard, j'avais complètement oublié de te remercier. Je ne suis pas parvenu à faire l'algorithme tel que demandé mais j'ai réussi à faire "ma propre variante".

Donc voilà, merci pour les conseils

[Mirayrak]

Bonjour,

Je sais que ce post date vraiment d'il y a longtemps mais par chance peut être, est-ce que quelqu'un aurait des documentations précis sur le Lloyd? ou sinon si cela ne vous dérange pas de partager votre code final( si bien sure vous l'avez toujours comme ça remonte il y a longtemps) car j'ai un projet plus ou mois similaire au votre et j'aimerai m'en inspirer pour mieux comprendre au niveau codage. Je dois justement faire une compression d'image par programmation dynamique et par approche gloutonne et en analysant théoriquement, mon raisonnement me semble concret mais j'aimerais tout de même le comparer au votre si possible. Merci d'avance!