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) :
Pourriez-vous me débloquer ?
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); }
Merci d'avance !
Partager