The fault-tolerant capability is an important performance specification for most of technical systems. The examples showing its importance are some catastrophes in civil aviation. According to some official investigations, some air incidents are technically avoidable if the pilots can take right measures. But, relying on the skill and experience of the pilots, it cannot be guaranteed that reliable flight decisions are always made. Instead, if fault-tolerant strategies can be included in the decision-making procedure, it will be very useful for safer flight. Fault-tolerant control is generally classified into passive and active fault-tolerant control. Passive fault-tolerant control relies on robustness of controller, which can only provide limited fault-tolerant ability, while active fault-tolerant control turns to a fault detection and isolation module to obtain fault information and then actively take actions to tolerate the effect of faults. Thus, active fault-tolerant control generally has stronger fault-tolerant ability. In this dissertation, one focuses on active fault-tolerant control, which for this case considers model predictive control and set-based fault detection and isolation. Model predictive control is a successful advanced control strategy in process industry and has been widely used for processes such as chemistry and water treatment, because of its ability to deal with multivariable constrained systems. However, the performance of model redictive control has deep dependence on system-model accuracy. Realistically, it is impossible to avoid the effect of modelling errors, disturbances, noises and faults, which always result in model mismatch. Comparatively, model mismatch induced by faults is possible to be effectively handled by suitable fault-tolerant strategies. The objective of this dissertation is to endow model predictive control with fault-tolerant ability to improve its effectiveness. In order to reach this objective, set-based fault detection and isolation methods are used in the proposed fault-tolerant schemes. The important advantage of set-based fault detection and isolation is that it can make robust fault detection and isolation decisions, which is key for taking right fault-tolerant measures. This dissertation includes four parts. The first part introduces this research, presents the state of the art and gives an introduction of used research tools. The second part proposes set-based fault detection and isolation for actuator or=and sensor faults, which are involved in interval observers, invariant sets and set-membership estimation. First, the relationship between interval observers and invariant sets is investigated. Then, actuator and sensor faults are separately coped with depending on their own features. The third part focuses on actuator or=and sensor fault-tolerant model predictive control, where the control strategy is robust model predictive control (tube-based and min-max approaches). The last part draws some conclusions, summarizes this research and gives clues for the further work. / La capacidad de los sistemas para tolerar fallos es una importante especificación de desempeño para la mayoría de sistemas. Ejemplos que muestran su importancia son algunas catástrofes en aviación civil. De acuerdo a investigaciones oficiales, algunos incidentes aéreos son técnicamente evitables si los pilotos pudiesen tomar las medidas adecuadas. Aun así, basándose en las habilidades y experiencia de los pilotos, no se puede garantizar que decisiones de vuelo confiables serán siempre posible de tomar. En cambio, si estrategias de tolerancia a fallos se pudieran incluir en el proceso de toma de decisión, los vuelos serían mucho más seguros. El control tolerante a fallos es generalmente clasificado en control pasivo y activo. El control pasivo se basa en la robustez del controlador, el cual sólo provee una habilidad limitada de tolerancia a fallos, mientras que el control tolerante a fallos de tipo activo se convierte en un modulo de detección y aislamiento de fallos que permite obtener información de éstos, y luego, activamente, tomar acciones para tolerar el efecto de dichos fallos. Así pues, el control activo generalmente tiene habilidades más fuertes de tolerancia a fallos. Esta tesis se enfoca en control tolerante a fallos activo, para lo cual considera el control predictivo basado en modelos y la detección y aislamiento de fallos basados en conjuntos. El control predictivo basado en modelos es una estrategia de control exitosa en la industria de procesos y ha sido ampliamente utilizada para procesos químicos y tratamiento de aguas, debido a su habilidad de tratar con sistemas multivariables con restricciones. A pesar de esto, el desempeño del control predictivo basado en modelos tiene una profunda dependencia de la precisión del modelo del sistema. Siendo realistas, es imposible evitar el efecto de errores de modelado, perturbaciones, ruidos y fallos, que siempre llevan a diferencias entre el modelo y el sistema real. Comparativamente, el error de modelo inducido por los fallos es posible de ser manejado efectivamente por estrategias adecuadas de control tolerante a fallos. Con el fin de alcanzar este objetivo, métodos de detección y aislamiento de fallos basados en conjuntos son utilizados en los esquemas de tolerancia a fallos propuestos en esta tesis. La ventaja importante de estas técnicas de detección y aislamiento de fallos basadas en conjuntos es que puede tomar decisiones robustas de detección y aislamiento, lo cual es clave para tomar medidas acertadas de tolerancia a fallos. Esta tesis esta dividida en cuatro partes. La primera parte es introductoria, presenta el estado del arte y hace una introducción a las herramientas de investigación utilizadas. La segunda parte expone la detección y aislamiento de fallos en actuadores y/o sensores, basándose en teoría de conjuntos, a partir de observadores de intervalo, y conjuntos invariantes. La tercera parte se enfoca en el control predictivo robusto (con enfoques basados tanto en tubos robustos como en min-max) con tolerancia a fallos en actuadores y/o sensores. La cuarta parte presenta algunas conclusiones, hace un resumen de esta investigación y da algunas ideas para trabajos futuros.

