The first parts of this Thesis are focused on the study of the supervised evaluation of image segmentation algorithms. Supervised in the sense that the segmentation results are compared to a human-made annotation, known as ground truth, by means of different measures of similarity. The evaluation depends, therefore, on three main points. First, the image segmentation techniques we evaluate. We review the state of the art in image segmentation, making an explicit difference between those techniques that provide a flat output, that is, a single clustering of the set of pixels into regions; and those that produce a hierarchical segmentation, that is, a tree-like structure that represents regions at different scales from the details to the whole image. Second, ground-truth databases are of paramount importance in the evaluation. They can be divided into those annotated only at object level, that is, with marked sets of pixels that refer to objects that do not cover the whole image; or those with annotated full partitions, which provide a full clustering of all pixels in an image. Depending on the type of database, we say that the analysis is done from an object perspective or from a partition perspective. Finally, the similarity measures used to compare the generated results to the ground truth are what will provide us with a quantitative tool to evaluate whether our results are good, and in which way they can be improved. The main contributions of the first parts of the thesis are in the field of the similarity measures. First of all, from an object perspective, we review the used basic measures to compare two object representations and show that some of them are equivalent. In order to evaluate full partitions and hierarchies against an object, one needs to select which of their regions form the object to be assessed. We review and improve these techniques by means of a mathematical model of the problem. This analysis allows us to show that hierarchies can represent objects much better with much less number of regions than flat partitions. From a partition perspective, the literature about evaluation measures is large and entangled. Our first contribution is to review, structure, and deduplicate the measures available. We provide a new measure that we show that improves previous ones in terms of a set of qualitative and quantitative meta-measures. We also extend the measures on flat partitions to cover hierarchical segmentations. The second part of this Thesis moves from the evaluation of image segmentation to its application to object detection. In particular, we build on some of the conclusions extracted in the first part to generate segmented object candidates. Given a set of hierarchies, we build the pairs and triplets of regions, we learn to combine the set from each hierarchy, and we rank them using low-level and mid-level cues. We conduct an extensive experimental validation that show that our method outperforms the state of the art in many metrics tested.

Geometric constraint solving is a central topic in many fields such as parametric solid modeling, computer-aided design or chemical molecular docking. A geometric constraint problem consists of a set geometric objects on which a set of constraints is defined. Solving the geometric constraint problem means finding a placement for the geometric elements with respect to each other such that the set of constraints holds. Clearly, the primary goal of geometric constraint solving is to define rigid shapes. However an interesting problem arises when we ask whether allowing parameter constraint values to change with time makes sense. The answer is in the positive. Assuming a continuous change in the variant parameters, the result of the geometric constraint solving with variant parameters would result in the generation of families of different shapes built on top of the same geometric elements but governed by a fixed set of constraints. Considering the problem where several parameters change simultaneously would be a great accomplishment. However the potential combinatorial complexity make us to consider problems with just one variant parameter. Elaborating on work from other authors, we develop a new algorithm based on a new tool we have called h-graphs that properly solves the geometric constraint solving problem with one variant parameter. We offer a complete proof for the soundness of the approach which was missing in the original work. Dynamic geometry is a computer-based technology developed to teach geometry at secondary school, which provides the users with tools to define geometric constructions along with interaction tools such as drag-and-drop. The goal of the system is to show in the user's screen how the geometry changes in real time as the user interacts with the system. It is argued that this kind of interaction fosters students interest in experimenting and checking their ideas. The most important drawback of dynamic geometry is that it is the user who must know how the geometric problem is actually solved. Based on the fact that current user-computer interaction technology basically allows the user to drag just one geometric element at a time, we have developed a new dynamic geometry approach based on two ideas: 1) the underlying problem is just a geometric constraint problem with one variant parameter, which can be different for each drag-and-drop operation, and, 2) the burden of solving the geometric problem is left to the geometric constraint solver. Two classic and interesting problems in many computational models are the reachability and the tracing problems. Reachability consists in deciding whether a certain state of the system can be reached from a given initial state following a set of allowed transformations. This problem is paramount in many fields such as robotics, path finding, path planing, Petri Nets, etc. When translated to dynamic geometry two specific problems arise: 1) when intersecting geometric elements were at least one of them has degree two or higher, the solution is not unique and, 2) for given values assigned to constraint parameters, it may well be the case that the geometric problem is not realizable. For example computing the intersection of two parallel lines. Within our geometric constraint-based dynamic geometry system we have developed an specific approach that solves both the reachability and the tracing problems by properly applying tools from dynamic systems theory. Finally we consider Henneberg graphs, Laman graphs and tree-decomposable graphs which are fundamental tools in geometric constraint solving and its applications. We study which relationships can be established between them and show the conditions under which Henneberg constructions preserve graph tree-decomposability. Then we develop an algorithm to automatically generate tree-decomposable Laman graphs of a given order using Henneberg construction steps.

