La modélisation 3d automatique d'un environnement à partir d'images est un sujet toujours d'actualité en vision par ordinateur. Ce problème se résout en général en trois temps : déplacer une caméra dans la scène pour prendre la séquence d'images, reconstruire la géométrie, et utiliser une méthode de stéréo dense pour obtenir une surface de la scène. La seconde étape met en correspondances des points d'intérêts dans les images puis estime simultanément les poses de la caméra et un nuage épars de points 3d de la scène correspondant aux points d'intérêts. La troisième étape utilise l'information sur l'ensemble des pixels pour reconstruire une surface de la scène, par exemple en estimant un nuage de points dense.Ici nous proposons de traiter le problème en calculant directement une surface à partir du nuage épars de points et de son information de visibilité fournis par l'estimation de la géométrie. Les avantages sont des faibles complexités en temps et en espace, ce qui est utile par exemple pour obtenir des modèles compacts de grands environnements comme une ville. Pour cela, nous présentons une méthode de reconstruction de surface du type sculpture dans une triangulation de Delaunay 3d des points reconstruits. L'information de visibilité est utilisée pour classer les tétraèdres en espace vide ou matière. Puis une surface est extraite de sorte à séparer au mieux ces tétraèdres à l'aide d'une méthode gloutonne et d'une minorité de points de Steiner. On impose sur la surface la contrainte de 2-variété pour permettre des traitements ultérieurs classiques tels que lissage, raffinement par optimisation de photo-consistance ... Cette méthode a ensuite été étendue au cas incrémental : à chaque nouvelle image clef sélectionnée dans une vidéo, de nouveaux points 3d et une nouvelle pose sont estimés, puis la surface est mise à jour. La complexité en temps est étudiée dans les deux cas (incrémental ou non). Dans les expériences, nous utilisons une caméra catadioptrique bas coût et obtenons des modèles 3d texturés pour des environnements complets incluant bâtiments, sol, végétation ... Un inconvénient de nos méthodes est que la reconstruction des éléments fins de la scène n'est pas correcte, par exemple les branches des arbres et les pylônes électriques. / The automatic 3d modeling of an environment using images is still an active topic in Computer Vision. Standard methods have three steps : moving a camera in the environment to take an image sequence, reconstructing the geometry of the environment, and applying a dense stereo method to obtain a surface model of the environment. In the second step, interest points are detected and matched in images, then camera poses and a sparse cloud of 3d points corresponding to the interest points are simultaneously estimated. In the third step, all pixels of images are used to reconstruct a surface of the environment, e.g. by estimating a dense cloud of 3d points. Here we propose to generate a surface directly from the sparse point cloud and its visibility information provided by the geometry reconstruction step. The advantages are low time and space complexities ; this is useful e.g. for obtaining compact models of large and complete environments like a city. To do so, a surface reconstruction method by sculpting 3d Delaunay triangulation of the reconstructed points is proposed.The visibility information is used to classify the tetrahedra in free-space and matter. Then a surface is extracted thanks to a greedy method and a minority of Steiner points. The 2-manifold constraint is enforced on the surface to allow standard surface post-processing such as denoising, refinement by photo-consistency optimization ... This method is also extended to the incremental case : each time a new key-frame is selected in the input video, new 3d points and camera pose are estimated, then the reconstructed surface is updated.We study the time complexity in both cases (incremental or not). In experiments, a low-cost catadioptric camera is used to generate textured 3d models for complete environments including buildings, ground, vegetation ... A drawback of our methods is that thin scene components cannot be correctly reconstructed, e.g. tree branches and electric posts.

Dado um processo de Poisson d-dimensional, construímos funções harmônicas na triangulação de Delaunay associada, com comportamento assintótico linear, como limite de um processo de harness sem ruído. Tais funções permitem que construamos uma nova imersão da triangulação de Delaunay, que denominaremos de deformação harmônica. / Given a d-dimensional Poisson point process, we construct harmonic functions on the associated Delaunay triangulation, with linear assymptotic behaviour, as the limit of a noiseless harness process. These mappings allow us to find a new embedding for the Delaunay triangulation. We call it harmonic deformation of the graph.

