Le principe de maximum d'entropie [Résolu]

[math_infomatique]

Bonjour,

J'aimerai bien comprendre davantage le principe de la méthode maximum d entropie.
D'après une petite recherche sur google j'ai lu plusieurs articles, mais toujours j'ai pas bien compris et j'ai capté plusieurs informations d'une façon désordonnée.

Généralement les distributions des probabilités sont subjectives ou dépendent de l'observateur. et quand nous avons des contraintes on parle de maximum d entropie.
L'entropie est la mesure d'incertitude et elle est maximale quand toutes les probabilités sont égales.

est ce que c'est juste ?? et c'est quoi le rapport de cette méthode avec le seuillage automatique ??

[pseudocode]

Envoyé par math_infomatique

Généralement les distributions des probabilités sont subjectives ou dépendent de l'observateur. et quand nous avons des contraintes on parle de maximum d entropie.

subjectives ?

L'entropie est la mesure d'incertitude et elle est maximale quand toutes les probabilités sont égales. est ce que c'est juste ??

Oui.

Une manière plus concrète de voir les choses, c'est que l'entropie nous donne le nombre "idéal" de bits qu'il faut pour encoder l'information.

Pour des images quelconques avec 256 niveaux de gris, c'est 8 bits.

Maintenant, si tes images sont des scans d'articles de journaux, il y a en proportion beaucoup de noir, beaucoup de blanc et plus rarement des gris intermédiaires. On a donc au moins besoin de 1 bit (pour coder noir/blanc) et "un peu plus" pour les niveaux de gris. Ce qui nous donnerait une entropie du genre 1.578 (au hasard), bien loin des 8 bits du cas uniforme.

et c'est quoi le rapport de cette méthode avec le seuillage automatique ??

Quand on seuil, on crée 2 ensembles de valeurs
- E1 = les valeurs inférieurs au seuil
- E2 = les valeurs supérieurs ou égales au seuil

Si le seuil est mal choisi, l'un des deux ensembles contient très peu de pixels différents => son entropie est basse (proche de 0). L'information de toute l'image est presque intégralement contenu dans l'autre ensemble.

Il faut donc trouver le seuil pour lequel l'information est équitablement répartie dans les 2 ensembles => chaque ensemble à une entropie élevée => la somme des 2 entropies est grande (propriété du log)

[math_infomatique]

Bonjour,

Envoyé par pseudocode

subjectives ?

je l'ai lu dans un article!!

Envoyé par pseudocode

Oui.

Une manière plus concrète de voir les choses, c'est que l'entropie nous donne le nombre "idéal" de bits qu'il faut pour encoder l'information.

Pour des images quelconques avec 256 niveaux de gris, c'est 8 bits.

Maintenant, si tes images sont des scans d'articles de journaux, il y a en proportion beaucoup de noir, beaucoup de blanc et plus rarement des gris intermédiaires. On a donc au moins besoin de 1 bit (pour coder noir/blanc) et "un peu plus" pour les niveaux de gris. Ce qui nous donnerait une entropie du genre 1.578 (au hasard), bien loin des 8 bits du cas uniforme.

merci pour l'exemple. il rend les choses plus simple.
mais ici on a la probabilité des pixels noirs 45% et blanc 45% et 10% restante pour les niveaux de gris
les probabilités ne sont pas égales donc l'entropie n'est pas maximale n'est ce pas ?

Envoyé par pseudocode

Quand on seuil, on crée 2 ensembles de valeurs
- E1 = les valeurs inférieurs au seuil
- E2 = les valeurs supérieurs ou égales au seuil

Si le seuil est mal choisi, l'un des deux ensembles contient très peu de pixels différents => son entropie est basse (proche de 0). L'information de toute l'image est presque intégralement contenu dans l'autre ensemble.

Il faut donc trouver le seuil pour lequel l'information est équitablement répartie dans les 2 ensembles => chaque ensemble à une entropie élevée => la somme des 2 entropies est grande (propriété du log)

si l'entropie est élevée pour un ensemble ceci veut dire que l'incertitude est élevée
normalement on augmente la certitude non ?
je comprends plus
pourquoi on parle pas de minimum d'entropie