En aquesta tesis doctoral es presenta un nou mètode per al càlcul de desalineaments en sistemes òptics a partir del front d'ona a la sortida del sistema. El mètode parteix de l'ajust de polinomis de Zernike al front d'ona del sistema òptic, i estableix una funció de transformació entre els coeficients de Zernike i les variables de desalineament. En aquesta memòria es presenta el desenvolupament matemàtic del mètode i s'estableixen tres funcions de transformació: per sistema d'equacions lineals, per sistema d'equacions no lineals i per xarxes neuronals artificials. El mètode s’ha validat per simulació mitjançant l'aplicació d'aquestes tres funcions de transformació a un sistema òptic format per tres lents en què una d'elles està desalineada. Es presenten i comparen els resultats obtinguts en aplicar cada funció, on es mostra que per desalineaments senzills les tres funcions donen bons resultats, però per desalineaments complexes s'ha necessitat aplicar el mètode amb les xares neuronals en dos passos, un per a les variables de gir i un altre per les variables de descentrament. S'ha generalitzat el mètode per més d'un element desalineat, mostrant resultats satisfactoris en el càlcul de desalineaments per dos elements del triplet mitjançant les xarxes neuronals. / En esta tesis doctoral se presenta un nuevo método para el cálculo de desalineamientos en sistemas ópticos a partir del frente de onda a la salida del mismo. El método parte del ajuste de polinomios de Zernike al frente de onda del sistema óptico, y establece una función de transformación entre los coeficientes de Zernike y las variables de desalineamiento. En esta memoria se presenta el desarrollo matemático del método y se establecen tres funciones de transformación: por sistema de ecuaciones lineales, por sistema de ecuaciones no lineales y por redes neuronales artificiales. El método se valida por simulación mediante la aplicación de estas tres funciones de transformación a un sistema óptico formado por tres lentes en el que una de ellas es desalineada. Se presentan y comparan los resultados obtenidos en aplicar cada función, donde se muestra que para desalineamientos sencillos las tres funciones dan buenos resultados, sin embargo para desalineamientos complejos se ha necesitado aplicar el método mediante las redes neuronales en dos pasos, uno para las variables de giro y otro para las variables de descentramiento. Se ha generalizado el método para más de un elemento desalineado, mostrando resultados satisfactorio en el cálculo de desalineamientos para dos elementos del triplete. / In this thesis a new method to determine element misalignments in optical systems is presented. The method starts with the adjustment of Zernike polynomials to the wavefront of the optical system, and sets a transformation function between the Zernike coefficients and the misalignment variables. Herein we present the mathematical development of the method and three transformation functions: a system of linear equations, a system of nonlinear equations and artificial neural networks. The method is validated by simulation by applying the three transformation functions to an optical system composed of three lenses in which one of them is misaligned. We present and compare the results of applying each function, showing that for simple misalignments the three functions work well, however, for complex misalignments, it has been required to apply the method with the artificial neural networks in two steps, one for decentering variables and one for tilt variables. The method has been generalized for more than one element, showing satisfactory results in the calculation of misalignment for two elements of the triplet system.

Matrix computations lie at the heart of most scientific computational tasks. The solution of linear systems of equations is a very frequent operation in many fields in science, engineering, surveying, physics and others. Other matrix operations occur frequently in many other fields such as pattern recognition and classification, or multimedia applications. Therefore, it is important to perform matrix operations efficiently. The work in this thesis focuses on the efficient execution on commodity processors of matrix operations which arise frequently in different fields.We study some important operations which appear in the solution of real world problems: some sparse and dense linear algebra codes and a classification algorithm. In particular, we focus our attention on the efficient execution of the following operations: sparse Cholesky factorization; dense matrix multiplication; dense Cholesky factorization; and Nearest Neighbor Classification.A lot of research has been conducted on the efficient parallelization of numerical algorithms. However, the efficiency of a parallel algorithm depends ultimately on the performance obtained from the computations performed on each node. The work presented in this thesis focuses on the sequential execution on a single processor.There exists a number of data structures for sparse computations which can be used in order to avoid the storage of and computation on zero elements. We work with a hierarchical data structure known as hypermatrix. A matrix is subdivided recursively an arbitrary number of times. Several pointer matrices are used to store the location ofsubmatrices at each level. The last level consists of data submatrices which are dealt with as dense submatrices. When the block size of this dense submatrices is small, the number of zeros can be greatly reduced. However, the performance obtained from BLAS3 routines drops heavily. Consequently, there is a trade-off in the size of data submatrices used for a sparse Cholesky factorization with the hypermatrix scheme. Our goal is that of reducing the overhead introduced by the unnecessary operation on zeros when a hypermatrix data structure is used to produce a sparse Cholesky factorization. In this work we study several techniques for reducing such overhead in order to obtain high performance.One of our goals is the creation of codes which work efficiently on different platforms when operating on dense matrices. To obtain high performance, the resources offered by the CPU must be properly utilized. At the same time, the memory hierarchy must be exploited to tolerate increasing memory latencies. To achieve the former, we produce inner kernels which use the CPU very efficiently. To achieve the latter, we investigate nonlinear data layouts. Such data formats can contribute to the effective use of the memory system.The use of highly optimized inner kernels is of paramount importance for obtaining efficient numerical algorithms. Often, such kernels are created by hand. However, we want to create efficient inner kernels for a variety of processors using a general approach and avoiding hand-made codification in assembly language. In this work, we present an alternative way to produce efficient kernels automatically, based on a set of simple codes written in a high level language, which can be parameterized at compilation time. The advantage of our method lies in the ability to generate very efficient inner kernels by means of a good compiler. Working on regular codes for small matrices most of the compilers we used in different platforms were creating very efficient inner kernels for matrix multiplication. Using the resulting kernels we have been able to produce high performance sparse and dense linear algebra codes on a variety of platforms.In this work we also show that techniques used in linear algebra codes can be useful in other fields. We present the work we have done in the optimization of the Nearest Neighbor classification focusing on the speed of the classification process.Tuning several codes for different problems and machines can become a heavy and unbearable task. For this reason we have developed an environment for development and automatic benchmarking of codes which is presented in this thesis.As a practical result of this work, we have been able to create efficient codes for several matrix operations on a variety of platforms. Our codes are highly competitive with other state-of-art codes for some problems.