Tesi per compendi de publicacions. La consulta íntegra de la tesi, inclosos els articles no comunicats públicament per drets d'autor, es pot realitzar prèvia petició a l'Arxiu de la UPC / The thesis falls into the field of machine olfaction and accompanying experimental set up for chemical gas sensing. Perhaps more than any other sensory modality, chemical sensing faces with major technical and conceptual challenges: low specificity, slow response time, long term instability, power consumption, portability, coding capacity and robustness. There is an important trend of the last decade pushing artificial olfaction to mimic the biological olfaction system of insects and mammalians. The designers of machine olfaction devices take inspiration from the biological olfactory system, because animals effortlessly accomplish some of the unsolved problems in machine olfaction. In a remarkable example of an olfactory guided behavior, male moths navigate over large distances in order to locate calling females by detecting pheromone signals both rapidly and robustly. The biomimetic chemical sensing aims to identify the key blocks in the olfactory pathways at all levels from the olfactory receptors to the central nervous system, and simulate to some extent the operation of these blocks, that would allow to approach the sensing performance known in biological olfactory system of animals. New technical requirements arise to the hardware and software equipment used in such machine olfaction experiments. This work explores the bioinspired approach to machine olfaction in depth on the technological side. At the hardware level, the embedded computer is assembled, being the core part of the experimental set up. The embedded computer is interfaced with two main biomimetic modules designed by the collaborators: a large-scale sensor array for emulation of the population of the olfactory receptors, and a mobile robotic platform for autonomous experiments for guiding olfactory behaviour. At the software level, the software development kit is designed to host the neuromorphic models of the collaborators for processing the sensory inputs as in the olfactory pathway. Virtualization of the set up was one of the key engineering solutions in the development. Being a device, the set up is transformed to a virtual system for running data simulations, where the software environment is essentially the same, and the real sensors are replaced by the virtual sensors coming from especially designed data simulation tool. The proposed abstraction of the set up results in an ecosystem containing both the models of the olfactory system and the virtual array. This ecosystem can loaded from the developed system image on any personal computer. In addition to the engineering products released in the course of thesis, the scientific results have been published in three journal articles, two book chapters and conference proceedings. The main results on validation of the set up under the scenario of robotic odour localization are reported in the book chapters. The series of three journal articles covers the work on the data simulation tool for machine olfaction: the novel model of drift, the models to simulate the sensor array data based on the reference data set, and the parametrized simulated data and benchmarks proposed for the first time in machine olfaction. This thesis ends up with a solid foundation for the research in biomimetic simulations and algorithms on machine olfaction. The results achieved in the thesis are expected to give rise to new bioinspired applications in machine olfaction, which could have a significant impact in the biomedical engineering research area. / Esta tesis se enmarca en el campo de bioingeneria, mas particularmente en la configuración de un sistema experimental de sensores de gases químicos. Quizás más que en cualquier otra modalidad de sensores, los sensores químicos representan un conjunto de retos técnicos y conceptuales ya que deben lidiar con problemas como su baja especificidad, su respuesta temporal lenta, su inestabilidad a largo plazo, su alto consumo enérgético, su portabilidad, así como la necesidad de un sistema de datos y código robusto. En la última década, se ha observado una clara tendencia por parte de los sistemas de machine olfaction hacia la imitación del sistema de olfato biológico de insectos y mamíferos. Los diseñadores de estos sistemas se inspiran del sistema olfativo biológico, ya que los animales cumplen, sin apenas esfuerzo, algunos de los escenarios no resueltos en machine olfaction. Por ejemplo, las polillas machos recorren largas distancias para localizar las polillas hembra, detectando sus feromonas de forma rápida y robusta. La detección biomimética de gases químicos tiene como objetivo identificar los elementos fundamentales de la vía olfativa a todos los niveles, desde los receptores olfativos hasta el sistema nervioso central, y simular, en cierta medida, el funcionamiento de estos bloques, lo que permitiría acercar el rendimiento de la detección al rendimiento de los sistemas olfativos conociodos de los animales. Esto conlleva nuevos requisitos técnicos a nivel de equipamiento tanto hardware como software utilizado en este tipo de experimentos de machine olfaction. Este trabajo propone un enfoque bioinspirado para la ¿machine olfaction¿, explorando a fondo la parte tecnológica. A nivel hardware, un ordenador embedido se ha ensamblado, siendo ésta la parte más importante de la configuración experimental. Este ordenador integrado está interconectado con dos módulos principales biomiméticos diseñados por los colaboradores: una matriz de sensores a gran escala y una plataforma móvil robotizada para experimentos autónomos. A nivel software, el kit de desarrollo software se ha diseñado para recoger los modelos neuromórficos de los colaboradores para el procesamiento de las entradas sensoriales como en la vía olfativa biológica. La virtualización del sistema fue una de las soluciones ingenieriles clave de su desarrollo. Al ser un dispositivo, el sistema se ha transformado en un sistema virtual para la realización de simulaciones de datos, donde el entorno de software es esencialmente el mismo, y donde los sensores reales se sustituyen por sensores virtuales procedentes de una herramienta de simulación de datos especialmente diseñada. La propuesta de abstracción del sistema resulta en un ecosistema que contiene tanto los modelos del sistema olfativo como la matriz virtual . Este ecosistema se puede cargar en cualquier ordenador personal como una imagen del sistema desarrollado. Además de los productos de ingeniería entregados en esta tesis, los resultados científicos se han publicado en tres artículos en revistas, dos capítulos de libros y los proceedings de dos conferencias internacionales. Los principales resultados en la validación del sistema en el escenario de la localización robótica de olores se presentan en los capítulos del libro. Los tres artículos de revistas abarcan el trabajo en la herramienta de simulación de datos para machine olfaction: el novedoso modelo de drift, los modelos para simular la matriz de sensores basado en el conjunto de datos de referencia, y la parametrización de los datos simulados y los benchmarks propuestos por primera vez en machine olfaction. Esta tesis ofrece una base sólida para la investigación en simulaciones biomiméticas y en algoritmos en machine olfaction. Los resultados obtenidos en la tesis pretenden dar lugar a nuevas aplicaciones bioinspiradas en machine olfaction, lo que podría tener un significativo impacto en el área de investigación en ingeniería biomédica

La importància històrica del comerç tradicional produeix l' interés de la realització de la present tesi amb l' objetiu d' identificar les diferents estratègies competitives utilitzades en la distribució comercial per tal d' analizar, posteriorment, de quina manera la selecció concreta d' algunes d' aquestesLa importància històrica del comerç tradicional produeix l' interés de la realització de la present tesi amb l' objetiu d' identificar les diferents estratègies competitives utilitzades en la distribució comercial per tal d' analizar, posteriorment, de quina manera la selecció concreta d' algunes d' aquestes estratègias competitives poden ajudar a les micro i petites empreses detallistes a competir en front la gran distribució i fer-les sostenibles en el paisatge i la vida del país. A partir d' aquest objetiu, a més, aquesta tesi oferirà resposta a les següents preguntes: -Poden els micro i petits detallistes tradicionals utilitzar les mateixes estratègies competitives que la gran distribució? -Presenten els micro i petits detallistes tradicionals unes característiques competitives comunes que els hi permeten utilitzar les mateixes estratègies competitives per enfrontar-se a la gran distribució? -Conèixen els micro i petits detallistes els seus punts febles i els seus avantatges competitius? -Tenen els micro i petits detallistes prou preparació per tal de generar per si mateixos un canvi competitiu al seu negoci? -Poseeixen els micro i petits detallistes una visió clara del seu model de negoci? -Tenen els micro i petits detallistes una visió en comú del mercat? -Poden tots els micro i petits detallistes competir amb les mateixes estratègies contra la gran distribució, amb independència de la seva ubicació geogràfica? estratègias competitives poden ajudar a les micro i petites empreses detallistes a competir en front la gran distribució i fer-les sostenibles en el paisatge i la vida del país. A partir d' aquest objetiu, a més, aquesta tesi oferirà resposta a les següents preguntes: -Poden els micro i petits detallistes tradicionals utilitzar les mateixes estratègies competitives que la gran distribució? -Presenten els micro i petits detallistes tradicionals unes característiques competitives comunes que els hi permeten utilitzar les mateixes estratègies competitives per enfrontar-se a la gran distribució? -Conèixen els micro i petits detallistes els seus punts febles i els seus avantatges competitius? -Tenen els micro i petits detallistes prou preparació per tal de generar per si mateixos un canvi competitiu al seu negoci? -Poseeixen els micro i petits detallistes una visió clara del seu model de negoci? -Tenen els micro i petits detallistes una visió en comú del mercat? -Poden tots els micro i petits detallistes competir amb les mateixes estratègies contra la gran distribució, amb independència de la seva ubicació geogràfica? / La importancia histórica del comercio tradicional produce el interés de la realización de esta tesis con el objetivo de identificar las diferentes estrategias competitivas utilizadas en la distribución comercial para analizar, posteriormente, de qué forma la selección concreta de algunas de estas estrategias competitivas pueden ayudar a las micro y pequeñas empresas detallistas a competir ante la gran distribución y hacerlas sostenibles en el paisaje y la vida del país. A partir de este objetivo, además, esta tesis dará respuesta a las siguientes preguntas: -¿Pueden los micro y pequeños detallistas tradicionales utilizar las mismas estrategias competitivas que la gran distribución? -¿Presentan los micro y pequeños detallistas tradicionales unas características competitivas comunes que les permitan utilizar las mismas estrategias competitivas para enfrentarse a la gran distribución? -¿Conocen los micro y pequeños detallistas sus puntos débiles y sus ventajas competitivas? -¿Tienen los micro y pequeños detallistas la suficiente preparación como para generar por sí mismos un cambio competitivo en su negocio? -¿Poseen los micro y pequeños detallistas una visión clara de su modelo de negocio? -¿Tienen los micro y pequeños detallistas una visión común de su mercado? -¿Pueden todos los micro y pequeños detallistas competir con las mismas estrategias contra la gran distribución, independientemente de su ubicación geográfica?

