Дисертації з теми "Graph of discontinuous maps"

In this thesis we study the relaxation of the area functional w.r.t. the L^1 topology of a map from a bounded planar domain with values in the plane and jumping on a segment. We estimate from above the singular contribution of this functional due to the presence of the jump in terms of the infimum of the area among a suitable family of surfaces that we call semicartesian surfaces. In our analysis, we also introduce a different notion of area, namely the relaxation of the area w.r.t. a convergence stronger than the L^1 convergence, whose singular contribution is completely characterized in terms of suitable semicartesian area minimizing problems. We propose also some examples of maps for which the two notions of relaxation are different: these examples underline the highly non-local behaviour of the L^1-relaxation, and justify the introduction of the other functional. Some result about the existence of a semicartesian area-minimizing surface is also provided.

A 3-map is a 3-region colorable map. They have been studied by Craft and White in their paper 3-maps. This thesis introduces topological graph theory and then investigates 3-maps in detail, including examples, special types of 3-maps, the use of 3-maps to find the genus of special graphs, and a generalization known as n-maps.

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO
Reconstruir a informação 3D de uma cena é uma tarefa bastante comum em Visão Computacional. Uma das técnicas mais utilizadas para realizar esta tarefa é a correspondência por estéreo, que consiste basicamente em, dadas duas imagens referentes a uma mesma cena vista de pontos diferentes, determinar os pontos correspondentes entre essas duas imagens e armazenar essa informação em um mapa de disparidades. Até hoje diversos métodos foram propostos para resolver o problema de estéreo com esforço computacional viável e mantendo a qualidade dos resultados. Essa, entretanto, é uma tarefa bastante árdua e que difícilmente alcança resultados precisos com pouco esforço computacional. Nesse âmbito, uma técnica que tem sido muito estudada são os Cortes de Grafo (Graph Cuts), que almeja resolver o problema de minimização de energia em tempo polinomial. Nesse caso o problema de estéreo é mapeado como um problema de minimização de energia e desta forma solucionado utilizando cortes de grafo. Neste trabalho estudamos as técnicas de cortes de grafo mais recentes e eficientes e propomos um método para a determinação de correspondências entre duas imagens num contexto de multi-resolução, no qual uma pirâmide Gaussiana para as imagens é construída e a técnica de cortes de grafo é aplicada em níveis menores, otimizando a performance e obtendo resultados mais precisos através da utilização do algoritmo de expansão-alfa. São revisadas as técnicas de cortes de grafo e de multi-resolução e os resultados obtidos são apresentados e avaliados em relação a métodos semelhantes.
Reconstructing the 3D information of a scene is a common task in Computer Vision. Stereo matching is one of the most investigated techniques used to perform this task, which basically consists of, given two images of a scene seen from different view points, determining corresponding pixels in these two images and store this information in a disparity map. Several methods have been proposed to solve the stereo problem keeping good performance and giving good quality results. This is however a very arduos task which hardly achieves precise results with low computational power. In this context, the Graph Cuts method has been very much considered, which aims to solve the energy minimization problem in polinomial time. In this case the stereo problem can be modelled as an energy minimization problem and, thus solved using the Graph Cuts technique. In this work we investigate the most recent and efficient Graph Cuts methods and propose a method for establishing the correspondences between two images in the context of multi-resolution, in which a Gaussian pyramid for the input images is built and the Graph Cuts methods is applied in coarser levels, optimizing the performance and getting more precise results through the use of the alfa-expansion algorithm. The Graph Cuts and multi-resolution techniques are reviewed and the results of the proposed method are presented and evaluated compared to similar methods.

In this thesis we present the diffusion maps, a framework based on diffusion processes for finding meaningful geometric descriptions of data sets. A diffusion process can be described via an iterative application of the heat kernel which has two main characteristics: it satisfies a Markov semigroup property and its level sets encode all geometric features of the space. This process, well known in regular manifolds, has been extended to general data set by Coifman and Lafon. They define a diffusion kernel starting from the geometric properties of the data and their density properties. This kernel will be a compact operator, and the projection on its eigenvectors at different instant of time, provides a family of embeddings of a dataset into a suitable Euclidean space. The projection on the first eigenvectors, naturally leads to a dimensionality reduction algorithm. Numerical implementation is provided on different data set.

Discontinuous dynamical systems and multiagent systems are encountered in numerous engineering applications. This dissertation develops stability and dissipativity of nonlinear dynamical systems with discontinuous right-hand sides, optimality of discontinuous feed-back controllers for Filippov dynamical systems, almost consensus protocols for multiagent systems with innaccurate sensor measurements, and adaptive estimation algorithms using multiagent network identifiers. In particular, we present stability results for discontinuous dynamical systems using nonsmooth Lyapunov theory. Then, we develop a constructive feedback control law for discontinuous dynamical systems based on the existence of a nonsmooth control Lyapunov function de fined in the sense of generalized Clarke gradients and set-valued Lie derivatives. Furthermore, we develop dissipativity notions and extended Kalman-Yakubovich-Popov conditions and apply these results to develop feedback interconnection stability results for discontinuous systems. In addition, we derive guaranteed gain, sector, and disk margins for nonlinear optimal and inverse optimal discontinuous feedback regulators that minimize a nonlinear-nonquadratic performance functional for Filippov dynamical systems. Then, we provide connections between dissipativity and optimality of nonlinear discontinuous controllers for Filippov dynamical systems. Furthermore, we address the consensus problem for a group of agent robots with uncertain interagent measurement data, and show that the agents reach an almost consensus state and converge to a set centered at the centroid of agents initial locations. Finally, we develop an adaptive estimation framework predicated on multiagent network identifiers with undirected and directed graph topologies that identifies the system state and plant parameters online.