Dia a dia, la capacitat de detectar i reconèixer objectes en imatges automàticament es fa cada vegada més important. Des dels sistemes de seguretat i robots, als telèfons d'última generació i la realitat augmentada, tot dispositiu intel·ligent necessita conèixer el significat semàntic de la imatge. Aquesta tesi aborda el problema de la detecció ràpida d'objectes a partir de models basats en patrons. La cerca d'un objecte en imatges s'implementa evaluant la similitud entre el model i cada ubicació i escala possibles en una imatge. Aquí s'argumenta que utilitzar una representació d'objectes basada en una jerarquia de múltiples resolucions és una opció adequada que pot conduir a una excel·lent precisió i un càlcul molt ràpid. Com, per detectar a múltiples escales, la cerca de l'objecte s'efectua de forma implícita a múltiples resolucions, el fet d'utilitzar un model en múltiples resolucions permet una millor representació de l'objecte, gairebé sense cost computacional addicional. A més, un model multiresolució s'adapta de forma natural a una cerca també en múltiples resolucions en la imatge, des de baixes a altes. Això ens porta a un conjunt d'acceleracions importants, degut a que es poden limitar el conjunt d'ubicacions on fer la cerca de l'objecte a nivells baixos de resolució, el que comporta un cost més reduït en l'avaluació del model. Una cerca jeràrquica de baixes a altes resolucions es pot fer utilizant una cascada de classificadors multiresolució, que elimina facils hipòtesis neagatives utilizant la baixa resolució. %basades en la probabilitat trobada en cada lloc on es fa la detecció, Un mètode alternatiu es basa en seleccionar localment, però de manera uniforme, les ubicacions de detecció a resolució baixa y propagarles fins a la resolució més alta. Aquest enfocament alternatiu, que llamem cerca coarse-to-fine, té una acceleració i rendiments semblants a la cascada de múltiples resolucions, però en un temps de computació independent del contingut de la imatge. La cerca coarse-to-fine s'ha estès a models deformables amb partes. En aquest enfocament, la jerarquia dels models se separa de forma recursiva en les subparts deformables de l'objecte a mesura que augmentem la resolució del model. D'aquesta manera, cada part s'ajusta a l'objecte en la imatge, produint una millor representació i, per tant una millor precisió en la detecció, juntament amb un temps computacional molt reduït. S'han validat els diferents models de multiresolució en diverses bases de dades conegudes i d'ús comú, mostrant que els resultats arriben a l'estat de l'art, però amb un cost computacional molt reduït. Finalment, es presenta una especialització d'aquest model multiresolució deformable per la tasca de detecció de vianants des de vehicles en moviment, que requereix tant una alta precisió com que el rendiment sigui en temps real. S'ha demostrat que la qualitat global del model proposat és superior als treballs anteriors i que té un grau de detecció de vianants fiable i ràpid utilitzant únicament informació de la imatge. / Día a día, la capacidad de detectar y reconocer objetos en imágenes automáticamente se hace cada vez más importante. Desde los sistemas de seguridad y los robots, a los teléfonos de última generación y la realidad aumentada, cada dispositivo inteligente necesita conocer el significado semántico de la imagen. Esta tesis aborda el problema de la detección rápida de objetos a partir de modelos basados en patrones. La búsqueda de un objeto en una imagen es el procedimiento de evaluar la similitud entre el modelo y cada ubicación y escala posible de la imagen. En esta tesis se argumenta que utilizar una representación del modelo de objetos basada en una jerarquía de resoluciones múltiples es una opción adecuada que puede conducir a una excelente precisión y un cálculo rápido. Como, para detectar a múltiples escalas, la búsqueda del objeto se efectúa de forma implícita en múltiples resoluciones, utilizar también un modelo de objetos con resoluciones múltiples permite una representación mejor del modelo, casi sin coste computacional adicional. Además, el modelo multiresolución se adapta de forma natural a una búsqueda sobre multiples resoluciones en la imagen, desde bajas a altas. Esto conduce a una doble aceleración debida a: un inicialmente reducido conjunto de ubicaciones en baja resolución donde realizar la búsqueda del objeto; un coste reducido de la evaluación del modelo. La búsqueda sobre multiples resoluciones puede efectuarse utilizando una cascada de clasificadores multirresolución, que elimina los ejemplos negativos en la resolución baja. Un método alternativo se basa en seleccionar localmente, pero de manera uniforme, las mejores detecciones a resolución baja y, luego, propagar estas hipothesis a los siguientes niveles de resolución. Este método, que llamamos búsqueda coarse-to-fine, tiene una aceleración parecida a la cascada de multiples resoluciones, pero el coste computacional es independiente del contenido de la imagen. La búsqueda coarse-to-fine se extiende a modelos deformables con partes. En este enfoque, la jerarquía de los modelos se separa de forma recursiva en las subpartes deformables a medida que aumenta la resolución del modelo. De esta manera, cada parte puede ajustarse al objecto en la imagen, produciendo una mejor representación y, por tanto, una mejor precisión en la detección con un tiempo computacional muy reducido. Se han validado los diferentes modelos de multirresolución en varias bases de datos de uso común, mostrando que los resultados alcanzan el estado del arte, pero con un coste computacional reducido. Por último, se presenta una especialización del modelo de multirresolución deformable para la tarea de detección de peatones desde vehículos en movimiento, que requiere tanto una alta precisión como un rendimiento en tiempo real. Se ha demostrado que la calidad global de nuestro modelo es superior a los trabajos anteriores y que puede producir una detección fiable de peatones basada solamente en imágenes. / Day by day, the ability to automatically detect and recognize objects in unconstrained images is becoming more and more important. From security systems and robots, to smart phones and augmented reality, every intelligent device needs to know the semantic meaning of an image. This thesis tackles the problem of fast object detection based on template models. Searching for an object in an image is the procedure of evaluating the similarity between the template model and every possible image location and scale. %the likelihood of the presence of that object. Here we argue that using a template model representation based on a multiple resolution hierarchy is an optimal choice that can lead to excellent detection accuracy and fast computation. As the search of the object is implicitly effectuated at multiple image resolutions to detect objects at multiple scales, using also a template model with multiple resolutions permits an improved model representation almost without any additional computational cost. Also, the hierarchy of multiple resolutions naturally adapts to a search over image resolutions, from coarse to fine. This leads to a double speed-up due to: an initially reduced set of coarse locations where to search for the object; a lower cost of evaluating the template model. The search over resolutions can be effectuated by using a cascade of multiresolution classifiers, which saves computation by early stopping the search at coarse level when finding easy negative examples. %pruning hypotheses based on the likelihood of each detection location, which leads to a cascade of multiresolution classifiers. An alternative approach is to locally but uniformly selecting the most promising detection locations at coarse level and, then, iteratively propagate only these ones to the finer resolutions, saving computation. This procedure, that we call coarse-to-fine search, has a speed-up similar to the multiresolution cascade, but a computational time independent of the image content. The coarse-to-fine search is then extended to deformable parts models. In this approach, as increasing the model resolution, the hierarchy of models is recursively separated into deformable subparts. In this way, each part can be aligned to the object in the image, producing a better representation and, therefore, an improved detection accuracy with still a reduced computational cost. We validate the different multiresolution models on several commonly used datasets, showing state-of-the-art results with a reduced computational cost. Finally, we specialize the multiresolution deformable model to the challenging task of pedestrian detection on moving vehicles, that requires both high accuracy and real-time performance. We show that the overall quality of our model is superior to previous works and it can lead to the first reliable pedestrian detection based only on images.