j'ai lu quelque part que: plus un evenement est rare plus le gain d'information obtenu par sa réalisation est grand !!


et pour le logarithme, son utilisation rend additif le gain totale d'information obtenu par la réalisation de plusieurs évènements indépendants.. c'est pour ça on fait une sommation pondérée des informations ?
S(p)=sum(pi ln (1/pi)) = -sum(pi ln (pi))

[pseudocode]

Envoyé par math_infomatique

merci pour l'exemple. il rend les choses plus simple.
mais ici on a la probabilité des pixels noirs 45% et blanc 45% et 10% restante pour les niveaux de gris
les probabilités ne sont pas égales donc l'entropie n'est pas maximale n'est ce pas ?

Dans l'absolu, ca ne signifie pas grand chose de parler "d'entropie maximale".

On parle du "maximum d'entropie" par rapport a un ensemble de choix possibles. Pour le seuillage, c'est le 'maximum d'entropie" par rapport au seuil choisi pour segmenter l'image.

si l'entropie est élevée pour un ensemble ceci veut dire que l'incertitude est élevée
normalement on augmente la certitude non ?
je comprends plus
pourquoi on parle pas de minimum d'entropie

entropie élevée dans un ensemble E => incertitude grande de prédire la valeur d'un tirage aléatoire dans E

=> E contient peu de valeurs "rares". Chaque valeur est importante. E est donc un très bon échantillon représentatif de la distribution.

Pour notre seuillage, ca signifie que notre choix de seuil nous donnera une image binaire (donc composée de 0 et 1) qui sera un bon échantillon représentatif de l'image d'origine.

[math_infomatique]

donc concernant le seuillage dans une image
on peut dire :

soit l'image f(x,y) où on represente les niveaux de gris des pixels (x,y)
0 < f(x,y) < 255
h(i) : histogramme

et t = seuil de binarisation

on a la sum pi=1
pi : la probabilité d'occurrence du pixel i

le maximum d entropie essaie de maximiser l'information entre la partie proche à la couleur Noir et la partie proche à la couleur Blanche

comme si on a deux classes une pour les Noirs et une pour les Blancs
on calcule l'entropie pour chaque classe

normalement le seuil choisi doit maximiser ces deux entropie.
c'est à dire ce seuil nous donne la meilleure distribution des pixels dans une image.


c'est ça ?

peut-on trouver d'autre méthode de seuillage automatique basé sur la mesure de l'entropie ?

[pseudocode]

Envoyé par math_infomatique

c'est ça ?

Oui, c'est exactement cela.

peut-on trouver d'autre méthode de seuillage automatique basé sur la mesure de l'entropie ?

Le maximum d'entropie est surement la méthode d'entropie la plus répandue.

Une autre consiste a minimiser l'entropie de la différence "image d'origine" vs "image binaire". C'est à dire faire en sorte que la perte d'information soit la moins grande possible.

[math_infomatique]

merci bcp

[math_infomatique]

bonjour,

me revoilà une autre fois je suis désolé mais j'ai eu une nouvelle question sur la différence entre la méthode du maximum d'entropie et la méthode Otsu pour le seuillage?

d'après wikipedia le principe de Otsu est presque le même que celui du maximum d'entropie...

mon but est de chercher les différentes méthodes de seuillage automatique et faire une comparaison.

[pseudocode]

Envoyé par math_infomatique

d'après wikipedia le principe de Otsu est presque le même que celui du maximum d'entropie...

Hum... pas tout à fait, mais pas loin.

Avec le maximum d'entropie, on cherche un seuil qui maximise l'information dans chaque ensemble. Avec Otsu, on cherche un seuil qui sépare le mieux les deux ensembles.

Il y a une différence entre parler de probabilités (entropie) et de statistiques (Otsu). En probabilité on s'intéresse a la variable aléatoire (= au phénomène qu'on observe), alors qu'en statistique on s'intéresse aux données (= aux observations du phénomène).

C'est subtil, mais différent.

[math_infomatique]

ouais c'est subtil !!

[math_infomatique]

Envoyé par pseudocode

Une autre consiste a minimiser l'entropie de la différence "image d'origine" vs "image binaire". C'est à dire faire en sorte que la perte d'information soit la moins grande possible.