La tesi versa sobre sistemes dinàmics discrets 1-dimensionals, des d'un punt de vista combinatori i topològic. Estem interessats en les òrbites periòdiques i l'entropia topològica de les aplicacions contínues definides en arbres i grafs.
El problema central és la caracterització del conjunt de períodes de totes les òrbites periòdiques d'una aplicació contínua d'un arbre en ell mateix. El teorema de Sharkovskii (1964) fou el primer resultat remarcable en aquest sentit. Aquest bonic teorema estableix que el conjunt de períodes d'una aplicació de l'interval és un segment inicial d'un ordre lineal (ordre de Sharkovskii). Recíprocament, donat qualsevol segment inicial d'aquest ordre, existeix una aplicació de l'interval que el té com a conjunt de períodes.
Durant les darreres dècades hi ha hagut diversos intents de trobar resultats similars al de Sharkovskii per a altres espais 1-dimensionals. Recentment, el cas d'arbres ha estat tractat especialment. El Teorema de Baldwin (1991) resol el problema en el cas de les n-estrelles i ha estat un dels avenços més significatius en aquesta direcció. Aquest resultat estableix que el conjunt de períodes per a una aplicació de la n-estrella és unió finita de segments inicials de n ordres parcials (ordres de Baldwin), i recíprocament.
El nostre objectiu principal és descriure l'estructura del conjunt de períodes de qualsevol aplicació contínua d'un arbre T en termes de les propietats combinatòries i topològiques de T: quantitat i disposició d'extrems, vèrtexs i arestes. En el capítol 1 discutim detalladament la manera més natural d'atacar el problema, i proposem una estratègia consistent en tres etapes consecutives. L'eina principal d'aquesta estratègia són els models minimals de patrons. Aquestes nocions es van desenvolupar i utilitzar durant les darreres dècades en el context de l'interval. En canvi, no es disposava de definicions operatives equivalents per a arbres, fins que al 1997 Alseda, Guaschi, Los, Manyosas i Mumbru proposaren de definir el patró d'un conjunt finit invariant P essencialment com una classe d'homotopia d'aplicacions relativa a P, i provaren (constructivament) que sempre existeix un model P-canònic amb propietats de minimalitat dinàmica.
L'objectiu del capítol 2 és implementar completament el programa proposat, duent a terme les etapes 2 i 3. El resultat principal d'aquest capítol diu que, donada una aplicació g definida en un arbre T, existeix un conjunt S de successions finites d'enters positius tal que el conjunt de períodes de g és (excepte un conjunt finit explícitament acotat) una unió finita de segments inicials d'ordres de Baldwin donats en termes del conjunt S, que depèn de les propietats combinatòries de l'arbre T. També provem el recíproc.
En el capítol 3 duem a terme experiments informàtics sobre la minimalitat dinàmica dels models canònics. En un esperit de programació modular, hem dissenyat moltes funcions autocontingudes que poden ser usades per implementar una gran varietat d'aplicacions d'ús divers. Entre altres, tenim funcions que calculen el model canònic d'un patró donat per l'usuari, calculen la matriu de Markov associada a un model monòton a trossos i extreuen tots els llaços simples d'una matriu de transició de Markov.
Finalment, en el capítol 4 generalitzem alguns resultats de Block i Coven, Misiurewicz i Nitecki i Takahashi, en els quals l'entropia topològica d'una aplicació de l'interval s'aproxima per les entropies de les seves òrbites periòdiques. Hem provat relacions anàlogues en el context de les aplicacions de grafs.
This memoir deals with one-dimensional discrete dynamical systems, from both a topological and a combinatorial point of view. We are interested in the periodic orbits and topological entropy of continuous self-maps defined on trees and graphs.
The central problem is the characterisation of the set of periods of all periodic orbits exhibited by any continuous map from a tree into itself. The Sharkovskii's Theorem (1964) was the first remarkable result in this setting. This theorem states that the set of periods of any interval map is an initial segment of a linear ordering (the so-called Sharkovskii ordering). Conversely, given any initial segment of the Sharkovskii ordering, there exists an interval map whose set of periods coincides with it.
During the last decades there have been several attempts to find results similar to that of Sharkovskii for other one-dimensional spaces. Recently, the case of maps defined on general trees has been specially treated. Baldwin's Theorem (1991), which solves the problem in the case of n-stars for any n, has been one of the most significant advances in this direction. This result states that the set of periods of any n-star map is a finite union of initial segments of n-many partial orderings (the Baldwin orderings). The converse is also true.
Our main purpose is to describe the generic structure of the set of periods of any continuous self-map defined on a tree T in terms of the combinatorial and topological properties of T: amount and arrangement of endpoints, vertices and edges. In Chapter 1 we make a detailed discussion about which is the more natural approach to this problem, and we propose a strategy consisting on three consecutive stages and using minimal models of patterns as the main tool. These notions were developed in the context of interval maps and widely used in a number of papers during the last two decades. However, equivalent operative definitions for tree maps were not available until 1997, when Alseda, Guaschi, Los, Manosas and Mumbru proposed to define the pattern of a finite invariant set P essentially as a homotopy class of maps relative to the points of P, and proved (constructively) that there always exists a P-canonical model displaying dynamic minimality properties.
The goal of Chapter 2 is to implement in full the above programme by completing stages 2 and 3. The main result of Chapter 2 tells us that for each tree map g defined on a tree T there exists a finite set S of sequences of positive integers such that the set of periods of g is (up to an explicitly bounded finite set) a finite union of initial segments of Baldwin orderings, given in terms of the set S, which depends on the combinatorial properties of the tree T. We also prove the converse result.
In Chapter 3 we report some computer experiments on the minimality of the dynamics of canonical models. In a spirit of modular programming, we have designed lots of self-contained functions which can be used to implement a wide variety of several-purpose software. Among other, we have functions that: compute the canonical model of a pattern provided by the user, calculate the Markov transition matrix associated to a piecewise monotone tree map and extract all the simple loops of a given length from a Markov transition matrix.
Finally, in Chapter 4 we generalize some results of Block & Coven, Misiurewicz & Nitecki and Takahashi, where the topological entropy of an interval map was approximated by the entropies of its periodic orbits. We prove analogous relations in the setting of graph maps.

This thesis is focusing on boundary problems for various classical integrable schemes. First, we consider the vector nonlinear Schrodinger (NLS) equation on the halfline. Using a Backlund transformation method which explores the folding symmetry of the system, classes of integrable boundary conditions (BCs) are derived. These BCs coincide with the linearizable BCs obtained using the unified transform method developed by Fokas. The notion of integrability is argued by constructing an explicit generating function for conserved quantities. Then, by adapting a mirror image technique, an inverse scattering method with an integrable boundary is constructed in order to obtain N-soliton solutions on the half-line, i.e. N-soliton reflections. An interesting phenomenon of transmission between different components of vector solitons before and after interacting with the boundary is demonstrated. Next, in light of the fact that the soliton-soliton interactions give rise to Yang-Baxter maps, we realize that the soliton-boundary interactions that are extracted from the N-soliton reflections can be translated into maps satisfying the set-theoretical counterpart of the quantum reflection equation. Solutions of the set-theoretical reflection equation are referred to as reflection maps. Both the Yang-Baxter maps and the reflection maps guarantee the factorization of the soliton-soliton and soliton-boundary interactions for vector NLS solitons on the half-line. Indeed, reflection maps represent a novel mathematical structure. Basic notions such as parametric reflection maps, their graphic representations and transfer maps are also introduced. As a natural extension, this object is studied in the context of quadrirational Yang-Baxter maps, and a classification of quadrirational reflection maps is obtained. Finally, boundaries are added to discrete integrable systems on quad-graphs. Triangle configurations are used to discretize quad-graphs with boundaries. Relations involving vertices of the triangles give rise to boundary equations that are used to described BCs. We introduce the notion of integrable BCs by giving a three-dimensional boundary consistency as a criterion for integrability. By exploring the correspondence between the quadrirational Yang-Baxter maps and the so-called ABS classification, we also show that quadrirational reflection maps can be used as a systematic tool to generate integrable boundary equations for the equations from the ABS classification.

The problem of counting ramified covers of a Riemann surface up to homeomorphism was proposed by Hurwitz in the late 1800's. This problem translates combinatorially into factoring a permutation with a specified cycle type, with certain conditions on the cycle types of the factors, such as minimality and transitivity. Goulden and Jackson have given a proof for the number of minimal, transitive factorizations of a permutation into transpositions. This proof involves a partial differential equation for the generating series, called the Join-Cut equation. Furthermore, this argument is generalized to surfaces of higher genus. Recently, Bousquet-Mélou and Schaeffer have found the number of minimal, transitive factorizations of a permutation into arbitrary unspecified factors. This was proved by a purely combinatorial argument, based on a direct bijection between factorizations and certain objects called m-Eulerian trees. In this thesis, we will give a new proof of the result by Bousquet-Mélou and Schaeffer, introducing a simple partial differential equation. We apply algebraic methods based on Lagrange's theorem, and combinatorial methods based on a new use of Bousquet-Mélou and Schaeffer's m-Eulerian trees. Some partial results are also given for a refinement of this problem, in which the number of cycles in each factor is specified. This involves Lagrange's theorem in many variables.

Dissertation to obtain the degree of Doctor in Electrical and Computer Engineering, specialization of Collaborative Networks
Participation in collaborative networks is vital for small and medium-sized enterprises to survive in the current market, bringing them several benefits. However,participation in collaborative networks also involves risks and often consortia fail due to internal conflicts. Conflicts can be originated by different prioritization of values and different perceptions of outcomes. The perception of outcomes is, to some extent, subjective given that it depends on the preferences of the subject and how exchanges are evaluated. Therefore, the establishment of a common Value System or the effort to align the Value Systems of network members can play an important role in the collaboration sustainability. Although the topic of values and values alignment has been studied within the scope of various scientific disciplines, there is still no common understanding on these concepts and the literature does not include any suitable models to formally represent and analyze Value Systems within the scope of collaborative networks. This thesis proposes a set of models and formal mechanisms for specifying and analyzing Value Systems in collaborative networks. The development of models and methods followed a hybrid approach, where qualitative and quantitative techniques are used in order to represent and analyze the Value System. A web application was designed and a prototype developed in order to show that the models and methods proposed can be implemented by a computer program and can be integrated into a single framework in order to support Value Systems management within the scope of collaborative networks. The application of a multifaceted and systematic validation strategy, supported by the “Square Validation Framework” brought together a set of preliminary results that attest the theoretical and practical relevance of the proposed approach and allow us to conclude that: (i) it is possible to define and analyze Value Systems in collaborative networks, considering the economic and sociologic approach, in an integrated and unambiguous way, (ii) the potential impacts between Value Systems in collaborative environments can be inferred if the typical influences among core values are known and the preferences of the actors, regarding those values, are identified; (iii) the identification and assessment of Value Systems misalignments would be improved if qualitative and quantitative assessment methods integrating the notion of shared-values, potential for conflict and positive impacts were developed.

