final

[these_gilles.git] / THESE / Chapters / chapter1 / chapter1.tex

diff --git a/THESE/Chapters/chapter1/chapter1.tex b/THESE/Chapters/chapter1/chapter1.tex
index 97ae15d0634748519e3951ececb254deee142904..b2289ac4daaa6f7c9f38275732c18e9fd3baa261 100644 (file)
--- a/THESE/Chapters/chapter1/chapter1.tex
+++ b/THESE/Chapters/chapter1/chapter1.tex
@@ -1,34 +1,35 @@
-Le traitement d'image n'est pas issu des technologies numériques. C'est pourtant l'idée qui peut venir à l'esprit lorsqu'on évoque cette discipline, tant elle a bénéficié du développement récent de ce que l'on nomme les ``nouvelles technologies''. C'est aussi dans ce cadre que s'inscrivent les travaux présentés ici et qui prétendent à réaliser des traitements rapides d'images numériques. 
+Le traitement d'image n'est pas issu des technologies numériques. C'est pourtant l'idée qui peut venir à l'esprit lorsqu'on évoque cette discipline, tant elle a bénéficié du développement récent de ce que l'on nomme les \og nouvelles technologies \fg{}. C'est aussi dans ce cadre que s'inscrivent les travaux présentés ici et qui effectuent des traitements rapides d'images numériques. 

 
 N'oublions pas, toutefois, que l'origine en est notre propre perception visuelle, qui elle-même procède à une interprétation des données brutes recueillies par l'\oe il. Au delà de l'\oe il lui-même, notre cerveau génère ou extrait de précieuses informations sur ce qui nous entoure : couleur, forme, volume, texture, mais aussi position, vitesse et accélération relatives à notre propre mouvement. Ces images de la réalité donnent à leur tour naissance à des représentations simplifiées,  des modèles,  de cette perception immédiate et qui ont permis de faire naître la lecture et l'écriture, au travers de la reconnaissance des signes qui la composent et donnent le sens au texte écrit. Mais ces représentations interviennent aussi dans les diverses expressions picturales dont la pratique est presque aussi ancienne que l'Homme.
 
 
 N'oublions pas, toutefois, que l'origine en est notre propre perception visuelle, qui elle-même procède à une interprétation des données brutes recueillies par l'\oe il. Au delà de l'\oe il lui-même, notre cerveau génère ou extrait de précieuses informations sur ce qui nous entoure : couleur, forme, volume, texture, mais aussi position, vitesse et accélération relatives à notre propre mouvement. Ces images de la réalité donnent à leur tour naissance à des représentations simplifiées,  des modèles,  de cette perception immédiate et qui ont permis de faire naître la lecture et l'écriture, au travers de la reconnaissance des signes qui la composent et donnent le sens au texte écrit. Mais ces représentations interviennent aussi dans les diverses expressions picturales dont la pratique est presque aussi ancienne que l'Homme.
 

-Les avènements de la photographie, puis de l'éléctricité avec la radio et télévision ont toutefois ouvert des voies nouvelles au traitement technique de l'information,  dont les application à l'image forment un des domaines aux contours et méthodes particuliers.
+Les avènements de la photographie, puis de l'électricité avec la radio et télévision ont toutefois ouvert des voies nouvelles au traitement technique de l'information,  dont les applications à l'image forment un des domaines aux contours et méthodes particuliers.

 
 

-Durant une période que l'on peut juger, a posteriori, assez courte, la chaîne d'imagerie électronique fut entièrement analogique, de la caméra vidéo à l'écran cathodique par exemple, la télévision étant un des moteurs des progrès techniques dans le domaine.
+Durant une période que l'on peut juger, \textit{a posteriori}, assez courte, la chaîne d'imagerie électronique fut entièrement analogique, de la caméra vidéo à l'écran cathodique par exemple, la télévision étant un des moteurs des progrès techniques dans le domaine.

 Peut-être qu'aujourd'hui, à l'époque du numérique roi, les jeunes gens ne se le figurent pas, mais de nombreuses opérations étaient déjà appliquées à ces signaux analogiques qui véhiculaient les images.  
 Peut-être qu'aujourd'hui, à l'époque du numérique roi, les jeunes gens ne se le figurent pas, mais de nombreuses opérations étaient déjà appliquées à ces signaux analogiques qui véhiculaient les images.  

