Segmentation de régions : algorithmes et méthodes

Dans la section précédente, nous avons implémenté un seuillage multi-canal qui nous a permis détecter le fond et de mettre en valeur les différents objets présents dans l’image. À la suite de cela, nous avons présenté une alternative à cette méthode qui se sert de la composante teinte de l’espace de couleurs HSI afin de segmenter l’image. Grâce à cette section, nous avons acquis les techniques de base permettant de séparer le fond et les objets présents dans une image. Seulement, dans la majorité des applications de traitement d’images, ces techniques ne seront pas suffisante car elles ne permettent pas différencier les différent objets présent dans l’image. Dans cette section, nous verrons donc comment identifier les différents objets présents dans une image après binarisation de celle-ci et comment séparer ces objets.

Étiquettage des régions (regions labelling: en anglais)

L’étiquetage des régions est l’opération qui consiste à identifier les régions présentes dans une image binaire. Cette opération, nous permet d’isoler les différents objets présents dans l’image à condition que ces objets ne soient pas superposés. [3]. Malheureusement dans les cas pratiques, cette condition n’est pas toujours respectée, il convient alors d’utiliser des algorithmes plus sophistiqués faisant appel à la morphologie mathématique tel que la Ligne de partage des eaux . Ces techniques seront présentées ultérieurement dans ce tutoriel.

L’étiquetage des régions peut être réalisé par de nombreux algorithmes[3,4] , Grana et al. ont par ailleurs évalués les différentes méthodes existantes et ont publié un comparatif de celle-ci[2] . De manière générale, il n’est pas nécessaire de disposer de l’algorithme d’étiquetage le plus efficace. Un algorithme simple fera l’affaire dans la majorité des problèmes de traitement d’images. Seulement, certaines méthodes peuvent être plus adaptées que d'autres selon les situations dans lesquelles on les utilise. Dans la sous-section suivante :nous présenterons une méthode simple, abordable et efficiente permettant d’extraire les régions : L’algorithme de groupement des pixel en contact.

Algorithme de groupement des pixels en contact

L’algorithme de groupement des pixels en contact, considère que deux pixels font partie d’une même région s'ils sont en contact. Son fonctionnement est le suivant : Un pixel objet « blanc » de départ est sélectionné (en vert sur la figure 1-b) , ce pixel devient alors la région initiale que l’on cherchera à étendre. Les 8 plus proches pixels objet voisin (en violet sur la figure 1-c) du pixel précédemment sélectionné sont alors ajoutés à la région (coloré en vert sur la figure 1-d), cette étape est par la suite répétée pour les pixels voisins des pixels nouvellement ajoutés (figure 1-e,f,g) et cela jusqu'à ce qu’il n’y ait plus de voisin (figure 1-h).

Figure 1(a): Itération 1.
Figure 1(b): Itération 2.
Figure 1(c): Itération 3.
Figure 1(d): Itération 4.
Figure 1(e): Itération 5.
Figure 1(f): Itération 6.
Figure 1(g): Itération 7.
Figure 1(h): Itération 100.

Implémentation

Dans un premier temps, nous commençons par déclarer la fonction d’agrandissement de région. Cette fonction prend en paramètre les coordonnées du pixel initial « x_start » et « y_start », l’étiquette de la région « label_color » qui permettra d’attribuer une couleur à la région et enfin une file « file_pixel » qui stockera les pixels qui n’ont pas encore été traités.
//agrandissement_region.h
...
void agrandissement_region( int x_start, int y_start , Vec3b label_color, File_px *file_pixel)
{
	//CODE
}

