Orientador: Sueli Irene Rodrigues Costa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-10T10:56:09Z (GMT). No. of bitstreams: 1 Strapasson_JoaoEloir_D.pdf: 1100322 bytes, checksum: 054aeab4b36f30144155ce6b1668659a (MD5) Previous issue date: 2007 / Resumo: Este trabalho está dividido em duas partes. A primeira e dedicada ao problema de encontrar o menor vetor não nulo de um reticulado. Este é um problema de alta complexidade computacional e que tem grande interesse tanto para a Teoria dos Códigos, como para diversas outras áreas. Esse mínimo está associado a performance do reticulado em termos da codificação: quanto maior for a razão entre este mínimo e o determinante do reticulado, melhor e a distribuição dos pontos no espaço (alta densidade de empacotamento). Nesta tese demos ênfase ao caso especial dos reticulados obtidos por uma projeção ortogonal do reticulado n-dimensional dos inteiros na direção de seus elementos. Tais reticulados estão associados ao problema de codificação contínua fonte/canal. Mostramos nos casos tri e quadridimensionais em que condições podemos garantir reticulados bons, ou seja, com alta densidade de empacotamento. Neste processo foram também construídos dois novos algoritmos, um para cálculo da base de Minkowski de um reticulado e outro específico para a busca da norma mínima do reticulado-projeção. Na segunda parte trabalhamos com grafos em toros planares que são quocientes de reticulados, os quais são isomorfos a grafos circulantes. Estabelecemos a conexão entre estes códigos esféricos rotulados por grupos cíclicos e códigos perfeitos na métrica de Lee. A partir de tal associação foram também obtidos resultados sobre o gênero 1 e a determinação do dos gênero de uma classe especial de grafos circulantes que tem número arbitrariamente grande de conexões (grau) / Abstract: The research developed here is related and inspired by problems in coding theory. It is presented in two parts. In the first we focus on the search for the minimum nonvanishing vector of a lattice, specially in the case of a projection of the ndimensional integer lattice in the direction of one of its vectors. This is a problem of high computational complexity which is related to the search for efficient joint sourcechannel continuous coding. In the second part we deal with flat torus graphs generated by a quotient of lattices and which are labeled by a a cyclic group of isometries. We show that any circulant graph is isomorphic to one of these graphs and hence associated to a spherical code. Through these isomorphism a complete classification of circulant graphs of genus one and the genus of an arbitrarily high order class of circulant graphs is obtained. / Doutorado / Geometria Topologia / Doutor em Matemática

Orientador : Sueli Irene Rodrigues Costa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-06T14:39:59Z (GMT). No. of bitstreams: 1 Siqueira_RogerioMonteirode_D.pdf: 1994309 bytes, checksum: 7735d63966bc2d9b5c84ccac989c3289 (MD5) Previous issue date: 2006 / Resumo: Códigos esféricos euclidianos com simetrias são órbitas finitas de grupos de matrizes ortogonais. Tais códigos são também conhecidos como códigos de grupo. Neste trabalho, os códigos de grupo comutativo em dimensão par são caracterizados sobre toros planos, subvariedades da esfera. Em particular, se o grupo de matrizes for cíclico, o código gerado está contido em um nó que se enrola em um tora. Se a dimensão for ímpar, todo código de grupo comutativo mora em anti-primas cujas bases estão contidas em dois toros planos. Tal caracterização permitiu a construção de limitantes para a cardinalidade destas constelações de pontos em termos da distância mínima destes códigos e da densidade de empacotamento de um reticulado associado. Utilizando o método de Biglieri e Elia, que procura o vetor inicial cujo respectivo código de grupo cíclico tem a melhor distância mínima, apresentamos também os melhores códigos de grupo cíclico em dimensão quatro até 100 pontos / Abstract: Euclidean spherical codes with symmetries are orbits of finite orthogonal matrix groups. These codes are also known as group codes. ln this work, the commutative group codes in even dimensions are viewed on flat tori, which are submanifolds of the sphere. Also, if the matrix group is cyclic, the generated code lies on a knot which wraps around a torus. If the dimension is odd, every commutative group code lies on an anti-prism whose bases are contained in two flat tori. This interpretation lead us to build upper bounds for the cardinality of these constellations involving their minimum distance and the packing density of an associated lattice. Using a method by Biglieri and Elia, which searchs the initial vector for a cyclic group in order to achieve the best minimum distance, we also present the best cyclic group codes in dimension four up to 100 points / Doutorado / Matematica / Doutor em Matemática