The most basic requirement for any computer controlled game agent in a video game is to be able to successfully navigate the game environment. Pathfinding is an essential component of any agent navigation system. Pathfinding is, at the simplest level, a search technique for finding a route between two points in an environment. The real-time multi-agent nature of video games places extremely tight constraints on the pathfinding problem. This study aims to provide the first complete review of the current state of video game pathfinding both in regards to the graph search algorithms employed as well as the implications of pathfinding within dynamic game environments. Furthermore this thesis presents novel work in the form of a domain specific search algorithm for use on grid-based game maps: the spatial grid A* algorithm which is shown to offer significant improvements over A* within the intended domain. Copyright
Dissertation (MSc)--University of Pretoria, 2011.
Computer Science
unrestricted

In questo lavoro, metodi provenienti dalla Fisica, dalla Statistica e dalla Teoria dei Grafi sono stati impiegati per caratterizzare ed analizzare profili di apertura e accessibilità della cromatina ottenuti con la tecnica ATAC-seq in singole cellule, nella fattispecie linfociti B provenienti da tre pazienti affetti da Leucemia Linfocitica Cronica. Una pipeline bioinformatica è stata sviluppata per processare i dati di sequencing ed ottenere le posizioni accessibili del genoma per ciascuna cellula. La quantità di regioni aperte e la loro distribuzione spaziale lungo il DNA sono state caratterizzate. Infine, l’apertura simultanea nelle stesse singole cellule di regioni regolatrici è stata impiegata come metrica per valutare relazioni funzionali, e in questo modo grafi tra enhancer e promoter sono stati costruiti e le loro proprietà sono state analizzate. La distribuzione spaziale lungo il genoma di regioni aperte consecutive ricapitola proprietà strutturali come gli array di nucleosomi e le strutture a loop della cromatina. Inoltre, i profili di accessibilità delle regioni regolatrici sono significativamente conservati nelle singole cellule. I network tra enhancer e promoter forniscono un modo per caratterizzare la rilevanza di ciascuna regione regolatrice in termini di centralità. Le statistiche sulla connettività tra enhancer e promoter confermano il modello di relazione uno-a-uno come il più frequente, in cui un promoter è regolato dall'enhancer ad esso più vicino. Infine, anche il funzionamento dei superenhancer è stato indagato. In conclusione, ATAC-seq si rivela un'efficace tecnica per indagare l'apertura della cromatina in singole cellule, i cui profili di accessibilità ricapitolano caratteristiche strutturali e funzionali della cromatina. Al fine di indagare i meccanismi della malattia, il panorama di accessibilità dei lifociti tumorali può essere confrontato con quello di cellule sane e cellule trattate con farmaci epigenetici.

In this thesis the novel concept of Sycophant Wireless Sensors (SWS) is introduced. A SWS network is a static ectoparasitic clandestine sensor network mounted incognito on a mobile agent using only the agent&rsquo
s mobility without intervention. SWS networks not only communicate with each other through mobileWireless Sensor Networks (WSN) but also cooperate with them to form a global hybrid Wireless Sensor Network. Such a hybrid network has its own problems and opportunities, some of which have been studied in this thesis work. Assuming that direct position measurements are not always feasible tracking performance of the sycophant using range only measurements for various communication intervals is studied. Then this framework was used to create a hybrid 2D map of the environment utilizing the capabilities of the mobile network the sycophant. In order to show possible applications of a sycophant deployment, the sycophant sensor node was equipped with a laser ranger as its sensor, and it was let to create a 2D map of its environment. This 2D map, which corresponds to a height dierent than the follower network, was merged with the 2D map of the mobile network forming a novel rough 3D map. Then by giving up from the need to properly localize the sycophant even when it is disconnected to the rest of the network, a full 3D map of the environment is obtained by fusing 2D map and tracking capabilities of the mobile network with the 2D vertical scans of the environment by the sycophant. And finally connectivity problems that arise from the hybrid sensor/actuator network were solved. For this 2 new connectivity maintenance algorithms, one based on the helix structures of the proteins, and the other based on the acute triangulation of the space forming a Gabriel Graph, were introduced. In this new algorithms emphasis has been given to sparseness in order to increase fault tolerance to regional problems. To better asses sparseness a new measure, called Resistance was introduced, as well as another called updistance.

The main goal of this work is to implement a system, which will be able to optimize routes between warehouses and selected customers and visualize them using maps by the Google Inc. This problem is being analyzed not only on the theoretical, but also, and mainly, on the practical aspects and tries to find a gap in the market with similar applications.

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

Submitted by Marlene Santos (marlene.bc.ufg@gmail.com) on 2017-09-04T16:56:52Z No. of bitstreams: 2 Dissertação - Lais Cândido Rodrigues da Silva Lopes - 2017.pdf: 3651786 bytes, checksum: 544801154cf6cd32456e6887eaa09b85 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-09-15T13:52:55Z (GMT) No. of bitstreams: 2 Dissertação - Lais Cândido Rodrigues da Silva Lopes - 2017.pdf: 3651786 bytes, checksum: 544801154cf6cd32456e6887eaa09b85 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Made available in DSpace on 2017-09-15T13:52:55Z (GMT). No. of bitstreams: 2 Dissertação - Lais Cândido Rodrigues da Silva Lopes - 2017.pdf: 3651786 bytes, checksum: 544801154cf6cd32456e6887eaa09b85 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-08-03
Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG
The capture of images by multiple positions allows to recover the three-dimensional information of the environment applying the knowledge about the geometry of the cameras and the correspondences between the points of the images. The correspondence of characteristics in images is the task of relating regions of different images to the same point of interest, being considered a problem of difficult solution, since it suffers with ambiguities, occlusions, variation of illumination, besides local distortions. For having so many challenges, this subject is one of the most investigated in the field of computer vision cite Scharstein2001. The present dissertation aims to generate dense disparity maps, using graph cutting, from search spaces constructed with matching metrics based on laws of the Gestalt theory. A hybrid approach was developed, consisting of a local algorithm to construct the image disparity space (EDI), and a global algorithm used to optimize the disparities. The results were maps of disparities close to the expected maps ( textit groundtruth). It was also perceived the best performance of the methodology proposed in relation to the separate methods that compose it.
A captura de imagens por múltiplas posições permite recuperar a informação tridimensional do ambiente aplicando o conhecimento sobre a geometria das câmeras e as correspondências entre os pontos das imagens. A correspondência de características em imagens é a tarefa de relacionar regiões de imagens diferentes a um mesmo ponto de interesse, sendo considerado um problema de difícil solução, uma vez que, sofre com ambiguidades, oclusões, variação de iluminação, além de distorções locais. Por contar com tantos desafios, este tema é um dos mais investigados na área de visão computacional [Scharstein e Szeliski 2002]. A presente dissertação tem por objetivo gerar mapas de disparidade densos, usando corte de grafos, a partir de espaços de busca construídos com métricas de correspondência baseadas em leis da teoria Gestalt. Foi desenvolvida uma abordagem híbrida, composta de um algoritmo local para construir o espaço de disparidades da imagem (EDI), e um algoritmo global utilizado para otimizar as disparidades. Os resultados foram mapas de disparidades próximos dos mapas esperados (ground-truth). Percebeu-se a melhor performance da metodologia proposta em relação aos métodos em separado que a compõe.