Dado um processo de Poisson d-dimensional, construímos funções harmônicas na triangulação de Delaunay associada, com comportamento assintótico linear, como limite de um processo de harness sem ruído. Tais funções permitem que construamos uma nova imersão da triangulação de Delaunay, que denominaremos de deformação harmônica. / Given a d-dimensional Poisson point process, we construct harmonic functions on the associated Delaunay triangulation, with linear assymptotic behaviour, as the limit of a noiseless harness process. These mappings allow us to find a new embedding for the Delaunay triangulation. We call it harmonic deformation of the graph.

Given a set of n points P ⊂ R2, the Delaunay graph of P for a family of geometric objects C is a graph defined as follows: the vertex set is P and two points p, p' ∈ P are connected by an edge if and only if there exists some C ∈ C containing p, p' but no other point of P. Delaunay graph of circle is often called as Delaunay triangulation as each of its inner face is a triangle if no three points are co-linear and no four points are co-circular. The dual of the Delaunay triangulation is the Voronoi diagram, which is a well studied structure. The study of graph theoretic properties on Delaunay graphs was motivated by its application to wireless sensor networks, meshing, computer vision, computer graphics, computational geometry, height interpolation, etc. The problem of finding an optimal vertex cover on a graph is a classical NP-hard problem. In this thesis we focus on the vertex cover problem on Delaunay graphs for geometric objects like axis-parallel slabs and circles(Delaunay triangulation). 1. We consider the vertex cover problem on Delaunay graph of axis-parallel slabs. It turns out that the Delaunay graph of axis-parallel slabs has a very special property — its edge set is the union of two Hamiltonian paths. Thus, our problem reduces to solving vertex cover on the class of graphs whose edge set is simply the union of two Hamiltonian Paths. We refer to such a graph as a braid graph. Despite the appealing structure, we show that deciding k-vertex cover on braid graphs is NP-complete. This involves a rather intricate reduction from the problem of finding a vertex cover on 2-connected cubic planar graphs. 2. Having established the NP-hardness of the vertex cover problem on braid graphs, we pursue the question of improved fixed parameter algorithms on braid graphs. The best-known algorithm for vertex cover on general graphs has a running time of O(1.2738k + kn) [CKX10]. We propose a branching based fixed parameter tractable algorithm with running time O⋆(1.2637k) for graphs with maximum degree bounded by four. This improves the best known algorithm for this class, which surprisingly has been no better than the algorithm for general graphs. Note that this implies faster algorithms for the class of braid graphs (since they have maximum degree at most four). 3. A triangulation is a 2-connected plane graph in which all the faces except possibly the outer face are triangles, we often refer to such graphs as triangulated graphs. A chordless-NST is a triangulation that does not have chords or separating triangles (non-facial triangles). We focus on the computational problem of optimal vertex covers on triangulations, specifically chordless-NST. We call a triangulation Delaunay realizable if it is combinatorially equivalent to some Delaunay triangulation. Characterizations of Delaunay triangulations have been well studied in graph theory. Dillencourt and Smith [DS96] showed that chordless-NSTs are Delaunay realizable. We show that for chordless-NST, deciding the vertex cover problem is NP-complete. We prove this by giving a reduction from vertex cover on 3-connected, triangle free planar graph to an instance of vertex cover on a chordless-NST. 4. If the outer face of a triangulation is also a triangle, then it is called a maximal planar graph. We prove that the vertex cover problem is NP-complete on maximal planar graphs by reducing an instance of vertex cover on a triangulated graph to an instance of vertex cover on a maximal planar graph.