La théorie de l'homologie formalise la notion de trou dans un espace. Pour un sous-ensemble de l'espace Euclidien, on définit une séquence de groupes d'homologie, dont leurs rangs sont interprétés comme le nombre de trous de chaque dimension. Ces groupes sont calculables quand l'espace est décrit d'une façon combinatoire, comme c'est le cas pour les complexes simpliciaux ou cubiques. À partir d'un objet discret (un ensemble de pixels, voxels ou leur analogue en dimension supérieure) nous pouvons construire un complexe cubique et donc calculer ses groupes d'homologie.Cette thèse étudie trois approches relatives au calcul de l'homologie sur des objets discrets. En premier lieu, nous introduisons le champ de vecteurs discret homologique, une structure combinatoire généralisant les champs de vecteurs gradients discrets, qui permet de calculer les groupes d'homologie. Cette notion permet de voir la relation entre plusieurs méthodes existantes pour le calcul de l'homologie et révèle également des notions subtiles associés. Nous présentons ensuite un algorithme linéaire pour calculer les nombres de Betti dans un complexe cubique 3D, ce qui peut être utilisé pour les volumes binaires. Enfin, nous présentons deux mesures (l'épaisseur et l'ampleur) associés aux trous d'un objet discret, ce qui permet d'obtenir une signature topologique et géométrique plus intéressante que les simples nombres de Betti. Cette approche fournit aussi quelques heuristiques permettant de localiser les trous, d'obtenir des générateurs d'homologie ou de cohomologie minimaux, d'ouvrir et de fermer les trous. / Homology theory formalizes the concept of hole in a space. For a given subspace of the Euclidean space, we define a sequence of homology groups, whose ranks are considered as the number of holes of each dimension. Hence, b0, the rank of the 0-dimensional homology group, is the number of connected components, b1 is the number of tunnels or handles and b2 is the number of cavities. These groups are computable when the space is described in a combinatorial way, as simplicial or cubical complexes are. Given a discrete object (a set of pixels, voxels or their analog in higher dimension) we can build a cubical complex and thus compute its homology groups.This thesis studies three approaches regarding the homology computation of discrete objects. First, we introduce the homological discrete vector field, a combinatorial structure which generalizes the discrete gradient vector field and allows to compute the homology groups. This notion allows to see the relation between different existing methods for computing homology. Next, we present a linear algorithm for computing the Betti numbers of a 3D cubical complex, which can be used for binary volumes. Finally, we introduce two measures (the thickness and the breadth) associated to the holes in a discrete object, which provide a topological and geometric signature more interesting than only the Betti numbers. This approach provides also some heuristics for localizing holes, obtaining minimal homology or cohomology generators, opening and closing holes.