On suppose que S=Sg,n est un surface connexe orientable de type topologique fini, de genre g≥3 et n≥0 épointements. Dans les chapitres 1 et 2 on décrit l'ensemble principal d'une surface et prouve que en utilisant expansions rigides itérés, on peut créer suites croissantes d'ensembles finis qui sa réunion est le complexe des courbes de la surface C(S). Dans le 3ème chapitre on introduit l'ensemble rigide X(S) de Aramayona et Leininger et l'utilise pour montrer que la suite des chapitres précédents est eventuellement une suite d'ensembles rigides. On utilise cela pour prouver que si Si=Sgi,ni pour i=1,2 sont surfaces telles que k(S1)≥k(S2) et g1≥3, toute application qui préserve les arêtes de C(S1) dans C(S2) est induite par un homéomorphisme. Ceci est utilisé pour montrer un résultat similaire pour les homomorphismes de sous-groupes de Mod*(S1) dans Mod*(S2). Dans le 4ème chapitre on utilise les résultats précédents pour prouver que l'unique façon d'obtenir une application qui préserve les arêtes et qui est alternante du graphe de Hatcher-Thurston de S1, HT(S1), dans soi de S2, HT(S2) est en utilisant un homéomorphisme de S1 et puis piquer la surface n fois pour obtenir S2. Ceci implique que toute application qui préserve les arêtes et qui est alternante de HT(S) dans soi même et aussi tous les automorphismes de HT(S), sont induits par homéomorphismes. Dans le 5ème chapitre on montre que toute application super-injective du graphe des courbes qui ne sépare pas et courbes extérieures de S1, NO(S1), dans soi de S2, NO(S2), est induite par un homéomorphisme. Finalement, dans les conclusions on discute la signifiance des résultats et les façons possibles d'étendre leur
Suppose S = Sg,n is an orientable connected surface of finite topological type, with genus g ≥ 3 and n ≥ 0 punctures. In the first two chapters we describe the principal set of a surface, and prove that through iterated rigid expansions we can create an increasing sequence of finite sets whose union in the curve complex of the surface C(S). In the third chapter we introduced Aramayona and Leininger's finite rigid set X(S) and use it to prove that the increasing sequence of the previous two chapters becomes an increasing sequence of finite rigid sets after, at most, the fifth iterated rigid expansion. We use this to prove that given S1 = Sg1,n1 and S2 = Sg2,n2 surfaces such that k(S1) ≥ k(S2) and g1 ≥ 3, any edge-preserving map from C(S1) to C(S2) is induced by a homeomorphism from S1 to S2. This is later used to prove a similar statement using homomorphisms from certain subgroups of Mod*(S1) to Mod*(S2). In the fourth chapter we use the previous results to prove that the only way to obtain an edge-preserving and alternating map from the Hatcher-Thurston graph of S1 = Sg,0, HT(S1), to the Hatcher-Thurston graph of S2 = Sg,n, HT(S2), is using a homeomorphism of S1 and then make n punctures to the surface to obtain S2. As a consequence, any edge-preserving and alternating self-map of HT(S) as well as any automorphism is induced by a homeomorphism. In the fifth chapter we prove that any superinjective map from the nonseparating and outer curve graph of S1, NO(S1), to that of S2, NO(S2), is induced by a homeomorphism assuming the same conditions as in the previous chapters. Finally, in the conclusions we discuss the meaning of these results and possible ways to expand them

In this thesis, an exploration mode for the PUREi9 robotic vacuum cleaner is implemented. This exploration would provide information for optimizing the cleaning path beforehand, and would allow the robot to relocalize itself or the charger more easily in case it gets lost. Two elements are needed in order to implement an exploration mode; first, an exploration algo-rithm which will decide the next position of the robot in order to obtain useful information about the environment (unknown areas, empty spaces, obstacles...), and second, an exploration map which stores that information and is updated each time a new relevant position is reached. These elements are related and generally both are required for performing successfully the exploration of a specific environment. A frontier-based strategy is adopted for the exploration algorithm, together with occupancy grid maps. This strategy has long been regarded as a key method for autonomous robots working in unknown or changing environments. The idea of frontier-based algorithms is to divide the environ-ment into cells of regular size and drive the robot to the frontiers between cells with no obstacles and cells for which no information has been gathered. It plans one step ahead by choosing a lo-cation which provides new environment information, instead of planning in advance all locations where the robot needs to acquire new sensor information. Based on frontier strategy, two different exploration algorithms are implemented in the project. The first one is called "random frontier strategy", which chooses arbitrarily the frontier to go among the frontiers set. The second is called "closest frontier strategy", which chooses the closest frontier as the NBV (Next Best View) the robot should drive to. A path planning algorithm, based on Dijkstra’s algorithm and a node graph, has also been implemented in order to guide the robot towards the frontiers. The two methods have been compared by means of simulations in different environments. In addition, both exploration strategies have been tested on a real device. It is found that the closest frontier strategy is more efficient in terms of path length between scanning points, while both methods give a similar exploration ratio, or percentage of fully explored cells within the final map. Some additional work is required in order to improve the performance of the exploration method in the future, such as detecting unreachable frontiers, implementing a more robust path planning algorithm, or filtering the laser measurements more extensively.
I den här rapporten har vi implementerat en utforskningsmod för robotdammsugaren Pure i9. Sådan utforskning skulle ge underlag för att optimera städmönstret i förhand och låta roboten relokalisera sig själv eller laddaren om den tappar bort sig. För att implementera utforskning behövs två saker. För det första krävs en algoritm för utforsk-ning, som bestämmer nästa position för roboten, med målet att samla användbar information om omgivningen (okända eller fria områden, hinder etc.) För det andra krävs en karta som lagrar informationen och uppdateras varje gång roboten når en relevant ny position. Dessa två hänger ihop och i allmänhet krävs båda för att framgångsrikt utforska ett specifikt område. Vi har valt en front-baserad strategi för utforskningsalgoritmen, tillsammans med en rutnäts-karta med sannolikheten för hinder. Denna strategi har länge betraktats som en nyckelmetod för autonoma robotar som arbetar i okända eller föränderliga miljöer. Idén med front-baserade strate-gier är att köra roboten till fronterna mellan celler utan hinder och celler där information saknas. Den planerar ett steg framåt genom att välja en plats som ger ny information om miljön, istället för att i förväg planera alla platser där roboten behöver samla in ny sensorinformation. Baserat på front-strategi, har vi implementerat två utforskningsalgoritmer i projektet. Den första är en slumpmässig strategi, som godtyckligt väljer en front att åka till, ur hela mängden av fronter. Den andra är en närmaste fronten-strategi som väljer den närmaste fronten som den nästa bästa utsiktspunkt som roboten ska åka till. Vi har också implementerat en algoritm för banplanering, baserad på Dijkstras algoritm och en nod-graf, för att styra roboten mot fronterna. Vi har jämfört de två metoderna genom simulering i olika miljöer. Dessutom har båda utforsk-ningsstrategierna testats på en riktig enhet. Närmaste fronten-strategin är effektivare med avse-ende på banlängd mellan skanningspunkter, medan båda metoderna ger liknande utforsknings-grad, eller samma procentandel av fullt utforskade celler inom den slutliga kartan.