Els incendis a gran escala suposen un gran repte degut a l'impacte que tenen en la societat a diversos nivells. Aquest fenomen físic és un problema multidisciplinar que requereix de l'esforç d'investigadors de diferents camps. Així doncs, predir el comportament dels incendis forestals i minimitzar els seus efectes són els principals objectius d'aquest treball. Un dels principals problemes d'aquests tipus de fenòmens és la incertesa i la imprecisió dels paràmetres d'entrada. Per abordar aquest problema, ens basem en una estratègia de predicció basada en tècniques de calibració, que tracten de sintonitzar aquests paràmetres per tal de proporcionar una predicció més precisa, i reduir la incertesa sobre els paràmetres. En aquest treball, proposem estratègies per resoldre certes restriccions associades a aquesta tècnica. La distribució espacial dels paràmetres ha estat considerada uniforme en tot el terreny, per la qual cosa s'introdueix un model complementari que simula l'efecte del vent sobre terrenys complexes, degut al paper fonamental del vent en la propagació del foc. A més a més, es suggereix acoblar un model meteorològic, per enriquir el coneixement del sistema sobre l'evolució temporal de les variables meteorològiques. Tots aquests components s'integren en un entorn de simulació i predicció, i es defineix una metodologia per simular incendis forestals reals, en la qual s'especifiquen els passos, procediments, models i eines necessàries per a construir un sistema d'avaluació del risc d'incendis forestals a temps real. Aquest sistema utilitza recursos i paradigmes propis de la Computació d'Altes Prestacions per proporcionar una resposta en un temps acceptable, degut a l'elevat cost computacional de l'avaluació de múltiples escenaris i de la integració de models complementaris. / Los incendios a gran escala suponen un gran reto debido al impacto que tienen en la sociedad a múltiples niveles. Este fenómeno físico es un problema multidisciplinar que requiere del esfuerzo de investigadores de campos diversos. Por lo tanto, predecir el comportamiento de los incendios forestales y minimizar sus efectos son las principales metas de este trabajo. Uno de los problemas principales de este tipo de fenómenos es la incertidumbre e imprecisión de los parámetros de entrada. Para abordar este problema, nos basamos en una estrategia de predicción basada en técnicas de calibración, que trata de sintonizar estos parámetros para proporcionar una predicción más certera, y reducir la incertidumbre sobre los parámetros. En este trabajo, proponemos estrategias para resolver ciertas restricciones asociadas a esta técnica. La distribución espacial de los parámetros ha sido considerada uniforme a lo largo del terreno, por lo que introducimos un modelo complementario para simular el efecto del viento sobre terrenos complejos, debido al papel fundamental del viento en la propagación del fuego. Además, se sugiere acoplar un modelo meteorológico para enriquecer el conocimiento del sistema sobre la evolución temporal de las variables meteorológicas. Todos estos componentes se integran en un entorno de simulación y predicción, y se define una metodología para simular incendios forestales reales donde se especifican los pasos, procedimientos, modelos, y herramientas necesarias para construir un sistema de evaluación del riesgo de incendios forestales en tiempo real. Este sistema se sirve de recursos y paradigmas propios de la Computación de Altas Prestaciones para proporcionar una respuesta en un tiempo aceptable debido al alto coste computacional de evaluar múltiples escenarios, e integrar modelos complementarios. / Large scale forest fires suppose a great challenge due to their impact on society on many levels. This physical phenomenon is an interdisciplinary problem that requires the efforts of researchers across various fields. Therefore, predicting the behavior of forest fires and minimizing the effects of this hazard is the main goal of this work. One of the major problems with this kind of hazard is the uncertainty and imprecision of the input parameters. We rely on a prediction strategy based on calibration techniques that try to tune these parameters to produce a more accurate prediction and reduce the uncertainty of the parameters. In this work, we propose strategies to solve some of the restrictions associated with this technique. The spatial distribution of the parameters has been considered uniform along the terrain, and we introduce a complementary model to simulate the wind behavior over complex terrains, due to the leading role of wind in fire spreading. We also suggest coupling a meteorological model to enrich the knowledge of the system of the temporal evolution of the weather variables. All these components are integrated in a simulation and prediction framework, and a methodology to simulate real forest fire scenarios is defined in which the steps, processes, models and tools to build an effective real-time forest fire assessment system are specified. This system relies on High Performance Computing resources and paradigms to provide a response in an acceptable time due to the high computational cost of evaluating several scenarios and integrating complementary models.