Dans ce travail de thèse , je présente comment extraire les géométries discrètes de l'espace-temps de la formulation covariante de la gravitaté quantique à boucles, qui est appelé le formalisme de la mousse de spin. LQG est une théorie quantique de la gravité qui non-perturbativement quantifie la relativité générale indépendante d'un fond fixe. Il prédit que la géométrie de l'espace est quantifiée, dans lequel l'aire et le volume ne peuvent prendre que la valeur discrète. L'espace de Hilbert cinématique est engendré par les fonctions du réseau de spin. L'excitation de la géométrie peut être parfaitement visualisée comme des polyèdres floue qui collées à travers leurs facettes. La mousse de spin définit la dynamique de la LQG par une amplitude de la mousse de spin sur un complexe cellulaire avec un état du réseau de spin comme la frontiére. Cette thèse présente deux résultats principaux. Premièrement, la limite semi-classique de l'amplitude de la mousse de spin sur un complexe simplicial arbitraire avec une frontière est complètement étudiée. La géométrie discrète classique de l'espace-temps est reconstruite et classée par les configurations critiques de l'amplitude de la mousse de spin. Deuxièmement, la fonction de trois-point de LQG est calculé. Il coïncide avec le résultat de la gravité discrète. Troisièmement, la description des géométries discrètes de hypersurfaces nulles est explorée dans le cadre de la LQG. En particulier, la géométrie nulle est décrit par une structure singulière euclidienne sur la surface de type espace à deux dimensions définie par un feuilletage de l'espace-temps par hypersurfaces nulles. / In this thesis, I will present how to extract discrete geometries of space-time fromthe covariant formulation of loop quantum gravity (LQG), which is called the spinfoam formalism. LQG is a quantum theory of gravity that non-perturbative quantizesgeneral relativity independent from a fix background. It predicts that the geometryof space is quantized, in which area and volume can only take discrete value. Thekinematical Hilbert space is spanned by Penrose's spin network functions. The excita-tion of geometry can be neatly visualized as fuzzy polyhedra that glued through theirfacets. The spin foam defines the dynamics of LQG by a spin foam amplitude on acellular complex, bounded by the spin network states. There are three main results inthis thesis. First, the semiclassical limit of the spin foam amplitude on an arbitrarysimplicial cellular complex with boundary is studied completely. The classical discretegeometry of space-time is reconstructed and classified by the critical configurations ofthe spin foam amplitude. Second, the three-point function from LQG is calculated.It coincides with the results from discrete gravity. Third, the description of discretegeometries of null hypersurfaces is explored in the context of LQG. In particular, thenull geometry is described by a Euclidean singular structure on the two-dimensionalspacelike surface defined by a foliation of space-time by null hypersurfaces. Its quan-tization is U(1) spin network states which are embedded nontrivially in the unitaryirreducible representations of the Lorentz group.

Les travaux effectués durant cette thèse portent sur l’appariement de formes planes basé sur une squelettisation hiérarchique. Dans un premier temps, nous avons abordé la création d’un squelette de forme grâce à un algorithme associant des outils de la géométrie discrète et des filtres. Cette association permet d’acquérir un squelette regroupant les propriétés désirées dans le cadre de l’appariement. Néanmoins, le squelette obtenu reste une représentation de la forme ne différenciant pas les branches représentant l’allure générale de celles représentant un détail de la forme. Or, lors de l’appariement, il semble plus intéressant d’associer des branches ayant le même ordre d’importance, mais aussi de donner plus de poids aux associations décrivant un aspect global des formes. Notre deuxième contribution porte sur la résolution de ce problème. Elle concerne donc la hiérarchisation des branches du squelette, précédemment créé, en leur attribuant une pondération reflétant leur importance dans la forme. À cet effet, nous lissons progressivement une forme et étudions la persistance des branches pour leur attribuer un poids. L’ultime étape consiste donc à apparier les formes grâce à leur squelette hiérarchique modélisé par un hypergraphe. En d’autres termes, nous associons les branches deux à deux pour déterminer une mesure de dissimilarité entre deux formes. Pour ce faire, nous prenons en compte la géométrie des formes, la position relative des différentes parties des formes ainsi que de leur importance. / The works performed during this thesis focuses on the matching of planar shapes based on a hierarchical skeletonisation. First, we approached the creation of a shape skeleton using an algorithm combining the tools of discrete geometry and filters. This combination allows to acquire a skeleton gathering the desired properties in the context of matching. Nevertheless, the resulting skeleton remains a representation of the shape, which does not differentiate branches representing the general shape of those coming from a detail of the shape. But when matching, it seems more interesting to pair branches of the same order of importance, but also to give more weight to associations describing an overall appearance of shapes. Our second contribution focuses on solving this problem. It concerns the prioritization of skeletal branches, previously created by assigning a weight reflecting their importance in shape. To this end, we gradually smooth a shape and study the persistence of branches to assign a weight. The final step is to match the shapes with their hierarchical skeleton modeled as a hypergraph. In other words, we associate the branches two by two to determine a dissimilarity measure between two shapes. To do this, we take into account the geometry of the shapes, the relative position of different parts of the shapes and their importance.

