Le développement fulgurant de réseaux informatiques, a entraîné l'apparition de diverses applications multimédia qui emploient des données 3D dans des multiples contextes. Si la majorité des travaux de recherche sur ces données s'est appuyées sur les modèles statiques, c'est à présent vers Les modèles dynamiques de maillages qu'il faut se tourner. Cependant, le maillage triangulaire est une représentation extrinsèque, sensible face aux différentes transformations affines et isométriques. Par conséquent, il a besoin d'un descripteur structurel intrinsèque. Pour relever ces défis, nous nous concentrons sur la modélisation topologique intrinsèque basée sur les graphes de Reeb. Notre principale contribution consiste à définir une nouvelle fonction continue basée sur les propriétés de diffusion de la chaleur. Ce dernier est calculé comme la distance de diffusion d'un point de la surface aux points localisés aux extrémités du modèle 3D qui représentent l'extremum locales de l'objet . Cette approche de construction de graph de Reeb peut être extrêmement utile comme descripteur de forme locale pour la reconnaissance de forme 3D. Il peut également être introduit dans un système de compression dynamique basée sur la segmentation.Dans une deuxième partie, nous avons proposé d'exploiter la méthode de construction de graphe de Reeb dans un système de reconnaissance de formes 3D non rigides. L'objectif consiste à segmenter le graphe de Reeb en cartes de Reeb définis comme cartes de topologie contrôlée. Chaque carte de Reeb est projetée vers le domaine planaire canonique. Ce dépliage dans le domaine planaire canonique introduit des distorsions d'aire et d'angle. En se basant sur une estimation de distorsion, l'extraction de vecteur caractéristique est effectuée. Nous calculons pour chaque carte un couple de signatures, qui sera utilisé par la suite pour faire l'appariement entre les cartes de Reeb.Dans une troisième partie, nous avons proposé de concevoir une technique de segmentation, des maillages dynamiques 3D. Le processus de segmentation est effectué en fonction des valeurs de la fonction scalaire proposée dans la première partie. Le principe consiste à dériver une segmentation purement topologique qui vise à partitionner le maillage en des régions rigides tout en estimant le mouvement de chaque région au cours du temps. Pour obtenir une bonne répartition des sommets situés sur les frontières des régions, nous avons proposé d'ajouter une étape de raffinement basée sur l'information de la courbure. Chaque limite de région est associée à une valeur de la fonction qui correspond à un point critique. L'objectif visé est de trouver la valeur optimale de cette fonction qui détermine le profil des limites. La technique de segmentation développée est exploitée dans un système de compression sans perte des maillages dynamiques 3D. Il s'agit de partitionner la première trame de la séquence. Chaque région est modélisée par une transformée affine et leurs poids d'animation associés. Le vecteur partition, associant à chaque sommet l'index de la région auquel il appartient, est compressé par un codeur arithmétique. Les deux ensembles des transformées affines et des poids d'animation sont quantifiés uniformément et compressés par un codeur arithmétique. La première trame de la séquence est compressée en appliquant un codeur de maillage statique. L a quantification de l'erreur de prédiction temporelle est optimisée en minimisant l'erreur de reconstruction. Ce processus est effectué sur les données de l'erreur de prédiction, qui est divisé en 3 sous-bandes correspondant aux erreurs de prédiction des 3 coordonnées x, y et z. Le taux de distorsion introduit est déterminé en calculant le pas de quantification, pour chaque sous-bande, afin d'atteindre le débit binaire cible. / In the last decade, the technological progress in telecommunication, hardware design and multimedia, allows access to an ever finer three-dimensional (3-D) modeling of the world. While most researchers have focused on the field of 3D objects, now it is necessary to turn to 3D time domain (3D+t). 3D dynamic meshes are becoming a media of increasing importance. This 3D content is subject to various processing operations such as indexation, segmentation or compression. However, surface mesh is an extrinsic shape representation. Therefore, it suffers from important variability under different sampling strategies and canonical shape-non-altering surface transformations, such as affine or isometric transformations. Consequently it needs an intrinsic structural descriptor before being processed by one of the aforementioned processing operations. The research topic of this thesis work is the topological modeling based on Reeb graphs. Specifically, we focus on 3D shapes represented by triangulated surfaces. Our objective is to propose a new approach, of Reeb graph construction, which exploits the temporal information. The main contribution consists in defining a new continuous function based on the heat diffusion properties. The latter is computed from the discrete representation of the shape to obtain a topological structure.The restriction of the heat kernel to temporal domain makes the proposed function intrinsic and stable against transformation. Due to the presence of neighborhood information in the heat kernel, the proposed Reeb Graph construction approach can be extremely useful as local shape descriptor for non-rigid shape retrieval. It can also be introduced into a segmentation-based dynamic compression scheme in order to infer the functional parts of a 3D shape by decomposing it into parts of uniform motion. In this context, we apply the concept of Reeb graph in two widely used applications which are pattern recognition and compression.Reeb graph has been known as an interesting candidate for 3D shape intrinsic structural representation. we propose a 3D non rigid shape recognition approach. The main contribution consists in defining a new scalar function to construct the Reeb graph. This function is computed based on the diffusion distance. For matching purpose, the constructed Reeb graph is segmented into Reeb charts, which are associated with a couple of geometrical signatures. The matching between two Reeb charts is performed based on the distances between their corresponding signatures. As a result, the global similarity is estimated based on the minimum distance between Reeb chart pairs. Skeletonisation and segmentation tasks are closely related. Mesh segmentation can be formulated as graph clustering. First we propose an implicit segmentation method which consists in partitioning mesh sequences, with constant connectivity, based on the Reeb graph construction method. Regions are separated according to the values of the proposed continuous function while adding a refinement step based on curvature and boundary information.Intrinsic mesh surface segmentation has been studied in the field of computer vision, especially for compression and simplification purposes. Therefore we present a segmentation-based compression scheme for animated sequences of meshes with constant connectivity. The proposed method exploits the temporal coherence of the geometry component by using the heat diffusion properties during the segmentation process. The motion of the resulting regions is accurately described by 3D affine transforms. These transforms are computed at the first frame to match the subsequent ones. In order to improve the performance of our coding scheme, the quantization of temporal prediction errors is optimized by using a bit allocation procedure. The objective aimed at is to control the compression rate while minimizing the reconstruction error.