En aquesta tesi doctoral es descriu una metodologia per a l’evaluació del temps de resposta i la qualitat en la predicció de l’evolució d’emergències mediambientals. El treball s’ha centrat en el cas específic dels incendis forestals, com un dels desastres naturals més importants i devastadors, però és facilment extrapol·lable a altre tipus d’emèrgencies mediambientals. Existeixen molts entorns de predicció que es basen en l’ús de simuladors de l’evolució del fenòmen catastròfic. Donat el creixent poder quant a capacitat de cómput que ens ofereixen els nous progressos computacionals, com les arquitectures multicore i manycore, i inclús els paradigmes de cómput distribuit, com Grid o Cloud Computing, sorgeix la necessitat d’explotar encertadament el poder computacional que aquests ens ofereixen. Aquest objectiu s’assoleix proporcionant la capacitat d’avaluar, per endavant, com les restriccions existents en el moment d’atendre un incendi forestal actiu afectaran als resultats que s’obtindran, en termes de qualitat (precisió) obtinguda, i temps necessari per prendre una decisió, i en conseqüència, tenir la capacitat de escollir la configuració més adient tant de l’estratègia de predicció, com dels recursos computacionals. Com a conseqüència, el sistema que deriva de l’aplicació d’aquesta metodologia no està dissenyat per ser un Sistema de Suport a les Decisions (DSS), però sí una eina de la que la majoria de DSSs per incendis forestals es poden beneficiar notablement. El problema s’ha tractat per mitjà de la caracterització del comportament d’aquests dos factors durant el procés de predicció. Per això, es presenta un mètode de predicció de dues etapes i s’utilitza com a base de treball, donat el notable augment de qualitat que proporciona en les prediccions. Aquesta metodologia implica haver de treballar amb tècniques pròpies del camp de la Intel.ligència Artificial, com són els Algorismes Genètics i els Arbres de Decisió, i també es recolza en un intens estudi estadístic de les bases de dades d’entrenament, compostes pels resultats de milers de simulacions. Els resultats obtinguts en aquest treball d’investigació de llarga durada són completament satisfactoris, i obren camí a nous reptes. A més, la flexibilitat que ofereix aquesta metodologia permet aplicar-la en qualsevol altre context d’emergència, el qual la converteix en una destacable i molt útil eina per lluitar contra aquestes catàstrofes. / En esta tesis doctoral se describe una metodología para la evaluación del tiempo de respuesta y la calidad en la predicción de la evolución de emergencias medioambientales. El trabajo se ha centrado en el caso específico de los incendios forestales, como uno de los desastres naturales más importantes y devastadores, pero es fácilmente extrapolable a otro tipo de emergencias medioambientales. Existen muchos entornos de predicción que se basan en el uso de simuladores de la evolución del fenómeno catastrófico. Dado el creciente poder en cuanto a capacidad de cómputo que nos ofrecen los nuevos avances computacionales, como las arquitecturas multicore y manycore, e incluso los paradigmas de cómputo distribuido, como Grid o Cloud Computing, surge la necesidad de ser capaces de explotar acertadamente el poder computacional que éstos nos ofrecen. Tal objetivo se alcanza proporcionando la capacidad de evaluar, de antemano, cómo las restricciones existentes a la hora de atender un incendio forestal activo afectarán a los resultados que se obtendrán, tanto en términos de calidad (precisión) obtenida, y tiempo necesario para tomar una decisión, y por consiguiente, tener la capacidad de escoger la configuración más adecuada tanto de la estrategia de predicción, como de los recursos computacionales. Como consecuencia, el sistema que deriva de la aplicación de esta metodología no está diseñado para ser un Sistema de Soporte a las Decisiones (DSS), pero sí una herramienta de la que la mayoría de DSSs para incendios forestales se pueden beneficiar notablemente. El problema se ha tratado por medio de la caracterización del comportamiento de estos dos factores durante el proceso de predicción. Para ello, un método de predicción de dos etapas es presentado y utilizado como base de trabajo, dado el notable aumento de calidad que proporciona en las predicciones. Esta metodología implica lidiar con técnicas propias del campo de la Inteligencia Artificial, como son los Algoritmos Genéticos y los Árboles de Decisión, y a su vez se apoya en un intenso estudio estadístico de bases de datos de entrenamiento, compuestas por los resultados de miles de distintas simulaciones. Los resultados obtenidos en este trabajo de investigación a largo plazo son completamente satisfactorios, y abren camino a nuevos retos. Además, la flexibilidad que ofrece la metodología permite aplicarla en cualquier otro contexto de emergencia, lo que la convierte en una destacable y muy útil herramienta para luchar contra estas catástrofes / This thesis describes a methodology for time response and quality assessment in natural hazards evolution prediction. This work has been focused on the specific case of forest fires as an important and worrisome catastrophe, but it can easily be extrapolated to all other kinds of natural hazards. There exist many prediction frameworks based on the use of simulators of the evolution of the hazard. Given the increasing computing capabilities allowed by new computing advances such as multicore and manycore architectures, and even distributed-computing paradigms, such as Grid and Cloud Computing, the need arises to be able to properly exploit the computational power they offer. This goal is fulfilled by introducing the capability to assess in advance how the present constraints at the time of attending to an ongoing forest fire will affect the results obtained from them, both in terms of quality (accuracy) obtained and time needed to make a decision, and therefore being able to select the most suitable configuration of both the prediction strategy and computational resources to be used. As a consequence, the framework derived from the application of this methodology is not supposed to be a new Decision Support System (DSS) for fire departments and Civil Protection agencies, but a tool from which most of forest fire (and other kinds of natural hazards) DSSs could benefit notably. The problem has been tackled by means of characterizing the behavior of these two factors during the prediction process. For this purpose, a two-stage prediction framework is presented and considered as a suitable and powerful strategy to enhance the quality of the predictions. This methodology involves dealing with Artificial Intelligence techniques, such as Genetic Algorithms and Decision Trees and also relies on a strong statistical study from training databases, composed of the results of thousands of different simulations. The results obtained in this long-term research work are fully satisfactory, and give rise to several new challenges. Moreover, the flexibility offered by the methodology allows it to be applied to other kinds of emergency contexts, which turns it into an outstanding and very useful tool in fighting against these catastrophes.

