Las aplicaciones tipo workflow se caracterizan por tener un elevado tiempo de cómputo y una elevada transferencia de datos. Como consecuencia, el tiempo de ejecución o makespan de un workflow es elevado. Con el propósito de reducir el makespan del workflow, las tareas se ejecutan en diferentes máquinas interconectadas a través de una red. Asignar correctamente las tareas del DAG a las máquinas disponibles del entorno de ejecución mejora el makespan. El encargado de realizar la asignación de las tareas del workflow a las máquinas es el planificador. El problema de un planificador estático es que no tiene en cuenta los cambios ocurridos en el entorno de ejecución durante la ejecución del DAG. La solución a este problema ha sido el desarrollo de un nuevo planificador dinámico. El planificador dinámico mejora el makespan del DAG debido a que considera los cambios ocurridos en el entorno de ejecución durante la ejecución del workflow, pero como contrapartida, genera overhead producido a consecuencia de reaccionar ante los cambios detectados. El objetivo de este trabajo es proporcionar estrategias que reducen el overhead del planificador dinámico, sin afectar al makespan del DAG. Para reducir el overhead, el algoritmo reacciona ante los cambios detectados durante la ejecución del DAG únicamente si anticipa que su makespan mejora. La política dinámica desarrollada ha sido evaluada a través de ejecuciones simuladas y ejecuciones realizadas en un entorno oportunístico real. En la experimentación simulada se ha mejorado el makespan entre 5% y 30%, y en la experimentación real la mejora del makespan ha sido entre 5% y 15%. En lo que respecta al overhead, éste se ha reducido como mínimo un 20% respecto a otras políticas de planificación dinámicas. / Workflow applications exhibit both high computation times and data transfer rates. For this reason, the completion time or makespan of the workflow is high. To reduce completion time, tasks of a workflow ought to run on different machines interconnected by a network. Efficient assignment of tasks to machines within the runtime environment is an important aspect to achieve a good makespan. The manager making these assignment is the scheduler. The main problem of a static scheduler is that it ignores changes that occur in the execution environment during workflow execution. To solve this problem, we developed a new dynamic scheduler. Taking into account the changes that occur to the execution environment during the execution of the DAG improves the makespan, but generates overhead as a result of reacting to the detected changes. The objective of this thesis was to reduce the overhead incurred by excessive self-adaptations, without affecting the makespan. To reduce overhead, the proposed dynamic algorithm self-adapts only when an improvement in makespan is expected. The proposed policies have been evaluated by simulation and executed in a real environment. In simulated experiments we achieved a makespan improvement between 5% and 30%, while in real experiments the makespan improvement was between 5% and 15%. Regarding the overhead, our strategy incurred in at least 20% less overhead than other dynamic scheduling policies.