Existeix un ressorgiment en l'ús de mètodes estructurals per al problema de reconeixement i recuperació per contingut d'objectes en imatges. La teoria de grafs, en particular, la posada en correspondència de grafs (graph matching) juga un paper rellevant en aixó. En particular, la detecció d'un objecte (o una part) en una imatge es pot formular com un aparellament de subgrafs en termes de característiques estructurals. El matching de subgrafs és una tasca difícil. Especialment a causa de la presència de valors atípics, molts dels algoritmes existents per al matching de grafs tenen di- ficultats en l'escenari de matching de subgrafs. A més, l'aparellament de subgrafs de manera exacta s'ha demostrat ser una problema NP-complet. Així que hi ha una activitat intensa a la comunitat cientíca per proporcionar algoritmes eficaços per abordar el problema de manera suboptimal. La majoria d'ells treballen amb algoritmes aproximats que tracten d'obtenir una solució inexacta en forma aproximada. A més, el reconeixement habitualment ha de fer front a la distorsió. L'aparellament de subgrafs de manera inexacta consisteix a trobar el millor isomorfisme sota una mesura de similitud. Des del punt de vista teòric, aquesta tesi proposa algoritmes per a la solució al problema de l'aparellament de subgrafs de manera aproximada i inexacta. Des d'un punt de vista aplicat, aquesta tesi tracta el problema de la detecció de símbols en imatges de documents gràfics o dibuixos lineals (symbol spotting). Aquest és un problema ben conegut a la comunitat de reconeixement de gràfics. Es pot aplicar per a la indexació i classificació de documents sobre la base dels seus continguts. El caràcter estructural d'aquest tipus de documents motiva de forma natural la utilització d'una representació de grafs. Així el problema de detectar símbols en documents gràfics pot ser considerat com un problema d'aparellament de subgrafs. Els principals desaàments en aquest domini d'aplicació són el soroll i les distorsions que provenen de l'ús, la digitalització i la conversió de ràster a vectors d'aquests documents. A part que la visió per computador en l'actualitat no limita les aplicacions a un nombre limitat d'imatges. Així que el pas a l'escala i tractar un gran nombre d'imatges en el reconeixement de documents gràfics és un altre desaàment. En aquesta tesi, d'una banda, hem treballat en representacions de grafs eficients i robustes per solucionar el soroll i les distorsions dels documents. D'altra banda, hem treballat en diferents mètodes de matching de grafs per resoldre el problema de l'aparellament inexacte de subgrafs, que també sigui escalable davant d'un considerable nombre d'imatges. En primer lloc, es proposa un mètode per a detectar símbols mitjançant funcions de hash de subgrafs serialitzats. L'organització del graf una vegada factoritzat en subestructures comunes, que es poden organitzar en taules hash en funció de les similituds estructurals, i la serialització de les mateixes en estructures unidimensionals com ara camins, són dues aportacions d'aquesta part de la tesi. L'ús de les tècniques de hashing ajuda a reduir substancialment l'espai de cerca i accelera el procediment de la detecció. En segon lloc, presentem mecanismes de similitud contextual basades en la propagació basada en camins (walks) sobre el graf producte (tensor product graph). Aquestes similituds contextuals impliquen més informació d'ordre superior i més àble que les similituds locals. Utilitzem aquestes similituds d'ordre superior per formular l'aparellament de subgrafs com una problema de selecció de nodes i arestes al graf producte. En tercer lloc, proposem agrupament perceptual basat en convexitats per formar regions quasi convexes que elimina les limitacions de la representació tradicional dels grafs de regions per al reconeixement gràfic. En quart lloc, es proposa una representació de graf jeràrquic mitjançant la simplificació/correcció dels errors estructurals per crear un graf jeràrquic del graf de base. Aquests estructures de grafs jeràrquics s'integren en mètodes d'aparellament de grafs. A part d'aixó, en aquesta tesi hem proporcionat una comparació experimental general de tots els mètodes i alguns dels mètodes de l'estat de l'art. A més, també s'han proporcionat bases de dades d'experimentació. / Existe un resurgimiento en el uso de métodos estructurales para el problema de reconocimiento y recuperación por contenido de objetos en imágenes. La teoría de grafos, en particular la puesta en correspondencia de grafos (graph matching) juega un papel relevante en ello. Así, la detección de un objeto (o una parte) en una imagen se puede formular como un emparejamiento de subgrafos en términos de características estructurals. El matching de subgrafos es una tarea difícil. Especialmente debido a la presencia de valores atípicos, muchos de los algoritmos existentes para el matching de grafos tienen dificultades en el escenario de matching de subgrafos. Además, el apareamiento de subgrafos de manera exacta ha demostrado ser una problema NP-completo . Así que hay una actividad intensa en la comunidad científica para proporcionar algoritmos eficaces para abordar el problema de manera suboptimal. La mayoría de ellos trabajan con algoritmos aproximados que tratan de obtener una solución inexacta en forma aproximada. Además, el reconocimiento habitualmente debe hacer frente a la distorsión. El emparejamiento de subgrafos de manera inexacta consiste en encontrar el mejor isomorfismo bajo una medida de similitud. Desde el punto de vista teórico, esta tesis propone algoritmos para la solución al problema del emparejamiento de subgrafos de manera aproximada e inexacta. Desde un punto de vista aplicado, esta tesis trata el problema de la detección de símbolos en imágenes de documentos gráficos o dibujos lineales (symbol spotting). Este es un problema conocido en la comunidad de reconocimiento de gráficos. Se puede aplicar para la indexación y clasificación de documentos sobre la base de sus contenidos. El carácter estructural de este tipo de documentos motiva de forma natural la utilización de una representación de grafos. Así el problema de detectar símbolos en documentos gráficos puede ser considerado como un problema de apareamiento de subgrafos. Los principales desafiós en este dominio de aplicación son el ruido y las distorsiones que provienen del uso, la digitalización y la conversión de raster a vectores de estos documentos. Aparte de que la visión por computador en la actualidad no limita las aplicaciones a un número limitado de imágenes. Así que el paso a la escala y tratar un gran número de imágenes en el reconocimiento de documentos gráficos es otro desafió. En esta tesis, por una parte, hemos trabajado en representaciones de grafos efi- cientes y robustas para solucionar el ruido y las distorsiones de los documentos. Por otra parte, hemos trabajado en diferentes métodos de matching de grafos para resolver el problema del emparejamiento inexacto de subgrafos, que también sea escalable ante un considerable número de imágenes. En primer lugar, se propone un método para de tectar símbolos mediante funciones de hash de subgrafos serializados. La organización del grafo una vez factorizado en subestructuras comunes, que se pueden organizar en tablas hash en función de las similitudes estructurales, y la serialización de las mismas en estructuras unidimensionales como caminos, son dos aportaciones de esta parte de la tesis. El uso de las técnicas de hashing ayuda a reducir sustancialmente el espacio de búsqueda y acelera el procedimiento de la detección. En segundo lugar, presentamos mecanismos de similitud contextual basadas en la propagación basada en caminos (walks) sobre el grafo producto (tensor product graph). Estas similitudes contextuales implican más información de orden superior y más áble que las similitudes locales. Utilizamos estas similitudes de orden superior para formular el apareamiento de subgrafos como una problema de selección de nodos y aristas al grafo producto. En tercer lugar, proponemos agrupamiento perceptual basado en convexidades para formar regiones casi convexas que elimina las limitaciones de la representación tradicional de los grafos de regiones para el reconocimiento gráfico. En cuarto lugar, se propone una representación de grafo jerárquico mediante la simplificación/corrección de los errores estructurales para crear un grafo jerárquico del grafo de base. Estos estructuras de grafos jerárquicos integran en métodos de emparejamiento de grafos. Aparte de esto, en esta tesis hemos proporcionado una comparación experimental general de todos los métodos y algunos de los métodos del estado del arte. Además, también se han proporcionado bases de datos de experimentación. / There is a resurgence in the use of structural approaches in the usual object recognition and retrieval problem. Graph theory, in particular, graph matching plays a relevant role in that. Specifically, the detection of an object (or a part of that) in an image in terms of structural features can be formulated as a subgraph matching. Subgraph matching is a challenging task. Specially due to the presence of outliers most of the graph matching algorithms do not perform well in subgraph matching scenario. Also exact subgraph isomorphism has proven to be an NP-complete problem. So naturally, in graph matching community, there are lot of efiorts addressing the problem of subgraph matching within suboptimal bound. Most of them work with approximate algorithms that try to get an inexact solution in approximate way. In addition, usual recognition must cope with distortion. Inexact graph matching consists in finding the best isomorphism under a similarity measure. Theoretically this thesis proposes algorithms for solving subgraph matching in an approximate and inexact way. We consider the symbol spotting problem on graphical documents or line drawings from application point of view. This is a well known problem in the graphics recognition community. It can be further applied for indexing and classification of documents based on their contents. The structural nature of this kind of documents easily motivates one for giving a graph based representation. So the symbol spotting problem on graphical documents can be considered as a subgraph matching problem. The main challenges in this application domain is the noise and distortions that might come during the usage, digitalization and raster to vector conversion of those documents. Apart from that computer vision nowadays is not any more confined within a limited number of images. So dealing a huge number of images with graph based method is a further challenge. In this thesis, on one hand, we have worked on eficient and robust graph representation to cope with the noise and distortions coming from documents. On the other hand, we have worked on difierent graph based methods and framework to solve the subgraph matching problem in a better approximated way, which can also deal with considerable number of images. Firstly, we propose a symbol spotting method by hashing serialized subgraphs. Graph serialization allows to create factorized substructures such as graph paths, which can be organized in hash tables depending on the structural similarities of the serialized subgraphs. The involvement of hashing techniques helps to reduce the search space substantially and speeds up the spotting procedure. Secondly, we introduce contextual similarities based on the walk based propagation on tensor product graph. These contextual similarities involve higher order information and more reliable than pairwise similarities. We use these higher order similarities to formulate subgraph matching as a node and edge selection problem in the tensor product graph. Thirdly, we propose near convex grouping to form near convex region adjacency graph which eliminates the limitations of traditional region adjacency graph representation for graphic recognition. Fourthly, we propose a hierarchical graph representation by simplifying/correcting the structural errors to create a hierarchical graph of the base graph. Later these hierarchical graph structures are matched with some graph matching methods. Apart from that, in this thesis we have provided an overall experimental comparison of all the methods and some of the state-of-the-art methods. Furthermore, some dataset models have also been proposed.

