Aquest treball proposa una nova arquitectura de control amb coordinació distribuïda per a un robot mòbil (ARMADiCo). La metodologia de coordinació distribuïda consisteix en dos passos: el primer determina quin és l'agent que guanya el recurs basat en el càlcul privat de la utilitat i el segon, com es fa el canvi del recurs per evitar comportaments abruptes del robot.Aquesta arquitectura ha estat concebuda per facilitar la introducció de nous components hardware i software, definint un patró de disseny d'agents que captura les característiques comunes dels agents. Aquest patró ha portat al desenvolupament d'una arquitectura modular dins l'agent que permet la separació dels diferents mètodes utilitzats per aconseguir els objectius, la col·laboració, la competició i la coordinació de recursos.ARMADiCo s'ha provat en un robot Pioneer 2DX de MobileRobots Inc.. S'han fet diversos experiments i els resultats han demostrat que s'han aconseguit les característiques proposades per l'arquitectura. / This work proposes a new mobile robot control architecture with distributed coordination (ARMADiCo). The distributed coordination methodology consists of two steps: the first determines which agent wins the resource based on a private utility computation, and the second how the resource exchange is carried out in order to avoid abrupt robot behaviors. This architecture has been conceived to make easy the introduction of new hardware and software components and an agent design pattern has been defined in order to capture the agents' common features. This pattern has also lead to the development of a modular architecture inside the agent that allows separation of the different methods of achieving goals, collaboration and competition as well as resource coordination.ARMADiCo has been tested on a MobileRobots Inc. Pioneer 2DX robot. Several experiments have been carried out and the results show that the proposed features of the architecture have been accomplished.