L'étude non destructive du bois à partir de scanners à rayons X nécessite d’imaginer de nouvelles solutions adaptées à l'analyse des images. Préoccupation à la fois de la recherche agronomique et du milieu industriel des scieries, la segmentation des nœuds de bois est un défi majeur en termes de robustesse aux spécificités de chaque espèce et aux conditions d'acquisition des images. Les travaux menés dans cette thèse permettent de proposer un processus de segmentation en deux phases. Il isole d'abord chaque nœud dans une zone réduite puis segmente le nœud unique de chaque zone. Les solutions proposées pour chaque phase permettent d'intégrer les connaissances sur l'organisation interne du tronc et les mécanismes inhérents à sa croissance, à travers des outils classiques du traitement et de l'analyse d'image. La première phase repose en grande partie sur un principe de détection du mouvement emprunté à l'analyse vidéo et revisité. Deux approches de segmentation sont ensuite proposées, considérant pour l'une les coupes tomographiques initiales, et pour l'autre de nouvelles coupes ré-échantillonnées pour chaque nœud, orthogonalement à sa trajectoire. L'intégralité du processus a été implémenté dans un logiciel dédié aussi bien à l'expérimentation et la validation de l'approche qu'aux échanges interdisciplinaires. Le support applicatif du bois souligne la capacité de spécialisation des algorithmes génériques du traitement et de l'analyse d'image, et la pertinence de l'intégration de connaissances a priori dans cette optique / The non-destructive study of wood from X-Ray CT scanners requires to imagine new solutions adapted to analysis of images. Relating both agronomic research and industrial sector of sawmills, segmentation of wood knots is a major challenge in terms of robustness to specificities of each species and to image acquisition conditions. The works carried out in this thesis allow to propose a segmentation process in two phases. It first isolates each knot in a reduced area then it segments the unique knot of each area. Proposed solutions for each phase allow to integrate knowledges about internal organization of trunk and mechanisms inherent to its growth, through classical tools of image analysis and processing. The first phase is essentially based on a movement detection principle borrowed from video analysis and revisited. Two segmentation approaches are then proposed, considering for one the initial CT slices and for the other news slices resampled for each knot orthogonally to its trajectory. The complete process has been implemented in a software dedicated both for experimentation and validation of approach, and to interdisciplinary dialogs. The applicative support of wood emphasizes the specialization abilities of generic image analysis and processing algorithms, and the relevance to integrate priori knowledges in this perspective