j'ai encore une question concernant le principe de Minimum cross entropy MCE

D(P,Q)=sum pi log(pi/qi)

P et Q deux distributions differentes
mais elles représentent quoi réellement??
je peux dire que P est la probabilité de l'occurrence d'un pixel i
mais Q serait quoi alors ?

ou bien P est l'image binaire et Q l'image d'origine? c'est flou?



et est ce que je peux écrire
D(P,Q)=sum pi log(pi/qi) tel que qi=1-pi
seulement dans ce cas on peut avoir pi=qi d'où log1=0
D(P,Q)=0

[pseudocode]

Envoyé par math_infomatique

j'ai encore une question concernant le principe de Minimum cross entropy MCE

D(P,Q)=sum pi log(pi/qi)

P et Q deux distributions differentes
mais elles représentent quoi réellement??
je peux dire que P est la probabilité de l'occurrence d'un pixel i
mais Q serait quoi alors ?

ou bien P est l'image binaire et Q l'image d'origine? c'est flou?

Si on applique le principe de MCE au seuillage d'image, P représente la distribution des valeurs dans l'image d'origine.

Q représente la la distribution des valeurs dans l'image partagée en 2 : une demi-image "valeur basse" et une demi-image "valeur haute".

On cherche alors le meilleurs seuil, celui qui maximise la "ressemblance" entre les 2 distributions. Et donc qui minimise la perte d'information => qui minimise l'entropie de la différence.

et est ce que je peux écrire
D(P,Q)=sum pi log(pi/qi) tel que qi=1-pi
seulement dans ce cas on peut avoir pi=qi d'où log1=0
D(P,Q)=0

Heu... on peut tout écrire. Mais je ne vois pas pourquoi tu veux faire cela.

Si tu cherches a faire du seuillage, les distributions P,Q sont les histogrammes des images. Si "histo" est l'histogramme normalisé de P, alors :

D(P,Q) = sum{ i.histo(i).Log( i.histo(i) / T(i).histo(i) ) }
       = sum{ i.histo(i).Log( i / T(i) ) }
       = sum{ i.histo(i).Log(i) } -  sum{ i.histo(i).Log(T(i)) }

Avec T(i) la valeur de i dans la demi-image basse/haute suivant la valeur de i. Par exemple :
T_low = sum {i.histo(i)} pour i<seuil
T_high = sum {i.histo(i)} pour i>=seuil
d'où:

D(P,Q) = sum{ i.histo(i).Log(i) } - sum_(i<seuil){ i.histo(i).Log(T_low) } - sum_(i>=seuil){ i.histo(i).Log(T_high) }

(si je ne me suis pas trompé dans les calculs )

[math_infomatique]

Envoyé par pseudocode

Si on applique le principe de MCE au seuillage d'image, P représente la distribution des valeurs dans l'image d'origine.

Q représente la la distribution des valeurs dans l'image partagée en 2 : une demi-image "valeur basse" et une demi-image "valeur haute".

On cherche alors le meilleurs seuil, celui qui maximise la "ressemblance" entre les 2 distributions. Et donc qui minimise la perte d'information => qui minimise l'entropie de la différence.

Envoyé par pseudocode

Si tu cherches a faire du seuillage, les distributions P,Q sont les histogrammes des images. Si "histo" est l'histogramme normalisé de P, alors :

D(P,Q) = sum{ i.histo(i).Log( i.histo(i) / T(i).histo(i) ) }
       = sum{ i.histo(i).Log( i / T(i) ) }
       = sum{ i.histo(i).Log(i) } -  sum{ i.histo(i).Log(T(i)) }

Avec T(i) la valeur de i dans la demi-image basse/haute suivant la valeur de i. Par exemple :
T_low = sum {i.histo(i)} pour i<seuil
T_high = sum {i.histo(i)} pour i>=seuil
d'où:

D(P,Q) = sum{ i.histo(i).Log(i) } - sum_(i<seuil){ i.histo(i).Log(T_low) } - sum_(i>=seuil){ i.histo(i).Log(T_high) }

(si je ne me suis pas trompé dans les calculs )

Bon alors je récapitule
P et Q sont les histogramme
P représente la distribution de l'image d'origine

