Algorithms For Automatic And Robust Registration Of 3D Head Scans

wo methods for registering laser-scans of human heads and transforming them to a new semantically consistent topology defined by a user-provided template mesh are described. Both algorithms are stated within the Iterative Closest Point framework. The first method is based on finding landmark correspondences by iteratively registering the vicinity of a landmark with a re-weighted error function. Thin-plate spline interpolation is then used to deform the template mesh and finally the scan is resampled in the topology of the deformed template. The second algorithm employs a morphable shape model, which can be computed from a database of laser-scans using the first algorithm. It directly optimizes pose and shape of the morphable model. The use of the algorithm with PCA mixture models, where the shape is split up into regions each described by an individual subspace, is addressed. Mixture models require either blending or regularization strategies, both of which are described in detail. For both algorithms, strategies for filling in missing geometry for incomplete laser-scans are described. While an interpolation-based approach can be used to fill in small or smooth regions, the model-driven algorithm is capable of fitting a plausible complete head mesh to arbitrarily small geometry, which is known as "shape completion". The importance of regularization in the case of extreme shape completion is shown.

The Minimum Number of Points Taking Part in k-Sets in Sets of Unaligned Points

En este trabajo se da un ejemplo de un conjunto de n puntos situados en posición general, en el que se alcanza el mínimo número de puntos que pueden formar parte de algún k-set para todo k con 1menor que=kmenor quen/2. Se generaliza también, a puntos en posición no general, el resultado de Erdõs et al., 1973, sobre el mínimo número de puntos que pueden formar parte de algún k-set. The study of k- sets is a very relevant topic in the research area of computational geometry. The study of the maximum and minimum number of k-sets in sets of points of the plane in general position, specifically, has been developed at great length in the literature. With respect to the maximum number of k-sets, lower bounds for this maximum have been provided by Erdõs et al., Edelsbrunner and Welzl, and later by Toth. Dey also stated an upper bound for this maximum number of k-sets. With respect to the minimum number of k-set, this has been stated by Erdos el al. and, independently, by Lovasz et al. In this paper the authors give an example of a set of n points in the plane in general position (no three collinear), in which the minimum number of points that can take part in, at least, a k-set is attained for every k with 1 ≤ k < n/2. The authors also extend Erdos’s result about the minimum number of points in general position which can take part in a k-set to a set of n points not necessarily in general position. That is why this work complements the classic works we have mentioned before.

Metaheuristic approaches for MWT and MWPT problems

It is known that the Minimum Weight Triangulation problem is NP-hard. Also the complexity of the Minimum Weight Pseudo-Triangulation problem is unknown, yet it is suspected to be also NP-hard. Therefore we focused on the development of approximate algorithms to find high quality triangulations and pseudo-triangulations of minimum weight. In this work we propose two metaheuristics to solve these problems: Ant Colony Optimization (ACO) and Simulated Annealing (SA). For the experimental study we have created a set of instances for MWT and MWPT problems, since no reference to benchmarks for these problems were found in the literature. Through experimental evaluation, we assess the applicability of the ACO and SA metaheuristics for MWT and MWPT problems. These results are compared with those obtained from the application of deterministic algorithms for the same problems (Delaunay Triangulation for MWT and a Greedy algorithm respectively for MWT and MWPT).

Solving the minimum vertex floodlight problem with hybrid metaheuristics

In this paper we propose four approximation algorithms (metaheuristic based), for the Minimum Vertex Floodlight Set problem. Urrutia et al. [9] solved the combinatorial problem, although it is strongly believed that the algorithmic problem is NP-hard. We conclude that, on average, the minimum number of vertex floodlights needed to illuminate a orthogonal polygon with n vertices is n/4,29.

Connecting red cells in a bichromatic Voronoi diagram

Let S be a set of n + m sites, of which n are red and have weight wR, and m are blue and weigh wB. The objective of this paper is to calculate the minimum value of wR such that the union of the red Voronoi cells in the weighted Voronoi diagram of S is a connected set. The problem is solved for the multiplicatively-weighted Voronoi diagram in O((n+m)^2 log(nm)) time and for the additively-weighted Voronoi diagram in O(nmlog(nm)) time.

Improving shortest paths in the Delaunay triangulation

We study a problem about shortest paths in Delaunay triangulations. Given two nodes s; t in the Delaunay triangulation of a point set P, we look for a new point p that can be added, such that the shortest path from s to t in the Delaunay triangulation of P u{p} improves as much as possible. We study properties of the problem and give efficient algorithms to find such a point when the graph-distance used is Euclidean and for the link-distance. Several other variations of the problem are also discussed.

Aerial Coverage Path Planning applied to Mapping

