Connexite d'une image binaire

Suite à la détection de la couleur de peau, nous obtenons une image binaire ( figure a ), où l'on trouve les morceaux de peau détectés ainsi que du bruit ( pixels isolés ou zones ayant une couleur proche de celle de la peau ).

figure a

Pour exploiter cette image binaire, il nous faut donc séparer ces zones et garder les plus grandes, qui correspondent aux zones de la peau. Pour cela nous avons utilisé un algorithme de connexité qui étiquette toutes les zones détectées. L'algorithme va parcourir l'image binaire et numéroter toutes les zones connexes.

Presentation de l'algorithme

Plusieurs algorithmes existent pour étiquetter les zones connexes d'une image binaire. Lors de nos recherches, nous avons trouvé trois méthodes.

La première est une méthode assez intuitive, mais qui limite le nombre de parcours des pixels de l'image grâce à l'introduction d'équivalence de zone
Image Binaire
une autre utilise une pile FIFO, pour y stocker les pixels non indexés.
Etiquettage avec pile
Et une troisième assez originale qui reprennait la méthode intuitive mais en utilisant le codage RLC de l'image, ce dernier algorithme se nomme Light Speed labeling

Nous avons choisi la premiere méthode qui paraissait la plus simple à programmer et la plus facilement parallélisable.

Algorithme de connexité

Lors de son traitement, l'image va être parcourue de gauche à droite et du haut vers le bas. Donc on considère que chaque pixel a quatre prédécesseurs, son pixel de gauche, celui en haut à gauche, en haut et en haut à droite. Comme le montre la figure b.

figure b : P est le pixel courant, les cases marquées d'un 'a' sont ses prédécesseurs

On parcourt donc l'image, quand on trouve un pixel non nul ( pour l'image binaire ) on regarde ses voisins, si ses voisins n'ont pas de numéro, on lui assigne un nouveau numéro de zone, sinon on lui assigne le numéro d'un de ses voisins et on met à jour le tableau de correspondance pour noter les équivalences de zone si il y a.

Algorithme de Connexite

Pour tous pixels P

Si le pixel de l'image binaire est nul, on ne fait rien
Sinon on regarde les prédécesseurs

Si les prédécesseurs n'ont pas de numéro on assigne un nouveau numéro à P
Sinon on assigne à P le plus petit numéro de zone de ses prédécesseurs et on met à jour la table de correspondance.

Table de correspondance

Pour traduire l'équivalence de certaines zones, nous avons besoin d'une table de correspondance. Nous avons choisi de la représenter par un tableau T, tel que si T(i) = j alors i et j sont deux zones équivalentes. On initialise T par T(i) = i . Les équivalences sont donc représentées par des chaînes, dont la zone de référence de i sera telle que T(i) = i. ( figure c )

figure c : 6, 8, 10, 3, 5 sont équivalents, 5 est la zone de référence

Ainsi lorsque que l'on trouve une équivalence des zones i et j ( avec i < j ) On regarde la zone de référence de i ( noté R(i) ) et on associe toutes les équivalences de j à R(i). Les zones i et j ont donc la même zone de référence et deviennent équivalentes. ( figure d )

figure d : On a trouvé que la zone 3 est équivalente à la zone 6

A la fin de l'algorithme, une boucle permet de modifier la table de correspondance pour associer chaque zone à sa zone de correspondance, avec T(i) = R(i) .

Statistiques par zone

Pour chaque zone, nous avions besoin des statistiques. Son nombre de pixel, ses maximums et minimums en x et y, la somme des x, y, x², y² et xy. Ce qui nous permet ensuite plusieurs opérations sur les zones : encadrement, classement, tri, calcul de barycentre, matrice de covariance et ses vecteurs propres...

A la fin, l'algorithme donne donc une image, où toutes les zones sont indexées ( figure e ), et les statistiques de chaque zone qui vont permettre de localiser la zone, de calculer son barycentre, ses axes principaux... etc ( figure f ).

-->

figure e : Chaque couleur représente une zone distincte.

figure f : La zone ayant le plus grand nombre de pixel est encadrée et on affiche son barycentre

Performance et Paralellisation

Version Séquentielle

La version séquentielle a tout de suite donné de très bon résultats, avec un temps de calcul moyen de 15ms sur une image 640*480. et 5ms sur une image sous échantillonnée par deux. Nous avons tout de même voulu paralléliser l'algorithme.

Version Parallèle

Pour paralléliser l'algorithme nous avons divisé l'image en deux sous images, et appliqué l'algorithme précédent sur les deux sous images. Nous obtenons deux images étiquettées et deux tables de correspondance. Nous fusionnons ensuite les deux tables de correspondances et nous complétons la table obtenue en parcourant la frontière des deux sous images. La version parallèle permet un gain d'environ 30%. On obtient un temps moyen de calcul de 10ms pour une image 640*480, et de 3ms pour une image sous échantillonnée par deux.

Precedent	Menu	Suivant
	Retour haut de la page