Aquesta tesi tracta el problema de l'aprenentatge automàtic d'entorns estructurats n robòtica mòbil. Particularment, l'extracció de característiques a partir dels senyals dels sensors, la construcció autònoma de mapes, i l'autolocalització de robots.S'estudien els fonaments matemàtics necessaris per a l'extracció de característiques a partir d'imatges i registres d'un làser, els quals permeten la identificació unívoca dels elements de l'entorn. Els atributs extrets a partir del senyal d'un sol sensor poden ser insuficients quan es volen caracteritzar els elements de l'entorn de forma invariant; això es pot millorar combinant informació de múltiples fonts. Es presenta un nou algorisme per la fusió d'informació complementaria extreta de dos mòduls de visió de baix nivell.Aquesta fusió d'informació produeix descripcions més completes dels objectes de l'entorn, els quals poden ser seguits i apresos dins el context de la robòtica mòbil. Les variacions en les condicions d'il·luminació i les oclusions fan que l'associació de dades en visió per computador sigui una tasca difícil de completar.Tot i això, l'ús de restriccions geomètriques i fotogramètriques permeten reduir la cerca de correspondències entre imatges successives; i al centrar l'atenció en un reduït nombre de característiques, aquestes poden ser seguides en imatges successives, simplificant així el problema d'associació de dades. Es recalquen les tècniques de la geometria de múltiples vistes que són rellevants pel còmput d'una estimació inicial de la posició dels elements de l'entorn, el que permet la reconstrucció del moviment del robot entre imatges successives; situació desitjable quan no existeix odometria o quan las seves lectures són poc fiables.Quan els elements de l'entorn s'han extret i identificat, la segona part del problema consisteix en utilitzar aquestes observacions tant per estimar la posició del robot, com per refinar l'estimació dels mateixos elements de l'entorn. El moviment del robot i les lectures dels sensors es consideren com dos processos estocàstics, i el problema es tracta des del punt de vista de la teoria d'estimació, on el soroll inherent als sensors i al moviment del robot es consideren com a seqüències aleatòries.El principal inconvenient existent en l'ús de tècniques d'estimació pel còmput concurrent de la posició del robot i la construcció d'un mapa, és que fins ara s'ha considerat la seva aplicació únicament en entorns estàtics, i que el seu ús en situacions més realistes ofereix poca robustesa. Es proposa un conjunt de funcions per avaluar la qualitat temporal de les observacions per tal de resoldre les situacions en que les observacions dels elements de l'entorn no siguin consistents en el temps. Es mostra com la utilització d'aquestes proves de qualitat temporal conjuntament amb les proves de compatibilitat espacial milloren els resultats quan es fen servir amb un mètode d'estimació òptima de la construcció concurrent de mapes i l'autolocalització de robots.La idea principal consisteix en emprar un històric dels errors en l'associació de les dades per calcular la possibilitat d'incórrer en nous errors d'associació; i excloure del mapa aquells elements dels quals les observacions no siguin consistents.Es posa especial atenció en el fet que l'eliminació dels elements inconsistents del mapa no violi les propietats dels algorismes de construcció concurrent de mapes i autolocalització descrits en la literatura; és a dir, convergència assimptòtica i correlació completa.Aquesta tesi proporciona també un profund anàlisi del model de construcció concurrent de mapes i autolocalització totalment correlat des d'un punt de vista de la teoria de control de sistemes. Partint del fet que el filtre de Kalman no és més que un estimador òptim, s'analitzen les implicacions de tenir un vector d'estats que es revisa a partir de mesures totalment correladas.Es revela de manera teòrica i amb experiments les limitacions d'utilitzar un enfocament per la construcció concurrent de mapes i l'autolocalització a partir de mesures totalment correladas.El fet de tenir un model parcialment observable inhibeix la reconstrucció total de l'espai d'estats, produint tant mateix una estimació de la posició dels elements de l'entorn que depèn en tot cas de les observacions inicials, i que no garanteix la convergència a una matriu de covariància definida positivament.D'altra banda, el fet de tenir un vector d'estats parcialment controlable fa que, desprès d'un reduït nombre d'iteracions el filtre cregui tenir una estimació perfecta de l'estat dels elements de l'entorn; amb els corresponents guanys de Kalman convergint a zero. Per tant, desprès d'un reduït nombre d'iteracions del filtre, els innovacions no s'utilitzen més. Es mostra com reduir els efectes de la correlació total i de la controlabilitat parcial. A més a més, suposant que el filtre de Kalman és un observador òptim per a la reconstrucció dels estats, és pertinent construir un regulador òptim que permeti conduir el robot el més a prop possible a una trajectòria desitjada durant la construcció d'un mapa. Es mostra com la dualitat existent entre l'observabilitat i la controlabilitat es pot fer servir en el disseny d'aquest regulador òptim.Qualsevol algorisme de construcció concurrent de mapes i autolocalització de robots mòbils que s'ha d'usar en un entorn real ha de ser capaç de relacionar les observacions i els seus corresponents elements del mapa de manera expedita. Algunes de les proves de compatibilitat de les observacions són costoses des del punt de vista de la seva complexitat computacional, i la seva aplicació s'ha de dissenyar amb especial atenció. Es comenten els costos computacionals de les diferents proves de compatibilitat entre observacions; així com altres característiques desitjables de l'estructura de dades que es fa servir per a la construcció del mapa. A més a més es proposen una sèrie de tasques que han de realitzar-se durant l'associació de dades. Començant per les proves de compatibilitat amb un model bàsic dels elements del mapa, i continuant amb la reducció de l'espai de cerca quan es generen hipòtesis d'associació, així com les proves espacial i temporal d'associació de dades.El treball que es presenta en aquesta tesi proposa noves tècniques en àrees de l'enginyera i ciències computacionals, que van des de nous algorismes per la visió per computador, a idees novells de la construcció concurrent de mapes i l'autolocalització de robots mòbils. Les contribucions principals són la proposta d'una nova tècnica per la fusió de dades visuals; la formulació d'un nou algorisme per la construcció concurrent de mapes i l'autolocalització de robots que considera la qualitat temporal dels elements del mapa; nous resultats teòrics en el nivell de reconstrucció possible quan es construeixen mapes a partir d'observacions totalment correladas; i les tècniques necessàries per pal·liar els efectes de l'observabilitat i la controlabilitat parcials, així com els efectes de les no linealitats en la solució del problema de construcció concurrent de mapes i de l'autolocalització. / Esta tesis aborda el problema del aprendizaje automático de entornos estructurados en robótica móvil. Particularmente, la extracción de características a partir de las se nales de los censores, la construcción autónoma de mapas, y la autolocalización de robots.Se estudian los fundamentos matemáticos necesarios para la extracción de características a partir de imágenes y registros de un láser, las cuales permiten la identificación unívoca de los elementos del entorno. Los atributos extraídos a partir de la se nal de un solo sensor pueden ser insuficientes a la hora de caracterizar los elementos del entorno de forma invariante; lo que conlleva a la combinación de información de múltiples fuentes. Se presenta un nuevo algoritmo para la fusión de información complementaria extraída de dos módulos de visión de bajo nivel. Esta fusión de información produce descripciones más completas de los objetos presentes en el entorno, los cuales pueden ser seguidos y aprendidos en el contexto de la robótica móvil.Las variaciones en las condiciones de iluminación y las oclusiones hacen que la asociación de datos en visión por computador sea una tarea difícil de llevar a cabo. Sin embargo, el uso de restricciones geométricas y fotogramétricas permiten reducir la búsqueda de correspondencias entre imágenes; y al centrar la atención en un reducido número de características, estas pueden ser seguidas en imágenes sucesivas, simplificando así el problema de asociación de datos. Se hace hincapié en las técnicas de la geometría de múltiples vistas relevantes para el cómputo de una estimación inicial de la posición de los elementos del entorno, lo cual permite la reconstrucción del movimientodel robot entre imágenes sucesivas; situación deseable cuando se carece de odometría o cuando sus lecturas son poco fiables.Una vez que los elementos del entorno han sido extraídos e identificados, la segunda parte del problema consiste en usar estas observaciones tanto para estimar la posición del robot, como para refinar la estimación de los mismos elementos del entorno. El movimiento del robot y las lecturas de los sensores se consideran como dos procesos estocásticos, y el problema se aborda desde el punto de vista de la teoría de estimación, en donde el ruido inherente a los sensores y al movimiento del robot se consideran como secuencias aleatorias.La principal desventaja existente en el uso de técnicas de estimación para el cómputo concurrente de la posición del robot y la construcción de un mapa, es que hasta ahora se ha considerado su uso en entornos estáticos únicamente, y que su aplicación en situaciones más realistas carece de robustez.Se propone un conjunto de funciones para evaluar la calidad temporal de las observaciones con el fin de solventar aquellas situaciones en que las observaciones de los elementos del entorno no sean consistentes en el tiempo.Se muestra como el uso de estas pruebas de calidad temporal junto con las pruebas de compatibilidad espacial existentes mejora los resultados al usar un método de estimación óptima para la construcción concurrente de mapas y la autolocalización de robots. La idea principal consiste en usar un históricode los errores en la asociación de datos para el cómputo de la posibilidad de incurrir en nuevos errores de asociación; y eliminar del mapa aquellos elementos cuyas observaciones no sean consistentes.Se presta especial atención a que la eliminación de elementos inconsistentes del mapa no viole las propiedades de los algoritmos de construcción concurrente de mapas y autolocalización descritos en la literatura; es decir, convergencia asintótica y correlación completa.Esta tesis proporciona a su vez un análisis en profundidad del modelo de construcción concurrente de mapas y autolocalización totalmente correlado desde un punto de vista de la teoría de control de sistemas. Partiendo del hecho de que el filtro de Kalman no es otra cosa que un estimador óptimo, se analizan las implicaciones de tener un vector de estados que se revisa a partir de mediciones totalmente correladas. Se revela de forma teórica y con experimentos las limitaciones de usar un enfoque para la construcción concurrente de mapas y autolocalización a partir de mediciones totalmente correladas.El hecho de tener un modelo parcialmente observable inhibe la reconstrucción total del espacio de estados, produciendo a su vez una estimación de la posición de los elementos del entorno que dependerá en todo caso de las observaciones iniciales, y que no garantiza la convergencia a una matriz de covarianza positivamente definida. Por otro lado, el hecho de tener un vector de estados parcialmente controlable, produce después de un reducido número de iteraciones que el filtro crea tener una estimación perfecta del estado de los elementos del entorno; con sus correspondientes ganancias de Kalman convergiendo a cero. Esto es, después de un peque no número de iteraciones del filtro, las innovaciones no se usan. Se muestra como reducir los efectos de la correlación total y la controlabilidad parcial. Además, dado que el filtro de Kalman es un observador óptimo para la reconstrucción de los estados, es pertinente construir un regulador óptimo que permita conducir al robot lo más cerca posible de una trayectoria deseada durante la construcción de un mapa. Se muestra como la dualidad existente entre la observabilidad y la controlabilidad se puede emplear en el diseño de este regulador óptimo. Cualquier algoritmo de construcción concurrente de mapas y autolocalización de robots móviles que deba funcionar en un entorno real deberá ser capaz de relacionar las observaciones y sus correspondientes elementos del mapa de manera expedita. Algunas de las pruebas de compatibilidad de las observaciones son caras desde el punto de vista de su complejidad computacional, y su aplicación debe diseñarse con riguroso cuidado. Se comentan los costes computacionales de las distintas pruebas de compatibilidad entre observaciones; así como otras características deseadas de la estructura de datos elegida para la construcción del mapa. Además, se propone una serie de tareas que debe llevarse a cabo durante la asociación de datos. Partiendo por las pruebas de compatibilidad con un modelo básico de los elementos del mapa, y continuando con la reducción del espacio de búsqueda al generar hipótesis de asociación, así como las pruebas espacial y temporal de asociación de datos.El trabajo que se presenta en esta tesis propone nuevas técnicas en áreas de la ingeniería y las ciencias computacionales, que van desde nuevos algoritmos de visión por computador, a ideas noveles en la construcción concurrente de mapas y la autolocalización de robots móviles. Las contribuciones principales son la propuesta de una nueva técnica para la fusión de datos visuales; la formulación de un nuevo algoritmo para la construcción concurrente de mapas y autolocalización de robots que toma en cuenta la calidad temporal de los elementos del mapa; nuevos resultados teóricos en el grado de reconstrucción posible al construir mapas a partir de observaciones totalmente correladas; y las técnicas necesarias para paliar los efectos de la observabilidad y controlabilidad parciales, así como los efectos de las no linealidades en la solución del problema de construcción concurrente de mapas y autolocalización. / This thesis focuses on the various aspects of autonomous environment learning for indoor service robots. Particularly, on landmark extraction from sensor data, autonomous map building, and robot localization. To univocally identify landmarks from sensor data, we study several landmark representations, and the mathematical foundation necessary to extract the features that build them from images and laser range data. The features extracted from just one sensor may not suce in the invariant characterization of landmarks and objects, pushing for the combination of information from multiple sources. We present a new algorithm that fuses complementary information from two low level vision modules into coherent object models that can be tracked and learned in a mobile robotics context. Illumination conditions and occlusions are the most prominent artifactsthat hinder data association in computer vision. By using photogrammetric and geometric constraints we restrict the search for landmark matches in successive images, and by locking our interest in one or a set of landmarks in the scene, we track those landmarks along successive frames, reducing considerably the data association problem. We concentrate on those tools from the geometry of multiple views that are relevant to the computation of initial landmark location estimates for coarse motion recovery; a desirable characteristic when odometry is not available or is highly unreliable.Once landmarks are accurately extracted and identied, the second part of the problem is to use these observations for the localization of the robot, as well as the renement of the landmark location estimates. We consider robot motion and sensor observations as stochastic processes, and treat the problem from an estimation theoretic point of view, dealing with noise by using probabilistic methods.The main drawback we encounter is that current estimation techniques have been devised for static environments, and that they lack robustness in more realistic situations. To aid in those situations in which landmark observations might not be consistent in time, we propose a new set of temporal landmark quality functions, and show how by incorporating these functions in the data association tests, the overall estimation-theoretic approach to map building and localization is improved. The basic idea consists on using the history of data association mismatches for the computation of the likelihood of future data association, together with the spatial compatibility tests already available.Special attention is paid in that the removal of spurious landmarks from the map does not violate the basic convergence properties of the localization and map building algorithms already described in the literature; namely, asymptotic convergence and full correlation.The thesis also gives an in depth analysis of the fully correlated model to localization and map building from a control systems theory point of view. Considering the fact that the Kalman .lter is nothing else but an optimal observer, we analyze the implications of having a state vector that is being revised by fully correlated noise measurements. We end up revealingtheoretically and with experiments the strong limitations of using a fully correlated noise driven estimation theoretic approach to map building and localization in relation to the total number of landmarks used. Partial observability hinders full reconstructibility of the state space, making the .nal map estimate dependant on the initial observations, and does not guarantee convergence to a positive de nite covariance matrix. Partial controllability on the other hand, makes the .lter beleive after a number of iterations, that it has accurate estimates of the landmark states, with their corresponding Kalman gains converging to zero. That is, after a few steps, innovations are useless. We show how to palliate the e.ects of full correlationand partial controllability. Furthermore, given that the Kalman .lter is an optimal observer for the reconstruction of fully correlated states; it seems pertinent to build an optimal regulator in order to keep the robot as close as possible to a desired motion path when building a map. We show also how the duality between observability and controllability can be exploited in designing such an optimal regulator. Any map building and localization algorithm for mobile robotics that is to work in real time must be able to relate observations and model matches in an expeditious way. Some of the landmark compatibility tests are computationally expensive, and their application has to be carefully designed. We touch upon the time complexity issues of the various landmark compatibility tests used, and also on the desirable properties of our chosen map data structure.Furthermore, we propose a series of tasks that must be handled when dealing with landmark data association. From model compatibility tests, to search space reduction and hypothesis formation, to the actual association of observations and models. The work presented in this thesis spans several areas of engineering and computer science, from new computer vision algorithms, to novel ideas in mobile robot localization and map building. The key contributions are the proposal of a new technique to fuse visual data; the formulation of new algorithms to concurrent localization and map building that take into account temporal landmark quality; new theoretical results on the degree of reconstruction possible when building maps from fully correlated observations; and the necessary techniques to palliate partial observability, partial controllability, and the nonlinear e.ects when solving the simultaneous localization and map building problem.