Entendre el contingut de les imatges és un dels grans reptes de la visió per computador. Arribar a ser capaços de reconèixer quins objectes apareixen en les imatges, quina acció hi realitzen, i finalment, entendre el per què esta succeïnt, és l'objectiu del topic de Image Understanding. El fet d'entendre què succeeix en un instant de temps, ja sigui capturat en una fotografia, en un vídeo o simplement la imatge retinguda en la retina de l'ull (humà o un robòtic) és un pas fonamental per tal de formar-n'hi part. Per exemple, per un robot o un cotxe intel·ligent, es imprescindible de reconèixer el que succeeix en el seu entorn per tal de poder-hi navegar i interactuar de forma segura. O bé, es pot interactuar amb el contingut d'una imatge i extreure'n conceptes textuals per desprès ser utilitzats en els buscadors d'Internet actuals. En aquesta tesis es pretén descobrir què apareix en una imatge, i com extreure'n informació semàntica de més alt nivell. En altres paraules, l'objectiu és el de categoritzar i localitzar els objectes dins d'una imatge. Abans de res, per tal d'aprofundir en el coneixement sobre la formació d'imatges, proposem un mètode que aprèn a reconèixer alguna de les propietats físiques que han creat la imatge. Combinant informació fotomètrica i geomètrica, aprenem a dir si un gradient ha estat format pel material de l'objecte dins l'escena o bé si ha estat causat per alteracions a l'escena com ombres o reflexos. Endinsant-nos en l'àmbit del reconeixement semàntic dels objectes, ens centrem en dues aproximacions per a descriure els objectes. En la primera volem reconèixer quina categoria d'objecte s'amaga darrera de cada píxel, el que s'anomena segmentació semàntica. La segona aproximació s'inclou dins el tòpic de detecció d'objectes, en el que no són tan important els píxels, sinó l'objecte sencer i es es representa a través d'un requadre envoltant l'objecte. La segmentació semàntica és un problema en el que la ambigüitat dels píxels s'ha de resoldre a través d'afegir característiques contextuals. Nosaltres proposem que el context a varis nivells d'escala s'ha de tractar de forma diferent. A baix nivell ens podem aprendre si l'aparen\c{c}a d'un píxel podria representar l'objecte o no, però per estar-ne més segurs es requereix de més informació. En els metodes que proposem, incloim la informació de entitat i la coherencia amb la resta de l'escena, introduint la co-ocurrència semàntica. Pel que fa a la detecció d'objectes, es proposen dos nous algoritmes. El primer, es basa en millorar la representació d'objectes a nivell local, introduint el concepte de factorització d'aparences. D'aquesta manera, un objecte esta representat per diferents parts, i cada una de les parts podria ser representada per més d'una aparen\c{c}a. Finalment, l'últim mètode proposat adre\c{c}a el problema computacional de reconèixer i localitzar milers de categories d'objectes en una imatge. El principi bàsic és el de crear representacions d'objectes que siguin útils per qualsevol tipus d'objecte, i així reaprofitar la computació de la representació. / Entender el contenido de las imágenes es uno de los grandes retos de la visión por computador. Llegar a reconocer cuales son los objetos que aparecen en las imágenes, qué acciones están realizando, y finalmente, entender el porqué sucede, es el objetivo del tópico de "Image Understanding". El hecho de entender que está sucediendo en un tiempo determinado, ya sea mediante la toma de una fotografía, en un video, o simplemente la imagen reflejada en la retina del ojo (humano o robótico) es una paso fundamental para llegar a formar parte de ese instante. Por ejemplo, para un robot o coche inteligente, es imprescindible reconocer que sucede al su alrededor para poder navegar y interactuar con el entorno de forma segura. Otro ejemplo se puede encontrar en el hecho de interactuar con el contenido de las imágenes, de modo que se puedan extraer conceptos textuales de esta, para luego ser utilizados en los buscadores de Internet actuales. En esta tesis se pretende descubrir que aparece en una imagen, y como se puede extraer información semántica de mas alto nivel. En otras palabras, el objetivo es el de categorizar y localizar los objetos dentro de una imagen. Antes de nada, para profundizar en el conocimiento sobre la formación de las imágenes, proponemos un método que aprende a reconocer las propiedades físicas que han creado la imagen. Combinando información fotométrica y geométrica, podemos aprender a decir si un gradiente ha sido creado por variaciones en el materiales de los objetos o bien, si es causado por alteraciones en la escena como sombras o reflejos. Entrando en el ámbito del reconocimiento semántico de los objetos, nos centramos en dos aproximaciones para describir los objetos. En la primera, queremos reconocer qué categoría de objeto se esconde detrás de los pixeles, lo que denominamos segmentación semántica de imágenes. La segunda aproximación se incluye en el tópico de detección de objetos}, en el que no es tan importante el resultado en los pixeles, sino dónde se encuentra un objeto entero. Se representa a través de un recuadro que envuelve el objeto. La segmentación semántica es un problema en el que la ambigüedad de los pixeles se debe resolver a través de añadir características contextuales. Nosotros proponemos que el contexto a varios niveles de escala se debe tratar de forma distinta. A bajo nivel, podemos aprender si la apariencia de un pixel podría parecerse a la del objeto o no, pero para estar seguros se requiere mas información. En los métodos que proponemos, añadimos información del objeto como entidad y la coherencia con el resto de la escena, introduciendo el concepto de co-ocurréncia semántica. En cuanto a la detección de objetos, se proponen dos nuevos algoritmos. El primero, se basa en mejorar la representación de los objetos a nivel local, con el concepto de factorización de apariencias. De este modo, un objeto se representa con varias partes, y cada una de las partes puede ser representada por más de una apariencia. Finalmente, el último método propuesto aborda el problema computacional de reconocer y localizar miles de categorías de objetos en una imagen. El principio básico es el de crear representaciones que objetos que sean útiles para cualquier tipo de objeto, y así reaprovechar la computación de la representación. / Understand the content of the images is one of the great challenges of computer vision. Being able to recognize which are the objects in the images, what actions are doing, and finally understand why it happens, is the purpose of Image Understanding. The fact of understanding what is happening in a given time, either by taking a picture, video, or simply the image on the retina of the eye (human or robot) is a fundamental step to become part of that instant. For example, for a robot or smart car is essential to recognize what is succeeding to navigate around and interact with the environment safely. Another example can be found by interacting with the image content, so that their textual concepts can be used in modern Web searchers. This thesis seeks to discover what appears in a picture, and how to extract semantic information of higher level. In other words, the objective is to categorize and locate objects within an image. First of all, to deepen the knowledge on the formation of images, we propose a method that learns to recognize the physical properties that have created the image. By combining photometric and geometric information, we can learn to say whether a gradient is created by variations in the materials or objects, or it is caused by alterations in the scene as shadows or reflections. Entering the field of semantic recognition of objects, we focus on two approaches to describe the objects. First, we recognize which object category is hidden behind the pixels, which we call semantic segmentation. The second approach is included in the topic of object detection, which is not as important outcome in pixels, but where there is a whole object. Is represented by a frame which surrounds the object. Semantic segmentation is a problem in which the ambiguity of the pixels must be resolved by adding contextual features. We propose that the context at various scale levels should be treated differently. At low level, we learn whether the appearance of a pixel resembles the object or not, but to become confident, more information is required. We add information about the object as an entity and we enforce consistency with the rest of the scene, introducing the concept of semantic co-occurrence. As for object detection, we propose two new algorithms. The first is based on improving the representation of objects locally, with the concept of factorize appearances. Thus, an object is represented by several parts, and each of the parts can be represented by more than one appearance. Finally, the last proposed method addresses the computational problem of identifying and locating thousands of categories of objects in an image. The basic principle is to create representations of objects that are useful for any type of object, and thus reuse the computation of the performance.

