20 déc

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

diff --git a/THESE/Chapters/chapter1/chapter1.tex b/THESE/Chapters/chapter1/chapter1.tex
index c205aa6a07612e887f747a6dd11d2d492b8aa58d..b2289ac4daaa6f7c9f38275732c18e9fd3baa261 100644 (file)
--- a/THESE/Chapters/chapter1/chapter1.tex
+++ b/THESE/Chapters/chapter1/chapter1.tex
@@ -1,38 +1,35 @@
-Nous percevons le monde au travers le filtre de nos cinq sens, parmi lesquels la vue et plus largement la vision joue un rôle essentiel et unique.
-Elle nous fournit de précieuses données sur les objets qui nous entourent et leur comportement, comme leur couleur, leur forme, leur volume, leur texture mais aussi leur position, vitesse et accélération relative à notre propre mouvement.
+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. 

 
 

-Notre vision est aussi l'appareil sensoriel grâce auquel ont pu naître la lecture et l'écriture, au travers de la reconnaissance des signes qui composent les mots et la ponctuation, ainsi que des groupes de signes qui forment les mots et des groupes de mots qui donnent le sens au texte écrit.
+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.

 
 

-Très tôt, l'être social qu'est l'homme a exprimé le désir et le besoin de partager avec d'autres hommes ce qu'il voyait ou avait vu. Dès lors, il a simplifié, modélisé et inventé des représentations pour les adapter à sa perception et aussi aux contraintes externes. Ses représentations visuelles ont tout d'abord été statiques, exécutées sur des murs de roche, puis il a un jour été capable de les emporter avec lui pour transmettre des messages, partager des informations et des émotions.
+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.

 
 

-Les images prennent ainsi diverses formes selon le rôle qu'on leur attribue: véhiculer des informations textuelles, géométriques ou techniques au travers de schémas conceptuels, ou reproduire au mieux une réalité observée comme le fait la photographie, mais aussi provoquer des émotions au travers de représentations abstraites comme des peintures.
+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.  
+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é. 

 
 

-Certains traitements appliqués à ces représentations sont déjà très anciens ; le fait d'y dissimuler des informations supplémentaires (stéganographie) remonte par exemple à l'antiquité et à été développé sous de multiples formes depuis, tant la nécessité de transmettre secrètement des informations à toujours été un enjeu particulièrement important.
+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.

 
 

-Toutefois, la découverte et la maîtrise de l'électricité ont ouvert des voies nouvelles au traitement technique de l'information et ont permis l'avènement de ce que l'on nomme désormais le traitement du signal, dont les application à l'image forment un des domaines aux contours et méthodes particuliers.
+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.

 
 

-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.
-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.
+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.

 
 

-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é. Ce dernier paraîtrait archaïque de nos jours tant son principe était simple : permuter les lignes de chaque image selon une séquence prédéterminée. La capacité de calcul d'un simple téléphone portable actuel serait suffisante pour en décrypter la séquence et décoder les images en temps réel. 
+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. 

 
 

-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. L'informatique est le coeur de ces techniques récentes et 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.
-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 demeurent très difficiles à automatiser alors que notre cerveau semble les effectuer sans effort, comme la segmentation.  
-
-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. 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, toutefois, à 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.
-%vérifier                    
+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.
 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 sont ainsi devenues de véritables assistants processeurs graphiques, ou coprocesseur, appelés aujourd'hui GPU pour \textit{graphical processing unit}.
+Ces cartes graphiques GPU (Graphical Processing Unit) sont ainsi devenues de véritables assistants processeurs graphiques, ou coprocesseurs.
+
+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.

 
 

-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.
-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 éloigné et dont l'usage s'avère donc très pénalisant.      
-Cette organisation très particulière est naturellement adaptée aux opérations d'affichage, pour lesquelles elle a été conçue, mais considérant les débits permis par ces processeurs graphiques, les chercheurs et développeurs ont très vite voulu profiter de ces performances pour traduire des algorithmes dont les implémentations étaient jusqu'alors trop lentes. Toutefois, l'adaptation à l'architecture des GPU s'est avérée souvent délicate et n'a parfois apporté aucune amélioration des performances.
+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 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, pas nécessairement optimal au sens de la qualité du traitement, mais 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. Dans le chapitre \ref{ch_ea}, nous présenterons les principaux travaux de recherche en lien avec ceux que nous avons menés et qui seront présentés dans les chapitres \ref{ch_snake} et suivants, en commençant par notre contribution à la segmentation orientée régions, suivie de celles concernant 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.