Aquesta tesi tracta sobre el problema de la navegació per a vehicles submarins autònoms que operen en entorns artificials estructurats com ara ports, canals, plataformes marines i altres escenaris similars. A partir d'una estimació precisa de la posició en aquests entorns, les capacitats dels vehicles submarins s'incrementen notablement i s'obre una porta al seu funcionament autònom. El manteniment, inspecció i vigilància d'instal lacions marines són alguns exemples de possibles aplicacions. Les principals contribucions d'aquesta tesi consisteixen per una banda en el desenvolupament de diferents sistemes de localització per a aquelles situacions on es disposa d'un mapa previ de l'entorn i per l'altra en el desenvolupament d'una nova solució al problema de la Localització i Construcció Simultània de Mapes (SLAM en les seves sigles en anglès), la finalitat del qual és fer que un vehicle autònom creï un mapa de l'entorn desconegut que el rodeja i, al mateix temps, utilitzi aquest mapa per a determinar la seva pròpia posició. S'ha escollit un sonar d'imatges d'escaneig mecànic com a sensor principal per a aquest treball tant pel seu relatiu baix cost com per la seva capacitat per produir una representació detallada de l'entorn. Per altra banda, les particularitats de la seva operació i, especialment, la baixa freqúència a la que es produeixen les mesures, constitueixen els principals inconvenients que s'han hagut d'abordar en les estratègies de localització proposades. Les solucions adoptades per aquests problemes constitueixen una altra contribució d'aquesta tesi. El desenvolupament de vehicles autònoms i el seu ús com a plataformes experimentals és un altre aspecte important d'aquest treball. Experiments portats a terme tant en el laboratori com en escenaris reals d'aplicació han proporcionat les dades necessàries per a provar i avaluar els diferents sistemes de localització proposats. / This thesis is concerned with the navigation problem for autonomous underwater vehicles operating in artificial structured environments like harbours, marinas, marine platforms and other similar scenarios. Obtaining an accurate position in such scenarios would notably increase the capabilities of underwater vehicles and open the door to real autonomous operation. Maintenance, inspection and surveillance of marine installations are only a few examples of possible applications. The principal contributions of this thesis consist of the development of different localization systems for those situations in which an a priori map of the environment is available but, in particular, in the development of a novel solution to the Simultaneous Localization and Mapping (SLAM) problem. This solution pursues the objective of providing an autonomous vehicle with the ability to build a map within an unknown environment while, at the same time, using this same map to keep track of its current position. A mechanical scanning imaging sonar has been chosen as the principal sensor for this work because of its relative low cost and its capacity to produce a rich representation of the environment. On the other hand, the particularities of its operation and, especially, its low scanning rate, have presented many challenges during the development of this proposed localization strategies. The solutions adopted to address these problems constitute another contribution in this thesis. The development of underwater vehicles and their use as experimental platforms is another important aspect of the research work presented here. Experiments carried out in both laboratory and real application environments have provided the different datasets necessary for the testing and evaluation of the different localization approaches.