In the last decade we have seen how small and light weight aerial platforms - aka, Mini Unmanned Aerial Vehicles (MUAV) - shipped with heterogeneous sensors have become a 'most wanted' Remote Sensing (RS) tool. Most of the off-the-shelf aerial systems found in the market provide way-point navigation. However, they do not rely on a tool that compute the aerial trajectories considering all the aspects that allow optimizing the aerial missions. One of the most demanded RS applications of MUAV is image surveying. The images acquired are typically used to build a high-resolution image, i.e., a mosaic of the workspace surface. Although, it may be applied to any other application where a sensor-based map must be computed. This thesis provides a study of this application and a set of solutions and methods to address this kind of aerial mission by using a fleet of MUAVs. In particular, a set of algorithms are proposed for map-based sampling, and aerial coverage path planning (ACPP). Regarding to map-based sampling, the approaches proposed consider workspaces with different shapes and surface characteristics. The workspace is sampled considering the sensor characteristics and a set of mission requirements. The algorithm applies different computational geometry approaches, providing a unique way to deal with workspaces with different shape and surface characteristics in order to be surveyed by one or more MUAVs. This feature introduces a previous optimization step before path planning. After that, the ACPP problem is theorized and a set of ACPP algorithms to compute the MUAVs trajectories are proposed. The problem addressed herein is the problem to coverage a wide area by using MUAVs with limited autonomy. Therefore, the mission must be accomplished in the shortest amount of time. The aerial survey is usually subject to a set of workspace restrictions, such as the take-off and landing positions as well as a safety distance between elements of the fleet. Moreover, it has to avoid forbidden zones to y. Three different algorithms have been studied to address this problem. The approaches studied are based on graph searching, heuristic and meta-heuristic approaches, e.g., mimic, evolutionary. Finally, an extended survey of field experiments applying the previous methods, as well as the materials and methods adopted in outdoor missions is presented. The reported outcomes demonstrate that the findings attained from this thesis improve ACPP mission for mapping purpose in an efficient and safe manner.

Geometric Study of the Weak Equilibrium in a Weighted Case for a Two-Dimensional Competition Game

In this work, an improvement of the results presented by [1] Abellanas et al. (Weak Equilibrium in a Spatial Model. International Journal of Game Theory, 40(3), 449-459) is discussed. Concretely, this paper investigates an abstract game of competition between two players that want to earn the maximum number of points from a finite set of points in the plane. It is assumed that the distribution of these points is not uniform, so an appropriate weight to each position is assigned. A definition of equilibrium which is weaker than the classical one is included in order to avoid the uniqueness of the equilibrium position typical of the Nash equilibrium in these kinds of games. The existence of this approximated equilibrium in the game is analyzed by means of computational geometry techniques.

Aerial Coverage Path Planning applied to Mapping

In the last decade we have seen how small and light weight aerial platforms - aka, Mini Unmanned Aerial Vehicles (MUAV) - shipped with heterogeneous sensors have become a 'most wanted' Remote Sensing (RS) tool. Most of the off-the-shelf aerial systems found in the market provide way-point navigation. However, they do not rely on a tool that compute the aerial trajectories considering all the aspects that allow optimizing the aerial missions. One of the most demanded RS applications of MUAV is image surveying. The images acquired are typically used to build a high-resolution image, i.e., a mosaic of the workspace surface. Although, it may be applied to any other application where a sensor-based map must be computed. This thesis provides a study of this application and a set of solutions and methods to address this kind of aerial mission by using a fleet of MUAVs. In particular, a set of algorithms are proposed for map-based sampling, and aerial coverage path planning (ACPP). Regarding to map-based sampling, the approaches proposed consider workspaces with different shapes and surface characteristics. The workspace is sampled considering the sensor characteristics and a set of mission requirements. The algorithm applies different computational geometry approaches, providing a unique way to deal with workspaces with different shape and surface characteristics in order to be surveyed by one or more MUAVs. This feature introduces a previous optimization step before path planning. After that, the ACPP problem is theorized and a set of ACPP algorithms to compute the MUAVs trajectories are proposed. The problem addressed herein is the problem to coverage a wide area by using MUAVs with limited autonomy. Therefore, the mission must be accomplished in the shortest amount of time. The aerial survey is usually subject to a set of workspace restrictions, such as the take-off and landing positions as well as a safety distance between elements of the fleet. Moreover, it has to avoid forbidden zones to y. Three different algorithms have been studied to address this problem. The approaches studied are based on graph searching, heuristic and meta-heuristic approaches, e.g., mimic, evolutionary. Finally, an extended survey of field experiments applying the previous methods, as well as the materials and methods adopted in outdoor missions is presented. The reported outcomes demonstrate that the findings attained from this thesis improve ACPP mission for mapping purpose in an efficient and safe manner.

Voronoi cells via linear inequality systems