Réaliser des variations d'un même modèle est un besoin en expansion dans de nombreux domaines de modélisation (architecture, archéologie, CAO, etc.). Mais la production manuelle de ces variations est fastidieuse, il faut donc faire appel à des techniques permettant de rejouer automatiquement tout ou partie du processus de construction du modèle, après spécification des modifications. La majorité des approches dédiées à la réalisation du rejeu sont basées sur un système de modélisation paramétrique, composée d’un modèle géométrique et d’une spécification paramétrique permettant d’enregistrer la succession d’opérations l’ayant créé ainsi que leurs paramètres. On peut ensuite faire varier ces paramètres ou éditer cette liste d’opérations afin de modifier le modèle. On utilise pour cela un système de nommage persistant, introduit dans les années 90, et permettant d’identifier et d’apparier les entités d’une spécification initiale et celles d'une spécification rejouée. L’objectif de cette thèse est de proposer un système de nommage persistant général, homogène et permettant de gérer l’édition de spécification paramétriques (déplacer, ajouter et supprimer des opérations). Nous nous basons sur la bibliothèque Jerboa, qui repose sur des règles de transformation de graphes, tant pour utiliser ces règles dans la réalisation de la méthode de nommage que pour lier les notions de spécification paramétrique à ces règles de transformations de graphes. Nous décrivons ensuite comment exploiter notre méthode de nommage pour rejouer et éditer des spécifications paramétriques d’opérations, puis nous la comparons avec les approches de la littérature
In many modelling fields, such as architecture, archaeology or CAD, performing many variations of the same model is an expanding need. But building all those variations manually takes time. It is therefore needed to use automatic technics to revaluate some parts of a model, or even an entire model, after the user specifies the modifications. Most of the existing approaches dedicated to revaluating models are based on a system called parametric modelling. It is made of two parts, a geometric model and a parametric specification, which allows to record the series of operation that created the model, and the different parameters of those operations. This way, the user can change some parameters, or edit the list of operations to modify the model. To do so, we use a system called persistent naming, introduced during the 90ies, that allows us to identify and match the entities of an initial specification and the ones of a revaluated specification. In this thesis, our goal is to propose a persistent naming system that would be general, homogeneous and that would allow the user to edit a parametric specification (which means move, add, or delete some operations). We base our system on the Jerboa library, which uses graph transformation rules. This way, we will be able to use those rules to create our naming system, while also linking the notions of graph transformation rules and parametric specification. We will then describe how to use our naming method to revaluate or edit parametric specifications. Finally, we will compare our method with the other ones from the literature

La fibronectine (FN) cellulaire, composante majeure de la matrice extracellulaire, est organisée en réseaux fibrillaires de maniéré différente suivant les deux extra-domaines EDB et EDA. Notre objectif a été le développement de biomarqueurs quantitatifs pour caractériser l'organisation géométrique des quatre variants de FN à partir d'images de microscopie confocale 2D, puis de comparer les tissus sains et cancéreux. Premièrement, nous avons montré à travers deux pipelines de classification fondés sur les curvelets et sur l'apprentissage profond, que les variants peuvent être distingués avec une performance similaire à celle d'un annotateur humain. Nous avons ensuite construit une représentation des fibres (détectées avec des filtres Gabor) fondée sur des graphes. Les variantes ont été classés en utilisant des attributs spécifiques aux graphes, prouvant que ceux-ci intègrent des informations pertinentes dans les images confocales. De plus, nous avons identifié différentes techniques capables de différencier les graphes, afin de comparer les variants de FN quantitativement et qualitativement. Une analyse des performances sur des exemples simples a montré la capacité des méthodes fondées sur l'appariement de graphes et le transport optimal, de comparer les graphes. Nous avons ensuite proposé différentes méthodologies pour définir le graphe représentatif d'une certaine classe. De plus, l'appariement de graphes nous a permis de calculer des cartes de déformation des paramètres entre tissus sains et cancéreux. Ces cartes ont ensuite été analysées dans un cadre statistique montrant si la variation du paramètre peut être expliquée ou non par la variance au sein d'une même classe
A major constituent of the Extracellular Matrix is a large protein called the Fibronectin (FN). Cellular FN is organized in fibrillar networks and can be assembled differently in the presence of two Extra Domains, EDA and EDB. Our objective was to develop numerical quantitative biomarkers to characterize the geometrical organization of the four FN variants (that differ by the inclusion/exclusion of EDA/EDB) from 2D confocal microscopy images, and to compare sane and cancerous tissues. First, we showed through two classification pipelines, based on curvelet features and deep learning framework, that the FN variants can be distinguished with a similar performance to that of a human annotator. We constructed a graph-based representation of the fibers, which were detected using Gabor filters. Graphspecific attributes were employed to classify the variants, proving that the graph representation embeds relevant information from the confocal images. Furthermore, we identified various techniques capable to differentiate the graphs, allowing us to compare the FN variants quantitatively and qualitatively. Performance analysis using toy graphs showed that the methods, which are based on graph matching and optimal transport, can meaningfully compare graphs. Using the graph-matching framework, we proposed different methodologies for defining the prototype graph, representative of a certain FN class. Additionally, the graph matching served as a tool to compute parameter deformation maps between the variants. These deformation maps were analyzed in a statistical framework showing whether or not the variation of the parameters can be explained by the variance within the same class

Un área sumamente interesante dentro del modelado molecular es el diseño de nuevos compuestos. Con sus propiedades definidas antes de ser sintetizados. Los métodos QSPR/QSAR han demostrado que las relaciones entre la estructura molecular y las propiedades físico químicas o actividades biológicas de los compuestos se pueden cuantificar matemáticamente a partir de parámetros estructurales simples.
Las redes neuronales (ANN) constituyen una alternativa para el desarrollo de algoritmos predictivos aplicados en diversos campos como: análisis masivo de bases de datos, para subsanar los obstáculos derivados de la selección o la multicolinealidad de variables, así como la sensibilidad de los modelos a la presencia de ruido en los datos de entrada al sistema neuronal. En la mayoría de los casos, las redes neuronales han dado mejores resultados que los métodos de regresión multilineal (MLR), el análisis de componentes principales (PCA), o los métodos de mínimos cuadrados parciales (PLS) debido a la no linealidad inherente en los modelos de redes.

En los últimos años el interés por los modelos QSPR/QSAR basados en redes neuronales se ha incrementado. La principal ventaja de los modelos de redes recae en el hecho que un modelo QSAR/QSPR puede desarrollarse sin especificar a priori la forma analítica del modelo. Las redes neuronales son especialmente útiles para establecer las complejas relaciones existentes entre la salida del modelo (propiedades físico químicas o biológicas) y la entrada del modelo (descriptores moleculares). Además, permiten clasificar los compuestos de acuerdo a sus descriptores moleculares y usar esta información para seleccionar el conjunto de índices capaz de caracterizar mejor al conjunto de moléculas. Los modelos QSPR basados en redes usan principalmente algoritmos del tipo backpropagation. Backpropagation es un sistema basado en un aprendizaje por minimización del error. Sin embargo, ya que los compuestos químicos pueden clasificarse en grupos de acuerdo a su similitud molecular, es factible usar un clasificador cognitivo como fuzzy ARTMAP para crear una representación simultánea de la estructura y de la propiedad objetivo. Este tipo de sistema cognitivo usa un aprendizaje competitivo, en el cual hay una activa búsqueda de la categoría o la hipótesis cuyos prototipos provean una mejor representación de los datos de entrada (estructura química).

En el presente trabajo se propone y se estudia una metodología que integra dos sistemas cognitivos SOM y fuzzy ARTMAP para obtener modelos QSAR/QSPR. Los modelos estiman diferentes propiedades como las temperaturas de transición de fase (temperatura de ebullición, temperatura de fusión) y propiedades críticas (temperatura y presión), así como la actividad biológica de compuestos orgánicos diversos (indicadores de toxicidad). Dentro de este contexto, se comparan la selección de variables realizados por métodos tradicionales (PCA, o métodos combinatorios) con la realizada usando mapas auto-organizados (SOM).

El conjunto de descriptores moleculares más factible se obtiene escogiendo un representante de cada categoría de índices, en particular aquel índice con la correlación más alta con respecto a la propiedad objetivo. El proceso continúa añadiendo índices en orden decreciente de correlación. Este proceso concluye cuando una medida de disimilitud entre mapas para los diferentes conjuntos de descriptores alcanza un valor mínimo, lo cual indica que el añadir descriptores adicionales no provee información complementaria a la clasificación de los compuestos estudiados. El conjunto de descriptores seleccionados se usa como vector de entrada a la red fuzzy ARTMAP modificada para poder predecir.

Los modelos propuestos QSPR/QSAR para predecir propiedades tanto físico químicas como actividades biológicas predice mejor que los modelos obtenidos con métodos como backpropagation o métodos de contribución de grupos en los casos en los que se apliquen dichos métodos.
One of the most attractive applications of computer-aided techniques in molecular modeling stands on the possibility of assessing certain molecular properties before the molecule is synthesized. The field of Quantitative Structure Activity/Property Relationships (QSAR/QSPR) has demonstrated that the biological activity and the physical properties of a set of compounds can be mathematically related to some "simple" molecular structure parameters.