Darrerament, l'interès pel desenvolupament d'aplicacions amb robots submarins autònoms (AUV) ha crescut de forma considerable. Els AUVs són atractius gràcies al seu tamany i el fet que no necessiten un operador humà per pilotar-los. Tot i això, és impossible comparar, en termes d'eficiència i flexibilitat, l'habilitat d'un pilot humà amb les escasses capacitats operatives que ofereixen els AUVs actuals. L'utilització de AUVs per cobrir grans àrees implica resoldre problemes complexos, especialment si es desitja que el nostre robot reaccioni en temps real a canvis sobtats en les condicions de treball. Per aquestes raons, el desenvolupament de sistemes de control autònom amb l'objectiu de millorar aquestes capacitats ha esdevingut una prioritat. Aquesta tesi tracta sobre el problema de la presa de decisions utilizant AUVs. El treball presentat es centra en l'estudi, disseny i aplicació de comportaments per a AUVs utilitzant tècniques d'aprenentatge per reforç (RL). La contribució principal d'aquesta tesi consisteix en l'aplicació de diverses tècniques de RL per tal de millorar l'autonomia dels robots submarins, amb l'objectiu final de demostrar la viabilitat d'aquests algoritmes per aprendre tasques submarines autònomes en temps real. En RL, el robot intenta maximitzar un reforç escalar obtingut com a conseqüència de la seva interacció amb l'entorn. L'objectiu és trobar una política òptima que relaciona tots els estats possibles amb les accions a executar per a cada estat que maximitzen la suma de reforços totals. Així, aquesta tesi investiga principalment dues tipologies d'algoritmes basats en RL: mètodes basats en funcions de valor (VF) i mètodes basats en el gradient (PG). Els resultats experimentals finals mostren el robot submarí Ictineu en una tasca autònoma real de seguiment de cables submarins. Per portar-la a terme, s'ha dissenyat un algoritme anomenat mètode d'Actor i Crític (AC), fruit de la fusió de mètodes VF amb tècniques de PG. / A considerable interest has arisen around Autonomous Underwater Vehicle (AUV) applications. AUVs are very useful because of their size and their independence from human operators. However, comparison with humans in terms of efficiency and flexibility is often unequal. The development of autonomous control systems able to deal with such issues becomes a priority. The use of AUVs for covering large unknown dynamic underwater areas is a very complex problem, mainly when the AUV is required to react in real time to unpredictable changes in the environment. This thesis is concerned with the field of AUVs and the problem of action-decision. The methodology chosen to solve this problem is Reinforcement Learning (RL). The work presented here focuses on the study and development of RL-based behaviors and their application to AUVs in real robotic tasks. The principal contribution of this thesis is the application of different RL techniques for autonomy improvement of an AUV, with the final purpose of demonstrating the feasibility of learning algorithms to help AUVs perform autonomous tasks. In RL, the robot tries to maximize a scalar evaluation obtained as a result of its interaction with the environment with the aim of finding an optimal policy to map the state of the environment to an action which in turn will maximize the accumulated future rewards. Thus, this dissertation is based on the principals of RL theory, surveying the two main classes of RL algorithms: Value Function (VF)-based methods and Policy Gradient (PG)-based techniques. A particular class of algorithms, Actor-Critic methods, born of the combination of PG algorithms with VF methods, is used for the final experimental results of this thesis: a real underwater task in which the underwater robot Ictineu AUV learns to perform an autonomous cable tracking task.

Un dels camps de la robòtica que estan despertant gran interès per part de la comunitat científica és el dels entorns multirobot. Aquest nom genèric inclou diferents tipus de sistemes amb característiques i problemàtiques força diferenciades. En aquest treball s'utilitza aquest terme per fer referència a cel·les robotitzades composades per més d'un robot treballant coordinadament, entès robot com braç manipulador. En aquesta tesis s'han abordat diferents aspectes relacionats amb la cinemàtica i el control de sistemes multirobot. Dins de la cinemàtica s'han estudiat en detall les característiques de l'espai del treball i les mesures de manipulabilitat dels sistemes multirobot. En aquesta línia s'ha proposat una nova metodologia per estudiar l'espai de treball del sistemes multirobot basada en els conceptes de figura destra i figura realitzable. Aquestes dues figures geomètriques generades a partir dels espais de treball individuals, permeten descriure l'espai de treball com la intersecció de figures geomètriques. Aquest interpretació permet dissenyar de forma intuïtiva cel·les multirobot en les que hi ha manipulació conjunta. La metodologia s'ha implementat en el cas de dos tipus de robots, SCARA, i PUMA.Dins els aspectes de dinàmica i control tractats en la tesi, cal diferenciar els referents a la dinàmica dels sistemes multirobot i els referents als sistemes en els que cadascun dels robots té un control de posició.En l'àmbit de la dinàmica pròpiament dita s'ha analitzat en detall la formulació en equacions algebraic diferencials (DAE) dels sistemes mecànics amb restriccions holònomes, cas genèric dins el que s'engloben els sistemes multirobot amb manipulació rígida d'objectes rígids. Aquesta formulació permet obtenir el comportament del sistema a partir de les equacions que descriuen el comportament individual de cadascun dels robots i dels conjunt de restriccions cinemàtiques que actuen sobre el sistema.En el cas dels robots amb control de posició, el comportament i el control presenten unes característiques totalment diferents. Per aquest tipus d'entorns s'han proposat, dos enfocs de control diferents: un basat en el control híbrid, i un altre basat en control d'impedància. En l'enfoc de control híbrid es descompossa el sistema en eixos sobre els que s'aplica control de posició i eixos en els que s'aplica control de força, aquests darrers corresponen a les forces internes. Aquest plantejament és totalment centralitzat, es a dir, hi ha un element central encarregat de controlar el comportament del sistema. Com a principal aportació dins aquesta línia, s'ha proposat una metodologia per identificar el comportament de les forces internes que actuen sobre el sistema.Com alternativa, al control híbrid s'ha desenvolupat un esquema de control basat en la imposició d'un comportament d'impedància en cadascun dels robots. Aquest plantejament és totalment desacoblat, és a dir cadascun dels controladors realitza la seva funció sense necessitat d'un intercanvi d'informació amb la resta de controladors. La principal aportació dins aquesta línia és que el comportament d'impedància s'ha plantejat sobre SE(3), el que fa que els comportaments obtinguts estiguin d'acord amb la topologia de l'espai de treball.La tesi finalitza amb una presentació de les principals conclusions i línies de treball obertes per treballs futurs. / One field in today robotics in which a lot of people are working is the one concerning multirobot systems. This generic name includes different kinds of systems, each one with its own characteristics and problems. In this work "multirobot system" refers to work cells composed by several robots working in a coordinated way. In this thesis several aspects related with kinematics and control of multirobot systems has been studied. Inside cinematic the workspace and manipulability measures for multirobots systems have been studied in detail. A new methodology to study multirobot systems workspace has been proposed, this approach is based on the dexterous figure and the reachable figure concepts. These two geometric figures are obtained from the individual workspace. A key issue in this new approach is the fact the multirobot workspace can be described as the intersection of several geometric figures, this introduces a new understanding which can be of great interest in the geometric design of multirobot workcell. This methodology has been used in the analysis and design of workcells composed by SCARA and PUMA robots.Inside dynamics and control aspects, the dissertation includes two different problems, one related with multirobot dynamics modeling and control and another related with control of multirobot systems where the different robots are position controlled.In the dynamic related aspects, a new formulation based on the formulation of robotic system with holonomic constraints as Diferential Algebraic Equation Systems (DAE). One particular case of this generic kind of systems is multirobot systems which rigidly manipulate a rigid object. This approach allows obtaining the system behavior from the dynamic equations describing the individual behavior and the set of equations describing the holonomic constrains over the systems.For the multirobot systems formed by position controlled robots, two different strategies have been proposed and tested in a real workcell. The first one is based on the hybrid control approach and the second one is based on the impedance control approach.The hybrid control approach decomposes the space in several axes, some of them are controlled in position and the others are force controlled. These force controlled axes are the ones related with internal force control. Hybrid control follows a centralized approach, so a central coordination element is needed. Inside this area a new methodology to identify and control the internal forces dynamics has been proposed.A different approach has been proposed, impedance control is based on defining an individual behaviour for each robot. This approach is decoupled by definition, in other works each robot do not need information from the other robots. Most important contributions inside this area, is the fact that the individual behaviour is defined over SE(3), this means that obtained movements are topologicaly coherent.The dissertation concludes with some conclusions and future works.