Los procesadores están evolucionando para obtener más rendimiento, utilizando más transistores y siendo cada vez más densos y más complejos. Un efecto secundario de este escenario es que los procesadores son cada vez menos robustos frente a fallos transitorios. Como las soluciones integradas en los propios procesadores son caras o tienden a degradar el rendimiento del procesador, estas soluciones para hacer frente a estos fallos transitorios se complementan con propuestas en las capas superiores, como en el sistema operativo, o incluso en los programas. Las propuestas de tolerancia a fallos para tratar fallos transitorios integrados en la capa de aplicación, para su validación y evaluación usan frecuentemente experimentos de inyección de fallos, de este modo pueden evaluar el comportamiento de los programas con y sin sus propuestas de detección de fallas. Utilizar experimentos de inyección de fallos para evaluar el comportamiento de los programas en presencia de fallos transitorios, requiere ejecutar el programa evaluado, haciendo la inyección de un fallo (por lo general cambiando un solo bit en un registro del procesador) una cantidad significativa de veces, siempre observando el comportamiento del programa y si este ha finalizado presentando el resultado esperado. Un problema con esta estrategia es que el espacio de inyección de fallos es proporcional a la cantidad de instrucciones ejecutadas multiplicado por la cantidad de bits en el archivo de registros de la arquitectura del procesador. En lugar de ser exhaustivos (que sería inviable), este método consume mucho tiempo de CPU ejecutando o simulando el programa que se está evaluando tantas veces como sea necesario para obtener una aproximación estadística válida razonable (por lo general sólo unos pocos miles de veces). Así, el tiempo requerido para evaluar cómo se comportaría un solo programa en presencia de fallos transitorios podría ser proporcional al tiempo necesario para ejecutar el programa cerca de cinco mil veces. En este trabajo se presenta el concepto de robustez de un programa frente a fallos transitorios y también presenta una metodología llamada ARTFUL diseñada para, en lugar de utilizar las ejecuciones con inyecciones de fallos, hacer el cálculo de la robustez de forma determinística, basada en una traza de ejecución del programa y en la información sobre la arquitectura utilizada. Nuestro método fue evaluado calculando la robustez precisa de conocidos benchmarks reduciendo significativamente el tiempo necesario para realizar la evaluación. / Computer chips are evolving to obtain more performance, using more transistors and becoming denser and more complex. One side effect of such a scenario is that processors are becoming less robust than ever against transient faults. As on-chip solutions are expensive or tend to degrade processor performance, the efforts to deal with these transient faults in higher levels, such as the operating system or even by the programs, are increasing. Software based fault tolerance approaches to deal with transient faults often use fault injection experiments to evaluate the behavior of programs with and without their fault detection proposals. Using fault injection experiments to evaluate programs behavior in presence of transient faults require running the program under evaluation and injecting a fault (usually by flipping a single bit in a processor register) for a sufficient amount of times, always observing the program behavior and if it ended presenting the expected result. One problem with this strategy is that the fault injection space is proportional to the amount of instructions executed multiplied by the amount of bits in the processor architecture register file. Instead of being exhaustive (it would be unfeasible), this approach consumes lots of CPU time by running or simulating the program being evaluated as many times as necessary to obtain a reasonable valid statistical approximation (usually just a few thousand times). So, the time required to evaluate how a single program would behave in presence of transient faults might be proportional to the time needed to run the program for five thousand times. In this work we present the concept of a program's robustness against transient faults and also present a methodology named ARTFUL (from Assessing the Robustness against Transient Faults) designed to, instead of using executions with fault injections, deterministically calculate this robustness based on program’s execution trace over an given processor architecture and on information about the used architecture. Our approach was able to calculate the precise robustness of some benchmarks using just the time need to run the evaluated program for tents of times in the best cases.

