Wiki du LAMA (UMR 5127) - Contributions [fr]

Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

2018-05-26T19:24:59Z

Ruet :

== Introduction ==

La segmentation d'image est une famille dans le traitement d'image qui consiste à regrouper des pixels d'une image selon certaines de leurs caractéristiques.

On va ici utiliser un algorithme appelé "ligne de partage des eaux" sur des images en niveaux de gris.
Dans cet algorithme on utilise deux approches de la segmentation d'image, la segmentation par détection de contours et la segmentation par détection de régions. Deux étapes principales constituent donc l'algorithme.
La première est de représenter l'image en fonction de l'intensité de ses variations, on met ainsi en valeur les fortes variations de valeur dans l'image, donc les potentiels contours. La deuxième est de regrouper les zones dans cette nouvelle image par homogénéité, on détecte ainsi des régions dans l'image.

== Première étape : Approximation du gradient d'une image==
=== Image et notion de gradient d'une image ===
==== Image ====
Une image est un ensemble de points associés à une couleur.
Pour afficher une couleur, on combine une intensité de lumière rouge, une intensité de lumière verte et une intensité de lumière bleue.
Dans une image couleur chaque pixel est donc associé à 3 valeurs, les intensités de ces couleurs.
Ces intensités sont généralement codées sur 8 bits, donc comprises entre 0 et 255.

Ici, l'image traitée est une image en niveaux de gris. Une couleur est perçue comme un niveau de gris lorsque les intensités de lumière rouge, de lumière verte et de lumière bleue sont identiques.
Ainsi chaque point est décrit par ses coordonnées et associé à une seule valeur (entre 0 et 255) dans les images que l'algorithme pourra traiter.

D'un point de vue mathématique on peut considérer que l'image est une fonction de R*R vers R : on prend un couple de réels (les coordonnées) auquel un autre réel est associé (un niveau de gris).

==== Gradient ====

Pour réaliser la segmentation d'une image par détection de contour, la première étape est de représenter les variations de valeur dans l'image.
Si l'image est une fonction, et qu'elle est considérée différentiable, il est possible d'utiliser le gradient pour déterminer les variations de valeur en chaque point.

Le gradient d'une fonction est un vecteur qui représente les variations de la fonction par rapport à ses différents paramètres.

La direction et le sens du gradient indiquent le sens dans lequel la fonction varie le plus et sa norme indique l'intensité de la variation.

Ainsi, plus la norme du gradient est élevée en un point, plus les variations "autour" du point sont élevées.

Les coordonnées du gradient sont les dérivées partielles en fonction de chacun des paramètres de la fonction. Si les deux paramètres d'une fonction de R*R vers R sont appelés x et y, on aura en première coordonnée la dérivée partielle de la fonction selon x et en deuxième coordonnée la dérivée partielle de la fonction selon y.

Pour calculer les dérivées partielles de la fonction, il est nécéssaire de pouvoir connaître ses valeurs en chaque point.
Hors dans notre cas, les valeurs de la fonction image ne sont connues qu'en certains points, qui sont "distincts" entre eux.

Le gradient n'est donc pas calculable, cependant il est possible d'en avoir une approximation.

=== Filtre de Sobel ===

Le filtre de sobel est un opérateur permettant d'approximer le gradient de chacun des points de l'image.

Cet opérateur utilise des masques de convolution.

L'application des masques de convolution dans une image est lié au produit de convolution, un opérateur mathématique dont je parlerai pas car je ne connais que peu le sujet.

Pour obtenir la nouvelle valeur d'un pixel, on va convoluer la région "autour" du pixel avec un masque.

Le filtre de Sobel utilise deux masques, pour calculer chaque dérivée partielle.

[[File:sobel_x.png|border|100px]] ''Masque utilisé pour approximer la dérivée partielle en x''

[[File:sobel_y.png|border|100px]] ''Masque utilisé pour approximer la dérivée partielle en y''

==== Utilisation des masques de convolution ====

Pour chaque convolution, on utilise le masque et l'entourage d'un pixel dont on veut calculer la valeur.

Exemple, on veut calculer ici la nouvelle valeur du pixel entouré de rouge :

