Méthode d'Otsu : comment elle fonctionne ?

La méthode d’Otsu a été inventée par Nobuyuki Otsu en 1979. Son principe de fonctionnement est le suivant : nous posons l’hypothèse que dans l’image que nous traitons il existe deux classes de pixels. La première correspond aux pixels du fond, la seconde correspond aux pixels des objets. En admettant que ces deux classes sont séparables par leur niveau de gris, nous pouvons définir que les pixels ayant une intensité comprise entre 0 et k appartiennent à la première classe et que les autres dont l’intensité comprise entre k+1 et 255 appartiennent à la seconde classe. L’inverse est aussi possible, notamment dans le cas d’un fond blanc. Nous allons donc chercher à fixer un seuil k tels que la séparation de ces deux classes soit optimale. Afin de fixer ce seuil automatiquement, il nous est nécessaire de disposer d’une ou de plusieurs mesures numérique exprimant la qualité de la segmentation. La méthode d’Otsu se sert de la variance inter-classe, comme mesure de qualité. Cette mesure caractérise la dissimilarité entre les pixel de nos deux classe. Plus cette valeur est haute, moins les deux classe se ressemble à l’inverse plus elle est basse et plus les deux classes de départ se ressemblent. Le seuil optimal est donc le seuil pour lequel l’on obtiens la plus grande variance inter-classe.


L’implémentation de la méthode d’Otsu, est expliquée ci-dessous :


Soit, C1 les pixels de l’image appartenant à la première classe et C2 les pixels de la seconde. Nous rappelons que les intensités de pixel de C1 sont comprises entre 0 et k et que les intensités des pixels c2 sont comprises entre k+1 et 255.


Les étapes de l’algorithme d’Otsu sont les suivantes :

1- Construction de l’histogramme des niveaux de gris.

La construction de l’histogramme des niveaux de gris a été vue dans la sous-section précédente.


2-Normalisation de l’histogramme des couleurs :

Normaliser l’histogramme, consiste à construire un histogramme des niveaux de gris dont toutes les valeurs en ordonnée seront comprises entre 0 et 1.

Le calcul ci-dessous permet d’y parvenir :


f(k)=(k-min)/(max -min)


avec k étant l’abscisse de la valeur de l’histogramme que l’on souhaite transformer, min étant la valeur minimale en ordonnée de l’histogramme et max étant la valeur maximale en ordonnée de l’histogramme. Le code permettant d’obtenir la n normalisation est présenté ci-dessous :



Remarque : en normalisant l’histogramme des couleurs l’on obtient une distribution de probabilité. Ainsi, par exemple la probabilité que dans notre image il y ait un pixel dont le niveau de gris est 255 est la valeur de notre histogramme normalisé pour l’abscisse 255.



3-Calcul de la probabilité d’obtenir un pixel appartenant à la classe 1 PC1.


Comme nos pixels de classe C1 ont une intensité allant de 0 à k, nous pouvons calculer la probabilité d’obtenir un pixel de classe C1 en sommant l’ensemble des colonnes de notre histogramme allant de 0 à k.



Code :

float compute_zero_order_cumulative_moment(float *hist, int k)

{

float zero_order_cumulative_moment = 0;

for (int i = 0; i < k; i++)

{

zero_order_cumulative_moment += hist[i];

}

return zero_order_cumulative_moment;

}

Cette probabilité est également appelée le moment cumulatif d’ordre zéro.



2- Calcul de la probabilité d’obtenir un pixel appartenant aàla classe 2 PC2


Nous pouvons obtenir la probabilité qu’un pixel appartienne à la classe C2 en soustrayant à 1 la probabilité d’obtenir un pixel de classe C1, car il n’y a que deux classes.



Code :

PC2=1-PC1




class mean level zero cumulative moment *valeur du pixel

linear algebre for image

3- Calcule de la variance inter classe entre C1 et C2










float compute_variance_class_separability(float uT,float wk, float uk)

{

return pow((uT*wk-uk),2)/(wk*(1-wk));

}




6- Nous devons répeter les étape 2,3,4,5 pour toute les valeur de k possible, le k optimum est le k pour lequelle nous obenon la variance inter-classe maxima.


Code final:




Code Complet : Otsu Méthode



float compute_first_order_cumulative_moment(float *hist, int k)

{

float first_order_cumulative_moment = 0;


for (int i = 0; i < k; i++)

{

first_order_cumulative_moment += i*hist[i];

}

return first_order_cumulative_moment;


}

float compute_variance_class_separability(float uT,float wk, float uk)

{

return pow((uT*wk-uk),2)/(wk*(1-wk));

}


void otsu(Mat img)

{

int s;

float hist[256];

for (int i = 0; i < 256; i++)

{

hist[i] = 0;

}

for (int i = 0; i < img.rows; i++)

{

for (int j = 0; j < img.cols; j++)

{

hist[img.at<uchar>(i, j)] += 1;

}

}

int N = img.cols*img.rows;

for (int i = 0; i < 256; i++)

{

hist[i] = hist[i] / N;

}

float w[256],u[256],uT;


for (int i = 0; i < 256; i++)

{

w[i] = compute_zero_order_cumulative_moment(hist, i);

u[i] = compute_first_order_cumulative_moment(hist, i);

}

uT = compute_first_order_cumulative_moment(hist, 256);

float variance_class_separability_max = -1;

float best_threesold = 0;

for (int i = 0; i < 256; i++)

{

int vk = compute_variance_class_separability(uT, w[i], u[i]);


if (vk > variance_class_separability_max)

{

variance_class_separability_max = vk;

best_threesold = i;

}

}

for (int i = 0; i < img.rows; i++)

{

for (int j = 0; j < img.cols; j++)

{

if (img.at<uchar>(i, j) < best_threesold)

{

img.at<uchar>(i, j) = 0;

}

else

{

img.at<uchar>(i, j) = 255;

}

}

}


}


Source :

https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4310076

https://en.wikipedia.org/wiki/Otsu%27s_method


. Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.0 Generic License.