Artificial neural network (ANN) approaches provide an alternative to established predictive algorithms for analyzing massive chemical databases, potentially overcoming obstacles arising from variable selection, multicollinearity, specification of important parameters, and sensitivy to erroneous values. In most instances, ANN's have proven to be better than MLR, PCA or PLS because of their ability to handle non-linear associations.

In the last years there has been a growing interest in the application of neural networks to the development of QSAR/QSPR. The mayor advantage of ANN lies in the fact QSAR/QSPR can be developed without having to a priori specify an analytical form for the correlation model. The NN approach is especially suited for mapping complex non-linear relationships that exists between model output (physicochemical or biological properties) and input model (molecular descriptors). The NN approach could also be used to classify chemicals according to their chemical descriptors and used this information to select the most suitable indices capable of characterize the set of molecules. Existing neural networks based QSAR/QSPR for estimating properties of chemicals have relied primarily on backpropagation architecture. Backpropagation are an error based learning system in which adaptive weights are dynamically revised so as to minimize estimation errors of target values. However, since chemical compounds can be classified into various structural categories, it is also feasible to use cognitive classifiers such as fuzzy ARTMAP cognitive system, for unsupervised learning of categories, which represent structure and properties simultaneously. This class of neural networks uses a match-based learning, in that it actively searches for recognition categories or hypotheses whose prototype provides an acceptable match to input data.

The current study have been proposed a new QSAR/QSPR fuzzy ARTMAP neural network based models for predicting diverse physical properties such as phase transition temperatures (boiling and melting points) and critical properties (temperature and pressure) and the biological activities (toxicity indicators) of diverse set of compounds. In addition, traditional pre-screening methods to determine de minimum set of inputs parameters have been compared with novel methodology based in self organized maps algorithms.

The most suitable set of molecular descriptor was obtained by choosing a representative from each cluster, in particular the index that presented the highest correlation with the target variable, and additional indices afterwards in order of decreasing correlation. The selection process ended when a dissimilarity measure between the maps for the different sets of descriptors reached a minimum valued, indicating that the inclusion of more descriptors did not add supplementary information. The optimal subset of descriptors was finally used as input to a fuzzy ARTMAP architecture modified to effect predictive capabilities.

The proposed QSPR/QSAR model predicted physicochemical or biological activities significantly better than backpropagation neural networks or traditional approaches such as group contribution methods when they applied.

This dissertation investigates and introduces novel algorithms, theories, and supporting frameworks to significantly improve the growing problem of Internet security. A distributed firewall and active response architecture is introduced that enables any device within a cyber environment to participate in the active discovery and response of cyber attacks. A theory of semantic association systems is developed for the general problem of knowledge discovery in data. The theory of semantic association systems forms the basis of a novel semantic path merger packet classification algorithm. The theoretical aspects of the semantic path merger packet classification algorithm are investigated, and the algorithm's hardware-based implementation is evaluated along with comparative analysis versus content addressable memory. Experimental results show that the hardware implementation of the semantic path merger algorithm significantly outperforms content addressable memory in terms of energy consumption and operational timing.

Šajā darbā mēs pētam kombinatoriskās kartes, kas tiek kodētas kā permutāciju pāri, pielietojot ģeometrisku ideju, ka stūri starp šķautnēm grafam, kas izvietots uz virsmas, ir elementi, uz kuriem permutācijas darbojas.
Ģeometriskās kombinatoriskās kartes kā arī parciālās kartes tiek aplūkotas, ciklu pārklājumu teorija, kas dod objektus, kas atbilst cikliem grafā, tiek attīstīta. Tiek atrastas dažas permutāciju formulas, kas rēķina grafu teorētiskos pielietojumos aktuālus karšu raksturlielumus. Visa darba ideja ir meklēt noderīgus pielietojumus: atrast permutāciju izteiksmēs rēķināmus raksturlielumus, kuriem atbilst grafu teorētiski raksturlielumi.
Datorprograma, kas rēķina permutāciju formulas un no attīstītās teorijas iegūtos algoritmus, ir izveidota.

We introduce Hypoelliptic Diffusion Maps (HDM), a novel semi-supervised machine learning framework for the analysis of collections of anatomical surfaces. Triangular meshes obtained from discretizing these surfaces are high-dimensional, noisy, and unorganized, which makes it difficult to consistently extract robust geometric features for the whole collection. Traditionally, biologists put equal numbers of ``landmarks'' on each mesh, and study the ``shape space'' with this fixed number of landmarks to understand patterns of shape variation in the collection of surfaces; we propose here a correspondence-based, landmark-free approach that automates this process while maintaining morphological interpretability. Our methodology avoids explicit feature extraction and is thus related to the kernel methods, but the equivalent notion of ``kernel function'' takes value in pairwise correspondences between triangular meshes in the collection. Under the assumption that the data set is sampled from a fibre bundle, we show that the new graph Laplacian defined in the HDM framework is the discrete counterpart of a class of hypoelliptic partial differential operators.

This thesis is organized as follows: Chapter 1 is the introduction; Chapter 2 describes the correspondences between anatomical surfaces used in this research; Chapter 3 and 4 discuss the HDM framework in detail; Chapter 5 illustrates some interesting applications of this framework in geometric morphometrics.

Dissertation

Dissertation submitted in partial fulfilment of the requirements for the degree of Master of Science in Geospatial Technologies
The octilinear schematic map, layout recognized worldwide in metro maps, is an important transit informative tool. This research investigates how algorithms for the visualization of schematic maps can be availed in mobile web devices context in order to empower the efficiency in transmitting information of bus transit maps. A genetic algorithm for path octilinear schematization technique has been used and tested to create the schematic data. Location-based and interactivity functionalities were embedded to the resulting digital maps in order to create personalized maps to meet specific user needs. A prototype of a web application and real transit data of the city of Castellón in Spain was used to test the methodology. The results have shown that real time schematizations open possibilities concerning usability that add extra value to schematic transit maps. Additionally, suggested improvements have been made to the genetic algorithm and performance tests show that genetic algorithms are adequate, in terms of efficiency, to sketch bus transit maps automatically.

Dissertação de Mestrado em Engenharia Electrotécnica e de Computadores, apresentada à Faculdade de Ciências e Tecnologia da Universidade de Coimbra
Nowadays, the evolution in the robotics eld allows to free human beings in a set of tasks, mainly the most monotonous and repetitive or, eventually, with dangerous concerns. One of these tasks is the patrolling task in infrastructures. The development and conception of patrolling methods using mobile robots is a scienti c area which has a growing interest. This work focuses on patrolling algorithms for teams of mobile robots endowed with the environment map and the ability for self-location and navigation. The main objective is to develop and validate an original algorithm, scalable to large dimension environments, patrolled by a large number of agents with e cient cooperation, resulting in a high-performance execution of the mission and robustness in the case a fault occurs in a subset of the initially available agents. The presented algorithm is based on multilevel partitioning of the environment map, assigning di erent regions to each mobile agent. Each region corresponds to a subgraph extracted from the existing topological representation. The algorithm deals with the local patrolling task assigned for each robot, being named Multilevel Subgraph Patrolling (MSP) Algorithm. In order to support the algorithm's development and evaluate its performance, a simulator was built, which represented an essential tool during the project. Its properties are presented throughout this document.