Cada dia, vídeos i imatges es transmeten per Internet. La compressió d’imatges permet reduir la quantitat total de dades transmeses i accelera la seva entrega. En escenaris de vídeo-sota-demanda, el vídeo s’ha de transmetre el més ràpid possible utilitzant la capacitat disponible del canal. En aquests escenaris, la compressió d’imatges es mandatària per transmetre el més ràpid possible. Comunament, els vídeos són codificats permeten pèrdua de qualitat en els fotogrames, el que es coneix com ha compressió amb pèrdua. Els mètodes de compressió amb pèrdua són els més utilitzats per transmetre per Internet degut als seus elevats factors de compressió. Un altre característica clau en els escenaris de vídeo-sota-demanda és la capacitat del canal. Dependent de la capacitat, un mètode de assignació de rati assigna la quantitat de dades que es deu transmetre per cada fotograma. La majoria d’aquests mètodes tenen com a objectiu aconseguir la millor qualitat possible donat un ample de banda. A la pràctica, l’ample de banda del canal pot sofrir variacions en la seva capacitat degut a la congestió en el canal o problemes en la seva infraestructura. Aquestes variacions poden causar el desbordament o buidament del buffer del client, provocant pauses en la reproducció del vídeo. La primera contribució d’aquesta tesis es un mètode d’assignació de rati basat en JPEG2000 per a canals variants en el temps. La seva principal avantatja és el ràpid processament aconseguint una qualitat quasi òptima en la transmissió. Encara que la compressió amb pèrdua sigui la més usada per la transmissió d’imatges i vídeo per Internet, hi ha situacions on la pèrdua de qualitat no està permesa, en aquests casos la compressió sense pèrdua ha de ser utilitzada. La compressió sense pèrdua pot no ser viable en alguns escenaris degut als seus baixos factors de compressió. Per superar aquest inconvenient, la compressió visualment sense pèrdua pot ser utilitzada. La compressió visualment sense pèrdua és una tècnica basada en el sistema de visió humana per codificar només les dades visualment rellevants. Això permet factors de compressió majors que els de la compressió sense pèrdua, aconseguint pèrdues no perceptibles a l’ull humà. La segona contribució d’aquesta tesis és un sistema de codificació visualment sense pèrdua per a imatges JPEG2000 prèviament codificades. El propòsit d’aquest mètode es permetre la descodificació i/o transmissió de imatges dins en un règim visualment sense pèrdua. / Cada día, vídeos e imágenes se transmiten por Internet. La compresión de imágenes permite reducir la cantidad total de datos transmitidos y acelera su entrega. En escenarios de vídeo-bajodemanda, el vídeo debe transmitirse lo más rápido posible usando la capacidad disponible del canal. En éstos escenarios, la compresión de imágenes es mandataria para transmitir lo más rápido posible. Comúnmente, los videos son codificados permitiendo pérdida de calidad en los fotogramas, lo que se conoce como compresión con pérdida. Los métodos de compresión con pérdida son los más usados para transmitir por Internet dados sus elevados factores de compresión. Otra característica clave en escenarios de video-bajo-demanda es la capacidad del canal. Dependiendo de la capacidad, un método de asignación de ratio asigna la cantidad de datos que deben ser transmitidos por cada fotograma. La mayoría de estos métodos tienen como objetivo conseguir la mejor calidad posible dado un ancho de banda. A la práctica, el ancho de banda del canal puede sufrir variaciones en su capacidad debido a congestión en el canal o problemas en su infraestructura. Estas variaciones pueden causar el desbordamiento o vaciado del buffer del cliente, provocando pausas en la reproducción del vídeo. La primera contribución de esta tesis es un método de asignación de ratio basado en JPEG2000 para canales variantes en el tiempo. Su principal ventaja es el procesado rápido consiguiendo una calidad casi óptima en la transmisión. Aunque la compresión con pérdida sea la más usada para la transmisión de imágenes y vídeos por Internet, hay situaciones donde la pérdida de calidad no está permitida, en éstos casos la compresión sin pérdida debe ser usada. La compresión sin pérdida puede no ser viable en escenarios debido sus bajos factores de compresión. Para superar este inconveniente, la compresión visualmente sin pérdida puede ser usada. La compresión visualmente sin pérdida es una técnica que está basada en el sistema de visión humano para codificar sólo los datos de una imagen que son visualmente relevantes. Esto permite mayores factores de compresión que en la compresión sin pérdida, consiguiendo pérdidas no perceptibles al ojo humano. La segunda contribución de esta tesis es un sistema de codificación visualmente sin pérdida para imágenes JPEG2000 que ya han sido codificadas previamente. El propósito de este método es permitir la decodificación y/o transmisión de imágenes en un régimen visualmente sin pérdida. / Every day, videos and images are transmitted over the Internet. Image compression allows to reduce the total amount of data transmitted and accelerates the delivery of such data. In video-on-demand scenarios, the video has to be transmitted as fast as possible employing the available channel capacity. In such scenarios, image compression is mandatory for faster transmission. Commonly, videos are coded allowing quality loss in every frame, which is referred to as lossy compression. Lossy coding schemes are the most used for Internet transmission due its high compression ratios. Another key feature in video-on-demand scenarios is the channel capacity. Depending on the capacity a rate allocation method decides the amount of data that is transmitted for every frame. Most rate allocation methods aim at achieving the best quality for a given channel capacity. In practice, the channel bandwidth may suffer variations on its capacity due traffic congestion or problems in its infrastructure. This variations may cause buffer under-/over-flows in the client that causes pauses while playing a video. The first contribution of this thesis is a JPEG2000 rate allocation method for time-varying channels. Its main advantage is that allows fast processing achieving transmission quality close to the optimal. Although lossy compression is the most used to transmit images and videos in Internet, when image quality loss is not allowed, lossless compression schemes must be used. Lossless compression may not be suitable in scenarios due its lower compression ratios. To overcome this drawback, visually lossless coding regimes can be used. Visually lossless compression is a technique based in the human visual system to encode only the visually relevant data of an image. It allows higher compression ratios than lossless compression achieving losses that are not perceptible to the human eye. The second contribution of this thesis is a visually lossless coding scheme aimed at JPEG2000 imagery that is already coded. The proposed method permits the decoding and/or transmission of images in a visually lossless regime.