La présence de spécularité sur un objet est un problème récurrent qui limite l'application de nombreuses méthodes de segmentation. En effet, les spécularités sont des zones ayant une intensité très élevée et perturbent énormément la détection dès lors que l'on utilise la notion de gradient de l'image. Les travaux menés dans cette thèse permettent de proposer une nouvelle méthode de détection d'un objet tubulaire métallique dans une image. La méthode s'affranchit de la notion de gradient en utilisant la notion de profil d'intensité. Nous proposons dans ce manuscrit, un processus qui parcourt des zones rectangulaires prédéfinies de l'image, par balayage d'un segment discret à la recherche d'un profil d'intensité référence. Ces travaux s'inscrivent dans une collaboration avec Numalliance, une entreprise qui fabrique des machines-outils. Cette collaboration permet de mettre en pratique cette méthode dans le cadre d'un système de contrôle qualité automatique et temps-réel des pièces manufacturées par les machines-outils. Pour cela, la méthode présentée doit être rapide, robuste aux spécularités et à l'environnement industriel tout en étant suffisamment précise pour permettre de conclure sur la conformité ou non de la pièce / The presence of specularity on an object is a recurring problem that limits the application of many segmentation methods. Indeed, specularities are areas with a very high intensity and greatly disturb the detection when the notion of gradient of the image is used. The work carried out in this thesis makes it possible to propose a new detection method for a metallic tubular object in an image. The method avoids the notion of gradient by using the notion of intensity profile. We propose in this manuscript a process which traverses predefined rectangular areas of the image by scanning a discrete segment in search of a reference intensity profile. This work is part of a collaboration with Numalliance, a company that manufactures machine tools. This collaboration enables this method to be put into a real industrial application as part of an automatic and real-time quality control system for parts manufactured by machine tools. To this end, the method presented must be fast, robust to the specularities and to the industrial environment while being sufficiently precise to make it possible to conclude on the conformity or not of the part

<p>This PhD thesis, consisting of an introduction, four papers, and some supplementary results, studies the problem of finding an <i>optimal realization</i> of a given finite metric space: a weighted graph which preserves the metric's distances and has minimal total edge weight. This problem is known to be NP-hard, and solutions are not necessarily unique.</p><p>It has been conjectured that <i>extremally weighted</i> optimal realizations may be found as subgraphs of the <i>hereditarily optimal realization</i> Γ_d, a graph which in general has a higher total edge weight than the optimal realization but has the advantages of being unique, and possible to construct explicitly via the <i>tight span</i> of the metric.</p><p>In Paper I, we prove that the graph Γ_d is equivalent to the 1-skeleton of the tight span precisely when the metric considered is <i>totally split-decomposable</i>. For the subset of totally split-decomposable metrics known as <i>consistent</i> metrics this implies that Γ_d is isomorphic to the easily constructed <i>Buneman graph</i>.</p><p>In Paper II, we show that for any metric on at most five points, any optimal realization can be found as a subgraph of Γ_d.</p><p>In Paper III we provide a series of counterexamples; metrics for which there exist extremally weighted optimal realizations which are not subgraphs of Γ_d. However, for these examples there also exists at least one optimal realization which is a subgraph.</p><p>Finally, Paper IV examines a weakened conjecture suggested by the above counterexamples: can we always find some optimal realization as a subgraph in Γ_d? Defining <i>extremal</i> optimal realizations as those having the maximum possible number of shortest paths, we prove that any embedding of the vertices of an extremal optimal realization into Γ_d is injective. Moreover, we prove that this weakened conjecture holds for the subset of consistent metrics which have a 2-dimensional tight span</p>

This PhD thesis, consisting of an introduction, four papers, and some supplementary results, studies the problem of finding an optimal realization of a given finite metric space: a weighted graph which preserves the metric's distances and has minimal total edge weight. This problem is known to be NP-hard, and solutions are not necessarily unique. It has been conjectured that extremally weighted optimal realizations may be found as subgraphs of the hereditarily optimal realization Γd, a graph which in general has a higher total edge weight than the optimal realization but has the advantages of being unique, and possible to construct explicitly via the tight span of the metric. In Paper I, we prove that the graph Γd is equivalent to the 1-skeleton of the tight span precisely when the metric considered is totally split-decomposable. For the subset of totally split-decomposable metrics known as consistent metrics this implies that Γd is isomorphic to the easily constructed Buneman graph. In Paper II, we show that for any metric on at most five points, any optimal realization can be found as a subgraph of Γd. In Paper III we provide a series of counterexamples; metrics for which there exist extremally weighted optimal realizations which are not subgraphs of Γd. However, for these examples there also exists at least one optimal realization which is a subgraph. Finally, Paper IV examines a weakened conjecture suggested by the above counterexamples: can we always find some optimal realization as a subgraph in Γd? Defining extremal optimal realizations as those having the maximum possible number of shortest paths, we prove that any embedding of the vertices of an extremal optimal realization into Γd is injective. Moreover, we prove that this weakened conjecture holds for the subset of consistent metrics which have a 2-dimensional tight span