-Parmi les tous premiers furent les traitements visant à améliorer la qualité visuelle, c'est à dire à réduire l'effet des perturbations imputables aux dispositifs d'acquisition ou bien ajuster les niveaux de luminosité et contraste d'une prise de vue effectuée dans des conditions difficiles. Bien d'autres, plus complexes, furent aussi maîtrisés comme l'incrustation d'éléments synthétiques ou le codage permettant de réserver la visualisation des images aux détenteurs d'un décodeur adapté. 
+Parmi les tous premiers furent les traitements visant à améliorer la qualité visuelle, c'est-à-dire à réduire l'effet des perturbations imputables aux dispositifs d'acquisition ou bien ajuster les niveaux de luminosité et contraste d'une prise de vue effectuée dans des conditions difficiles. Bien d'autres, plus complexes, furent aussi maîtrisés comme l'incrustation d'éléments synthétiques ou le codage permettant de réserver la visualisation des images aux détenteurs d'un décodeur adapté. 

 
 

-Naturellement, la représentation numérique des signaux à de nouveau fait émerger de nouvelles perspectives que l'on ne cerne vraisemblablement que partiellement, pour en vivre les évolutions au jour le jour. Au c\oe ur de ces techniques récentes, l'informatique a déjà permis le développement d'opérations très complexes, quasi irréalisables en analogique, mais aujourd'hui mises à la portée de tout possesseur d'ordinateur personnel : citons en exemple la segmentation, capacité à distinguer les différentes zones d'une image, ou bien la reconnaissance de formes qui intervient, entre autres, dans l'interprétation de texte manuscrit, ou encore la poursuite (tracking) permettant de suivre l'évolution d'objets en mouvement dans une séquence d'images.
+Naturellement, la représentation numérique des signaux a fait émerger de nouvelles perspectives que l'on ne cerne vraisemblablement que partiellement, pour en vivre les évolutions au jour le jour. Au c\oe ur de ces techniques récentes, l'informatique a déjà permis le développement d'opérations très complexes, quasi irréalisables en analogique, mais aujourd'hui mises à la portée de tout possesseur d'ordinateur personnel : citons en exemple la segmentation, capacité à distinguer différentes zones d'une image, ou bien la reconnaissance de formes qui intervient, entre autres, dans l'interprétation de texte manuscrit, ou encore la poursuite (\textit{tracking}) permettant de suivre l'évolution d'objets en mouvement dans une séquence d'images.

 
 Malgré tout, même si certains algorithmes sont capables d'opérations impossibles à la vision humaine, comme par exemple l'extraction d'information dans des images très fortement bruitées, d'autres, comme la segmentation, demeurent très difficiles à automatiser alors que notre cerveau semble les effectuer sans effort.
 
 Malgré tout, même si certains algorithmes sont capables d'opérations impossibles à la vision humaine, comme par exemple l'extraction d'information dans des images très fortement bruitées, d'autres, comme la segmentation, demeurent très difficiles à automatiser alors que notre cerveau semble les effectuer sans effort.

-Certains invariants demeurent toutefois, comme le fait que l'image numérisée est naturellement altérée par des \textit{bruits} de nature et intensité variables trouvant leurs origines dans les dispositifs d'acquisition et l'éclairage des scènes. 

 
 