In this doctoral thesis, we study and analyze Deep Learning applications to learn physically-based simulations’ results. The first type of application is focused on underground flow analysis problems modeled through Discrete Fracture Networks, training Deep Learning models as reduced models for Uncertainty Quantification. In particular, we look for trained Neural Networks able to predict the outflowing fluxes of a Discrete Fracture Network model. These Neural Networks are also exploited to define a new backbone identification method for a network of underground fractures. The second type of application deals with the parametric design optimization processes; specifically, we train Deep Learning models to speed up the objective function calls. These applications are described after a novel and sound formalization of the main concepts of supervised Machine Learning and Deep Neural Networks (the quintessence of Deep Learning). A numerical approach characterizes this new formalization of the learning problem; furthermore, we describe how the learning techniques evolved in history to reach the current state of the art. We test different kinds of Neural Network architectures in this thesis, such as the multitask Neural Networks and the residual Neural Networks. Moreover, we develop two new Neural Network layers: the Graph Informed layer and the Discontinuous layer. The first one is defined to embed Neural Network architectures with graphs and improve prediction abilities on graph-structured data (as the Discrete Fracture Network models). The second one introduces learnable discontinuities into Neural Networks, to approximate discontinuous functions and identify discontinuity interfaces. The last chapter of this thesis is dedicated to the definition and description of the Discontinuous layers.

Thesis is devoted to the analysis of the functioning of the urban ecosystem by methods of cognitive modeling to study the impact of seasonal climate change on the nature of chemical pollution of the ecosystem. The aim of the work is to conduct cognitive modeling of the urban ecosystem to analyze the factors of influence and assess pollution in accordance with the season.
Дипломна робота присвячена аналізу функціонування урбоекосистеми методами когнітивного моделювання для вивчення впливу сезонних змін клімату на характер хімічного забруднення екосистеми. Метою роботи є проведення когнітивного моделювання урбоекосистеми для аналізу факторів впливу та оцінки забруднення у відповідності до пори року.
ЗМІСТ Вступ .... 11 1 Аналіз літературних джерел ...13 1.1 Загальні поняття ...13 1.2 Когнітивна комп’ютерна графіка в рамках прикладної науки інформатики ...15 1.3 Якісна візуалізація даних ...18 1.4 Класифікація програмних продуктів, що використовують ідею когнітивного моделювання ...19 1.4.1 Підтримка когнітивного інтерфейсу ...19 1.4.2 Когнітивне моделювання в пакетах імітаційного моделювання .... 20 1.4.3 Пакети для розробки якісної візуалізації даних ...21 1.5 Висновок до першого розділу ...22 2 Обґрунтування проблеми...23 2.1 Когнітивні карти та методи їх побудови ...23 2.2 Імпульсні процеси ...24 2.3 Стабільність системи...30 2.4 Завдання і методи когнітивного дослідження ...32 2.5 Когнітивне моделювання на прикладі системи споживання енергії на транспорті ...33 2.6 Висновок до другого розділу ...40 3 Методи та засоби вирішення проблеми ...41 3.1 Аналіз впливу сезонних змін клімату на хімічне забруднення урбоекосистеми ...41 3.2 Автоматизація побудови процедур ...50 3.3 Висновок до третього розділу...53 4 Практична реалізація ...54 4.1 Опис основних процедур та вікон програми ...54 4.2 Висновок до четвертого розділу ...62 5 Спеціальна частина ...63 5.1 Опис платформи NET Framework ...63 5.2 Компіляція вихідного коду ...67 5.3 Висновок до п’ятого розділу ...68 6 Обгрунтування економічної ефективності ...69 6.1 Розрахунок норм часу на виконання науково-дослідної роботи ...69 6.2 Визначення витрат на оплату праці та відрахувань на соціальні заходи ... 70 6.3 Розрахунок матеріальних витрат ...72 6.4 Розрахунок витрат на електроенергію ...73 6.5 Розрахунок суми амортизаційних відрахувань ...74 6.6 Складання кошторису витрат та визначення собівартості науково-дослідницької роботи ...75 6.7 Розрахунок ціни програмного продукту ...76 6.8 Визначення економічної ефективності і терміну окупності капітальних вкладень ... 77 6.9 Висновок до шостого розділу ...79 7 Охорона праці та безпека в надзвичайних ситуаціях ...80 7.1 Охорона праці ...80 7.1.1 Організація охорони праці на малому підприємстві ...80 7.1.2 Методи регулювання якістю повітря і зниження негативного впливу забруднюючих речовин на працівників ...82 7.2 Безпека в надзвичайних ситуаціях ...86 7.2.1 Організація та забезпечення заходів щодо розосередження робітників та службовців суб’єктів господарювання, що продовжують свою роботу в особливий період і евакуації населення ...86 7.2.2 Ергономічні вимоги до робочого місця користувача ПК ...90 7.3 Висновок до сьомого розділу ...93 8 ЕКОЛОГІЯ ...94 8.1 Статистика природних та екологічних чинників ...94 8.2 Джерела шуму і вібрацій та методи їх знешкодження ...96 8.3 Висновок до восьмого розділу ...99 ВИСНОВКИ ...100 ПЕРЕЛІК ВИКОРИСТАНИХ ДЖЕРЕЛ ...102

Tese de doutoramento em Engenharia Electrotécnica e de Computadores, apresentada ao Departamento de Engenharia Electrotécnica e de Computadores da Faculdade de Ciências e Tecnologia da Universidade de Coimbra
In the digital era that we live in, advances in technology have proliferated throughout our society, quickening the completion of tasks that were painful in the old days, improving solutions to the everyday problems that we face, and generally assisting human beings both in their professional and personal life. Robotics is a clear example of a broad technological field that evolves every day. In fact, scientists predict that in the upcoming few decades, robots will naturally interact and coexist alongside human beings. While it is true that robots already have a strong presence in industrial environments, e.g., robotic arms for manufacturing, the average person still looks upon robots with suspicion, since they are not acquainted by such type of technology. In this thesis, the author deploys teams of mobile robots in indoor scenarios to cooperatively perform patrolling missions, which represents an effort to bring robots closer to humans and assist them in monotonous or repetitive tasks, such as supervising and monitoring indoor infrastructures or simply cooperatively cleaning floors. In this context, the team of robots should be able to sense the environment, localize and navigate autonomously between way points while avoiding obstacles, incorporate any number of robots, communicate actions in a distributed way and being robust not only to agent failures but also communication failures, so as to effectively coordinate to achieve optimal collective performance. The referred capabilities are an evidence that such systems can only prove their reliability in real-world environments if robots are endowed with intelligence and autonomy. Thus, the author follows a line of research where patrolling units have the necessary tools for intelligent decision-making, according to the information of the mission, the environment and teammates' actions, using distributed coordination architectures. An incremental approach is followed. Firstly, the problem is presented and the literature is deeply studied in order to identify potential weaknesses and research opportunities, backing up the objectives and contributions proposed in this thesis. Then, problem fundamentals are described and benchmarking of multi-robot patrolling algorithms in realistic conditions is conducted. In these earlier stages, the role of different parameters of the problem, like environment connectivity, team size and strategy philosophy, will become evident through extensive empirical results and statistical analysis. In addition, scalability is deeply analyzed and tied with inter-robot interference and coordination, imposed by each patrolling strategy. After gaining sensibility to the problem, preliminary models for multi-robot patrol with special focus on real-world application are presented, using a Bayesian inspired formalism. Based on these, distributed strategies that lead to superior team performance are described. Interference between autonomous agents is explicitly dealt with, and the approaches are shown to scale to large teams of robots. Additionally, the robustness to agent and communication failures is demonstrated, as well as the flexibility of the model proposed. In fact, by later generalizing the model with learning agents and maintaining memory of past events, it is then shown that these capabilities can be inherited, while at the same time increasing team performance even further and fostering adaptability. This is verified in simulation experiments and real-world results in a large indoor scenario. Furthermore, since the issue of team scalability is highly in focus in this thesis, a method for estimating the optimal team size in a patrolling mission, according to the environment topology is proposed. Upper bounds for team performance prior to the mission start are provided, supporting the choice of the number of robots to be used so that temporal constraints can be satisfied. All methods developed in this thesis are tested and corroborated by experimental results, showing the usefulness of employing cooperative teams of robots in real-world environments and the potential for similar systems to emerge in our society.
FCT - SFRH/BD/64426/2009