El triatge de víctimes és una de les primeres i més importants tasques a realitzar en arribar a un escenari d'emergència. Aquest procés prioritza l'atenció mèdica a les víctima en base al nivell de les seves lesions. Aquest procés és molt important per a una assignació de recursos eficient i eficaç, sobretot en emergències de gran abast amb un gran nombre de víctimes. El procés de classificació de víctimes tradicional utilitza etiquetes de triatge com a indicador de l'estat de la víctima, una solució que comporta alguns inconvenients: Els metges han d'acostar-se a la víctima per veure el seu estat en l'etiqueta de paper, la pèrdua de l'etiqueta de triatge, etc. Avui dia, la informatització de les etiquetes de classificació és essencial per a una coordinació i atenció a les víctimes més ràpida. No obstant això, els escenaris d'emergència usualment es caracteritzen per la falta de xarxes sense fils disponibles per al seu ús. Xarxes sense fils basades en infraestructura com les xarxes de telefonia mòbil o les xarxes Wi-Fi solen destruir-se o saturar-se a causa d'un gran intent d'utilització o per la mateixa naturalesa de l'emergència. Algunes solucions proposen l'ús de sensors i la creació d'una xarxa de sensors sense fils per transmetre l'estat i la posició de les víctimes o el desplegament de repetidors per crear una MANET completament connectada. No obstant això, en grans emergències, això pot no ser possible a causa de l'extensió d'aquesta o pot no ser viable a causa del temps requerit per desplegar els repetidors. Aquesta tesi analitza les situacions d'emergència des del punt de vista de xarxes i comunicacions. Es proposa un sistema per a la classificació electrònica de víctimes fins i tot en casos sense cap tipus de xarxa disponible gràcies a la utilització de xarxes oportunistes i agents mòbils. També s'analitza el rendiment dels protocols de forwarding a les zones de desastre i es proposen algunes millores per reduir el consum d'energia. / El triaje de víctimas es una de las primeras y más importantes tareas al llegar a un escenario de emergencia. Este proceso prioriza la atención médica a las víctima en base al nivel de sus lesiones. Este proceso es muy importante para una asignación de recursos eficiente y eficaz, sobretodo en emergencias de gran abasto con un gran número de víctimas. El proceso de clasificación de víctimas tradicional utiliza etiquetas de triaje como indicador del estado de la víctima, una solución que con algunos inconvenientes: Los médicos tienen que acercarse a la víctima para ver su estado en la etiqueta de papel, la pérdida de la etiqueta de triaje, etc. Hoy en día, la informatización de las etiquetas de clasificación es esencial para una coordinación y atención a las víctimas más rápida. Sin embargo, los escenarios de emergencia usualmente se caracterizan por la falta de redes inalámbricas disponibles para su uso. Redes inalámbricas basadas en infraestructura como las redes de telefonía móvil o las redes Wi-Fi suelen destruirse o saturarse debido un gran intento de utilización o a la misma naturaleza de la emergencia. Algunas soluciones proponen el uso de sensores y la creación de una red de sensores inalámbricos para transmitir el estado y la posición de las víctimas o el despliegue de repetidores para crear una MANET completamente conectada. Sin embargo, en grandes emergencias, esto puede no ser posible debido a la extensión de esta o puede no ser viable debido al tiempo requerido para desplegar los repetidores. Esta tesis analiza las situaciones de emergencia desde el punto de vista de redes y comunicaciones. Se propone un sistema para la clasificación electrónica de víctimas incluso en casos sin ningún tipo de red disponible gracias a la utilización de redes oportunistas y agentes móviles. También se analiza el rendimiento de los protocolos de forwarding en las zonas de desastre y se proponen algunas mejoras para reducir el consumo de energía. / Triaging victims is the first and foremost task in an emergency scenario. This process priorizes victim's attention based on their injuries, very important for an efficient and effective resource allocation in mass casualty incidents which large amount of victims. Traditional triage process used paper triage tags as victim's injury level indicator, a solution that had some drawbacks: first responder had to go to the each victim to see their injury level on the paper triage tag, loss of the triage tag, etc. On today emergencies, an electronic triage tag is essential for a faster coordination and attention to victims. However, emergency scenarios are usually characterized by the lack of wireless networks to rely on. Infrastructure based wireless networks as mobile phone networks or Wi-Fi networks are usually destroyed or overused due to the very nature of the emergency. Some solutions propose the use of sensors, creating a wireless sensor networks to transmit the injury level and position of the victim or deploying repeaters to create a fully connected MANET. However, in large emergencies this may not be possible and the time required to deploy all the repeaters could be not worth. This thesis analyses emergencies from the communication point of view. It proposes a system for the electronic triage of victims and emergency management to work even in worst cases scenarios from the network communications perspective thanks to the use of opportunistic networks and mobile agents. It also analyses the performance of several forwarding protocols in disaster areas and proposes some improvements to reduce energy consumption.

