Cette thèse s’inscrit dans le cadre d’une convention industrielle de formation par la recherche (CIFRE) entre le laboratoire Hubert Curien et l’entreprise Pattyn Bakery Division. L’objectif de ces travaux est le développement d’un système de détection de trait laser sur FPGA (Field Programmable Gate Array) qui soit plus performant que système actuel de l’entreprise. Dans l’industrie, les concepteurs de systèmes de vision doivent pouvoir créer et modifier facilement leurs systèmes afin de pouvoir les adapter aux besoins de leurs clients et aux évolutions technologiques. Ainsi les opérateurs développés doivent être génériques afin de permettre aux concepteurs de modifier le système de vision sans nécessairement avoir de compétences matérielles. Les concepteurs doivent également pouvoir être en mesure d’estimer quelles seront les ressources utilisées par l’opérateur en cas modifications du système : paramètres de l’application, capteur, famille de FPGA... Dans ce manuscrit, les principaux algorithmes de détection de trait laser ainsi que leurs propriétés ont été étudiés. Un opérateur de détection de trait laser a été choisi et développé. L’implantation de cet opérateur sur une caméra-FPGA du marché a permis d’obtenir un premier prototype fonctionnel. Les performances temporelles de ce nouveau système sont quatre fois supérieures à celles du système actuellement utilisé par l’entreprise. Le nouveau système est capable de traiter jusqu’à 2500 images par seconde. Enfin, les modèles de la consommation des ressources permettent de dimensionner une architecture à partir d’un ensemble de paramètres prédéfinis de manière rapide et sans faire de synthèses. Le paramètre auquel les concepteurs doivent prêter le plus d’attention est le niveau de parallélisme des données. Ce paramètre permet d’exploiter les capacités de parallélisme du FPGA en consommant plus de ressources. Cependant, les ressources du FPGA sont limitées et augmenter le niveau de parallélisme peut induire la nécessité de changer de FPGA. Le système et les données fournies permettront à l’entreprise d’adapter le système de vision selon les besoins futurs des clients en les guidant vers le choix du matériel / This thesis is part of an industrial research training agreement (CIFRE) between the Hubert Curien laboratory and the company Pattyn Bakery Division. The goal of this work is the development of an FPGA laser line detection system that is more efficient than the current system of the company. In the industry, vision system designers need to be able to easily create and modify their systems in order to adapt them to their customers’ needs and technological developments. Thus developed operators must be generic to allow designers to change the vision system without necessarily having material skills. Designers must also be able to estimate what resources will be used by the operator in case of system changes : application parameters, sensor, family of FPGAs ... In this manuscript, the main laser line detection algorithms and their properties have been studied. A laser line detection operator was chosen and developed. The implementation of this operator on an FPGA-camera from market has resulted in a first functional prototype. The time performance of this new system is four times that of the system currently used by the company. The new system is able to process up to 2500 frames per second. Finally, resource consumption models makes it possible to size an architecture from a set of predefined parameters quickly and without synthesizing. The parameter to which designers must pay the most attention is the level of parallelism of the data. This parameter makes it possible to exploit the parallelism capabilities of the FPGA by consuming more resources. However, the resources of the FPGA are limited and increasing the level of parallelism can induce the need to change the family of FPGAs. The system and the data provided will enable the company to adapt the vision system to the future needs of customers by guiding the choice of equipment.