Réaliser des variations d'un même modèle est un besoin en expansion dans de nombreux domaines de modélisation (architecture, archéologie, CAO, etc.). Mais la production manuelle de ces variations est fastidieuse, il faut donc faire appel à des techniques permettant de rejouer automatiquement tout ou partie du processus de construction du modèle, après spécification des modifications. La majorité des approches dédiées à la réalisation du rejeu sont basées sur un système de modélisation paramétrique, composée d’un modèle géométrique et d’une spécification paramétrique permettant d’enregistrer la succession d’opérations l’ayant créé ainsi que leurs paramètres. On peut ensuite faire varier ces paramètres ou éditer cette liste d’opérations afin de modifier le modèle. On utilise pour cela un système de nommage persistant, introduit dans les années 90, et permettant d’identifier et d’apparier les entités d’une spécification initiale et celles d'une spécification rejouée. L’objectif de cette thèse est de proposer un système de nommage persistant général, homogène et permettant de gérer l’édition de spécification paramétriques (déplacer, ajouter et supprimer des opérations). Nous nous basons sur la bibliothèque Jerboa, qui repose sur des règles de transformation de graphes, tant pour utiliser ces règles dans la réalisation de la méthode de nommage que pour lier les notions de spécification paramétrique à ces règles de transformations de graphes. Nous décrivons ensuite comment exploiter notre méthode de nommage pour rejouer et éditer des spécifications paramétriques d’opérations, puis nous la comparons avec les approches de la littérature
In many modelling fields, such as architecture, archaeology or CAD, performing many variations of the same model is an expanding need. But building all those variations manually takes time. It is therefore needed to use automatic technics to revaluate some parts of a model, or even an entire model, after the user specifies the modifications. Most of the existing approaches dedicated to revaluating models are based on a system called parametric modelling. It is made of two parts, a geometric model and a parametric specification, which allows to record the series of operation that created the model, and the different parameters of those operations. This way, the user can change some parameters, or edit the list of operations to modify the model. To do so, we use a system called persistent naming, introduced during the 90ies, that allows us to identify and match the entities of an initial specification and the ones of a revaluated specification. In this thesis, our goal is to propose a persistent naming system that would be general, homogeneous and that would allow the user to edit a parametric specification (which means move, add, or delete some operations). We base our system on the Jerboa library, which uses graph transformation rules. This way, we will be able to use those rules to create our naming system, while also linking the notions of graph transformation rules and parametric specification. We will then describe how to use our naming method to revaluate or edit parametric specifications. Finally, we will compare our method with the other ones from the literature

Η παρούσα εργασία ασχολείται με την ανάκτηση σχήματος. Πιο συγκεκριμένα επικεντρώνεται σε επίπεδα (δισδιάστατα) σχήματα τα οποία είναι μη άκαμπτα και έχουν υποστεί κάμψη ή μεταβάλλονται εξαιτίας της παρουσίας κάποιας άρθρωσης. Τέτοια εύκαμπτα σχήματα συναντάμε καθημερινά στη φύση όπως για παράδειγμα τους μικροοργανισμούς μέχρι και τον ίδιο τον άνθρωπο. Τα κριτήρια ομοιότητας μεταξύ των σχημάτων που χρησιμοποιούνται εδώ είναι Intrinsic. Τέτοια κριτήρια μπορεί κανείς να εξάγει δημιουργώντας ένα τελεστή διάχυσης. Οι τελεστές διάχυσης μπορούν να διατυπωθούν με πολλούς τρόπους. Στην παρούσα εργασία βασιζόμαστε στην πιθανολογική προσέγγιση δημιουργώντας ένα τελεστή (Μητρώο Markov) ενώ ταυτόχρονα λαμβάνουμε ένα τυχαίο περίπατο στα δεδομένα. Ο τελεστής αυτός επιπλέον έχει το πλεονέκτημα ότι μπορεί να προσεγγίσει τον τελεστή Laplace-Beltrami ασχέτως της πυκνότητας δειγματοληψίας των δεδομένων. Ορίζεται λοιπόν ως Απόσταση Διάχυσης η απόσταση δύο σημείων. Η απόσταση αυτή είναι μικρότερη όσο περισσότερα μονοπάτια συνδέουν τα δύο σημεία. Η φασματική ανάλυση του μητρώου αυτού μας επιτρέπει να αναπαραστήσουμε τα δεδομένα μας σε ένα νέο χώρο με σαφή μετρική απόσταση την Ευκλείδεια χρησιμοποιώντας τις ιδιοτιμές και τα ιδιοδιανύσματα που προκύπτουν. Επιπλέον η Ευκλείδεια απόσταση στο νέο χώρο ισούται με την απόσταση Διάχυσης στον αρχικό χώρο. Ο συνδυασμός των φασματικών ιδιοτήτων του μητρώου Διάχυσης με τις Markov διεργασίες οδηγεί σε μία ανάλυση των δεδομένων σε πολλές κλίμακες. Αυτό ισοδυναμεί με το να προχωρήσουμε τον τυχαίο περίπατο μπροστά. Από τις απεικονίσεις αυτές μπορούμε να εξάγουμε ιστογράμματα κατανομής αποστάσεων. Έτσι για κάθε σχήμα και για κάθε κλίμακα λαμβάνουμε ένα ιστόγραμμα κατανομής αποστάσεων. Συνεπώς δύο σχήματα μπορεί να βρίσκονται πολύ κοντά σε μία κλίμακα χρόνου ενώ να βρίσκονται πολύ μακριά σε μία άλλη κλίμακα. Συγκεκριμένα εδώ παραθέτουμε την άποψη η απόσταση των σχημάτων συνδέεται άμεσα με την κλίμακα- χρόνο. Μελετώνται οι ιδιότητες των μικρών, μεσαίων και μεγάλων κλιμάκων κυρίως ως προς τα γεωμετρικά χαρακτηριστικά που μπορούν να περιγράψουν και κατά συνέπεια την ικανότητα να εξάγουν αποδοτικούς περιγραφείς των σχημάτων. Η συνεισφορά της παρούσας Διπλωματικής Εργασίας είναι διπλή: A. Προτείνεται για πρώτη φορά μία νέα μέθοδος κατά την οποία αξιοποιούνται οι ιδιότητες των διαφορετικών κλιμάκων της διεργασίας Διάχυσης που αναφέραμε. Ονομάζουμε τη μέθοδο αυτή Weighted Multiscale Diffusion Distance -WMDD. B. Τα αποτελέσματα που παρουσιάζονται φέρνουν την μέθοδο αυτή στην κορυφή για τις συγκεκριμένες βάσεις σχημάτων (MPEG-7 και KIMIA 99).
This thesis focuses explicitly at shape retrieval applications. More precisely concentrates in planar shapes that are non-rigid, meaning that they might have been articulated or bended. These non-rigid shapes appear in humans’ life like for example bacteria and also the same the human body. The shape pair wise similarity criteria are intrinsic. Such similarity criteria one can take through a Diffusion Operator. Diffusion Operators can be defined in many ways. In this thesis we concern only in the probabilistic interpretation of Diffusion Operators. Thus by constructing a Diffusion Operator we also construct a random Walk on data. This operator converges to the Laplace-Beltrami even if the sampling density of the data is not uniform. Through this framework the Diffusion Distance between two points is defined. This distance gets smaller as much more paths are connecting two points. Spectral decomposition if this diffusion kernel allows us to map, re-represent our data using the eigenvectors and the eigenvalues in a new space with the property of embedding with an explicit metric. These maps are called Diffusion Maps and have the property that diffusion distance in the initial space equals the Euclidean distance in the embedding space. A combination of spectral properties of a Markov matrix with Markov Processes leads to a multiscale analysis. This corresponds to running the random walk forward. From these embeddings we can extract histograms of distributions of distances. Thus for every shape and every scale we have one histogram. Therefore two shapes may be close in one scale but not in another one. The contribution of this Thesis is twofold: A. For first time a new method where the properties of different scales as studied in order to take the advantage of the most discriminative times/ steps of the diffusion process that we described above. We called this method Weighted Multiscale Diffusion Distance- WMDD. B. The results presented here bring our method to the state of the art for the MPEG- and KIMIA 99 databases.