En Computación de Altas Prestaciones (HPC), con el objetivo de aumentar las prestaciones se ha ido incrementando el número de recursos de cómputo. Con el aumento del tamaño de las aplicaciones ejecutadas en computadores de altas prestaciones, también ha aumentado el número de interrupciones como consecuencia de fallos de hardware. La disminución en el tiempo medio entre fallos (MTBF) en los sistemas de cómputo actuales, fomenta la propuesta de soluciones de tolerancia a fallos apropiadas que permitan la finalización correcta de aplicaciones paralelas afectadas por fallos de componentes físicos. Por lo tanto, las técnicas de tolerancia a fallos son cruciales para aumentar la disponibilidad en computadores de altas prestaciones. Cuando son ejecutadas aplicaciones paralelas en computadores de altas prestaciones, los principales objetivos normalmente son: lograr una aceleración (speedup) cercana a la lineal, utilización eficiente de recursos y finalización correcta de las ejecuciones. Por lo tanto, los sistemas paralelos se enfrentan a un problema multiobjetivo que consiste en incrementar las prestaciones mientras se utilizan técnicas de tolerancia a fallos; dicha combinación en la cual se consideran prestaciones y confiabilidad se denomina en la literatura Performability. Las estrategias de tolerancia a fallos basadas en rollback-recovery han sido extensamente utilizadas en computación de altas prestaciones. Estas estrategias se basan en salvar el estado de la aplicación y cuando ocurren fallos las aplicaciones pueden volver atrás y re-ejecutar desde el último estado guardado (checkpoint). Estas estrategias introducen una sobrecarga durante la ejecución de las aplicaciones en aspectos que afectan a las prestaciones, tales como una sobrecarga en el tiempo de cómputo, uso de recursos, etc. Las estrategias de checkpoint no coordinadas permiten a los procesos salvar sus estados independientemente. Cuando estas estrategias se combinan con mecanismos de log de mensajes, se evitan problemas como el efecto dominó o la aparición de mensajes huérfanos. Las técnicas de log de mensajes son responsables de la mayor parte de la sobrecarga introducida durante ejecuciones libre de fallos. En esta tesis nos hemos centrado en disminuir el impacto de las técnicas de log de mensajes considerando tanto el impacto en las ejecuciones libres de fallos así en como en el tiempo de recuperación. Una de las contribuciones de esta tesis es un mecanismo de log denominado Hybrid Message Pessimistic Logging (HMPL). Este protocolo se enfoca en combinar las características de rápida recuperación de los mecanismos de log pesimistas basados en el receptor con la baja sobrecarga que introducen los mecanismos de log basados en el emisor en ejecuciones libres de fallos. Sin perder las ventajas de un sistema de log de mensajes pesimista basado en el receptor, el HMPL permite a las aplicaciones paralelas continuar con su ejecución inclusive cuando un mensaje no ha sido guardado totalmente en el log del receptor, y de esta manera se reducen las sobrecargas en comparación con los mecanismos de log pesimistas basados en el receptor. Para poder garantizar que no se pierde ningún mensaje, un mecanismo de log pesimista basado en el emisor es utilizado para guardar temporalmente mensajes, mientras los receptores se encargan de guardar totalmente el mensaje recibido. Además proponemos otras estrategias que permiten incrementar la performability de aplicaciones paralelas. Una estrategia consiste en evitar la degradación que ocurre como consecuencia de un fallo mediante la utilización automática de nodos de repuesto (Spare Nodes) para reemplazar nodos que han fallado. Teniendo en cuenta que las tareas de tolerancia a fallos son gestionadas por un middleware transparente al usuario, hemos propuesto una metodología que permite determinar configuraciones apropiadas de las tareas de tolerancia a fallos para disminuir la sobrecarga en ejecuciones libres de fallos. Esta metodología se basa en analizar el impacto del mecanismo de log de mensajes utilizado y configurar las ejecuciones paralelas disminuyendo la perturbación introducida. Además, hemos desarrollado una metodología para la ejecución de aplicaciones pertenecientes al paradigma Single Problem Multiple Data (SPMD). Dicha metodología permite obtener el máximo speedup teniendo en cuenta un umbral de eficiencia computacional definida y considerando el impacto de las tareas de un mecanismo de log de mensajes. Los resultados experimentales han mostrado que mediante la caracterización del impacto del log de mensajes en el cómputo y en las comunicaciones, es posible seleccionar un número de procesos o cores de cómputo que permitan hacer un uso eficiente de los recursos mientras se aumenta la performability. / In High Performance Computing (HPC) the demand for more performance is satisfied by increasing the number of components. With the growing scale of HPC applications has came an increase in the number of interruptions as a consequence of hardware failures. The remarkable decrease of Mean Times Between Failures (MTBF) in current systems encourages the research of suitable fault tolerance solutions which makes it possible to guarantee the successful completion of parallel applications. Therefore, fault tolerance mechanisms are a valuable feature to provide high availability in HPC clusters. When running parallel applications on HPC clusters the prior objectives usually are: almost linear speedup, efficient resources utilization, scalability and successful completion. Hence, parallel applications executions are now facing a multiobjective problem which is focused on improving Performance while giving Fault Tolerance (FT) support; this combination is defined as Performability. A widely used strategy to provide FT support is rollback-recovery, which consists in saving the application state periodically. In the presence of failures, applications resume their executions from the most recent saved state. These FT protocols usually introduce overheads during applications' executions. Uncoordinated checkpoint allows processes to save their states independently. By combining this protocol with message logging, problems such as the domino effect and orphan messages are avoided. Message logging techniques are usually responsible for most of the overhead during failure-free executions in uncoordinated solutions. Considering this fact, in this thesis we focus on lowering the impact of message logging techniques taking into account failure-free executions and recovery times. A contribution of this thesis is a Hybrid Message Pessimistic Logging protocol (HMPL). It focuses on combining the fast recovery feature of pessimistic receiver-based message logging with the low overhead introduced by pessimistic sender-based message logging during failure-free executions. The HMPL aims to reduce the overhead introduced by pessimistic receiver-based approaches by allowing applications to continue normally before a received message is properly saved. In order to guarantee that no message is lost, a pessimistic sender-based logging is used to temporarily save messages while the receiver fully saves its received messages. In this thesis we propose strategies to increase the performability of parallel applications. One approach focuses on avoiding performance degradation when failure occurs by using automatic spare node management to replace failed nodes. Taking into account that the fault tolerance tasks are managed by an user-transparent middleware, we propose a methodology that allows us to determine suitable configurations of these tasks in order to lower overheads in failure-free executions. This methodology is based on analyzing the message log impact and configuring the parallel executions decreasing the introduced disturbance. Another contribution of this thesis is a methodology that allows to obtain the maximum speedup under a defined efficiency threshold, considering the impact of message logging tasks for Single Program Multiple Data (SPMD) applications. Experiments have shown that characterizing the message logging effects in computation and communication, allows us to select a better number of processes or computational cores to be used in order to improve resource utilization while increasing performability.