[[File:Convolution_pixel.png|exemple d'utilisation du produit de convolution]]

Chaque valeur d'un pixel "autour" du pixel dont on veut la nouvelle valeur est multipliée par la valeur correspondante dans le masque.

Dans ce cas pour obtenir une approximation de la dérivée partielle selon x, on devrait diviser par 8 le résultat (on utilise 8 valeurs parmi les pixels voisins).

Cependant, on souhaite que la valeur de la norme du gradient en un point soit toujours comprise entre 0 et 255 (pour pouvoir l'enregistrer dans une image).

Cette division n'est donc pas effectuée, les valeurs obtenues avec les deux masques du filtre de Sobel seront utilisées directement pour calculer la norme.

La norme calculée sera ensuite multipliée par un coefficient pour ramener les valeurs entre 0 et 255.

Les coordonnées de la norme calculée sont proportionellles aux coordonnées de la vraie norme ; elle sont comprises entre -1020 et 1020 (-4*255 et 4*255).

Si ces coordonnées sont appelées dx et dy, on a:

<math>
Norme = \sqrt{dx^2 + dy^2}
</math>

Donc

<math>
0\leq Norme\leq \sqrt{2}*1020
</math>

Pour que la valeur de cette norme soit comprise entre 0 et 255, elle sera multipliée par <math>\frac{255}{\sqrt{2}*1020}</math>.

En arrondissant cette valeur, on obtient l'intensité du pixel dans l'image résultat.

=== Calcul des bords de l'image gradient ===

Un problème survient, celui des pixels situés aux bords de l'image. Ils n'ont en effet pas de voisins dans toutes les directions, ainsi il n'est pas possible de convoluer directement leur "entourage" avec les masques du filtre de sobel.

Les pixels "manquants" sont remplacés.

Plusieurs solutions sont possibles :
* Ne rien faire et enlever les "bords" de l'image obtenue (l'image obtenue après application de l'algorithme est donc plus petite). Cette méthode donne de bons résultats car les résultats de l'algorithme au bord de l'image sont peu intéressants.

* Prolonger l'image. Il existe de nouveaux plusieurs méthodes, comme se référer à la valeur du pixel dans l'image le plus proche lorsque le pixel voulu est en dehors de l'image, ou répéter l'image lorsque la valeur voulue est hors de l'image. La manière de prolonger l'image dépend de la manière dont on va utiliser le résultat.

Ici j'ai choisi de prolonger l'image. Une méthode pour cela est de symétriser de l'image par rapport au pixel dont on veut calculer le gradient ; cette méthode a pour but de prolonger les formes au bord de l'image.

Voici un exemple du résultat attendu, où la ligne bleue représente le bord de l'image :

[[File:Sobel_bords.png|border|100px]]

Cependant cette solution ne permet pas calculer les valeurs aux "coins".

[[File:sobel_coin.png|border|100px|Symétriser l'image ne permet pas de remplacer les valeurs manquantes]]''Symétriser l'image ne permet pas de remplacer les valeurs manquantes''

Les pixels dont on ne peut pas remplacer la valeur par cette symétrie sont remplacés par le pixel dont on veut calculer le gradient.

Après l'utilisation de cette algorithme, l'image obtenue en résultat est une image "gradient".

[[File:sobel_gradient.png|border|300px|Image et son gradient]]
''Remarque : dans cet exemple, l'image gradient n'est pas celle obtenue avec l'algorithme ; les valeurs des pixels ont été augmentées pour que l'impact de cette étape soit plus visible.''

La valeur d'un pixel est élevée s'il se trouve dans une zone où les valeurs des pixels varient beaucoup.

Il est facile d'observer que les contours sont mis en valeur (ou plutôt, les zones où les valeurs des pixels varient beaucoup).

== Deuxième étape : détermination de la "ligne de partage des eaux"==

Pour la deuxième étape de l'algorithme, on utilise l'image gradient. Elle est alors considérée comme un relief où les pixels de faible intensité sont à faible altitude, et où les pixels d'intensité élevée sont à forte altitude.

=== Définitions ===

En topologie la ligne de partage des eaux peut-être définie de plusieurs manières ; elle est la séparation entre deux bassins versants dans un relief.

Notre image est considérée comme un relief, et la ligne de partage des eaux sera la séparation entre les zones de l'image.

Un bassin versant est un bassin dont toutes les eaux ont le même exutoire, par exemple une rivière ou l'océan.

Pour déterminer la ligne de partage des eaux, plusieurs méthodes sont possibles :

* On place une source d'eau dans chaque minimum local (donc dans chaque bassin) et on inonde, quand deux bassins se rencontrent on place une ligne de partage des eaux.
Les algorithmes utilisant ce principe sont appelés des algorithmes par inondation.

* Une deuxième méthode est de considérer que des deux côtés de la ligne l'écoulement de l'eau se termine dans des bassins versants différents.
Dans l'algorithme associé, on va faire "s'écouler" de l'eau sur chaque pixel et tracer une ligne de partage entre deux pixels (ou sur l'un des deux pixels) quand les eaux qui s'écoulent depuis ces pixels arrive dans des minima locaux différents.
Ce sont les algorithmes par ruissellement.

=== Algorithme utilisé (créé par Luc Vincent et Pierre Soille) ===

L'algorithme choisi est un algorithme par inondation.

Les pixels de faible intensité vont donc être traités en priorité.

La première étape est donc de trier les pixels de l'image par ordre croissant d'intensité.

L'algorithme va traiter les pixels d'intensité la plus basse, puis une fois ceux-ci traités, les pixels avec une intensité légèrement supérieure sont traités, et ainsi de suite jusqu'à avoir traité toute l'image.

Trois problèmes se posent alors :
* Comment inonder un étage, c'est à dire de quelle manière traiter les pixels de même intensité, à partir de bassins connus ?
* Comment déterminer à quel bassin appartient un pixel ?
* Comment repérer les nouveaux bassins ?

==== Inonder un étage (pixels d'intensité identique) ====

Chaque bassin doit progresser à la même vitesse sur un étage, c'est à dire que la ligne de partage des eaux qui sépare deux bassins doit être à égale distance de chacun.

Chaque pixel est à une "distance" d'un bassin. Par exemple les pixels collés à un bassin connu sont à une distance de 1. Leurs voisins sont eux à une distance de 2 (à condition qu'ils ne soient pas collés à un bassin connu).

[[File:file_distance.png|frame|Distance à laquelle se trouve les pixels du bassin connu (bleu)]]

Pour que les bassins s'étendent correctement, on traite d'abord tous les pixels à distance 1, puis ceux à distance 2 et ainsi de suite.

Une file d'attente est créée ; la première étape est de placer les pixels à une distance de 1 dans la file d'attente.
On va pouvoir traiter ces pixels là. On sait également que leurs voisins sont à une distance de 2, et pourront donc être traités lorsque les pixels à distance 1 seront associés à un bassin.

Les voisins non-traités des pixels à une distance de 1 sont donc les prochains pixels de l'étage à traiter.
Ils sont placés dans une autre file d'attente, qui sera parcourue une fois que la première a été entièrement utilisée.

Ensuite, les voisins des pixels à une distance de 2 seront les prochains pixels à traiter, et on va recommencer cette suite d'opérations.

Voici un exemple de la manière dont les pixels sont placés dans la file d'attente :

* Tout d'abord les pixels directement voisins d'un bassin connu sont placés dans la file d'attente

[[File:file_1.png|500px]] [[File:file_legende.png|200px]]

* Puis une fois que les pixels dans la file d'attente ont été traités, les pixels voisins des pixels qui viennent d'être traités sont placés dans la file d'attente

[[File:file_2.png|500px]] [[File:file_legende.png|200px]]

* Cette étape se répète tant qu'il y a des pixels dans la file d'attente

[[File:file_3.png|500px]] [[File:file_legende.png|200px]]

Ainsi le traitement d'une file d'attente (file d'attente d'une distance particulière) fait avancer d'un pixel tous les bassins, et tous les bassins progressent à la même vitesse.

==== Détermination du bassin auquel appartient un pixel ====

Avec cette manière de faire progresser les bassins, le bassin auquel appartient un pixel est déterminé par les bassins auxquels appartiennent ses voisins.

Plusieurs cas sont alors possibles lorsqu'un pixel est traité.

[[File:choix_label.png]]

*Un des cas les plus simples est lorsque tous les voisins traités du pixel appartiennent au même bassin.Le bassin s'étend alors, et le pixel à traiter est associé au bassin auquel appartiennent ses voisins.

*Cette même décision est prise si tous les pixels voisins traités appartiennent au même bassin sauf certains qui appartiennent à une ligne de partage des eaux (LPE). L'autre décision possible est de prolonger la LPE, cependant des lignes épaisses (et imprécises) seraient créées.

*Si les pixels voisins traités du pixel appartiennent à une LPE, le bassin auquel appartient le pixel est inconnu. On ne peut pas "prolonger" la ligne car on ne connaît alors pas à quelle distance d'un bassin se trouve le pixel. Si un pixel appartient à une LPE, ses voisins ne sont donc pas placés en file d'attente.

*Lorsque les pixels voisins appartiennent à des bassins différents, alors le pixel appartient à une LPE ; on sépare les bassins au moment de leur rencontre.

*Le dernier cas se présente lorsque tous les pixels voisins sont traités et qu'ils appartiennent tous à une LPE. Pour éviter qu'un bassin d'un seul pixel soit créé, on prolonge la LPE.

En résumé :
*S'il n'y a qu'un seul bassin autour du pixel en excluant les LPE, le pixel appartient à ce bassin.
*Si en excluant les LPE il y a plusieurs bassins autour du pixel, le pixel appartient à une LPE.
*Si le pixel est entouré par des LPE, alors il appartient à une LPE.

==== Création de nouveaux bassins ====

Lors de la propagation des bassins, si une file d'attente est vide alors tous les pixels de l'étage qui appartenaient à un bassin déjà connu ont été traités.

Les pixels restants appartiennent donc à de nouveaux bassins.

Un nouveau bassin est donc créé, le premier pixel qui lui appartient est choisi parmi un des pixels de l'étage non-traités.

On réinitialise alors la file d'attente, et on place les voisins non-traités du pixel associé au nouveau bassin dedans.

On recommence alors le traitement de la file d'attente, et tous les pixels qui appartiennent à ce bassin lui seront attribués.

Voici un exemple de la manière dont les nouveaux bassins sont créés, sur une petite image de 5x5.

[[File:minima_image.png|300px]]

Plusieurs étapes se déroulent alors :

* Le traitement d'un étage commence. Les pixels appartenant à un bassin connu se situent à un étage inférieur.

[[File:minima_1.png|300px]] [[File:minima_legende.png|500px]]

* Tous les pixels appartenant à un bassin connu ont été traités ; il reste cependant des pixels non-traités à cet étage. Ils appartiennent donc à un ou plusieurs nouveaux bassins. On choisit donc un pixel non-traité de l'étage, et on lui attribue un nouveau bassin.

[[File:minima_2.png|300px]] [[File:minima_legende.png|500px]]

* On propage le nouveau bassin créé.

[[File:minima_3.png|300px]] [[File:minima_legende.png|500px]]

Ces étapes sont répétées tant qu'il reste des pixels non-traités à l'étage en cours de traitement. On détecte ainsi tous les nouveaux bassins de l'étage.

Une fois que tous les pixels d'un étage ont été traités, on passe à l'étage supérieur.

==== Résultats ====
Voici un exemple de résultat que donne cet algorithme :

[[File:lpe_brute.png]]''A gauche le gradient d'une image ; à droite le résultat de l'algorithme de détermination des LPE''

On s'aperçoit que l'algorithme est très sensible au bruit, c'est à dire aux légères variations d'intensité qui créent des minima locaux.

On veut donc améliorer les résultats obtenus.

=== Réduire l'impact du bruit ===
Plusieurs méthodes sont applicables pour réduire l'impact du bruit sur le résultat.

==== Ajout d'une tolérance ====
La plus efficace est d'ajouter une "tolérance".

En effet, dans l'algorithme décrit précédemment, les pixels appartiennent à un même étage si leurs intensités sont exactement identiques.

On considére qu'un pixel appartient à l'étage traité si la différence entre son intensité et l'intensité de l'étage traitée est inférieure à un nombre, qu'on appelle tolérance.

Ainsi la sensibilité au bruit de l'algorithme est réduite car les petites variations d'intensité ne créent plus de nouveaux bassins.

Voici un exemple sur une petite image.

[[File:lpe_tolerance_image.png]]

Tout d'abord, s'il n'y a pas de tolérance, les pixels d'intensité 130 et le pixel d'intensité 135 sont à des étages différents.
Deux bassins sont donc créés lors du traitement de l'étage d'intensité 130 (bleu et vert, le noir représente une LPE).

[[File:lpe_sans_tolerance.png]]

Cependant, avec l'ajout d'une tolérance (par exemple 10), les trois pixels sont considérés au même étage (car on a 135-130 < 10).

[[File:lpe_tolerance.png]]

Ainsi une unique bassin est créé.

Le résultat est alors bien plus précis sur de vraies images:

[[File:lpe_res_tolerance.png]] ''A gauche le résultat (de cette [[#Résultats|image]]) de l'algorithme sans tolérance, à droite le résultat avec une tolérance de 5''

==== Flouter l'image avant le traitement ====

Une deuxième méthode est de traiter l'image avant d'appliquer l'algorithme.
Si l'image est floutée avant application de l'algorithme, le bruit aura moins d'impact, car les changements de valeur seront atténués.
Dans l'image floutée, chaque valeur d'un pixel est une moyenne des valeurs des pixels voisins à ce pixel dans l'image originale.

Pour cela, on peut convoluer l'image par cette matrice :

[[File:lpe_flou.png|200px]]

Chaque produit de convolution donnera un entier qui devra être divisé par 9 ; on ajoute les valeurs des 9 pixels dans un carré de 3x3 autour du pixel dont on veut la nouvelle valeur, pour avoir la moyenne des valeurs dans ce carré on doit alors diviser par 9.

Cette méthode ne donne pas de bons résultats si elle est la seule utilisée. Cependant, combinée avec l'utilisation de la tolérance, le nombre de petites zones est fortement réduit.

Les LPE sont en contrepartie moins précises.

Exemple de résultat :

[[File:lpe_flou_tolerance5.png]]

==== Fusion des petites zones ====

Une troisième solution est d'empêcher la création de zones trop petites, en indiquant une taille minimale.
Si des bassins plus petits que cette taille rencontrent un autre bassin, alors ils fusionnent, et le point de leur rencontre est associé à ce nouveau bassin issu de la fusion.

Si au point de rencontre des bassins se rencontrent deux zones plus grandes que la taille minimale, on doit tout de même placer une LPE, pour séparer les deux "grands" bassins.

Cette méthode ne donne pas non plus de résultats intéressants si utilisée seule, il est nécessaire de la combiner avec l'ajout d'une tolérance.

Un des résultats obtenus avec cette méthode est (où la taille minimale d'un bassin est de 5px) :

[[File:lpe_fusion5.png]]

== Conclusion ==

Pour conclure, on peut citer deux avantages de cet algorithme. Tout d'abord, les lignes de partage des eaux créées sont peu épaisses ; elles ne font jamais plus de 3 pixels de large, et se limitent dans la plupart des cas à une épaisseur d'un seul pixel.

Ensuite, l'algorithme est de complexité linéaire, c'est à dire que le temps d’exécution dépend linéairement du nombre de pixels de l'image sur laquelle on applique l'algorithme.
Voici quelques mesures du temps d'exécution selon le nombre de pixels de l'image en entrée (les images utilisées pour ces tests ne représentent rien et contiennent de nombreuses zones).

[[File:lpe_tableau_temps.png|border|mesures du temps d'exécution]]
[[File:lpe_temps.png|border|temps d'exécution en fonction du nombre de pixels]]

== Code source ==
Voici le code source de l'algorithme.

Pour manipuler des images, j'ai utilisé la bibliothèque PILLOW.

Les principales fonctions utilisées dans cette bibliothèque sont :
*Image.open(fichier) : ouvrir le fichier fichier en tant qu'objet image
*image.getpixel((x,y)) : récupérer la valeur du pixel aux coordonnées (x,y) dans un objet Image (appelé ici 'image')
*image.setpixel((x,y),(r,v,b)) : Changer la valeur du pixel aux coordonnées (x,y) dans un objet Image (appelé ici 'image') ; (r,v,b) sont les valeurs rouge,vert,bleu.
*image.save(nom) : sauvegarder l'image sous le nom souhaité.

<pre>
###########################################################
# RUET Nils
# Algorithme de détermination de ligne de partage des eaux, créé par Luc Vincent et Pierre Soille
#

########################################################################################################
# IMPORTATIONS
########################################################################################################

from PIL import Image
from math import sqrt
from random import randint

########################################################################################################
# CONSTANTES ET VARIABLES GLOBALES
########################################################################################################

#Chaque pixel a 3 valeurs qui lui sont associées ; son intensité, l'information sur s'il a déjà été placé en file d'attente, et le label qui lui a été associé.
#Ces informations sont stockés dans un tableau et ces constantes sont les indices auxquels trouver les informations voulues.
VALEUR = 0
LABELLED = 1
LABEL = 2

indiceEtage = 0# Lorsque l'on traite un étage, certains pixels ne sont pas traitables à partir des données connues. Ils correspondent à de nouveaux bassins.
# On dispose d'une liste des pixels de l'étage ; lorsqu'on doit créer un bassin, on cherche donc le premier pixel dans cette liste qui n'est pas labellé.
# Cette variable contient le nombre de pixels "consécutifs" traités, c'est à dire l'indice du dernier pixel non traité trouvé dans la liste.
# Ainsi on n'a pas à reparcourir la liste entière lorsque l'on créé plusieurs nouveaux bassins à un étage car on sait que tous les pixels "avant" (dans la liste) celui choisi pour créer un nouveau bassin ont été labellés.

########################################################################################################
# CALCUL DU GRADIENT
########################################################################################################

def deterCoef(mat):
"""Cette fonction prend un masque de convolution en entrée. Elle permet de déterminer un décalage et un coefficient utilisés pour ramener toutes les valeurs
obtenues après convolution entre 0 et 255"""
sommeP=0
sommeN=0
for i in range(len(mat)): #On compte les coefficients négatifs et les coefficients positifs dans le masque
for j in range(len(mat[0])):
if mat[i][j] > 0:
sommeP+=mat[i][j]
else:
sommeN-=mat[i][j]
decal = sommeN * 255 #Les coefficients négatifs permettent de connaître la valeur à ajouter pour n'obtenir que des valeurs positives après la convolution
coef = sommeN+sommeP #La somme des valeurs absolues des coefficients permet de savoir comment ramener toutes ces valeurs entre 0 et 255.
return (coef, decal)

def Convolution(image, x, y, filtre):
"""Effectue le produit de convolution entre un filtre et l'enourage du pixel aux coordonnées (x,y) dans l'image 'image' """
somme = 0
centre = len(filtre)//2
for i in range(-centre,centre+1): #i et j indiquent la position relative du pixel dont on a besoin dans l'image par rapport au pixel dont on calcule la nouvelle valeur.
for j in range(-centre,centre+1):
if filtre[i+centre][j+centre] != 0: #Vu qu'on multiplie la valeur d'un pixel par une valeur dans le filtre, on vérifie que la valeur dans le filtre ne vaut pas 0.
if 0<=x+i<image.width and 0<=y+j<image.height: #Si le pixel voulu est dans l'image, xl (x local) et yl (y local) sont ses coordonnées.
xl = x+i
yl = y+j
else: #Sinon on va chercher la valeur du pixel en symlétrie par rapport au pixel dont on veut la nouvelle valeur
xl = x-i
yl = y-j

if not 0<=xl<image.width or not 0<=yl<image.height: #Si après cela le pixel n'est toujours pas dans l'image, on se réfère à la valeur du pixel dont on veut la nouvelle valeur.
xl = x
yl = y
somme+= (image.getpixel((xl,yl))[0] *filtre[i+centre][j+centre])
return somme

def AppliqueFiltre(image, filtre):
"""Permet d'appliquer le masque de convolution 'filtre' (double tableau) à tous les pixels de l'image 'image' """
res = image.copy()
(coef, decal) = deterCoef(filtre)
for x in range(image.width): #Pour chaque pixel de l'image
for y in range(image.height):
somme = Convolution(image,x,y,filtre) #On prend le résultat de la convolution
val = round((somme+decal)/coef) #On ramène ce résultat entre 0 et 255
res.putpixel((x,y),(val,val,val)) #On met le pixel dans l'image résultat à cette valeur
return res

def Filtre(image, filtre, nom_sortie="filtre", saveIm=True):
"""Permet d'appeler la fonction qui permet de convoluer l'image 'image' par le masque 'filtre' et choisir si le résultat est sauvegardé dans un fichier image ou non"""
res = AppliqueFiltre(image, filtre)
if saveIm:
res.save("{}_{}".format(nom_sortie, fichierImage))
return res

def FiltreSobel(fichierIm):
"""Permer de calculer la norme du gradient de l'image 'fichierIm' (nom du fichier image) en chaque point avec la méthode du filtre de Sobel"""
image = Image.open(fichierIm)
res = image.copy()
masquex = [[-1,0,1],[-2,0,2],[-1,0,1]]
masquey = [[-1,-2,-1],[0,0,0],[1,2,1]]
for x in range(image.width): #Pour chaque pixel de l'image
for y in range(image.height):
dx = Convolution(image,x,y,masquex) #On approxime ses dérivées partielles
dy = Convolution(image,x,y,masquey) #

val = round(sqrt(dx**2 + dy**2)*255/(sqrt(2)*1020)) #On calcule la norme du gradient, qu'on ramène entre 0 et 255.
res.putpixel((x,y),(val,val,val)) #Cette valeur est associée au pixel dans le résultat
return res

#########################################################################################################
# ALGORITHME LIGNE DE PARTAGE DES EAUX
#########################################################################################################

def InitTableau(image):
"""Initialise le double tableau contenant les informations sur chaque pixel; aux indices [x][y] on accède aux informations du pixel (x,y). Ces informations sont l'intensité, l'avancement du traitement et le label."""
tableau = [0]*image.width #On initialise un tableau de la taille de l'image
for i in range(len(tableau)):
tableau[i]=[0]*image.height

for i in range(len(tableau)): #On initialise les informations de chaque pixel :
for j in range(len(tableau[i])):
tableau[i][j] = [image.getpixel((i,j))[0],False,"init"] #Sa valeur dans l'image, l'avancement du traitement (False si le pixel n'a pas été traité, True sinon), et le label qui lui est associé
return tableau

def InitListeOrdonnee(image):
"""Initialise la liste des pixels de l'image, triés par intensité ; chaque case contient la position du pixel attribué et son intensité"""
liste = []
for i in range(image.width):
for j in range(image.height):
liste.append([image.getpixel((i,j))[0],i,j])#On regarde chaque pixel de l'image et on ajoute dans une case de la liste son intensité, son abcisse, son ordonnée
liste.sort(key=lambda pixel: pixel[0]) #On trie cette liste en fonction de l'intensité des pixels (ordre croissant)
return liste

def PixelsEtage(listeOrdonnee, intensite, indice, tablImage, tolerance):
"""Prend en entrée la liste ordonnée des pixels de l'image, une intensité, l'indice à partir duquel commence cette intensité dans la liste, et une tolérance.
Renvoie la liste des pixels d'un "étage" d'intensité, plus précisément :
La liste des pixels non-labellés de l'intensité choisie plus ou moins la tolérance donnée. L'indice à partir duquel commence l'intensité choisie est modifié par une autre partie
du programme ; on sait que tous les pixels d'une valeur inférieure à l'intensité choisie ont déjà été traités par l'algorithme."""
pixels = []
nouvelIndice = indice
while nouvelIndice < len(listeOrdonnee) and (listeOrdonnee[nouvelIndice][0] - intensite) <= tolerance:#On ajoute à la liste des pixels de l'étage intensité les pixels qui ont une intensité dans l'intervalle souhaité
if not tablImage[listeOrdonnee[nouvelIndice][1]][listeOrdonnee[nouvelIndice][2]][LABELLED]: #Et non labellés
pixels.append(listeOrdonnee[nouvelIndice])
nouvelIndice+=1
return pixels

def labelsPixelsVoisins(x, y, tablImage):
"""Fonctions qui renvoie la liste des labels des pixels voisins au pixel situé aux coordonnée entrées en paramètre, ignore les pixels non labellés"""
labels = []

voisins = [(-1,0),(1,0),(0,-1),(0,1)]
for coords in voisins:
i = coords[0]
j = coords[1]
if 0<=x+i<len(tablImage) and 0<=y+j<len(tablImage[0]) and tablImage[x+i][y+j][LABEL] != "init":
labels.append(tablImage[x+i][y+j][LABEL])
return labels

def PixelTraitable(xPixel, yPixel, tablImage):
"""Fonction qui renvoie True si le pixel aux coordonnées entrées en paramètre est labellable, False sinon"""
labels = labelsPixelsVoisins(xPixel, yPixel, tablImage)
for label in labels:
if label!="watershed":#Un pixel est labellable s'il a un pixel labellé par autre chose qu'une ligne de partage parmi ses voisins.
return True

voisinsDansImage = 0 #Sinon si le pixel n'a pas de pixels labellés par autre chose que watershed parmi ses voisins,
voisins = [(-1,0),(1,0),(0,-1),(0,1)]
for coords in voisins: #On détermine son nombre de voisins (4 au centre, 3 sur les bords et 2 dans les coins)
i = coords[0]
j = coords[1]
if 0<=xPixel+i<len(tablImage) and 0<=yPixel+j<len(tablImage[0]):
voisinsDansImage += 1
return len(labels)==voisinsDansImage #Le pixel est labellable si tous ses voisins sont des lignes de partage des eaux

def nouveauLabel(listePixels, tablImage, fileAttente, listeLabels, intensite, tolerance):
"""Cette fonction est appelée lorsque l'algorithme n'a pas traité tous les pixels d'un étage, mais qu'aucun pixel n'a été placé en file attente <=> aucun pixel non traité n'est traitable à cet étage.
A partir de la liste des pixels de l'étage, de la liste des labels attribués, de l'intensité de l'étage et de la tolérance, on modifie alors la file d'attente"""
global indiceEtage
while tablImage[listePixels[indiceEtage][1]][listePixels[indiceEtage][2]][LABELLED]: #On parcourt la liste des pixels de l'étage pour en trouver un non labellé
indiceEtage+=1
x = listePixels[indiceEtage][1]
y = listePixels[indiceEtage][2]
voisins = [(-1,0),(1,0),(0,-1),(0,1)]
for coords in voisins: #On regarde les voisins du premier pixel non labellé trouvé
i = coords[0]
j = coords[1]
if 0<=x+i<len(tablImage) and 0<=y+j<len(tablImage[0]) and not tablImage[x+i][y+j][LABELLED] and (tablImage[x+i][y+j][VALEUR] - intensite) <= tolerance:
#Si un voisin est dans le bon intervalle d'intensité, non labellé et dans l'image, alors on le place dans la file d'attente
tablImage[x+i][y+j][LABELLED] = True
fileAttente[0].append([tablImage[x+i][y+j][VALEUR], x+i, y+j])

tablImage[x][y][LABEL] = len(listeLabels)#On créé un nouveau label en augmentant de 1 le numéro du dernier label ; cela correspond à la longueur de la liste des labels
#Puis on l'associe au pixel non traité trouvé dans l'étage
tablImage[x][y][LABELLED] = True #Ce pixel et désormais traité
listeLabels.append(1) #On ajoute le nouveau label créé à la liste des labels ; le bassin associé à ce label est de taille 1px initalement
return fileAttente #On renvoie la nouvelle file d'attente ; les voisins traitables du pixel trouvés

def AjoutFileAttente(fileAttente, distance, tablImage,intensite,tolerance):
"""A partir des pixels traités au moment de l'appel de cette fonction, on détermine les prochains pixels qui pourront être traités par la suite.
Ces pixels sont les voisins des pixels déjà traités (à l'exception des lignes de partage) du même étage, non traités et dans l'image"""
fileAttente.append([]) #On ajoute une file d'attente pour la distance suivante
for pixel in fileAttente[distance]:#Pour chaque pixel traité à la distance précédente
x = pixel[1]
y = pixel[2]
if tablImage[x][y][LABEL] != "watershed":#S'il n'est pas une ligne de partage, il appartient à un bassin et ses voisins sont potentiellement traitables
voisins = [(-1,0),(1,0),(0,-1),(0,1)]
for coords in voisins:
i = coords[0]
j = coords[1]
if 0<=x+i<len(tablImage) and 0<=y+j<len(tablImage[0]):
if (tablImage[x+i][y+j][VALEUR] - intensite) <= tolerance and not tablImage[x+i][y+j][LABELLED]:#Les voisins traitables sont les pixel du même étage non labellés
tablImage[x+i][y+j][LABELLED] = True
fileAttente[distance+1].append([tablImage[x+i][y+j][VALEUR], x+i, y+j])#On les ajoute à la file d'attente suivante

def valeursUniques(T):
"""Prend un tableau en entrée et supprime les valeurs qui s'y trouvent en double"""
res = []
for e in T:
if not e in res:
res.append(e)
return res

def fusionZones(labelsChange, nouvLabel, listeLabels, x, y, tablImage):
""" A partir d'une liste de labels à changer (labelsChange), du nouveau label qui leur sera associé, et d'un pixel de départ aux coordonnées x,y
On fusionne les bassins qui se rencontrent en x,y en modifiant le label des pixels de ces bassins.
Chaque fois qu'un pixel change de label, on change le label de ses voisins si cela est nécéssaire
"""
tablImage[x][y][LABEL] = nouvLabel
voisins = [(-1,0),(1,0),(0,-1),(0,1)]

file = [[x,y]]
indiceFile = 0
while indiceFile != len(file):#Tant que tous les pixels de la file n'ont pas été associés au nouveau label
pixel = file[indiceFile] #On prend le prochain pixel dans la file
for coords in voisins: #Et on regarde chacun de ses voisins
i = coords[0]
j = coords[1]
if 0<=pixel[0]+i<len(tablImage) and 0<=pixel[1]+j<len(tablImage[0]) and (tablImage[pixel[0]+i][pixel[1]+j][LABEL] in labelsChange): #Si un pixel voisins dans l'image a un label qui doit être changé
file.append([pixel[0]+i,pixel[1]+j])#On l'ajoute à la file
tablImage[pixel[0]+i][pixel[1]+j][LABEL] = nouvLabel#On lui attribue son nouveau label
listeLabels[nouvLabel]+=1#On augmente le nombre de pixels qui appartiennent au nouveau bassin
indiceFile+=1

def determinationLabels(fileAttente, distance, tablImage, listeLabels, tailleMini):
"""Procédure qui détermine le label attribué à un pixel en fonction des labels des pixels voisins"""
for pixel in fileAttente[distance]: #On attribue un label à chaque pixel dans la file d'attente
labels = labelsPixelsVoisins(pixel[1], pixel[2], tablImage) #On récupère les labels de ses voisins
lstLabels = valeursUniques(labels) #On supprime les doublons,
if ("watershed" in lstLabels): #et le label de ligne de partage des eaux
lstLabels.remove("watershed")

voisinsDansImage = 0
voisins = [(-1,0),(1,0),(0,-1),(0,1)]
for coords in voisins: #On compte le nombre de pixels voisins dans l'image ; 4 si le pixel est au centre de l'image, 3 s'il est au bord etc.
i = coords[0]
j = coords[1]
if 0<=pixel[1]+i<len(tablImage) and 0<=pixel[2]+j<len(tablImage[0]):
voisinsDansImage += 1
if len(lstLabels) == 0 and len(labels)==voisinsDansImage: #Si le pixel est entouré de watershed, on lui attribue ce label
tablImage[pixel[1]][pixel[2]][LABEL] = "watershed"

elif len(lstLabels) == 1: #Si le pixel n'a qu'un seul label hormis les watershed autour de lui, on lui attribue ce label
tablImage[pixel[1]][pixel[2]][LABEL] = lstLabels[0]
listeLabels[lstLabels[0]] += 1

elif len(lstLabels) > 1: #S'il y a plusieurs labels autour de lui, il se trouve entre deux bassins et est donc une ligne de partage des eaux ; si les bassins sont petits on les fusionne
i = 0
plusGrand = []
moinsGrand = []
while i<len(lstLabels):
if listeLabels[lstLabels[i]]>tailleMini:
plusGrand.append(lstLabels[i])
else:
moinsGrand.append(lstLabels[i])
i+=1
if len(moinsGrand)>0 and len(plusGrand)<2: #Si des bassins sont en dessous de la taille minimale et qu'il n'y a pas plusieurs bassins au dessus de cette taille
if len(plusGrand)==1: #Si il n'y a qu'un bassin au dessus, tous les petits bassins lui seront rattachés
labelsChange = moinsGrand[:]
nouvLabel = plusGrand[0]
elif len(plusGrand)==0: #S'il n'y en a aucun, les petits bassins fusionnent entre eux
labelsChange = moinsGrand[1:]
nouvLabel = moinsGrand[0]

tablImage[pixel[1]][pixel[2]][LABEL] = nouvLabel #Les bassins vont fusionner, le pixel que l'on regardait appartient donc au nouveau bassin
listeLabels[nouvLabel] += 1 #On augmente le compteur de pixels appartenant à ce bassin

voisins = [(-1,0),(1,0),(0,-1),(0,1)]
for coords in voisins: #On regarde chaque voisin, s'il est dans l'image et que son label doit etre changé, on appelle la procédure qui permet de changer les labels du bassin
i = coords[0]
j = coords[1]
if 0<=pixel[1]+i<len(tablImage) and 0<=pixel[2]+j<len(tablImage[0]) and tablImage[pixel[1]+i][pixel[2]+j][LABEL] in labelsChange:
fusionZones(labelsChange, nouvLabel, listeLabels, pixel[1]+i, pixel[2]+j, tablImage)

else: #Si aucun bassin n'est trop petit ou si au moins 2 sont au dessus de la taille minimale, le pixel est une ligne de partage des eaux
tablImage[pixel[1]][pixel[2]][LABEL] = "watershed"

def Algo(image, tolerance, tailleMini):
global indiceEtage

#### INITALISATION ###

#Initaliser tableaux :
# -double tableau qui contient les informations de chaque pixel
tableauImage = InitTableau(image)

# -la liste des labels
listeLabels = []

# -Initialiser la liste des pixels triée par leur intensité
listePixelsOrdonnee = InitListeOrdonnee(image)

# -l'indice de parcours de la liste des pixels triée
indice = 0

### TRAITEMENT POUR CHAQUE INTENSITE ###
for intensite in range(256):
#Initialiser la liste des pixels appartenant à l'étage traité
pixelsMemeEtage = PixelsEtage(listePixelsOrdonnee, intensite, indice, tableauImage, tolerance)

indice += len(pixelsMemeEtage)#On connaît le nombre de pixels de cet étage, on en déduit l'indice où commencera le prochaine étage
indiceEtage = 0 #Initialisation du compteur de pixels "consécutifs" traités à cet étage
compteurPxTraites = 0 #Compteur du nombre de pixels traités à cet étage

# Initialiser la file d'attente :
# La file d'attente est une liste de listes de pixels ; chaque sous-liste correspond à une distance, une étape du traitement
# Les premiers pixels traités sont collés à un pixel déjà labellé ; leurs voisins seront traitables par la suite
# et sont donc mis dans la file d'attente "suivante". Ils sont à une "distance" supérieure, et seront traités après le traitement de la distance actuelle
# C'est avec ce principe qu'on forme la file d'attente.
fileAttente=[[]]

# On fait d'abord un parcours de l'étage, pour trouver les pixels collés à des pixels labellés lors du traitement d'étages précédents
for pixel in pixelsMemeEtage:
# Pour chaque pixel de l'étage, on regarde ses voisins, si au moins un est labellé, le pixel est à distance 0, c'est à dire traitable directement.
if PixelTraitable(pixel[1],pixel[2], tableauImage):
#Si c'est le cas on l'ajoute à la file d'attente
fileAttente[0].append(pixel)
tableauImage[pixel[1]][pixel[2]][LABELLED] = True

#On initialise le numéro de l'étape du traitement, la distance : elle commence à 0 et augmente à chaque tour de boucle
distance = 0

while len(pixelsMemeEtage) > compteurPxTraites: #Tant que le nombre de pixels de cet étage traités est inférieur au nombre de pixels de l'étage, on a pas traité tout l'étage.

if len(fileAttente[distance])==0: #On regarde s'il y a des pixels dans la file d'attente
fileAttente = nouveauLabel(pixelsMemeEtage, tableauImage, fileAttente, listeLabels, intensite, tolerance) #Si non alors il n'y a plus aucun bassin connu à cet étage, on en ajoute:
compteurPxTraites += 1 #On sait qu'un pixel a été traité en ajoutant un nouveau bassin (le premier pixel du bassin), on l'ajoute au compteur

else: #Si il y a des pixels à traiter on les traite
while len(fileAttente[distance]) > 0: #avec ces nouvelles informations de nouveaux pixels seront traitables.
#On continue ces actions jusqu'à qu'aucun pixel ne soit traitable

determinationLabels(fileAttente, distance, tableauImage, listeLabels, tailleMini) #On commence par déterminer les labels des pixels traitables
AjoutFileAttente(fileAttente, distance, tableauImage, intensite, tolerance) #On ajoute les pixels désormais traitable dans la file d'attente qui sera parcourue au prochain tour de boucle
compteurPxTraites+=len(fileAttente[distance]) #Tous les pixels de la file d'attente à cet étape ont été traités ; on augmente le compteur en conséquence
distance +=1 #On passe à l'étape suivant de l'algorithme / la nouvelle file d'attente

distance = 0 #Une fois que la boucle est terminé, on a labellé tous les pixels possibles à cet étage qui n'appartiennent pas à un nouveau bassin
fileAttente = [[]] #On réinitialise la file d'attente pour refaire le même traitement avec un nouveau bassin

#Si tous les pixels de l'étage n'ont pas été traités, alors on va ainsi créer un nouveau bassin et le propager, jusqu'à que tous les pixels de l'étage aient été traités.

return AffichageImage(tableauImage, image, listeLabels)#On enregistre les résultats du traitement dans une image

def AffichageImage(tableauImage, image, listeLabels):
"""Fonction qui prend le résultat de l'algorithme sur le fichier fichier et le convertit en image ;
Les pixels des lignes de partage des eaux sont affichés en noir, et chaque label est associé à une couleur.
On enregistre ensuite cette image."""
lpe = image.copy()
couleurs = [0]*len(listeLabels)
for e in range(len(couleurs)):
couleurs[e] = (randint(100,200),randint(100,200),randint(100,200))
for i in range(image.width):
for j in range(image.height):
if tableauImage[i][j][LABEL] == "watershed":
lpe.putpixel((i,j),(0,0,0))
else:
lpe.putpixel((i,j),couleurs[tableauImage[i][j][LABEL]])
return lpe

########################################################################################################
# UTILISATION
########################################################################################################

def LPE(fichierImage, saveGradient=False, tolerance=0, flou=False, tailleMini=0, fichierGradient="none"):
"""Prend un fichier image en entrée et calcule son gradient,
avant d'appliquer l'algorithme de détermination de ligne de partage des eaux

l'option "saveGradient" est un booléen qui permet d'enregistrer le gradient de l'image si souhaité

l'option fichierGradient permet d'éxécuter uniquement la détermination de la LPE sur un fichier.
On peut donc appliquer la deuxième partir de l'algorithme sur une image gradient déjà calculée.

D'autres options sont disponibles, qui permettent de réduire la sensibilité au bruit de l'algorithme
- tolerance : entier ; deux pixels seront traités comme appartenant au même "étage"
si cet entier est plus grand que la différence de leurs valeurs
- flou : booléen qui si vaut vrai, applique un flou sur l'image de départ afin de diminuer
l'impact du bruit sur le résultat
- tailleMini : entier ; au moment où plusieurs zones se rencontrent, si cela est possible,
on fusionne les zones de taille inférieure (la taille est le nombre de pixels associés à la zone) à cet entier. Cela permet la supression des petites zones.

Les options réduisant la sensibilité au bruit peuvent rendre le résultat imprécis en fonction de leurs valeurs

Le résultat est sauvegardé sous forme d'image, où chaque zone est associée à une couleur et où les lignes de partage des eaux sont en noir."""

if fichierGradient == "none":
gradient = FiltreSobel(fichierImage)
if saveGradient:
gradient.save("gradient_{}".format(fichierImage))
else:
gradient = Image.open(fichierGradient)
if flou:
gradient = Filtre(gradient, [[1,1,1],[1,1,1],[1,1,1]], saveIm=False)
lpe = Algo(gradient, tolerance, tailleMini)

nom = "lpe_"
if flou:
nom+="flou_"
if tolerance!=0:
nom+="tolerance-{}_".format(tolerance)
if tailleMini!=0:
nom+="mini-{}_".format(tailleMini)
nom += "{}".format(fichierImage)
lpe.save(nom)
</pre>

== Sources ==
*[https://fr.wikipedia.org/wiki/Segmentation_d%27image Segmentation d'image]
*[https://fr.wikipedia.org/wiki/Filtre_de_Sobel Filtre de Sobel]
*[https://fr.wikipedia.org/wiki/Ligne_de_partage_des_eaux Ligne de partage des eaux (géographie)]
*[https://en.wikipedia.org/wiki/Watershed_(image_processing) Algorithmes existants pour calculer des lignes de partage des eaux (segmentation)]
*[https://pdfs.semanticscholar.org/a381/9dda9a5f00dbb8cd3413ca7422e37a0d5794.pdf Algorithme de Luc Vincent et Pierre Soille]

== Annexes ==
*[https://pillow.readthedocs.io/en/5.1.x/ Bibliothèque de manipulation d'image utilisée (PILLOW)]

Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

2018-05-26T19:14:42Z

Ruet :

Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

2018-05-26T19:11:52Z

Ruet :

== Introduction ==

La segmentation d'image est une famille dans le traitement d'image qui consiste à regrouper des pixels d'une image selon certaines de leurs caractéristiques.

On va ici utiliser un algorithme appelé "ligne de partage des eaux" sur des images en niveaux de gris.
Dans cet algorithme on utilise deux approches de la segmentation d'image, la segmentation par détection de contours et la segmentation par détection de régions. Deux étapes principales constituent donc l'algorithme.
La première est de représenter l'image en fonction de l'intensité de ses variations, on met ainsi en valeur les fortes variations de valeur dans l'image, donc les potentiels contours. La deuxième est de regrouper les zones dans cette nouvelle image par homogénéité, on détecte ainsi des régions dans l'image.

== Première étape : Approximation du gradient d'une image==
=== Image et notion de gradient d'une image ===
==== Image ====
Une image est un ensemble de points associés à une couleur.
Pour afficher une couleur, on combine une intensité de lumière rouge, une intensité de lumière verte et une intensité de lumière bleue.
Dans une image couleur chaque pixel est donc associé à 3 valeurs, les intensités de ces couleurs.
Ces intensités sont généralement codées sur 8 bits, donc comprises entre 0 et 255.

Ici, l'image traitée est une image en niveaux de gris. Une couleur est perçue comme un niveau de gris lorsque les intensités de lumière rouge, de lumière verte et de lumière bleue sont identiques.
Ainsi chaque point est décrit par ses coordonnées et associé à une seule valeur (entre 0 et 255) dans les images que l'algorithme pourra traiter.

D'un point de vue mathématique on peut considérer que l'image est une fonction de R*R vers R : on prend un couple de réels (les coordonnées) auquel un autre réel est associé (un niveau de gris).

==== Gradient ====

Pour réaliser la segmentation d'une image par détection de contour, la première étape est de représenter les variations de valeur dans l'image.
Si l'image est une fonction, et qu'elle est considérée différentiable, il est possible d'utiliser le gradient pour déterminer les variations de valeur en chaque point.

Le gradient d'une fonction est un vecteur qui représente les variations de la fonction par rapport à ses différents paramètres.

La direction et le sens du gradient indiquent le sens dans lequel la fonction varie le plus et sa norme indique l'intensité de la variation.

Ainsi, plus la norme du gradient est élevée en un point, plus les variations "autour" du point sont élevées.

Les coordonnées du gradient sont les dérivées partielles en fonction de chacun des paramètres de la fonction. Si les deux paramètres d'une fonction de R*R vers R sont appelés x et y, on aura en première coordonnée la dérivée partielle de la fonction selon x et en deuxième coordonnée la dérivée partielle de la fonction selon y.

Pour calculer les dérivées partielles de la fonction, il est nécéssaire de pouvoir connaître ses valeurs en chaque point.
Hors dans notre cas, les valeurs de la fonction image ne sont connues qu'en certains points, qui sont "distincts" entre eux.

Le gradient n'est donc pas calculable, cependant il est possible d'en avoir une approximation.

=== Filtre de Sobel ===

Le filtre de sobel est un opérateur permettant d'approximer le gradient de chacun des points de l'image.

Cet opérateur utilise des masques de convolution.

L'application des masques de convolution dans une image est lié au produit de convolution, un opérateur mathématique dont je parlerai pas car je ne connais que peu le sujet.

Pour obtenir la nouvelle valeur d'un pixel, on va convoluer la région "autour" du pixel avec un masque.

Le filtre de Sobel utilise deux masques, pour calculer chaque dérivée partielle.

[[File:sobel_x.png|border|100px]] ''Masque utilisé pour approximer la dérivée partielle en x''

[[File:sobel_y.png|border|100px]] ''Masque utilisé pour approximer la dérivée partielle en y''

==== Utilisation des masques de convolution ====

Pour chaque convolution, on utilise le masque et l'entourage d'un pixel dont on veut calculer la valeur.

Exemple, on veut calculer ici la nouvelle valeur du pixel entouré de rouge :

[[File:Convolution_pixel.png|exemple d'utilisation du produit de convolution]]

Chaque valeur d'un pixel "autour" du pixel dont on veut la nouvelle valeur est multipliée par la valeur correspondante dans le masque.

Dans ce cas pour obtenir une approximation de la dérivée partielle selon x, on devrait diviser par 8 le résultat (on utilise 8 valeurs parmi les pixels voisins).

Cependant, on souhaite que la valeur de la norme du gradient en un point soit toujours comprise entre 0 et 255 (pour pouvoir l'enregistrer dans une image).

Cette division n'est donc pas effectuée, les valeurs obtenues avec les deux masques du filtre de Sobel seront utilisées directement pour calculer la norme.

La norme calculée sera ensuite multipliée par un coefficient pour ramener les valeurs entre 0 et 255.

Les coordonnées de la norme calculée sont proportionellles aux coordonnées de la vraie norme ; elle sont comprises entre -1020 et 1020 (-4*255 et 4*255).

Si ces coordonnées sont appelées dx et dy, on a:

<math>
Norme = \sqrt{dx^2 + dy^2}
</math>

Donc

<math>
0\leq Norme\leq \sqrt{2}*1020
</math>

Pour que la valeur de cette norme soit comprise entre 0 et 255, elle sera multipliée par <math>\frac{255}{\sqrt{2}*1020}</math>.

En arrondissant cette valeur, on obtient l'intensité du pixel dans l'image résultat.

=== Calcul des bords de l'image gradient ===

Un problème survient, celui des pixels situés aux bords de l'image. Ils n'ont en effet pas de voisins dans toutes les directions, ainsi il n'est pas possible de convoluer directement leur "entourage" avec les masques du filtre de sobel.

Les pixels "manquants" sont remplacés.

Plusieurs solutions sont possibles :
* Ne rien faire et enlever les "bords" de l'image obtenue (l'image obtenue après application de l'algorithme est donc plus petite). Cette méthode donne de bons résultats car les résultats de l'algorithme au bord de l'image sont peu intéressants.

* Prolonger l'image. Il existe de nouveaux plusieurs méthodes, comme se référer à la valeur du pixel dans l'image le plus proche lorsque le pixel voulu est en dehors de l'image, ou répéter l'image lorsque la valeur voulue est hors de l'image. La manière de prolonger l'image dépend de la manière dont on va utiliser le résultat.

Ici j'ai choisi de prolonger l'image. Une méthode pour cela est de symétriser de l'image par rapport au pixel dont on veut calculer le gradient ; cette méthode a pour but de prolonger les formes au bord de l'image.

Voici un exemple du résultat attendu, où la ligne bleue représente le bord de l'image :

[[File:Sobel_bords.png|border|100px]]

Cependant cette solution ne permet pas calculer les valeurs aux "coins".

[[File:sobel_coin.png|border|100px|Symétriser l'image ne permet pas de remplacer les valeurs manquantes]]''Symétriser l'image ne permet pas de remplacer les valeurs manquantes''

Les pixels dont on ne peut pas remplacer la valeur par cette symétrie sont remplacés par le pixel dont on veut calculer le gradient.

Après l'utilisation de cette algorithme, l'image obtenue en résultat est une image "gradient".

[[File:sobel_gradient.png|border|300px|Image et son gradient]]
''Remarque : dans cet exemple, l'image gradient n'est pas celle obtenue avec l'algorithme ; les valeurs des pixels ont été augmentées pour que l'impact de cette étape soit plus visible.''

La valeur d'un pixel est élevée s'il se trouve dans une zone où les valeurs des pixels varient beaucoup.

Il est facile d'observer que les contours sont mis en valeur (ou plutôt, les zones où les valeurs des pixels varient beaucoup).

== Deuxième étape : détermination de la "ligne de partage des eaux"==

Pour la deuxième étape de l'algorithme, on utilise l'image gradient. Elle est alors considérée comme un relief où les pixels de faible intensité sont à faible altitude, et où les pixels d'intensité élevée sont à forte altitude.

=== Définitions ===

En topologie la ligne de partage des eaux peut-être définie de plusieurs manières ; elle est la séparation entre deux bassins versants dans un relief.

Notre image est considérée comme un relief, et la ligne de partage des eaux sera la séparation entre les zones de l'image.

Un bassin versant est un bassin dont toutes les eaux ont le même exutoire, par exemple une rivière ou l'océan.

Pour déterminer la ligne de partage des eaux, plusieurs méthodes sont possibles :

* On place une source d'eau dans chaque minimum local (donc dans chaque bassin) et on inonde, quand deux bassins se rencontrent on place une ligne de partage des eaux.
Les algorithmes utilisant ce principe sont appelés des algorithmes par inondation.

* Une deuxième méthode est de considérer que des deux côtés de la ligne l'écoulement de l'eau se termine dans des bassins versants différents.
Dans l'algorithme associé, on va faire "s'écouler" de l'eau sur chaque pixel et tracer une ligne de partage entre deux pixels (ou sur l'un des deux pixels) quand les eaux qui s'écoulent depuis ces pixels arrive dans des minima locaux différents.
Ce sont les algorithmes par ruissellement.

=== Algorithme utilisé (créé par Luc Vincent et Pierre Soille) ===

L'algorithme choisi est un algorithme par inondation.

Les pixels de faible intensité vont donc être traités en priorité.

La première étape est donc de trier les pixels de l'image par ordre croissant d'intensité.

L'algorithme va traiter les pixels d'intensité la plus basse, puis une fois ceux-ci traités, les pixels avec une intensité légèrement supérieure sont traités, et ainsi de suite jusqu'à avoir traité toute l'image.

Trois problèmes se posent alors :
* Comment inonder un étage, c'est à dire de quelle manière traiter les pixels de même intensité, à partir de bassins connus ?
* Comment déterminer à quel bassin appartient un pixel ?
* Comment repérer les nouveaux bassins ?

==== Inonder un étage (pixels d'intensité identique) ====

Chaque bassin doit progresser à la même vitesse sur un étage, c'est à dire que la ligne de partage des eaux qui sépare deux bassins doit être à égale distance de chacun.

Chaque pixel est à une "distance" d'un bassin. Par exemple les pixels collés à un bassin connu sont à une distance de 1. Leurs voisins sont eux à une distance de 2 (à condition qu'ils ne soient pas collés à un bassin connu).

[[File:file_distance.png|frame|Distance à laquelle se trouve les pixels du bassin connu (bleu)]]

Pour que les bassins s'étendent correctement, on traite d'abord tous les pixels à distance 1, puis ceux à distance 2 et ainsi de suite.

Une file d'attente est créée ; la première étape est de placer les pixels à une distance de 1 dans la file d'attente.
On va pouvoir traiter ces pixels là. On sait également que leurs voisins sont à une distance de 2, et pourront donc être traités lorsque les pixels à distance 1 seront associés à un bassin.

Les voisins non-traités des pixels à une distance de 1 sont donc les prochains pixels de l'étage à traiter.
Ils sont placés dans une autre file d'attente, qui sera parcourue une fois que la première a été entièrement utilisée.

Ensuite, les voisins des pixels à une distance de 2 seront les prochains pixels à traiter, et on va recommencer cette suite d'opérations.

Voici un exemple de la manière dont les pixels sont placés dans la file d'attente :

* Tout d'abord les pixels directement voisins d'un bassin connu sont placés dans la file d'attente

[[File:file_1.png|500px]] [[File:file_legende.png|200px]]

* Puis une fois que les pixels dans la file d'attente ont été traités, les pixels voisins des pixels qui viennent d'être traités sont placés dans la file d'attente

[[File:file_2.png|500px]] [[File:file_legende.png|200px]]

* Cette étape se répète tant qu'il y a des pixels dans la file d'attente

[[File:file_3.png|500px]] [[File:file_legende.png|200px]]

Ainsi le traitement d'une file d'attente (file d'attente d'une distance particulière) fait avancer d'un pixel tous les bassins, et tous les bassins progressent à la même vitesse.

==== Détermination du bassin auquel appartient un pixel ====

Avec cette manière de faire progresser les bassins, le bassin auquel appartient un pixel est déterminé par les bassins auxquels appartiennent ses voisins.

Plusieurs cas sont alors possibles lorsqu'un pixel est traité.

[[File:choix_label.png]]

*Un des cas les plus simples est lorsque tous les voisins traités du pixel appartiennent au même bassin.Le bassin s'étend alors, et le pixel à traiter est associé au bassin auquel appartiennent ses voisins.

*Cette même décision est prise si tous les pixels voisins traités appartiennent au même bassin sauf certains qui appartiennent à une ligne de partage des eaux (LPE). L'autre décision possible est de prolonger la LPE, cependant des lignes épaisses (et imprécises) seraient créées.

*Si les pixels voisins traités du pixel appartiennent à une LPE, le bassin auquel appartient le pixel est inconnu. On ne peut pas "prolonger" la ligne car on ne connaît alors pas à quelle distance d'un bassin se trouve le pixel. Si un pixel appartient à une LPE, ses voisins ne sont donc pas placés en file d'attente.

*Lorsque les pixels voisins appartiennent à des bassins différents, alors le pixel appartient à une LPE ; on sépare les bassins au moment de leur rencontre.

*Le dernier cas se présente lorsque tous les pixels voisins sont traités et qu'ils appartiennent tous à une LPE. Pour éviter qu'un bassin d'un seul pixel soit créé, on prolonge la LPE.

En résumé :
*S'il n'y a qu'un seul bassin autour du pixel en excluant les LPE, le pixel appartient à ce bassin.
*Si en excluant les LPE il y a plusieurs bassins autour du pixel, le pixel appartient à une LPE.
*Si le pixel est entouré par des LPE, alors il appartient à une LPE.

==== Création de nouveaux bassins ====

Lors de la propagation des bassins, si une file d'attente est vide alors tous les pixels de l'étage qui appartenaient à un bassin déjà connu ont été traités.

Les pixels restants appartiennent donc à de nouveaux bassins.

Un nouveau bassin est donc créé, le premier pixel qui lui appartient est choisi parmi un des pixels de l'étage non-traités.

On réinitialise alors la file d'attente, et on place les voisins non-traités du pixel associé au nouveau bassin dedans.

On recommence alors le traitement de la file d'attente, et tous les pixels qui appartiennent à ce bassin lui seront attribués.

Voici un exemple de la manière dont les nouveaux bassins sont créés, sur une petite image de 5x5.

[[File:minima_image.png|300px]]

Plusieurs étapes se déroulent alors :

* Le traitement d'un étage commence. Les pixels appartenant à un bassin connu se situent à un étage inférieur.

[[File:minima_1.png|300px]] [[File:minima_legende.png|500px]]

* Tous les pixels appartenant à un bassin connu ont été traités ; il reste cependant des pixels non-traités à cet étage. Ils appartiennent donc à un ou plusieurs nouveaux bassins. On choisit donc un pixel non-traité de l'étage, et on lui attribue un nouveau bassin.

[[File:minima_2.png|300px]] [[File:minima_legende.png|500px]]

* On propage le nouveau bassin créé.

[[File:minima_3.png|300px]] [[File:minima_legende.png|500px]]

Ces étapes sont répétées tant qu'il reste des pixels non-traités à l'étage en cours de traitement. On détecte ainsi tous les nouveaux bassins de l'étage.

Une fois que tous les pixels d'un étage ont été traités, on passe à l'étage supérieur.

==== Résultats ====
Voici un exemple de résultat que donne cet algorithme :

[[File:lpe_brute.png]]''A gauche le gradient d'une image ; à droite le résultat de l'algorithme de détermination des LPE''

On s'aperçoit que l'algorithme est très sensible au bruit, c'est à dire aux légères variations d'intensité qui créent des minima locaux.

On veut donc améliorer les résultats obtenus.

=== Réduire l'impact du bruit ===
Plusieurs méthodes sont applicables pour réduire l'impact du bruit sur le résultat.

==== Ajout d'une tolérance ====
La plus efficace est d'ajouter une "tolérance".

En effet, dans l'algorithme décrit précédemment, les pixels appartiennent à un même étage si leurs intensités sont exactement identiques.

On considére qu'un pixel appartient à l'étage traité si la différence entre son intensité et l'intensité de l'étage traitée est inférieure à un nombre, qu'on appelle tolérance.

Ainsi la sensibilité au bruit de l'algorithme est réduite car les petites variations d'intensité ne créent plus de nouveaux bassins.

Voici un exemple sur une petite image.

[[File:lpe_tolerance_image.png]]

Tout d'abord, s'il n'y a pas de tolérance, les pixels d'intensité 130 et le pixel d'intensité 135 sont à des étages différents.
Deux bassins sont donc créés lors du traitement de l'étage d'intensité 130 (bleu et vert, le noir représente une LPE).

[[File:lpe_sans_tolerance.png]]

Cependant, avec l'ajout d'une tolérance (par exemple 10), les trois pixels sont considérés au même étage (car on a 135-130 < 10).

[[File:lpe_tolerance.png]]

Ainsi une unique bassin est créé.

Le résultat est alors bien plus précis sur de vraies images:

[[File:lpe_res_tolerance.png]] ''A gauche le résultat (de cette [[#Résultats|image]]) de l'algorithme sans tolérance, à droite le résultat avec une tolérance de 5''

==== Flouter l'image avant le traitement ====

Une deuxième méthode est de traiter l'image avant d'appliquer l'algorithme.
Si l'image est floutée avant application de l'algorithme, le bruit aura moins d'impact, car les changements de valeur seront atténués.
Dans l'image floutée, chaque valeur d'un pixel est une moyenne des valeurs des pixels voisins à ce pixel dans l'image originale.

Pour cela, on peut convoluer l'image par cette matrice :

[[File:lpe_flou.png|200px]]

Chaque produit de convolution donnera un entier qui devra être divisé par 9 ; on ajoute les valeurs des 9 pixels dans un carré de 3x3 autour du pixel dont on veut la nouvelle valeur, pour avoir la moyenne des valeurs dans ce carré on doit alors diviser par 9.

Cette méthode ne donne pas de bons résultats si elle est la seule utilisée. Cependant, combinée avec l'utilisation de la tolérance, le nombre de petites zones est fortement réduit.

Les LPE sont en contrepartie moins précises.

Exemple de résultat :

[[File:lpe_flou_tolerance5.png]]

==== Fusion des petites zones ====

Une troisième solution est d'empêcher la création de zones trop petites, en indiquant une taille minimale.
Si des bassins plus petits que cette taille rencontrent un autre bassin, alors ils fusionnent, et le point de leur rencontre est associé à ce nouveau bassin issu de la fusion.

Si au point de rencontre des bassins se rencontrent deux zones plus grandes que la taille minimale, on doit tout de même placer une LPE, pour séparer les deux "grands" bassins.

Cette méthode ne donne pas non plus de résultats intéressants si utilisée seule, il est nécessaire de la combiner avec l'ajout d'une tolérance.

Un des résultats obtenus avec cette méthode est (où la taille minimale d'un bassin est de 5px) :

[[File:lpe_fusion5.png]]

== Conclusion ==

Pour conclure, on peut citer deux avantages de cet algorithme. Tout d'abord, les lignes de partage des eaux créées sont peu épaisses ; elles ne font jamais plus de 3 pixels de large, et se limitent dans la plupart des cas à une épaisseur d'un seul pixel.

Ensuite, l'algorithme est de complexité linéaire, c'est à dire que le temps d’exécution dépend linéairement du nombre de pixels de l'image sur laquelle on applique l'algorithme.
Voici quelques mesures du temps d'exécution selon le nombre de pixels de l'image en entrée (les images utilisées pour ces tests ne représentent rien et contiennent de nombreuses zones).

[[File:lpe_tableau_temps.png|border|mesures du temps d'exécution]]
[[File:lpe_temps.png|border|temps d'exécution en fonction du nombre de pixels]]

== Code source ==
Voici le code source de l'algorithme.

Pour manipuler des images, j'ai utilisé la bibliothèque PILLOW.

Les principales fonctions utilisées dans cette bibliothèque sont :
*Image.open(fichier) : ouvrir le fichier fichier en tant qu'objet image
*image.getpixel((x,y)) : récupérer la valeur du pixel aux coordonnées (x,y) dans un objet Image (appelé ici 'image')
*image.setpixel((x,y),(r,v,b)) : Changer la valeur du pixel aux coordonnées (x,y) dans un objet Image (appelé ici 'image') ; (r,v,b) sont les valeurs rouge,vert,bleu.
*image.save(nom) : sauvegarder l'image sous le nom souhaité.

<pre>
###########################################################
# RUET Nils
# Algorithme de détermination de ligne de partage des eaux, créé par Luc Vincent et Pierre Soille
#

########################################################################################################
# IMPORTATIONS
########################################################################################################

from PIL import Image
from math import sqrt
from random import randint

########################################################################################################
# CONSTANTES ET VARIABLES GLOBALES
########################################################################################################

#Chaque pixel a 3 valeurs qui lui sont associées ; son intensité, l'information sur s'il a déjà été placé en file d'attente, et le label qui lui a été associé.
#Ces informations sont stockés dans un tableau et ces constantes sont les indices auxquels trouver les informations voulues.
VALEUR = 0
LABELLED = 1
LABEL = 2

indiceEtage = 0# Lorsque l'on traite un étage, certains pixels ne sont pas traitables à partir des données connues. Ils correspondent à de nouveaux bassins.
# On dispose d'une liste des pixels de l'étage ; lorsqu'on doit créer un bassin, on cherche donc le premier pixel dans cette liste qui n'est pas labellé.
# Cette variable contient le nombre de pixels "consécutifs" traités, c'est à dire l'indice du dernier pixel non traité trouvé dans la liste.
# Ainsi on n'a pas à reparcourir la liste entière lorsque l'on créé plusieurs nouveaux bassins à un étage car on sait que tous les pixels "avant" (dans la liste) celui choisi pour créer un nouveau bassin ont été labellés.

########################################################################################################
# CALCUL DU GRADIENT
########################################################################################################

def deterCoef(mat):
"""Cette fonction prend un masque de convolution en entrée. Elle permet de déterminer un décalage et un coefficient utilisés pour ramener toutes les valeurs
obtenues après convolution entre 0 et 255"""
sommeP=0
sommeN=0
for i in range(len(mat)): #On compte les coefficients négatifs et les coefficients positifs dans le masque
for j in range(len(mat[0])):
if mat[i][j] > 0:
sommeP+=mat[i][j]
else:
sommeN-=mat[i][j]
decal = sommeN * 255 #Les coefficients négatifs permettent de connaître la valeur à ajouter pour n'obtenir que des valeurs positives après la convolution
coef = sommeN+sommeP #La somme des valeurs absolues des coefficients permet de savoir comment ramener toutes ces valeurs entre 0 et 255.
return (coef, decal)

def Convolution(image, x, y, filtre):
"""Effectue le produit de convolution entre un filtre et l'enourage du pixel aux coordonnées (x,y) dans l'image 'image' """
somme = 0
centre = len(filtre)//2
for i in range(-centre,centre+1): #i et j indiquent la position relative du pixel dont on a besoin dans l'image par rapport au pixel dont on calcule la nouvelle valeur.
for j in range(-centre,centre+1):
if filtre[i+centre][j+centre] != 0: #Vu qu'on multiplie la valeur d'un pixel par une valeur dans le filtre, on vérifie que la valeur dans le filtre ne vaut pas 0.
if 0<=x+i<image.width and 0<=y+j<image.height: #Si le pixel voulu est dans l'image, xl (x local) et yl (y local) sont ses coordonnées.
xl = x+i
yl = y+j
else: #Sinon on va chercher la valeur du pixel en symlétrie par rapport au pixel dont on veut la nouvelle valeur
xl = x-i
yl = y-j

if not 0<=xl<image.width or not 0<=yl<image.height: #Si après cela le pixel n'est toujours pas dans l'image, on se réfère à la valeur du pixel dont on veut la nouvelle valeur.
xl = x
yl = y
somme+= (image.getpixel((xl,yl))[0] *filtre[i+centre][j+centre])
return somme

def AppliqueFiltre(image, filtre):
"""Permet d'appliquer le masque de convolution 'filtre' (double tableau) à tous les pixels de l'image 'image' """
res = image.copy()
(coef, decal) = deterCoef(filtre)
for x in range(image.width): #Pour chaque pixel de l'image
for y in range(image.height):
somme = Convolution(image,x,y,filtre) #On prend le résultat de la convolution
val = round((somme+decal)/coef) #On ramène ce résultat entre 0 et 255
res.putpixel((x,y),(val,val,val)) #On met le pixel dans l'image résultat à cette valeur
return res

def Filtre(image, filtre, nom_sortie="filtre", saveIm=True):
"""Permet d'appeler la fonction qui permet de convoluer l'image 'image' par le masque 'filtre' et choisir si le résultat est sauvegardé dans un fichier image ou non"""
res = AppliqueFiltre(image, filtre)
if saveIm:
res.save("{}_{}".format(nom_sortie, fichierImage))
return res

def FiltreSobel(fichierIm):
"""Permer de calculer la norme du gradient de l'image 'fichierIm' (nom du fichier image) en chaque point avec la méthode du filtre de Sobel"""
image = Image.open(fichierIm)
res = image.copy()
masquex = [[-1,0,1],[-2,0,2],[-1,0,1]]
masquey = [[-1,-2,-1],[0,0,0],[1,2,1]]
for x in range(image.width): #Pour chaque pixel de l'image
for y in range(image.height):
dx = Convolution(image,x,y,masquex) #On approxime ses dérivées partielles
dy = Convolution(image,x,y,masquey) #

val = round(sqrt(dx**2 + dy**2)*255/(sqrt(2)*1020)) #On calcule la norme du gradient, qu'on ramène entre 0 et 255.
res.putpixel((x,y),(val,val,val)) #Cette valeur est associée au pixel dans le résultat
return res

#########################################################################################################
# ALGORITHME LIGNE DE PARTAGE DES EAUX
#########################################################################################################

def InitTableau(image):
"""Initialise le double tableau contenant les informations sur chaque pixel; aux indices [x][y] on accède aux informations du pixel (x,y). Ces informations sont l'intensité, l'avancement du traitement et le label."""
tableau = [0]*image.width #On initialise un tableau de la taille de l'image
for i in range(len(tableau)):
tableau[i]=[0]*image.height

for i in range(len(tableau)): #On initialise les informations de chaque pixel :
for j in range(len(tableau[i])):
tableau[i][j] = [image.getpixel((i,j))[0],False,"init"] #Sa valeur dans l'image, l'avancement du traitement (False si le pixel n'a pas été traité, True sinon), et le label qui lui est associé
return tableau

def InitListeOrdonnee(image):
"""Initialise la liste des pixels de l'image, triés par intensité ; chaque case contient la position du pixel attribué et son intensité"""
liste = []
for i in range(image.width):
for j in range(image.height):
liste.append([image.getpixel((i,j))[0],i,j])#On regarde chaque pixel de l'image et on ajoute dans une case de la liste son intensité, son abcisse, son ordonnée
liste.sort(key=lambda pixel: pixel[0]) #On trie cette liste en fonction de l'intensité des pixels (ordre croissant)
return liste

def PixelsEtage(listeOrdonnee, intensite, indice, tablImage, tolerance):
"""Prend en entrée la liste ordonnée des pixels de l'image, une intensité, l'indice à partir duquel commence cette intensité dans la liste, et une tolérance.
Renvoie la liste des pixels d'un "étage" d'intensité, plus précisément :
La liste des pixels non-labellés de l'intensité choisie plus ou moins la tolérance donnée. L'indice à partir duquel commence l'intensité choisie est modifié par une autre partie
du programme ; on sait que tous les pixels d'une valeur inférieure à l'intensité choisie ont déjà été traités par l'algorithme."""
pixels = []
nouvelIndice = indice
while nouvelIndice < len(listeOrdonnee) and (listeOrdonnee[nouvelIndice][0] - intensite) <= tolerance:#On ajoute à la liste des pixels de l'étage intensité les pixels qui ont une intensité dans l'intervalle souhaité
if not tablImage[listeOrdonnee[nouvelIndice][1]][listeOrdonnee[nouvelIndice][2]][LABELLED]: #Et non labellés
pixels.append(listeOrdonnee[nouvelIndice])
nouvelIndice+=1
return pixels

def labelsPixelsVoisins(x, y, tablImage):
"""Fonctions qui renvoie la liste des labels des pixels voisins au pixel situé aux coordonnée entrées en paramètre, ignore les pixels non labellés"""
labels = []

voisins = [(-1,0),(1,0),(0,-1),(0,1)]
for coords in voisins:
i = coords[0]
j = coords[1]
if 0<=x+i<len(tablImage) and 0<=y+j<len(tablImage[0]) and tablImage[x+i][y+j][LABEL] != "init":
labels.append(tablImage[x+i][y+j][LABEL])
return labels

def PixelTraitable(xPixel, yPixel, tablImage):
"""Fonction qui renvoie True si le pixel aux coordonnées entrées en paramètre est labellable, False sinon"""
labels = labelsPixelsVoisins(xPixel, yPixel, tablImage)
for label in labels:
if label!="watershed":#Un pixel est labellable s'il a un pixel labellé par autre chose qu'une ligne de partage parmi ses voisins.
return True

voisinsDansImage = 0 #Sinon si le pixel n'a pas de pixels labellés par autre chose que watershed parmi ses voisins,
voisins = [(-1,0),(1,0),(0,-1),(0,1)]
for coords in voisins: #On détermine son nombre de voisins (4 au centre, 3 sur les bords et 2 dans les coins)
i = coords[0]
j = coords[1]
if 0<=xPixel+i<len(tablImage) and 0<=yPixel+j<len(tablImage[0]):
voisinsDansImage += 1
return len(labels)==voisinsDansImage #Le pixel est labellable si tous ses voisins sont des lignes de partage des eaux

def nouveauLabel(listePixels, tablImage, fileAttente, listeLabels, intensite, tolerance):
"""Cette fonction est appelée lorsque l'algorithme n'a pas traité tous les pixels d'un étage, mais qu'aucun pixel n'a été placé en file attente <=> aucun pixel non traité n'est traitable à cet étage.
A partir de la liste des pixels de l'étage, de la liste des labels attribués, de l'intensité de l'étage et de la tolérance, on modifie alors la file d'attente"""
global indiceEtage
while tablImage[listePixels[indiceEtage][1]][listePixels[indiceEtage][2]][LABELLED]: #On parcourt la liste des pixels de l'étage pour en trouver un non labellé
indiceEtage+=1
x = listePixels[indiceEtage][1]
y = listePixels[indiceEtage][2]
voisins = [(-1,0),(1,0),(0,-1),(0,1)]
for coords in voisins: #On regarde les voisins du premier pixel non labellé trouvé
i = coords[0]
j = coords[1]
if 0<=x+i<len(tablImage) and 0<=y+j<len(tablImage[0]) and not tablImage[x+i][y+j][LABELLED] and (tablImage[x+i][y+j][VALEUR] - intensite) <= tolerance:
#Si un voisin est dans le bon intervalle d'intensité, non labellé et dans l'image, alors on le place dans la file d'attente
tablImage[x+i][y+j][LABELLED] = True
fileAttente[0].append([tablImage[x+i][y+j][VALEUR], x+i, y+j])

tablImage[x][y][LABEL] = len(listeLabels)#On créé un nouveau label en augmentant de 1 le numéro du dernier label ; cela correspond à la longueur de la liste des labels
#Puis on l'associe au pixel non traité trouvé dans l'étage
tablImage[x][y][LABELLED] = True #Ce pixel et désormais traité
listeLabels.append(1) #On ajoute le nouveau label créé à la liste des labels ; le bassin associé à ce label est de taille 1px initalement
return fileAttente #On renvoie la nouvelle file d'attente ; les voisins traitables du pixel trouvés

def AjoutFileAttente(fileAttente, distance, tablImage,intensite,tolerance):
"""A partir des pixels traités au moment de l'appel de cette fonction, on détermine les prochains pixels qui pourront être traités par la suite.
Ces pixels sont les voisins des pixels déjà traités (à l'exception des lignes de partage) du même étage, non traités et dans l'image"""
fileAttente.append([]) #On ajoute une file d'attente pour la distance suivante
for pixel in fileAttente[distance]:#Pour chaque pixel traité à la distance précédente
x = pixel[1]
y = pixel[2]
if tablImage[x][y][LABEL] != "watershed":#S'il n'est pas une ligne de partage, il appartient à un bassin et ses voisins sont potentiellement traitables
voisins = [(-1,0),(1,0),(0,-1),(0,1)]
for coords in voisins:
i = coords[0]
j = coords[1]
if 0<=x+i<len(tablImage) and 0<=y+j<len(tablImage[0]):
if (tablImage[x+i][y+j][VALEUR] - intensite) <= tolerance and not tablImage[x+i][y+j][LABELLED]:#Les voisins traitables sont les pixel du même étage non labellés
tablImage[x+i][y+j][LABELLED] = True
fileAttente[distance+1].append([tablImage[x+i][y+j][VALEUR], x+i, y+j])#On les ajoute à la file d'attente suivante

def valeursUniques(T):
"""Prend un tableau en entrée et supprime les valeurs qui s'y trouvent en double"""
res = []
for e in T:
if not e in res:
res.append(e)
return res

def fusionZones(labelsChange, nouvLabel, listeLabels, x, y, tablImage):
""" A partir d'une liste de labels à changer (labelsChange), du nouveau label qui leur sera associé, et d'un pixel de départ aux coordonnées x,y
On fusionne les bassins qui se rencontrent en x,y en modifiant le label des pixels de ces bassins.
Chaque fois qu'un pixel change de label, on change le label de ses voisins si cela est nécéssaire
"""
tablImage[x][y][LABEL] = nouvLabel
voisins = [(-1,0),(1,0),(0,-1),(0,1)]

file = [[x,y]]
indiceFile = 0
while indiceFile != len(file):#Tant que tous les pixels de la file n'ont pas été associés au nouveau label
pixel = file[indiceFile] #On prend le prochain pixel dans la file
for coords in voisins: #Et on regarde chacun de ses voisins
i = coords[0]
j = coords[1]
if 0<=pixel[0]+i<len(tablImage) and 0<=pixel[1]+j<len(tablImage[0]) and (tablImage[pixel[0]+i][pixel[1]+j][LABEL] in labelsChange): #Si un pixel voisins dans l'image a un label qui doit être changé
file.append([pixel[0]+i,pixel[1]+j])#On l'ajoute à la file
tablImage[pixel[0]+i][pixel[1]+j][LABEL] = nouvLabel#On lui attribue son nouveau label
listeLabels[nouvLabel]+=1#On augmente le nombre de pixels qui appartiennent au nouveau bassin
indiceFile+=1

def determinationLabels(fileAttente, distance, tablImage, listeLabels, tailleMini):
"""Procédure qui détermine le label attribué à un pixel en fonction des labels des pixels voisins"""
for pixel in fileAttente[distance]: #On attribue un label à chaque pixel dans la file d'attente
labels = labelsPixelsVoisins(pixel[1], pixel[2], tablImage) #On récupère les labels de ses voisins
lstLabels = valeursUniques(labels) #On supprime les doublons,
if ("watershed" in lstLabels): #et le label de ligne de partage des eaux
lstLabels.remove("watershed")

voisinsDansImage = 0
voisins = [(-1,0),(1,0),(0,-1),(0,1)]
for coords in voisins: #On compte le nombre de pixels voisins dans l'image ; 4 si le pixel est au centre de l'image, 3 s'il est au bord etc.
i = coords[0]
j = coords[1]
if 0<=pixel[1]+i<len(tablImage) and 0<=pixel[2]+j<len(tablImage[0]):
voisinsDansImage += 1
if len(lstLabels) == 0 and len(labels)==voisinsDansImage: #Si le pixel est entouré de watershed, on lui attribue ce label
tablImage[pixel[1]][pixel[2]][LABEL] = "watershed"

elif len(lstLabels) == 1: #Si le pixel n'a qu'un seul label hormis les watershed autour de lui, on lui attribue ce label
tablImage[pixel[1]][pixel[2]][LABEL] = lstLabels[0]
listeLabels[lstLabels[0]] += 1

elif len(lstLabels) > 1: #S'il y a plusieurs labels autour de lui, il se trouve entre deux bassins et est donc une ligne de partage des eaux ; si les bassins sont petits on les fusionne
i = 0
plusGrand = []
moinsGrand = []
while i<len(lstLabels):
if listeLabels[lstLabels[i]]>tailleMini:
plusGrand.append(lstLabels[i])
else:
moinsGrand.append(lstLabels[i])
i+=1
if len(moinsGrand)>0 and len(plusGrand)<2: #Si des bassins sont en dessous de la taille minimale et qu'il n'y a pas plusieurs bassins au dessus de cette taille
if len(plusGrand)==1: #Si il n'y a qu'un bassin au dessus, tous les petits bassins lui seront rattachés
labelsChange = moinsGrand[:]
nouvLabel = plusGrand[0]
elif len(plusGrand)==0: #S'il n'y en a aucun, les petits bassins fusionnent entre eux
labelsChange = moinsGrand[1:]
nouvLabel = moinsGrand[0]

tablImage[pixel[1]][pixel[2]][LABEL] = nouvLabel #Les bassins vont fusionner, le pixel que l'on regardait appartient donc au nouveau bassin
listeLabels[nouvLabel] += 1 #On augmente le compteur de pixels appartenant à ce bassin

voisins = [(-1,0),(1,0),(0,-1),(0,1)]
for coords in voisins: #On regarde chaque voisin, s'il est dans l'image et que son label doit etre changé, on appelle la procédure qui permet de changer les labels du bassin
i = coords[0]
j = coords[1]
if 0<=pixel[1]+i<len(tablImage) and 0<=pixel[2]+j<len(tablImage[0]) and tablImage[pixel[1]+i][pixel[2]+j][LABEL] in labelsChange:
fusionZones(labelsChange, nouvLabel, listeLabels, pixel[1]+i, pixel[2]+j, tablImage)

else: #Si aucun bassin n'est trop petit ou si au moins 2 sont au dessus de la taille minimale, le pixel est une ligne de partage des eaux
tablImage[pixel[1]][pixel[2]][LABEL] = "watershed"

def Algo(image, tolerance, tailleMini):
global indiceEtage

#### INITALISATION ###

#Initaliser tableaux :
# -double tableau qui contient les informations de chaque pixel
tableauImage = InitTableau(image)

# -la liste des labels
listeLabels = []

# -Initialiser la liste des pixels triée par leur intensité
listePixelsOrdonnee = InitListeOrdonnee(image)

# -l'indice de parcours de la liste des pixels triée
indice = 0

### TRAITEMENT POUR CHAQUE INTENSITE ###
for intensite in range(256):
#Initialiser la liste des pixels appartenant à l'étage traité
pixelsMemeEtage = PixelsEtage(listePixelsOrdonnee, intensite, indice, tableauImage, tolerance)

indice += len(pixelsMemeEtage)#On connaît le nombre de pixels de cet étage, on en déduit l'indice où commencera le prochaine étage
indiceEtage = 0 #Initialisation du compteur de pixels "consécutifs" traités à cet étage
compteurPxTraites = 0 #Compteur du nombre de pixels traités à cet étage

# Initialiser la file d'attente :
# La file d'attente est une liste de listes de pixels ; chaque sous-liste correspond à une distance, une étape du traitement
# Les premiers pixels traités sont collés à un pixel déjà labellé ; leurs voisins seront traitables par la suite
# et sont donc mis dans la file d'attente "suivante". Ils sont à une "distance" supérieure, et seront traités après le traitement de la distance actuelle
# C'est avec ce principe qu'on forme la file d'attente.
fileAttente=[[]]

# On fait d'abord un parcours de l'étage, pour trouver les pixels collés à des pixels labellés lors du traitement d'étages précédents
for pixel in pixelsMemeEtage:
# Pour chaque pixel de l'étage, on regarde ses voisins, si au moins un est labellé, le pixel est à distance 0, c'est à dire traitable directement.
if PixelTraitable(pixel[1],pixel[2], tableauImage):
#Si c'est le cas on l'ajoute à la file d'attente
fileAttente[0].append(pixel)
tableauImage[pixel[1]][pixel[2]][LABELLED] = True

#On initialise le numéro de l'étape du traitement, la distance : elle commence à 0 et augmente à chaque tour de boucle
distance = 0

while len(pixelsMemeEtage) > compteurPxTraites: #Tant que le nombre de pixels de cet étage traités est inférieur au nombre de pixels de l'étage, on a pas traité tout l'étage.

if len(fileAttente[distance])==0: #On regarde s'il y a des pixels dans la file d'attente
fileAttente = nouveauLabel(pixelsMemeEtage, tableauImage, fileAttente, listeLabels, intensite, tolerance) #Si non alors il n'y a plus aucun bassin connu à cet étage, on en ajoute:
compteurPxTraites += 1 #On sait qu'un pixel a été traité en ajoutant un nouveau bassin (le premier pixel du bassin), on l'ajoute au compteur

else: #Si il y a des pixels à traiter on les traite
while len(fileAttente[distance]) > 0: #avec ces nouvelles informations de nouveaux pixels seront traitables.
#On continue ces actions jusqu'à qu'aucun pixel ne soit traitable

determinationLabels(fileAttente, distance, tableauImage, listeLabels, tailleMini) #On commence par déterminer les labels des pixels traitables
AjoutFileAttente(fileAttente, distance, tableauImage, intensite, tolerance) #On ajoute les pixels désormais traitable dans la file d'attente qui sera parcourue au prochain tour de boucle
compteurPxTraites+=len(fileAttente[distance]) #Tous les pixels de la file d'attente à cet étape ont été traités ; on augmente le compteur en conséquence
distance +=1 #On passe à l'étape suivant de l'algorithme / la nouvelle file d'attente

distance = 0 #Une fois que la boucle est terminé, on a labellé tous les pixels possibles à cet étage qui n'appartiennent pas à un nouveau bassin
fileAttente = [[]] #On réinitialise la file d'attente pour refaire le même traitement avec un nouveau bassin

#Si tous les pixels de l'étage n'ont pas été traités, alors on va ainsi créer un nouveau bassin et le propager, jusqu'à que tous les pixels de l'étage aient été traités.

return AffichageImage(tableauImage, image, listeLabels)#On enregistre les résultats du traitement dans une image

def AffichageImage(tableauImage, image, listeLabels):
"""Fonction qui prend le résultat de l'algorithme sur le fichier fichier et le convertit en image ;
Les pixels des lignes de partage des eaux sont affichés en noir, et chaque label est associé à une couleur.
On enregistre ensuite cette image."""
lpe = image.copy()
couleurs = [0]*len(listeLabels)
for e in range(len(couleurs)):
couleurs[e] = (randint(100,200),randint(100,200),randint(100,200))
for i in range(image.width):
for j in range(image.height):
if tableauImage[i][j][LABEL] == "watershed":
lpe.putpixel((i,j),(0,0,0))
else:
lpe.putpixel((i,j),couleurs[tableauImage[i][j][LABEL]])
return lpe

########################################################################################################
# UTILISATION
########################################################################################################

def LPE(fichierImage, saveGradient=False, tolerance=0, flou=False, tailleMini=0, fichierGradient="none"):
"""Prend un fichier image en entrée et calcule son gradient,
avant d'appliquer l'algorithme de détermination de ligne de partage des eaux

l'option "saveGradient" est un booléen qui permet d'enregistrer le gradient de l'image si souhaité

l'option fichierGradient permet d'éxécuter uniquement la détermination de la LPE sur un fichier.
On peut donc appliquer la deuxième partir de l'algorithme sur une image gradient déjà calculée.

D'autres options sont disponibles, qui permettent de réduire la sensibilité au bruit de l'algorithme
- tolerance : entier ; deux pixels seront traités comme appartenant au même "étage"
si cet entier est plus grand que la différence de leurs valeurs
- flou : booléen qui si vaut vrai, applique un flou sur l'image de départ afin de diminuer
l'impact du bruit sur le résultat
- tailleMini : entier ; au moment où plusieurs zones se rencontrent, si cela est possible,
on fusionne les zones de taille inférieure (la taille est le nombre de pixels associés à la zone) à cet entier. Cela permet la supression des petites zones.

Les options réduisant la sensibilité au bruit peuvent rendre le résultat imprécis en fonction de leurs valeurs

Le résultat est sauvegardé sous forme d'image, où chaque zone est associée à une couleur et où les lignes de partage des eaux sont en noir."""

if fichierGradient == "none":
gradient = FiltreSobel(fichierImage)
if saveGradient:
gradient.save("gradient_{}".format(fichierImage))
else:
gradient = Image.open(fichierGradient)
if flou:
gradient = Filtre(gradient, [[1,1,1],[1,1,1],[1,1,1]], saveIm=False)
lpe = Algo(gradient, tolerance, tailleMini)

nom = "lpe_"
if flou:
nom+="flou_"
if tolerance!=0:
nom+="tolerance-{}_".format(tolerance)
if tailleMini!=0:
nom+="mini-{}_".format(tailleMini)
nom += "{}".format(fichierImage)
lpe.save(nom)
</pre>

== Sources ==
*[https://fr.wikipedia.org/wiki/Segmentation_d%27image Segmentation d'image]
*[https://fr.wikipedia.org/wiki/Filtre_de_Sobel Filtre de Sobel]
*[https://fr.wikipedia.org/wiki/Ligne_de_partage_des_eaux Ligne de partage des eaux (géographie)]
*[https://en.wikipedia.org/wiki/Watershed_(image_processing) Algorithmes existants pour calculer des lignes de partage des eaux (segmentation)]
*[https://pdfs.semanticscholar.org/a381/9dda9a5f00dbb8cd3413ca7422e37a0d5794.pdf Algorithme de Luc Vincent et Pierre Soille]
*[https://pillow.readthedocs.io/en/5.1.x/ Bibliothèque de manipulation d'image utilisée (PILLOW)]

Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

2018-05-26T19:06:51Z

Ruet :

== Introduction ==

La segmentation d'image est une famille dans le traitement d'image qui consiste à regrouper des pixels d'une image selon certaines de leurs caractéristiques.

On va ici utiliser un algorithme appelé "ligne de partage des eaux" sur des images en niveaux de gris.
Dans cet algorithme on utilise deux approches de la segmentation d'image, la segmentation par détection de contours et la segmentation par détection de régions. Deux étapes principales constituent donc l'algorithme.
La première est de représenter l'image en fonction de l'intensité de ses variations, on met ainsi en valeur les fortes variations de valeur dans l'image, donc les potentiels contours. La deuxième est de regrouper les zones dans cette nouvelle image par homogénéité, on détecte ainsi des régions dans l'image.

== Première étape : Approximation du gradient d'une image==
=== Image et notion de gradient d'une image ===
==== Image ====
Une image est un ensemble de points associés à une couleur.
Pour afficher une couleur, on combine une intensité de lumière rouge, une intensité de lumière verte et une intensité de lumière bleue.
Dans une image couleur chaque pixel est donc associé à 3 valeurs, les intensités de ces couleurs.
Ces intensités sont généralement codées sur 8 bits, donc comprises entre 0 et 255.

Ici, l'image traitée est une image en niveaux de gris. Une couleur est perçue comme un niveau de gris lorsque les intensités de lumière rouge, de lumière verte et de lumière bleue sont identiques.
Ainsi chaque point est décrit par ses coordonnées et associé à une seule valeur (entre 0 et 255) dans les images que l'algorithme pourra traiter.

D'un point de vue mathématique on peut considérer que l'image est une fonction de R*R vers R : on prend un couple de réels (les coordonnées) auquel un autre réel est associé (un niveau de gris).

==== Gradient ====

Pour réaliser la segmentation d'une image par détection de contour, la première étape est de représenter les variations de valeur dans l'image.
Si l'image est une fonction, et qu'elle est considérée différentiable, il est possible d'utiliser le gradient pour déterminer les variations de valeur en chaque point.

Le gradient d'une fonction est un vecteur qui représente les variations de la fonction par rapport à ses différents paramètres.

La direction et le sens du gradient indiquent le sens dans lequel la fonction varie le plus et sa norme indique l'intensité de la variation.

Ainsi, plus la norme du gradient est élevée en un point, plus les variations "autour" du point sont élevées.

Les coordonnées du gradient sont les dérivées partielles en fonction de chacun des paramètres de la fonction. Si les deux paramètres d'une fonction de R*R vers R sont appelés x et y, on aura en première coordonnée la dérivée partielle de la fonction selon x et en deuxième coordonnée la dérivée partielle de la fonction selon y.

Pour calculer les dérivées partielles de la fonction, il est nécéssaire de pouvoir connaître ses valeurs en chaque point.
Hors dans notre cas, les valeurs de la fonction image ne sont connues qu'en certains points, qui sont "distincts" entre eux.

Le gradient n'est donc pas calculable, cependant il est possible d'en avoir une approximation.

=== Filtre de Sobel ===

Le filtre de sobel est un opérateur permettant d'approximer le gradient de chacun des points de l'image.

Cet opérateur utilise des masques de convolution.

L'application des masques de convolution dans une image est lié au produit de convolution, un opérateur mathématique dont je parlerai pas car je ne connais que peu le sujet.

Pour obtenir la nouvelle valeur d'un pixel, on va convoluer la région "autour" du pixel avec un masque.

Le filtre de Sobel utilise deux masques, pour calculer chaque dérivée partielle.

[[File:sobel_x.png|border|100px]] ''Masque utilisé pour approximer la dérivée partielle en x''

[[File:sobel_y.png|border|100px]] ''Masque utilisé pour approximer la dérivée partielle en y''

==== Utilisation des masques de convolution ====

Pour chaque convolution, on utilise le masque et l'entourage d'un pixel dont on veut calculer la valeur.

Exemple, on veut calculer ici la nouvelle valeur du pixel entouré de rouge :

[[File:Convolution_pixel.png|exemple d'utilisation du produit de convolution]]

Chaque valeur d'un pixel "autour" du pixel dont on veut la nouvelle valeur est multipliée par la valeur correspondante dans le masque.

Dans ce cas pour obtenir une approximation de la dérivée partielle selon x, on devrait diviser par 8 le résultat (on utilise 8 valeurs parmi les pixels voisins).

Cependant, on souhaite que la valeur de la norme du gradient en un point soit toujours comprise entre 0 et 255 (pour pouvoir l'enregistrer dans une image).

Cette division n'est donc pas effectuée, les valeurs obtenues avec les deux masques du filtre de Sobel seront utilisées directement pour calculer la norme.

La norme calculée sera ensuite multipliée par un coefficient pour ramener les valeurs entre 0 et 255.

Les coordonnées de la norme calculée sont proportionellles aux coordonnées de la vraie norme ; elle sont comprises entre -1020 et 1020 (-4*255 et 4*255).

Si ces coordonnées sont appelées dx et dy, on a:

<math>
Norme = \sqrt{dx^2 + dy^2}
</math>

Donc

<math>
0\leq Norme\leq \sqrt{2}*1020
</math>

Pour que la valeur de cette norme soit comprise entre 0 et 255, elle sera multipliée par <math>\frac{255}{\sqrt{2}*1020}</math>.

En arrondissant cette valeur, on obtient l'intensité du pixel dans l'image résultat.

=== Calcul des bords de l'image gradient ===

Un problème survient, celui des pixels situés aux bords de l'image. Ils n'ont en effet pas de voisins dans toutes les directions, ainsi il n'est pas possible de convoluer directement leur "entourage" avec les masques du filtre de sobel.

Les pixels "manquants" sont remplacés.

Plusieurs solutions sont possibles :
* Ne rien faire et enlever les "bords" de l'image obtenue (l'image obtenue après application de l'algorithme est donc plus petite). Cette méthode donne de bons résultats car les résultats de l'algorithme au bord de l'image sont peu intéressants.

* Prolonger l'image. Il existe de nouveaux plusieurs méthodes, comme se référer à la valeur du pixel dans l'image le plus proche lorsque le pixel voulu est en dehors de l'image, ou répéter l'image lorsque la valeur voulue est hors de l'image. La manière de prolonger l'image dépend de la manière dont on va utiliser le résultat.

Ici j'ai choisi de prolonger l'image. Une méthode pour cela est de symétriser de l'image par rapport au pixel dont on veut calculer le gradient ; cette méthode a pour but de prolonger les formes au bord de l'image.

Voici un exemple du résultat attendu, où la ligne bleue représente le bord de l'image :

[[File:Sobel_bords.png|border|100px]]

Cependant cette solution ne permet pas calculer les valeurs aux "coins".

[[File:sobel_coin.png|border|100px|Symétriser l'image ne permet pas de remplacer les valeurs manquantes]]''Symétriser l'image ne permet pas de remplacer les valeurs manquantes''

Les pixels dont on ne peut pas remplacer la valeur par cette symétrie sont remplacés par le pixel dont on veut calculer le gradient.

Après l'utilisation de cette algorithme, l'image obtenue en résultat est une image "gradient".

[[File:sobel_gradient.png|border|300px|Image et son gradient]]
''Remarque : dans cet exemple, l'image gradient n'est pas celle obtenue avec l'algorithme ; les valeurs des pixels ont été augmentées pour que l'impact de cette étape soit plus visible.''

La valeur d'un pixel est élevée s'il se trouve dans une zone où les valeurs des pixels varient beaucoup.

Il est facile d'observer que les contours sont mis en valeur (ou plutôt, les zones où les valeurs des pixels varient beaucoup).

== Deuxième étape : détermination de la "ligne de partage des eaux"==

Pour la deuxième étape de l'algorithme, on utilise l'image gradient. Elle est alors considérée comme un relief où les pixels de faible intensité sont à faible altitude, et où les pixels d'intensité élevée sont à forte altitude.

=== Définitions ===

En topologie la ligne de partage des eaux peut-être définie de plusieurs manières ; elle est la séparation entre deux bassins versants dans un relief.

Notre image est considérée comme un relief, et la ligne de partage des eaux sera la séparation entre les zones de l'image.

Un bassin versant est un bassin dont toutes les eaux ont le même exutoire, par exemple une rivière ou l'océan.

Pour déterminer la ligne de partage des eaux, plusieurs méthodes sont possibles :

* On place une source d'eau dans chaque minimum local (donc dans chaque bassin) et on inonde, quand deux bassins se rencontrent on place une ligne de partage des eaux.
Les algorithmes utilisant ce principe sont appelés des algorithmes par inondation.

* Une deuxième méthode est de considérer que des deux côtés de la ligne l'écoulement de l'eau se termine dans des bassins versants différents.
Dans l'algorithme associé, on va faire "s'écouler" de l'eau sur chaque pixel et tracer une ligne de partage entre deux pixels (ou sur l'un des deux pixels) quand les eaux qui s'écoulent depuis ces pixels arrive dans des minima locaux différents.
Ce sont les algorithmes par ruissellement.

=== Algorithme utilisé (créé par Luc Vincent et Pierre Soille) ===

L'algorithme choisi est un algorithme par inondation.

Les pixels de faible intensité vont donc être traités en priorité.

La première étape est donc de trier les pixels de l'image par ordre croissant d'intensité.

L'algorithme va traiter les pixels d'intensité la plus basse, puis une fois ceux-ci traités, les pixels avec une intensité légèrement supérieure sont traités, et ainsi de suite jusqu'à avoir traité toute l'image.

Trois problèmes se posent alors :
* Comment inonder un étage, c'est à dire de quelle manière traiter les pixels de même intensité, à partir de bassins connus ?
* Comment déterminer à quel bassin appartient un pixel ?
* Comment repérer les nouveaux bassins ?

==== Inonder un étage (pixels d'intensité identique) ====

Chaque bassin doit progresser à la même vitesse sur un étage, c'est à dire que la ligne de partage des eaux qui sépare deux bassins doit être à égale distance de chacun.

Chaque pixel est à une "distance" d'un bassin. Par exemple les pixels collés à un bassin connu sont à une distance de 1. Leurs voisins sont eux à une distance de 2 (à condition qu'ils ne soient pas collés à un bassin connu).

[[File:file_distance.png|frame|Distance à laquelle se trouve les pixels du bassin connu (bleu)]]

Pour que les bassins s'étendent correctement, on traite d'abord tous les pixels à distance 1, puis ceux à distance 2 et ainsi de suite.

Une file d'attente est créée ; la première étape est de placer les pixels à une distance de 1 dans la file d'attente.
On va pouvoir traiter ces pixels là. On sait également que leurs voisins sont à une distance de 2, et pourront donc être traités lorsque les pixels à distance 1 seront associés à un bassin.

Les voisins non-traités des pixels à une distance de 1 sont donc les prochains pixels de l'étage à traiter.
Ils sont placés dans une autre file d'attente, qui sera parcourue une fois que la première a été entièrement utilisée.

Ensuite, les voisins des pixels à une distance de 2 seront les prochains pixels à traiter, et on va recommencer cette suite d'opérations.

Voici un exemple de la manière dont les pixels sont placés dans la file d'attente :

* Tout d'abord les pixels directement voisins d'un bassin connu sont placés dans la file d'attente

[[File:file_1.png|500px]] [[File:file_legende.png|200px]]

* Puis une fois que les pixels dans la file d'attente ont été traités, les pixels voisins des pixels qui viennent d'être traités sont placés dans la file d'attente

[[File:file_2.png|500px]] [[File:file_legende.png|200px]]

* Cette étape se répète tant qu'il y a des pixels dans la file d'attente

[[File:file_3.png|500px]] [[File:file_legende.png|200px]]

Ainsi le traitement d'une file d'attente (file d'attente d'une distance particulière) fait avancer d'un pixel tous les bassins, et tous les bassins progressent à la même vitesse.

==== Détermination du bassin auquel appartient un pixel ====

Avec cette manière de faire progresser les bassins, le bassin auquel appartient un pixel est déterminé par les bassins auxquels appartiennent ses voisins.

Plusieurs cas sont alors possibles lorsqu'un pixel est traité.

[[File:choix_label.png]]

*Un des cas les plus simples est lorsque tous les voisins traités du pixel appartiennent au même bassin.Le bassin s'étend alors, et le pixel à traiter est associé au bassin auquel appartiennent ses voisins.

*Cette même décision est prise si tous les pixels voisins traités appartiennent au même bassin sauf certains qui appartiennent à une ligne de partage des eaux (LPE). L'autre décision possible est de prolonger la LPE, cependant des lignes épaisses (et imprécises) seraient créées.

*Si les pixels voisins traités du pixel appartiennent à une LPE, le bassin auquel appartient le pixel est inconnu. On ne peut pas "prolonger" la ligne car on ne connaît alors pas à quelle distance d'un bassin se trouve le pixel. Si un pixel appartient à une LPE, ses voisins ne sont donc pas placés en file d'attente.

*Lorsque les pixels voisins appartiennent à des bassins différents, alors le pixel appartient à une LPE ; on sépare les bassins au moment de leur rencontre.

*Le dernier cas se présente lorsque tous les pixels voisins sont traités et qu'ils appartiennent tous à une LPE. Pour éviter qu'un bassin d'un seul pixel soit créé, on prolonge la LPE.

En résumé :
*S'il n'y a qu'un seul bassin autour du pixel en excluant les LPE, le pixel appartient à ce bassin.
*Si en excluant les LPE il y a plusieurs bassins autour du pixel, le pixel appartient à une LPE.
*Si le pixel est entouré par des LPE, alors il appartient à une LPE.

==== Création de nouveaux bassins ====

Lors de la propagation des bassins, si une file d'attente est vide alors tous les pixels de l'étage qui appartenaient à un bassin déjà connu ont été traités.

Les pixels restants appartiennent donc à de nouveaux bassins.

Un nouveau bassin est donc créé, le premier pixel qui lui appartient est choisi parmi un des pixels de l'étage non-traités.

On réinitialise alors la file d'attente, et on place les voisins non-traités du pixel associé au nouveau bassin dedans.

On recommence alors le traitement de la file d'attente, et tous les pixels qui appartiennent à ce bassin lui seront attribués.

Voici un exemple de la manière dont les nouveaux bassins sont créés, sur une petite image de 5x5.

[[File:minima_image.png|300px]]

Plusieurs étapes se déroulent alors :

* Le traitement d'un étage commence. Les pixels appartenant à un bassin connu se situent à un étage inférieur.

[[File:minima_1.png|300px]] [[File:minima_legende.png|500px]]

* Tous les pixels appartenant à un bassin connu ont été traités ; il reste cependant des pixels non-traités à cet étage. Ils appartiennent donc à un ou plusieurs nouveaux bassins. On choisit donc un pixel non-traité de l'étage, et on lui attribue un nouveau bassin.

[[File:minima_2.png|300px]] [[File:minima_legende.png|500px]]

* On propage le nouveau bassin créé.

[[File:minima_3.png|300px]] [[File:minima_legende.png|500px]]

Ces étapes sont répétées tant qu'il reste des pixels non-traités à l'étage en cours de traitement. On détecte ainsi tous les nouveaux bassins de l'étage.

Une fois que tous les pixels d'un étage ont été traités, on passe à l'étage supérieur.

==== Résultats ====
Voici un exemple de résultat que donne cet algorithme :

[[File:lpe_brute.png]]''A gauche le gradient d'une image ; à droite le résultat de l'algorithme de détermination des LPE''

On s'aperçoit que l'algorithme est très sensible au bruit, c'est à dire aux légères variations d'intensité qui créent des minima locaux.

On veut donc améliorer les résultats obtenus.

=== Réduire l'impact du bruit ===
Plusieurs méthodes sont applicables pour réduire l'impact du bruit sur le résultat.

==== Ajout d'une tolérance ====
La plus efficace est d'ajouter une "tolérance".

En effet, dans l'algorithme décrit précédemment, les pixels appartiennent à un même étage si leurs intensités sont exactement identiques.

On considére qu'un pixel appartient à l'étage traité si la différence entre son intensité et l'intensité de l'étage traitée est inférieure à un nombre, qu'on appelle tolérance.

Ainsi la sensibilité au bruit de l'algorithme est réduite car les petites variations d'intensité ne créent plus de nouveaux bassins.

Voici un exemple sur une petite image.

[[File:lpe_tolerance_image.png]]

Tout d'abord, s'il n'y a pas de tolérance, les pixels d'intensité 130 et le pixel d'intensité 135 sont à des étages différents.
Deux bassins sont donc créés lors du traitement de l'étage d'intensité 130 (bleu et vert, le noir représente une LPE).

[[File:lpe_sans_tolerance.png]]

Cependant, avec l'ajout d'une tolérance (par exemple 10), les trois pixels sont considérés au même étage (car on a 135-130 < 10).

[[File:lpe_tolerance.png]]

Ainsi une unique bassin est créé.

Le résultat est alors bien plus précis sur de vraies images:

[[File:lpe_res_tolerance.png]] ''A gauche le résultat (de cette [[#Résultats|image]]) de l'algorithme sans tolérance, à droite le résultat avec une tolérance de 5''

==== Flouter l'image avant le traitement ====

Une deuxième méthode est de traiter l'image avant d'appliquer l'algorithme.
Si l'image est floutée avant application de l'algorithme, le bruit aura moins d'impact, car les changements de valeur seront atténués.
Dans l'image floutée, chaque valeur d'un pixel est une moyenne des valeurs des pixels voisins à ce pixel dans l'image originale.

Pour cela, on peut convoluer l'image par cette matrice :

[[File:lpe_flou.png|200px]]

Chaque produit de convolution donnera un entier qui devra être divisé par 9 ; on ajoute les valeurs des 9 pixels dans un carré de 3x3 autour du pixel dont on veut la nouvelle valeur, pour avoir la moyenne des valeurs dans ce carré on doit alors diviser par 9.

Cette méthode ne donne pas de bons résultats si elle est la seule utilisée. Cependant, combinée avec l'utilisation de la tolérance, le nombre de petites zones est fortement réduit.

Les LPE sont en contrepartie moins précises.

Exemple de résultat :

[[File:lpe_flou_tolerance5.png]]

==== Fusion des petites zones ====

Une troisième solution est d'empêcher la création de zones trop petites, en indiquant une taille minimale.
Si des bassins plus petits que cette taille rencontrent un autre bassin, alors ils fusionnent, et le point de leur rencontre est associé à ce nouveau bassin issu de la fusion.

Si au point de rencontre des bassins se rencontrent deux zones plus grandes que la taille minimale, on doit tout de même placer une LPE, pour séparer les deux "grands" bassins.

Cette méthode ne donne pas non plus de résultats intéressants si utilisée seule, il est nécessaire de la combiner avec l'ajout d'une tolérance.

Un des résultats obtenus avec cette méthode est (où la taille minimale d'un bassin est de 5px) :

[[File:lpe_fusion5.png]]

== Conclusion ==

Pour conclure, on peut citer deux avantages de cet algorithme. Tout d'abord, les lignes de partage des eaux créées sont peu épaisses ; elles ne font jamais plus de 3 pixels de large, et se limitent dans la plupart des cas à une épaisseur d'un seul pixel.

Ensuite, l'algorithme est de complexité linéaire, c'est à dire que le temps d’exécution dépend linéairement du nombre de pixels de l'image sur laquelle on applique l'algorithme.
Voici quelques mesures du temps d'exécution selon le nombre de pixels de l'image en entrée (les images utilisées pour ces tests ne représentent rien et contiennent de nombreuses zones).

[[File:lpe_tableau_temps.png|border|mesures du temps d'exécution]]
[[File:lpe_temps.png|border|temps d'exécution en fonction du nombre de pixels]]

== Code source ==
Voici le code source de l'algorithme.

Pour manipuler des images, j'ai utilisé la bibliothèque PILLOW.

Les principales fonctions utilisées dans cette bibliothèque sont :
*Image.open(fichier) : ouvrir le fichier fichier en tant qu'objet image
*image.getpixel((x,y)) : récupérer la valeur du pixel aux coordonnées (x,y) dans un objet Image (appelé ici 'image')
*image.setpixel((x,y),(r,v,b)) : Changer la valeur du pixel aux coordonnées (x,y) dans un objet Image (appelé ici 'image') ; (r,v,b) sont les valeurs rouge,vert,bleu.
*image.save(nom) : sauvegarder l'image sous le nom souhaité.

<pre>
###########################################################
# RUET Nils
# Algorithme de détermination de ligne de partage des eaux, créé par Luc Vincent et Pierre Soille
#

########################################################################################################
# IMPORTATIONS
########################################################################################################

from PIL import Image
from math import sqrt
from random import randint

########################################################################################################
# CONSTANTES ET VARIABLES GLOBALES
########################################################################################################

#Chaque pixel a 3 valeurs qui lui sont associées ; son intensité, l'information sur s'il a déjà été placé en file d'attente, et le label qui lui a été associé.
#Ces informations sont stockés dans un tableau et ces constantes sont les indices auxquels trouver les informations voulues.
VALEUR = 0
LABELLED = 1
LABEL = 2

indiceEtage = 0# Lorsque l'on traite un étage, certains pixels ne sont pas traitables à partir des données connues. Ils correspondent à de nouveaux bassins.
# On dispose d'une liste des pixels de l'étage ; lorsqu'on doit créer un bassin, on cherche donc le premier pixel dans cette liste qui n'est pas labellé.
# Cette variable contient le nombre de pixels "consécutifs" traités, c'est à dire l'indice du dernier pixel non traité trouvé dans la liste.
# Ainsi on n'a pas à reparcourir la liste entière lorsque l'on créé plusieurs nouveaux bassins à un étage car on sait que tous les pixels "avant" (dans la liste) celui choisi pour créer un nouveau bassin ont été labellés.

########################################################################################################
# CALCUL DU GRADIENT
########################################################################################################

def deterCoef(mat):
"""Cette fonction prend un masque de convolution en entrée. Elle permet de déterminer un décalage et un coefficient utilisés pour ramener toutes les valeurs
obtenues après convolution entre 0 et 255"""
sommeP=0
sommeN=0
for i in range(len(mat)): #On compte les coefficients négatifs et les coefficients positifs dans le masque
for j in range(len(mat[0])):
if mat[i][j] > 0:
sommeP+=mat[i][j]
else:
sommeN-=mat[i][j]
decal = sommeN * 255 #Les coefficients négatifs permettent de connaître la valeur à ajouter pour n'obtenir que des valeurs positives après la convolution
coef = sommeN+sommeP #La somme des valeurs absolues des coefficients permet de savoir comment ramener toutes ces valeurs entre 0 et 255.
return (coef, decal)

def Convolution(image, x, y, filtre):
"""Effectue le produit de convolution entre un filtre et l'enourage du pixel aux coordonnées (x,y) dans l'image 'image' """
somme = 0
centre = len(filtre)//2
for i in range(-centre,centre+1): #i et j indiquent la position relative du pixel dont on a besoin dans l'image par rapport au pixel dont on calcule la nouvelle valeur.
for j in range(-centre,centre+1):
if filtre[i+centre][j+centre] != 0: #Vu qu'on multiplie la valeur d'un pixel par une valeur dans le filtre, on vérifie que la valeur dans le filtre ne vaut pas 0.
if 0<=x+i<image.width and 0<=y+j<image.height: #Si le pixel voulu est dans l'image, xl (x local) et yl (y local) sont ses coordonnées.
xl = x+i
yl = y+j
else: #Sinon on va chercher la valeur du pixel en symlétrie par rapport au pixel dont on veut la nouvelle valeur
xl = x-i
yl = y-j

if not 0<=xl<image.width or not 0<=yl<image.height: #Si après cela le pixel n'est toujours pas dans l'image, on se réfère à la valeur du pixel dont on veut la nouvelle valeur.
xl = x
yl = y
somme+= (image.getpixel((xl,yl))[0] *filtre[i+centre][j+centre])
return somme

def AppliqueFiltre(image, filtre):
"""Permet d'appliquer le masque de convolution 'filtre' (double tableau) à tous les pixels de l'image 'image' """
res = image.copy()
(coef, decal) = deterCoef(filtre)
for x in range(image.width): #Pour chaque pixel de l'image
for y in range(image.height):
somme = Convolution(image,x,y,filtre) #On prend le résultat de la convolution
val = round((somme+decal)/coef) #On ramène ce résultat entre 0 et 255
res.putpixel((x,y),(val,val,val)) #On met le pixel dans l'image résultat à cette valeur
return res

def Filtre(image, filtre, nom_sortie="filtre", saveIm=True):
"""Permet d'appeler la fonction qui permet de convoluer l'image 'image' par le masque 'filtre' et choisir si le résultat est sauvegardé dans un fichier image ou non"""
res = AppliqueFiltre(image, filtre)
if saveIm:
res.save("{}_{}".format(nom_sortie, fichierImage))
return res

def FiltreSobel(fichierIm):
"""Permer de calculer la norme du gradient de l'image 'fichierIm' (nom du fichier image) en chaque point avec la méthode du filtre de Sobel"""
image = Image.open(fichierIm)
res = image.copy()
masquex = [[-1,0,1],[-2,0,2],[-1,0,1]]
masquey = [[-1,-2,-1],[0,0,0],[1,2,1]]
for x in range(image.width): #Pour chaque pixel de l'image
for y in range(image.height):
dx = Convolution(image,x,y,masquex) #On approxime ses dérivées partielles
dy = Convolution(image,x,y,masquey) #

val = round(sqrt(dx**2 + dy**2)*255/(sqrt(2)*1020)) #On calcule la norme du gradient, qu'on ramène entre 0 et 255.
res.putpixel((x,y),(val,val,val)) #Cette valeur est associée au pixel dans le résultat
return res

#########################################################################################################
# ALGORITHME LIGNE DE PARTAGE DES EAUX
#########################################################################################################

def InitTableau(image):
"""Initialise le double tableau contenant les informations sur chaque pixel; aux indices [x][y] on accède aux informations du pixel (x,y). Ces informations sont l'intensité, l'avancement du traitement et le label."""
tableau = [0]*image.width #On initialise un tableau de la taille de l'image
for i in range(len(tableau)):
tableau[i]=[0]*image.height

for i in range(len(tableau)): #On initialise les informations de chaque pixel :
for j in range(len(tableau[i])):
tableau[i][j] = [image.getpixel((i,j))[0],False,"init"] #Sa valeur dans l'image, l'avancement du traitement (False si le pixel n'a pas été traité, True sinon), et le label qui lui est associé
return tableau

def InitListeOrdonnee(image):
"""Initialise la liste des pixels de l'image, triés par intensité ; chaque case contient la position du pixel attribué et son intensité"""
liste = []
for i in range(image.width):
for j in range(image.height):
liste.append([image.getpixel((i,j))[0],i,j])#On regarde chaque pixel de l'image et on ajoute dans une case de la liste son intensité, son abcisse, son ordonnée
liste.sort(key=lambda pixel: pixel[0]) #On trie cette liste en fonction de l'intensité des pixels (ordre croissant)
return liste

def PixelsEtage(listeOrdonnee, intensite, indice, tablImage, tolerance):
"""Prend en entrée la liste ordonnée des pixels de l'image, une intensité, l'indice à partir duquel commence cette intensité dans la liste, et une tolérance.
Renvoie la liste des pixels d'un "étage" d'intensité, plus précisément :
La liste des pixels non-labellés de l'intensité choisie plus ou moins la tolérance donnée. L'indice à partir duquel commence l'intensité choisie est modifié par une autre partie
du programme ; on sait que tous les pixels d'une valeur inférieure à l'intensité choisie ont déjà été traités par l'algorithme."""
pixels = []
nouvelIndice = indice
while nouvelIndice < len(listeOrdonnee) and (listeOrdonnee[nouvelIndice][0] - intensite) <= tolerance:#On ajoute à la liste des pixels de l'étage intensité les pixels qui ont une intensité dans l'intervalle souhaité
if not tablImage[listeOrdonnee[nouvelIndice][1]][listeOrdonnee[nouvelIndice][2]][LABELLED]: #Et non labellés
pixels.append(listeOrdonnee[nouvelIndice])
nouvelIndice+=1
return pixels

def labelsPixelsVoisins(x, y, tablImage):
"""Fonctions qui renvoie la liste des labels des pixels voisins au pixel situé aux coordonnée entrées en paramètre, ignore les pixels non labellés"""
labels = []

voisins = [(-1,0),(1,0),(0,-1),(0,1)]
for coords in voisins:
i = coords[0]
j = coords[1]
if 0<=x+i<len(tablImage) and 0<=y+j<len(tablImage[0]) and tablImage[x+i][y+j][LABEL] != "init":
labels.append(tablImage[x+i][y+j][LABEL])
return labels

def PixelTraitable(xPixel, yPixel, tablImage):
"""Fonction qui renvoie True si le pixel aux coordonnées entrées en paramètre est labellable, False sinon"""
labels = labelsPixelsVoisins(xPixel, yPixel, tablImage)
for label in labels:
if label!="watershed":#Un pixel est labellable s'il a un pixel labellé par autre chose qu'une ligne de partage parmi ses voisins.
return True

voisinsDansImage = 0 #Sinon si le pixel n'a pas de pixels labellés par autre chose que watershed parmi ses voisins,
voisins = [(-1,0),(1,0),(0,-1),(0,1)]
for coords in voisins: #On détermine son nombre de voisins (4 au centre, 3 sur les bords et 2 dans les coins)
i = coords[0]
j = coords[1]
if 0<=xPixel+i<len(tablImage) and 0<=yPixel+j<len(tablImage[0]):
voisinsDansImage += 1
return len(labels)==voisinsDansImage #Le pixel est labellable si tous ses voisins sont des lignes de partage des eaux

def nouveauLabel(listePixels, tablImage, fileAttente, listeLabels, intensite, tolerance):
"""Cette fonction est appelée lorsque l'algorithme n'a pas traité tous les pixels d'un étage, mais qu'aucun pixel n'a été placé en file attente <=> aucun pixel non traité n'est traitable à cet étage.
A partir de la liste des pixels de l'étage, de la liste des labels attribués, de l'intensité de l'étage et de la tolérance, on modifie alors la file d'attente"""
global indiceEtage
while tablImage[listePixels[indiceEtage][1]][listePixels[indiceEtage][2]][LABELLED]: #On parcourt la liste des pixels de l'étage pour en trouver un non labellé
indiceEtage+=1
x = listePixels[indiceEtage][1]
y = listePixels[indiceEtage][2]
voisins = [(-1,0),(1,0),(0,-1),(0,1)]
for coords in voisins: #On regarde les voisins du premier pixel non labellé trouvé
i = coords[0]
j = coords[1]
if 0<=x+i<len(tablImage) and 0<=y+j<len(tablImage[0]) and not tablImage[x+i][y+j][LABELLED] and (tablImage[x+i][y+j][VALEUR] - intensite) <= tolerance:
#Si un voisin est dans le bon intervalle d'intensité, non labellé et dans l'image, alors on le place dans la file d'attente
tablImage[x+i][y+j][LABELLED] = True
fileAttente[0].append([tablImage[x+i][y+j][VALEUR], x+i, y+j])

tablImage[x][y][LABEL] = len(listeLabels)#On créé un nouveau label en augmentant de 1 le numéro du dernier label ; cela correspond à la longueur de la liste des labels
#Puis on l'associe au pixel non traité trouvé dans l'étage
tablImage[x][y][LABELLED] = True #Ce pixel et désormais traité
listeLabels.append(1) #On ajoute le nouveau label créé à la liste des labels ; le bassin associé à ce label est de taille 1px initalement
return fileAttente #On renvoie la nouvelle file d'attente ; les voisins traitables du pixel trouvés

def AjoutFileAttente(fileAttente, distance, tablImage,intensite,tolerance):
"""A partir des pixels traités au moment de l'appel de cette fonction, on détermine les prochains pixels qui pourront être traités par la suite.
Ces pixels sont les voisins des pixels déjà traités (à l'exception des lignes de partage) du même étage, non traités et dans l'image"""
fileAttente.append([]) #On ajoute une file d'attente pour la distance suivante
for pixel in fileAttente[distance]:#Pour chaque pixel traité à la distance précédente
x = pixel[1]
y = pixel[2]
if tablImage[x][y][LABEL] != "watershed":#S'il n'est pas une ligne de partage, il appartient à un bassin et ses voisins sont potentiellement traitables
voisins = [(-1,0),(1,0),(0,-1),(0,1)]
for coords in voisins:
i = coords[0]
j = coords[1]
if 0<=x+i<len(tablImage) and 0<=y+j<len(tablImage[0]):
if (tablImage[x+i][y+j][VALEUR] - intensite) <= tolerance and not tablImage[x+i][y+j][LABELLED]:#Les voisins traitables sont les pixel du même étage non labellés
tablImage[x+i][y+j][LABELLED] = True
fileAttente[distance+1].append([tablImage[x+i][y+j][VALEUR], x+i, y+j])#On les ajoute à la file d'attente suivante

def valeursUniques(T):
"""Prend un tableau en entrée et supprime les valeurs qui s'y trouvent en double"""
res = []
for e in T:
if not e in res:
res.append(e)
return res

def fusionZones(labelsChange, nouvLabel, listeLabels, x, y, tablImage):
""" A partir d'une liste de labels à changer (labelsChange), du nouveau label qui leur sera associé, et d'un pixel de départ aux coordonnées x,y
On fusionne les bassins qui se rencontrent en x,y en modifiant le label des pixels de ces bassins.
Chaque fois qu'un pixel change de label, on change le label de ses voisins si cela est nécéssaire
"""
tablImage[x][y][LABEL] = nouvLabel
voisins = [(-1,0),(1,0),(0,-1),(0,1)]

file = [[x,y]]
indiceFile = 0
while indiceFile != len(file):#Tant que tous les pixels de la file n'ont pas été associés au nouveau label
pixel = file[indiceFile] #On prend le prochain pixel dans la file
for coords in voisins: #Et on regarde chacun de ses voisins
i = coords[0]
j = coords[1]
if 0<=pixel[0]+i<len(tablImage) and 0<=pixel[1]+j<len(tablImage[0]) and (tablImage[pixel[0]+i][pixel[1]+j][LABEL] in labelsChange): #Si un pixel voisins dans l'image a un label qui doit être changé
file.append([pixel[0]+i,pixel[1]+j])#On l'ajoute à la file
tablImage[pixel[0]+i][pixel[1]+j][LABEL] = nouvLabel#On lui attribue son nouveau label
listeLabels[nouvLabel]+=1#On augmente le nombre de pixels qui appartiennent au nouveau bassin
indiceFile+=1

def determinationLabels(fileAttente, distance, tablImage, listeLabels, tailleMini):
"""Procédure qui détermine le label attribué à un pixel en fonction des labels des pixels voisins"""
for pixel in fileAttente[distance]: #On attribue un label à chaque pixel dans la file d'attente
labels = labelsPixelsVoisins(pixel[1], pixel[2], tablImage) #On récupère les labels de ses voisins
lstLabels = valeursUniques(labels) #On supprime les doublons,
if ("watershed" in lstLabels): #et le label de ligne de partage des eaux
lstLabels.remove("watershed")

voisinsDansImage = 0
voisins = [(-1,0),(1,0),(0,-1),(0,1)]
for coords in voisins: #On compte le nombre de pixels voisins dans l'image ; 4 si le pixel est au centre de l'image, 3 s'il est au bord etc.
i = coords[0]
j = coords[1]
if 0<=pixel[1]+i<len(tablImage) and 0<=pixel[2]+j<len(tablImage[0]):
voisinsDansImage += 1
if len(lstLabels) == 0 and len(labels)==voisinsDansImage: #Si le pixel est entouré de watershed, on lui attribue ce label
tablImage[pixel[1]][pixel[2]][LABEL] = "watershed"

elif len(lstLabels) == 1: #Si le pixel n'a qu'un seul label hormis les watershed autour de lui, on lui attribue ce label
tablImage[pixel[1]][pixel[2]][LABEL] = lstLabels[0]
listeLabels[lstLabels[0]] += 1

elif len(lstLabels) > 1: #S'il y a plusieurs labels autour de lui, il se trouve entre deux bassins et est donc une ligne de partage des eaux ; si les bassins sont petits on les fusionne
i = 0
plusGrand = []
moinsGrand = []
while i<len(lstLabels):
if listeLabels[lstLabels[i]]>tailleMini:
plusGrand.append(lstLabels[i])
else:
moinsGrand.append(lstLabels[i])
i+=1
if len(moinsGrand)>0 and len(plusGrand)<2: #Si des bassins sont en dessous de la taille minimale et qu'il n'y a pas plusieurs bassins au dessus de cette taille
if len(plusGrand)==1: #Si il n'y a qu'un bassin au dessus, tous les petits bassins lui seront rattachés
labelsChange = moinsGrand[:]
nouvLabel = plusGrand[0]
elif len(plusGrand)==0: #S'il n'y en a aucun, les petits bassins fusionnent entre eux
labelsChange = moinsGrand[1:]
nouvLabel = moinsGrand[0]

tablImage[pixel[1]][pixel[2]][LABEL] = nouvLabel #Les bassins vont fusionner, le pixel que l'on regardait appartient donc au nouveau bassin
listeLabels[nouvLabel] += 1 #On augmente le compteur de pixels appartenant à ce bassin

voisins = [(-1,0),(1,0),(0,-1),(0,1)]
for coords in voisins: #On regarde chaque voisin, s'il est dans l'image et que son label doit etre changé, on appelle la procédure qui permet de changer les labels du bassin
i = coords[0]
j = coords[1]
if 0<=pixel[1]+i<len(tablImage) and 0<=pixel[2]+j<len(tablImage[0]) and tablImage[pixel[1]+i][pixel[2]+j][LABEL] in labelsChange:
fusionZones(labelsChange, nouvLabel, listeLabels, pixel[1]+i, pixel[2]+j, tablImage)

else: #Si aucun bassin n'est trop petit ou si au moins 2 sont au dessus de la taille minimale, le pixel est une ligne de partage des eaux
tablImage[pixel[1]][pixel[2]][LABEL] = "watershed"

def Algo(image, tolerance, tailleMini):
global indiceEtage

#### INITALISATION ###

#Initaliser tableaux :
# -double tableau qui contient les informations de chaque pixel
tableauImage = InitTableau(image)

# -la liste des labels
listeLabels = []

# -Initialiser la liste des pixels triée par leur intensité
listePixelsOrdonnee = InitListeOrdonnee(image)

# -l'indice de parcours de la liste des pixels triée
indice = 0

### TRAITEMENT POUR CHAQUE INTENSITE ###
for intensite in range(256):
#Initialiser la liste des pixels appartenant à l'étage traité
pixelsMemeEtage = PixelsEtage(listePixelsOrdonnee, intensite, indice, tableauImage, tolerance)

indice += len(pixelsMemeEtage)#On connaît le nombre de pixels de cet étage, on en déduit l'indice où commencera le prochaine étage
indiceEtage = 0 #Initialisation du compteur de pixels "consécutifs" traités à cet étage
compteurPxTraites = 0 #Compteur du nombre de pixels traités à cet étage

# Initialiser la file d'attente :
# La file d'attente est une liste de listes de pixels ; chaque sous-liste correspond à une distance, une étape du traitement
# Les premiers pixels traités sont collés à un pixel déjà labellé ; leurs voisins seront traitables par la suite
# et sont donc mis dans la file d'attente "suivante". Ils sont à une "distance" supérieure, et seront traités après le traitement de la distance actuelle
# C'est avec ce principe qu'on forme la file d'attente.
fileAttente=[[]]

# On fait d'abord un parcours de l'étage, pour trouver les pixels collés à des pixels labellés lors du traitement d'étages précédents
for pixel in pixelsMemeEtage:
# Pour chaque pixel de l'étage, on regarde ses voisins, si au moins un est labellé, le pixel est à distance 0, c'est à dire traitable directement.
if PixelTraitable(pixel[1],pixel[2], tableauImage):
#Si c'est le cas on l'ajoute à la file d'attente
fileAttente[0].append(pixel)
tableauImage[pixel[1]][pixel[2]][LABELLED] = True

#On initialise le numéro de l'étape du traitement, la distance : elle commence à 0 et augmente à chaque tour de boucle
distance = 0

while len(pixelsMemeEtage) > compteurPxTraites: #Tant que le nombre de pixels de cet étage traités est inférieur au nombre de pixels de l'étage, on a pas traité tout l'étage.

if len(fileAttente[distance])==0: #On regarde s'il y a des pixels dans la file d'attente
fileAttente = nouveauLabel(pixelsMemeEtage, tableauImage, fileAttente, listeLabels, intensite, tolerance) #Si non alors il n'y a plus aucun bassin connu à cet étage, on en ajoute:
compteurPxTraites += 1 #On sait qu'un pixel a été traité en ajoutant un nouveau bassin (le premier pixel du bassin), on l'ajoute au compteur

else: #Si il y a des pixels à traiter on les traite
while len(fileAttente[distance]) > 0: #avec ces nouvelles informations de nouveaux pixels seront traitables.
#On continue ces actions jusqu'à qu'aucun pixel ne soit traitable

determinationLabels(fileAttente, distance, tableauImage, listeLabels, tailleMini) #On commence par déterminer les labels des pixels traitables
AjoutFileAttente(fileAttente, distance, tableauImage, intensite, tolerance) #On ajoute les pixels désormais traitable dans la file d'attente qui sera parcourue au prochain tour de boucle
compteurPxTraites+=len(fileAttente[distance]) #Tous les pixels de la file d'attente à cet étape ont été traités ; on augmente le compteur en conséquence
distance +=1 #On passe à l'étape suivant de l'algorithme / la nouvelle file d'attente

distance = 0 #Une fois que la boucle est terminé, on a labellé tous les pixels possibles à cet étage qui n'appartiennent pas à un nouveau bassin
fileAttente = [[]] #On réinitialise la file d'attente pour refaire le même traitement avec un nouveau bassin

#Si tous les pixels de l'étage n'ont pas été traités, alors on va ainsi créer un nouveau bassin et le propager, jusqu'à que tous les pixels de l'étage aient été traités.

return AffichageImage(tableauImage, image, listeLabels)#On enregistre les résultats du traitement dans une image

def AffichageImage(tableauImage, image, listeLabels):
"""Fonction qui prend le résultat de l'algorithme sur le fichier fichier et le convertit en image ;
Les pixels des lignes de partage des eaux sont affichés en noir, et chaque label est associé à une couleur.
On enregistre ensuite cette image."""
lpe = image.copy()
couleurs = [0]*len(listeLabels)
for e in range(len(couleurs)):
couleurs[e] = (randint(100,200),randint(100,200),randint(100,200))
for i in range(image.width):
for j in range(image.height):
if tableauImage[i][j][LABEL] == "watershed":
lpe.putpixel((i,j),(0,0,0))
else:
lpe.putpixel((i,j),couleurs[tableauImage[i][j][LABEL]])
return lpe

########################################################################################################
# UTILISATION
########################################################################################################

def LPE(fichierImage, saveGradient=False, tolerance=0, flou=False, tailleMini=0, fichierGradient="none"):
"""Prend un fichier image en entrée et calcule son gradient,
avant d'appliquer l'algorithme de détermination de ligne de partage des eaux

l'option "saveGradient" est un booléen qui permet d'enregistrer le gradient de l'image si souhaité

l'option fichierGradient permet d'éxécuter uniquement la détermination de la LPE sur un fichier.
On peut donc appliquer la deuxième partir de l'algorithme sur une image gradient déjà calculée.

D'autres options sont disponibles, qui permettent de réduire la sensibilité au bruit de l'algorithme
- tolerance : entier ; deux pixels seront traités comme appartenant au même "étage"
si cet entier est plus grand que la différence de leurs valeurs
- flou : booléen qui si vaut vrai, applique un flou sur l'image de départ afin de diminuer
l'impact du bruit sur le résultat
- tailleMini : entier ; au moment où plusieurs zones se rencontrent, si cela est possible,
on fusionne les zones de taille inférieure (la taille est le nombre de pixels associés à la zone) à cet entier. Cela permet la supression des petites zones.

Les options réduisant la sensibilité au bruit peuvent rendre le résultat imprécis en fonction de leurs valeurs

Le résultat est sauvegardé sous forme d'image, où chaque zone est associée à une couleur et où les lignes de partage des eaux sont en noir."""

if fichierGradient == "none":
gradient = FiltreSobel(fichierImage)
if saveGradient:
gradient.save("gradient_{}".format(fichierImage))
else:
gradient = Image.open(fichierGradient)
if flou:
gradient = Filtre(gradient, [[1,1,1],[1,1,1],[1,1,1]], saveIm=False)
lpe = Algo(gradient, tolerance, tailleMini)

nom = "lpe_"
if flou:
nom+="flou_"
if tolerance!=0:
nom+="tolerance-{}_".format(tolerance)
if tailleMini!=0:
nom+="mini-{}_".format(tailleMini)
nom += "{}".format(fichierImage)
lpe.save(nom)
</pre>

== Sources ==
*[https://fr.wikipedia.org/wiki/Segmentation_d%27image Segmentation d'image]
*[https://fr.wikipedia.org/wiki/Filtre_de_Sobel Filtre de Sobel]
*[https://en.wikipedia.org/wiki/Watershed_(image_processing) Algorithmes existants pour calculer des lignes de partage des eaux]
*[https://pdfs.semanticscholar.org/a381/9dda9a5f00dbb8cd3413ca7422e37a0d5794.pdf Algorithme de Luc Vincent et Pierre Soille)]
*[https://pillow.readthedocs.io/en/5.1.x/ Bibliothèque de manipulation d'image utilisée (PILLOW)]

Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

2018-05-26T18:49:33Z

Ruet :

Fichier:Lpe tableau temps.png

2018-05-26T18:48:51Z

Ruet :

Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

2018-05-26T17:56:00Z

Ruet :

Fichier:Lpe temps.png

2018-05-26T17:52:40Z

Ruet :

Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

2018-05-26T17:49:56Z

Ruet :

Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

2018-05-26T17:30:19Z

Ruet :

Fichier:Lpe fusion5.png

2018-05-26T17:29:50Z

Ruet :

Fichier:Lpe flou tolerance5.png

2018-05-26T17:22:40Z

Ruet :

Fichier:Lpe flou.png

2018-05-26T17:17:52Z

Ruet :

Fichier:Lpe res tolerance.png

2018-05-26T17:05:50Z

Ruet :

Fichier:Lpe tolerance.png

2018-05-26T17:05:34Z

Ruet :

Fichier:Lpe sans tolerance.png

2018-05-26T17:05:15Z

Ruet :

Fichier:Lpe tolerance image.png

2018-05-26T17:04:58Z

Ruet :

Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

2018-05-26T16:43:35Z

Ruet :

Fichier:Lpe brute.png

2018-05-26T16:39:54Z

Ruet :

Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

2018-05-26T16:26:22Z

Ruet :

Fichier:Minima image.png

2018-05-26T16:24:18Z

Ruet : Ruet a téléversé une nouvelle version de Fichier:Minima image.png

Fichier:Minima image.png

2018-05-26T16:24:07Z

Ruet : Ruet a téléversé une nouvelle version de Fichier:Minima image.png

Fichier:Minima image.png

2018-05-26T16:23:41Z

Ruet : Ruet a téléversé une nouvelle version de Fichier:Minima image.png

Fichier:Minima legende.png

2018-05-26T16:15:54Z

Ruet :

Fichier:Minima image.png

2018-05-26T16:15:46Z

Ruet :

Fichier:Minima 3.png

2018-05-26T16:15:38Z

Ruet :

Fichier:Minima 2.png

2018-05-26T16:15:30Z

Ruet :

Fichier:Minima 1.png

2018-05-26T16:15:22Z

Ruet :

Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

2018-05-26T15:59:45Z

Ruet :

Fichier:Choix label.png

2018-05-26T15:48:08Z

Ruet :

Fichier:File legende.png

2018-05-26T15:42:01Z

Ruet :

Fichier:File 3.png

2018-05-26T15:31:22Z

Ruet :

Fichier:File 2.png

2018-05-26T15:31:13Z

Ruet :

Fichier:File 1.png

2018-05-26T15:30:58Z

Ruet :

Fichier:File distance.png

2018-05-26T15:24:47Z

Ruet : Ruet a téléversé une nouvelle version de Fichier:File distance.png

Distance à laquelle se trouve chaque pixel d'un bassin connu

Fichier:File distance.png

2018-05-26T15:22:17Z

Ruet : Distance à laquelle se trouve chaque pixel d'un bassin connu

Distance à laquelle se trouve chaque pixel d'un bassin connu

Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

2018-05-26T15:00:25Z

Ruet :

Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

2018-05-26T14:57:41Z

Ruet :

Fichier:Convolution pixel.png

2018-05-26T14:57:06Z

Ruet : Ruet a téléversé une nouvelle version de Fichier:Convolution pixel.png

Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

2018-05-26T14:52:33Z

Ruet :

Fichier:Sobel gradient.png

2018-05-26T14:48:41Z

Ruet :

Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

2018-05-26T14:43:39Z

Ruet :

Fichier:Sobel coin.png

2018-05-26T14:43:27Z

Ruet :

Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

2018-05-26T14:39:19Z

Ruet :

Fichier:Sobel bords.png

2018-05-26T14:37:15Z

Ruet : Ruet a téléversé une nouvelle version de Fichier:Sobel bords.png

Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

2018-05-26T14:31:38Z

Ruet :

Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

2018-05-26T14:11:49Z

Ruet :

Fichier:Convolution pixel.png

2018-05-26T14:08:53Z

Ruet : Ruet a téléversé une nouvelle version de Fichier:Convolution pixel.png

Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

2018-05-26T14:01:04Z

Ruet : Page créée avec « == Introduction == La segmentation d'image est une famille dans le traitement d'image qui consiste à regrouper des pixels d'une image selon certaines de leurs caractér... »

Fichier:Sobel y.png

2018-05-26T13:36:48Z

Ruet :