Es werden spektrale Eigenschaften des zweidimensionalen Schrödinger-Operators mit einem zweifach periodischen Potential und starkem magnetischem Feld untersucht mit Hilfe semiklassischer Methoden. Man beschreibt die spektrale Asymptotik durch Benutzung der Reeb-Graph-Technik. Im Falle des rationalen Flusses konstruiert man semiklassische Magneto-Bloch-Funktionen und beschreibt die Asymptotik des Spektrums auf dem physikalischen Beweisniveau. / Spectral properties of the two-dimensional Schroedinger operator with a two-periodic potential and a strong uniform magnetic field is studied with the help of semiclassical methods. The spectral asymptotics is described using the Reeb graph technique. In the case of the rational flux one constructs semiclassical magneto-Bloch functions and describes the asymptotics of the band spectrum on the physical level of proof.

<p>This thesis is concerned with a structure called the Reeb graph. There are three main problems considered. The first is devising an efficient algorithm for comnstructing the Reeb graph of a simplicial complex with respect to a generic simplex-wise linear real-valued function. We present an algorithm that builds the Reeb graph in almost optimal worst-case deterministic time. This was the first deterministic algorithm with the time bound which is linear up to a logarithmic factor. Without loss of generality, the complex is assumed to be 2-dimensional. The algorithm works by sweeping the function values and maintaining a spanning forest for the preimage, or the level-set, of the value. Using the observation that the operations that change the level-sets are off-line, we was able to achieve the above bound.</p><p>The second topic is the dynamic Reeb graphs. As the function changes its values, the Reeb graph also changes. We are interested in updating the Reeb graph. We reduce this problem to a graph problem that we call retroactive graph connectivity. We obtain algorithms for dynamic Reeb graphs, by using data structures that solve the graph problem. </p><p>The third topic is an argument regarding the complexity of computing Betti numbers. This problem is also related to the Reeb graph by means of the vertical Homology classes. The problem considered here is whether the realization of a simplicial complex in the Euclidean 4-space can result in an algorithm for computing its Homology groups faster than the usual matrix reduction methods. Using the observation that the vertical Betti numbers can always be computed more efficiently using the Reeb graph, we show that the answer to this question is in general negative. For instance, given a square matrix over the field with two elements, we construct a simplicial complex in linear time, realized in euclidean 4-space and a function on it, such that its Horizontal homology group, over the same field, is isomorphic with the null-space of the matrix. It follows that the Betti number computation for complexes realized in the 4-space is as hard as computing the rank for a sparse matrix.</p> / Dissertation

