From: zulu Date: Thu, 12 Sep 2013 06:11:28 +0000 (+0200) Subject: 12 sep X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_gilles.git/commitdiff_plain/2145c00e2163c4976cfc5dd2937ac2b5e7515892?ds=inline 12 sep --- diff --git a/THESE/Chapters/chapter2/chapter2.tex b/THESE/Chapters/chapter2/chapter2.tex index 7988109..b4368c0 100644 --- a/THESE/Chapters/chapter2/chapter2.tex +++ b/THESE/Chapters/chapter2/chapter2.tex @@ -83,7 +83,7 @@ Cet indicateur seul est cependant insuffisant pour caractériser convenablement \end{figure} \subsection{Les opérateurs de base} -\subsubsection{Les algorithmes de voisinage} +\subsubsection{Le filtre de convolution} L'opération la plus employée dans les procédés de traitement d'image est sans doute la convolution. Selon les valeurs affectées aux coefficients du masque, le filtrage par convolution permet de réaliser bon nombre de traitements comme la réduction de bruit par moyennage ou noyau gaussien ou encore la détection de contours. Si la fonction définissant le masque de convolution est notée $h$, l'expression générale de la valeur estimée de pixel de coordonnées $(i,j)$ est donnée par \begin{equation} @@ -105,6 +105,7 @@ Les matrices définissant les masques sont les suivantes : \label{fig-ny-convo} \end{figure} +\subsubsection{Le filtre médian} Le filtrage médian \cite{tukey77} est également une opération très employée en prétraitement pour sa simplicité et ses propriétés de préservation des contours alliées à une capacité de réduction de bruit gaussien importante. La valeur du niveau de gris de chaque pixel est remplacée par la médiane des niveaux de gris des pixels voisins. Un des intérêts de ce filtre réside dans le fait que la valeur filtrée est une des valeurs du voisinage, contrairement à ce qui se produit lors d'une convolution. Un autre est de bien filtrer les valeurs extrêmes et par conséquent de trouver naturellement son application dans la réduction du bruit impulsionnel. Toutefois, la non-linéraité de cette technique et sa complexité n'en ont pas fait un filtre très utilisé jusqu'à ce que des implémentation efficaces soient proposées, en particulier le filtre à temps de calcul ``constant'' décrit par Perreault et Hebert \cite{4287006}. Il est à noter que le filtrage médian est souvent appliqué en plusieurs passes de voisinage restreint. @@ -118,6 +119,8 @@ La figure \ref{fig-ny-median} montre la réduction de bruit impulsionnel obtenu \label{fig-ny-median} \end{figure} + +\subsubsection{Le filtre bilatéral} Le filtre bilatéral \cite{710815} est une composition d'opérations que l'on peut voir comme un filtre de convolution dont les coefficients ne dépendraient pas uniquement de la position du pixel courant par rapport au pixel central, mais également de la différence de leurs intensités (cas des images en niveaux de gris). Si l'on note $\Omega_k$ le voisinage du pixel d'indice $k$, l'expression générale du niveau de gris estimé est donnée par \[\widehat{u_k}=\displaystyle\frac{\sum_{p\in \Omega_k}\left(F_S(x_p, x_k)F_I(v_p, v_k)v_p\right)}{\sum_{p\in\Omega_k }\left(F_S(x_p, x_k)F_I(v_p, v_k)\right)} \] @@ -138,11 +141,13 @@ Ce filtre permet un bon niveau de réduction de bruit gaussien, mais au prix d'u \caption{Réduction de bruit gaussien par filtrage bilatéral de voisinage 5$\times$5. $\sigma_S$ et $\sigma_I$ sont les écarts type des fonctions gaussiennes de pondération spatiale et d'intensité.} \label{fig-ny-bilat} \end{figure} + +Il existe beaucoup de variantes d'algorithmes basés sur des moyennes ou médianes locales efféctuées sur des voisinages de formes diverses, variables et/ou adaptatives afin de sélectionner le plus finement possible les pixels pris en compte dans le calcul de la valeur filtrée. +Le principal défaut de ces techniques est de générer des aplats dans les zones homogènes et des marches d'escalier dans les zones de transition douce (staircase effect), ces dernières pouvant être considérablement atténuées comme il a été montré dans \cite{BuadesCM06}. +L'un de ces algorithmes tend à utiliser une portion de la ligne de niveau de chaque pixel comme voisinage pour le moyennage. Cette technique a été présentée dans \cite{bertaux2004speckle} et employée pour réduire le bruit de speckle. Nous y reviendrons en détail dans le chapitre \ref{ch-lniv}. -Beaucoup d'autres algorithmes basés sur des moyennes locales efféctuées sur des voisinages de formes diverses, variables et/ou adaptatives afin de sélectionner le plus finement possible les pixels pris en compte dans le calcul de la valeur filtrée. -Le principal défaut de ces techniques dites de réduction de variance est de générer des aplats dans les zones homogènes et des marches d'escalier dans les zones de transition douce (staircase effect), ces dernières pouvant être considérablement atténuées comme il a été montré dans \cite{BuadesCM06}. -\subsubsection{Les algorithmes par dictionnaire} +\subsubsection{Les algorithmes de filtrage par dictionnaire} Ces algorithmes font l'hypothèse qu'il est possible de décrire l'image à débruiter en utilisant une base de fonctions permettant de décomposer l'image en une combinaison linéaire des éléments de cette base. Les bases les plus employées sont les ondelettes \cite{Mallat:2008:WTS:1525499, Daubechies:1992:TLW:130655} ainsi que les fonctions sinusoïdales (DCT \cite{1093941,strang1999discrete}). Les éléments de la base peuvent être prédéterminés ou bien calculés à partir des données de l'image, par exemple en s'appuyant sur une analyse en composantes principales ou après apprentissage \cite{elad2006image}. Le principe du débruitage est de considérer que le bruit est décorellé des fonctions de la base et donc représenté par les petits coefficients de la décomposition, que l'on peut annuler. Diverses politiques de seuillage peuvent alors être appliquées selon le type d'image et le modèle de bruit ayant chacune ses propres avantages et inconvénients. L'intérêt principal de ces méthodes est de bien restituer les transitions rapides (grande énergie), mais elles génèrent en revanche des artefacts dus aux possibles grands coefficients de bruit. La figure \ref{fig-ny-dwt} illustre cela en montrant le résultat du débruitage obtenu par décomposition en ondelettes et seuillage ``dur''. Certains algorithmes récents, en particulier ceux utilisant une base d'ondelettes adaptative, comme dans \cite{elad2006image} sont proches, en terme de qualité, de l'état de l'art du domaine, avec souvent un avantage lié à des vitesses d'exécution assez rapides. @@ -157,7 +162,7 @@ Certains algorithmes récents, en particulier ceux utilisant une base d'ondelett \end{figure} -\subsection{Les techniques avancées} +\subsection{Les algorithmes de filtrage par patches} Les techniques de réduction de bruit les plus efficaces sont aujourd'hui celles qui reposent sur les propriétés d'auto-similarité ds images, on les appelles aussi les techniques par patchs. L'idée principale est, comme pour les techniques classiques à base de de voisinage, de rechercher un ensemble de pixels pertinents et comparables afin d'en faire une moyenne. Cependant, dans le cas des techniques à patchs, la recherche de cet ensemble ne se limite pas à un voisinage du pixel central, mais fait l'hypothèse qu'il existe des zones semblables au voisinage du pixel central, réparties dans l'image et pas nécessairement immédiatement contigues. Le moyennage s'effectue alors sur l'ensemble des ces zones identifiées. L'algorithme des moyennes non locales (NL-means, \cite{1467423}) fut parmi les premiers de cette lignée à être proposé et bien qu'ayant représenté un progrès notable dans la qualité de débruitage, fut rapidement suivi, en particulier par le BM3D et ses variantes qui représentent actuellement l'état de l'art en terme de qualité de débruitage \cite{Dabov06imagedenoising,Dabov09bm3dimage}. @@ -182,51 +187,86 @@ La figure \ref{fig-ny-nlm} montre des résultats de débruitage obtenus par la m \section{Les implémentations GPU des algorithmes de filtrage} Le fabricant de processeurs graphiques Nvidia, seul type d'équipements dont nous disposons, fournit des implémentations performantes de certains prétraitements et algorithmes de filtrage. C'est le cas des tranformées de fourrier (FFT, DCT), qui sont par exemple utilisées dans l'implémentation d'un algorithme d'\textit{inpainting} \cite{cmla2009Kes}. -C'est aussi vrai pour l'opération de convolution qui a fait l'objet d'une étude et d'une optimisation poussées pour déterminer la combinaison de solutions apportant la plus grande vitesse d'exécution \cite{convolutionsoup}. L'étude a testé 16 versions distinctes, chacune présentant une optimisation particulière quant-à l'organisation de la grille de calcul, aux types de transferts entre l'hôte et le GPU ainsi qu'au types de mémoire employé pour le calcul sur le GPU. Les résultats montrent que l'emploi de texture comme mémoire principale pour le stockage des images à traiter apporte un gain d'environ 50\% par rapport à l'utilisation de la mémoire globale. Par ailleurs, les transactions par paquets de 128 bits apportent également une amélioration sensible, ainsi que l'emploi de la mémoire partagée comme zone de travail pour le calcul des valeurs de sortie. Le traitement de référence effectué pour les mesures est la convolution générique (non séparable) d'une image 8 bits de 2048$\times$2048 pixels par un masque de convolution de 5$\times$5 pixels, expression que l'on raccourcira déronavant en \textit{convolution 5$\times$5}. + +\subsection{Le filtrage par convolution} +C'est aussi vrai pour l'opération de convolution qui a fait l'objet d'une étude et d'une optimisation poussées pour déterminer la combinaison de solutions apportant la plus grande vitesse d'exécution \cite{convolutionsoup}. L'étude a testé 16 versions distinctes, chacune présentant une optimisation particulière quant-à l'organisation de la grille de calcul, aux types de transferts entre l'hôte et le GPU ainsi qu'au types de mémoire employé pour le calcul sur le GPU. + +Les résultats montrent que l'emploi de texture comme mémoire principale pour le stockage des images à traiter apporte un gain d'environ 50\% par rapport à l'utilisation de la mémoire globale. Par ailleurs, les transactions par paquets de 128 bits apportent également une amélioration sensible, ainsi que l'emploi de la mémoire partagée comme zone de travail pour le calcul des valeurs de sortie. Le traitement de référence effectué pour les mesures est la convolution générique (non séparable) d'une image 8 bits de 2048$\times$2048 pixels par un masque de convolution de 5$\times$5 pixels, expression que l'on raccourcira déronavant en \textit{convolution 5$\times$5}. + Le meilleur résultat obtenu dans les conditions détaillées précédemment, sur architecture GT200 (carte GTX280) est de 1.4~ms pour le calcul, ce qui réalise un débit global de 945~MP/s lorsque l'on prend en compte les temps de transfert aller et retour des images (1.5~ms d'après nos mesures). Nous continuerons d'utiliser cette mesure de débit en \textit{Pixels par seconde} pour toutes les évaluations à venir ; elle permet en particulier de fournir des valeurs de performance indépendantes de la taille des images soumises au traitement. -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. +\subsection{Le filtre médian} +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. + +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. - + +\subsection{Le filtre bilatéral} 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. + +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 pour 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. La figure \ref{fig-prefetch-zheng} illustre la mise en \oe uvre de cette technique en montrant comment les threads d'un bloc se répartissent les pré-chargements en mémoire partagée des valeurs des pixels de la ROI. La géométrie des blocs de threads est ici choisie carrée, mais elle s'applique aisément à d'autres proportions comme nous le verrons plus loin. Les limites de cette méthode sont +\begin{itemize} +\item la taille de la mémoire partagée qui doit pouvoir stocker l'ensemble des valeurs des pixels de la ROI, ce qui peut imposer une limite sur la taille des blocs de threads. +\item l'étendue du voisinage qui ne peut être pré-chargé de cette façon (4 pixels par thread) que si la surface de la ROI demeure inférieure à 4 fois le nombre de thread par bloc. +\end{itemize} + +\begin{figure} + \centering + \includegraphics[width=10cm]{/home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/shmem_prefetch_zheng2011.png} +\caption{Illustration pré-chargement en mémoire partagée mise en \oe uvre dans \cite{zheng2011performance} pour l'implémentation, entre autres, du filtre bilatéral. a) en vert le bloc de threads associé aux pixels centraux. b-e) les blocs de pixels successivement pré-chargés en mémoire partagée. f) la configuration finale de la ROI en mémoire partagée.} +\label{fig-prefetch-zheng} +\end{figure} + +Cette recette est ensuite appliquée dans 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. - + +\subsection{Les filtres par patches} 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. +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, le modéle d'image 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. + +Généralement, 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. +Différents critères peuvent être appliqués pour cette analyse, visant par exemple à maximiser la variance \cite{4310076} 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. + +Ces techniques peuvent aujourd'hui être 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} @@ -260,8 +300,10 @@ $\epsilon \leftarrow 1$ \; \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. +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{Zahn:1971:GMD:1309266.1309359} 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. @@ -278,9 +320,10 @@ On construit ensuite la matrice de connectivité $D$, diagonale et dont les él 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) +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{wu1993optimal} et plus récemment \cite{wang2001image,wang2003image,felzenszwalb2004efficient,shi2000normalized}. 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. +Elles sont cependant 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{shi2000normalized} 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}} @@ -299,14 +342,14 @@ Il s'agit simplement de minimiser l'erreur quadratique totale, ce qui peut se r 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.} +Dès 1965, Mac Queen a proposé l'appellation k-means pour cette procédure itérative de regroupement \cite{macqueen1967some} 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}. +On compte aussi beaucoup de variantes telles les \textit{k-centers} \cite{agarwal2002exact} et les \textit{k-médians} \cite{arora1998approximation} 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{pelleg2000x}. À 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 @@ -318,11 +361,11 @@ Des solutions ont aussi été apportées pour l'estimation de $k$ en employant, \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. +Un algorithme initiallement proposé en 1975 par Fukunaga et Hostetler \cite{fukunaga1975estimation} 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. +É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{cheng1995mean} 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{foley1994introduction} et montré qu'elle permettait une meilleure identification des modes de l'image \cite{comaniciu1999mean,comaniciu2002mean}. +Une implémentation de la variante proposée par Keselman et Micheli-Tzanakou dans \cite{keselman1998extraction} 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}} @@ -354,7 +397,7 @@ et 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. +Dans sa version originale proposée par Kass \textit{et al.} en 1988 \cite{KassWT88}, 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. @@ -378,14 +421,26 @@ Parmi les variantes élaborées qui tentent de pallier ces défauts, les plus in \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. +Après la formulation initiale de Osher et Sethian en 1988 \cite{osher1988fronts}, 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{adalsteinsson1994fast} (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{sethian1996fast} 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{cohen1993surface, ronfard1994region}. 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{ChesnaudRB99,GallandBR03,GermainR01}. 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}. +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{arbelaez2011contour}. 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} (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 + +\section{Les implémentations GPU des techniques de segmentation} + +La problématique tant étudiée de la segmentation n'a pas échappé à l'engouement des chercheurs pour les processeurs graphiques modernes. Un certain nombre de travaux proposent ainsi des implémentations GPU plus ou moins directes de méthodes de segmentation tirant parti de l'architecture massivememnt parallèle de ces matériels. +La majorité d'entre elles cherche à répondre à des besoins liés à l'imagerie médicale allant de la simple extraction des contours d'un organe, d'une tumeur, etc., à la mesure de leur volume. La natures des tissus et les formes à identifier sont extrêmement variées. Les images sont souvent très bruitées et les modèles de bruit divers selon l'instrumentation employée. Enfin, le diagnostique médical requerant la plus grande précision possible, aucune solution générique satisfaisante de segmentation n'a encore pu émerger dans ce cadre, laissant place à autant d'implémentations adaptées que de besoin médical spécifique. + +Beaucoup d'algorithmes récents destinés à la segmentation comportent plusieurs phases de calcul et mettent en \oe uvre différents algorithmes réalisant des fonctions élémentaires comme de la réduction de bruit ou du calcul d'histogramme. + +%dire que les combianisons possibles sont nombreuses pour la conception, en fonction du niveau de prarllelisme. Par exmple, on peut calculer un histogramme par pixel mais le faire en sequentiel, ou bien chercher à paralleliser aussi le calcul d'histo. Das les deux cas, on dira histograme GPU, mais cela recouvrira des réalités et des niveaux de difficulté et de perf tres differents. + + + + \ No newline at end of file diff --git a/THESE/Chapters/chapter2/img/shmem_prefetch_zheng2011.png b/THESE/Chapters/chapter2/img/shmem_prefetch_zheng2011.png new file mode 100644 index 0000000..4fc252b Binary files /dev/null and b/THESE/Chapters/chapter2/img/shmem_prefetch_zheng2011.png differ diff --git a/THESE/biblio.bib b/THESE/biblio.bib index 7ca8309..1e12d97 100755 --- a/THESE/biblio.bib +++ b/THESE/biblio.bib @@ -710,4 +710,241 @@ ISSN={0190-3918},} pages={401}, year={1924}, publisher={Warwick \& York} +} +@ARTICLE{4310076, +journal={Systems, Man and Cybernetics, IEEE Transactions on}, +title={A Threshold Selection Method from Gray-Level Histograms}, +author={Otsu, N.}, +year={1979}, +volume={9}, +number={1}, +pages={62-66}, +keywords={Displays;Gaussian distribution;Histograms;Least squares approximation;Marine vehicles;Q measurement;Radar tracking;Sea measurements;Surveillance;Target tracking}, +doi={10.1109/TSMC.1979.4310076}, +ISSN={0018-9472},} +@article{Zahn:1971:GMD:1309266.1309359, + author = {Zahn, C. T.}, + title = {Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters}, + journal = {IEEE Trans. Comput.}, + issue_date = {January 1971}, + volume = {20}, + number = {1}, + month = jan, + year = {1971}, + issn = {0018-9340}, + pages = {68--86}, + numpages = {19}, + url = {http://dx.doi.org/10.1109/T-C.1971.223083}, + doi = {10.1109/T-C.1971.223083}, + acmid = {1309359}, + publisher = {IEEE Computer Society}, + address = {Washington, DC, USA}, + keywords = {Clustering, data structure analysis, feature space evaluation, gestalt psychology, graph theory, minimal spanning trees, nearest neighbor methods, numerical taxonomy, pattern recognition.}, +} +@article{wu1993optimal, + title={An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation}, + author={Wu, Zhenyu and Leahy, Richard}, + journal={Pattern Analysis and Machine Intelligence, IEEE Transactions on}, + volume={15}, + number={11}, + pages={1101--1113}, + year={1993}, + publisher={IEEE} +} +@article{felzenszwalb2004efficient, + title={Efficient graph-based image segmentation}, + author={Felzenszwalb, Pedro F and Huttenlocher, Daniel P}, + journal={International Journal of Computer Vision}, + volume={59}, + number={2}, + pages={167--181}, + year={2004}, + publisher={Springer} +} +@inproceedings{wang2001image, + title={Image segmentation with minimum mean cut}, + author={Wang, Song and Siskind, Jeffrey Mark}, + booktitle={Computer Vision, 2001. ICCV 2001. Proceedings. Eighth IEEE International Conference on}, + volume={1}, + pages={517--524}, + year={2001}, + organization={IEEE} +} +@article{wang2003image, + title={Image segmentation with ratio cut}, + author={Wang, Song and Siskind, Jeffrey Mark}, + journal={Pattern Analysis and Machine Intelligence, IEEE Transactions on}, + volume={25}, + number={6}, + pages={675--690}, + year={2003}, + publisher={IEEE} +} +@article{shi2000normalized, + title={Normalized cuts and image segmentation}, + author={Shi, Jianbo and Malik, Jitendra}, + journal={Pattern Analysis and Machine Intelligence, IEEE Transactions on}, + volume={22}, + number={8}, + pages={888--905}, + year={2000}, + publisher={IEEE} +} +@inproceedings{macqueen1967some, + title={Some methods for classification and analysis of multivariate observations}, + author={MacQueen, James and others}, + booktitle={Proceedings of the fifth Berkeley symposium on mathematical statistics and probability}, + volume={1}, + number={281-297}, + pages={14}, + year={1967}, + organization={California, USA} +} +@article{agarwal2002exact, + title={Exact and approximation algorithms for clustering}, + author={Agarwal, Pankaj K and Procopiuc, Cecilia Magdalena}, + journal={Algorithmica}, + volume={33}, + number={2}, + pages={201--226}, + year={2002}, + publisher={Springer} +} +@inproceedings{arora1998approximation, + title={Approximation schemes for Euclidean k-medians and related problems}, + author={Arora, Sanjeev and Raghavan, Prabhakar and Rao, Satish}, + booktitle={Proceedings of the thirtieth annual ACM symposium on Theory of computing}, + pages={106--113}, + year={1998}, + organization={ACM} +} +@inproceedings{pelleg2000x, + title={X-means: Extending K-means with Efficient Estimation of the Number of Clusters.}, + author={Pelleg, Dan and Moore, Andrew W and others}, + booktitle={ICML}, + pages={727--734}, + year={2000} +} +@article{fukunaga1975estimation, + title={The estimation of the gradient of a density function, with applications in pattern recognition}, + author={Fukunaga, Keinosuke and Hostetler, Larry}, + journal={Information Theory, IEEE Transactions on}, + volume={21}, + number={1}, + pages={32--40}, + year={1975}, + publisher={IEEE} +} +@article{cheng1995mean, + title={Mean shift, mode seeking, and clustering}, + author={Cheng, Yizong}, + journal={Pattern Analysis and Machine Intelligence, IEEE Transactions on}, + volume={17}, + number={8}, + pages={790--799}, + year={1995}, + publisher={IEEE} +} +@book{foley1994introduction, + title={Introduction to computer graphics}, + author={Foley, James D and Van Dam, Andries and Feiner, Steven K and Hughes, John F and Phillips, Richard L}, + volume={55}, + year={1994}, + publisher={Addison-Wesley Reading} +} +@inproceedings{comaniciu1999mean, + title={Mean shift analysis and applications}, + author={Comaniciu, Dorin and Meer, Peter}, + booktitle={Computer Vision, 1999. The Proceedings of the Seventh IEEE International Conference on}, + volume={2}, + pages={1197--1203}, + year={1999}, + organization={IEEE} +} +@article{comaniciu2002mean, + title={Mean shift: A robust approach toward feature space analysis}, + author={Comaniciu, Dorin and Meer, Peter}, + journal={Pattern Analysis and Machine Intelligence, IEEE Transactions on}, + volume={24}, + number={5}, + pages={603--619}, + year={2002}, + publisher={IEEE} +} +@inproceedings{keselman1998extraction, + title={Extraction and characterization of regions of interest in biomedical images}, + author={Keselman, Yakov and Micheli-Tzanakou, EVANGELIA}, + booktitle={Information Technology Applications in Biomedicine, 1998. ITAB 98. Proceedings. 1998 IEEE International Conference on}, + pages={87--90}, + year={1998}, + organization={IEEE} +} +@article{osher1988fronts, + title={Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations}, + author={Osher, Stanley and Sethian, James A}, + journal={Journal of computational physics}, + volume={79}, + number={1}, + pages={12--49}, + year={1988}, + publisher={Elsevier} +} +@phdthesis{adalsteinsson1994fast, + title={A fast level set method for propagating interfaces}, + author={Adalsteinsson, David and Sethian, James}, + year={1994}, + school={University of California} +} +@article{sethian1996fast, + title={A fast marching level set method for monotonically advancing fronts}, + author={Sethian, James A}, + journal={Proceedings of the National Academy of Sciences}, + volume={93}, + number={4}, + pages={1591--1595}, + year={1996}, + publisher={National Acad Sciences} +} +@article{cohen1993surface, + title={Surface reconstruction using active contour models}, + author={Cohen, Laurent D and Bardinet, Eric and Ayache, Nicholas and others}, + year={1993} +} +@article{ronfard1994region, + title={Region-based strategies for active contour models}, + author={Ronfard, R{\'e}mi}, + journal={International Journal of Computer Vision}, + volume={13}, + number={2}, + pages={229--251}, + year={1994}, + publisher={Springer} +} +@article{arbelaez2011contour, + title={Contour detection and hierarchical image segmentation}, + author={Arbelaez, Pablo and Maire, Michael and Fowlkes, Charless and Malik, Jitendra}, + journal={Pattern Analysis and Machine Intelligence, IEEE Transactions on}, + volume={33}, + number={5}, + pages={898--916}, + year={2011}, + publisher={IEEE} +} +@INPROCEEDINGS{6005963, +author={Lanfang Dong and Jiahui Chen and Jin Wang}, +booktitle={Image and Graphics (ICIG), 2011 Sixth International Conference on}, +title={A Real-Time Isoline Tracing Algorithm Based on CUDA}, +year={2011}, +pages={864-867}, +keywords={data visualisation;multi-threading;GPU multithread;compute unified device architecture;graphics processing unit;isoline tracing algorithm;reservoir simulation visualization;texture memory;Algorithm design and analysis;Arrays;Data visualization;Graphics processing unit;Indexes;Instruction sets;Real time systems;CUDA;Isoline Tracing;Real-time}, +doi={10.1109/ICIG.2011.117},} +@article{bertaux2004speckle, + title={Speckle removal using a maximum-likelihood technique with isoline gray-level regularization}, + author={Bertaux, Nicolas and Frauel, Yann and R{\'e}fr{\'e}gier, Philippe and Javidi, Bahram}, + journal={JOSA A}, + volume={21}, + number={12}, + pages={2283--2291}, + year={2004}, + publisher={Optical Society of America} } \ No newline at end of file diff --git a/THESE/these.aux b/THESE/these.aux index 39abc51..9e64a83 100644 --- a/THESE/these.aux +++ b/THESE/these.aux @@ -47,19 +47,21 @@ \@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {Bruit gaussien $\sigma =25$, PSNR=22.3~dB MSSIM=0.16}}}{14}{figure.2.1}} \@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {Bruit impulsionnel 25\%, PSNR=9.48~dB MSSIM=0.04}}}{14}{figure.2.1}} \@writefile{toc}{\contentsline {subsection}{\numberline {2.3.1}Les op\IeC {\'e}rateurs de base}{14}{subsection.2.3.1}} -\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.3.1.1}Les algorithmes de voisinage}{14}{subsubsection.2.3.1.1}} +\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.3.1.1}Le filtre de convolution}{14}{subsubsection.2.3.1.1}} \citation{tukey77} \citation{4287006} -\citation{710815} \@writefile{lof}{\contentsline {figure}{\numberline {2.2}{\ignorespaces Filtrage par convolution.}}{15}{figure.2.2}} \newlabel{fig-ny-convo}{{2.2}{15}{Filtrage par convolution}{figure.2.2}{}} \@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {Moyenneur 3$\times $3, PSNR=27.6dB MSSIM=0.34}}}{15}{figure.2.2}} \@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {Moyenneur 5$\times $5, PSNR=27.7dB MSSIM=0.38}}}{15}{figure.2.2}} \@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {Filtre gaussien 3$\times $3, PSNR=27.4dB MSSIM=0.33}}}{15}{figure.2.2}} -\newlabel{convoDef}{{2.1}{15}{Les algorithmes de voisinage\relax }{equation.2.3.1}{}} +\newlabel{convoDef}{{2.1}{15}{Le filtre de convolution\relax }{equation.2.3.1}{}} +\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.3.1.2}Le filtre m\IeC {\'e}dian}{15}{subsubsection.2.3.1.2}} +\citation{710815} \citation{1521458} \citation{4587843} \citation{BuadesCM06} +\citation{bertaux2004speckle} \citation{Mallat:2008:WTS:1525499} \citation{Daubechies:1992:TLW:130655} \citation{1093941} @@ -71,7 +73,7 @@ \@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {M\IeC {\'e}dian 3$\times $3 une passe, PSNR=26.4~dB MSSIM=0.90}}}{16}{figure.2.3}} \@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {M\IeC {\'e}dian 3$\times $3 deux passes, PSNR=34.4~dB MSSIM=0.98}}}{16}{figure.2.3}} \@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {M\IeC {\'e}dian 5$\times $5 une passe, PSNR=35.1~dB MSSIM=0.98}}}{16}{figure.2.3}} -\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.3.1.2}Les algorithmes par dictionnaire}{16}{subsubsection.2.3.1.2}} +\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.3.1.3}Le filtre bilat\IeC {\'e}ral}{16}{subsubsection.2.3.1.3}} \@writefile{lof}{\contentsline {figure}{\numberline {2.4}{\ignorespaces R\IeC {\'e}duction de bruit gaussien par filtrage bilat\IeC {\'e}ral de voisinage 5$\times $5. $\sigma _S$ et $\sigma _I$ sont les \IeC {\'e}carts type des fonctions gaussiennes de pond\IeC {\'e}ration spatiale et d'intensit\IeC {\'e}.}}{17}{figure.2.4}} \newlabel{fig-ny-bilat}{{2.4}{17}{Réduction de bruit gaussien par filtrage bilatéral de voisinage 5$\times $5. $\sigma _S$ et $\sigma _I$ sont les écarts type des fonctions gaussiennes de pondération spatiale et d'intensité}{figure.2.4}{}} \@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {$\sigma _S=1.0$ et $\sigma _I=0.1$, PSNR=25.6~dB MSSIM=0.25}}}{17}{figure.2.4}} @@ -91,7 +93,8 @@ \@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {$T=20$, PSNR=26.9~dB MSSIM=0.30}}}{18}{figure.2.5}} \@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {$T=35$, PSNR=27.6~dB MSSIM=0.36}}}{18}{figure.2.5}} \@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {$T=70$, PSNR=26.7~dB MSSIM=0.37}}}{18}{figure.2.5}} -\@writefile{toc}{\contentsline {subsection}{\numberline {2.3.2}Les techniques avanc\IeC {\'e}es}{18}{subsection.2.3.2}} +\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.3.1.4}Les algorithmes de filtrage par dictionnaire}{18}{subsubsection.2.3.1.4}} +\@writefile{toc}{\contentsline {subsection}{\numberline {2.3.2}Les algorithmes de filtrage par patches}{18}{subsection.2.3.2}} \citation{cmla2009Kes} \citation{convolutionsoup} \@writefile{lof}{\contentsline {figure}{\numberline {2.6}{\ignorespaces Filtrage par NL-means pour diff\IeC {\'e}rentes combinaisons des param\IeC {\`e}tres de similarit\IeC {\'e} $f$ et de non localit\IeC {\'e} $t$.}}{19}{figure.2.6}} @@ -108,134 +111,176 @@ \citation{5402362} \citation{chen09} \citation{5402362} +\@writefile{toc}{\contentsline {subsection}{\numberline {2.4.1}Le filtrage par convolution}{20}{subsection.2.4.1}} +\@writefile{toc}{\contentsline {subsection}{\numberline {2.4.2}Le filtre m\IeC {\'e}dian}{20}{subsection.2.4.2}} \citation{aldinucci2012parallel} \citation{5206542} \citation{zheng2011performance} +\citation{zheng2011performance} +\citation{zheng2011performance} +\@writefile{toc}{\contentsline {subsection}{\numberline {2.4.3}Le filtre bilat\IeC {\'e}ral}{21}{subsection.2.4.3}} \citation{PALHANOXAVIERDEFONTES} \citation{nlmeansgpubelge} -\@writefile{toc}{\contentsline {section}{\numberline {2.5}Les techniques de segmentation}{21}{section.2.5}} -\citation{biblio-web} -\citation{otsu79} -\@writefile{toc}{\contentsline {subsection}{\numberline {2.5.1}Analyse d'histogramme}{22}{subsection.2.5.1}} -\citation{slac-pub-0672} -\newlabel{fig-histo-cochon-a}{{2.8(a)}{23}{Subfigure 2 2.8(a)\relax }{subfigure.2.8.1}{}} -\newlabel{sub@fig-histo-cochon-a}{{(a)}{23}{Subfigure 2 2.8(a)\relax }{subfigure.2.8.1}{}} -\newlabel{fig-histo-cochon-b}{{2.8(b)}{23}{Subfigure 2 2.8(b)\relax }{subfigure.2.8.2}{}} -\newlabel{sub@fig-histo-cochon-b}{{(b)}{23}{Subfigure 2 2.8(b)\relax }{subfigure.2.8.2}{}} -\newlabel{fig-histo-cochon-c}{{2.8(c)}{23}{Subfigure 2 2.8(c)\relax }{subfigure.2.8.3}{}} -\newlabel{sub@fig-histo-cochon-c}{{(c)}{23}{Subfigure 2 2.8(c)\relax }{subfigure.2.8.3}{}} -\newlabel{fig-histo-cochon-d}{{2.8(d)}{23}{Subfigure 2 2.8(d)\relax }{subfigure.2.8.4}{}} -\newlabel{sub@fig-histo-cochon-d}{{(d)}{23}{Subfigure 2 2.8(d)\relax }{subfigure.2.8.4}{}} -\newlabel{fig-histo-cochon-e}{{2.8(e)}{23}{Subfigure 2 2.8(e)\relax }{subfigure.2.8.5}{}} -\newlabel{sub@fig-histo-cochon-e}{{(e)}{23}{Subfigure 2 2.8(e)\relax }{subfigure.2.8.5}{}} -\newlabel{fig-histo-cochon-f}{{2.8(f)}{23}{Subfigure 2 2.8(f)\relax }{subfigure.2.8.6}{}} -\newlabel{sub@fig-histo-cochon-f}{{(f)}{23}{Subfigure 2 2.8(f)\relax }{subfigure.2.8.6}{}} -\@writefile{lof}{\contentsline {figure}{\numberline {2.8}{\ignorespaces Segmentation d'une image en niveaux de gris de 128 $\times $ 128 pixels par analyse simple d'histogramme. Colonne de gauche : image d'entr\IeC {\'e}e. Colonne centrale : histogramme des niveaux de gris. Colonne de droite : r\IeC {\'e}sultat de la segmentation.}}{23}{figure.2.8}} -\newlabel{fig-histo-cochon}{{2.8}{23}{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}{figure.2.8}{}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {Image initiale comportant deux zones : le fond et le cochon (la cible)}}}{23}{figure.2.8}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {Histogramme des niveaux de gris}}}{23}{figure.2.8}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {Image binaire repr\IeC {\'e}sentant la segmentation. Seuil estim\IeC {\'e} \IeC {\`a} 101 apr\IeC {\`e}s 4 it\IeC {\'e}rations.}}}{23}{figure.2.8}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(d)}{\ignorespaces {Image initiale bruit\IeC {\'e}e}}}{23}{figure.2.8}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(e)}{\ignorespaces {Histogramme des niveaux de gris}}}{23}{figure.2.8}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(f)}{\ignorespaces {Image binaire repr\IeC {\'e}sentant la segmentation. Seuil estim\IeC {\'e} \IeC {\`a} 99 apr\IeC {\`e}s 5 it\IeC {\'e}rations.}}}{23}{figure.2.8}} -\@writefile{toc}{\contentsline {subsection}{\numberline {2.5.2}Analyse de graphe}{23}{subsection.2.5.2}} -\citation{wulealy_1993} -\citation{cf-notes-x5} -\citation{sm-ncuts-pami2000} -\@writefile{loa}{\contentsline {algocf}{\numberline {1}{\ignorespaces Calcul du seuil de s\IeC {\'e}paration des segments de l'histogramme.}}{24}{algocfline.1}} -\newlabel{algo-histo-cochon}{{1}{24}{Analyse d'histogramme\relax }{algocfline.1}{}} -\citation{kmeans-1965} -\@writefile{lof}{\contentsline {figure}{\numberline {2.9}{\ignorespaces 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 \IeC {\`a} 5.}}{25}{figure.2.9}} -\newlabel{fig-graph-cochon}{{2.9}{25}{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}{figure.2.9}{}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {$s = 2$}}}{25}{figure.2.9}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {$s = 3$}}}{25}{figure.2.9}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {$s = 4$}}}{25}{figure.2.9}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(d)}{\ignorespaces {$s = 5$}}}{25}{figure.2.9}} -\@writefile{toc}{\contentsline {subsection}{\numberline {2.5.3}kernel-means, mean-shift et d\IeC {\'e}riv\IeC {\'e}s}{25}{subsection.2.5.3}} -\citation{k-centers} -\citation{k-medians} -\citation{x-means} -\citation{Lestimation-html} -\citation{meanshift_1995} -\citation{Computer-Graphics-by-Foley-van-Dam-Feiner-and-Hughes-published-by-Addison-Wesley-1990} -\citation{mean-shift-1999} -\citation{2002} -\citation{yket1999} -\@writefile{lof}{\contentsline {figure}{\numberline {2.10}{\ignorespaces 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 \IeC {\`a} 5. Chaque couleur est associ\IeC {\'e}e \IeC {\`a} un segment. Les couleurs sont choisies pour une meilleure visualisation des diff\IeC {\'e}rents segments.}}{26}{figure.2.10}} -\newlabel{fig-kmeans-cochon}{{2.10}{26}{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}{figure.2.10}{}} +\@writefile{lof}{\contentsline {figure}{\numberline {2.8}{\ignorespaces Illustration pr\IeC {\'e}-chargement en m\IeC {\'e}moire partag\IeC {\'e}e mise en \oe uvre dans \cite {zheng2011performance} pour l'impl\IeC {\'e}mentation, entre autres, du filtre bilat\IeC {\'e}ral. a) en vert le bloc de threads associ\IeC {\'e} aux pixels centraux. b-e) les blocs de pixels successivement pr\IeC {\'e}-charg\IeC {\'e}s en m\IeC {\'e}moire partag\IeC {\'e}e. f) la configuration finale de la ROI en m\IeC {\'e}moire partag\IeC {\'e}e.}}{22}{figure.2.8}} +\newlabel{fig-prefetch-zheng}{{2.8}{22}{Illustration pré-chargement en mémoire partagée mise en \oe uvre dans \cite {zheng2011performance} pour l'implémentation, entre autres, du filtre bilatéral. a) en vert le bloc de threads associé aux pixels centraux. b-e) les blocs de pixels successivement pré-chargés en mémoire partagée. f) la configuration finale de la ROI en mémoire partagée}{figure.2.8}{}} +\@writefile{toc}{\contentsline {subsection}{\numberline {2.4.4}Les filtres par patches}{22}{subsection.2.4.4}} +\citation{humphrey1924psychology} +\citation{4310076} +\@writefile{toc}{\contentsline {section}{\numberline {2.5}Les techniques de segmentation}{23}{section.2.5}} +\@writefile{toc}{\contentsline {subsection}{\numberline {2.5.1}Analyse d'histogramme}{23}{subsection.2.5.1}} +\newlabel{fig-histo-cochon-a}{{2.9(a)}{24}{Subfigure 2 2.9(a)\relax }{subfigure.2.9.1}{}} +\newlabel{sub@fig-histo-cochon-a}{{(a)}{24}{Subfigure 2 2.9(a)\relax }{subfigure.2.9.1}{}} +\newlabel{fig-histo-cochon-b}{{2.9(b)}{24}{Subfigure 2 2.9(b)\relax }{subfigure.2.9.2}{}} +\newlabel{sub@fig-histo-cochon-b}{{(b)}{24}{Subfigure 2 2.9(b)\relax }{subfigure.2.9.2}{}} +\newlabel{fig-histo-cochon-c}{{2.9(c)}{24}{Subfigure 2 2.9(c)\relax }{subfigure.2.9.3}{}} +\newlabel{sub@fig-histo-cochon-c}{{(c)}{24}{Subfigure 2 2.9(c)\relax }{subfigure.2.9.3}{}} +\newlabel{fig-histo-cochon-d}{{2.9(d)}{24}{Subfigure 2 2.9(d)\relax }{subfigure.2.9.4}{}} +\newlabel{sub@fig-histo-cochon-d}{{(d)}{24}{Subfigure 2 2.9(d)\relax }{subfigure.2.9.4}{}} +\newlabel{fig-histo-cochon-e}{{2.9(e)}{24}{Subfigure 2 2.9(e)\relax }{subfigure.2.9.5}{}} +\newlabel{sub@fig-histo-cochon-e}{{(e)}{24}{Subfigure 2 2.9(e)\relax }{subfigure.2.9.5}{}} +\newlabel{fig-histo-cochon-f}{{2.9(f)}{24}{Subfigure 2 2.9(f)\relax }{subfigure.2.9.6}{}} +\newlabel{sub@fig-histo-cochon-f}{{(f)}{24}{Subfigure 2 2.9(f)\relax }{subfigure.2.9.6}{}} +\@writefile{lof}{\contentsline {figure}{\numberline {2.9}{\ignorespaces Segmentation d'une image en niveaux de gris de 128 $\times $ 128 pixels par analyse simple d'histogramme. Colonne de gauche : image d'entr\IeC {\'e}e. Colonne centrale : histogramme des niveaux de gris. Colonne de droite : r\IeC {\'e}sultat de la segmentation.}}{24}{figure.2.9}} +\newlabel{fig-histo-cochon}{{2.9}{24}{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}{figure.2.9}{}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {Image initiale comportant deux zones : le fond et le cochon (la cible)}}}{24}{figure.2.9}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {Histogramme des niveaux de gris}}}{24}{figure.2.9}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {Image binaire repr\IeC {\'e}sentant la segmentation. Seuil estim\IeC {\'e} \IeC {\`a} 101 apr\IeC {\`e}s 4 it\IeC {\'e}rations.}}}{24}{figure.2.9}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(d)}{\ignorespaces {Image initiale bruit\IeC {\'e}e}}}{24}{figure.2.9}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(e)}{\ignorespaces {Histogramme des niveaux de gris}}}{24}{figure.2.9}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(f)}{\ignorespaces {Image binaire repr\IeC {\'e}sentant la segmentation. Seuil estim\IeC {\'e} \IeC {\`a} 99 apr\IeC {\`e}s 5 it\IeC {\'e}rations.}}}{24}{figure.2.9}} +\@writefile{toc}{\contentsline {subsection}{\numberline {2.5.2}Analyse de graphe}{24}{subsection.2.5.2}} +\citation{Zahn:1971:GMD:1309266.1309359} +\@writefile{loa}{\contentsline {algocf}{\numberline {1}{\ignorespaces Calcul du seuil de s\IeC {\'e}paration des segments de l'histogramme.}}{25}{algocfline.1}} +\newlabel{algo-histo-cochon}{{1}{25}{Analyse d'histogramme\relax }{algocfline.1}{}} +\citation{wu1993optimal} +\citation{wang2001image} +\citation{wang2003image} +\citation{felzenszwalb2004efficient} +\citation{shi2000normalized} +\citation{shi2000normalized} +\citation{macqueen1967some} +\@writefile{lof}{\contentsline {figure}{\numberline {2.10}{\ignorespaces 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 \IeC {\`a} 5.}}{26}{figure.2.10}} +\newlabel{fig-graph-cochon}{{2.10}{26}{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}{figure.2.10}{}} \@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {$s = 2$}}}{26}{figure.2.10}} \@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {$s = 3$}}}{26}{figure.2.10}} \@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {$s = 4$}}}{26}{figure.2.10}} \@writefile{lof}{\contentsline {subfigure}{\numberline{(d)}{\ignorespaces {$s = 5$}}}{26}{figure.2.10}} -\@writefile{lof}{\contentsline {figure}{\numberline {2.11}{\ignorespaces 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 \IeC {\`a} 5. Le volume minimal admis pour un segment est fix\IeC {\'e} \IeC {\`a} 100 pixels. Chaque couleur est associ\IeC {\'e}e \IeC {\`a} un segment. Les couleurs sont choisies pour une meilleure visualisation des diff\IeC {\'e}rents segments.}}{27}{figure.2.11}} -\newlabel{fig-meanshift-cochon}{{2.11}{27}{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}{figure.2.11}{}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {$r=100 \Rightarrow s = 2$}}}{27}{figure.2.11}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {$r=50 \Rightarrow s = 3$}}}{27}{figure.2.11}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {$r=35 \Rightarrow s = 4$}}}{27}{figure.2.11}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(d)}{\ignorespaces {$r=25 \Rightarrow s = 5$}}}{27}{figure.2.11}} -\@writefile{toc}{\contentsline {subsection}{\numberline {2.5.4}Les contours actifs, ou \textit {snakes}}{27}{subsection.2.5.4}} -\citation{snake-kass-1988} -\citation{level-sets-osher-sethian-1988} -\citation{narrow-band-level-set} -\citation{fast_marching_sethian} -\@writefile{lof}{\contentsline {figure}{\numberline {2.12}{\ignorespaces 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\IeC {\`e}tres d'\IeC {\'e}lasticti\IeC {\'e}, de raideur et d'attraction ont \IeC {\'e}t\IeC {\'e} fix\IeC {\'e}s respectivement aux valeurs 5, 0.1 et 5. }}{28}{figure.2.12}} -\newlabel{fig-snake-tradi-cochon}{{2.12}{28}{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. \relax }{figure.2.12}{}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {Les \IeC {\'e}tats initial et suivant chacune des trois premi\IeC {\`e}res it\IeC {\'e}rations}}}{28}{figure.2.12}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {L'\IeC {\'e}tat du contour apr\IeC {\`e}s la septi\IeC {\`e}me it\IeC {\'e}ration}}}{28}{figure.2.12}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {L'\IeC {\'e}tat du contour apr\IeC {\`e}s la dixi\IeC {\`e}me it\IeC {\'e}ration}}}{28}{figure.2.12}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(d)}{\ignorespaces {L'\IeC {\'e}tat du contour apr\IeC {\`e}s la centi\IeC {\`e}me it\IeC {\'e}ration. C'est le contour final.}}}{28}{figure.2.12}} -\citation{cohenSMIE93} -\citation{ronfard} -\citation{snake-bertaux} -\citation{amfm-2010} -\citation{watershed} -\@writefile{toc}{\contentsline {subsection}{\numberline {2.5.5}M\IeC {\'e}thodes hybrides}{29}{subsection.2.5.5}} -\@writefile{toc}{\contentsline {section}{\numberline {2.6}L'\IeC {\'e}tat de l'art des impl\IeC {\'e}mentations GPU}{29}{section.2.6}} -\@writefile{toc}{\contentsline {chapter}{\numberline {3}La segmentation orient\IeC {\'e}e r\IeC {\'e}gions dans les images bruit\IeC {\'e}es}{31}{chapter.3}} +\@writefile{toc}{\contentsline {subsection}{\numberline {2.5.3}kernel-means, mean-shift et d\IeC {\'e}riv\IeC {\'e}s}{26}{subsection.2.5.3}} +\citation{agarwal2002exact} +\citation{arora1998approximation} +\citation{pelleg2000x} +\citation{fukunaga1975estimation} +\citation{cheng1995mean} +\citation{foley1994introduction} +\citation{comaniciu1999mean} +\citation{comaniciu2002mean} +\citation{keselman1998extraction} +\@writefile{lof}{\contentsline {figure}{\numberline {2.11}{\ignorespaces 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 \IeC {\`a} 5. Chaque couleur est associ\IeC {\'e}e \IeC {\`a} un segment. Les couleurs sont choisies pour une meilleure visualisation des diff\IeC {\'e}rents segments.}}{27}{figure.2.11}} +\newlabel{fig-kmeans-cochon}{{2.11}{27}{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}{figure.2.11}{}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {$s = 2$}}}{27}{figure.2.11}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {$s = 3$}}}{27}{figure.2.11}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {$s = 4$}}}{27}{figure.2.11}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(d)}{\ignorespaces {$s = 5$}}}{27}{figure.2.11}} +\@writefile{lof}{\contentsline {figure}{\numberline {2.12}{\ignorespaces 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 \IeC {\`a} 5. Le volume minimal admis pour un segment est fix\IeC {\'e} \IeC {\`a} 100 pixels. Chaque couleur est associ\IeC {\'e}e \IeC {\`a} un segment. Les couleurs sont choisies pour une meilleure visualisation des diff\IeC {\'e}rents segments.}}{28}{figure.2.12}} +\newlabel{fig-meanshift-cochon}{{2.12}{28}{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}{figure.2.12}{}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {$r=100 \Rightarrow s = 2$}}}{28}{figure.2.12}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {$r=50 \Rightarrow s = 3$}}}{28}{figure.2.12}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {$r=35 \Rightarrow s = 4$}}}{28}{figure.2.12}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(d)}{\ignorespaces {$r=25 \Rightarrow s = 5$}}}{28}{figure.2.12}} +\@writefile{toc}{\contentsline {subsection}{\numberline {2.5.4}Les contours actifs, ou \textit {snakes}}{28}{subsection.2.5.4}} +\citation{KassWT88} +\@writefile{lof}{\contentsline {figure}{\numberline {2.13}{\ignorespaces 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\IeC {\`e}tres d'\IeC {\'e}lasticti\IeC {\'e}, de raideur et d'attraction ont \IeC {\'e}t\IeC {\'e} fix\IeC {\'e}s respectivement aux valeurs 5, 0.1 et 5. }}{29}{figure.2.13}} +\newlabel{fig-snake-tradi-cochon}{{2.13}{29}{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. \relax }{figure.2.13}{}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {Les \IeC {\'e}tats initial et suivant chacune des trois premi\IeC {\`e}res it\IeC {\'e}rations}}}{29}{figure.2.13}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {L'\IeC {\'e}tat du contour apr\IeC {\`e}s la septi\IeC {\`e}me it\IeC {\'e}ration}}}{29}{figure.2.13}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {L'\IeC {\'e}tat du contour apr\IeC {\`e}s la dixi\IeC {\`e}me it\IeC {\'e}ration}}}{29}{figure.2.13}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(d)}{\ignorespaces {L'\IeC {\'e}tat du contour apr\IeC {\`e}s la centi\IeC {\`e}me it\IeC {\'e}ration. C'est le contour final.}}}{29}{figure.2.13}} +\citation{osher1988fronts} +\citation{adalsteinsson1994fast} +\citation{sethian1996fast} +\citation{cohen1993surface} +\citation{ronfard1994region} +\citation{ChesnaudRB99} +\citation{GallandBR03} +\citation{GermainR01} +\citation{arbelaez2011contour} +\@writefile{toc}{\contentsline {subsection}{\numberline {2.5.5}M\IeC {\'e}thodes hybrides}{30}{subsection.2.5.5}} +\@writefile{toc}{\contentsline {section}{\numberline {2.6}L'\IeC {\'e}tat de l'art des impl\IeC {\'e}mentations GPU}{31}{section.2.6}} +\@writefile{toc}{\contentsline {chapter}{\numberline {3}La segmentation orient\IeC {\'e}e r\IeC {\'e}gions dans les images bruit\IeC {\'e}es}{33}{chapter.3}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {section}{\numberline {3.1}Pr\IeC {\'e}sentation - existant}{31}{section.3.1}} -\@writefile{toc}{\contentsline {section}{\numberline {3.2}La parall\IeC {\`e}lisation du snake polygonal}{31}{section.3.2}} -\@writefile{toc}{\contentsline {chapter}{\numberline {4}Le filtrage des images sur GPU}{33}{chapter.4}} +\@writefile{toc}{\contentsline {section}{\numberline {3.1}Pr\IeC {\'e}sentation - existant}{33}{section.3.1}} +\@writefile{toc}{\contentsline {section}{\numberline {3.2}La parall\IeC {\`e}lisation du snake polygonal}{33}{section.3.2}} +\@writefile{toc}{\contentsline {chapter}{\numberline {4}Le filtrage des images sur GPU}{35}{chapter.4}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {section}{\numberline {4.1}Algorithme de r\IeC {\'e}duction de bruit par recherche des lignes de niveaux}{33}{section.4.1}} -\@writefile{toc}{\contentsline {section}{\numberline {4.2}Filtre m\IeC {\'e}dian}{33}{section.4.2}} -\@writefile{toc}{\contentsline {section}{\numberline {4.3}Filtres de convolution}{33}{section.4.3}} +\@writefile{toc}{\contentsline {section}{\numberline {4.1}Algorithme de r\IeC {\'e}duction de bruit par recherche des lignes de niveaux}{35}{section.4.1}} +\@writefile{toc}{\contentsline {section}{\numberline {4.2}Filtre m\IeC {\'e}dian}{35}{section.4.2}} +\@writefile{toc}{\contentsline {section}{\numberline {4.3}Filtres de convolution}{35}{section.4.3}} \bibstyle{plain} \bibdata{biblio} -\@writefile{toc}{\contentsline {chapter}{\numberline {5}Conclusion g\IeC {\'e}n\IeC {\'e}rale}{35}{chapter.5}} +\@writefile{toc}{\contentsline {chapter}{\numberline {5}Conclusion g\IeC {\'e}n\IeC {\'e}rale}{37}{chapter.5}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} \bibcite{kodakccd}{1} -\bibcite{aldinucci2012parallel}{2} -\bibcite{1467423}{3} -\bibcite{BuadesCM06}{4} -\bibcite{Caselles99topographicmaps}{5} -\bibcite{chen09}{6} -\bibcite{1093941}{7} -\bibcite{cutrona1990synthetic}{8} -\bibcite{Dabov06imagedenoising}{9} -\bibcite{Dabov09bm3dimage}{10} -\bibcite{Daubechies:1992:TLW:130655}{11} -\bibcite{elad2006image}{12} -\bibcite{nlmeansgpubelge}{13} -\bibcite{healey1994radiometric}{14} -\bibcite{5402362}{15} -\bibcite{cmla2009Kes}{16} -\bibcite{Mallat:2008:WTS:1525499}{17} -\bibcite{mancuso2001introduction}{18} -\bibcite{coil}{19} -\bibcite{PALHANOXAVIERDEFONTES}{20} -\bibcite{4287006}{21} -\bibcite{1521458}{22} -\bibcite{4587843}{23} -\bibcite{6288187}{24} -\bibcite{convolutionsoup}{25} -\bibcite{strang1999discrete}{26} -\bibcite{theuwissen2001ccd}{27} -\bibcite{710815}{28} -\bibcite{tukey77}{29} -\bibcite{Wang04imagequality}{30} -\bibcite{5206542}{31} -\bibcite{zheng2011performance}{32} +\bibcite{adalsteinsson1994fast}{2} +\bibcite{agarwal2002exact}{3} +\bibcite{aldinucci2012parallel}{4} +\bibcite{arbelaez2011contour}{5} +\bibcite{arora1998approximation}{6} +\bibcite{bertaux2004speckle}{7} +\bibcite{1467423}{8} +\bibcite{BuadesCM06}{9} +\bibcite{Caselles99topographicmaps}{10} +\bibcite{chen09}{11} +\bibcite{1093941}{12} +\bibcite{cheng1995mean}{13} +\bibcite{ChesnaudRB99}{14} +\bibcite{cohen1993surface}{15} +\bibcite{comaniciu1999mean}{16} +\bibcite{comaniciu2002mean}{17} +\bibcite{cutrona1990synthetic}{18} +\bibcite{Dabov06imagedenoising}{19} +\bibcite{Dabov09bm3dimage}{20} +\bibcite{Daubechies:1992:TLW:130655}{21} +\bibcite{elad2006image}{22} +\bibcite{felzenszwalb2004efficient}{23} +\bibcite{foley1994introduction}{24} +\bibcite{fukunaga1975estimation}{25} +\bibcite{GallandBR03}{26} +\bibcite{GermainR01}{27} +\bibcite{nlmeansgpubelge}{28} +\bibcite{healey1994radiometric}{29} +\bibcite{humphrey1924psychology}{30} +\bibcite{5402362}{31} +\bibcite{KassWT88}{32} +\bibcite{keselman1998extraction}{33} +\bibcite{cmla2009Kes}{34} +\bibcite{macqueen1967some}{35} +\bibcite{Mallat:2008:WTS:1525499}{36} +\bibcite{mancuso2001introduction}{37} +\bibcite{coil}{38} +\bibcite{osher1988fronts}{39} +\bibcite{4310076}{40} +\bibcite{PALHANOXAVIERDEFONTES}{41} +\bibcite{pelleg2000x}{42} +\bibcite{4287006}{43} +\bibcite{1521458}{44} +\bibcite{4587843}{45} +\bibcite{ronfard1994region}{46} +\bibcite{6288187}{47} +\bibcite{sethian1996fast}{48} +\bibcite{shi2000normalized}{49} +\bibcite{convolutionsoup}{50} +\bibcite{strang1999discrete}{51} +\bibcite{theuwissen2001ccd}{52} +\bibcite{710815}{53} +\bibcite{tukey77}{54} +\bibcite{wang2001image}{55} +\bibcite{wang2003image}{56} +\bibcite{Wang04imagequality}{57} +\bibcite{wu1993optimal}{58} +\bibcite{5206542}{59} +\bibcite{Zahn:1971:GMD:1309266.1309359}{60} +\bibcite{zheng2011performance}{61} +\citation{zheng2011performance} diff --git a/THESE/these.bbl b/THESE/these.bbl index 65eb750..e44d4b4 100644 --- a/THESE/these.bbl +++ b/THESE/these.bbl @@ -4,12 +4,40 @@ Ccd image sensor noise sources. \newblock Technical report, Eastman Kodak company, Rochester, August 2001. +\bibitem{adalsteinsson1994fast} +David Adalsteinsson and James Sethian. +\newblock {\em A fast level set method for propagating interfaces}. +\newblock PhD thesis, University of California, 1994. + +\bibitem{agarwal2002exact} +Pankaj~K Agarwal and Cecilia~Magdalena Procopiuc. +\newblock Exact and approximation algorithms for clustering. +\newblock {\em Algorithmica}, 33(2):201--226, 2002. + \bibitem{aldinucci2012parallel} M.~Aldinucci, C.S.M. Drocco, M.~Torquati, and S.~Palazzo. \newblock A parallel edge preserving algorithm for salt and pepper image denoising. \newblock 2012. +\bibitem{arbelaez2011contour} +Pablo Arbelaez, Michael Maire, Charless Fowlkes, and Jitendra Malik. +\newblock Contour detection and hierarchical image segmentation. +\newblock {\em Pattern Analysis and Machine Intelligence, IEEE Transactions + on}, 33(5):898--916, 2011. + +\bibitem{arora1998approximation} +Sanjeev Arora, Prabhakar Raghavan, and Satish Rao. +\newblock Approximation schemes for euclidean k-medians and related problems. +\newblock In {\em Proceedings of the thirtieth annual ACM symposium on Theory + of computing}, pages 106--113. ACM, 1998. + +\bibitem{bertaux2004speckle} +Nicolas Bertaux, Yann Frauel, Philippe R{\'e}fr{\'e}gier, and Bahram Javidi. +\newblock Speckle removal using a maximum-likelihood technique with isoline + gray-level regularization. +\newblock {\em JOSA A}, 21(12):2283--2291, 2004. + \bibitem{1467423} A.~Buades, B.~Coll, and J.~M Morel. \newblock A non-local algorithm for image denoising. @@ -37,6 +65,36 @@ Wen-Hsiung Chen, C.~Smith, and S.~Fralick. \newblock A fast computational algorithm for the discrete cosine transform. \newblock {\em Communications, IEEE Transactions on}, 25(9):1004--1009, 1977. +\bibitem{cheng1995mean} +Yizong Cheng. +\newblock Mean shift, mode seeking, and clustering. +\newblock {\em Pattern Analysis and Machine Intelligence, IEEE Transactions + on}, 17(8):790--799, 1995. + +\bibitem{ChesnaudRB99} +Christophe Chesnaud, Philippe R{\'e}fr{\'e}gier, and Vlady Boulet. +\newblock Statistical region snake-based segmentation adapted to different + physical noise models. +\newblock {\em IEEE Trans. Pattern Anal. Mach. Intell.}, 21(11):1145--1157, + 1999. + +\bibitem{cohen1993surface} +Laurent~D Cohen, Eric Bardinet, Nicholas Ayache, et~al. +\newblock Surface reconstruction using active contour models. +\newblock 1993. + +\bibitem{comaniciu1999mean} +Dorin Comaniciu and Peter Meer. +\newblock Mean shift analysis and applications. +\newblock In {\em Computer Vision, 1999. The Proceedings of the Seventh IEEE + International Conference on}, volume~2, pages 1197--1203. IEEE, 1999. + +\bibitem{comaniciu2002mean} +Dorin Comaniciu and Peter Meer. +\newblock Mean shift: A robust approach toward feature space analysis. +\newblock {\em Pattern Analysis and Machine Intelligence, IEEE Transactions + on}, 24(5):603--619, 2002. + \bibitem{cutrona1990synthetic} LJ~Cutrona. \newblock Synthetic aperture radar. @@ -69,6 +127,34 @@ Michael Elad and Michal Aharon. \newblock {\em Image Processing, IEEE Transactions on}, 15(12):3736--3745, 2006. +\bibitem{felzenszwalb2004efficient} +Pedro~F Felzenszwalb and Daniel~P Huttenlocher. +\newblock Efficient graph-based image segmentation. +\newblock {\em International Journal of Computer Vision}, 59(2):167--181, 2004. + +\bibitem{foley1994introduction} +James~D Foley, Andries Van~Dam, Steven~K Feiner, John~F Hughes, and Richard~L + Phillips. +\newblock {\em Introduction to computer graphics}, volume~55. +\newblock Addison-Wesley Reading, 1994. + +\bibitem{fukunaga1975estimation} +Keinosuke Fukunaga and Larry Hostetler. +\newblock The estimation of the gradient of a density function, with + applications in pattern recognition. +\newblock {\em Information Theory, IEEE Transactions on}, 21(1):32--40, 1975. + +\bibitem{GallandBR03} +Fr{\'e}d{\'e}ric Galland, Nicolas Bertaux, and Philippe R{\'e}fr{\'e}gier. +\newblock Minimum description length synthetic aperture radar image + segmentation. +\newblock {\em IEEE Transactions on Image Processing}, 12(9):995--1006, 2003. + +\bibitem{GermainR01} +Olivier Germain and Philippe R{\'e}fr{\'e}gier. +\newblock Statistical active grid for segmentation refinement. +\newblock {\em Pattern Recognition Letters}, 22(10):1125--1132, 2001. + \bibitem{nlmeansgpubelge} Bart Goossens, Hiêp Luong, Jan Aelterman, Aleksandra Pižurica, and Wilfried Philips. @@ -85,17 +171,42 @@ Glenn~E Healey and Raghava Kondepudy. \newblock {\em Pattern Analysis and Machine Intelligence, IEEE Transactions on}, 16(3):267--276, 1994. +\bibitem{humphrey1924psychology} +GEORGE Humphrey. +\newblock The psychology of the gestalt. +\newblock {\em Journal of Educational Psychology}, 15(7):401, 1924. + \bibitem{5402362} M.~Kachelriess. \newblock Branchless vectorized median filtering. \newblock In {\em Nuclear Science Symposium Conference Record (NSS/MIC), 2009 IEEE}, pages 4099 --4105, 24 2009-nov. 1 2009. +\bibitem{KassWT88} +Michael Kass, Andrew~P. Witkin, and Demetri Terzopoulos. +\newblock Snakes: Active contour models. +\newblock {\em International Journal of Computer Vision}, 1(4):321--331, 1988. + +\bibitem{keselman1998extraction} +Yakov Keselman and EVANGELIA Micheli-Tzanakou. +\newblock Extraction and characterization of regions of interest in biomedical + images. +\newblock In {\em Information Technology Applications in Biomedicine, 1998. + ITAB 98. Proceedings. 1998 IEEE International Conference on}, pages 87--90. + IEEE, 1998. + \bibitem{cmla2009Kes} P.~Kestener, Y.~Moudden, and A.~Pedron. \newblock Calcul scientifique sur gpu et application en traitement d'images. \newblock Seminaire HPC-GPU, CMLA, ENS Cachan, March 2009. +\bibitem{macqueen1967some} +James MacQueen et~al. +\newblock Some methods for classification and analysis of multivariate + observations. +\newblock In {\em Proceedings of the fifth Berkeley symposium on mathematical + statistics and probability}, volume~1, page~14. California, USA, 1967. + \bibitem{Mallat:2008:WTS:1525499} Stphane Mallat. \newblock {\em A Wavelet Tour of Signal Processing, Third Edition: The Sparse @@ -113,12 +224,30 @@ S.A. Nene, S.K. Nayar, and Murase H. \newblock Technical Report CUCS-006-96, Computer Vision Laboratory, Columbia University, February 1996. +\bibitem{osher1988fronts} +Stanley Osher and James~A Sethian. +\newblock Fronts propagating with curvature-dependent speed: algorithms based + on hamilton-jacobi formulations. +\newblock {\em Journal of computational physics}, 79(1):12--49, 1988. + +\bibitem{4310076} +N.~Otsu. +\newblock A threshold selection method from gray-level histograms. +\newblock {\em Systems, Man and Cybernetics, IEEE Transactions on}, + 9(1):62--66, 1979. + \bibitem{PALHANOXAVIERDEFONTES} Fernanda Palhano Xavier De~Fontes, Guillermo Andrade~Barroso, Pierrick Coup{\'e}, and Pierre Hellier. \newblock {Real time ultrasound image denoising}. \newblock {\em Journal of Real-Time Image Processing}, May 2010. +\bibitem{pelleg2000x} +Dan Pelleg, Andrew~W Moore, et~al. +\newblock X-means: Extending k-means with efficient estimation of the number of + clusters. +\newblock In {\em ICML}, pages 727--734, 2000. + \bibitem{4287006} S.~Perreault and P.~Hebert. \newblock Median filtering in constant time. @@ -137,12 +266,29 @@ F.~Porikli. \newblock In {\em Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on}, pages 1--8, 2008. +\bibitem{ronfard1994region} +R{\'e}mi Ronfard. +\newblock Region-based strategies for active contour models. +\newblock {\em International Journal of Computer Vision}, 13(2):229--251, 1994. + \bibitem{6288187} R.M. Sanchez and P.A. Rodriguez. \newblock Bidimensional median filter for parallel computing architectures. \newblock In {\em Acoustics, Speech and Signal Processing (ICASSP), 2012 IEEE International Conference on}, pages 1549 --1552, march 2012. +\bibitem{sethian1996fast} +James~A Sethian. +\newblock A fast marching level set method for monotonically advancing fronts. +\newblock {\em Proceedings of the National Academy of Sciences}, + 93(4):1591--1595, 1996. + +\bibitem{shi2000normalized} +Jianbo Shi and Jitendra Malik. +\newblock Normalized cuts and image segmentation. +\newblock {\em Pattern Analysis and Machine Intelligence, IEEE Transactions + on}, 22(8):888--905, 2000. + \bibitem{convolutionsoup} J.~Stam. \newblock Convolution soup. @@ -171,6 +317,18 @@ John~Wilder Tukey. \newblock {\em Exploratory Data Analysis}. \newblock Addison-Wesley, 1977. +\bibitem{wang2001image} +Song Wang and Jeffrey~Mark Siskind. +\newblock Image segmentation with minimum mean cut. +\newblock In {\em Computer Vision, 2001. ICCV 2001. Proceedings. Eighth IEEE + International Conference on}, volume~1, pages 517--524. IEEE, 2001. + +\bibitem{wang2003image} +Song Wang and Jeffrey~Mark Siskind. +\newblock Image segmentation with ratio cut. +\newblock {\em Pattern Analysis and Machine Intelligence, IEEE Transactions + on}, 25(6):675--690, 2003. + \bibitem{Wang04imagequality} Zhou Wang, Alan~Conrad Bovik, Hamid~Rahim Sheikh, Student Member, Eero~P. Simoncelli, and Senior Member. @@ -178,12 +336,25 @@ Zhou Wang, Alan~Conrad Bovik, Hamid~Rahim Sheikh, Student Member, Eero~P. similarity. \newblock {\em IEEE Transactions on Image Processing}, 13:600--612, 2004. +\bibitem{wu1993optimal} +Zhenyu Wu and Richard Leahy. +\newblock An optimal graph theoretic approach to data clustering: Theory and + its application to image segmentation. +\newblock {\em Pattern Analysis and Machine Intelligence, IEEE Transactions + on}, 15(11):1101--1113, 1993. + \bibitem{5206542} Qingxiong Yang, Kar-Han Tan, and N.~Ahuja. \newblock Real-time o(1) bilateral filtering. \newblock In {\em Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on}, pages 557--564, 2009. +\bibitem{Zahn:1971:GMD:1309266.1309359} +C.~T. Zahn. +\newblock Graph-theoretical methods for detecting and describing gestalt + clusters. +\newblock {\em IEEE Trans. Comput.}, 20(1):68--86, January 1971. + \bibitem{zheng2011performance} Z.~Zheng, W.~Xu, and K.~Mueller. \newblock Performance tuning for cuda-accelerated neighborhood denoising diff --git a/THESE/these.blg b/THESE/these.blg index de3bd2e..ef89975 100644 --- a/THESE/these.blg +++ b/THESE/these.blg @@ -2,73 +2,50 @@ This is BibTeX, Version 0.99c (TeX Live 2009/Debian) The top-level auxiliary file: these.aux The style file: plain.bst Database file #1: biblio.bib -Warning--I didn't find a database entry for "biblio-web" -Warning--I didn't find a database entry for "otsu79" -Warning--I didn't find a database entry for "slac-pub-0672" -Warning--I didn't find a database entry for "wulealy_1993" -Warning--I didn't find a database entry for "cf-notes-x5" -Warning--I didn't find a database entry for "sm-ncuts-pami2000" -Warning--I didn't find a database entry for "kmeans-1965" -Warning--I didn't find a database entry for "k-centers" -Warning--I didn't find a database entry for "k-medians" -Warning--I didn't find a database entry for "x-means" -Warning--I didn't find a database entry for "Lestimation-html" -Warning--I didn't find a database entry for "meanshift_1995" -Warning--I didn't find a database entry for "Computer-Graphics-by-Foley-van-Dam-Feiner-and-Hughes-published-by-Addison-Wesley-1990" -Warning--I didn't find a database entry for "mean-shift-1999" -Warning--I didn't find a database entry for "2002" -Warning--I didn't find a database entry for "yket1999" -Warning--I didn't find a database entry for "snake-kass-1988" -Warning--I didn't find a database entry for "level-sets-osher-sethian-1988" -Warning--I didn't find a database entry for "narrow-band-level-set" -Warning--I didn't find a database entry for "fast_marching_sethian" -Warning--I didn't find a database entry for "cohenSMIE93" -Warning--I didn't find a database entry for "ronfard" -Warning--I didn't find a database entry for "snake-bertaux" -Warning--I didn't find a database entry for "amfm-2010" -Warning--I didn't find a database entry for "watershed" Warning--to sort, need author or key in kodakccd Warning--empty author in kodakccd Warning--empty journal in aldinucci2012parallel -You've used 32 entries, +Warning--empty journal in cohen1993surface +Warning--can't use both volume and number fields in macqueen1967some +You've used 61 entries, 2118 wiz_defined-function locations, - 716 strings with 9937 characters, -and the built_in function-call counts, 11420 in all, are: -= -- 1111 -> -- 487 -< -- 14 -+ -- 199 -- -- 159 -* -- 746 -:= -- 1801 -add.period$ -- 97 -call.type$ -- 32 -change.case$ -- 172 + 857 strings with 14108 characters, +and the built_in function-call counts, 21700 in all, are: += -- 2175 +> -- 898 +< -- 24 ++ -- 366 +- -- 291 +* -- 1496 +:= -- 3454 +add.period$ -- 189 +call.type$ -- 61 +change.case$ -- 320 chr.to.int$ -- 0 -cite$ -- 35 -duplicate$ -- 486 -empty$ -- 943 -format.name$ -- 159 -if$ -- 2483 +cite$ -- 66 +duplicate$ -- 871 +empty$ -- 1771 +format.name$ -- 291 +if$ -- 4652 int.to.chr$ -- 0 -int.to.str$ -- 32 -missing$ -- 32 -newline$ -- 162 -num.names$ -- 64 -pop$ -- 210 +int.to.str$ -- 61 +missing$ -- 61 +newline$ -- 307 +num.names$ -- 122 +pop$ -- 339 preamble$ -- 1 -purify$ -- 141 +purify$ -- 262 quote$ -- 0 -skip$ -- 370 +skip$ -- 653 stack$ -- 0 -substring$ -- 714 -swap$ -- 148 -text.length$ -- 14 +substring$ -- 1518 +swap$ -- 237 +text.length$ -- 24 text.prefix$ -- 0 top$ -- 0 -type$ -- 122 -warning$ -- 3 -while$ -- 102 -width$ -- 34 -write$ -- 347 -(There were 28 warnings) +type$ -- 236 +warning$ -- 5 +while$ -- 214 +width$ -- 63 +write$ -- 672 +(There were 5 warnings) diff --git a/THESE/these.lof b/THESE/these.lof index 718386f..650b1f5 100644 --- a/THESE/these.lof +++ b/THESE/these.lof @@ -33,33 +33,34 @@ \contentsline {subfigure}{\numberline {(c)}{\ignorespaces {$f=5$ et $t=2$, PSNR=29.0~dB MSSIM=0.39}}}{19}{figure.2.6} \contentsline {subfigure}{\numberline {(d)}{\ignorespaces {$f=5$ et $t=5$, PSNR=29.0~dB MSSIM=0.40}}}{19}{figure.2.6} \contentsline {figure}{\numberline {2.7}{\ignorespaces Filtrage par BM3D, PSNR=29.3~dB MSSIM=0.41}}{19}{figure.2.7} -\contentsline {figure}{\numberline {2.8}{\ignorespaces Segmentation d'une image en niveaux de gris de 128 $\times $ 128 pixels par analyse simple d'histogramme. Colonne de gauche : image d'entr\IeC {\'e}e. Colonne centrale : histogramme des niveaux de gris. Colonne de droite : r\IeC {\'e}sultat de la segmentation.}}{23}{figure.2.8} -\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {Image initiale comportant deux zones : le fond et le cochon (la cible)}}}{23}{figure.2.8} -\contentsline {subfigure}{\numberline {(b)}{\ignorespaces {Histogramme des niveaux de gris}}}{23}{figure.2.8} -\contentsline {subfigure}{\numberline {(c)}{\ignorespaces {Image binaire repr\IeC {\'e}sentant la segmentation. Seuil estim\IeC {\'e} \IeC {\`a} 101 apr\IeC {\`e}s 4 it\IeC {\'e}rations.}}}{23}{figure.2.8} -\contentsline {subfigure}{\numberline {(d)}{\ignorespaces {Image initiale bruit\IeC {\'e}e}}}{23}{figure.2.8} -\contentsline {subfigure}{\numberline {(e)}{\ignorespaces {Histogramme des niveaux de gris}}}{23}{figure.2.8} -\contentsline {subfigure}{\numberline {(f)}{\ignorespaces {Image binaire repr\IeC {\'e}sentant la segmentation. Seuil estim\IeC {\'e} \IeC {\`a} 99 apr\IeC {\`e}s 5 it\IeC {\'e}rations.}}}{23}{figure.2.8} -\contentsline {figure}{\numberline {2.9}{\ignorespaces 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 \IeC {\`a} 5.}}{25}{figure.2.9} -\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {$s = 2$}}}{25}{figure.2.9} -\contentsline {subfigure}{\numberline {(b)}{\ignorespaces {$s = 3$}}}{25}{figure.2.9} -\contentsline {subfigure}{\numberline {(c)}{\ignorespaces {$s = 4$}}}{25}{figure.2.9} -\contentsline {subfigure}{\numberline {(d)}{\ignorespaces {$s = 5$}}}{25}{figure.2.9} -\contentsline {figure}{\numberline {2.10}{\ignorespaces 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 \IeC {\`a} 5. Chaque couleur est associ\IeC {\'e}e \IeC {\`a} un segment. Les couleurs sont choisies pour une meilleure visualisation des diff\IeC {\'e}rents segments.}}{26}{figure.2.10} +\contentsline {figure}{\numberline {2.8}{\ignorespaces Illustration pr\IeC {\'e}-chargement en m\IeC {\'e}moire partag\IeC {\'e}e mise en \oe uvre dans \cite {zheng2011performance} pour l'impl\IeC {\'e}mentation, entre autres, du filtre bilat\IeC {\'e}ral. a) en vert le bloc de threads associ\IeC {\'e} aux pixels centraux. b-e) les blocs de pixels successivement pr\IeC {\'e}-charg\IeC {\'e}s en m\IeC {\'e}moire partag\IeC {\'e}e. f) la configuration finale de la ROI en m\IeC {\'e}moire partag\IeC {\'e}e.}}{22}{figure.2.8} +\contentsline {figure}{\numberline {2.9}{\ignorespaces Segmentation d'une image en niveaux de gris de 128 $\times $ 128 pixels par analyse simple d'histogramme. Colonne de gauche : image d'entr\IeC {\'e}e. Colonne centrale : histogramme des niveaux de gris. Colonne de droite : r\IeC {\'e}sultat de la segmentation.}}{24}{figure.2.9} +\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {Image initiale comportant deux zones : le fond et le cochon (la cible)}}}{24}{figure.2.9} +\contentsline {subfigure}{\numberline {(b)}{\ignorespaces {Histogramme des niveaux de gris}}}{24}{figure.2.9} +\contentsline {subfigure}{\numberline {(c)}{\ignorespaces {Image binaire repr\IeC {\'e}sentant la segmentation. Seuil estim\IeC {\'e} \IeC {\`a} 101 apr\IeC {\`e}s 4 it\IeC {\'e}rations.}}}{24}{figure.2.9} +\contentsline {subfigure}{\numberline {(d)}{\ignorespaces {Image initiale bruit\IeC {\'e}e}}}{24}{figure.2.9} +\contentsline {subfigure}{\numberline {(e)}{\ignorespaces {Histogramme des niveaux de gris}}}{24}{figure.2.9} +\contentsline {subfigure}{\numberline {(f)}{\ignorespaces {Image binaire repr\IeC {\'e}sentant la segmentation. Seuil estim\IeC {\'e} \IeC {\`a} 99 apr\IeC {\`e}s 5 it\IeC {\'e}rations.}}}{24}{figure.2.9} +\contentsline {figure}{\numberline {2.10}{\ignorespaces 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 \IeC {\`a} 5.}}{26}{figure.2.10} \contentsline {subfigure}{\numberline {(a)}{\ignorespaces {$s = 2$}}}{26}{figure.2.10} \contentsline {subfigure}{\numberline {(b)}{\ignorespaces {$s = 3$}}}{26}{figure.2.10} \contentsline {subfigure}{\numberline {(c)}{\ignorespaces {$s = 4$}}}{26}{figure.2.10} \contentsline {subfigure}{\numberline {(d)}{\ignorespaces {$s = 5$}}}{26}{figure.2.10} -\contentsline {figure}{\numberline {2.11}{\ignorespaces 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 \IeC {\`a} 5. Le volume minimal admis pour un segment est fix\IeC {\'e} \IeC {\`a} 100 pixels. Chaque couleur est associ\IeC {\'e}e \IeC {\`a} un segment. Les couleurs sont choisies pour une meilleure visualisation des diff\IeC {\'e}rents segments.}}{27}{figure.2.11} -\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {$r=100 \Rightarrow s = 2$}}}{27}{figure.2.11} -\contentsline {subfigure}{\numberline {(b)}{\ignorespaces {$r=50 \Rightarrow s = 3$}}}{27}{figure.2.11} -\contentsline {subfigure}{\numberline {(c)}{\ignorespaces {$r=35 \Rightarrow s = 4$}}}{27}{figure.2.11} -\contentsline {subfigure}{\numberline {(d)}{\ignorespaces {$r=25 \Rightarrow s = 5$}}}{27}{figure.2.11} -\contentsline {figure}{\numberline {2.12}{\ignorespaces 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\IeC {\`e}tres d'\IeC {\'e}lasticti\IeC {\'e}, de raideur et d'attraction ont \IeC {\'e}t\IeC {\'e} fix\IeC {\'e}s respectivement aux valeurs 5, 0.1 et 5. }}{28}{figure.2.12} -\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {Les \IeC {\'e}tats initial et suivant chacune des trois premi\IeC {\`e}res it\IeC {\'e}rations}}}{28}{figure.2.12} -\contentsline {subfigure}{\numberline {(b)}{\ignorespaces {L'\IeC {\'e}tat du contour apr\IeC {\`e}s la septi\IeC {\`e}me it\IeC {\'e}ration}}}{28}{figure.2.12} -\contentsline {subfigure}{\numberline {(c)}{\ignorespaces {L'\IeC {\'e}tat du contour apr\IeC {\`e}s la dixi\IeC {\`e}me it\IeC {\'e}ration}}}{28}{figure.2.12} -\contentsline {subfigure}{\numberline {(d)}{\ignorespaces {L'\IeC {\'e}tat du contour apr\IeC {\`e}s la centi\IeC {\`e}me it\IeC {\'e}ration. C'est le contour final.}}}{28}{figure.2.12} +\contentsline {figure}{\numberline {2.11}{\ignorespaces 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 \IeC {\`a} 5. Chaque couleur est associ\IeC {\'e}e \IeC {\`a} un segment. Les couleurs sont choisies pour une meilleure visualisation des diff\IeC {\'e}rents segments.}}{27}{figure.2.11} +\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {$s = 2$}}}{27}{figure.2.11} +\contentsline {subfigure}{\numberline {(b)}{\ignorespaces {$s = 3$}}}{27}{figure.2.11} +\contentsline {subfigure}{\numberline {(c)}{\ignorespaces {$s = 4$}}}{27}{figure.2.11} +\contentsline {subfigure}{\numberline {(d)}{\ignorespaces {$s = 5$}}}{27}{figure.2.11} +\contentsline {figure}{\numberline {2.12}{\ignorespaces 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 \IeC {\`a} 5. Le volume minimal admis pour un segment est fix\IeC {\'e} \IeC {\`a} 100 pixels. Chaque couleur est associ\IeC {\'e}e \IeC {\`a} un segment. Les couleurs sont choisies pour une meilleure visualisation des diff\IeC {\'e}rents segments.}}{28}{figure.2.12} +\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {$r=100 \Rightarrow s = 2$}}}{28}{figure.2.12} +\contentsline {subfigure}{\numberline {(b)}{\ignorespaces {$r=50 \Rightarrow s = 3$}}}{28}{figure.2.12} +\contentsline {subfigure}{\numberline {(c)}{\ignorespaces {$r=35 \Rightarrow s = 4$}}}{28}{figure.2.12} +\contentsline {subfigure}{\numberline {(d)}{\ignorespaces {$r=25 \Rightarrow s = 5$}}}{28}{figure.2.12} +\contentsline {figure}{\numberline {2.13}{\ignorespaces 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\IeC {\`e}tres d'\IeC {\'e}lasticti\IeC {\'e}, de raideur et d'attraction ont \IeC {\'e}t\IeC {\'e} fix\IeC {\'e}s respectivement aux valeurs 5, 0.1 et 5. }}{29}{figure.2.13} +\contentsline {subfigure}{\numberline {(a)}{\ignorespaces {Les \IeC {\'e}tats initial et suivant chacune des trois premi\IeC {\`e}res it\IeC {\'e}rations}}}{29}{figure.2.13} +\contentsline {subfigure}{\numberline {(b)}{\ignorespaces {L'\IeC {\'e}tat du contour apr\IeC {\`e}s la septi\IeC {\`e}me it\IeC {\'e}ration}}}{29}{figure.2.13} +\contentsline {subfigure}{\numberline {(c)}{\ignorespaces {L'\IeC {\'e}tat du contour apr\IeC {\`e}s la dixi\IeC {\`e}me it\IeC {\'e}ration}}}{29}{figure.2.13} +\contentsline {subfigure}{\numberline {(d)}{\ignorespaces {L'\IeC {\'e}tat du contour apr\IeC {\`e}s la centi\IeC {\`e}me it\IeC {\'e}ration. C'est le contour final.}}}{29}{figure.2.13} \addvspace {10\p@ } \addvspace {10\p@ } \addvspace {10\p@ } diff --git a/THESE/these.log b/THESE/these.log index b07fc7c..ef80291 100644 --- a/THESE/these.log +++ b/THESE/these.log @@ -1,4 +1,4 @@ -This is pdfTeX, Version 3.1415926-1.40.10 (TeX Live 2009/Debian) (format=pdflatex 2012.12.6) 6 SEP 2013 16:03 +This is pdfTeX, Version 3.1415926-1.40.10 (TeX Live 2009/Debian) (format=pdflatex 2012.12.6) 10 SEP 2013 15:06 entering extended mode %&-line parsing enabled. **these.tex @@ -982,7 +982,7 @@ LaTeX Info: Redefining \Ref on input line 74. pdfTeX warning: pdflatex (file /usr/share/texmf/tex/latex/upmethodology-extensi ons/phd_thesis/spimufcphdthesis/spimufcphdthesis-frontpage.pdf): PDF inclusion: found PDF version <1.5>, but at most version <1.4> allowed - + File: spimufcphdthesis-frontpage.pdf Graphic file (type pdf) [1 @@ -993,7 +993,7 @@ File: spimufcphdthesis-frontpage.pdf Graphic file (type pdf) e.pdf>] [2 ] - + File: spimufcphdthesis-p3-head.pdf Graphic file (type pdf) @@ -1010,7 +1010,7 @@ LaTeX Font Info: Font shape `OT1/phv/bx/n' in size <10.95> not available ] (./these.toc LaTeX Font Info: Font shape `OT1/phv/m/it' in size <10.95> not available -(Font) Font shape `OT1/phv/m/sl' tried instead on input line 20. +(Font) Font shape `OT1/phv/m/sl' tried instead on input line 26. Package Fancyhdr Warning: \headheight is too small (12.0pt): @@ -1048,12 +1048,12 @@ Chapitre 2. (./Chapters/chapter2/chapter2.tex [11 ] [12] [13] - File: /home/zulu/Documents/these_gilles/THESE/codes/ny256.png Graphic file (typ e png) - File: /home/zulu/Documents/these_gilles/THESE/codes/ny256_gauss25.png Graphic f ile (type png) @@ -1069,7 +1069,7 @@ Underfull \hbox (badness 1997) in paragraph at lines 79--79 [] - File: /home/zulu/Documents/these_gilles/THESE/codes/ny256_sap25.png Graphic fil e (type png) @@ -1088,7 +1088,7 @@ Underfull \hbox (badness 10000) in paragraph at lines 80--80 /zulu/Documents/these_gilles/THESE/codes/ny256_gauss25.png (PNG copy)> ] +=347, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/convo/ny256_gauss25_moy3.pn g Graphic file (type png) @@ -1100,7 +1100,7 @@ Underfull \hbox (badness 10000) in paragraph at lines 101--101 +=348, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/convo/ny256_gauss25_moy5.pn g Graphic file (type png) @@ -1112,7 +1112,7 @@ Underfull \hbox (badness 10000) in paragraph at lines 102--102 +49, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/convo/ny256_gauss25_g3.png Graphic file (type png) @@ -1123,52 +1123,52 @@ Underfull \hbox (badness 10000) in paragraph at lines 103--103 +353, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/median/ny256_sap25_med3.png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 114--114 +Underfull \hbox (badness 10000) in paragraph at lines 115--115 []\OT1/phv/m/n/9 (a) M[]edian 3$\OMS/txsy/m/n/9 ^^B$\OT1/phv/m/n/9 3 une [] -Underfull \hbox (badness 10000) in paragraph at lines 114--114 +Underfull \hbox (badness 10000) in paragraph at lines 115--115 \OT1/phv/m/n/9 passe, PSNR=26.4 dB [] +d=354, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/median/ny256_sap25_med3x2.p ng Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 115--115 +Underfull \hbox (badness 10000) in paragraph at lines 116--116 []\OT1/phv/m/n/9 (b) M[]edian 3$\OMS/txsy/m/n/9 ^^B$\OT1/phv/m/n/9 3 deux [] -Underfull \hbox (badness 10000) in paragraph at lines 115--115 +Underfull \hbox (badness 10000) in paragraph at lines 116--116 \OT1/phv/m/n/9 passes, PSNR=34.4 dB [] +355, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/median/ny256_sap25_med5.png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 116--116 +Underfull \hbox (badness 10000) in paragraph at lines 117--117 []\OT1/phv/m/n/9 (c) M[]edian 5$\OMS/txsy/m/n/9 ^^B$\OT1/phv/m/n/9 5 une [] -Underfull \hbox (badness 10000) in paragraph at lines 116--116 +Underfull \hbox (badness 10000) in paragraph at lines 117--117 \OT1/phv/m/n/9 passe, PSNR=35.1 dB [] @@ -1177,121 +1177,124 @@ Underfull \hbox (badness 10000) in paragraph at lines 116--116 _moy5.png (PNG copy)> ] + id=371, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/bilat/ny_gauss25_bilat_1_01 .png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 129--129 +Underfull \hbox (badness 10000) in paragraph at lines 132--132 []\OT1/phv/m/n/9 (a) $\OML/txmi/m/it/9 ^^[[] \OT1/txr/m/n/9 = 1\OML/txmi/m/it/9 :\OT1/txr/m/n/9 0$ \OT1/phv/m/n/9 et [] + id=372, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/bilat/ny_gauss25_bilat_1_05 .png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 130--130 +Underfull \hbox (badness 10000) in paragraph at lines 133--133 []\OT1/phv/m/n/9 (b) $\OML/txmi/m/it/9 ^^[[] \OT1/txr/m/n/9 = 1\OML/txmi/m/it/9 :\OT1/txr/m/n/9 0$ \OT1/phv/m/n/9 et [] +id=373, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/bilat/ny_gauss25_bilat_1_1. png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 131--131 +Underfull \hbox (badness 10000) in paragraph at lines 134--134 []\OT1/phv/m/n/9 (c) $\OML/txmi/m/it/9 ^^[[] \OT1/txr/m/n/9 = 1\OML/txmi/m/it/9 :\OT1/txr/m/n/9 0$ \OT1/phv/m/n/9 et [] + id=374, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/bilat/ny_gauss25_bilat_2_01 .png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 132--132 +Underfull \hbox (badness 10000) in paragraph at lines 135--135 []\OT1/phv/m/n/9 (d) $\OML/txmi/m/it/9 ^^[[] \OT1/txr/m/n/9 = 2\OML/txmi/m/it/9 :\OT1/txr/m/n/9 0$ \OT1/phv/m/n/9 et [] + id=375, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/bilat/ny_gauss25_bilat_2_05 .png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 133--133 +Underfull \hbox (badness 10000) in paragraph at lines 136--136 []\OT1/phv/m/n/9 (e) $\OML/txmi/m/it/9 ^^[[] \OT1/txr/m/n/9 = 2\OML/txmi/m/it/9 :\OT1/txr/m/n/9 0$ \OT1/phv/m/n/9 et [] +id=376, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/bilat/ny_gauss25_bilat_2_1. png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 134--134 +Underfull \hbox (badness 10000) in paragraph at lines 137--137 []\OT1/phv/m/n/9 (f) $\OML/txmi/m/it/9 ^^[[] \OT1/txr/m/n/9 = 2\OML/txmi/m/it/9 :\OT1/txr/m/n/9 0$ \OT1/phv/m/n/9 et [] + id=377, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/bilat/ny_gauss25_bilat_5_01 .png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 135--135 +Underfull \hbox (badness 10000) in paragraph at lines 138--138 []\OT1/phv/m/n/9 (g) $\OML/txmi/m/it/9 ^^[[] \OT1/txr/m/n/9 = 5\OML/txmi/m/it/9 :\OT1/txr/m/n/9 0$ \OT1/phv/m/n/9 et [] + id=378, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/bilat/ny_gauss25_bilat_5_05 .png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 136--136 +Underfull \hbox (badness 10000) in paragraph at lines 139--139 []\OT1/phv/m/n/9 (h) $\OML/txmi/m/it/9 ^^[[] \OT1/txr/m/n/9 = 5\OML/txmi/m/it/9 :\OT1/txr/m/n/9 0$ \OT1/phv/m/n/9 et [] +id=379, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/bilat/ny_gauss25_bilat_5_1. png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 137--137 +Underfull \hbox (badness 10000) in paragraph at lines 140--140 []\OT1/phv/m/n/9 (i) $\OML/txmi/m/it/9 ^^[[] \OT1/txr/m/n/9 = 5\OML/txmi/m/it/9 :\OT1/txr/m/n/9 0$ \OT1/phv/m/n/9 et [] + +LaTeX Warning: Reference `ch-lniv' on page 16 undefined on input line 147. + [16 ] +=416, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/wave/ny256_gauss25_dwt20.pn g Graphic file (type png) - + File: /home/zulu/Documents/these_gilles/THESE/codes/wave/ny256_gauss25_dwt.png Graphic file (type png) +=418, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/wave/ny256_gauss25_dwt70.pn g Graphic file (type png) +.png, id=424, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/nlmeans/ny256_gauss25_nlm_2 _2_25.png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 168--168 +Underfull \hbox (badness 10000) in paragraph at lines 173--173 \OT1/phv/m/n/9 PSNR=28.5 dB [] +.png, id=425, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/nlmeans/ny256_gauss25_nlm_2 _5_25.png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 169--169 +Underfull \hbox (badness 10000) in paragraph at lines 174--174 \OT1/phv/m/n/9 PSNR=28.6 dB [] +.png, id=426, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/nlmeans/ny256_gauss25_nlm_5 _2_25.png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 170--170 +Underfull \hbox (badness 10000) in paragraph at lines 175--175 \OT1/phv/m/n/9 PSNR=29.0 dB [] +.png, id=427, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/nlmeans/ny256_gauss25_nlm_5 _5_25.png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 171--171 +Underfull \hbox (badness 10000) in paragraph at lines 176--176 \OT1/phv/m/n/9 PSNR=29.0 dB [] +428, 256.96pt x 256.96pt> File: /home/zulu/Documents/these_gilles/THESE/codes/bm3D/ny256_gauss25_bm3D.png Graphic file (type png) @@ -1383,439 +1386,361 @@ File: /home/zulu/Documents/these_gilles/THESE/codes/bm3D/ny256_gauss25_bm3D.png [18 ] [19 ] - -LaTeX Warning: Reference `fig-compare-jacket-pcmf' on page 20 undefined on inpu -t line 191. - - -LaTeX Warning: Reference `fig-compare-arrayfire-pcmf' on page 20 undefined on i -nput line 192. - +auss25_dwt70.png (PNG copy)>] +Underfull \vbox (badness 10000) has occurred while \output is active [] -Underfull \hbox (badness 3471) in paragraph at lines 189--195 + [19 ] +Underfull \hbox (badness 3471) in paragraph at lines 200--201 []\OT1/phv/m/n/10.95 On connait peu de ver-sions GPU du filtre m[]edian, peut-[ ]etre en rai-son des [] -Underfull \vbox (badness 10000) has occurred while \output is active [] +LaTeX Warning: Reference `fig-compare-jacket-pcmf' on page 20 undefined on inpu +t line 205. - [20] -[21] -LaTeX Warning: Citation `biblio-web' on page 22 undefined on input line 222. +LaTeX Warning: Reference `fig-compare-arrayfire-pcmf' on page 20 undefined on i +nput line 207. +[20] + +File: /home/zulu/Documents/these_gilles/THESE/Chapters/chapter2/img/shmem_prefe +tch_zheng2011.png Graphic file (type png) -LaTeX Warning: Citation `otsu79' on page 22 undefined on input line 227. + [21] +Underfull \vbox (badness 2617) has occurred while \output is active [] -[22] -] [23] + File: /home/zulu/Documents/these_gilles/THESE/codes/cochon256.png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 234--234 +Underfull \hbox (badness 10000) in paragraph at lines 270--270 []\OT1/phv/m/n/9 (a) Image ini-tiale [] -Underfull \hbox (badness 10000) in paragraph at lines 234--234 +Underfull \hbox (badness 10000) in paragraph at lines 270--270 \OT1/phv/m/n/9 com-por-tant deux [] +png, id=512, 289.883pt x 242.506pt> File: /home/zulu/Documents/these_gilles/THESE/codes/seg_histogramme/histo-cocho n256.png Graphic file (type png) +to-101-255.png, id=513, 204.765pt x 204.765pt> File: /home/zulu/Documents/these_gilles/THESE/codes/seg_histogramme/cochon256-s eghisto-101-255.png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 236--236 +Underfull \hbox (badness 10000) in paragraph at lines 272--272 []\OT1/phv/m/n/9 (c) Image bi-naire [] -Underfull \hbox (badness 2189) in paragraph at lines 236--236 +Underfull \hbox (badness 2189) in paragraph at lines 272--272 \OT1/phv/m/n/9 repr[]esentant la seg- [] -Underfull \hbox (badness 10000) in paragraph at lines 236--236 +Underfull \hbox (badness 10000) in paragraph at lines 272--272 \OT1/phv/m/n/9 men-ta-tion. Seuil [] - File: /home/zulu/Documents/these_gilles/THESE/codes/cochon256-sig25.png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 237--237 +Underfull \hbox (badness 10000) in paragraph at lines 273--273 []\OT1/phv/m/n/9 (d) Image ini-tiale [] +sig25.png, id=515, 287.474pt x 240.097pt> File: /home/zulu/Documents/these_gilles/THESE/codes/seg_histogramme/histo-cocho n256-sig25.png Graphic file (type png) +seghisto-99-255.png, id=516, 204.765pt x 204.765pt> File: /home/zulu/Documents/these_gilles/THESE/codes/seg_histogramme/cochon256-s ig25-seghisto-99-255.png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 239--239 +Underfull \hbox (badness 10000) in paragraph at lines 275--275 []\OT1/phv/m/n/9 (f) Image bi-naire [] -Underfull \hbox (badness 2189) in paragraph at lines 239--239 +Underfull \hbox (badness 2189) in paragraph at lines 275--275 \OT1/phv/m/n/9 repr[]esentant la seg- [] -Underfull \hbox (badness 10000) in paragraph at lines 239--239 +Underfull \hbox (badness 10000) in paragraph at lines 275--275 \OT1/phv/m/n/9 men-ta-tion. Seuil [] Package hyperref Info: bookmark level for unknown algocf defaults to 0 on input - line 247. + line 283. LaTeX Font Info: Font shape `OT1/phv/bx/n' in size <8> not available -(Font) Font shape `OT1/phv/b/n' tried instead on input line 249. - -LaTeX Warning: Citation `slac-pub-0672' on page 23 undefined on input line 264. - - -[23 ] - -LaTeX Warning: Citation `wulealy_1993' on page 24 undefined on input line 281. - - -LaTeX Warning: Citation `cf-notes-x5' on page 24 undefined on input line 281. - - -LaTeX Warning: Citation `sm-ncuts-pami2000' on page 24 undefined on input line -283. - - +png (PNG copy)>] [25] + id=553, 317.988pt x 251.339pt> File: /home/zulu/Documents/these_gilles/THESE/codes/graphe/cochon128_ncuts_2seg .png Graphic file (type png) + id=554, 317.988pt x 251.339pt> File: /home/zulu/Documents/these_gilles/THESE/codes/graphe/cochon128_ncuts_3seg .png Graphic file (type png) + id=555, 317.988pt x 251.339pt> File: /home/zulu/Documents/these_gilles/THESE/codes/graphe/cochon128_ncuts_4seg .png Graphic file (type png) + id=556, 317.988pt x 251.339pt> File: /home/zulu/Documents/these_gilles/THESE/codes/graphe/cochon128_ncuts_5seg .png Graphic file (type png) [24] - -LaTeX Warning: Citation `kmeans-1965' on page 25 undefined on input line 302. - -[25 ] - -LaTeX Warning: Citation `k-centers' on page 26 undefined on input line 308. - - -LaTeX Warning: Citation `k-medians' on page 26 undefined on input line 308. - - -LaTeX Warning: Citation `x-means' on page 26 undefined on input line 309. - - +png> [26 ] +, id=576, 317.988pt x 251.339pt> File: /home/zulu/Documents/these_gilles/THESE/codes/kmeans/cochon128_kmeans_2se g.png Graphic file (type png) +, id=577, 317.988pt x 251.339pt> File: /home/zulu/Documents/these_gilles/THESE/codes/kmeans/cochon128_kmeans_3se g.png Graphic file (type png) +, id=578, 317.988pt x 251.339pt> File: /home/zulu/Documents/these_gilles/THESE/codes/kmeans/cochon128_kmeans_4se g.png Graphic file (type png) +, id=579, 317.988pt x 251.339pt> File: /home/zulu/Documents/these_gilles/THESE/codes/kmeans/cochon128_kmeans_5se g.png Graphic file (type png) - -LaTeX Warning: Citation `Lestimation-html' on page 26 undefined on input line 3 -21. - - -LaTeX Warning: Citation `meanshift_1995' on page 26 undefined on input line 323 -. - - -LaTeX Warning: Citation `Computer-Graphics-by-Foley-van-Dam-Feiner-and-Hughes-p -ublished-by-Addison-Wesley-1990' on page 26 undefined on input line 324. - - -LaTeX Warning: Citation `mean-shift-1999' on page 26 undefined on input line 32 -4. - - -LaTeX Warning: Citation `2002' on page 26 undefined on input line 324. - - -LaTeX Warning: Citation `yket1999' on page 26 undefined on input line 325. - - +00m100.png, id=587, 318.791pt x 251.339pt> File: /home/zulu/Documents/these_gilles/THESE/codes/meanshift/cochon128_meanshi ft_r100m100.png Graphic file (type png) +0m100.png, id=588, 318.791pt x 251.339pt> File: /home/zulu/Documents/these_gilles/THESE/codes/meanshift/cochon128_meanshi ft_r50m100.png Graphic file (type png) +5m100.png, id=589, 317.988pt x 251.339pt> File: /home/zulu/Documents/these_gilles/THESE/codes/meanshift/cochon128_meanshi ft_r35m100.png Graphic file (type png) +5m100.png, id=590, 317.988pt x 251.339pt> File: /home/zulu/Documents/these_gilles/THESE/codes/meanshift/cochon128_meanshi ft_r25m100.png Graphic file (type png) -Underfull \vbox (badness 2689) has occurred while \output is active [] - - [26 ] +t_r25m100.png> [27 ] LaTeX Font Info: Font shape `OT1/phv/m/it' in size <12> not available -(Font) Font shape `OT1/phv/m/sl' tried instead on input line 339. - [27 ] - -LaTeX Warning: Citation `snake-kass-1988' on page 28 undefined on input line 35 -7. - - +(Font) Font shape `OT1/phv/m/sl' tried instead on input line 378. + +[28 ] +png, id=621, 138.116pt x 138.116pt> File: /home/zulu/Documents/these_gilles/THESE/codes/snake/cochon128_tradi_snake _it3.png Graphic file (type png) -Underfull \hbox (badness 2662) in paragraph at lines 366--366 +Underfull \hbox (badness 2662) in paragraph at lines 405--405 []\OT1/phv/m/n/9 (a) Les []etats ini-tial [] -Underfull \hbox (badness 4378) in paragraph at lines 366--366 +Underfull \hbox (badness 4378) in paragraph at lines 405--405 \OT1/phv/m/n/9 et sui-vant cha-cune [] -Underfull \hbox (badness 2582) in paragraph at lines 366--366 +Underfull \hbox (badness 2582) in paragraph at lines 405--405 \OT1/phv/m/n/9 des trois premi[]eres [] +png, id=622, 138.116pt x 138.116pt> File: /home/zulu/Documents/these_gilles/THESE/codes/snake/cochon128_tradi_snake _it7.png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 367--367 +Underfull \hbox (badness 10000) in paragraph at lines 406--406 \OT1/phv/m/n/9 apr[]es la septi[]eme [] +.png, id=623, 138.116pt x 138.116pt> File: /home/zulu/Documents/these_gilles/THESE/codes/snake/cochon128_tradi_snake _it10.png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 368--368 +Underfull \hbox (badness 10000) in paragraph at lines 407--407 \OT1/phv/m/n/9 apr[]es la dixi[]eme [] +lt.png, id=624, 271.414pt x 271.414pt> File: /home/zulu/Documents/these_gilles/THESE/codes/snake/cochon128_tradi_snake _result.png Graphic file (type png) -Underfull \hbox (badness 10000) in paragraph at lines 369--369 +Underfull \hbox (badness 10000) in paragraph at lines 408--408 \OT1/phv/m/n/9 apr[]es la centi[]eme [] -Underfull \hbox (badness 10000) in paragraph at lines 369--369 +Underfull \hbox (badness 10000) in paragraph at lines 408--408 \OT1/phv/m/n/9 it[]eration. C'est le [] - -LaTeX Warning: Citation `level-sets-osher-sethian-1988' on page 28 undefined on - input line 381. - - -LaTeX Warning: Citation `narrow-band-level-set' on page 28 undefined on input l -ine 381. - - -LaTeX Warning: Citation `fast_marching_sethian' on page 28 undefined on input l -ine 381. - -[28 ] -LaTeX Warning: Citation `cohenSMIE93' on page 29 undefined on input line 382. - - -LaTeX Warning: Citation `ronfard' on page 29 undefined on input line 382. - - -LaTeX Warning: Citation `snake-bertaux' on page 29 undefined on input line 382. - - - -LaTeX Warning: Reference `sec-contrib-snake' on page 29 undefined on input line - 382. +LaTeX Warning: Reference `sec-contrib-snake' on page 30 undefined on input line + 421. -LaTeX Warning: Citation `amfm-2010' on page 29 undefined on input line 388. +LaTeX Warning: Reference `sec_ea_gpu' on page 30 undefined on input line 428. +) +Underfull \vbox (badness 10000) has occurred while \output is active [] -LaTeX Warning: Citation `watershed' on page 29 undefined on input line 388. - - -LaTeX Warning: Reference `sec_ea_gpu' on page 29 undefined on input line 389. - -) [29] [30 + [30] +[31] [32 ] Chapitre 3. -[31] [32 +[33] [34 ] Chapitre 4. -[33] [34 +[35] [36 ] Chapitre 5. -(./these.bbl [35] [36 +(./these.bbl [37] [38 -] [37]) [38] (./these.lof) +] [39] [40] [41]) [42] (./these.lof) \tf@lof=\write5 \openout5 = `these.lof'. - [39 -] [40 +Underfull \vbox (badness 1448) has occurred while \output is active [] -] (./these.lot) + [43 + +] +[44] (./these.lot) \tf@lot=\write6 \openout6 = `these.lot'. + [45 -[41] [42 +] [46 -] [43] +] [47] pdfTeX warning: pdflatex (file /usr/share/texmf/tex/latex/upmethodology-extensi ons/phd_thesis/spimufcphdthesis/spimufcphdthesis-backpage.pdf): PDF inclusion: found PDF version <1.6>, but at most version <1.4> allowed - + File: spimufcphdthesis-backpage.pdf Graphic file (type pdf) LaTeX Font Info: Font shape `OT1/phv/bx/n' in size <12> not available (Font) Font shape `OT1/phv/b/n' tried instead on input line 127. - [44 + [48 ] @@ -1826,13 +1751,13 @@ LaTeX Warning: There were undefined references. ) (\end occurred when \iftrue on line 127 was incomplete) Here is how much of TeX's memory you used: - 10278 strings out of 495028 - 157849 string characters out of 1181229 - 273713 words of memory out of 3000000 - 12924 multiletter control sequences out of 15000+50000 + 10336 strings out of 495028 + 159341 string characters out of 1181229 + 274232 words of memory out of 3000000 + 12940 multiletter control sequences out of 15000+50000 71443 words of font info for 129 fonts, out of 3000000 for 9000 28 hyphenation exceptions out of 8191 - 61i,15n,47p,1405b,505s stack positions out of 5000i,500n,10000p,200000b,50000s + 61i,15n,47p,1405b,523s stack positions out of 5000i,500n,10000p,200000b,50000s {/usr/share/texmf-texliv e/fonts/enc/dvips/base/8r.enc} -Output written on these.pdf (44 pages, 4650934 bytes). +Output written on these.pdf (48 pages, 4723781 bytes). PDF statistics: - 719 PDF objects out of 1000 (max. 8388607) - 180 named destinations out of 1000 (max. 500000) - 488 words of extra memory for PDF output out of 10000 (max. 10000000) + 842 PDF objects out of 1000 (max. 8388607) + 220 named destinations out of 1000 (max. 500000) + 541 words of extra memory for PDF output out of 10000 (max. 10000000) diff --git a/THESE/these.out b/THESE/these.out index a0cf24c..2b18633 100644 --- a/THESE/these.out +++ b/THESE/these.out @@ -8,10 +8,16 @@ \BOOKMARK [2][]{subsection.2.2.4}{2.2.4 Le bruit de Poisson}{section.2.2} \BOOKMARK [1][]{section.2.3}{2.3 Les techniques de r\351duction de bruit}{chapter.2} \BOOKMARK [2][]{subsection.2.3.1}{2.3.1 Les op\351rateurs de base}{section.2.3} -\BOOKMARK [3][]{subsubsection.2.3.1.1}{2.3.1.1 Les algorithmes de voisinage}{subsection.2.3.1} -\BOOKMARK [3][]{subsubsection.2.3.1.2}{2.3.1.2 Les algorithmes par dictionnaire}{subsection.2.3.1} -\BOOKMARK [2][]{subsection.2.3.2}{2.3.2 Les techniques avanc\351es}{section.2.3} +\BOOKMARK [3][]{subsubsection.2.3.1.1}{2.3.1.1 Le filtre de convolution}{subsection.2.3.1} +\BOOKMARK [3][]{subsubsection.2.3.1.2}{2.3.1.2 Le filtre m\351dian}{subsection.2.3.1} +\BOOKMARK [3][]{subsubsection.2.3.1.3}{2.3.1.3 Le filtre bilat\351ral}{subsection.2.3.1} +\BOOKMARK [3][]{subsubsection.2.3.1.4}{2.3.1.4 Les algorithmes de filtrage par dictionnaire}{subsection.2.3.1} +\BOOKMARK [2][]{subsection.2.3.2}{2.3.2 Les algorithmes de filtrage par patches}{section.2.3} \BOOKMARK [1][]{section.2.4}{2.4 Les impl\351mentations GPU des algorithmes de filtrage}{chapter.2} +\BOOKMARK [2][]{subsection.2.4.1}{2.4.1 Le filtrage par convolution}{section.2.4} +\BOOKMARK [2][]{subsection.2.4.2}{2.4.2 Le filtre m\351dian}{section.2.4} +\BOOKMARK [2][]{subsection.2.4.3}{2.4.3 Le filtre bilat\351ral}{section.2.4} +\BOOKMARK [2][]{subsection.2.4.4}{2.4.4 Les filtres par patches}{section.2.4} \BOOKMARK [1][]{section.2.5}{2.5 Les techniques de segmentation}{chapter.2} \BOOKMARK [2][]{subsection.2.5.1}{2.5.1 Analyse d'histogramme}{section.2.5} \BOOKMARK [2][]{subsection.2.5.2}{2.5.2 Analyse de graphe}{section.2.5} diff --git a/THESE/these.pdf b/THESE/these.pdf index b625ba5..310a1e2 100644 Binary files a/THESE/these.pdf and b/THESE/these.pdf differ diff --git a/THESE/these.tex b/THESE/these.tex index 150460f..a8641af 100644 --- a/THESE/these.tex +++ b/THESE/these.tex @@ -1,10 +1,10 @@ \documentclass[french]{spimufcphdthesis} \usepackage[utf8]{inputenc} - + \usepackage{graphicx} \usepackage{color, xcolor} \usepackage[ruled,lined,linesnumbered]{algorithm2e} - + %%-------------------- %% Set the title, subtitle, defense date, and %% the registration number of the PhD thesis. @@ -18,7 +18,7 @@ %%-------------------- %% Set the author of the PhD thesis \addauthor[gilles.perrot@univ-fcomte.fr]{Gilles}{Perrot} - + %%-------------------- %% Add a member of the jury %% \addjury{Firstname}{Lastname}{Role in the jury}{Position} @@ -67,12 +67,12 @@ %% Left footer %\lfoot{} %% Center footer -%\cfoot{} +%\cfoot{} %% Right footer %\rfoot{} \begin{document} - + \tableofcontents %-------------------- diff --git a/THESE/these.toc b/THESE/these.toc index df5542d..7e51dda 100644 --- a/THESE/these.toc +++ b/THESE/these.toc @@ -9,22 +9,28 @@ \contentsline {subsection}{\numberline {2.2.4}Le bruit de Poisson}{13}{subsection.2.2.4} \contentsline {section}{\numberline {2.3}Les techniques de r\IeC {\'e}duction de bruit}{13}{section.2.3} \contentsline {subsection}{\numberline {2.3.1}Les op\IeC {\'e}rateurs de base}{14}{subsection.2.3.1} -\contentsline {subsubsection}{\numberline {2.3.1.1}Les algorithmes de voisinage}{14}{subsubsection.2.3.1.1} -\contentsline {subsubsection}{\numberline {2.3.1.2}Les algorithmes par dictionnaire}{16}{subsubsection.2.3.1.2} -\contentsline {subsection}{\numberline {2.3.2}Les techniques avanc\IeC {\'e}es}{18}{subsection.2.3.2} +\contentsline {subsubsection}{\numberline {2.3.1.1}Le filtre de convolution}{14}{subsubsection.2.3.1.1} +\contentsline {subsubsection}{\numberline {2.3.1.2}Le filtre m\IeC {\'e}dian}{15}{subsubsection.2.3.1.2} +\contentsline {subsubsection}{\numberline {2.3.1.3}Le filtre bilat\IeC {\'e}ral}{16}{subsubsection.2.3.1.3} +\contentsline {subsubsection}{\numberline {2.3.1.4}Les algorithmes de filtrage par dictionnaire}{18}{subsubsection.2.3.1.4} +\contentsline {subsection}{\numberline {2.3.2}Les algorithmes de filtrage par patches}{18}{subsection.2.3.2} \contentsline {section}{\numberline {2.4}Les impl\IeC {\'e}mentations GPU des algorithmes de filtrage}{19}{section.2.4} -\contentsline {section}{\numberline {2.5}Les techniques de segmentation}{21}{section.2.5} -\contentsline {subsection}{\numberline {2.5.1}Analyse d'histogramme}{22}{subsection.2.5.1} -\contentsline {subsection}{\numberline {2.5.2}Analyse de graphe}{23}{subsection.2.5.2} -\contentsline {subsection}{\numberline {2.5.3}kernel-means, mean-shift et d\IeC {\'e}riv\IeC {\'e}s}{25}{subsection.2.5.3} -\contentsline {subsection}{\numberline {2.5.4}Les contours actifs, ou \textit {snakes}}{27}{subsection.2.5.4} -\contentsline {subsection}{\numberline {2.5.5}M\IeC {\'e}thodes hybrides}{29}{subsection.2.5.5} -\contentsline {section}{\numberline {2.6}L'\IeC {\'e}tat de l'art des impl\IeC {\'e}mentations GPU}{29}{section.2.6} -\contentsline {chapter}{\numberline {3}La segmentation orient\IeC {\'e}e r\IeC {\'e}gions dans les images bruit\IeC {\'e}es}{31}{chapter.3} -\contentsline {section}{\numberline {3.1}Pr\IeC {\'e}sentation - existant}{31}{section.3.1} -\contentsline {section}{\numberline {3.2}La parall\IeC {\`e}lisation du snake polygonal}{31}{section.3.2} -\contentsline {chapter}{\numberline {4}Le filtrage des images sur GPU}{33}{chapter.4} -\contentsline {section}{\numberline {4.1}Algorithme de r\IeC {\'e}duction de bruit par recherche des lignes de niveaux}{33}{section.4.1} -\contentsline {section}{\numberline {4.2}Filtre m\IeC {\'e}dian}{33}{section.4.2} -\contentsline {section}{\numberline {4.3}Filtres de convolution}{33}{section.4.3} -\contentsline {chapter}{\numberline {5}Conclusion g\IeC {\'e}n\IeC {\'e}rale}{35}{chapter.5} +\contentsline {subsection}{\numberline {2.4.1}Le filtrage par convolution}{20}{subsection.2.4.1} +\contentsline {subsection}{\numberline {2.4.2}Le filtre m\IeC {\'e}dian}{20}{subsection.2.4.2} +\contentsline {subsection}{\numberline {2.4.3}Le filtre bilat\IeC {\'e}ral}{21}{subsection.2.4.3} +\contentsline {subsection}{\numberline {2.4.4}Les filtres par patches}{22}{subsection.2.4.4} +\contentsline {section}{\numberline {2.5}Les techniques de segmentation}{23}{section.2.5} +\contentsline {subsection}{\numberline {2.5.1}Analyse d'histogramme}{23}{subsection.2.5.1} +\contentsline {subsection}{\numberline {2.5.2}Analyse de graphe}{24}{subsection.2.5.2} +\contentsline {subsection}{\numberline {2.5.3}kernel-means, mean-shift et d\IeC {\'e}riv\IeC {\'e}s}{26}{subsection.2.5.3} +\contentsline {subsection}{\numberline {2.5.4}Les contours actifs, ou \textit {snakes}}{28}{subsection.2.5.4} +\contentsline {subsection}{\numberline {2.5.5}M\IeC {\'e}thodes hybrides}{30}{subsection.2.5.5} +\contentsline {section}{\numberline {2.6}L'\IeC {\'e}tat de l'art des impl\IeC {\'e}mentations GPU}{31}{section.2.6} +\contentsline {chapter}{\numberline {3}La segmentation orient\IeC {\'e}e r\IeC {\'e}gions dans les images bruit\IeC {\'e}es}{33}{chapter.3} +\contentsline {section}{\numberline {3.1}Pr\IeC {\'e}sentation - existant}{33}{section.3.1} +\contentsline {section}{\numberline {3.2}La parall\IeC {\`e}lisation du snake polygonal}{33}{section.3.2} +\contentsline {chapter}{\numberline {4}Le filtrage des images sur GPU}{35}{chapter.4} +\contentsline {section}{\numberline {4.1}Algorithme de r\IeC {\'e}duction de bruit par recherche des lignes de niveaux}{35}{section.4.1} +\contentsline {section}{\numberline {4.2}Filtre m\IeC {\'e}dian}{35}{section.4.2} +\contentsline {section}{\numberline {4.3}Filtres de convolution}{35}{section.4.3} +\contentsline {chapter}{\numberline {5}Conclusion g\IeC {\'e}n\IeC {\'e}rale}{37}{chapter.5}