Aquesta Tesi que pretén proporcionar un conjunt de tècniques per enfrontar-se al problema que suposa la variació del color en les imatges preses des d'una plataforma mòbil per causa del canvi en les condicions d'il·luminació entre diverses vistes d'una certa escena preses en diferents instants i posicions. També tracta el problema de la segmentació de imatges de color per a poder-les utilitzar en tasques associades a les capacitats d'un robot mòbil, com ara la identificació d'objectes o la recuperació d'imatges d'una gran base de dades.Per dur a terme aquests objectius, primerament s'estableix matemàticament la transformació entre colors degut a variacions d'il·luminació. Així es proposa un model continu per la generació del senyal de color com a generalització natural d'altres propostes anteriors. D'aquesta manera es pot estudiar matemàticament i amb generalitat les condicions per l'existència, unicitat i bon comportament de les solucions, i expressar qualsevol tipus d'aplicació entre colors, independentment del tipus de discretització. Així, queda palès la relació íntima entre el problema de la invariància de color i el de la recuperació espectral, que també es planteja a la pràctica. El model desenvolupat es contrasta numèricament amb els de regressió lineal, en termes d'errors de predicció.Un cop establert el model general, s'opta per un model lineal simplificat a l'hora de realitzar els càlculs pràctics i permet alleugerir el nombre dels mateixos. En particular, el mètode proposat es basa en trobar la transformació més probable entre dues imatges a partir del càlcul d'un conjunt de transformacions possibles i de l'estimació de la freqüència i grau d'efectivitat de cadascuna d'elles. Posteriorment, es selecciona el millor candidat d'acord amb la seva versemblança. L'aplicació resultant serveix per transformar els colors de la imatge tal i com es veuria sota les condicions d'il·luminació canòniques.Una vegada el color de les imatges d'una mateixa escena es manté constant, cal procedir a la seva segmentació per extreure'n la informació corresponent a les regions amb color homogeni. En aquesta Tesi es suggereix un algorisme basat en la partició de l'arbre d'expansió mínima d'una imatge mitjançant una mesura local de la probabilitat de les unions entre components. La idea és arribar a una segmentació coherent amb les regions reals, compromís entre particions amb moltes components (sobresegmentades) i amb molt poques (subsegmentades). Un altre objectiu és que l'algorisme sigui prou ràpid com per ser útil en aplicacions de robòtica mòbil. Aquesta característica s'assoleix amb un plantejament local del creixement de regions, tot i que el resultat presenti caràcters globals (color). La possible sobresegmentació es suavitza gràcies al factor probabilístic introduït.L'algorisme de segmentació també hauria de generar segmentacions estables en el temps. Així, l'algorisme referit s'ha ampliat incloent-hi un pas intermedi entre segmentacions que permet de relacionar regions semblants en imatges diferents i propagar cap endavant els reagrupaments de regions fets en anteriors imatges, així si en una imatge unes regions s'agrupen formant-ne una de sola, les regions corresponents en la imatge següent també s'han d'agrupar juntes. D'aquesta manera, dues segmentacions correlatives s'assemblen i es pot mantenir estable la segmentació d'una seqüència.Finalment, es planteja el problema de comparar imatges a partir del seu contingut. Aquesta Tesi es concentra només en la informació de color i, a més de investigar la millor distància entre segmentacions, es busca també mostrar com la invariància de color afecta les segmentacions.Els resultats obtinguts per cada objectiu proposat en aquesta Tesi avalen els punts de vista defensats, i mostren la utilitat dels algorismes, així com el model de color tant per la recuperació espectral com pel càlcul explícit de les transformacions entre colors. / This Thesis endeavors providing a set of techniques for facing the problem of color variation in images taken from a mobile platform and caused by the change in the conditions of lighting among several views of a certain scene taken at different instants and positions. It also treats the problem of segmenting color images in order to use them in tasks associated with the capacities of a mobile robot, such as object identification or image retrieval from a large database.In order to carry out these goals, first transformation among colors due to light variations is mathematically established. Thus, a continuous model for the generation of color is proposed as a natural generalization of other former models. In this way, conditions for the existence, uniqueness, and good behavior of the solutions can be mathematically studied with a great generality, and any type of applications among colors can be expressed independently of the discretization scheme applied. Thus, the intimate relation among the problem of color invariance and that of spectral recovery is made evident and studied in practice too. The developed model is numerically contrasted with those of a least squares linear regression in terms of prediction errors.Once the general model is established, a simplified linear version is chosen instead for carrying out the practical calculations while lightening the number of them. In particular, the proposed method is based on finding the likeliest transformation between two images from the calculation of a set of feasible transformations and the estimation of the frequency and the effectiveness degree of each of them. Later, the best candidate is selected in accordance with its likelihood. The resulting application is then able to transform the image colors as they would be seen under the canonical light.After keeping the image colors from a scene constant, it is necessary to proceed to their segmentation to extract information corresponding to regions with homogeneous colors. In this Thesis, an algorithm based on the partition of the minimum spanning tree of an image through a local measure of the likelihood of the unions among components is suggested. The idea is to arrive at a segmentation coherent with the real regions, a trade-off between partitions with many component (oversegmented) and those with fewer components (subsegmented).Another goal is that of obtaining an algorithm fast enough to be useful in applications of mobile robotics. This characteristic is attained by a local approach to region growing, even though the result still shows global feature (color). The possible oversegmentation is softened thanks to a probabilistic factor.The segmentation algorithm should also generate stable segmentations through time. Thus, the aforementioned algorithm has been widened by including an intermediate step that allows to relate similar regions in different images and to propagate forwards the regrouping of regions made in previous images. This way, if in some image some regions are grouped forming only one bigger region, the corresponding regions in the following image will also be grouped together. In this way, two correlatives segmentations resemble each other, keeping the whole segmented sequence stabler.Finally, the problem of comparing images via their content is also studied in this Thesis, focusing on the color information and, besides investigating which is for our aims the best distance between segmentation, also showing how color constancy affects segmentations. The results obtained in each of the goals proposed in this Thesis guarantee the exposed points of view, and show the utility of the algorithms suggested, as well as the color model for the spectral recovery and the explicit calculation of the transformations among colors.