alors Q normalement représente la distribution de l'image binaire?
qui est d'après ton explication T(i)?

et T c'est l'histogramme cumulatif avec un petite modification
T = sum i * h(i)

c'est ça?

voilà un petit code que j'ai écrit

Code :

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

% h : l'histogramme normalisé
% T : normalement c'est l'histogramme cumulatif modifié :D
T(1)=h(1)*1;
for i=1:256
T(i)=i*h(i)+(i-1)*h(i-1)
end

for t=1:256
T_low=T(t);
T_high= 1-T_low;

P1=0
for i=1:t
P1=P1+ ( T(i)*log(T_low) );
end

P2=0
for i=t:256
P2=P2+ ( T(i)*log(T_high) );
end

D(t)=T(t)log(t) - P1 - P2; 

end

best_t = min (D(t));

mais franchement toutes ces méthodes se ressemblent!! c subtil

max d'entropie h1= - sum pi/pc1 ln (pi/pc1)
et
min cross entropy D= sum pi log (pi/qi)
et qi ~= pc1

et est ce que je peux écrire
D(P,Q)=sum pi log(pi/qi) tel que qi=1-pi
seulement dans ce cas on peut avoir pi=qi d'où log1=0
D(P,Q)=0

Heu... on peut tout écrire. Mais je ne vois pas pourquoi tu veux faire cela.

je me disais peut être je trouverais un truc subtil aussi

[pseudocode]

Envoyé par math_infomatique

Bon alors je récapitule
P et Q sont les histogramme
P représente la distribution de l'image d'origine

alors Q normalement représente la distribution de l'image binaire?
qui est d'après ton explication T(i)?

et T c'est l'histogramme cumulatif avec un petite modification
T = sum i * h(i)

c'est ça?

Q n'est pas la distribution de l'image "binaire" (après le seuillage). Cette image serait composée de seulement 2 valeurs possibles : 0 et 1. Non, ce qu'on veut c'est la distribution de l'image originale en considérant qu'il n'y a que 2 valeurs possibles (low et high).

Pour parler concrètement, P,Q sont des distributions = des lois de probabilité.

-P représente la loi de probabilité qu'un pixel P(x,y) de l'image ait la valeur "i", avec "i" variant entre 0 et 255 (pour une image en niveau de gris).
-Q représente la loi de probabilité qu'un pixel P(x,y) de l'image ait la valeur "j", avec "j" = low ou high (2 valeurs possibles, non connues a priori).

Comme pour le maximum d'entropie, il faut imaginer qu'on teste toutes les valeurs de seuil possibles (0...255), et donc toutes les valeurs low/high correspondantes. On ensuite cherche le meilleur seuil. C'est la définition du mot "meilleur" qui est différente entre les 2 méthodes.

Dans le max d'entropie, on considère que le meilleur seuil est celui pour lequel les deux sous-images "low" et "high" contiennent ensembles le plus d'information (indépendamment de l'info contenue originellement dans l'image).

Dans la cross-entropy, on considère que le meilleur seuil est celui pour lequel on perd le moins d'information lors du seuillage.

voilà un petit code que j'ai écrit

mais franchement toutes ces méthodes se ressemblent!! c subtil

Pour le code, je ne maitrise pas matlab donc je ne peux pas t'aider.

C'est vrai que c'est subtil. La différence est dans la définition de "meilleur" seuil. C'est très subjectif.

[math_infomatique]

Envoyé par pseudocode

Q n'est pas la distribution de l'image "binaire" (après le seuillage). Cette image serait composée de seulement 2 valeurs possibles : 0 et 1. Non, ce qu'on veut c'est la distribution de l'image originale en considérant qu'il n'y a que 2 valeurs possibles (low et high).

Pour parler concrètement, P,Q sont des distributions = des lois de probabilité.

-P représente la loi de probabilité qu'un pixel P(x,y) de l'image ait la valeur "i", avec "i" variant entre 0 et 255 (pour une image en niveau de gris).
-Q représente la loi de probabilité qu'un pixel P(x,y) de l'image ait la valeur "j", avec "j" = low ou high (2 valeurs possibles, non connues a priori).