Els aventatges recents en les òptiques dels dispositius endoscopis han fet que hi hagi un creixement en el seu us per a diagnostics i intervencions no ivasives. Dins de tots els procediments endoscopics (els cuals s'incloeix l'exploració dels organs interns del pacient des de el nas al anus), la broncoscopia es un dels mes freqüents amb 261 millions d'intervencions a l'any. Encara que el seu us s'exten per per la majoria de les cliniques presenta alguns problemes o inconvenients com per exemple el més important de tots: el mesurament de forma visual de les estructures anotòmiques. Una de les intervencions més bàsiques implica l'obtenció del percentatge d'obtrucció anomenat estenosis. Enrrors en aquesta mesura tenen un impacte directe al tractament del pacient, per tant, un mesurament objectiu de les estenosis traqueals en videos de broncoscòpia constituiria una roptura en la utilització d'aquesta tècnica no invasiva i una reducció en el cost de les operacions per la sanitat pública per un decreixement en les operacions repetides per mesuraments visuals errornis. El càlcul del grau d'estenosis esta basat en la comparació de la regió delimitada per líarea luminal (en un frame patològic) amb la regió delimitada per el primer anell visible de referència (en un frame sa). Per aconseguir tenir una bona delimitació d'aquestes regions, una bona definició de les estructures traqueals (anells i lumen) es necessària. En aquesta tesis proposem una estrategia paramètrica per a l'extracció de les estructures traqueals necessaries per al càlcul de l'estenosis. Per assegurar una aplicabilitat del sistema presentem un protocol estadístic per seleccionar els paràmetres més òptims. Els experiments demostren que el nostre mètode està dins de la variabilitat dels metges, per tant el rendiment es comparable a un metge amb la particularitat que el temps de computació permet una implementació on-line en el moment del diagnòstic. / Los últimos avances en la óptica de los dispositivos de endoscopia han motivado un incremento en su uso en procedimientos mínimamente invasivos de diagnóstico y exploración. La broncoscopia, con más de 261 millones de intervenciones al a±o, es una de las técnicas endoscópicas -exploración de órganos internos desde la boca hasta el ano- más extendidas. Aunque su uso se ha popularizado en las instalaciones sanitarias aún dista de funcionar de manera perfecta, presentando algunas carencias como la imposibilidad de obtener medidas anatómicas exactas debido a que éstas son tomadas mediante inspección visual. De entre todas las intervenciones broncoscópicas nos centramos en el cálculo de estenosis que permite obtener el porcentaje de obstrucción traqueal. Un error en la estimación del grado de obstrucción tiene impacto en el tratamiento que se le prescribe al paciente, por tanto un cálculo objetivo de la estenosis supondría un salto cualitativo para la técnica así como una reducción de costes para el sistema sanitario al evitar repeticiones de operaciones debido a toma de medidas erróneas. El cálculo del porcentaje de estenosis se basa en la comparación de la región delimitada por el lumen en una imagen de obstrucción traqueal y la región delimitada por el primer anillo visible en una imagen normal de tráquea. Para obtener una definición adecuada de dichas regiones necesitamos de una caracterización eficiente de las estructuras traqueales involucradas: anillos y área luminal. En esta tesis proponemos una estrategia paramétrica para la extracción de dichas estructuras basándonos en un modelo de geometría y apariencia que guía un modelo deformable. Con el fin de potenciar una aplicabilidad real de nuestra propuesta proponemos un marco estadístico para elegir de manera automática los parámetros que optimizan el rendimiento de nuestro método. Nuestra propuesta es validada tanto a nivel de caracterización de estructuras anatómicas como a nivel global de porcentaje de estenosis. Dicha validación se ha realizado sobre bases de datos generadas en el contexto de esta tesis, validadas y anotadas por personal clínico. Los experimentos realizados certifican un rendimiento comparable al de los expertos clínicos, suponiendo nuestro método un coste computacional asumible de cara a una prometedora futura integración en los protocolos actuales. / Recent advances in the optics of endoscopic devices have increased their use for minimal invasive diagnostic and intervention procedures. Among all endoscopic procedures (which include exploration of patient internal organs from mouth to anus), bronchoscopy is one of the most frequents with around 261 millions of procedures per year. Although the use of bronchoscopy is spread among clinical facilities it presents some drawbacks, being the visual inspection for the acquisition and assessment of anatomical measurements the most prevalent of them. One of the basic interventions implies to obtain the percentage of airway obstruction, which is known as stenosis. Errors in this measurement have a direct impact in the treatment the patient will be prescribed. Therefore an objective computation of tracheal stenosis in bronchoscopy videos would constitute a breakthrough for this non-invasive technique and a reduction in operation cost for the public health service due to the decrease in interventions because of bad visual measurements. The calculation of the degree of stenosis is based on the comparison of the region delimited by the lumen in an obstructed frame and the region delimited by the first visible ring in a healthy frame. In order to obtain a good delimitation of these regions a reliable characterization of the needed tracheal structures: rings and luminal area is needed. We propose in this thesis a parametric strategy for the extraction of lumen and tracheal rings regions based on models of their geometry and appearance that guide a deformable model. In order to ensure a systematic applicability we present a statistical framework to select the optimal parameters of our method. We have validated our method in two ways: accuracy of the anatomical structures extraction and comparison of the performance of our automatic method over manually annotated stenosis. Experiments report results within inter-observer variability for both quality metrics. The performance of our method is comparable to the one provided by clinicians and its computation time allows for a on-line implementation in the operating room.

La industria y los científicos han buscado alternativas para procesar con eficacia el gran volumen de datos que se generan en diferentes áreas del conocimiento. MapReduce se presenta como una alternativa viable para el procesamiento de aplicaciones intensivas de datos. Los archivos de entrada se dividen en bloques más pequeños. Posteriormente, se distribuyen y se almacenan en los nodos donde serán procesados. Entornos Hadoop han sido utilizados para ejecutar aplicaciones MapReduce. Hadoop realiza automáticamente la división y distribución de los archivos de entrada, la división del trabajo en tareas Map y Reduce, la planificación de tareas entre los nodos, el control de fallos de nodos; y gestiona la necesidad de comunicación entre los nodos del cluster. Sin embargo, algunas aplicaciones MapReduce tienen un conjunto de características que no permiten que se beneficien plenamente de las políticas de planificación de tareas construídas para Hadoop. Los archivos de entrada compartidos entre múltiples trabajos y aplicaciones con grandes volúmenes de datos intermedios son las características de las aplicaciones que manejamos en nuestra investigación. El objetivo de nuestro trabajo es implementar una nueva política de planificación de trabajos que mejore el tiempo de makespan de lotes de trabajos Hadoop de dos maneras: en un nivel macro (nivel de planificación de trabajos), agrupar los trabajos que comparten los mismos archivos de entrada y procesarlos en lote; y en un nivel micro (nivel de planificación de tareas) las tareas de los diferentes trabajos procesados en el mismo lote, que manejan los mismos bloques de datos, se agrupan para ser ejecutas en el mismo nodo donde se asignó el bloque. La política de planificación de trabajos almacena los archivos compartidos de entrada y los datos intermedios en una RAMDISK, durante el procesamiento de cada lote. / Industry and scientists have sought alternatives to process effectively the large volume of data generated in different areas of knowledge. MapReduce is presented as a viable alternative for the processing of data intensive application. Input files are broken into smaller blocks. So they are distributed and stored in the nodes where they will be processed. Hadoop clusters have been used to execute MapReduce applications. The Hadoop framework automatically performs the division and distribution of the input files, the division of a job into Map and Reduce tasks, the scheduling tasks among the nodes, the failures control of nodes; and manages the need for communication between nodes in the cluster. However, some MapReduce applications have a set of features that do not allow them to benefit fully from the default Hadoop job scheduling policies. Input files shared between multiple jobs and applications with large volumes of intermediate data are the characteristics of the applications we handle in our research. The objective of our work is to improve execution efficiency in two ways: On a macro level (job scheduler level), we group the jobs that share the same input files and process them in batch. Then we store shared input files and intermediate data on a RAMDISK during batch processing. On a micro level (task scheduler level) tasks of different jobs processed in the same batch that handle the same data blocks are grouped to be executed on the same node where the block was allocated.