Aquesta tesi versa sobre l'estimació del moviment d'un robot mòbil a partir dels canvis en les imatges captades per una càmera muntada sobre el robot. El moviment es dedueix amb un algorisme prèviament proposat en el marc de la navegació qualitativa. Per tal d'emprar aquest algorisme en casos reals s'ha fet un estudi de la seva precisió. Per augmentar-ne l'aplicabilitat, s'ha adaptat l'algorisme al cas d'una càmera amb moviments d'orientació i de zoom.Quan els efectes perspectius no són importants, dues vistes d'una escena captades pel robot es poden relacionar amb una transformació afí (o afinitat), que normalment es calcula a partir de correspondències de punts. En aquesta tesi es vol seguir un enfoc alternatiu, i alhora complementari, fent servir la silueta d'un objecte modelada mitjançant un contorn actiu. El marc es el següent: a mesura que el robot es va movent, la projecció de l'objecte a la imatge va canviant i el contorn actiu es deforma convenientment per adaptar-s'hi; de les deformacions d'aquest contorn, expressades en espai de forma, se'n pot extreure el moviment del robot fins a un factor d'escala. Els contorns actius es caracteritzen per la rapidesa en la seva extracció i la seva robustesa a oclusions parcials. A més, un contorn és fàcil de trobar fins i tot en escenes poc texturades, on sovint és difícil trobar punts característics i la seva correspondència.La primera part d'aquest treball té l'objectiu de caracteritzar la precisió i la incertesa en l'estimació del moviment. Per avaluar la precisió, primer es duen a terme un parell d'experiències pràctiques, que mostren la potencialitat de l'algorisme en entorns reals i amb diferents robots. Estudiant la geometria epipolar que relaciona dues vistes d'un objecte planar es demostra que la direcció epipolar afí es pot recuperar en el cas que el moviment de la càmera estigui lliure de ciclorotació. Amb una bateria d'experiments, tant en simulació com reals, es fa servir la direcció epipolar per caracteritzar la precisió global de l'afinitat en diferents situacions, com ara, davant de diferents formes dels contorns, condicions de visualització extremes i soroll al sistema.Pel que fa a la incertesa, gràcies a que la implementació es basa en el filtre de Kalman, per a cada estimació del moviment també es té una estimació de la incertesa associada, però expressada en espai de forma. Per tal propagar la incertesa de l'espai de forma a l'espai de moviment 3D s'han seguit dos camins diferents: un analític i l'altre estadístic. Aquest estudi ha permès determinar quins graus de llibertat es recuperen amb més precisió, i quines correlacions existeixen entre les diferents components. Finalment, s'ha desenvolupat un algorisme que permet propagar la incertesa del moviment en temps de vídeo. Una de les limitacions més importants d'aquesta metodologia és que cal que la projecció de l'objecte estigui dins de la imatge i en condicions de visualització de perspectiva dèbil durant tota la seqüència. En la segona part d'aquest treball, s'estudia el seguiment de contorns actius en el marc de la visió activa per tal de superar aquesta limitació. És una relació natural, atès que el seguiment de contorns actius es pot veure com una tècnica per fixar el focus d'atenció. En primer lloc, s'han estudiat les propietats de les càmeres amb zoom i s'ha proposat un nou algorisme per determinar la profunditat de la càmera respecte a un objecte qualsevol. L'algorisme inclou un senzill calibratge geomètric que no implica cap coneixement sobre els paràmetres interns de la càmera. Finalment, per tal d'orientar la càmera adequadament, compensant en la mesura del possible els moviments del robot, s'ha desenvolupat un algorisme per al control dels mecanismes de zoom, capcineig i guinyada, i s'ha adaptat l'algorisme d'estimació del moviment incorporant-hi els girs coneguts del capcineig i la guinyada. / This thesis deals with the motion estimation of a mobile robot from changes in the images acquired by a camera mounted on the robot itself. The motion is deduced with an algorithm previously proposed in the framework of qualitative navigation. In order to employ this algorithm in real situations, a study of its accuracy has been performed. Moreover, relationships with the active vision paradigm have been analyzed, leading to an increase in its applicability.When perspective effects are not significant, two views of a scene are related by an affine transformation (or affinity), that it is usually computed from point correspondences. In this thesis we explore an alternative and at the same time complementary approach, using the contour of an object modeled by means of an active contour. The framework is the following: when the robot moves, the projection of the object in the image changes and the active contour adapts conveniently to it; from the deformation of this contour, expressed in shape space, the robot egomotion can be extracted up to a scale factor. Active contours are characterized by the speed of their extraction and their robustness to partial occlusions. Moreover, a contour is easy to find even in poorly textured scenes, where often it is difficult to find point features and their correspondences.The goal of the first part of this work is to characterize the accuracy and the uncertainty in the motion estimation. Some practical experiences are carried out to evaluate the accuracy, showing the potentiality of the algorithm in real environments and with different robots. We have studied also the epipolar geometry relating two views of a planar object. We prove that the affine epipolar direction between two images can be recovered from a shape vector when the camera motion is free of cyclorotation. With a battery of simulated as well as real experiments, the epipolar direction allows us to analyze the global accuracy of the affinity in a variety of situations: different contour shapes, extreme visualization conditions and presence of noise.Regarding uncertainty, since the implementation is based on a Kalman filter, for each motion estimate we have also its covariance matrix expressed in shape space. In order to propagate the uncertainty from shape space to 3D motion space, two different approaches have been followed: an analytical and a statistical one. This study has allowed us to determine which degrees of freedom are recovered with more accuracy, and what correlations exist between the different motion components. Finally, an algorithm to propagate the motion uncertainty at video rate has been proposed.One of the most important limitations of this methodology is that the object must project onto the image under weak-perspective visualization conditions all along the sequence. In the second part of this work, active contour tracking is studied within the framework of active vision to overcome this limitation. Both relate naturally, as active contour tracking can be seen as a focus-of-attention strategy.First, the properties of zooming cameras are studied and a new algorithm is proposed to estimate the depth of the camera with respect to an object. The algorithm includes a simple geometric calibration that does not require any knowledge about the camera internal parameters.Finally, in order to orientate the camera so as to suitably compensate for robot motion when possible, a new algorithm has been proposed for the control of zoom, pan and tilt mechanisms, and the motion estimation algorithm has been updated conveniently to incorporate the active camera state information.