In this thesis, an approach is presented for the generation of grids suitable for the simulation of high Reynolds number viscous flows in complex three-dimensional geometries. The automatic and reliable generation of such grids is today on the biggest bottlenecks in the industrial CFD simulation environment.<p><p>In the proposed approach, unstructured tetrahedral grids are employed for the regions far from the viscous boundaries of the domain, while semi-structured layers of high aspect ratio prismatic and hexahedral elements are used to provide the necessary grid resolution inside the boundary layers and normal to the viscous walls. The definition of the domain model is based on the STEP ISO standard and the topological information contained in the model is used for applying the hierarchical grid generation parameters defined by the user. An efficient, high-quality and robust algorithm is presented for the generation of the unstructured simplicial (triangular of tetrahedral) part of the grid. The algorithm is based on the Delaunay triangulation and the internal grid points are created following a centroid or frontal approach. For the surface grid generation, a hybrid approach is also proposed similar to the volume.<p>Semi-structured grids are generated on the surface grid (both on the edges and faces of the domain) to improve the grid resolution around convex and concave ridges and corners, by aligning the grid elements in the directions of high solution gradients along the surface. A method is also developed for automatically setting the grid generation parameters related to the surface grid generation based on the curvature of the surface in order to obtain an accurate and smooth surface grid. Finally, a semi-structured prismatic/hexahedral grid generation algorithm is presented for the generation of the part of grid close to the viscous walls of the domain. The algorithm is further extended with improvements meant to increase the grid quality around concave and convex ridges of the domain, where the semi-structured grids are known to be inadequate.<p><p>The combined methodology is demonstrated on a variety of complex examples mainly from the automotive and aeronautical industry. / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished

Cognitive radio (CR) is often described as a context-intelligent radio, capable of changing the transmit parameters dynamically based on the interaction with the environment it operates. The work in this thesis explores the problem of using received signal strength (RSS) measurements taken by a network of CR nodes to generate an interference map of a given geographical area and estimate the locations of multiple primary transmitters that operate simultaneously in the area. A probabilistic model of the problem is developed, and algorithms to address location estimation challenges are proposed. Three approaches are proposed to solve the localization problem. The first approach is based on estimating the locations from the generated interference map when no information about the propagation model or any of its parameters is present. The second approach is based on approximating the maximum likelihood (ML) estimate of the transmitter locations with the grid search method when the model is known and its parameters are available. The third approach also requires the knowledge of model parameters but it is actually based on generating samples from the joint posterior of the unknown location parameter with Markov chain Monte Carlo (MCMC) methods, as an alternative for the highly computationally complex grid search approach. For RF cartography generation problem, we study global and local interpolation techniques, specifically the Delaunay triangulation based techniques as the use of existing triangulation provides a computationally attractive solution. We present a comparative performance evaluation of these interpolation techniques in terms of RF field strength estimation and emitter localization. Even though the estimates obtained from the generated interference maps are less accurate compared to the ML estimator, the rough estimates are utilized to initialize a more accurate algorithm such as the MCMC technique to reduce the complexity of the algorithm. The complexity issues of ML estimators based on full grid search are also addressed by various types of iterative grid search methods. One challenge to apply the ML estimation algorithm to multiple emitter localization problem is that, it requires a pdf approximation to summands of log-normal random variables for likelihood calculations at each grid location. This inspires our investigations on sum of log-normal approximations studied in literature for selecting the appropriate approximation to our model assumptions. As a final extension of this work, we propose our own approximation based on distribution fitting to a set of simulated data and compare our approach with Fenton-Wilkinson's well-known approximation which is a simple and computational efficient approach that fits a log-normal distribution to sum of log-normals by matching the first and second central moments of random variables. We demonstrate that the location estimation accuracy of the grid search technique obtained with our proposed approximation is higher than the one obtained with Fenton-Wilkinson's in many different case scenarios.