Els motors de cerca d’Internet recullen i emmagatzemen informació sobre els seus usuaris per tal d’oferir-los millors serveis. A canvi de rebre un servei personalitzat, els usuaris perden el control de les seves pròpies dades. Els registres de cerca poden revelar informació sensible de l’usuari, o fins i tot revelar la seva identitat. En aquesta tesis tractem com limitar aquests problemes de privadesa mentre mantenim suficient informació a les dades. La primera part d’aquesta tesis tracta els mètodes per prevenir la recollida d’informació per part dels motores de cerca. Ja que aquesta informació es requerida per oferir un servei precís, l’objectiu es proporcionar registres de cerca que siguin adequats per proporcionar personalització. Amb aquesta finalitat, proposem un protocol que empra una xarxa social per tal d’ofuscar els perfils dels usuaris. La segona part tracta la disseminació de registres de cerca. Proposem tècniques que la permeten, proporcionant k-anonimat i minimitzant la pèrdua d’informació. / Web Search Engines collects and stores information about their users in order to tailor their services better to their users' needs. Nevertheless, while receiving a personalized attention, the users lose the control over their own data. Search logs can disclose sensitive information and the identities of the users, creating risks of privacy breaches. In this thesis we discuss the problem of limiting the disclosure risks while minimizing the information loss. The first part of this thesis focuses on the methods to prevent the gathering of information by WSEs. Since search logs are needed in order to receive an accurate service, the aim is to provide logs that are still suitable to provide personalization. We propose a protocol which uses a social network to obfuscate users' profiles. The second part deals with the dissemination of search logs. We propose microaggregation techniques which allow the publication of search logs, providing $k$-anonymity while minimizing the information loss.