Comme pour le maximum d'entropie, il faut imaginer qu'on teste toutes les valeurs de seuil possibles (0...255), et donc toutes les valeurs low/high correspondantes. On ensuite cherche le meilleur seuil. C'est la définition du mot "meilleur" qui est différente entre les 2 méthodes.

Dans le max d'entropie, on considère que le meilleur seuil est celui pour lequel les deux sous-images "low" et "high" contiennent ensembles le plus d'information (indépendamment de l'info contenue originellement dans l'image).

Dans la cross-entropy, on considère que le meilleur seuil est celui pour lequel on perd le moins d'information lors du seuillage.

très bonne explication

seulement je voulais vérifier, puisqu'on a
T_low = sum {i.histo(i)} pour i<seuil
T_high = sum {i.histo(i)} pour i>=seuil

ceci signifie que T_high=1-T_low ??

c'est presque le même truc dans le max d'entropie T_high et T_low représentent les classes C1 et C2

Pour le code, je ne maitrise pas matlab donc je ne peux pas t'aider.

ah ok

mais juste pour vérifier encore le principe
donc je calcule D(t) pour t allant de 0 à 255
D(t)=T(t)log(t) - P1 - P2;

ensuite je choisie le seuil qui minimise D(t)
best_t = min (D(t));

[pseudocode]

Envoyé par math_infomatique

très bonne explication

seulement je voulais vérifier, puisqu'on a
T_low = sum {i.histo(i)} pour i<seuil
T_high = sum {i.histo(i)} pour i>=seuil

ceci signifie que T_high=1-T_low ??

Heu... a priori non.

T_low c'est la valeur moyenne (= l'intensité moyenne) de l'image basse. Idem pour T_high dans l'image haute. Il n'y a priori aucun rapport entre les 2 valeurs.

c'est presque le même truc dans le max d'entropie T_high et T_low représentent les classes C1 et C2

C'est même exactement la même chose. Seul le critère pour choisir le "meilleur" seuil est différent.

mais juste pour vérifier encore le principe
donc je calcule D(t) pour t allant de 0 à 255
D(t)=T(t)log(t) - P1 - P2;

ensuite je choisie le seuil qui minimise D(t)
best_t = min (D(t));

Oui.

[math_infomatique]

Envoyé par pseudocode

Heu... a priori non.

T_low c'est la valeur moyenne (= l'intensité moyenne) de l'image basse. Idem pour T_high dans l'image haute. Il n'y a priori aucun rapport entre les 2 valeurs.


C'est même exactement la même chose. Seul le critère pour choisir le "meilleur" seuil est différent.

Je suis désolé de te déranger avec mes questions
j'ai l'impression que j'ai compris seulement lors d'écrire mon code je me bloque

puisque c'est la même chose alors
C1+C2=1 c'est la condition de la probabilité

normalement T_low + T_high = T(255) ?

en fait j'ai écrit plusieurs codes et à chaque fois je ne trouve pas de resultat (toujours seuil=0)

voilà l'algorithme de mon code


// hn ==> c'est l'histogramme normalisé
// hc ==> "histogramme cumulé"

hc(1)=hn(1)*1;

T(1)=hc(1)*log(1);

pour i=2 à 256
hc(i)=hc(i-1)+(i*hn(i));

T(i)=T(i-1)+(hc(i)*log(i));
fin pour


// D_low = zeros(1,256) ==> représente sum_(i<seuil){ i.histo(i).Log(T_low) }
// D_high = zeros(1,256) ==> représente sum_(i>=seuil){ i.histo(i).Log(T_high) }
// D = zeros(1,256) ==> représente D(P,Q) = sum{ i.histo(i).Log(i) } - D_low - D_high


// Parcourir toutes les valeurs du seuil possibles

pour seuil=1 à 256

T_low=T(seuil);

pour i=1 à seuil
D_low(seuil) = D_low(seuil)+(i*hc(i)*log(T_low));
fin pour



T_high=T(156)-T_low;

pour i=seuil+1 à 256
D_high(seuil) = D_high(seuil)+(i*hc(i)*log(T_high));
fin pour



D(seuil)= T(seuil) - D_low(seuil) - D_high(seuil);

fin pour