Selon la méthode utilisée pour construire un modèle structural en trois dimensions et selon l'application à laquelle il est destiné, son maillage, en d'autres termes sa représentation informatique, doit être adapté afin de respecter des critères de type, de nombre et de qualité de ses éléments. Les méthodes de maillage développées dans d'autres domaines que la géomodélisation ne permettent pas de modifier le modèle d'entrée. Ceci est souhaitable en géomodélisation afin de mieux contrôler le nombre d'éléments du maillage et leur qualité. L'objectif de cette thèse est de développer des méthodes de maillage permettant de remplir ces objectifs afin de gérer la complexité géométrique des modèles structuraux définis par frontières. Premièrement, une analyse des sources de complexité géométrique dans ces modèles est proposée. Les mesures développées constituent une première étape dans la définition d'outils permettant la comparaison objective de différents modèles et aident à caractériser précisément les zones plus compliquées à mailler dans un modèle. Ensuite, des méthodes originales de remaillage surfacique et de maillage volumique fondées sur l'utilisation des diagrammes de Voronoï sont proposées. Les fondements de ces deux méthodes sont identiques : (1) une optimisation de type Voronoï barycentrique est utilisée pour globalement obtenir un nombre contrôlé d’éléments de bonne qualité et (2) des considérations combinatoires permettant de construire localement le maillage final, éventuellement en modifiant le modèle initial. La méthode de remaillage surfacique est automatique et permet de simplifier un modèle à une résolution donnée. L'originalité de la méthode de maillage volumique est que les éléments générés sont de types différents. Des prismes et pyramides sont utilisés pour remplir les zones très fines du modèle, tandis que le reste du modèle est rempli avec des tétraèdres / Depending on the specific method used to build a 3D structural model, and on the exact purpose of this model, its mesh must be adapted so that it enforces criteria on element types, maximum number of elements, and mesh quality. Meshing methods developed for applications others than geomodeling forbid any modification of the input model, that may be desirable in geomodeling to better control the number of elements in the final mesh and their quality. The objective of this thesis is to develop meshing methods that fulfill this requirement to better manage the geometrical complexity of B-Rep geological structural models. An analysis of the sources of geometrical complexity in those models is first proposed. The introduced measures are a first step toward the definition of tools allowing objective comparisons of structural models and permit to characterize the model zones that are more complicated to mesh. We then introduce two original meshing methods based on Voronoi diagrams: the first for surface remeshing, the second for hybrid gridding. The key ideas of these methods are identical: (1) the use of a centroidal Voronoi optimization to have a globally controlled number of elements of good quality, and (2) combinatorial considerations to locally build the final mesh while sometimes modifying the initial model. The surface remeshing method is automatic and permits to simplify a model at a given resolution. The gridding method generates a hybrid volumetric mesh. Prisms and pyramids fill the very thin layers of the model while the remaining regions are filled with tetrahedra

在無線網狀網路(Wireless Mesh Network)中，每個節點須幫助相鄰節點轉送資料及提供使用者網路存取，例如WLAN(IEEE 802.11s)、WMAN(IEEE 802.16)等，皆可利用多跳接方式將資料轉送至通訊閘道器(Gateway)。在無線網狀網路中，常利用密集佈建的方式來解決通訊死角的問題。當網路節點的密度增加時，無線訊號的干擾也會增強，並且各節點的效能會顯著下降。 在本研究中，將利用幾何學概念，解決網路干擾問題，並提出拓樸重建演算法來重建路徑，使網路干擾達到最小化。我們試著最小化節點與節點間的干擾，以提升整體無線網狀網路效能。我們將網路問題轉換成幾何問題，並定義在幾何圖形中線段交錯問題，之後驗證在幾何圖形中是否有線段交錯的現象發生。若發生線段交錯時，則將此線段從幾何圖形中移除，並且利用三角化演算法將此區域線段重新規劃，使相鄰節點間的干擾最小。當網路拓樸建立完成後，我們利用標準差公式將干擾較大的連線移除，使得網路效能提升。上述測試線段交錯及三角化多邊形演算法可在時間複雜度O(n log n)內找到干擾最小的解。最後，我們將利用網路模擬器(Network Simulator)驗證所提出的方法是否能達到預期的系統效能指標。 / In wireless mesh networks, such as WLAN (IEEE 802.11s), WMAN (IEEE 802.16), etc., each node should forward packets of neighboring nodes toward gateway using multi-hop routing mechanism. In wireless mesh network, as the density of network nodes increases, the RF interference will increase and the throughput of each node will drop rapidly. In our research, we use the geometry to resolve the RF interference problem by rebuilding network topology. We try to minimize the interference between neighboring nodes and improve the throughput in wireless mesh network. We transform the network topology problem into geometry problem and define the line intersection problem in geometric graph, then check path intersection in the geometric graph. If line intersection occurs in the graph, we remove the intersection line from the graph and re-plan the region by triangulation algorithm. When the network topology is built up, we use a standard deviation formula to improve network performance by removing longer links. The line intersection algorithm and triangulation algorithm, both of time complexity O(n log n), are used to find the minimal interference solution. At the end of our research, we use network simulator to verify if the proposed methods can help to meet all those performance expectations.