El desenvolupament de noves tecnologies ha introduït el concepte de Computació Ubiqua, a on els objectes que ens envolten poden tenir processadors integrats i establir la comunicació amb altres sistemes, amb la finalitat d'oferir serveis personalitzats per ajudar-nos amb les nostres tasques habituals. No obstant això, a causa de que és possible tenir ordinadors en gairebé qualsevol lloc o objecte, això ha obert noves discussions sobre temes tals com la privadesa i la seguretat, considerats des de diferents punts de vista, com el desenvolupaments jurídics, socials, econòmics i tecnològics, amb una importància cada vegada major al món actual. En aquesta tesi discutim i analitzem algunes de les principals qüestions de seguretat i privadesa a les tecnologies actuals, tals com a telèfons intel·ligents, dispositius RFID o ciutats intel·ligents, i proposem alguns protocols per fer front a aquests temes garantint la privadesa dels usuaris a tot moment. / El desarrollo de nuevas tecnologías ha introducido el concepto de Computación Ubicua , en donde los objetos que nos rodean pueden tener procesadores integrados y establecer la comunicación con otros sistemas, con el fin de ofrecer servicios personalizados para ayudarnos con nuestras tareas habituales. Sin embargo, debido a que es posible tener ordenadores en casi cualquier lugar u objeto, esto ha abierto nuevas discusiones sobre temas tales como la privacidad y la seguridad, considerado desde diferentes puntos de vista, como el desarrollos jurídicos, sociales, económicos y tecnológicos, con una importancia cada vez mayor en el mundo actual. En esta tesis discutimos y analizamos algunas de las principales cuestiones de seguridad y privacidad en las tecnologías actuales, tales como teléfonos inteligentes, dispositivos RFID o ciudades inteligentes, y proponemos algunos protocolos para hacer frente a estos temas garantizando la privacidad de los usuarios en todo momento. / The development of new technologies has introduced the concept of Ubiquitous Computing, whereby the objects around us can have an embedded computer and establish communications with each other, in order to provide personalized services to assist with our tasks. However, because it is possible to have computers almost anywhere and within any object, this has opened up new discussions on issues such as privacy and security, considered from many different views, such as the legal, social, economic and technological development perspectives, all taking an increasingly significant importance in today’s world. In this dissertation we discuss and analyze some of the main privacy and security issues in current technologies, such as smartphones, RFIDs or smart cities, and we propose some protocols in order to face these issues guarantying users' privacy anytime.