Afin de gérer cette file, nous avons tout d’abord besoin de définir le type de données File_px et les fonctions de base qui permettront de gérer celui-ci. Pour ce faire nous créons une structure File_pixel qui sera composée des divers champs suivants : la file elle-même sous forme d’un tableau deux dimensions, la position courante du prochain élément à traiter « current_pos_file », le nombre de pixels à traiter contenu dans la file «  pos_dernier_element » et enfin la position du dernier élément à traiter que peut contenir la file « taille_max_file ».
typedef struct File_pixel
{
	int **file;
	int  current_pos_file;
	int pos_dernier_element;
	int taille_max_file;
} File_px;
Les fonctions de base que nous utiliserons pour la gestion de celle-ci sont les fonctions : enfilez, défilez et vide[5]. Elles sont définies comme suit :
Enfiler est une fonction qui permet d’ajouter la position d’un pixel à traiter à notre file.
void enfilez(File_px *file_pixel, int x, int y)
{

	int pos = file_pixel->pos_dernier_element;
	file_pixel->file[pos][0] = x;
	file_pixel->file[pos][1] = y;
	file_pixel->pos_dernier_element++;
}
La fonction défilez nous permet d’obtenir la position du prochain pixel à traiter.
void  defilez(File_px *file_pixel, int *x, int *y)
{
	int pos = file_pixel->current_pos_file;
	*x = file_pixel->file[pos][0];
	*y = file_pixel->file[pos][1];
	file_pixel->current_pos_file++;
}
La fonction vide nous permet de savoir si tous les pixels dans la file ont été traités.
bool vide(File_px *file_pixel)
{
	//Test si la position de l’élément courant est supérieure à celle du dernier élément
	if (file_pixel->current_pos_file>= file_pixel->pos_dernier_element)
	{
		return true;
	}
	return false;
}
Une fois que nous avons créé, l’ensemble des primitives de gestion de file, nous pouvons revenir à la fonction d’agrandissement des régions.Cette fonction commence par empiler le pixel initial :
void agrandissement_region(Mat src,Mat dst,int x_start, int y_start, Vec3b label_color, File_px *file_pixel)
{
	enfilez(file_pixel, x_start, y_start);
       ....
}
A la suite de cela, l’algorithme rentre dans une boucle tant que qui ne s’arrêtera que quand il n’y aura plus de pixels à traiter. Le pixel courant est alors dépilez pour être traité.
void agrandissement_region(Mat src,Mat dst,int x_start, int y_start, Vec3b label_color, File_px *file_pixel)
{    ...
while (vide(file_pixel) == false)
	{
			
		int x, y;
		defilez(file_pixel, &x, &y);
	}

	...
}
L’algorithme vérifie à la suite de cette étape, si parmi les 8 plus proche voisin du pixel courant il y a des pixels à traiter (des pixels blancs) si c’est le cas ces pixels sont empilés:
....
....
	for (int k = -1; k < 2; k++)
		{
			for (int l = -1; l < 2; l++)
			{
				// test si pour s’assurer que la position du voisin est dans l’image
				if (x + k >= 0 && y + l >= 0 && (x + k) < src.rows && (y + l) < src.cols)
					//test pour savoir si le voisin est à traiter 
					if (dst.at<Vec3b>(x + k, y + l) == <Vec3b>(255, 255, 255))
					{
						dst.at<Vec3b>(x+k, y+l) = label_color;
						enfilez(file_pixel, x + k, y + l);
					}
			}
		}

....
....
Enfin il nous faut construire la fonction main qui utilisera la fonction d’agrandissement de régions :
int main()
{
	Mat src, dst;
	src= imread("binarypizza.png", 1);
	dst = src.clone();
	File_px file_pixel;
	file_pixel.file = (int **)malloc(5*src.cols*src.rows * sizeof(int *));
	for (int i = 0; i < 5 * src.cols*src.rows; i++)
	{
		file_pixel.file[i] = (int *)malloc(2 * sizeof(int));
	}
	
	file_pixel.taille_max_file = 5 * src.cols*src.rows;
	for (int i = 0; i < dst.rows; i++)
	{
		for (int j = 0; j < dst.cols; j++)
		{
			if (dst.at<Vec3b>(i, j) == Vec3b(255, 255, 255))
			{
				file_pixel.current_pos_file = 0;
				file_pixel.pos_dernier_element = 0;
				agrandissement_region(src, dst, i, j, Vec3b(rand()%255, rand() % 255, rand() % 255), &file_pixel);
			}
		}
	}
	imwrite("region.png", dst);
  }

Résultat :

Figure 2(a): Image binarisée d'une pizza.
Figure 2(b): Région présente dans l'image de la figure 2(a).

Extraction des bounding box des régions

Afin d’extraire les bounding box présente dans l’images, nous allons définir une fonction d’extraction de bounding box. Celle-ci prendra en paramètre l’image nouvellement obtenue après coloration des régions « img_region_color »,l’image dont l’on souhaite extraire les région, un pointeur vers une liste d’image « bounding_boxes » qui contiendra nos bounding_box, enfin un vecteur contenant l’ensemble des couleurs présentent dans la région.
Void extract_bounding_box(Mat img_region_color, Mat img,vector *bounding_boxes,vector couleurs, )
{

}

La fonction extract_bounding_box va déterminer pour chaque région les coins du rectangle la contenant. Pour ce faire, Pour chacune des couleur il va chercher le plus petit abscisse « x_min », le plus petit ordonnée « y_min », le plus grand abscisse « x_max » et le plus grand ordonnée « y_max ». Les coordonnées des coins du rectangle contenant la régions sont alors les suivant : (x_min, y_min), (x_min,y_max),(x_max,y_min) et (x_max,y_max).