Dans cette thèse, nous étudions les problèmes de reconstruction statique et dynamique à partir de vues multiples et texturation, en s'appuyant sur des applications réelles et pratiques. Nous proposons trois méthodes de reconstruction destinées à l'estimation d'une représentation d'une scène statique/dynamique à partir d'un ensemble d'images/vidéos. Nous considérons ensuite le problème de texturation multi-vues en se concentrant sur la qualité visuelle de rendu..

This thesis investigates the problem of robot navigation using only landmark bearings. The proposed system allows a robot to move to a ground target location specified by the sensor values observed at this ground target posi- tion. The control actions are computed based on the difference between the current landmark bearings and the target landmark bearings. No Cartesian coordinates with respect to the ground are computed by the control system. The robot navigates using solely information from the bearing sensor space. Most existing robot navigation systems require a ground frame (2D Cartesian coordinate system) in order to navigate from a ground point A to a ground point B. The commonly used sensors such as laser range scanner, sonar, infrared, and vision do not directly provide the 2D ground coordi- nates of the robot. The existing systems use the sensor measurements to localise the robot with respect to a map, a set of 2D coordinates of the objects of interest. It is more natural to navigate between the points in the sensor space corresponding to A and B without requiring the Cartesian map and the localisation process. Research on animals has revealed how insects are able to exploit very limited computational and memory resources to successfully navigate to a desired destination without computing Cartesian positions. For example, a honeybee balances the left and right optical flows to navigate in a nar- row corridor. Unlike many other ants, Cataglyphis bicolor does not secrete pheromone trails in order to find its way home but instead uses the sun as a compass to keep track of its home direction vector. The home vector can be inaccurate, so the ant also uses landmark recognition. More precisely, it takes snapshots and compass headings of some landmarks. To return home, the ant tries to line up the landmarks exactly as they were before it started wandering. This thesis introduces a navigation method based on reflex actions in sensor space. The sensor vector is made of the bearings of some landmarks, and the reflex action is a gradient descent with respect to the distance in sensor space between the current sensor vector and the target sensor vec- tor. Our theoretical analysis shows that except for some fully characterized pathological cases, any point is reachable from any other point by reflex action in the bearing sensor space provided the environment contains three landmarks and is free of obstacles. The trajectories of a robot using reflex navigation, like other image- based visual control strategies, do not correspond necessarily to the shortest paths on the ground, because the sensor error is minimized, not the moving distance on the ground. However, we show that the use of a sequence of waypoints in sensor space can address this problem. In order to identify relevant waypoints, we train a Self Organising Map (SOM) from a set of observations uniformly distributed with respect to the ground. This SOM provides a sense of location to the robot, and allows a form of path planning in sensor space. The navigation proposed system is analysed theoretically, and evaluated both in simulation and with experiments on a real robot.