En ce moment même, d'énormes quantités de données sont générées, collectées et analysées. Dans de nombreux cas, ces données sont échantillonnées sur des objets à la structure géométrique particulière. De tels objets apparaissent fréquemment dans notre vie quotidienne. Utiliser ce genre de données pour inférer la structure géométrique de tels objets est souvent ardue. Cette tâche est rendue plus difficile encore si les objets sous-jacents sont abstraits ou encore de grande dimension. Dans cette thèse, nous nous intéressons à deux problèmes concernant l'analyse géométrique de données. Dans un premier temps, nous nous penchons sur l'inférence de la métrique de structures filamentaires. En supposant que ces structures sont des espaces métriques proches d'un graphe métrique nous proposons une méthode, combinant les graphes de Reeb et l'algorithme Mapper, pour approximer la structure filamentaire via un graphe de Reeb. Notre méthode peut de plus être facilement implémentée et permet de visualiser simplement le résultat. Nous nous concentrons ensuite sur le problème de la comparaison de formes. Nous étudions un ensemble de méthodes récentes et prometteuses pour la comparaison de formes qui utilisent la notion de carte fonctionnelles. Nos résultats théoriques montrent que ces approches sont stables et peuvent être utilisées dans un contexte plus général que la comparaison de formes comme la comparaison de variétés Riemanniennes de grande dimension. Enfin, en nous basant sur notre analyse théorique, nous proposons une généralisation des cartes fonctionnelles aux nuages de points. Bien que cette généralisation ne bénéficie par des garanties théoriques, elle permet d'étendre le champ d'application des méthodes basées sur les cartes fonctionnelles. / Massive amounts of data are being generated, collected and processed all the time. A considerable portion of them are sampled from objects with geometric structures. Such objects can be tangible and ubiquitous in our daily life. Inferring the geometric information from such data, however, is not always an obvious task. Moreover, it’s not a rare case that the underlying objects are abstract and of high dimension, where the data inference is more challenging. This thesis studies two problems on geometric data analysis. The first one concerns metric reconstruction for filamentary structures. We in general consider a filamentary structure as a metric space being close to an underlying metric graph, which is not necessarily embedded in some Euclidean spaces. Particularly, by combining the Reeb graph and the Mapper algorithm, we propose a variant of the Reeb graph, which not only faithfully approximates the metric of the filamentary structure but also allows for efficient implementation and convenient visualization of the result. Then we focus on the problem of shape comparison. In this part, we study the stability properties of some recent and promising approaches for shape comparison, which are based on the notion of functional maps. Our results show that these approaches are stable in theory and potential for being used in more general setting such as comparing high-dimensional Riemannian manifolds. Lastly, we propose a pipeline for implementing the functional-maps-based frameworks under our stability analysis on unorganised point cloud data. Though our pipeline is experimental, it undoubtedly extends the range of applications of these frameworks.

