Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Collège doctoral N° attribué par la bibliothèque THÈSE pour obtenir le grade de

Collège doctoral N° attribué par la bibliothèque THÈSE pour obtenir le grade de Docteur de l’École des Mines de Paris Spécialité “Morphologie Mathématique” présentée et soutenue publiquement par Jaromír BRAMBOR le 11 Juillet 2006 ALGORITHMES DE LA MORPHOLOGIE MATHÉMATIQUE POUR LES ARCHITECTURES ORIENTÉES FLUX Directeur de thèse : Michel BILODEAU Jury M. Gilles BERTRAND Examinateur M. Michel BILODEAU Examinateur M. Pierre BONTON Rapporteur M. Laurent CHABIN Examinateur M. Dominique JEULIN Président M. Michel PAINDAVOINE Rapporteur Marques commerciales déposées et/ou utilisées dans un ou plusieurs pays et leurs propriétaires respectifs Marques Propriétaire Aphelion Amerinex Applied Imaging, Inc. et ADCIS SA. AMD, AMD Athlon, AMD Opteron Advanced Micro Devices, Inc. ARM, ARM11 ARM Limited ATI, CrossFire, Radeon ATI Technologies Inc. SuperH Hitachi Ltd. IBM, PowerPC International Business Machines Corporation. IEEE, POSIX The Institute of Electrical and Electronics Engineers, In- corporated. Intel, Itanium, MMX, Pentium Intel Corporation MATLAB The MathWorks, Inc. DirectX, Microsoft, Microsoft Press, Windows, Win32, Xbox Microsoft Corporation AltiVec, MOTOROLA, Motorola, Inc. GeForce, NVidia, NVIDIA Quadro, SLI NVIDIA Corporation PCI Express PCI-SIG RenderMan Pixar Animation Studios OpenGL, OpenGL ES Silicon Graphics Incorporated Sony, PlayStation Sony Corporation Sun, VIS Sun Microsystems, Inc. Crusoe, Efﬁceon, Transmeta Transmeta Corporation TSMC Taiwan Semiconductor Manufacturing Company, Ltd. Linux Linus Torvalds Wikipedia Wikimedia Foundation, Inc. À Jaromír et Blanka mes parents et à Julie et Maxim Jaromír ma famille Cette page est blanche par intention Remerciements Cette thèse est l’aboutissement d’un projet de recherche de plusieurs années. Ce projet doit un grand merci à tous ceux qui l’ont soutenu directement ou indirectement lors de sa réalisation et à tous ceux qui ont suivi la création et la ﬁnalisation de cette thèse, de loin ou de près. Au Centre de Morphologie Mathématique et à ses membres J’aimerais exprimer mes sincères remerciements à l’École Nationale Supérieure des Mines de Paris et en particulier à son Centre de Morphologie Mathématique à Fontainebleau représenté par Monsieur Fernand Meyer pour m’avoir accueilli et m’avoir permis de travailler sur le sujet de mon projet de re- cherche. Mes remerciements s’adressent également à Monsieur Michel Bilodeau, mon directeur de thèse, pour le temps qu’il a consacré à l’encadrement de mon projet et de ma thèse et pour ses avis sur mon travail. Un merci s’adresse à Monsieur Jean Serra que j’apprécie beaucoup pour son travail effectué dans le domaine de la morphologie mathématique. Pour son travail qui inﬂuence le traitement d’images depuis des décennies, qui conduit d’autres chercheurs et qui les incite à utiliser la morphologie mathématique et à continuer de la développer. Un merci aussi aux autres membres du CMM – Beatriz Marcotegui et Dominique Jeulin, Serge Beucher, Jean-Claude Klein, Petr Dokládal, Etienne Decencière, Francis Bach et John-Richard Ordóñez Varela pour leur présence et leurs points de vue discutés au cours de séances de lectures et d’exposés car dans la science et la recherche, c’est aussi l’effet synergique qui importe et qui permet d’avancer plus rapidement. Je ne dois pas oublier de remercier deux membres non scientiﬁques mais dont l’importance au sein du CMM est cruciale et chez qui j’apprécie leurs valeurs humaines et leur serviabilité. Mon merci s’adresse ainsi à Catherine Moysan et à Laura Andriamasinoro. Aux partenaires du projet de recherche Une partie de cette thèse a été développée dans le cadre du projet Medea+ PocketMM et ﬁnancée par le Ministère de l’Économie, des Finances et de l’Industrie (MINÉFI) de la République française. Un grand merci à nos partenaires et en particulier à STMicroelectronics pour nous avoir procuré les outils de développement. À ma famille Un merci spécialement chaleureux à ma famille représentée par ma femme Julie et mon ﬁls Maxim Jaromír, par Blanka, ma mère, in memoriam par Jaromír, mon père, par mes sœurs Milena, Blanka et Soˇ na et leurs familles pour la patience dont ils ont fait preuve lors de la rédaction du manuscrit et pour le soutien qu’ils m’ont prodigué dans les moments rudes et éprouvants. Merci beaucoup. 5 Algorithmes de la morphologie mathématique pour les architectures orientées ﬂux Jaromír BRAMBOR À mes collègues en recherche Mes collègues du Centre de Morphologie Mathématique méritent, eux aussi, une part de remercie- ment car c’est eux qui ont donné l’esprit multiculturel à mon séjour à Fontainebleau et qui m’ont aidé à mettre au point mon français oral à travers des discussions portant sur les sujets scientiﬁques et mé- taphysiques. Mes mercis s’adressent1 à Eva Dokládalová, Mathilde Boehm, à Thomas Walter, Thomas Retornaz, RafﬁEnﬁciaud, Costin Alin Caciu, Jesús Angulo, Romain Lerallut, Gabriel Fricout, Timothée Faucon, Thibauld Nion, Nicolas Laveau, Souhaïl Outal et Maxime Moreaud. 1 nommés par ordre croissant selon la distance topologique à partir de mon bureau 6 Résumé ALGORITHMES DE LA MORPHOLOGIE MATHÉMATIQUE POUR LES ARCHITECTURES ORIENTÉES FLUX École des Mines de Paris Jaromír BRAMBOR, 11 Juillet 2006 Mots clés : morphologie mathématique, algorithmes rapides, ﬂux de données, macro blocs SIMD, pro- cesseurs graphiques, Haskell, description formelle, lambda calcul Cette thèse est consacrée aux algorithmes de morphologie mathématique qui peuvent considérer les pixels d’une image comme un ﬂux de données. Nous allons démontrer qu’un grand nombre d’algorithmes de morphologie mathématique peuvent être décrits comme un ﬂux de données traversant des unités d’exécution. Nous verrons que cette approche peut aussi fonctionner sur des processeurs génériques possédant un jeu d’instructions multimédia ou sur des cartes graphiques. Nous présentons dans un premier temps les possibilités offertes par les architectures grand public en guise de traitements morphologiques et explorons ensuite leurs capacités d’exécution parallèle avec des jeux d’instructions SIMD. Nous terminons cette partie en examinant les capacités de calcul parallèle à l’échelle des tâches et des ﬁls d’exécution que nous apportent les processeurs à plusieurs cœurs. Pour décrire les algorithmes en ﬂux de données, nous proposons d’utiliser le langage fonctionnel Haskell, ce qui nous permettra de décrire les briques de base de la construction des algorithmes de morphologie mathématique. On applique ces briques dans la description des algorithmes les plus cou- ramment utilisés (dilatation/érosion, opérations géodésiques, fonction distance et nivellements) ce qui facilitera le portage de ces algorithmes sur plusieurs plate-formes. L’apport principal de cette thèse est qu’elle aborde un sujet important du point de vue pratique et qu’elle explore les capacités SIMD des architectures multimédia en vue d’assurer l’exécution rapide des algorithmes morphologiques travaillant sur le voisinage. Nous proposons pour la construction des algo- rithmes morphologiques un mode d’exécution original par macro blocs et nous étudions en profondeur la transposition de cette idée aux architectures SIMD. Nous montrons que l’utilisation des macro blocs est particulièrement intéressante pour les architectures multimédia et nous montrons également que les algorithmes morphologiques proposés dans cette thèse atteignent de meilleures performances que les implémentations standard. Un nouveau champ s’ouvre ainsi aux algorithmes développés dans les appli- cations de traitement d’images en temps réel. Cette thèse explore également les processeurs graphiques et démontre sur des résultats expérimen- taux qu’ils sont, dès à présent, assez performants pour concurrencer les processeurs généraux. L’apport secondaire de cette thèse est celui du formalisme fonctionnel basé sur le lambda calcul qui a été adopté pour la description des algorithmes travaillant sur les ﬂux de données. 7 Cette page est blanche par intention Abstract ALGORITHMS OF MATHEMATICAL MORPHOLOGY FOR STREAM-ORIENTED ARCHITECTURES École des Mines de Paris Jaromír BRAMBOR, 11 July 2006 Keywords : Mathematical Morphology, fast algorithms, stream of data, SIMD macro blocs, graphics processors, Haskell, formal description, lambda calculus This thesis deals with the algorithms of Mathematical Morphology that can consider the pixels of an image as if they were a stream of data. We will show that a great number of algorithms of Mathematical Morphology can be described by data ﬂows (streams) passing through the operating units. We will see that this approach can function on generic processors supporting a multi-media instruction set as well as on graphics cards. Firstly, we present the possibilities of main stream architectures for morphological processing and then we explore their capacities in terms of parallel execution with SIMD instruction sets. Finally, we examine the possibilities of parallel computing using tasks and threads on multi-core processors. We propose to use the functional language Haskell for the description of algorithms operating on data ﬂows. This allows us to describe the building blocks that are used to construct morphological algorithms. We apply these bulding blocks in the description of the most usually used algorithms (dilation/erosion, geodesic operations, distance function and levelings). This will also facilitate the porting of these algo- rithms onto several platforms. The principal contribution of this thesis is to address an important subject from the practical point of view and to explore SIMD capabilities of multi-media architectures to ensure the fast execution of mor- phological algorithms working on neighborhood. We propose an original mode of execution by macro blocks for the construction of morphological algorithms and we study in depth the transposition of this idea to SIMD architectures. We show that the use of macro blocks is particularly interesting for multi- media architectures. We also show that the morphological algorithms proposed in this thesis reach better performances than standard implementations. Thus, a new ﬁeld opens uploads/Geographie/ brambor-doctoral-thesis.pdf