// enfin on cherche le meilleur seuil

[pseudocode]

Envoyé par math_infomatique

normalement T_low + T_high = T(255) ?

en fait j'ai écrit plusieurs codes et à chaque fois je ne trouve pas de resultat (toujours seuil=0)

Ah... C'est de ma faute. Je ne sais pas calculer une valeur moyenne.

T_low = sum{i.histo(i)} / sum{histo(i)}, pour i<seuil
T_high = sum{i.histo(i)} / sum{histo(i)}, pour i>=seuil



Exemple vite fait en java

Code java :

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
// normalized histogram 
double[] hist = histogramNormalized( InputImage );
 
// Entropy of gray-level image
double imgEntropy=0;
for(int i=0;i<256;i++) imgEntropy+=i*hist[i]*LOG(i);
 
double minCE=Double.MAX_VALUE;
int argMinCE=0;
for (int t = 0; t < 256; t++) {
 
	// mean value of low-range image
	double lowValue=0, lowSum=0;
	for(int i=0;i<t;i++) {lowValue+=i*hist[i]; lowSum+=hist[i];}
	if (lowSum>0) lowValue/=lowSum;
 
	// mean value of high-range image
	double highValue=0, highSum=0;
	for(int i=t;i<256;i++) {highValue+=i*hist[i]; highSum+=hist[i];}
	if (highSum>0) highValue/=highSum;
 
	// Entropy of low-range image
	double lowEntropy=0;
	for(int i=0;i<t;i++) lowEntropy+=i*hist[i]*LOG(lowValue);
 
	// Entropy of high-range image
	double highEntropy=0;
	for(int i=t;i<256;i++) highEntropy+=i*hist[i]*LOG(highValue);
 
	// Cross Entropy
	double CE = imgEntropy - lowEntropy - highEntropy;
 
	// save minArg
	if (CE<minCE) {minCE=CE; argMinCE=t;}
}
 
return argMinCE;

gauche : image orignale, 256 niveaux de gris
milieu : seuillage au maximum d'entropie (seuil=105)
droite : seuillage au minimum de cross-entropie (seuil=43)

[souviron34]

Le physicien que je suis ne résiste pas à vous faire partager la vraie définition de l'entropie, qui éclairera le sujet :

Entropie

elle peut être interprétée comme la mesure du degré de désordre d'un système au niveau microscopique.

d'où l'application en termes de débruitage ou seuillage...

Surtout lorsque conjointe à :

Second law of thermodynamics

The second law of thermodynamics is an expression of the tendency that over time, differences in temperature, pressure, and chemical potential equilibrate

Ce qui, appliqué en terme de maths, donne

Principe d'entropie maximale

de toutes ces distributions, c'est - par définition de l'entropie - celle d'entropie maximale qui contient le moins d'information, et elle est donc pour cette raison la moins arbitraire de toutes celles que l'on pourrait utiliser.

et, finalement, en termes d'information :

Principle of maximum entropy

In ordinary language, the principle of maximum entropy can be said to express a claim of epistemic modesty, or of maximum ignorance

[math_infomatique]

Envoyé par pseudocode

Ah... C'est de ma faute. Je ne sais pas calculer une valeur moyenne.

T_low = sum{i.histo(i)} / sum{histo(i)}, pour i<seuil
T_high = sum{i.histo(i)} / sum{histo(i)}, pour i>=seuil

lool
moi aussi j'aurais du faire attention car dans ton poste précédent tu m'as dit que c'est la valeur moyenne.. mais j'ai pas fait attention

Envoyé par pseudocode

Exemple vite fait en java
.......

et bien mon erreur était c'est que le imEntropy je le calcule pour toutes les valeurs du seuil possible (imEntropy(t)) !!

en tout cas merci pour ton aide je pense que mes idées sont claires

J'ai testé des images avec le cross entropie et le max entropie, et comme tu me l'as dit "le meilleur seuil" reste subjectif

Je m'amuse avec mes codes et je vais tester d'autre méthodes de seuillage

merci encore pseudocode

Envoyé par souviron34

Le physicien que je suis ne résiste pas à vous faire partager la vraie définition de l'entropie, qui éclairera le sujet :
......

merci souviron34