El mètode de detecció de simetria local de reflexió que es presenta, pretén ser una aportació més a la recerca en visió per computador i la robòtica. Com és sabut haches camps d'aplicació impliquen considerar el temps de processament com un paràmetre bàsic. Així doncs, en aquesta tesi no ens conformem en obtenir un algorisme eficient de detecció de simetria si no que es planteja millorar el temps de processame nt a partir de l'obtenció de metodologies i algorismes que tinguin la qualitat de permetre una fácil implantació del processament en paral· lel així com de la implementació de processadors específics.El mètode de detecció de simetria es basa en les contribucions a la simetria de les parelles de segments rectilinis de la imatge. Aquesta aproximació permet una reducció considerable de la complexitat, de la mateixa manera que altres autors utilitzen reduccions basades en diferents agrupacions de punts de contorn, com ara segments d'arcs, b-splines etc. El mètode, així concebut, serà aplicable en imatges on les línies rectes siguin predominats com és el cas de construccions artificials i entorns estructurats.Tot i que l'anterior restricció és important, és adequada per al tipus d'aplicacions que hem exposat anteriorment i ens permet obtenir un mètode de detecció contributiu, a partir de l'acumulació de contribucions locals a la simetria de les parelles de segments rectilinis de la imatge. Es tracta doncs d'un mètode basat en un anàlisi local que mostra els avantatges d'aquesta aproximació mentre que pel fet de tractar-se d'un mètode contributiu millora els dos principals inconvenients de l'aproximació local, és a dir, la sensibilitat al soroll i la inestabilitat, la qual cosa representa una aportació a la superació del dilema "anàlisi local versus anàlisi global".El mètode es composa de quatre etapes:- Obtenció de la llista de segments rectilinis de la imatge- Obtenció dels segments de contribució a la simetria- Càlcul del mapa d'acumulació dels segments de contribució- Extracció d'eixos locals de simetriaUna característica que distingeix el mètode és que proporciona l'abast de la simetria, és a dir, la llargada dels eixos de simetria, precisant-ne els punts inicial i final. Per altra banda la característica contributiva del mètode proposat, ha permès detectar els eixos de simetria local amb una ponderació associada segons la seva importància. D'aquesta forma s'evita el processat d'alt nivell posterior per tal de determinar els eixos més significatius, necessari en la majoria de mètodes basat en l'aproximació local. Respecta la millora del temps de processat i donada la complexitat i extensió del problema de la detecció de simetria, s'ha fet un primer esforç en una de les etapes del mètode de més cost de computació. Concretament s'ha accelerat un procés que forma part del càlcul del mapa d'acumulació esmentat anteriorment, consistent en l'obtenció dels píxels que aproximen, en el pla discret, un segment rectilini especificat per els seus punts inicial i finals. Aquesta millora s'ha obtingut mitjançant un algorisme paral· lel que presenta com avantatges més rellevants: la simplicitat, eficiència i que permet un directa implementació d'un processador dedicat. Per l'altra banda, amb el mateix objectiu de millorar el temps de processament i en base a l'algorisme anterior, s'ha dissenyat un processador paral· lel dedicat que té la capacitat d'obtenir i emmagatzemar simultàniament, en una matriu de registres, el conjunt de píxels que aproximen, en el pla discret, un segment rectilini caracteritzat per els seus punts inicial i final. Una característica molt remarcable del processador és que obté i registra els píxels anteriors en un únic període de rellotge.Finalment per tal de conèixer el paràmetres referents a la seva viabilitat i prestacions, s'ha obtingut, mitjançant la simulació, una versió reduïda amb tecnologia d'alta escala d'integració VLSI en un únic circuit. El disseny obtingut ha mostrat la capacitat de processar17,2 Mega Segments/seg, en el pitjor del casos, mentre que en les condicions més favorables es capaç de processar 57,3 Mega segments/segon. / The method of reflection local symmetry detection presented aims to be a new approach to the research in vision computer and robotics. As we know them, these fields of application imply to consider the processing time as a basic parameter. In this way, in this thesis we shall obtain an efficient algorithm for symmetry detection and, moreover, we will try to improve the processing time with methodologies and algorithms that will be able to embed easily in parallel architectures and the implementation of specific processors.The symmetry detection method is based in symmetry contributions from the straight segments in the image. This approximation permits a considerable reduction in the complexity in the same way that other authors use reductions based in different grouping of contour points, such as arcs, b-splines, etc. The method conceived like this will be applicable in images where straight lines are predominant like in the case of artificial buildings and structured environments.Although the above restriction is important, it is suitable for all kinds of applications that we have exposed previously and it allows us to obtain a contributive detection method from the accumulation of local contribution of symmetry in pairs of straight segments in the image. Thus, it is a method based in the local analysis that shows the advantages of this approach while it improves the two main disadvantages of local approximation because it is a contributive method. These drawbacks are the sensibility to noise and instability which represent a novel approach to the overcoming of the "local analysis versus global analysis" dilemma.Four steps compose the method: - To obtain the straight segments list in the image- To obtain the symmetry contribution segments- To calculate an accumulation map of contribution segments- To extract the local symmetry axes.A distinctive feature is that the method yields the symmetry range, that is, the length of symmetry axes, with precise position of initial and final points.On the other hand, the contributive feature of the proposed method has allowed us to detect the local symmetry axes with an associated weight to their importance. That avoids the posterior high level processing in order to determine the more significative axes needed in most of the approaches based in local approximation. With respect to the improvement of processing time, and given the complexity and extension of the symmetry detection problem, an initial effort has been made in one of the stages of higher computational cost in the method. Specifically, a process in the calculation of the accumulation map has been accelerated, consistently in the achieving of pixels that form, in the discrete plane, a straight segment specified for its initial and final points. This improvement has been obtained with a parallel algorithm that presents more relevant advantages: simplicity, efficiency and it allows a direct implementation with a dedicated processor.Furthermore, with the same objective of processing time improvement and in basis to the above algorithm, a dedicated parallel processor has been designed with the capability to obtain and store simultaneously, in an array of registers, the set of pixels that approximate, in the discrete plane, a straight segment characterised by its initial and final points. A very remarkable feature of the processor is to obtain and store those pixels in a unique clock period.Finally, in order to know the parameters concerning its viability and performance, a simulated reduced version with VLSI (very large scale integration) technology in a unique circuit has been achieved. The obtained design has shown the capability of processing 17.2 million segments per second in the worst case, while in the most favourable conditions it is able to process up to 57.3 million segments per second.