The theory and methods of linear algebra are a useful alternative to those of convex geometry in the framework of Voronoi cells and diagrams, which constitute basic tools of computational geometry. As shown by Voigt and Weis in 2010, the Voronoi cells of a given set of sites T, which provide a tesselation of the space called Voronoi diagram when T is finite, are solution sets of linear inequality systems indexed by T. This paper exploits systematically this fact in order to obtain geometrical information on Voronoi cells from sets associated with T (convex and conical hulls, tangent cones and the characteristic cones of their linear representations). The particular cases of T being a curve, a closed convex set and a discrete set are analyzed in detail. We also include conclusions on Voronoi diagrams of arbitrary sets.

A methodology for evacuation route planning inside buildings using geospatial technology

Evacuation route planning is a fundamental task for building engineering projects. Safety regulations are established so that all occupants are driven on time out of a building to a secure place when faced with an emergency situation. As an example, Spanish building code requires the planning of evacuation routes on large and, usually, public buildings. Engineers often plan these routes on single building projects, repeatedly assigning clusters of rooms to each emergency exit in a trial-and-error process. But problems may arise for a building complex where distribution and use changes make visual analysis cumbersome and sometimes unfeasible. This problem could be solved by using well-known spatial analysis techniques, implemented as a specialized software able to partially emulate engineer reasoning. In this paper we propose and test an easily reproducible methodology that makes use of free and open source software components for solving a case study. We ran a complete test on a building floor at the University of Alicante (Spain). This institution offers a web service (WFS) that allows retrieval of 2D geometries from any building within its campus. We demonstrate how geospatial technologies and computational geometry algorithms can be used for automating the creation and optimization of evacuation routes. In our case study, the engineers’ task is to verify that the load capacity of each emergency exit does not exceed the standards specified by Spain’s current regulations. Using Dijkstra’s algorithm, we obtain the shortest paths from every room to the most appropriate emergency exit. Once these paths are calculated, engineers can run simulations and validate, based on path statistics, different cluster configurations. Techniques and tools applied in this research would be helpful in the design and risk management phases of any complex building project.

Application of the Artificial Intelligence Algorithms for System Analysis of Multi Dimension Physiological Data for Developing Polyparametric Information System of Public Health Diagnostics

The polyparametric intelligence information system for diagnostics human functional state in medicine and public health is developed. The essence of the system consists in polyparametric describing of human functional state with the unified set of physiological parameters and using the polyparametric cognitive model developed as the tool for a system analysis of multitude data and diagnostics of a human functional state. The model is developed on the basis of general principles geometry and symmetry by algorithms of artificial intelligence systems. The architecture of the system is represented. The model allows analyzing traditional signs - absolute values of electrophysiological parameters and new signs generated by the model – relationships of ones. The classification of physiological multidimensional data is made with a transformer of the model. The results are presented to a physician in a form of visual graph – a pattern individual functional state. This graph allows performing clinical syndrome analysis. A level of human functional state is defined in the case of the developed standard (“ideal”) functional state. The complete formalization of results makes it possible to accumulate physiological data and to analyze them by mathematics methods.

Application of the Artificial Intelligence Algorithms with a Cognitive Graphic as a Tool for a System Analysis of Electrophysiological Processes

Summarizing the accumulated experience for a long time in the polyparametric cognitive modeling of different physiological processes (electrocardiogram, electroencephalogram, electroreovasogram and others) and the development on this basis some diagnostics methods give ground for formulating a new methodology of the system analysis in biology. The gist of the methodology consists of parametrization of fractals of electrophysiological processes, matrix description of functional state of an object with a unified set of parameters, construction of the polyparametric cognitive geometric model with artificial intelligence algorithms. The geometry model enables to display the parameter relationships are adequate to requirements of the system approach. The objective character of the elements of the models and high degree of formalization which facilitate the use of the mathematical methods are advantages of these models. At the same time the geometric images are easily interpreted in physiological and clinical terms. The polyparametric modeling is an object oriented tool possessed advances functional facilities and some principal features.

Структурная Модель Полутонового Изображения и ее Использование в Задаче Сегментации Изображений

Предложена структурная модель полутонового изображения. Структурная модель предполагает инвариантное относительно аффинных преобразований описание выделенных в изображении объектов. Форма объекта полностью определяет его описание и представлена его граничным контуром и функцией оптической плотности, которая определена в пределах этого контура. Предложено определение контура полутонового изображения как последовательности, состоящей из отрезков прямых и дуг кривых, причем эти отрезки прямых и дуги кривых являются особыми линиями поверхности, которая соответствует полутоновому изображению. Рассматривается пример использования структурной модели в процессе обработки полутоновых изображений медицинских препаратов, полученных по методу Кирлиан.

Approximating the MaxMin and MinMax Area Triangulations using Angular Constraints

* A preliminary version of this paper was presented at XI Encuentros de Geometr´ia Computacional, Santander, Spain, June 2005.