+Les images numérisées, par opposition aux images numériques de synthèse, partagent la caractéristique d'être naturellement altérées par des \textit{bruits} de nature et d'intensité variables trouvant leurs origines dans les dispositifs d'acquisition et l'éclairage des scènes. 

 La technologie des capteurs (CMOS), l'accroissement de leur densité en pixels et l'augmentation des fréquences de balayage concourent d'ailleurs à en intensifier les effets, justifiant la recherche de méthodes de réduction de bruit adaptées.
 La technologie des capteurs (CMOS), l'accroissement de leur densité en pixels et l'augmentation des fréquences de balayage concourent d'ailleurs à en intensifier les effets, justifiant la recherche de méthodes de réduction de bruit adaptées.

+

 De nombreuses solutions ont été proposées et expérimentées au fil des années, mais à ce jour, aucune ne s'est imposée comme universelle par ses propriétés ou son domaine d'application, tant les caractéristiques des images et des perturbations sont variées. 
 
 De nombreuses solutions ont été proposées et expérimentées au fil des années, mais à ce jour, aucune ne s'est imposée comme universelle par ses propriétés ou son domaine d'application, tant les caractéristiques des images et des perturbations sont variées. 
 

-Par ailleurs, aucune ne fait sauter le verrou du compromis qualité - vitesse et ainsi les méthodes qui génèrent des résultats de grande qualité ne sont dans la pratique pas utilisables du fait de leur temps de calcul trop long. Paradoxalement, ce type de limitation ne se résout pas automatiquement et systématiquement avec l'accroissement régulier des capacités de calcul des ordinateurs car la résolution des capteurs grandit en suivant une courbe quasi identique. La recherche de performance dans le traitement des images doit donc continuer de diversifier les voies qu'elle emprunte pour faire émerger des structures adaptées.         
+Par ailleurs, aucune ne fait sauter le verrou du compromis qualité - vitesse et ainsi les méthodes qui génèrent des résultats de grande qualité ne peuvent pas être utilisées de manière interactive du fait de leur temps de calcul trop long. Paradoxalement, ce type de limitation ne se résout pas automatiquement et systématiquement avec l'accroissement régulier des capacités de calcul des ordinateurs car la résolution des capteurs grandit en suivant une courbe quasi identique. La recherche de performance dans le traitement des images doit donc continuer de diversifier les voies qu'elle emprunte pour faire émerger des structures adaptées.         

 Dans ce contexte, répondant à la demande du grand public pour un rendu toujours plus réaliste des jeux vidéos, les fabricants d'adaptateurs graphiques (cartes graphiques) ont progressivement étendu les capacités de leurs produits pour les doter de moyens de traitement très spécialisés mais pouvant être exécutés à grande vitesse, permettant d'envisager la gestion en temps réel de flux vidéos en haute définition, ce que le processeur central d'un ordinateur personnel ne peut, le plus souvent, pas garantir.
 Ces cartes graphiques GPU (Graphical Processing Unit) sont ainsi devenues de véritables assistants processeurs graphiques, ou coprocesseurs.
 
 Dans ce contexte, répondant à la demande du grand public pour un rendu toujours plus réaliste des jeux vidéos, les fabricants d'adaptateurs graphiques (cartes graphiques) ont progressivement étendu les capacités de leurs produits pour les doter de moyens de traitement très spécialisés mais pouvant être exécutés à grande vitesse, permettant d'envisager la gestion en temps réel de flux vidéos en haute définition, ce que le processeur central d'un ordinateur personnel ne peut, le plus souvent, pas garantir.
 Ces cartes graphiques GPU (Graphical Processing Unit) sont ainsi devenues de véritables assistants processeurs graphiques, ou coprocesseurs.
 