Cette thèse présente une méthode de segmentation de modèles 3D en parties significatives ou fonctionnelles. La segmentation s’effectue par "transfert" d’une segmentation exemple : la segmentation d’un modèle est calculée en transférant les segments d’une segmentation exemple d’un objet appartenant à la même classe de modèles 3D. Pour ce faire, nous avons adapté et étendu la méthode de segmentation par les marches aléatoires et transformé notre problème en un problème de localisation et mise en correspondance de faces germes. Notre méthode comporte quatre étapes fondamentales : la mise en correspondance entre le modèle exemple et le modèle cible, la localisation automatique de germes sur le modèle cible pour initialiser les régions, le calcul des segments du modèle cible et l’amélioration de leurs frontières. En constatant que les critères de similarité diffèrent selon que les objets sont de type rigide (chaises, avions,…) ou de type articulé (humains, quadrupèdes,…), nous décomposons notre approche en deux. La première dédiée aux objets rigides, où la mise en correspondance est basée sur le calcul des transformations rigides afin d’aligner au mieux les parties significatives des deux objets comparés. La deuxième dédiée aux modèles articulés, où la mise en correspondance des parties fonctionnelles, présentant des variations de poses plus importantes, est basée sur des squelettes calculés via des diagrammes de Reeb. Nous montrons à travers des évaluations qualitatives et quantitatives que notre méthode obtient des résultats meilleurs que les techniques de segmentation individuelle et comparables aux techniques de co-segmentation avec un temps de calcul nettement inférieur. / In this dissertation, we present a new method to segment 3D models into their functional parts. The segmentation is performed by a transfer approach: a semantic-oriented segmentation of an object is calculated using a pre-segmented example model from the same class (chairs, humans, etc.). To this end, we adapted and extended the random walk segmentation method which allowed us to transform our problem into a problem of locating and matching seed faces. Our method consists of four fundamental steps: establishing correspondences between the example and the target model, localizing seeds to initialize regions in the target model, computing the segments and refining their boundaries in the target model. We decomposed our approach in two, taking into account similarity criteria which differ regarding the object type (rigid vs. articulated). The first approach is dedicated to rigid objects (chairs, airplanes, etc.), where the matching is based on rigid transformations to determine the best alignment between the functional parts of the compared objects. The second one focused on articulated objects (humans, quadrupeds, etc.), where coarse topological shape attributes are used in a skeleton-based approach to cover larger pose variations when computing correspondences between functional parts. We show through qualitative and quantitative evaluations that our method improves upon individual segmentation techniques and obtains results that are close to the co-segmentation techniques results with an important calculation time reduction.

No description available.

Bartsch (BARTSCH, 1993) introduziu uma teoria de índice cohomológico, conhecida como o length, para G-espaços, no qual G é um grupo de Lie compacto. Apresentamos o cálculo do length de G-espaços os quais são esferas de cohomologia e G = (Z2)k, (Zp)k ou (S1)k, k &ge; 1. Como consequências, obtemos um teorema de Borsuk-Ulam neste contexto e damos condições suficientes para a existência de aplicações G-equivariantes entre uma esfera de cohomologia e uma esfera de representação quando G = (Zp)<sup<k. Também, uma versão Bourgin-Yang do teorema de Borsuk-Ulam é apresentada. Como segunda parte desta tese, uma nova definição do grafo de Reeb R( f) de uma função suave f : MR com pontos críticos isolados, como um subcomplexo de M é dada. Para isto, um complexo 1-dimensional &Gamma; (f ) mergulhado em M e equivalente por homotopia a R( f ) é construído. Como consequência, mostramos que para toda função f sobre uma variedade com grupo fundamental finito, o grafo de Reeb de f é uma árvore. Se &pi;1(M) é um grupo abeliano, ou mais geralmente, um grupo amenable1, então R( f ) conterá no máximo um laço. Finalmente, é provado que o número de laços do grafo de Reeb de toda função sobre uma superfície Mg é estimado superiormente por g, o genus de Mg. Os resultados desta segunda parte estão publicados em (KALUBA; MARZANTOWICZ; SILVA, 2015). / Bartsch (BARTSCH, 1993) introduced a numerical cohomological index theory, known as the length, for G-spaces, where G is a compact Lie group. We present the length of G-spaces which are cohomology spheres and G = (Z2)k, (Zp)k or (S1)k, k &ge; 1. As consequences, we obtain a Borsuk-Ulam theorem in this context and we give a sucient condition for the existence of G-maps between a cohomological sphere and a representation sphere when G = (Zp)k. Also, a Bourgin-Yang version of the Borsuk-Ulam theorem is presented. As a second part of this thesis, a new definition of the Reeb graph R( f ) of a smooth function f : M &rarr; R with isolated critical points as a subcomplex of M is given. For that, a 1-dimensional complex &Gamma; ( f ) embedded into M and homotopy equivalent to R( f ) is constructed. As consequence it is shown that for every function f on a manifold with finite fundamental group, the Reeb graph of f is a tree. If &pi; 1 (M) is an abelian group, or more generally, an amenable group2, then R( f ) contais at most one loop. Finally, it is proved that the number of loops of the Reeb graph of every function on a surface Mg is estimated from above by g, the genus of Mg. The results of this second part is published in (KALUBA; MARZANTOWICZ; SILVA, 2015).