Esta tesis se ha enfocado en el desarrollo y evaluación de un conjunto de técnicas eficientes para generar y procesar mallas triangulares adaptativas obtenidas a partir de imágenes digitales.Tres objetivos diferentes han sido considerados: (1) aproximación de imágenes digitales con mallas triangulares adaptativas, (2) ejecución de operaciones típicas de procesamiento de imagen sobre mallas triangulares adaptativas y (3) obtención de imágenes digitales a partir de mallas triangulares adaptativas.Aproximación de Imágenes Digitales con Mallas Triangulares AdaptativasDos nuevas técnicas para aproximar imágenes digitales con mallas triangulares adaptativas han sido estudiadas y desarrolladas en esta tesis.La primera técnica aproxima una imagen digital dada con una malla triangular adaptativa garantizando un máximo error (tolerancia) con respecto a la imagen original.La segunda técnica aproxima una imagen digital dada con una malla triangular adaptativa conservando las formas y discontinuidades presentes en la imagen, evitando criterios de optimización. Esta segunda técnica puede ser complementada con la primera si un máximo error debe ser garantizado.Operaciones de Procesamiento de Imagen sobre Mallas Triangulares AdaptativasUn conjunto de técnicas para aplicar operaciones de análisis y realzado de imágenes sobre mallas triangulares adaptativas han sido desarrolladas en esta tesis. Estas técnicas permiten la ejecución de operaciones típicas de procesamiento de imagen a mallas triangulares que representan cualquier tipo de información, tales como imágenes de nivel de gris, mapas de profundidad (range images) o superficies de terreno. De este modo, cualquiera de las operaciones típicas de procesamiento de imagen ejecutadas sobre imágenes de nivel de gris pueden también ser aplicadas a mallas triangulares en general.Una ventaja adicional de las técnicas propuestas es que dado que las mallas triangulares procesadas pueden ser representaciones compactas de las imágenes digitales, algunas operaciones de procesamiento de imagen aplicadas en el dominio geométrico a mallas triangulares pueden ser ejecutas más eficientemente que si ellas son aplicadas en el dominio de imagen a las imágenes originales píxel por píxel.Generación de Imágenes Digitales a partir de Mallas Triangulares AdaptativasAdemás de ser capaces de generar mallas triangulares adaptativas desde imágenes digitales, es también necesario proceder por el camino inverso a modo de determinar la exactitud con la cual las mallas obtenidas aproximan las imágenes originales. De este modo, dos técnicas eficientes que permiten la generación de imágenes digitales a partir de mallas triangulares adaptativas han sido propuestas. La primera técnica muestrea cada triángulo de la malla dada uniformemente en tantas posiciones como píxeles aquel triángulo cubre. El resultado es una imagen digital aproximante. La segunda técnica genera una imagen digital a partir de una malla triangular adaptativa dada aplicando funciones de la libreria gráfica OpenGL, las cuales están implementadas tomando ventaja de la aceleración por hardware. En este forma, el estado de generación de imagen llega a ser significativamente más rápido que la anterior técnica de muestreo uniforme geométrico.Aunque los objetivos anteriores deben ser entendidos dentro del campo de procesamiento de imagen, muchas de las técnicas propuestas pueden ser aplicadas a otros campos tales como: visión por computador, robótica, modelado de superficies de terreno o imágenes médicas, por mencionar unos pocos. / This dissertation has focused on the development and evaluation of a set of efficient techniques to generate and to process adaptive triangular meshes obtained from digital images. Three different goals have been considered: (1) approximating digital images with adaptive triangular meshes, (2) performing typical image processing operations upon adaptive triangular meshes and (3) obtaining digital images from adaptive triangular meshes.Approximation of Digital Images with Adaptive Triangular MeshesTwo new techniques for approximating digital images with adaptive triangular meshes have been studied and developed in this dissertation. The first technique approximates a given digital image with an adaptive triangular mesh guaranteeing a maximum error (tolerance) with respect to the original image. The second technique approximates a given digital image with an adaptive triangular mesh by preserving the shapes and discontinuities present in the image, avoiding optimization criteria. This second technique can be complemented with the first one if a maximum error is to be guaranteed.Image Processing Operations upon Adaptive Triangular MeshesA set of techniques to perform image analysis and enhancement operations upon adaptive triangular meshes has been developed in this dissertation. These techniques allow the application of typical image processing operations to triangular meshes that represent any type of information, such as gray-level images, range images or terrain surfaces. Hence, many of the typical image processing operations performed upon gray-level images can also be performed to triangular meshes in general.An additional advantage of the proposed techniques is that since the processed triangular meshes can be compact representations of digital images, some image processing operations applied in the geometric domain to triangular meshes can run more efficiently that if they are applied in the image domain to the original images pixel by pixel.Generation of Digital Images from Adaptive Triangular MeshesBesides being able to generate adaptive triangular meshes from digital images, it is also necessary to proceed in the other way round in order to determine the accuracy with which the obtained meshes approximate the original images. Hence, two efficient techniques that allow the generation of digital images from adaptive triangular meshes have been proposed. The first technique samples every triangle of the given mesh uniformly at as many positions as pixels that triangle covers. The result is an approximating digital image. The second technique generates a digital image from a given adaptive triangular mesh by applying functions of the OpenGL graphics library, which are implemented by taking advantage of hardware acceleration. In this way, the image generation stage turns out to be significantly faster than with the previous geometric uniform sampling technique.Although the previous objectives must be understood within the field of image processing, many of the proposed techniques can be applied to other fields such as: computer vision, robotics, terrain surface modeling or medical imaging, to mention a few.

El modelat d'escenes és clau en un gran ventall d'aplicacions que van des de la generació mapes fins a la realitat augmentada. Aquesta tesis presenta una solució completa per a la creació de models 3D amb textura. En primer lloc es presenta un mètode de Structure from Motion seqüencial, a on el model 3D de l'entorn s'actualitza a mesura que s'adquireix nova informació visual. La proposta és més precisa i robusta que l'estat de l'art. També s'ha desenvolupat un mètode online, basat en visual bag-of-words, per a la detecció eficient de llaços. Essent una tècnica completament seqüencial i automàtica, permet la reducció de deriva, millorant la navegació i construcció de mapes. Per tal de construir mapes en àrees extenses, es proposa un algorisme de simplificació de models 3D, orientat a aplicacions online. L'eficiència de les propostes s'ha comparat amb altres mètodes utilitzant diversos conjunts de dades submarines i terrestres. / Scene modeling has a key role in applications ranging from visual mapping to augmented reality. This thesis presents an end-to-end solution for creating accurate, automatic 3D textured models, with contributions at different levels. First, we discuss a method developed within the framework of sequential Structure from Motion, where a 3D model of the environment is maintained and updated as visual information becomes available. The technique is more accurate and robust than state-of-the-art 3D modeling approaches. We also develop an online effcient loop-closure detection algorithm, allowing the reduction of drift and uncertainties for mapping and navigation. Inspired from visual bag-of-words, the technique is entirely sequential and automatic. Lastly, motivated by the need to map large areas, we propose a 3D model simplification oriented towards online applications. We discuss the efficiency of the proposals and compare them with state-of-the-art approaches, using a series of challenging datasets both in underwater and outdoor scenarios.