Étant donné un ensemble S de points du plan, une triangulation de S est une décomposition de l'enveloppe convexe de S en triangles dont les sommets sont les points de S. Une triangulation de S est dite de Delaunay si le cercle circonscrit à chaque triangle ne contient aucun point de S en son intérieur. Dans cette thèse, nous étudions une généralisation de ces notions à un ensemble S de segments disjoints du plan.<br />Nous commençons par définir une nouvelle famille de diagrammes, appelés triangulations de segments. Nous étudions leurs propriétés géométriques et topologiques et nous donnons un algorithme pour construire efficacement une telle triangulation.<br />Nous généralisons ensuite la notion de triangulation de Delaunay aux triangulations de segments et nous mettons en évidence la dualité avec le diagramme de Voronoï de segments.<br />Nous étendons également la légalité des arêtes au cas des triangulations de segments en définissant, d'une part, la légalité géométrique qui caractérise la triangulation de Delaunay de segments parmi l'ensemble de toutes les triangulations de segments possibles et, d'autre part, la légalité topologique qui caractérise les triangulations de segments qui ont la même topologie que celle de Delaunay.<br />Enfin, nous décrivons un algorithme de « flip » qui transforme toute triangulation de segments en une triangulation qui a la même topologie que celle de Delaunay. À l'aide de fonctions localement convexes, nous démontrons que la suite de triangulations construites par cet algorithme converge vers celle de Delaunay et nous prouvons qu'une triangulation de segments qui a la même topologie que celle de Delaunay est obtenue après un nombre fini d'étapes.

Dans cette thèse, nous étudions les triangulations définies par un ensemble de points dans des espaces de topologies différentes. Nous proposons une définition générale de la triangulation de Delaunay, valide pour plusieurs classes d'espaces, ainsi qu'un algorithme de construction. Nous fournissons une implantation pour le cas particulier du tore plat tridimensionnel. Ce travail est motivé à l'origine par le besoin de logiciels calculant des triangulations de Delaunay périodiques, dans de nombreux domaines dont l'astronomie, l'ingénierie des matériaux, le calcul biomédical, la dynamique des fluides, etc. Les triangulations périodiques peuvent être vues comme des triangulations du tore plat. Nous fournissons une définition et nous développons un algorithme incrémentiel efficace pour calculer la triangulation de Delaunay dans le tore plat. L'algorithme est adapté de l'algorithme incrémentiel usuel dans R^d. Au contraire des travaux antérieurs sur les triangulations périodiques, nous évitons de maintenir plusieurs copies périodiques des points, lorsque cela est possible. Le résultat fourni par l'algorithme est toujours une triangulation du tore plat. Nous présentons une implantation de notre algorithme, à présent disponible publiquement comme un module de la bibliothèque d'algorithmes géométriques CGAL. Nous généralisons les résultats à une classe plus générale d'espaces quotients plats, ainsi qu'à des espaces quotients de courbure constante positive. Enfin, nous considérons le cas du tore double, qui est un exemple de la classe beaucoup plus riche des espaces quotients de courbure négative constante.

Thesis (MSc (Mathematical Sciences. Applied Mathematics))--University of Stellenbosch, 2007. / Image morphing is a popular technique used to create spectacular visual effects, by gradually transforming one image into another. This thesis explains what exactly is meant by the terms “image morphing” / “warping”, where it is used and how it is done. A few existing morphing techniques are described and finally an implementation using Delaunay triangulation and texture mapping is presented.

The main goal of this work is to present a discrete analogous of the laplacian operator, that is, a linear operator on the set of piecewise linear functions over a triangular mesh that has similar properties to the continuous laplacian over a surface. Particularly, we will show that if the mesh satisfies a Delaunay criterion, the laplacian obeys a discrete version of the maximum principle, which importance in the discrete setting is similar to the importance of the maximum principle in the theory of harmonic functions. We also present three applications of the discrete laplacian: the first one has as objective to get parametrizations of meshes for texture mapping; the second one consists of mesh smoothing by a diffusion process; the third and last application aims to identify forms and symmetries of objects by means of the contour curves associated to the eigenfunctions of the laplacian operator. / Fundação de Amparo a Pesquisa do Estado de Alagoas / O objetivo desta disserta¸c ao ´e apresentar um an´alogo discreto do operador laplaciano, ou seja, um operador linear definido no conjunto das fun¸c oes lineares por partes em uma malha de tri angulos que possua o m´aximo de propriedades an´alogas ao operador laplaciano cont´&#305;nuo sobre uma superf´&#305;cie. Em particular, mostraremos que se a malha satisfaz ao crit´erio de Delaunay, o laplaciano obedece a uma vers ao discreta do princ´&#305;pio do m´aximo, que possui import ancia semelhante ao princ´&#305;pio do m´aximo na teoria das fun¸c oes harm onicas. Apresentamos ainda tr es aplica¸c oes do laplaciano discretizado: a primeira tem como objetivo obter parametriza¸c oes de malhas para efeito de mapeamento de textura; a segunda consiste na suaviza¸c ao de malhas por meio do processo de difus ao; a terceira e ´ultima aplica¸c ao visa identificar formas e simetrias de objetos por meio das curvas de contorno associadas `as autofun¸c oes do laplaciano.