Void extract_bounding_box(Mat img_region_color,vector *bounding_boxes,vector couleurs)
{
	for (int i=0;i< couleurs.size() ; i++)
	{
		int xmin= 100000;
		int xmax = -100000;
		int ymin = 100000;
		int ymax = -100000;
		for (int j = 0; j < img.rows; j++)
		{
		for (int k = 0; k < img.cols; k++)
		{
			if (img_region_color .at(j, k) == couleur[i])
			{
				if (j < xmin)xmin = j;
				if (j > xmax )xmax =j;
				if (k < ymin)ymin= k;
				if (k > ymax)ymax = k;	
			}
		 }
	}

	

}
Après avoir localisé les coins de l’image, il ne nous reste plus qu’à créer une nouvelle image et à copier la région dans celle-ci :
Void extract_bounding_box(Mat img_region_color,vector *bounding_boxes,vector couleurs)
{
	for (int i=0;i< couleurs.size() ; i++)
	{
		…
		…
		//Création de la nouvelle image 
		Mat region = Mat(Size(ymax- ymin, xmax - xmin), CV_8UC3);
		//Copi
	
			//Copie de la région dans la nouvelle image
			int i2 = 0;
			for (int i = xmin; i < xmax; i++)
			{
				int j2 = 0;
				for (int j = ymin; j < ymax; j++)
				{
					
					region.at(i2,j2)= img.at(i,j)
					j2++ ;
				}
				i2++ ;	
			}	

			//ajout de la nouvelle image dans la liste des bounding boxes
				bounding_box->push_back(region);

	

}
Pour finir, nous allons modifier la fonction main afin qu’elle enregistre les couleur attribuée au région et qu’elle sauvegarde dans le dossier courant du projet les bounding_box obtenus :
int main()
{
	…
	…

	…
	 vector regions_color() ;

	
	for (int i = 0; i < img.rows; i++)
	{
		for (int j = 0; j < img.cols; j++)
		{
				if (img.at(i, j) == Vec3b(255, 255, 255))
					{
						Vec3b color=Vec3b(rand() %255, rand() %255, rand() %255)
						 regions_color→push_back(color) ;
						agrandissement_region( i, j ,color, &file_pixel,img
 img)
						
					}
		}
	}


	//extraction des bounding box de l’images
	 vector bounding_boxes ;
	Mat img=imread(« pizza.jpg »)
	 extract_bounding_box(img_region_color,img,&bounding_boxes,regions_color)
	//sauvegarde des bounding boxes

	for (int i = 0; i 
Résultat

Code complet :

//agrandissementregion.h
#pragma once
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/imgproc/imgproc.hpp>
#include <opencv2/opencv.hpp>

using namespace cv;
using namespace std;

typedef struct File_pixel
{
	int **file;
	int  current_pos_file;
	int pos_dernier_element;
	int taille_max_file;
} File_px;


void enfilez(File_px *file_pixel, int x, int y)
{

	int pos = file_pixel->pos_dernier_element;
	file_pixel->file[pos][0] = x;
	file_pixel->file[pos][1] = y;
	file_pixel->pos_dernier_element++;
}

void  defilez(File_px *file_pixel, int *x, int *y)
{
	int pos = file_pixel->current_pos_file;
	*x = file_pixel->file[pos][0];
	*y = file_pixel->file[pos][1];
	file_pixel->current_pos_file++;
}

bool vide(File_px *file_pixel)
{
	//Test si la position de l’élément courant est supérieure à celle du dernier élément
	if (file_pixel->current_pos_file>= file_pixel->pos_dernier_element)
	{
		return true;
	}
	return false;
}

void agrandissement_region(Mat src,Mat dst,int x_start, int y_start, Vec3b label_color, File_px *file_pixel)
{
	enfilez(file_pixel, x_start, y_start);


	while (vide(file_pixel) == false)
	{
			
		int x, y;
		defilez(file_pixel, &x, &y);
		dst.at<Vec3b>(x, y) = label_color;
		for (int k = -1; k < 2; k++)
		{
			for (int l = -1; l < 2; l++)
			{
				// test si pour s’assurer que la position du voisin est dans l’image
				if (x + k >= 0 && y + l >= 0 && (x + k) < src.rows && (y + l) < src.cols)
					//test pour savoir si le voisin est à traiter 
					if (dst.at<Vec3b>(x + k, y + l) == <Vec3b>(255, 255, 255))
					{
						dst.at<Vec3b>(x+k, y+l) = label_color;
						enfilez(file_pixel, x + k, y + l);
					}
			}
		}
	}
}
Fichier :

Référence :

[5] Introduction à l'algorithmique: Cours et exercices, Cormen T, Leiserson C, Rivest R, Stein C, 2016, pp 195-198.
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.