Seuillage manuel & méthode d'Otsu

Les images capturées par les caméras et les appareils photo récents contiennent plusieurs millions de pixels. Stocker, analyser et traiter des images de cette taille se révéle être trés couteux en ressources mémoire et processeurs. C’est pour cette raison qu’en traitement et analyse d’images, nous ne travaillions pas sur chaque pixel individuellement. Préalablement à toute analyse ou traitement d’une image, nous agrégeons les pixels de l’image en sous-groupe de pixels. Cette représentation, permet d’extraire de l’images des informations sur les objets présents dans celles-ci. Si nous prenons à titre d’exemple l’image 1, nous remarquons, qu’en isolant l’ensemble des pixels de couleur orange du reste de l’image, l’on peut aisément obtenir des informations sur la taille et la forme de l’orange.

Figure 1: Une orange

Ces informations sont essentielles pour les algorithmes de traitement d’images mais aussi pour nous, car c’est grâce à celle-ci que nous pouvons dire qu’il s’agit bel et bien d’une orange. L'étape consistant à séparer les pixels de l’image en différents sous-groupes de pixels que nous appellerons objets est communément appelée la segmentation. Il s’agit de la premiére étape de tout algorithme d’analyse d’images. Il existe différents types de segmentation. Il y a la segmentation couleurs, qui consiste à séparer les différents objets de l’image en se basant sur leurs couleurs, la segmentation de contour qui se base sur les contours des objets afin de les séparer. La segmentation texturale qui utilise la texture des différents objets pour les isoler. Enfin, il y a des technique de segmentation hybride qui sont un mélange des différentes catégories de segmentation cités ci-dessus. Dans ce chapitre, nous décrirons et illustrerons chaque type de segmentation avec des exemples.

Isoler les objets d’une image grâce à leur couleur : Seuillage global

Le seuillage d’une image consiste à choisir une valeur de niveau de gris que l’on appellera seuil et à définir comme étant objet tout pixel dépassant ce seuil. Les pixels en deçà du seuil sont alors considérés comme faisant partie du fond. Nous avons choisi de commencer cette section en travaillant uniquement sur des images en noir et blanc. Ces images présentent la particularité d’être codées sur une seule matrice de pixel, leur traitement en est donc simplifié. Le lecteur pourra facilement étendre les techniques utilisés dans cette section aux images couleurs, en utilisant des opérations binaires d’image tels que « OR », « XOR » ou encore « ET ». Cette section sera organisée comme suit : dans un premier temps, nous montrerons comment construire un histogramme de couleurs. Nous verrons par la suite comment déterminer manuellement un bon seuil grâce à l’histogramme précédemment construit. La sous-section qui suivra sera dédiée à la présentation de la méthode d’Otsu, une méthode automatique de seuillage. Les deux derniére sous-section seront dédié à la présentation de l’espace couleur HSV et au seuillage multi-bande respectivement.

Figure 2(a): Une image de pizza en niveau de gris
Figure 2(b) L'histogramme de niveaux de gris de l'image 2(a).

En observant l’histogramme présenté dans la figure 2, nous obtenons des informations importantes sur la distribution des pixels dans l’image. Sur l’histogramme, un grand pic de pixel apparaît pour les intensités comprises entre 0 et 70. Les pixels compris entre 0 et 70 sont des pixels majoritairement sombres, en observant l’image de la pizza nous pouvons en déduire que ce pic correspond à la table sur laquelle est placé à pizza car elle est sombre. Le reste des pixel correspondant donc à la pizza, à la biére et au divers autres objets présent sur la table.

Le code permettant d’obtenir cet histogramme est le suivant :

  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;
		}
	}


Les informations obtenues grâce à l’histogramme des niveaux de gris, vont nous permettre de définir un seuil de niveau optimal permettant d’isoler les différents objets présents sur la table. Une méthode générale permettant de séparer le fonds des objets consiste à choisir un seuil se situant aprés ou avant un pic sur l’histogramme des intensités. Ainsi, dans notre cas, un seuil optimal serait approximativement au alentour de 75. En choisissant ce seuil nous obtenons le résultat présenté sur la figure 3.

Figure 3(a): L'image de la figure 2(a) après seuillage, T=75.
Figure 3(b):L'histogramme de niveaux de gris de l'image 2(a) et en rouge le seuil T=75.

Sur l’image ci-dessus, nous remarquons, que l’ensemble des objets présents sur la table ont été partiellement séparés de cette derniére. Ce résultat n’est pas parfait, nous verrons donc dans les prochaines sous-sections comment l’améliorer.

for (int i = 0; i < img.rows; i++)
{
	for (int j = 0; j < img.cols; j++)
	{
    if(img.at<uchar>(i, j)<75)
    {
		 binary_img.at<uchar>(i, j)] = 0;
    }
    else
    {
     binary_img.at<uchar>(i, j)] = 255;
    }
	}
}