L'embryon humain est aujourd'hui au centre d'une multitude de préoccupations : personnelles, familiales, scientifiques, sociales, politiques et éthiques. Sa manipulation dans le cadre de la recherche scientifique constitue aujourd'hui une question controversée et polémique au Brésil et en France. En s'appuyant sur la théorie des représentations sociales, nous nous intéressons à comprendre comment des éléments contextuels façonnent la construction de l'embryon humain en tant qu'objet social. Nous avons entrepris un programme de recherche pluri-méthodologique afin d'étudier la production et l'actualisation des représentations concernant l'embryon humain et la recherche sur l'embryon humain en fonction des différentes dimensions contextuelles d'ordre cognitif et social au Brésil et en France. Ce programme s'inscrit dans une approche multi-niveaux des représentations sociales dont l'enjeu théorico-méthodologique est l'étude des phénomènes représentationnels dans différents lieux de production et d'actualisation (formation des savoirs et des attitudes, communications sociales, pratiques institutionnelles ; situations de naturalité et situations provoquées d'expression des représentations). Le croisement des différentes techniques nous permet d'accéder à des observations qui corroborent pour montrer l'incidence du social dans la construction de l'embryon humain en tant qu'objet de représentation et de statuer sur le caractère local/global de cette incidence. Nous discutons l'ensemble de ces résultats afin de montrer l'intérêt heuristique des représentations sociales dans les approches comparatives contextuelles en psychologie sociale et notamment dans le champ de la bioéthique. / The human embryo is at the center of a wide range of personal, familial, scientific, social, political and ethical concerns. Scientific use of the human embryo represents today a controversial issue in Brazil and France. Using the theory of social representations, we investigate how contextual elements shape the construction of the human embryo qua social object. We have undertaken a multi-methodological study to determine the production and realization of the representations regarding the human embryo and the scientific research on human embryos according to the different contextual dimensions of cognitive and social development in Brazil and in France. This program is a multi-level approach using social representations for which the theoretical and methodological challenge is the study of representational phenomena in different places of production and realization (construction of knowledge and attitudes, social communication, institutional practices; situations of naturalness and situations induced by the expression of the representations). The unification of different techniques has allowed us access to convergent observations that show the impact of the social construction of the human embryo qua represented object and to arbitrate the local / global character of that impact. In the discussion of the results we demonstrate the heuristic interest of the approach of social representations in the context of comparative approaches in social psychology, particularly in the field of bioethics.

Dans une perspective psychosociale, l’objectif de cette thèse est de saisir l’aspect dynamique de la rumeur inter et intragroupe et son rôle dans la reconstruction des mémoires collectives dans des contextes spatio-temporels précis. A partir d’une étude monographique, sur la catastrophe de l’usine AZF survenue le 21 septembre à Toulouse, notre travail de thèse vise à expliquer ce qui est en jeu pour les groupes en présence, d’adhérer à et de faire perdurer ou non, telle ou telle « version ». En prenant en compte l'espace en tant que cadre social de la mémoire, nous nous intéressons à l'inscription spatiale de la rumeur, notamment au travers des pratiques commémoratives, comme une manière de s'approprier les lieux détruits par cette catastrophe. Notre recherche s’ancre dans le champ de la pensée sociale interrogeant les savoirs du sens commun et les manières de penser en contexte en fonction des insertions sociales des individus. Dans cette perspective nous adoptons le regard ternaire propre à la psychologie sociale pour interroger la rumeur dans une visée compréhensive du phénomène. Pour cela, nous avons mis en place une triangulation méthodologique (entretiens semi-directifs, observations, analyse de presse et questionnaires) afin de saisir la dynamique de la rumeur dans ses différentes temporalités, au travers de plusieurs groupes plus ou moins impliqués. L’analyse de l’ensemble des résultats confirme alors l’existence d’un phénomène rumoral à Toulouse plus de 10 ans après la catastrophe autour des origines de l’explosion au sein des différents lieux et groupes enquêtés. Le niveau d’implication des sujets et le degré des émotions négatives ressenties suite à l’événement sont alors des facteurs saillants expliquant d’une part, l’adhésion à une rumeur et, d’autre part, sa persistance. Toutefois, nos résultats mettent en évidence des variations de contenu du message de la rumeur selon les groupes en fonction de leur insertion et position sociales ainsi que du lien qui les rattachait à l’usine AZF. Notre recherche souligne ainsi combien le processus de la rumeur et les fonctions qu’elle remplit ne sont pas simplement animés par une mécanique cognitive de la pensée mais davantage motivés par des enjeux identitaires et mémoriels, selon les intérêts du moment pour le groupe. La permanence de la rumeur dans le temps et des lieux précis, témoigne alors de son rôle dans la transmission d’une mémoire collective, de sorte qu’elle soit valorisante pour les groupes. / In a psychosocial perspective, the aim of this research is to capture the dynamic aspect of inter and intragroup rumor and its role in the reconstruction of collective memories in specific spatiotemporal contexts. Based on a monographic study relative to the explosion of the AZF factory that occurred September 21th, 2001, in Toulouse, our PhD work aims to explain what is at stake for the groups involved, and why would they adopt and perpetuate or not a « version » of the story or another. Taking into account space as a social framework of memory, we will focus on the spatial inscription of the rumor, particularly through commemorative practices, considered as a way to re-appropriate places destroyed by the catastrophe. Our research belongs to the field of social thought, which question common sense knowledge and ways of thinking in specific contexts, depending on individuals’ social insertion. In this perspective, we adopt a « ternary » interpretation of facts, inherent to social psychology, to investigate rumor in a comprehensive approach. To fulfill this goal, we applied methodological triangulation in our research (semi-structured interviews, observations, press analyses and questionnaires), in order to seize the dynamic of rumor in its different temporalities, through several groups more or less involved. The analysis of all results confirm the existence of a rumor phenomenon in Toulouse over 10 years after the disaster and related to the origins of the explosion, in the different investigated places and groups. The level of implication and the level of negative emotions felt after the event are salient factors to explain both the adhesion to a rumor and its persistence. However, our results highlight variations in the message content for different groups depending on their social insertion and position as well as the bond that relationship that bonded them to the AZF factory. Our research affirm that the rumor process and functions are not simply animated by a cognitive mechanisms of though but rather motivated by identity and memory issues, depending on the group’s present interest. The persistence of rumor in specific times and places demonstrate its role in the transmission of a collective memory, in a gratifying way for the involved groups.

Nous étudions dans cette thèse la génération de maillages anisotropes basée sur la triangulation de Delaunay et le diagramme de Voronoi. Nous considérons tout d'abord les maillages anisotropes localement uniformes, développés par Boissonnat, Wormser et Yvinec. Bien que l'aspect théorique de cette approche soit connu, son utilité pratique n'a été que peu explorée. Une étude empirique exhaustive est présentée et révèle les avantages, mais aussi les inconvénients majeurs de cette méthode. Dans un second temps, nous étudions les diagrammes de Voronoi anisotropes définis par Labelle et Shewchuk. Nous donnons des conditions suffisantes sur un ensemble de points pour que le dual du diagramme soit une triangulation plongée en toute dimension ; un algorithme générant de tels ensembles est conçu. Ce diagramme est utilisé pour concevoir un algorithme qui génère efficacement un maillage anisotrope pour des domaines de dimension intrinsèque faible plongés dans des espaces de dimension large. Notre algorithme est prouvable, mais les résultats sont décevants. Enfin, nous présentons le diagramme de Voronoi Riemannien discret, qui utilise des avancées récentes dans l'estimation de distances géodésiques et dont le calcul est grandement accéléré par l'utilisation d'un graphe anisotrope. Nous donnons des conditions suffisantes pour que notre structure soit combinatoirement équivalente au diagramme de Voronoi Riemannien et que son dual utilisant des simplexes droits mais aussi courbes est une triangulation plongée en toute dimension. Nous obtenons de bien meilleurs résultats que pour nos autres techniques, mais dont l'utilité reste limitée / In this thesis, we study the generation of anisotropic meshes using the concepts of Delaunay triangulations and Voronoi diagrams. We first consider the framework of locally uniform anisotropic meshes introduced by Boissonnat, Wormser and Yvinec. Despite known theoretical guarantees, the practicality of this approach has only been hardly studied. An exhaustive empirical study is presented and reveals the strengths but also the overall impracticality of the method. In a second part, we investigate the anisotropic Voronoi diagram introduced by Labelle and Shewchuk and give conditions on a set of seeds such that the corresponding diagram has a dual that is an embedded triangulation in any dimension; an algorithm to generate such sets is devised. Using the same diagram, we propose an algorithm to generate efficiently anisotropic triangulations of low-dimensional manifolds embedded in high-dimensional spaces. Our algorithm is provable, but produces disappointing results. Finally, we study Riemannian Voronoi diagrams and introduce discrete Riemannian Voronoi diagrams, which employ recent developments in the numerical computation of geodesic distances and whose computation is accelerated through the use of an underlying anisotropic graph structure. We give conditions that guarantee that our discrete structure is combinatorially equivalent to the Riemannian Voronoi diagram and that its dual is an embedded triangulation, using both straight and curved simplices. We obtain significantly better results than with our other methods, but the overall utility of

Inspired by work of Hubery [Hub] and Fomin, Shapiro and Thurston [FST06] related to cluster algebras, we construct a bijection between certain curves on a cylinder and the string modules over a path algebra of type Ãn. We show that under this bijection irreducible maps and the Auslander-Reiten translation have a geometric interpretation. Furthermore we prove that the dimension of extension groups can be expressed in terms of intersection numbers. Finally we explain the connection to cluster algebras and apply our results to describe the exchange graph in type Ãn. / Angeregt durch Arbeiten zu Cluster-Algebren von Hubery [Hub] und Fomin, Shapiro und Thurston [FST06] konstruieren wir eine Bijektion zwischen gewissen Kurven auf einem Zylinder und den Fadenmoduln über einer Wege-Algebra vom Typ Ãn. Wir zeigen, daß unter dieser Bijektion sowohl irreduzible Abbildungen als auch die Auslander-Reiten-Verschiebung eine geometrische Interpretation haben. Weiterhin beweisen wir, daß sich die Dimension der Erweiterungsgruppen mittels Anzahlen von Schnittpunkten ausdrücken läßt. Schließlich erklären wir die Verbindung zu Cluster-Algebren und verwenden unsere Ergebnisse um den Austauschgraph im Typ Ãn zu beschreiben.

Inspired by work of Hubery [Hub] and Fomin, Shapiro and Thurston [FST06] related to cluster algebras, we construct a bijection between certain curves on a cylinder and the string modules over a path algebra of type Ãn. We show that under this bijection irreducible maps and the Auslander-Reiten translation have a geometric interpretation. Furthermore we prove that the dimension of extension groups can be expressed in terms of intersection numbers. Finally we explain the connection to cluster algebras and apply our results to describe the exchange graph in type Ãn. / Angeregt durch Arbeiten zu Cluster-Algebren von Hubery [Hub] und Fomin, Shapiro und Thurston [FST06] konstruieren wir eine Bijektion zwischen gewissen Kurven auf einem Zylinder und den Fadenmoduln über einer Wege-Algebra vom Typ Ãn. Wir zeigen, daß unter dieser Bijektion sowohl irreduzible Abbildungen als auch die Auslander-Reiten-Verschiebung eine geometrische Interpretation haben. Weiterhin beweisen wir, daß sich die Dimension der Erweiterungsgruppen mittels Anzahlen von Schnittpunkten ausdrücken läßt. Schließlich erklären wir die Verbindung zu Cluster-Algebren und verwenden unsere Ergebnisse um den Austauschgraph im Typ Ãn zu beschreiben.