-La technologie de fabrication des GPU est identique à celle utilisée pour la fabrication des microprocesseurs classiques qui pilotent nos ordinateurs (CPU) : il s'agit de la photolithogravure de motifs sur un substrat de silicium. Les éléments fonctionnels de base de ces motifs sont des transistors CMOS (Complementary Metal Oxyde semiconductor) mesurant aujourd'hui $22~nm$. Pour parvenir à traiter les flux d'image plus rapidement que ne peuvent le faire les CPU, les constructeurs de GPU ont organisé différemment les transistors de sorte à disposer d'un grande nombre de petites unités de calcul, chacune avec une faible capacité de stockage individuelle. Ce faisant, les GPU ne disposent plus de toutes les fonctionnalités de gestion et de contrôle que possèdent les CPU et doivent donc être employés différemment pour tirer parti de cette structure particulière.
+La technologie de fabrication des GPUs est identique à celle utilisée pour la fabrication des microprocesseurs classiques qui pilotent nos ordinateurs (CPU) : il s'agit de la photolithogravure de motifs sur un substrat de silicium. Les éléments fonctionnels de base de ces motifs sont des transistors CMOS (Complementary Metal Oxyde semiconductor) mesurant aujourd'hui $22~nm$. Pour parvenir à traiter les flux d'images plus rapidement que ne peuvent le faire les CPUs, les constructeurs de GPU ont organisé différemment les transistors de sorte à disposer d'un grand nombre de petites unités de calcul, chacune avec une faible capacité de stockage individuelle. Ce faisant, les GPUs ne disposent plus de toutes les fonctionnalités de gestion et de contrôle que possèdent les CPUs et doivent donc être employés différemment pour tirer parti de cette structure particulière.

 
 Pour tenter de comprendre l'organisation d'un GPU actuel, il faut s'imaginer des millions d'exécutants (les fils d'exécution ou threads) regroupés en équipes de travail (les blocs), comportant jusqu'à un millier d'exécutant. Au sein d'une même équipe, les exécutants peuvent communiquer entre eux et échanger des données grâce à un espace de stockage proche et rapide. En revanche, la communication inter équipe est difficile et très lente, associée à un espace de stockage, certes volumineux mais dont l'accès est difficile et dont l'usage s'avère donc pénalisant.      
 
 Pour tenter de comprendre l'organisation d'un GPU actuel, il faut s'imaginer des millions d'exécutants (les fils d'exécution ou threads) regroupés en équipes de travail (les blocs), comportant jusqu'à un millier d'exécutant. Au sein d'une même équipe, les exécutants peuvent communiquer entre eux et échanger des données grâce à un espace de stockage proche et rapide. En revanche, la communication inter équipe est difficile et très lente, associée à un espace de stockage, certes volumineux mais dont l'accès est difficile et dont l'usage s'avère donc pénalisant.      

-Même si cette organisation très particulière est naturellement adaptée aux opérations d'affichage, pour lesquelles elle a été conçue, les chercheurs et développeurs, considérant les débits permis par ces processeurs graphiques, ont très vite voulu profiter de ces performances pour traduire des algorithmes dont les implémentations étaient jusqu'alors trop lentes. L'adaptation à l'architecture des GPU s'est toutefois avérée souvent délicate et n'a parfois apporté aucune amélioration des performances.
+Même si cette organisation très particulière est naturellement adaptée aux opérations d'affichage, pour lesquelles elle a été conçue, les chercheurs et développeurs, considérant les débits permis par ces processeurs graphiques, ont très vite voulu profiter de ces performances pour traduire des algorithmes dont les implémentations étaient jusqu'alors trop lentes. L'adaptation à l'architecture des GPUs s'est toutefois avérée souvent délicate et n'a parfois apporté aucune amélioration des performances.

 
 

-C'est dans ce cadre que s'inscrivent les travaux présentés ici, axés sur la recherche de méthodes performantes pour le traitement sur GPU d'images numériques bruitées. Nos premiers travaux ont porté sur la segmentation en parallélisant un algorithme existant pour CPU, tout en lui conférant la capacité de traiter des images de plus grande taille (jusqu'à 16 millions de pixels). Nous nous sommes ensuite intéressé à la réduction de bruit et proposé un algorithme original et adaptable à une grande variété de perturbations, du bruit additif gaussien au bruit multiplicatif gamma. La conception de cet algorithme a été guidée par la volonté de fournir un élément fonctionnel performant sur GPU, permettant une utilisation temps réel tout en apportant une amélioration qualitative par rapport aux filtres rapides simples.
-Dans le même esprit, nous nous sommes penché sur l'implémentation du très employé et très étudié filtre médian pour en proposer l'implémentation la plus performante connue à ce jour avec un débit de plus de 1,85 milliards de pixels à la seconde. À cette occasion, nous avons appliqué des principes d'utilisation de la mémoire qui semblent pouvoir être transposables avec succès à d'autres classes d'algorithmes. Nous l'avons ainsi montré pour les filtres de convolutions.
+C'est dans ce cadre que s'inscrivent les travaux présentés ici, axés sur la recherche de méthodes performantes pour le traitement sur GPU d'images numériques bruitées. Nos premiers travaux ont porté sur la segmentation, en parallélisant un algorithme existant pour CPU, tout en lui conférant la capacité de traiter des images de plus grande taille (jusqu'à 16 millions de pixels). La présentation détaillée en est faite au chapitre \ref{ch-snake}. Nous nous sommes ensuite intéressés à la réduction de bruit et avons proposé un algorithme original et adaptable à une grande variété de perturbations, du bruit additif gaussien au bruit multiplicatif gamma. La conception de cet algorithme a été guidée par la volonté de fournir un élément fonctionnel performant sur GPU, permettant une utilisation temps réel tout en apportant une amélioration qualitative par rapport aux filtres rapides simples, ainsi que le montre le chapitre \ref{ch-lniv} qui lui est consacré.
+Dans le même esprit, le chapitre \ref{ch-median} décrit notre contribution à l'implémentation du très employé et très étudié filtre médian pour en proposer l'implémentation la plus performante connue à ce jour avec un débit de plus de 1.85 milliards de pixels à la seconde. À cette occasion, nous avons appliqué à l'utilisation des différents types de mémoires du GPU, des principes qui semblent être transposables avec succès à d'autres classes d'algorithmes. Nous l'avons ainsi montré au chapitre \ref{ch-convo} pour les filtres de convolutions auxquels nous avons également apporté des performances inégalées sur GPU avec plus de 2 milliards de pixels traités à la seconde (plus de 7 milliards pour le calcul seul).

 
 Ces techniques permettent des gains substantiels en terme de vitesse, mais imposent en contrepartie un style de programmation très inhabituel et fastidieux, ôtant parfois toute versatilité aux blocs fonctionnels ainsi conçus.
 C'est pourquoi enfin, nous avons développé une application en ligne, accessible à tous et permettant de générer simplement le code source des fonctions souhaitées (médians, convolutions) en sélectionnant les options et valeurs des paramètres adaptés au besoin.
 
 
 Ces techniques permettent des gains substantiels en terme de vitesse, mais imposent en contrepartie un style de programmation très inhabituel et fastidieux, ôtant parfois toute versatilité aux blocs fonctionnels ainsi conçus.
 C'est pourquoi enfin, nous avons développé une application en ligne, accessible à tous et permettant de générer simplement le code source des fonctions souhaitées (médians, convolutions) en sélectionnant les options et valeurs des paramètres adaptés au besoin.
 

-Nous nous attacherons dans la suite à effectuer un survol des techniques de traitement d'images numériques et des principales classes d'algorithmes employés. Ce chapitre sera également l'occasion de définir les notations générales applicables à tous le manuscrit et de présenter les principaux travaux de recherche en lien avec nos contributions, qui seront détaillées en commençant par la segmentation orientée régions, suivie la réduction de bruit sous les formes du filtre contraint par lignes de niveaux, du filtre médian, puis des filtres de convolution.             
+Nous nous attacherons dans la suite à effectuer un survol des techniques de traitement d'images numériques et des principales classes d'algorithmes employés. Ce chapitre sera également l'occasion de définir les notations générales applicables à tout le manuscrit et de présenter les principaux travaux de recherche en lien avec nos contributions. Celles-ci seront détaillées, en commençant par la segmentation orientée régions, suivie par la réduction de bruit sous les formes du filtre contraint par lignes de niveaux, du filtre médian, et enfin des filtres de convolution.