X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/these_gilles.git/blobdiff_plain/72441aeeda78a2607a1fe941b9a3580e74b4951c..e81bd9912542bc52e4b0fd1206e0b6f9b93a5fda:/THESE/Chapters/chapter1/chapter1.tex?ds=inline

diff --git a/THESE/Chapters/chapter1/chapter1.tex b/THESE/Chapters/chapter1/chapter1.tex
index 97ae15d..b2289ac 100644
--- 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.
 
-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.  
-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.
-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.
+
 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.
 
-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.      
-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.
 
-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.             