Bartsch (BARTSCH, 1993) introduziu uma teoria de índice cohomológico, conhecida como o length, para G-espaços, no qual G é um grupo de Lie compacto. Apresentamos o cálculo do length de G-espaços os quais são esferas de cohomologia e G = (Z2)k, (Zp)k ou (S1)k, k &ge; 1. Como consequências, obtemos um teorema de Borsuk-Ulam neste contexto e damos condições suficientes para a existência de aplicações G-equivariantes entre uma esfera de cohomologia e uma esfera de representação quando G = (Zp)<sup<k. Também, uma versão Bourgin-Yang do teorema de Borsuk-Ulam é apresentada. Como segunda parte desta tese, uma nova definição do grafo de Reeb R( f) de uma função suave f : MR com pontos críticos isolados, como um subcomplexo de M é dada. Para isto, um complexo 1-dimensional &Gamma; (f ) mergulhado em M e equivalente por homotopia a R( f ) é construído. Como consequência, mostramos que para toda função f sobre uma variedade com grupo fundamental finito, o grafo de Reeb de f é uma árvore. Se &pi;1(M) é um grupo abeliano, ou mais geralmente, um grupo amenable1, então R( f ) conterá no máximo um laço. Finalmente, é provado que o número de laços do grafo de Reeb de toda função sobre uma superfície Mg é estimado superiormente por g, o genus de Mg. Os resultados desta segunda parte estão publicados em (KALUBA; MARZANTOWICZ; SILVA, 2015). / Bartsch (BARTSCH, 1993) introduced a numerical cohomological index theory, known as the length, for G-spaces, where G is a compact Lie group. We present the length of G-spaces which are cohomology spheres and G = (Z2)k, (Zp)k or (S1)k, k &ge; 1. As consequences, we obtain a Borsuk-Ulam theorem in this context and we give a sucient condition for the existence of G-maps between a cohomological sphere and a representation sphere when G = (Zp)k. Also, a Bourgin-Yang version of the Borsuk-Ulam theorem is presented. As a second part of this thesis, a new definition of the Reeb graph R( f ) of a smooth function f : M &rarr; R with isolated critical points as a subcomplex of M is given. For that, a 1-dimensional complex &Gamma; ( f ) embedded into M and homotopy equivalent to R( f ) is constructed. As consequence it is shown that for every function f on a manifold with finite fundamental group, the Reeb graph of f is a tree. If &pi; 1 (M) is an abelian group, or more generally, an amenable group2, then R( f ) contais at most one loop. Finally, it is proved that the number of loops of the Reeb graph of every function on a surface Mg is estimated from above by g, the genus of Mg. The results of this second part is published in (KALUBA; MARZANTOWICZ; SILVA, 2015).

No description available.

Nesta tese estudamos os sistemas integráveis definidos em superfícies compactas possuindo uma integral primeira que é uma função Morse-Bott a valores em R. Estes sistemas são aqui chamados de sistemas integráveis Morse-Bott. Classificamos as curvas fechadas e oitos associados a pontos de selas imersos em superfícies compactas. Essa classificação é aplicada ao estudo das folheações Morse-Bott em superfícies e nos permite definir um invariante topológico completo para a classificação topológica global destas folheações. Como uma aplicação desse estudo obtemos a classificação dos sistemas Morse-Bott assim como a classificação topológica das funções Morse-Bott em superfícies compactas e orientáveis. Demonstramos ainda um teorema da realização baseado em duas transformações e numa folheação geradora. Para o caso das funções Morse-Bott também obtivemos um teorema de realização. Finalmente, investigamos a generalização de alguns dos resultados anteriores para sistemas definidos em superfícies não orientáveis. / In this thesis we study integrable systems on compact surfaces with a first integral as a Morse-Bott function with target R. These systems are called here integrable Morse-Bott systems. Initially we present the classification of closed curves and eights associated to saddle points on compact surfaces. This classification is applied to the study of Morse- Bott foliations on surfaces allowing us to define a complete topological invariant for the global topological classification of these foliations. Then as an application of this study we obtain the classification of integrable Morse-Bott systems as well as the topological classification of Morse-Bott functions on compact and orientable surfaces. We also prove a realization theorem based on two transformation and a generating foliation (the foliation on the sphere with two centers). In the case of Morse-Bott functions we also obtain a realization theorem. Finally we investigate generalizations of previous results for systems defined on non-orientable surfaces.