L'augment de la quantitat de dades que necessiten ser processades actualment, representa un dels majors reptes a l' ambit de la computaci o. Aix o ha perm es el creixement d'aplicacions amb requeriments especials conegudes com aplicacions intensives en dades. En general, per afavorir l'execuci o en paral lel de aquest tipus d'aplicacions, les dades d'entrada son partits en trossos m es petits que poden ser processats individualment. No obstant aix o, en molts casos, aquestes aplicacions mostren problemes graus de rendiment, deguts principalment a desequilibris de c arrega, l' us ine cient dels recursos de c omput disponibles, i inadequades pol tiques de partici o i distribuci o de les dades. A m es, l'impacte d'aquests problemes de rendiment es pot veure acrescut pel comportament din amic de l'aplicaci o. Aquest treball proposa una metodologia per a millorar, din amicament, el rendiment d'aplicacions intensives en dades, basat en: (i) l'adaptaci o de la grand aria i nombre de les particions de dades amb la nalitat de reduir el temp d'execuci o total; i (ii) l'adaptaci o del nombre de nodes de c omput per aconseguir una execuci o e cient. Proposem observar el comportament de l'aplicaci o per cada iteraci o (o consulta) i utilitzar les dades recollides per a ajustar din amicament el seu rendiment. La metodologia assumeix que cada execuci o inclou m ultiples consultes relacionades sobre una unica c arrega de treball partida. L'ajust del factor de partici o de la c arrega de treball es fa mitjan cant la de nici o de la grand aria inicial dels trossos de dades; la modi caci o de la pol tica de plani caci o (per a enviar primerament els trossos amb major temps d'execuci o); la divisi o dels trossos amb major temps d'execuci o; i el agrupament de trossos de dades amb temps de c omput massa curts. Els criteris per a decidir si el trossos es divideixen o es agrupen estan basats en els temps d'execuci o associats a cada tros (com el temps mitj a i la desviaci o est andard) aix com tamb e en el nombre de nodes de c omputs que s'estan utilitzant. A m es a m es, el referent a l' us de recursos de c omput es va abordar mitjan cant l'avaluaci o din amica del rendiment de l'aplicaci o, juntament amb l'estimaci o i modi caci o del nombre de nodes de processament que es puguin utilitzar e cientment. Hem avaluat la nostra proposta usant aplicacions intensives en dades reals i sint etiques. Aix com tamb e hem analitzat les expressions anal tiques propostes mitjan cant simulaci o. Despr es d'aplicar la nostra metodologia, hem obtingut resultats prometedors en la reducci o del temps total d'execuci o i l' us e cient dels recursos. Paraules claus: balanceig de c arrega; an alisi i sintonitzaci o din amic del rendiment; aplicacions intensives en dades; c arrega arbitr ariament divisible. / La gran cantidad de datos que recientemente necesitan ser procesados, representa uno de los mayores retos en el campo de la computaci on. Esto ha conllevado al crecimiento de aplicaciones con requerimientos especiales conocidas como aplicaciones intensivas en datos. En general, para facilitar la ejecuci on en paralelo de aplicaciones intensivas en datos, los datos de entrada son divididos en trozos m as peque~nos que pueden ser procesados individualmente. Sin embargo, en muchos casos, estas aplicaciones muestran graves problemas de rendimiento debidos principalmente a desbalances de carga, uso ine ciente de los recursos de c omputo disponibles, e inapropiadas pol ticas de partici on y distribuci on de los datos. Adem as, el impacto de dichos problemas de rendimiento puede depender del comportamiento din amico de la aplicaci on. Este trabajo propone una metodolog a para mejorar, din amicamente, el rendimiento de aplicaciones intensivas en datos, en base a: (i) adaptar el tama~no y el n umero de las particiones de datos con el n de reducir el tiempo de ejecuci on total; y (ii) adaptar el n umero de nodos de c omputo para conseguir una ejecuci on e ciente. Proponemos monitorizar el comportamiento de la aplicaci on para cada iteraci on (o consulta) y usar los datos recogidos para ajustar din amicamente el rendimiento de la aplicaci on. La metodolog a asume que una sola ejecuci on incluye m ultiples consultas relacionadas sobre una misma carga de trabajo particionada. El ajuste del factor de partici on de la carga de trabajo es llevado a cabo a trav es de la de nici on del tama~no inicial de los trozos de datos; la modi caci on de la pol tica de plani caci on, para enviar primero los trozos de datos con los tiempos de procesamiento m as largos; la divisi on de dichos trozos de datos; y el agrupamiento de trozos de datos con tiempos de c omputo muy cortos. Los criterios para decidir dividir o agrupar trozos est an basados en los tiempos de ejecuci on asociados a cada pieza (tiempo medio y desviaci on est andar) y en el n umero de elementos de c omputo que est an siendo utilizados. Adicionalmente, lo inherente al uso de los recursos se abord o mediante la evaluaci on din amica del rendimiento de la aplicaci on, junto con la estimaci on y consiguiente modi caci on del n umero de nodos de procesamiento que pueden ser utilizados e cientemente. Hemos evaluado nuestra propuesta usando aplicaciones intensivas en datos reales y sint eticas. As como tambi en hemos analizado las expresiones anal ticas propuestas a trav es de simulaci on. Luego de aplicar nuestra metodolog a, hemos obtenido resultados prometedores en la reducci on del tiempo total de ejecuci on y el uso e ciente de los recursos. Palabras clave: balanceo de carga; an alisis y sintonizaci on din amico del rendimiento; aplicaciones intensivas en datos; carga arbitrariamente divisible. / The recent large amount of data needing to be processed represents one of the major challenges in the computational eld. This fact led to the growth of specially designed applications known as data-intensive applications. In general, to ease the parallel execution of data-intensive applications input data is divided into smaller data chunks that can be processed separately. However, in many cases, these applications show severe performance problems mainly due to load imbalance, ine cient use of available resources, and improper data partition policies. In addition, the impact of these performance problems can depend on the dynamic behavior of the application. This work proposes a methodology to dynamically improve the performance of data-intensive applications based on: (i) adapting the size and the number of data partitions to reduce overall execution time; and (ii) adapting the number of processing nodes to achieve an e cient execution. We propose to monitor the application behavior for each iteration (query) and use gathered data to dynamically tune the performance of the application. The methodology assumes that a single execution includes multiple related queries on the same partitioned workload. The adaptation of the workload partition factor is addressed through the de nition of the initial size for the data chunks; the modi cation of the scheduling policy to send rst data chunks with large processing times; dividing of the data chunks with the biggest associated computation times; and joining of data chunks with small computation times. The criteria for dividing or gathering chunks are based on the chunks' associated execution time (average and standard deviation) and the number of processing elements being used. Additionally, the resources utilization is addressed through the dynamic evaluation of the application performance and the estimation and modi cation of the number of processing nodes that can be e ciently used. We have evaluated our strategy using a real and a synthetic data-intensive application. Analytical expressions have been analyzed through simulation. Applying our methodology, we have obtained encouraging results reducing total execution times and e cient use of resources. Keywords: load balancing; dynamic performance analysis and tuning; Data-intensive applications; arbitrarily divisible load.

La correspondència de característiques és un problema fonamental de la Visió per Computador, que té múltiples aplicacions com el seguiment, la classificació i recuperació d’imatges, el reconeixement de formes i la visió estereoscòpica. En molts àmbits, és útil per representar l’estructura local de les carácterístiques en correspondència, per augmentar la precissió o per fer les correspondències invariants a certes transformacions (afins, homografies, etc...). No obstant això, la codificació d’aquest coneixement requereix complicar el model mitjançant l’establiment de relacions d’ordre alt entre els elements del model, i per tant l’augment de la complexitat del problema d’optimització. La importància de les correspondències molts-a-molts es de vegades ignorada en la literatura. La majoria dels mètodes es limiten a realizar correspondències un-a-un, generalment validant en conjunts de dades sintètiques, o no realistes. En un entorn real, amb variacions d’escala, il.luminació i orientació de l’objecte d’interés, i amb la presència d’oclusions, desordre, i observacions sorolloses, les relacions molts-a-molts son necessàries per aconseguir resultats satisfactoris. Com a conseqüència, trovar la correspondència molts-a-molts més probable, implica un procés complicat d’optimització combinatòria. En aquest treball dissenyem i demostrem algorismes de correspondència que calculen associacions molts-a-molts, i que poden ser aplicats a diversos problemes difícils de resoldre. El nostre objectiu és fer ús de representacios d’ordre alt per millorar el poder expressiu de la correspondència, alhora que ferm possible el procés d’inferència o l’optimització d’aquests models. Al llarg de la tesi, hem utilitzat eficaçment els models gràfics com la nostra representació preferida, ja que proporcionen un marc probabilístic elegant per abordar problemes de predicció estructurada. Hem introdüit un algorisme de seguiment bassat en correspondències que es porten a terme entre els fotogrames d’una sequència de vídeo, per tal de resoldre el problema de segument de fars de cotxes durant la nit. També generalitzem aquest mateix algorisme per resoldre el problema de l’associació de dades aplicat a different escenaris de seguiment. Hem demostrat l’eficàcia d’aquest enfoc en seqüències de vídeo reals i demostrem que el nostre algorisme de seguiment es pot utilitzar per millorar la precisió d’un sistema de classificació de fars de cotxes. A la segona part d’aquest treball, pasem desde correspondències no denses (punts) cap a correspondèencies denses (regions), i introdüim una nova representació jeràrquica d’imatges. Seguidament, fem ús d’aquest model per desenvolupar correspondències molts-a-molts d’ordre alt entre parelles d’imatges. Demostrem que l’ús de models d’ordre alt en comparació amb altres models més senzills no només millora l’exactitud dels resultats, sinó també la velocitat de convergència de l’algorisme d’inferència. Finalment, seguim explotant la idea de correspondència de regions per dissenyar un algorisme de co-segmentació completament no supervisat, que és capaç de competir amb altres mètodes supervisats de l’estat-de-l’art. El nostre mètode supera inconvenients típics d’alguns treballs passats, com evitar la necesitat d’aparences variades al fons de les imatges. La correspondència de regions en aquest cas s’aplica per explotar eficaçment la informació compartida entre les imatges. També extenem aquest treball per dur a terme co-segmentació de vídeos, sent la primera vegada que s’aborda aquest problema. / Feature matching is a fundamental problem in Computer Vision, having multiple applications such as tracking, image classification and retrieval, shape recognition and stereo fusion. In numerous domains, it is useful to represent the local structure of the matching features to increase the matching accuracy or to make the correspondence invariant to certain transformations (affine, homography, etc…). However, ncoding this knowledge requires complicating the model by establishing high-order relationships between the model elements, and therefore increasing the complexity of the optimization problem. The importance of many-to-many matching is sometimes dismissed in the literature. Most methods are restricted to perform one-to-one matching, and are usually validated on synthetic, or non-realistic datasets. In a real challenging environment, with scale, pose and illumination variations of the object of interest, as well as the presence of occlusions, clutter, and noisy observations, many-to-many matching is necessary to achieve satisfactory results. As a consequence, finding the most likely many-to-many correspondence often involves a challenging combinatorial optimization process. In this work, we design and demonstrate matching algorithms that compute many-to-many correspondences, applied to several challenging problems. Our goal is to make use of high-order representations to improve the expressive power of the matching, at the same time that we make feasible the process of inference or optimization of such models. We effectively use graphical models as our preferred representation because they provide an elegant probabilistic framework to tackle structured prediction problems. We introduce a matching-based tracking algorithm which performs matching between frames of a video sequence in order to solve the difficult problem of headlight tracking at night-time. We also generalize this algorithm to solve the problem of data association applied to various tracking scenarios. We demonstrate the effectiveness of such approach in real video sequences and we show that our tracking algorithm can be used to improve the accuracy of a headlight classification system. In the second part of this work, we move from single (point) matching to dense (region) matching and we introduce a new hierarchical image representation. We make use of such model to develop a high-order many-to-many matching between pairs of images. We show that the use of high-order models in comparison to simpler models improves not only the accuracy of the results, but also the convergence speed of the inference algorithm. Finally, we keep exploiting the idea of region matching to design a fully unsupervised image cosegmentation algorithm that is able to perform competitively with state-of-the-art supervised methods. Our method also overcomes the typical drawbacks of some of the past works, such as avoiding the necessity of variate appearances on the image backgrounds. The region matching in this case is applied to effectively exploit inter-image information. We also extend this work to perform co-segmentation of videos, being the first time that such problem is addressed, as a way to perform video object segmentation.

El objetivo principal del presente trabajo es abordar el problema de precisión y tiempo de espera en la predicción meteorológica, la cual es habitualmente llevada a cabo por aplicaciones computaciones conocidas como modelos de predicción meteorológica numérica (Numerical Weather Prediction, NWP). Estos modelos han sido muy desarrollados en las últimas décadas y su rendimiento mejora constantemente con el aumento de la potencia de cómputo. Sin embargo, en la práctica, la comunidad científica aun esta dedicando considerables esfuerzos para reducir el problema ampliamente conocido como 'tiempo limitado de predicción' (weather limited predictability). Principalmente, los dos mayores retos son la voluntad de obtener predicciones meteorológicas más fiables y realizarlas más rápidamente. Como en muchas otras áreas de la modelización medioambiental, los modelos NWP, la mayoría de del software de simulación trabaja con modelos sólidos y ampliamente aceptados. Por lo tanto, la necesidad de optimización de los parámetros de entrada del simulador representa un problema conocido y tratado en numerosas ocasiones por la comunidad científica. En estos entornos en particular no se puede disponer de parámetros de entrada correctos a tiempo. Se requiere utilizar una estrategia de estimación y optimización computacionalmente eficiente para minimizar la desviación entre el escenario predicho y el comportamiento real del fenómeno. Basándose en lo mencionado previamente, esta tesis trata de: 1 Proveer un estudio de sensibilidad del efecto de los parámetros de entrada del modelo NWP en la calidad de la predicción. 2 Proponer un framework, el cual permita realizar búsquedas de los valores óptimos de los parámetros de entrada del modelo que, según nuestra hipótesis, proveerá una mejor calidad de predicción. 3 Reducir el tiempo de espera necesitado para obtener predicciones meteorológicas más fiables. Para cumplir los objetivos de la propuesta presentada, se ha introducido un nuevo esquema de predicción meteorológica. Este nuevo esquema implementa un algoritmo de cómputo evolutivo, el cual se centra en la calibración de los parámetros de entrada del modelo NWP. El esquema presentado se denomina Genetic Ensemble, compuesto por dos etapas: etapa de calibración y etapa de predicción. Mediante la etapa de calibración, esta aproximación aplica un Algoritmo Genético de forma iterativa, para encontrar los 'mejores' valores de los parámetros de entrada del modelo NWP que acto seguido, serán utilizados en la siguiente etapa de predicción. Han sido desarrolladas diversas estrategias del Genetic Ensemble, como la extensión para calibrar más de un nivel de parámetros de entrada, y también para evaluar estos valores utilizando diferentes estrategias. Por otro lado, el esquema propuesto es paralelizado utilizando un paradigma Master/Worker, y es apto para ser ejecutado en plataformas de computación de altas prestaciones (HPC) gracias a las cuales el tiempo total de ejecución se reduce. Este esquema ha sido evaluado ejecutando experimentos de predicción meteorológica correspondientes a una catástrofe muy conocida, el huracán Katrina en 2005. Los resultados obtenidos mostraron una mejora en la calidad de la predicción meteorológica y una reducción significativa del tiempo de ejecución total. / The main goal of the presented work is to tackle the problem of accuracy and waiting time in weather forecasting, which are normally conducted by computational applications known as Numerical Weather Prediction (NWP) models. These models have been strongly developed in the last decades and their performance constantly increases with the advances in computational power. However, in practice, many serious are still gaining considerable efforts by the scientific community in order to reduce what is widely known as 'weather limited predictability'. Mainly, the major two challenges are the willingness to get more reliable weather predictions, and to do it faster. As in many other areas of environmental modeling, most simulation software works with well-founded and widely accepted models. Hence, the need for input parameter optimization to improve model output is a long¬known and often-tackled problem. Particularly, in such environments where correct and timely input parameters cannot be provided. Efficient computational parameter estimation and optimization strategies are required to minimize the deviation between the predicted scenario and the real phenomenon behaviour. Based on the before mentioned, this thesis intends to: 1. Provide a sensitivity study of the effect of NWP model input parameters on prediction quality. 2. Propose a valid framework, which allows to search for the most 'optimal' values of model input parameters which, in our hypothesis, will provide better prediction quality. 3. Reduce the waiting time needed to get more reliable weather predictions. To accomplish the objectives of the presented proposal, a new weather prediction scheme is introduced. This new scheme implements an evolutionary computing algorithm, which focuses on the calibration of input parameters in NWP models. The presented scheme is called Genetic Ensemble, which is composed of two-phases: calibration phase and prediction phase. Through the calibration phase, the presented approach applies Genetic Algorithm operators iteratively, in order to find 'best' values of NWP model input parameters, which consequently, will be used in the consequent prediction phase. Many strategies of the Genetic Ensemble have been developed, as such, it s extended to calibrate more than one level of input parameters, and also to evaluate their values using different strategies. On the other hand, the proposed scheme is paralleled using a Master/Worker programming paradigm, and is suitable to be executed in high performance computing (HPC) platforms, by which, execution time is intended to be reduced. The presented scheme has been evaluated by running weather prediction experiments over a well-known weather catastrophe; Hurricane Katrina 2005. Obtained results showed both significant improvement in weather prediction quality, and a considerable reduction in the over all execution time.

En las últimas décadas se han producido mejoras significativas en las técnicas de imagen médica. Hoy en día, el uso de estas técnicas es habitual en la mayoría de sistemas sanitarios, y las imágenes producidas forman parte integral de las fichas de los pacientes. De entre las modalidades de imagen médica habitualmente empleadas, los rayos X es una de las más populares gracias a su bajo coste, alta resolución y su excelente capacidad para penetrar dentro de los tejidos. Dentro de la familia de la imagen de rayos X, las angiografías de rayos X --las cuales emplean cateterización minimamente invaisva-- se emplean rutinariamente para detectar irregularidades en el sistema vascular. Las imágenes de angiografías de rayos X se pueden clasificar en dos typos: angiografía de rayos X general (GXA) ,las cuales presentan los vasos sanguíneos de diferentes partes del cuerpo como brazos, piernas, pies, etc., y las secuencias de video de angiogramas coronarios (CAVSs), las cuales muestran solo los árboles de los vasos coronarios para el diagnóstico de enfermedades cardiovasculares. Dadas las diferencias en cuanto a función, estos dos tipos de imagen presentan características muy diferentes. Las imágenes GXA suelen poseer una alta resolución espacial, pero una baja resolución temporal. Por otro lado, las CAVSs suelen tener una resolución espacial más baja pero una resolución temporal mucho mayor. Debido al número creciente de estudios médicos que emplean angiogramas de rayos X, surge una necesidad de almacenar y compartir las imágenes producidas, por lo que la compresión de las mismas se está convirtiendo en una tarea crítica. La compresión con pérdida tiene la ventaja de una gran capacidad de reducción del tamaño del fichero comprimido, pero en general se rechaza en la comunidad médico debido a que los cambios introducidos en las imágenes podrían afectar al proceso de diagnóstico. Por otro lado, la compresión sin pérdida garantiza una fidelidad de datos perfecta, pero resulta en ratios de compresión menores. Por última. la compresión sin pérdida en el diagnóstico se está convirtiendo en la opción preferida dado que permite obtener ratios de compresión mejores que la compresión puramente sin pérdida, sin sacrificar excesiva precisión en los procesos de diagnóstico. En la compresión sin pérdida en el diagnóstico, los datos clínicamente relevantes se comprimen sin pérdida, mientras que los datos irrelevantes para el diagnóstico se comprimen con algo de pérdida. En este escenario, identificar las zonas relevantes y no relevantes para el diagnóstico es la primera etapa, y además la más importante en este tipo de compresión. En esta tesis se desarrollan dos estrategias de compresión sin pérdida en el diagnóstico. La primera se propone para imágenes GXA. La segunda, para CAVSs. La técnica para imágenes GXA identifica primero el área focal relevante y después se aplican métodos de supresión de fondo (background) para mejorar el rendimiento de la compresión. La técnica para imágenes CAVSs se ha implementado para reconocer los cuadros (frames) que no contienen estructuras de vasos sanguíneos visibles. Estos cuadros se comprimen con pérdida, mientras que el resto se comprimen sin pérdida. Se han probado varias técnicas de compresión para cada tipo de imágenes, incluyendo standars compatibles con DICOM como JPEG2000, JPEG-LS, H.264/AVC, y el último estandard de compresión de vídeo HEVC. En JPEG2000, la compresión multicomponente y la compresión progresiva también se han evaluado. Los resultados experimentales indican que las dos técnicas arriba descritas son capaces de detectar los datos relevantes para el diagnóstico. En cuanto a los resultados de compresión, la técnica propuesta para imágenes GXA obtiene reducciones de tamaño de hasta el 34% y mejoras en la reconstrucción progresiva de hasta 20~dB de SNR. La técnica para CAVSs produce resultados de compresión un 19% mejores, en comparación con las técnicas de compresión sin pérdida. / The past several decades have witnessed a major evolution in medical imaging techniques, making medical images become commonplace in healthcare systems and an integral part of a patient medical record. Among the existing medical imaging modalities, X-ray imaging is one of the most popular technologies due to its low cost, high resolution and excellent capability to penetrate deep within tissue. In particular, X-ray angiographies --which use minimally invasive catheterization-- and X-ray imaging are widely used to identify irregularities in the vascular system. X-ray angiography images can be classified into two types: general X-ray angiography (GXA) images, which present blood vessels in several body parts like arms, legs, foots, etc.; and coronary angiogram video squences (CAVSs), which only focus on coronary vessel trees for diagnosing cardiovascular diseases. Because of the differences in functions, these two types of images have different features: GXA images normally have high spatial resolutions (the width and height sizes) but low temporal resolution (the number of frames), while CAVSs usually have lower spatial resolutions but higher temporal resolution. Due to the increasing number of medical studies using X-ray angiography images and the need to store and share them, compression of these images is becoming critical. Lossy compression has the advantage of high data reduction capability, but it is rarely accepted by medical communities because of the modification of data that may affect the diagnosis process. Lossless compression guarantees perfect reconstruction of the medical signal, but results in low compression ratios. Diagnostically lossless compression is becoming the preferred choice, as it provides an optimal trade-off between compression performance and diagnostic accuracy. In diagnostically lossless compression, the clinically relevant data is encoded without any loss while the irrelevant data is encoded with loss. In this scenario, identifying and distinguishing the clinically relevant from the clinically irrelevant data in medical images is the first and usually most important stage in diagnostically lossless compression methods. In this thesis, two diagnostically lossless compression strategies are developed. The first one is proposed for GXA images. The second one if proposed for CAVSs. For GXA images, the clinically relevant focal area in each frame is first identified; and then a background-suppression approach is employed to increase the data redundancy of the images and hence improve the compression performance. For CAVSs, a frame-identification procedure is implemented to recognise the diagnostically unimportant frames that do not contain visible vessel structures; then, lossy compression is applied to these frames, and lossless compression is applied to the other frames. Several compression techniques have been investigated for both types of images, including the DICOM-compliant standards JPEG2000, JPEG-LS and H.264/AVC, and the latest advanced video compression standard HEVC. For JPEG2000, multicomponent-transform and progressive lossy-to-lossless coding are also tested. Experimental results suggest that both the focal-area-identification and frame-identification processes are automatic in computation and accurate in clinically relevant data identification. Regarding the compression performance, for GXA images, when compared to the case of coding with no background-suppression, the diagnostically lossless compression method achieves average bit-stream reductions of as much as 34\% and improvements on the reconstruction quality of up to 20 dB-SNR for progressive decoding; for CAVSs, the frame-identification followed by selective lossy \& lossless compression strategy achieves bit-stream reductions of more than 19\% on average as compared to lossless compression.

SISTEMAS DE INSERCIÓN Y BORRADO: COMPLEJIDAD Y CAPACIDAD DE MODELADO El objetivo central de la tesis es el estudio de los sistemas de inserción y borrado y su capacidad computacional. Más concretamente, estudiamos algunos modelos de generación de lenguaje que usan operaciones de reescritura de dos cadenas. También consideramos una variante distribuida de los sistemas de inserción y borrado en el sentido de que las reglas se separan entre un número finito de nodos de un grafo. Estos sistemas se denominan sistemas controlados mediante grafo, y aparecen en muchas áreas de la Informática, jugando un papel muy importante en los lenguajes formales, la lingüística y la bio-informática. Estudiamos la decidibilidad/ universalidad de nuestros modelos mediante la variación de los parámetros de tamaño del vector. Concretamente, damos respuesta a la cuestión más importante concerniente a la expresividad de la capacidad computacional: si nuestro modelo es equivalente a una máquina de Turing o no. Abordamos sistemáticamente las cuestiones sobre los tamaños mínimos de los sistemas con y sin control de grafo. / COMPLEXITY AND MODELING POWER OF INSERTION-DELETION SYSTEMS The central object of the thesis are insertion-deletion systems and their computational power. More specifically, we study language generating models that use two string rewriting operations: contextual insertion and contextual deletion, and their extensions. We also consider a distributed variant of insertion-deletion systems in the sense that rules are separated among a finite number of nodes of a graph. Such systems are refereed as graph-controlled systems. These systems appear in many areas of Computer Science and they play an important role in formal languages, linguistics, and bio-informatics. We vary the parameters of the vector of size of insertion-deletion systems and we study decidability/universality of obtained models. More precisely, we answer the most important questions regarding the expressiveness of the computational model: whether our model is Turing equivalent or not. We systematically approach the questions about the minimal sizes of the insertiondeletion systems with and without the graph-control.

La forma más extendida de implementar una aplicación de simulación es mediante la utilización de un grafo de escena. Este tipo de estructura resulta muy adecuado para definir escenas estáticas, pero presenta serias carencias a la hora de representar estructuras articuladas, u objetos con comportamientos complejos. Ambas circunstancias se dan en el caso de los actores virtuales.Este trabajo define nuevas estructuras de datos y métodos que permiten integrar de una forma adecuada actores virtuales en una aplicación de simulación:1-Se presentan dos nuevos tipos de nodos (Actor y Skeleton), que actúan como elemento modular para la definición y gestión de cualquier tipo de actor virtual. En el diseño de estos nodos se ha prestado especial atención a la estandarización, y la eficiencia computacional. 2-Se proponen técnicas que permiten solventar algunas carencias de los grafos de escena actuales a la hora de ser empleados con actores virtuales. Se actúa sobre el cuello de botella existente en relación con aplicación de matrices de transformación. Se define un nuevo método de gestión de culling específico para actores, es compatible con el tradicional, y actúa sobre los costes asociados a la gestión del comportamiento. Se define un método de gestión de nivel de detalle específico, que actúa simultáneamente sobre la geometría, la topología y el comportamiento, y se realiza un análisis sobre la forma en que los actores han de ser integrados en un sistema multiprocesador3-Se describe una estructura de nombre "ActorClass", que es independiente del grafo de escena y que se encarga de almacenar todas las informaciones de alto nivel que son compartidas por varios actores de la misma "especie". Esta estructura es capaz de absorber futuras ampliaciones y permite realizar simulaciones macroscópicas.Con el objeto de demostrar la utilidad práctica de los resultados de este trabajo, se ha implementado una librería de programación y una arquitectura modular que actúan sobre la base de las estructuras y métodos descritos, y se ha desarrollado un ejemplo de su utilización que muestra en detalle todos los aspectos de la integración de actores virtuales en una aplicación de simulación ya existente. / The "Scene Graph" is the most widespread method of implementation simulation applications. This kind of structure is a very convenient way to define static scenes, but it has serious drawbacks in representing articulated structures or objects with complex behaviours. Both circumstances are inherent in virtual actors.This thesis defines new data structures and methods permiting the adequate integratión of virtual actors in a simulatión application:1. Two new kinds of nodes are presented (Actor and Skeleton). These nodes function as modular elements to define and manage all kinds of virtual actor. During the dessing process of this nodes a great attention was paid to standarization and computational efficience.2. Special techniques are presented in order to solve problems in the current scene graphs: Working on the bottleneck that exists in relation to the transformation matrix process; Defining a new method of culling, specific to actors, that is compatible with the traditional, and considers the costs associated with the behaviour management; Defining a specific "Level of Detail" method, that works simultaneously with the geometry, the topology and the behaviour; Making an analisis of the technique to ingrate actors in a multiprocessor system.3. A new structure, named "ActorClass", is defined. This structure is independent of the scene graph and is responsible for storing all the high level information that is shared by several actors of the same "species". This structure has the capability of assimilating future expansions, and supporting the definition of macroscopic simulations.In order to show the practical utility of the results of this work, a programming library and a modular architecture have been implemented on the basis of these proposed structures and methods. In addition, a practical sample sample has been developed, showing in detail all the aspects of the integratión of virtual actors in an existing simulation application.

Els valors dels píxels de les imatges són el resultat d'una combinació d'informacions visuals provinents de múltiples fonts. Recuperar la informació dels múltiples factors que han produït una imatge sembla un problema molt difícil. Tanmateix, és important fixar-se que els éssers humans desenvolupem l'habilitat d'interpretar les imatges i de reconèixer i aïllar determinades propietats físiques de l'escena. Les imatges que descriuen una sola característica física d'una escena s'anomenen imatges intrínseques. Aquestes imatges serien molt útils per la majoria de processos de la visió per computador, que sovint es veuen afectats pels diversos efectes que normalment trobem en les imatges naturals (ombres, especularitats, interreflexions, etc.) En aquesta tesi s'analitza el problema de l'estimació d'imatges intrínseques des de diferents punts de vista, com per exemple la formulació teòrica del problema, les cues visuals que poden ser útils per a estimar certes imatges intrínseques o els mecanismes d'avaluació del problema. Primer introduïm breument l'origen del problema de l'estimació d'imatges intrínseques i també parlem del seu context i d'alguns temes relacionats. Llavors, presentem una revisió exhaustiva de la bibliografia d'imatges intrínseques en el camp de la visió per computador, proporcionant una descripció detallada i organitzada de les tècniques per a l'estimació d'imatges intrínseques que han aparegut fins ara. D'altra banda, també examinem els mecanismes d'avaluació d'imatges intrínseques que s'han utilitzat fins ara, estudiant les bases de dades i les mètriques existents. A més a més, analitzem l'evolució del problema i identifiquem les tendències actuals d'aquest camp de recerca. Sovint, en el camp de la visió per computador, la informació del color ha estat ignorada. Tanmateix, el color ha resultat ser molt útil en l'estimació d'imatges intrínseques. En aquest treball presentem un mètode de descomposició d'imatges intrínseques que estima la reflectància i el shading d'una imatge utilitzant observacions de dos atributs de color que es combinen en un marc probabilístic. D'altra banda, la majoria dels mètodes de descomposició d'imatges intrínseques fins ara han assumit que les escenes estan il·luminades per una ``llum blanca'' i han ignorat completament els efectes dels sensors de la càmera en les imatges. Tots dos factors, però, afecten els valors de les imatges resultants durant el procés d'adquisició. En aquest treball analitzem la formulació teòrica del problema de descomposició d'imatges intrínseques i proposem un nou marc, més general, on es modelitzen els efectes tant dels sensors de la càmera com del color de l'il·luminant. En aquesta nova formulació hi introduïm un nou component, anomenat reflectància absoluta, que és invariant a tots dos efectes. A més a més, demostrem que qualsevol coneixement sobre el color de l'il·luminant o sobre els sensors de la càmera es pot utilitzar per millorar les reflectàncies estimades dels diferents mètodes de descomposició d'imatges intrínseques. Finalment, analitzem els mecanismes d'avaluació d'imatges intrínseques, que han evolucionat constantment durant aquesta última dècada. En aquesta tesi presentem dues bases de dades per a l'avaluació d'imatges intrínseques. Una d'elles és una base de dades calibrada que inclou informació sobre l'il·luminant de l'escena i els sensors de la càmera. Aquesta base de dades s'ha utilitzat per validar experimentalment el marc teòric per a la descomposició d'imatges intrínseques presentat en aquesta tesi. La segona base de dades s'ha construït mitjançant tècniques de gràfics per computador i conté imatges, tant d'objectes simples com d'escenes complexes, adquirides amb diferents condicions d'il·luminació. En aquest treball es demostra que amb programari de gràfics per computador i motors de representació gràfica, és possible construir bases de dades molt grans i realistes per a l'avaluació d'imatges intrínseques. / Image values are the result of a combination of visual information coming from multiple sources. Recovering information from the multiple factors that produced an image seems a hard and ill-posed problem. However, it is important to observe that human beings develop the ability to interpret images and recognize and isolate specific physical properties of the scene. Images describing a single physical characteristic of an scene are called intrinsic images. These images would benefit most computer vision tasks which are often affected by the multiple complex effects that are usually found in natural images (cast shadows, specularities, interreflections...). In this thesis we will analyze the problem of intrinsic image estimation from different perspectives, including the theoretical formulation of the problem, the visual cues that can be used to estimate the intrinsic components and the evaluation mechanisms of the problem. We first give a brief introduction on the background and the nature of the problem of intrinsic image estimation and some of its closely related topics. Then, we present an exhaustive review of the literature of intrinsic images in the field of computer vision, giving a comprehensive and organized description of the existing techniques for intrinsic image estimation. We also examine the evaluation mechanisms that have been used so far in this problem. We analyze the existing databases and metrics, discuss the evolution of the problem and identify the recent trends in the field. Color information has been frequently ignored in the field of computer vision. In this work we present a method for intrinsic image decomposition which estimates the intrinsic reflectance and shading components of a single input image using observations from two different color attributes combined in a probabilistic framework. One of them, based on the semantic description of color used by humans, provides a sparse description of reflectances in an image. The other, based on an analysis of color distributions in the histogram space which connects local maxima, gives us a consistent description of surfaces sharing the same reflectance, providing stability of color-names in shadowed or near highlight regions of the image. Moreover, most methods for intrinsic image decomposition have usually assumed ``white light'' in the scenes and have completely ignored the effect of camera sensors in images. However, both factors strongly influence the resulting image values during the acquisition process. In this work we analyze the theoretical formulation underlying the decomposition problem and propose a generalized framework where we model the effects of both the camera sensors and the color of the illuminant. In this novel formulation we introduce a new reflectance component, called absolute reflectance, which is invariant to both effects. Furthermore, we demonstrate that any knowledge of the color of the illuminant or the camera sensors from input images can be used to improve the reflectance estimates of different existing methods for intrinsic image decomposition. Finally, we analyze the evaluation mechanisms of intrinsic images, which have continuously evolved during the last decade. In this thesis we present two datasets for intrinsic image evaluation. One is a calibrated dataset which includes ground truth information about the illuminant of the scene and the camera sensors. This dataset is used in this work to experimentally validate the theoretical framework for intrinsic image decomposition proposed in this thesis. The second dataset uses synthetic data and contains both simple objects and complex scenes under different illumination conditions. In this work we demonstrate that it is possible to build large and realistic datasets for intrinsic image evaluation using computer graphics software and rendering engines.

Les representacions de forma i registre són dos problemes importants tant en la visió per computador com en els gràfics. La representació d'un núvol de punts a través d'una funció implícita proporciona major nivell d'informació alhora de descriure les dades. Aquesta representació pot ser més compacta, més robusta al soroll i als \textit{outlier}, pel que pot ser explotada diferents aplicacions de visió per computador. La primera part d'aquesta tesi aborda representacions de forma implícites que inclouen tant la representació mitjançant \textit{B-splines} i polinomials. Primer es proposa una aproximació per mesurar la distancia geomètrica entre un núvol de punts i una superfície implícita. L'anàlisi de la distancia proposada mostra una estimació acurada amb un comportament suau. Aquesta distància és usada en un algorisme d'ajustament quadràtic basat en RANSAC. A més a més, atès que la informació de gradient de la distància respecte els paràmetres de la superfície pot ser calculat analíticament, els paràmetres de la superfície poden ser refinats utilitzant l'algorisme de Levenberg-Marquadt. Seguint un enfocament diferent, un algorisme d'ajustament algebraic es pot utilitzar per representar un objecte a través de \textit{B-splines} implícites. El resultat és una superfície suau i flexible que pot ser representada en diferents nivells de detall. Aquesta propietat ha estat explotada per solucionar el problema de registració a la segona part de la tesi. En el mètode de registració proposat, el model és substituït amb la representació implícita proposada en la primera part, i desprès la registració punt a punt és converteix en una registració punt a model en un nivell superior d'abstracció. Aquesta representació es pot beneficiar de diferents distancies per accelerar el proces de registració sense haver de cercar correspondències. Finalment, el problema de registre de models no rígids és abordat mitjançant d'una aproximació de la distància quadràtica que està basada en la informació de la curvatura del conjunt de models. Aquesta aproximació s'utilitza en un model \textit{Free Form Deformation} (FFD) per actualitzar la seva xarxa de control. Després és mostra com una aproximació acurada de la distància pot beneficiar el problema de registració no-rígida. / Shape representation and registration are two important problems in computer vision and graphics. Representing the given cloud of points through an implicit function provides a higher level information describing the data. This representation can be more compact more robust to noise and outliers, hence it can be exploited in different computer vision application. In the first part of this thesis implicit shape representations, including both implicit B-spline and polynomial, are tackled. First, an approximation of a geometric distance is proposed to measure the closeness of the given cloud of points and the implicit surface. The analysis of the proposed distance shows an accurate distance with smooth behavior. The distance by itself is used in a RANSAC based quadratic fitting method. Moreover, since the gradient information of the distance with respect to the surface parameter can be analytically computed, it is used in Levenberg-Marquadt algorithm to refine the surface parameters. In a different approach, an algebraic fitting method is used to represent an object through implicit B-splines. The outcome is a smooth flexible surface and can be represented in different level from coarse to fine. This property has been exploited to solve the registration problem in the second part of the thesis. In the proposed registration technique the model set is replaced with an implicit representation provided in the first part; then, the point-to-point registration is converted to a point-to-model one in a higher level. This registration error can benefit from different distance estimations to speed up the registration process even without need of correspondence search. Finally, the non-rigid registration problem is tackled through a quadratic distance approximation that is based on the curvature information of the model set. This approximation is used in a free form deformation model to update its control lattice. Then it is shown how an accurate distance approximation can benefit non-rigid registration problem.

This thesis addresses the development of techniques to build fully-automatic tools for analyzing sequential programs written in imperative languages like C or C++. In order to do the reasoning about programs, the approach taken in this thesis follows the constraint-based method used in program analysis. The idea of the constraint-based method is to consider a template for candidate invariant properties, e.g., linear conjunctions of inequalities. These templates involve both program variables as well as parameters whose values are initially unknown and have to be determined so as to ensure invariance. To this end, the conditions on inductive invariants are expressed by means of constraints (hence the name of the approach) on the unknowns. Any solution to these constraints then yields an invariant. In particular, if linear inequalities are taken as target invariants, conditions can be transformed into arithmetic constraints over the unknowns by means of Farkas' Lemma. In the general case, a Satisfiability Modulo Theories (SMT) problem over non-linear arithmetic is obtained, for which effective SMT solvers exist. One of the novelties of this thesis is the presentation of an optimization version of the SMT problems generated by the constraint-based method in such a way that, even when they turn out to be unsatisfiable, some useful information can be obtained for refining the program analysis. In particular, we show in this work how our approach can be exploited for proving termination of sequential programs, disproving termination of non-deterministic programs, and do compositional safety verification. Besides, an extension of the constraint-based method to generate universally quantified array invariants is also presented. Since the development of practical methods is a priority in this thesis, all the techniques have been implemented and tested with examples coming from academic and industrial environments. The main contributions of this thesis are summarized as follows: 1. A new constraint-based method for the generation of universally quantified invariants of array programs. We also provide extensions of the approach for sorted arrays. 2. A novel Max-SMT-based technique for proving termination. Thanks to expressing the generation of a ranking function as a Max-SMT optimization problem where constraints are assigned different weights, quasi-ranking functions -functions that almost satisfy all conditions for ensuring well-foundedness- are produced in a lack of ranking functions. Moreover, Max-SMT makes it easy to combine the process of building the termination argument with the usually necessary task of generating supporting invariants. 3. A Max-SMT constraint-based approach for proving that programs do not terminate. The key notion of the approach is that of a quasi-invariant, which is a property such that if it holds at a location during execution once, then it continues to hold at that location from then onwards. Our technique considers for analysis strongly connected subgraphs of a program's control flow graph and thus produces more generic witnesses of non-termination than existing methods. Furthermore, it can handle programs with unbounded non-determinism. 4. An automated compositional program verification technique for safety properties based on quasi-invariants. For a given program part (e.g., a single loop) and a postcondition, we show how to, using a Max-SMT solver, an inductive invariant together with a precondition can be synthesized so that the precondition ensures the validity of the invariant and that the invariant implies the postcondition. From this, we build a bottom-up program verification framework that propagates preconditions of small program parts as postconditions for preceding program parts. The method recovers from failures to prove validity of a precondition, using the obtained intermediate results to restrict the search space for further proof attempts. / Esta tesis se centra en el desarrollo de técnicas para construir herramientas altamente automatizadas que analicen programas secuenciales escritos en lenguajes imperativos como C o C++. Para realizar el razonamiento sobre los programas, la aproximación tomada en esta tesis se basa en un conocido método basado en restricciones utilizado en análisis de progamas. La idea de dicho método consiste en considerar plantillas que expresen propiedades invariantes candidatas, p.e., conjunciones de desigualdades lineales. Estas plantillas contienen tanto variables del programa como parámetros cuyos valores son inicialmente desconocidos y tienen que ser determinados para garantizar la invariancia. Para este fin, las condiciones sobre invariantes inductivos son expresadas mediante restricciones sobre los valores desconocidos. Cualquier solución a estas restricciones llevan a un invariante. En particular, si desigualdades lineales son los invariantes objetivo, las condiciones pueden ser transformadas en restricciones aritméticas sobre los valores desconocidos mediante el lema de Farkas. En el caso general, un problema de Satisfactibilidad Modulo Teorías (SMT) sobre aritmética no-lineal es obtenido, para el cual existen resolvedores eficientes. Una de las novedades de esta tesis es la presentación de una versión de optimización de los problemas SMT generados por el método tal que, incluso cuando son insatisfactibles, se puede obtener cierta información útil para refinar el análisis del programa. En particular, en este trabajo se muestra como la aproximación tomada puede usarse para probar terminación de programas, probar la no terminación de programas y realizar verificación por partes de la corrección de programas. Además, también se describe una extensión del método basado en restricciones para generar invariantes universalmente cuantificados sobre arrays. Debido a que el desarrollo de métodos prácticos es una prioridad en esta tesis, todas las técnicas han sido implementadas y probadas con ejemplos extraídos del entorno académico e industrial. Las principales contribuciones de esta tesis pueden resumirse en: 1. Un nuevo método basado en restricciones para la generación de invariantes universalmente cuantificados sobre arrays. También se explica extensiones del método para aplicarlo a arrays ordenados. 2. Un técnica novedosa basada en Max-SMT para probar terminación. Gracias a expresar la generación de funciones de ranking como problemas de optimización Max-SMT, donde a las restricciones se les asigna diferentes pesos, se generan cuasi-funciones de ranking, funciones que casi satisfacen todas las condiciones que garantizan la existencia de una relación bien fundada, en ausencia de funciones de ranking. Además, Max-SMT facilita la combinación del proceso de construcción de un argumento de terminación con la tarea habitualmente necesaria de generar invariantes de apoyo. 3. Un método basado en restricciones y Max-SMT para probar que un programa no termina. El concepto clave del método es el de cuasi-invariante, que es una propiedad tal que si se cumple una vez en un punto del programa durante la ejecución, entonces continúa cumpliendose en ese punto desde entonces en adelante. Nuestra técnica considera en su análisis subgrafos fuertemente conexos del grafo de control de flujo del programa y produce testigos de no terminación más genéricos que otros métodos existentes. Además, es capaz de tratar programas con no determinismo. 4. Una técnica automatizada de verificación por partes de propiedades de corrección de un programa basada en cuasi-invariantes. Dado una parte de un programa (p.e., un único bucle) con una postcondición, se muestra como, usando Max-SMT, puede sintetizarse un invariante inductivo junto a una precondición que garantiza la validez del invariante y que el invariante implica la postcondición. Apartir de esto, se describe una infraestructura de verificación de programas de abajo a arriba que propaga precondiciones.