-On connait peu de versions GPU du filtre médian, peut-être en raison des implémentations CPU performantes et génériques que l'on a déjà évoquées (voir par exemple \cite{4287006}) et dont le portage sur GPU ne laisse pas entrevoir de potentiel, ou bien reste à inventer. Néanmoins, une bibliothèque commerciale (LibJacket et ArrayFire) en propose une implémentation GPU dont nous avons pu mesurer les performances pour un masque de 3$\times$3 et qui est également prise comme référence par Sanchez \textit{et al.} pour évaluer les performances de leur propre implémentation appelée PCMF \cite{6288187}. Sur architecture GT200 (GTX260), les performances maximales de ces deux versions sont obtenues pour un masque de 3$\times$3 pixels avec respectivement 175~MP/s pour libJacket et 60~MP/s pour PCMF.
-Une précédente implémentation avait été réalisée, basée sur l'algorithme BVM décrit dans \cite{5402362}. Elle prouve son efficacité dans l'élimination des artefacts générés par les dispositifs d'imagerie médicale magnétique en 3D \cite{chen09}, mais ne permet pas d'exploiter véritablement le parallélisme des GPU en filtrage d'image en 2D.
-La figure \ref{fig-compare-jacket-pcmf}, tirée de \cite{5402362}, compare ces trois implémentations et montre que le débit permis par la libJacket décroit très vite avec la taille du masque pour passer à 30~MP/s dès la taille 5$\times$5, alors que le PCMF décroit linéairement jusqu'à la taille 11$\times$11 où il permet encore de traiter quelque 40~MP/s. Ceci s'explique simplement par le fait que libJacket utilise un tri simple pour la sélection de la valeur médiane alors que le PCMF exploite les propriétés des histogrammes cumulés et n'est ainsi que très peu dépendant de la taille du masque.
-Plus récemment, Sanchez \textit{et al.} ont actualisé leurs mesures sur architecture Fermi (GPU C2075) en comparant leur PCMF à la version ré-écrite en C de libJacket, nommée ArrayFire. Les courbes sont celles de la figure \ref{fig-compare-arrayfire-pcmf}, où l'on constate que les variations selon la taille du masque demeurent comparables, avec toutefois des valeurs de débit augmentées, avec près de 185~MP/s pour ArrayFire et 82~MP/s pour PCMF.
-Parallèlement, on trouve aussi des implémentations de filtre médian dans des traitements plus complexes comme dans \cite{aldinucci2012parallel} où les auteurs décrivent la plus récente évolution de leur technique itérative de réduction de bruit impulsionnel, sans qu'il soit possible d'évaluer le débit du médian seul.
-Il faut noter enfin que certains codes sont plus performants sur l'ancienne architecture GT200/Tesla que sur la plus récente Fermi ; c'est le cas pour l'implémentation du médian incluse dans la bibliothèque ArrayFire et nous reviendrons sur les raisons de cette perte de performances constatée au passage à une architecture plus récente dans le chapitre consacré à notre implémentation du filtre médian.
-
-Le filtre bilatéral a été plus abordé et un certain nombre de publications font état d'implémentations rapides.
-Une implémentation à temps constant en est proposée par Yang \textit{et al.} \cite{5206542} et s'exécute entre 3.7~ms et 15~ms pour une image de 1~MP. Cela ne constitue pas une référence de vitesse pour les masques de petite taille, mais devient compétitif pour des masque de grande taille (plus de 400 pixels dans le voisinage).
-Une autre plus classique, employée dans la génération des images médicales tomographiques, annonce 16~ms pour un masque de 11$\times$11 sur une image de 0.25~MP.
-Il demeure souvent difficile de comparer les implémentations sans disposer des codes sources, en raison de conditions de test très variables, en particulier en ce qui concerne le modèle de GPU et la taille du masque.
-Ceci étant précisé, on peut prendre comme première référence la version proposée par Nvidia dans le SDK CUDA et nommée ``ImageDenoising''. Elle permet d'exécuter sur GPU GTX480 un filtre bilatéral 7$\times$7 sur une image, déjà en mémoire GPU, de 1~MPixels en 0.411~ms, pour un débit global de 133~MP/s.
-Dans \cite{zheng2011performance}, les auteurs présentent un cadre général pour optimiser l'accès aux données par les différents kernels en utilisant la mémoire partagée par les threads d'un même bloc.
-Le principe est de pré-charger les valeurs utiles au bloc de threads dans la mémoire partagée, cela comprend les valeurs (niveaux de gris) des pixels associés aux threads ainsi que le halo correspondant aux voisinages des pixels de la bande périphérique. On appelle communément cet ensemble la \textit{region of interest} ou ROI.
-Ils appliquent ensuite leur recette à l'implémentation d'un filtre bilatéral et d'un filtre à moyennes non locales (NL-means). Concernant le filtre bilatéral, ils pré-calculent aussi les coefficients de la pondération spatiale, alors que ceux de la pondération d'intensité resent calculés à la volée.
-Ces deux optimisations permettent un gain de 20\% sur le temps de calcul du filtre bilatéral pour arriver à 0.326~ms dans les mêmes conditions que ci-dessus. Toutefois, le débit global ne gagne que très peu (132~MP/s) en raison de la prépondérance des temps de tranfert annoncés à 7.5~ms pour l'image de 1~MP.
-Ce travail d'optimisation ne perd toutefois pas son intérêt, en ce sens où si le filtre fait partie d'une chaîne de traitement entièrement exécutée par le GPU, le transfert des données n'a besoin d'être effectué qu'une seule fois en tout début et en toute fin de traitement.
-Enfin, l'implémentation qui semble à ce jour la plus performante s'attache à réduire les redondances de calculs et parvient à filtrer une image de 9~MP avec un masque de 21$\times$21 en seulement 200~ms, soir un débit de 47~MP/s hors transfers.
-
-Intuitivement, les algorithmes à base de patches paraissent moins adaptés au parallèlisme des GPU, du fait de la nécessité d'accéder à un voisinage étendu autour de chaque pixel. On recense malgré tout quelques implémentations dont celle présente dans le SDK CUDA qui fait cependant l'hypothèse que les coefficients de pondération spatiale sont localement constants.
-Dans \cite{PALHANOXAVIERDEFONTES}, le modèle de bruit employé vise une adaptation aux images échographiques présentant du bruit proche du speckle. Dans cette implémentation, aucune approximation des coefficients n'est faite, mais la taille maximale du patch est limitée par la quantité de mémoire partagée disponible pour chaque bloc de threads.
-Une version plus récente implémente exactement l'algorithme original \cite{nlmeansgpubelge} en proposant des optimisations algorithmiques exploitant la symétrie des coefficients spatiaux ainsi que l'interprétation du calcul de la similarité comme une convolution séparable, opération aisément parallélisable sur GPU, comme nous le détaillerons plus loin. Les auteurs parviennent ainsi à filtrer des séquences vidéo couleur de dimension 720$\times$480 à plus de 30~fps en améliorant le PSNR de 16~dB (la séquence bruitée présentant un PSNR de 20~dB).
-
-\section{Les techniques de segmentation}
-La segmentation représente également un enjeu important dans le domaine du traitement d'image et à ce titre a fait l'objet d'abondants travaux et publications touchant les nombreux cas d'analyse dans lesquels une segmentation est utilisée. On peut citer la reconnaissance de formes, la détections et/ou la poursuite de cibles, la cartographie, le diagnostique médical, l'interaction Homme-machine, la discrimination d'arrière plan, etc.
-
-On pourrait donner de la segmentation une définition spécifique par type d'usage, mais dans un souci d'unification, on propose la formulation générique suivante :
-``La segmentation consiste à distinguer les zones homogènes au sein d'une image''.
-Dans cette définition, le caractère \textit{homogène} s'entend au sens d'un critère pré établi, adapté aux contraintes particulières de traitement comme le type de bruit corrompant les images, ou bien la dimension du signal observé $\bar{v}$ selon que l'image est en couleur ou non. Un tel critère peut ainsi être un simple seuil de niveau de gris ou bien nécessiter de coûteux calculs statistiques dont certains seront détaillés dans les chapitres suivants.
-
-Devant la diversité des cas à traiter et des objectifs à atteindre, on sait aujourd'hui qu'à l'instar du filtre unique, la méthode universelle de segmentation n'existe pas et qu'une bonne segmentation est celle qui conduit effectivement à l'extraction des structures pertinentes d'une image selon l'interprétation qui doit en être faite.
-
-Les éléments constitutifs de la segmentation sont soit des régions, soit des contours. Les deux notions sont complémentaires étant donné que les contours délimitent des régions, mais les techniques de calcul basés sur l'un ou l'autre de ces éléments relèvent d'abords différents.
-Les algorithmes de segmentation orientés régions s'appuient pour beaucoup sur des techniques de regroupement, ou \textit{clustering}, pour l'identification et le peuplement des régions. Ce lien trouve son origine dans la psychologie du \textit{gestalt} \cite{humphrey1924psychology} où l'on considère que la perception conceptuelle s'élabore au travers de regroupements visuel d'éléments.
-La plupart des approches proposées jusqu'à très récemment consistent à minimiser une fonction d'énergie qui n'a pas de solution formelle et que l'on résout donc à l'aide de techniques numériques, souvent itératives.
-
-\subsection{Analyse d'histogramme}
-Les techniques les plus simples à mettre en \oe uvre en segmentation sont les techniques de seuillage, basées sur une analyse de l'histogramme des niveaux de gris (ou de couleurs) et cherchant à en distinguer les différentes classes comme autant d'occurrences représentant des \textit{régions} homogènes.
-Différents critères peuvent être appliqués pour cette analyse, visant par exemple à maximiser la variance \cite{otsu79} ou encore à maximiser le contraste pour déterminer les valeurs pertinentes des seuils.
-Malgré la multitude de variantes proposées, ces méthodes demeurent toutefois peu robustes et présentent l'inconvénient majeur de ne pas garantir la connexité des régions déterminées. On les réserve à des applications très spécifiques où, par exemple, on dispose d'une image de référence dont l'histogramme peut être comparé à celui des images à traiter. C'est le cas de certaines application de contrôle industriel où la simplicité algorithmique permet de surcroît des implémentations très rapides, voire câblées.
-Ces techniques sont aujourd'hui considérées comme rudimentaires mais les calculs d'histogrammes et les analyses associées interviennent dans beaucoup d'algorithmes récents parmi les plus évolués et performants.
-La figure \ref{fig-histo-cochon} illustre le traitement typique de l'histogramme de l'image d'entrée \ref{fig-histo-cochon-a} dans le but de distinguer les deux régions du fond et du cochon (la cible). La première étape consiste à dresser l'histogramme des niveaux de gris sur tout le domaine de l'image \ref{fig-histo-cochon-b}. Il faut ensuite identifier le seuil de séparation des deux régions supposées, ici, homogènes au sens des valeurs de niveau de gris. Une estimation visuelle peut-être faite, mais on voit immédiatement que même dans une situation aussi claire, le choix du seuil n'est pas évident. Pour un traitement automatique, on peut par exemple proposer la technique itérative présentée par l'Algorithme \ref{algo-histo-cochon} qui conduit à la segmentation de la figure \ref{fig-histo-cochon-c}. L'image \ref{fig-histo-cochon-d} est l'image initiale, corrompue par un bruit gaussien de moyenne nulle et d'écart type 25 . Les résultats de la segmentation (\ref{fig-histo-cochon-c} et \ref{fig-histo-cochon-f}) de cette image sont clairement insuffisants le segment de la cible comporte des discontinuités et dans le cas de l'image bruitée, des pixels orphelins épars demeurent en quantité. Cette technique nécessiterait une étape supplémentaire pour disposer d'une segmentation pertinente.
-
-\begin{figure}
- \centering
- \subfigure[Image initiale comportant deux zones : le fond et le cochon (la cible)]{\label{fig-histo-cochon-a} \includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/cochon256.png}}\quad
- \subfigure[Histogramme des niveaux de gris]{\label{fig-histo-cochon-b} \includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/seg_histogramme/histo-cochon256.png}}\quad
- \subfigure[Image binaire représentant la segmentation. Seuil estimé à 101 après 4 itérations.]{\label{fig-histo-cochon-c} \includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/seg_histogramme/cochon256-seghisto-101-255.png}}\\
-\subfigure[Image initiale bruitée]{\label{fig-histo-cochon-d} \includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/cochon256-sig25.png}}\quad
- \subfigure[Histogramme des niveaux de gris]{\label{fig-histo-cochon-e} \includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/seg_histogramme/histo-cochon256-sig25.png}}\quad
- \subfigure[Image binaire représentant la segmentation. Seuil estimé à 99 après 5 itérations.]{\label{fig-histo-cochon-f} \includegraphics[height=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/seg_histogramme/cochon256-sig25-seghisto-99-255.png}}
- \caption{Segmentation d'une image en niveaux de gris de 128 $\times$ 128 pixels par analyse simple d'histogramme. Colonne de gauche : image d'entrée. Colonne centrale : histogramme des niveaux de gris. Colonne de droite : résultat de la segmentation.}
-\label{fig-histo-cochon}
-\end{figure}
-
-\begin{algorithm}
- %\SetNlSty{textbf}{}{:}
- %\SetKwComment{Videcomment}{}{}
-\caption{Calcul du seuil de séparation des segments de l'histogramme.}
-\label{algo-histo-cochon}
-$\overline{h} \leftarrow $ histogramme sur l'image \;
-$S_{init} \leftarrow 128$ \;
-$S_k \leftarrow S_{init}$ \;
-$\epsilon \leftarrow 1$ \;
-\Repeat{$\|S_k - \frac{1}{2}(\mu_{inf} + \mu_{sup})\| < \epsilon $}{
- $\mu_{inf}=\displaystyle \frac{\displaystyle\sum_{i<S_k}h_ii}{\displaystyle\sum_{i<S_k}h_i}$ \;
- $\mu_{sup}=\displaystyle \frac{\displaystyle\sum_{i\geq S_k}h_ii}{\displaystyle\sum_{i\geq S_k}h_i}$ \;
- $S_k = \frac{1}{2}(\mu_{inf} + \mu_{sup})$ \ ;
-}
-\end{algorithm}
-
-\subsection{Analyse de graphe}
-Un autre formalisme qui a généré une vaste classe d'algorithmes de segmentation est celui des graphes et repose sur l'idée que les régions de l'image sont représentées par les n\oe uds du graphe, alors que les liens traduisent les relations de voisinage existant entre les régions.
-L'idée de base est d'initialiser le graphe avec un n\oe ud pour chaque pixel. La segmentation est obtenue par simplification itérative du graphe, en évaluant les liens et en déterminant ceux à supprimer et ce, jusqu'à convergence.
-L'essentiel de la problématique réside donc dans la métrique retenue pour évaluer les liens ainsi que dans le critère de sélection et là encore, la littérature regorge d'une grande variété de propositions.
-Nous pouvons retenir que les premières d'entre elles, qui n'étaient pas spécifiquement dédiées à la segmentation d'images numériques mais au regroupement d'éléments répartis sur un domaine (1D ou 2D), ont été élaborées autour d'une mesure locale des liens basée sur la distance entre les éléments. La réduction du graphe est ensuite effectuée en utilisant un algorithme spécifique, comme le \textit{minimum spanning tree}, dont l'application a été décrite dès 1970 dans \cite{slac-pub-0672} et où il s'agit simplement de supprimer les liens \textit{inconsistants}, c'est à dire ceux dont le poids est significativement plus élevé que la moyenne des voisins se trouvant de chaque coté du lien en question.
-L'extension a rapidement été faite aux images numériques en ajoutant l'intensité des pixels au vecteur des paramètres pris en compte dans l'évaluation du poids des liens.
-D'autres critères de simplification ont aussi été élaborés, avec pour ambition de toujours mieux prendre en compte les caractéristiques structurelles globales des images pour prétendre à une segmentation qui conduise à une meilleure perception conceptuelle.
-Le principe général des solutions actuelles est proche de l'analyse en composantes principales appliquée à une matrice de similarité qui traduit les liens entre les segments.
-Pour des images en niveaux de gris, l'expression générale des éléments $w_{ij}$ de la matrice de similarité $W$ est :
-\[w_{ij} =
-\begin{cases}
-\mathrm{e}^{\|v_i-v_j\|^2/\sigma_v^2}\mathrm{e}^{\|x_i-x_j\|^2/\sigma_x^2} & \text{si $\|x_i-x_j\|<r$}\\
-0 & \text{sinon}
-\end{cases}
-\]
-On construit ensuite la matrice de connectivité $D$, diagonale et dont les éléments sont :
-\[d_{i} = \displaystyle\sum_jw_{ij}\]
-
-Le système dont on cherche les valeurs propres $\lambda_k$ et les vecteurs propres associés $Y_k$ est alors le suivant :
-\[\left(D-W)\right)Y=\lambda DY \]
-
-Parmi les méthodes reposant sur ce principe, on peut citer, par ordre chronologique, celles qui reposent sur le \textit{graphe optimal} de Wu et Leahy \cite{wulealy_1993} et plus récemment \cite{cf-notes-x5}. Le principal point faible de ces techniques réside essentiellement dans la difficulté à trouver un compromis acceptable entre identification de structures globales et préservation des éléments de détails. Cela se traduit dans la pratique par un ensemble de paramètres à régler pour chaque type de segmentation à effectuer.
-Cependant, elles sont employées dans les algorithmes de haut niveau les plus récents, comme nous le verrons plus loin.
-La figure \ref{fig-graph-cochon} montre un exemple de l'application de l'algorithme \textit{normalized cuts} décrit dans \cite{sm-ncuts-pami2000} et implémenté par Cour, Yu et Shi en 2004. Cette implémentation utilise des valeurs pré-établies des paramètres de calcul de la matrice de similarité produisant de bonnes segmentations d'objets et/ou personnes dans les images naturelles, mais requiert de prédéterminer le nombre de segments à obtenir. Les images de la figure représentent les résultats obtenus avec un nombre de segments variant de 2 à 5 et montrent qu'il difficile de trouver un compromis acceptable. Enfin, les temps d'exécutions peuvent devenir très rapidement prohibitifs, même avec des implémentations plus optimisées. Pour information, les résultats de la figure \ref{fig-graph-cochon} ont été obtenus en 1.5~s environ (Matlab R2010 sur CPU intel core i5-2520M @ 2.50GHz - linux 3.2.0)
-\begin{figure}
- \centering
- \subfigure[$s = 2$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/graphe/cochon128_ncuts_2seg.png}}
- \subfigure[$s = 3$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/graphe/cochon128_ncuts_3seg.png}}
- \subfigure[$s = 4$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/graphe/cochon128_ncuts_4seg.png}}
- \subfigure[$s = 5$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/graphe/cochon128_ncuts_5seg.png}}
- \caption{Segmentation d'une image en niveaux de gris de 128 $\times$ 128 pixels par simplification de graphe de type \textit{Normalized cut} pour un nombre $s$ de segments variant de 2 à 5.}
-\label{fig-graph-cochon}
-\end{figure}
-
-
-\subsection{kernel-means, mean-shift et dérivés}
-Parallèlement à la réduction de graphes, d'autres approches ont donné naissance à une multitude de variantes tournées vers la recherche des moindres carrés.
-Il s'agit simplement de minimiser l'erreur quadratique totale, ce qui peut se résumer, pour une image de $N$ pixels, en la détermination du nombre $C$ de segments $\Omega_i$ et leur contenu, de sorte à minimiser l'expression
-\[\sum_{i\in[1..C]}\sum_{x_k\in\Omega_i} \left(v_k-\mu_i\right)^2\]
-où $\mu_i$ représente la valeur affectée au segment $\Omega_i$, i.e la valeur moyenne des observations $v_k$ sur $\Omega_i$, et $\displaystyle{\bigcup_{i\in[1..C]}\Omega_i=\Omega}$
-
-Cette idée est très intuitive et simple, mais n'a pas souvent de solution explicite, d'autant que le nombre des segments est \textit{a priori} inconnu.
-Dès 1965, Mac Queen a proposé l'appellation k-means pour cette procédure itérative de regroupement \cite{kmeans-1965} qui débute avec $k$ groupes d'un seul pixel\footnote{Dans son article, MacQueen ne parle pas de pixel mais de point. En effet, la méthode décrite ne visait pas à segmenter des images, mais des données de natures diverses.}
-pris au hasard, puis d'ajouter chaque point au groupe dont la moyenne est la plus proche de la valeur du point à ajouter. La moyenne du groupe nouvellement agrandi doit alors être recalculée avant le prochain ajout.
-Cette implémentation est extrêmement simple à mettre en \oe uvre \footnote{Même si en 1965, rien n'était simple à programmer} mais elle possède de nombreux défaut dont le principal est qu'elle ne converge pas nécessairement vers le regroupement optimal, même si on connait la ``bonne'' valeur de $k$.
-Un autre est d'être très dépendant du choix des $k$ éléments initiaux, en nombre et en position.
-
-Toutefois, vraisemblablement du fait de sa simplicité d'implémentation et de temps d'exécution rapides, la communauté scientifique s'est beaucoup penchée sur cette méthode pour en compenser les défauts, jusqu'à en faire une des plus employées, en particulier par les statisticiens.
-On compte aussi beaucoup de variantes telles les \textit{k-centers} \cite{k-centers} et les \textit{k-médians} \cite{k-medians} qui n'employent pas la moyenne arithmétique comme expression du ``centre'' d'un segment.
-Des solutions ont aussi été apportées pour l'estimation de $k$ en employant, par exemple, un critère de vraisemblance pour choisir la meilleure valeur de $k$ dans un intervalle donné \cite{x-means}.
-À titre d'illustration et de comparaison, l'image du cochon a été traitée par une implémentation naïve de l'algorithme original des \textit{k-means} en donnant successivement au nombre de segments les valeurs $s=2$ à $s=5$. Les résultats sont reproduits à la figure \ref{fig-kmeans-cochon} et montrent encore une fois l'influence de $s$ sur la segmentation.
-\begin{figure}
- \centering
- \subfigure[$s = 2$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/kmeans/cochon128_kmeans_2seg.png}}
- \subfigure[$s = 3$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/kmeans/cochon128_kmeans_3seg.png}}
- \subfigure[$s = 4$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/kmeans/cochon128_kmeans_4seg.png}}
- \subfigure[$s = 5$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/kmeans/cochon128_kmeans_5seg.png}}
- \caption{Segmentation d'une image en niveaux de gris de 128 $\times$ 128 pixels par algorithme \textit{k-means} pour un nombre $s$ de segments variant de 2 à 5. Chaque couleur est associée à un segment. Les couleurs sont choisies pour une meilleure visualisation des différents segments.}
-\label{fig-kmeans-cochon}
-\end{figure}
-
-Un algorithme initiallement proposé en 1975 par Fukunaga et Hostetler \cite{Lestimation-html} permet de manière plus générique de déterminer le nombre de segments, ou modes, ainsi que les points, ou pixels, qui les composent. Il cherche pour ce faire à localiser les $k$ positions ou le gradient de densité s'annule.
-Il utilisé un voisinage pondére (ou \textit{kernel}) et détermine le centre de masse des segments en suivant itérativement le gradient de densité dans le voisinage autour de chaque élément du domaine. Lorsque l'algorithme à convergé, les $k$ segments sont identifiés et continennent chacun l'ensemble des points qui ont conduit à leur centre de masse respectif.
-Étonnement, malgré ses qualités intrinsèques, cet algorithme du \textit{mean-shift} est resté longtemps sans susciter de grand intérêt, jusqu'à l'étude de Cheng \cite{meanshift_1995} qui en a demontré les propriétés et établi les lien avec d'autres techniques d'optimisation commme la descente/montée de gradient ou de filtrage commme le floutage.
-Comaniciu et Peer ont alors étendu l'étude et proposé une application à la segmentation en utilisant l'espace colorimétrique CIELUV \cite{Computer-Graphics-by-Foley-van-Dam-Feiner-and-Hughes-published-by-Addison-Wesley-1990} et montré qu'elle permettait une meilleure identification des modes de l'image \cite{mean-shift-1999,2002}.
-Une implémentation de la variante proposée par Keselman et Micheli-Tzanakou dans \cite{yket1999} appliquée à notre image de test fournit les résultats reproduits à la figure \ref{fig-meanshift-cochon}. Pour se rapprocher des traitements précédents, nous avons identifié, par essais successifs, les tailles de voisinage conduisant à des nombre de segments identiques à ceux des figures précedentes (de 2 à 5). Le volume minimal admis pour un segment à été arbitrairement fixé à 100 pixels.
-\begin{figure}
- \centering
- \subfigure[$r=100 \Rightarrow s = 2$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/meanshift/cochon128_meanshift_r100m100.png}}
- \subfigure[$r=50 \Rightarrow s = 3$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/meanshift/cochon128_meanshift_r50m100.png}}
-\subfigure[$r=35 \Rightarrow s = 4$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/meanshift/cochon128_meanshift_r35m100.png}}
- \subfigure[$r=25 \Rightarrow s = 5$]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/meanshift/cochon128_meanshift_r25m100.png}}
- \caption{Segmentation d'une image en niveaux de gris de 128 $\times$ 128 pixels par algorithme \textit{mean-shift} pour un rayon de voisinage $r$ de 100, 50, 35 et 25 pixels permettant d'obtenir un nombre $s$ de segments variant respectivement de 2 à 5. Le volume minimal admis pour un segment est fixé à 100 pixels. Chaque couleur est associée à un segment. Les couleurs sont choisies pour une meilleure visualisation des différents segments.}
-\label{fig-meanshift-cochon}
-\end{figure}
-
-Il est à noter que les segmentations basées sur des algorithmes de \textit{clustering} comme ceux que l'on vient de présenter nécessitent le plus souvent une phase supplémentaire de génération des frontières inter-segments et d'affectation de la valeur de chaque segment aux éléments qui le composent.
-Par ailleurs, dans les deux cas du \textit{k-means} et du \textit{mean-shift}, chaque itération génère une réduction de la variance (due au moyennage) et on peut donc rapprocher ces techniques de celles de réduction de bruit par minimisation de variance.
-
-\subsection{Les contours actifs, ou \textit{snakes}}
-Contrairement aux précédentes techniques et comme leur nom le laisse deviner, les éléments constitutifs de ces méthodes sont cette fois des \textit{contours} et non plus des \textit{régions}. De fait, ils définissent nativement une segmentation de l'image.
-Le principe général est de superposer une courbe paramétrique $S$ à l'image, le \textit{snake}, puis de lui appliquer des déformations successives destinées à rapprocher le \textit{snake} des contours de l'objet. Les déformations à appliquer sont guidées par l'évaluation d'une fonction d'énergie $E_{snake}$ prenant en compte :
-\begin{itemize}
-\item l'énergie interne $E_{int}$ de la courbe, fonction de son allongement de sa courbure.
-\item l'énergie externe $E_{ext}$ liée à l'image, fonction de la proximité de la courbe avec les zones de fort gradient et éventuellement une contrainte fixée par l'utilisateur comme des points imposés par exemple.
-\end{itemize}
-L'expression générique peut alors s'écrire
-\[E_{snake} = E_{int}+E_{ext}\]
-où
-\[E_{int} = \displaystyle\sum_{s\in S} \frac{1}{2}\left(\alpha\left|\frac{\partial x_s}{\partial s}\right|^2
-+\beta \left|\frac{\partial^2x_s}{\partial s^2}\right|\right)ds\]
-et
-\[E_{ext} = \displaystyle\sum_{s\in S} -\left|\nabla\left[G_{\sigma}(x_s)\ast v_s\right]\right|^2ds\]
-
-L'idée générale de l'algorithme du \textit{snake} est de trouver une courbe $S$ qui minimise l'énergie totale $E_{snake}$.
-Ici encore, la résolution du problème revient donc à minimiser une fonction sous contrainte et les diverses techniques de résolution numérique peuvent s'appliquer comme pour les autres classes d'algorithmes itératifs présentés précédemment, avec ici encore, un nombre de paramètres à régler assez important. Notons également que dans le cas général, les paramètres notés $\alpha$ et $\beta$, que l'on qualifie aussi d'élasticité et de raideur, sont aussi des fonctions de l'abscisse curviligne $s$. La fonction $G_{\sigma}$ est la fonction d'attraction aux forts gradients de l'image.
-
-Dans sa version originale proposée par Kass \textit{et al.} en 1988 \cite{snake-kass-1988}, l'algorithme dit du \textit{snake} présente l'intérêt de converger en un nombre d'itérations assez réduit et permet de suivre naturellement un \textit{cible} en mouvement après une convergence initiale à une position donnée, chaque position de convergence fournissant une position initiale pertinente pour la position suivante.
-Toutefois, il se montre particulièrement sensible à l'état initial de la courbe et requiert souvent de celle-ci qu'elle soit assez proche de l'objet à ``entourer'', sous peine de se verrouiller dans un minimum local.
-La sensibilité au bruit n'est pas non plus très bonne du fait de la formulation locale de l'énergie.
-Les ``concavités'' étroites ou présentant un goulot d'étranglement marqué sont par ailleurs mal délimitées.
-Enfin, la fonction d'énergie étant calculée sur la longueur totale de la courbe, cela pénalise la bonne identification des structures de petite taille vis à vis de la longueur totale de la courbe.
-La figure \ref{fig-snake-tradi-cochon} illustre ces défauts en montrant quelques états intérmédiaires ainsi que le résultat final d'une segmentation réalisée à partir d'un contour initial circulaire et des paramètres à valeurs constantes et réglés empiriquement, en employant la méthode du snake original.
-On voit que la convergence est assez rapide mais que le contour ainsi détérminé ne ``colle'' pas bien à l'objet que l'on s'attend à isoler.
-\begin{figure}
- \centering
-\subfigure[Les états initial et suivant chacune des trois premières itérations]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/snake/cochon128_tradi_snake_it3.png}}
-\subfigure[L'état du contour après la septième itération]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/snake/cochon128_tradi_snake_it7.png}}
-\subfigure[L'état du contour après la dixième itération]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/snake/cochon128_tradi_snake_it10.png}}
-\subfigure[L'état du contour après la centième itération. C'est le contour final.]{\includegraphics[width=3cm]{/home/zulu/Documents/these_gilles/THESE/codes/snake/cochon128_tradi_snake_result.png}}
-\caption{Segmentation d'une image en niveaux de gris de 128 $\times$ 128 pixels par algorithme dit du \textit{snake}, dans sa version originale. Les paramètres d'élastictié, de raideur et d'attraction ont été fixés respectivement aux valeurs 5, 0.1 et 5. }
-\label{fig-snake-tradi-cochon}
-\end{figure}
-
-Il est cependant possible de contrôler la finesse de la segmentation mais au prix de temps de calculs qui peuvent devenir très longs.
-Parmi les variantes élaborées qui tentent de pallier ces défauts, les plus intéressantes sont :
-\begin{itemize}
-\item le \textit{balloon snake}, conçu pour remédier au mauvais suivi des concavités en introduisant une force supplémentaire de pression tendant à \textit{gonfler} le snake jusqu'à ce qu'il rencontre un contour suffisamment marqué. Cela suppose toutefois que l'état initial de la courbe la situe entièrement à l'intérieur de la zone à segmenter et est surtout employé dans des applications semi-automatiques où l'utilisateur définit au moins une position et une taille initiales pour la courbe.
-\item le \textit{snake} GVF (pour Gradient Vector Flow), dont le but est de permettre qu'une initialisation lointaine de la courbe ne pénalise pas la segmentation. Une carte des lignes de gradient est établie sur tout le domaine de l'image et sert à intégrer une force supplémentaire dans l'énergie totale, qui attire la courbe vers la zone de fort gradient.
-\item les \textit{level-sets}, dont la particularité est de ne pas employer directement une courbe paramétrique plane mais de définir l'évolution des frontières comme l'évolution temporelle de l'ensemble des points d'une surface 3D soumise à un champ de force, tels que leur élévation soit constamment nulle.
-Les propriétés des contours actifs par \textit{level-sets} se sont révélées intéressantes, en particulier la faculté de se disjoindre ou de fusionner, mais les temps de calcul très pénalisants.
-Après la formulation initiale de Osher et Sethian en 1988 \cite{level-sets-osher-sethian-1988}, plusieurs façon de réduire le coût du calcul ont été formulées, dont les plus importantes restent les techniques dites \textit{narrow band} \cite{narrow-band-level-set} (bande étroite) qui ne calcule à chaque itération que les points dans une bande étroite autour du plan $z=0$ de l'itération courante et \textit{fast marching} \cite{fast_marching_sethian} qui s'applique dans le cas particulier d'une évolution monotone des fronts.
-\item les \textit{snake} orientés régions, qui visent essentiellement à mieux caractériser les zones à segmenter et améliorer la robustesse vis à vis du bruit en employant une formulation de l'énergie calculée sur le domaine complet de l'image \cite{cohenSMIE93, ronfard}. Les premiers résultats confirment la qualité de cette méthode, mais la nécessité d'effectuer les calculs sur l'image entière générait des temps de traitement prohibitifs jusqu'à ce que Bertaux \textit{et al.} proposent une amélioration algorithmique exacte permettant à nouveau un calcul en 1D, le long de la courbe, moyennant une simple étape initiale générant un certain nombre d'images intégrales \cite{snake-bertaux}. La section \ref{sec-contrib-snake} qui introduit notre contribution à cette technique en donnera une description détaillée.
-\end{itemize}
-
-% ne faut-il pas mieux éluder le paragraphe ci-dessous
-\subsection{Méthodes hybrides}
-Aujourd'hui, les algorithmes de segmentation les plus performants en terme de qualité emploient des techniques qui tentent de tirer le meilleur parti de plusieurs des méthodes ``historiques'' décrites précédemment.
-Le meilleur exemple, et le seul que nous citerons, est le détecteur de contour et l'algorithme de segmentation associé proposé par Arbelaez \textit{et al.} en 2010 \cite{amfm-2010}. Il compose avec la constructions d'histogrammes locaux pour générer une matrice de similitude (affinity matrix) et appliquer les techniques liées à la théorie des graphes pour réduire la dimension de l'espace de représentation (calcul des valeurs et vecteurs propres). Il utilise ensuite une technique adaptée de \textit{ligne de partage des eaux} \cite{watershed} (que l'on aurait rangée avec les mean-shift) pour regrouper les segments.
-Les résultats sont très bons et des implémentations efficaces ont dores et déjà été écrites (voir section \ref{sec_ea_gpu}.
-%TODO
-%peut-être dire deux mots sur le partage des eaux (avec kmeans et meanshift) puisqu'il est employé dans gPb