Avant de terminer cette sous-section, nous tenons à avertir le lecteur qu’il n’est pas recommandé d’utiliser un seuillage manuel car celui-ci présente de nombreux inconvénients. Parmi ces inconvénients, nous retrouvons le fait qu’utiliser un seuillage manuel empêche l’automatisation totale du programme. De plus, la qualité de la segmentation sera amenée à grandement varier selon l’état de l’opérateur qui l’effectue ou encore selon l’opérateur. Cette technique introduit donc un biais inter et intra-opérateur. Dans la sous-section qui suit nous présentons un méthode de seuillage automatique permettant de résoudre les problémes précédemment évoqué.

Méthode de seuillage automatique

Dans la sous-section précédente, nous avons vu comment à partir de l’histogramme des couleurs nous pouvions segmenter manuellement une image. Nous avons également vu qu’en pratique, les méthodes de segmentation manuelle sont à éviter car bien que nous puissons obtenir une segmentation satisfaisante grâce à ces techniques, elles ne permettent pas l’automatisation totale du programme. De plus les résultats obtenus à partir de ces méthodes présentent l’inconvénient de varier selon l’opérateur humain qui choisit le seuil et selon son état. Dans cette sous-section nous verrons donc comment à partir de l’histogramme des couleur, nous pouvons automatiquement sélectionner un seuil afin de segmenter au mieux une image. Plusieurs méthode de sélection automatique de seuils existent mais la plus connu et celle que nous présenterons dans cette sous-section se nomme la méthode d’Otsu.

La méthode d’Otsu a été inventée par Nobuyuki Otsu en 1979 [1] . 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 des deux classes. 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[2] :

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)=(f(k)-min)/(max -min)

avec k étant l’abscisse de l’histogramme que l’on souhaite transformer, f(k) la valeur de l'histogramme à l'abscisse k et f'(k) la valeur de l'histogramme normalisé à l'abscisse k, min étant la plus petite valeur en ordonnée que peut prendre l'histogramme et max étant la plus grande valeurs en ordonnée possible. Dans notre cas le min est 0 tandis que le max est le nombre de pixels que contient notre image. Le code permettant d’obtenir la normalisation est présenté ci-dessous : Code :
int N = img.cols*img.rows;
for (int i = 0; i < 256; i++)
	{
		hist[i] = hist[i] / N;
	}


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 l' histogramme normalisé allant de 0 à k. Cette probabilité est communément connue sous le nom de moment cumulatif d’ordre zéro.

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;
 }
  


4- Calcul de la probabilité d’obtenir un pixel appartenant à la classe 2 PC2Nous 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.



float  pc2=1-pc1;

5-Calcul de l'intensité moyenne MC1 des pixels de la classe C1, également appelé moment cumulatif de premier ordre.
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 MC1= compute_first_order_cumulative_moment(hist, k);
6- Calcul de l'intensité moyenne MT de tout les pixel .
float MT = compute_first_order_cumulative_moment(hist, 256);

7- Calcul de la variance inter-classe entre C1 et C2. La variance inter-classe est un ratio entre les mesure que nous avons calculé précédemment. La formule de ce ratio est la suivante :

VC1C2=MT*PC1-MC1/PC1*PC2

avec VC1C2 étant la variance inter-classe entre C1 et C2,MT la moyenne total des pixels, PC1 la probabilité d'obtenir un pixel de la classe C1, MC1 la moyenne des pixels de la classe C1 et PC2 la probabilité d'obtenir un pixel de la classe C2.
float compute_variance_class_separability(float uT,float wk, float uk)
{
	return pow((uT*wk-uk),2)/(wk*(1-wk));
}

7- 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 obtenons la variance inter-classe maximum.

Résultat :

Figure 4: Résultat de la segmentation de l'image 2(a) en appliquant la mé~thode d'Otsu.
Le seuil optimal est 96 selon la méthode d'Otsu.

Code final: Code Complet C++ : Otsu Méthode
//otsu.h
#include  <stdio.h>
#include  <ostream>
#include  <math.h>
#include <opencv2/highgui/highgui.hpp>
#include  <opencv2/imgproc/imgproc.hpp>
#include  <opencv2/opencv.hpp>
using namespace  cv;
using namespace std;
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;
}

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;
		}
	}
 // Normalisation de l'histogramme des niveau de gris
	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;
			}
		}
	}


}
//main.cpp
#include "Otsu.h"
int main()
{
        Mat src, src_gray;
	src = imread("pizza.jpg", 1);
        cvtColor(src, src_gray, CV_BGR2GRAY);
        otsu(src_gray);
        imwrite("resultatotsu.png",src_gray);
}

Référence :

[1] A Threshold Selection Method from Gray-Level Histograms NOBUYUKI OTSU, 1979.
[2] Feature Extraction and Image Processing, Nixon M, Aguado A 2008 pp 77-81,
Introduction
Segmentation, extraction d'objets présents dans une image.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.0 Generic License.