Orientadores: Sueli Irene Rodrigues Costa, Jose Plinio de Oliveira Santos / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-13T23:35:30Z (GMT). No. of bitstreams: 1 Torezzan_Cristiano_D.pdf: 2362096 bytes, checksum: 1680bc5fc7cb94a63b0b11b50ac5a1c4 (MD5) Previous issue date: 2009 / Resumo: Códigos esféricos em espaços euclidianos n-dimensionais são conjuntos finitos de pontos sobre superfícies esféricas e têm sido amplamente estudados em conexão com a transmissão de sinais sobre um canal Gaussiano. Para este propósito deseja-se maximizar a distância mínima entre dois pontos quaisquer do código, o que está fortemente relacionado com o problema mais geral do empacotamento em esferas, o qual contempla aplicações em outras áreas. Na primeira parte deste trabalho estudamos códigos esféricos gerados como órbita de um vetor unitário sob a ação de um grupo comutativo de matrizes ortogonais, os denominados códigos de grupo comutativo. Propomos um método para obter o melhor código de grupo comutativo n-dimensional de ordem M, que baseia-se na associação entre tais códigos em dimensão 2k e reticulados k-dimensionais. Utilizando fatorações matriciais conhecidas, como as formas normais de Hermite e Smith, demonstramos que é possível reduzir o número de casos a serem analisados através da identificação de códigos isométricos que podem ser descartados. O problema da busca do vetor inicial ótimo para códigos de grupo comutativo é formalmente estabelecido com um problema de programação linear e utilizado em uma das etapas do método. Apresentamos resultados numéricos, incluindo tabelas com códigos de grupo comutativo ótimos em várias dimensões. Outra contribuição deste trabalho é a introdução de uma nova família de códigos esféricos, na qual os pontos são alocados sobre a superfície da esfera unitária 2k-dimensional em camadas de toros planares. Em cada uma das camadas deste código, pode-se estabelecer um código de grupo para a geração dos sinais e utilizar os resultados acima mencionados. Além de limitantes, inferior e superior, para o número de pontos, um método para construção destes códigos é apresentado explicitamente e alguns exemplos são construídos. Os resultados mostram que tais códigos têm desempenho comparável aos melhores códigos esféricos estruturados conhecidos, com destaque para uma potencial vantagem no processo de codificação/decodificação, decorrente da homogeneidade, estrutura de grupo e associação a reticulados na metade da dimensão / Abstract: Spherical codes in Euclidean spaces are finite sets of points on the surface of a multidimensional sphere and have been widely studied in connection with the signal transmission over a Gaussian channel. For this purpose one fundamental issue is to maximize the minimum distance between two code points, what is strongly related to the more general problem of sphere packing. In the first part of this work we study spherical codes generated as orbit of a initial vector under the action of a commutative group of orthogonal matrices, the so called commutative group codes. A method for searching the best n-dimensional commutative group code of order M is presented. Based on the well known Hermite and Smith normal form decomposition of matrices, and also on the relation between 2k-dimensional com- mutative group codes and k-dimensional lattices, we show that it is possible to reduce the number of cases to be analyzed through the identification of isometric codes which can be discarded. The initial vector problem for these codes is formally established as a linear programming problem and used as a sub-routine of the method. Numerical results are presented, including tables of good commutative groups codes in several dimensions. Other contribution of this work is a new class of spherical codes, constructed by placing points on flat tori layers. The codebook on each torus can be generated by a commutative group of orthogonal matrices, using the results previously mentioned. Upper and lower bounds on performance are derived and a systematic method for constructing the codes is presented. Some examples are constructed and the results exhibit good performance when compared to the best known structured spherical codes, with some advantage in the encoding/decoding process, due to the homogeneity, group structure and the relation with lattices in the half of the dimension / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada