Efficient Model-based 3D Tracking by Using Direct Image Registration

This thesis deals with the problem of efficiently tracking 3D objects in sequences of images. We tackle the efficient 3D tracking problem by using direct image registration. This problem is posed as an iterative optimization procedure that minimizes a brightness error norm. We review the most popular iterative methods for image registration in the literature, turning our attention to those algorithms that use efficient optimization techniques. Two forms of efficient registration algorithms are investigated. The first type comprises the additive registration algorithms: these algorithms incrementally compute the motion parameters by linearly approximating the brightness error function. We centre our attention on Hager and Belhumeur’s factorization-based algorithm for image registration. We propose a fundamental requirement that factorization-based algorithms must satisfy to guarantee good convergence, and introduce a systematic procedure that automatically computes the factorization. Finally, we also bring out two warp functions to register rigid and nonrigid 3D targets that satisfy the requirement. The second type comprises the compositional registration algorithms, where the brightness function error is written by using function composition. We study the current approaches to compositional image alignment, and we emphasize the importance of the Inverse Compositional method, which is known to be the most efficient image registration algorithm. We introduce a new algorithm, the Efficient Forward Compositional image registration: this algorithm avoids the necessity of inverting the warping function, and provides a new interpretation of the working mechanisms of the inverse compositional alignment. By using this information, we propose two fundamental requirements that guarantee the convergence of compositional image registration methods. Finally, we support our claims by using extensive experimental testing with synthetic and real-world data. We propose a distinction between image registration and tracking when using efficient algorithms. We show that, depending whether the fundamental requirements are hold, some efficient algorithms are eligible for image registration but not for tracking.

A Hierarchical Tracking Strategy for Vision-Based Applications On-Board UAVs

In this paper, we apply a hierarchical tracking strategy of planar objects (or that can be assumed to be planar) that is based on direct methods for vision-based applications on-board UAVs. The use of this tracking strategy allows to achieve the tasks at real-time frame rates and to overcome problems posed by the challenging conditions of the tasks: e.g. constant vibrations, fast 3D changes, or limited capacity on-board. The vast majority of approaches make use of feature-based methods to track objects. Nonetheless, in this paper we show that although some of these feature-based solutions are faster, direct methods can be more robust under fast 3D motions (fast changes in position), some changes in appearance, constant vibrations (without requiring any specific hardware or software for video stabilization), and situations in which part of the object to track is outside of the field of view of the camera. The performance of the proposed tracking strategy on-board UAVs is evaluated with images from realflight tests using manually-generated ground truth information, accurate position estimation using a Vicon system, and also with simulated data from a simulation environment. Results show that the hierarchical tracking strategy performs better than wellknown feature-based algorithms and well-known configurations of direct methods, and that its performance is robust enough for vision-in-the-loop tasks, e.g. for vision-based landing tasks.

Securing implementations of feedback-shift-register-based ciphers using compiler optimizations and co-processors

Los algoritmos basados en registros de desplazamiento con realimentación (en inglés FSR) se han utilizado como generadores de flujos pseudoaleatorios en aplicaciones con recursos limitados como los sistemas de apertura sin llave. Se considera canal primario a aquel que se utiliza para realizar una transmisión de información. La aparición de los ataques de canal auxiliar (en inglés SCA), que explotan información filtrada inintencionadamente a través de canales laterales como el consumo, las emisiones electromagnéticas o el tiempo empleado, supone una grave amenaza para estas aplicaciones, dado que los dispositivos son accesibles por un atacante. El objetivo de esta tesis es proporcionar un conjunto de protecciones que se puedan aplicar de forma automática y que utilicen recursos ya disponibles, evitando un incremento sustancial en los costes y alargando la vida útil de aplicaciones que puedan estar desplegadas. Explotamos el paralelismo existente en algoritmos FSR, ya que sólo hay 1 bit de diferencia entre estados de rondas consecutivas. Realizamos aportaciones en tres niveles: a nivel de sistema, utilizando un coprocesador reconfigurable, a través del compilador y a nivel de bit, aprovechando los recursos disponibles en el procesador. Proponemos un marco de trabajo que nos permite evaluar implementaciones de un algoritmo incluyendo los efectos introducidos por el compilador considerando que el atacante es experto. En el campo de los ataques, hemos propuesto un nuevo ataque diferencial que se adapta mejor a las condiciones de las implementaciones software de FSR, en las que el consumo entre rondas es muy similar. SORU2 es un co-procesador vectorial reconfigurable propuesto para reducir el consumo energético en aplicaciones con paralelismo y basadas en el uso de bucles. Proponemos el uso de SORU2, además, para ejecutar algoritmos basados en FSR de forma segura. Al ser reconfigurable, no supone un sobrecoste en recursos, ya que no está dedicado en exclusiva al algoritmo de cifrado. Proponemos una configuración que ejecuta múltiples algoritmos de cifrado similares de forma simultánea, con distintas implementaciones y claves. A partir de una implementación sin protecciones, que demostramos que es completamente vulnerable ante SCA, obtenemos una implementación segura a los ataques que hemos realizado. A nivel de compilador, proponemos un mecanismo para evaluar los efectos de las secuencias de optimización del compilador sobre una implementación. El número de posibles secuencias de optimizaciones de compilador es extremadamente alto. El marco de trabajo propuesto incluye un algoritmo para la selección de las secuencias de optimización a considerar. Debido a que las optimizaciones del compilador transforman las implementaciones, se pueden generar automáticamente implementaciones diferentes combinamos para incrementar la seguridad ante SCA. Proponemos 2 mecanismos de aplicación de estas contramedidas, que aumentan la seguridad de la implementación original sin poder considerarse seguras. Finalmente hemos propuesto la ejecución paralela a nivel de bit del algoritmo en un procesador. Utilizamos la forma algebraica normal del algoritmo, que automáticamente se paraleliza. La implementación sobre el algoritmo evaluado mejora en rendimiento y evita que se filtre información por una ejecución dependiente de datos. Sin embargo, es más vulnerable ante ataques diferenciales que la implementación original. Proponemos una modificación del algoritmo para obtener una implementación segura, descartando parcialmente ejecuciones del algoritmo, de forma aleatoria. Esta implementación no introduce una sobrecarga en rendimiento comparada con las implementaciones originales. En definitiva, hemos propuesto varios mecanismos originales a distintos niveles para introducir aleatoridad en implementaciones de algoritmos FSR sin incrementar sustancialmente los recursos necesarios. ABSTRACT Feedback Shift Registers (FSR) have been traditionally used to implement pseudorandom sequence generators. These generators are used in Stream ciphers in systems with tight resource constraints, such as Remote Keyless Entry. When communicating electronic devices, the primary channel is the one used to transmit the information. Side-Channel Attack (SCA) use additional information leaking from the actual implementation, including power consumption, electromagnetic emissions or timing information. Side-Channel Attacks (SCA) are a serious threat to FSR-based applications, as an attacker usually has physical access to the devices. The main objective of this Ph.D. thesis is to provide a set of countermeasures that can be applied automatically using the available resources, avoiding a significant cost overhead and extending the useful life of deployed systems. If possible, we propose to take advantage of the inherent parallelism of FSR-based algorithms, as the state of a FSR differs from previous values only in 1-bit. We have contributed in three different levels: architecture (using a reconfigurable co-processor), using compiler optimizations, and at bit level, making the most of the resources available at the processor. We have developed a framework to evaluate implementations of an algorithm including the effects introduced by the compiler. We consider the presence of an expert attacker with great knowledge on the application and the device. Regarding SCA, we have presented a new differential SCA that performs better than traditional SCA on software FSR-based algorithms, where the leaked values are similar between rounds. SORU2 is a reconfigurable vector co-processor. It has been developed to reduce energy consumption in loop-based applications with parallelism. In addition, we propose its use for secure implementations of FSR-based algorithms. The cost overhead is discarded as the co-processor is not exclusively dedicated to the encryption algorithm. We present a co-processor configuration that executes multiple simultaneous encryptions, using different implementations and keys. From a basic implementation, which is proved to be vulnerable to SCA, we obtain an implementation where the SCA applied were unsuccessful. At compiler level, we use the framework to evaluate the effect of sequences of compiler optimization passes on a software implementation. There are many optimization passes available. The optimization sequences are combinations of the available passes. The amount of sequences is extremely high. The framework includes an algorithm for the selection of interesting sequences that require detailed evaluation. As existing compiler optimizations transform the software implementation, using different optimization sequences we can automatically generate different implementations. We propose to randomly switch between the generated implementations to increase the resistance against SCA.We propose two countermeasures. The results show that, although they increase the resistance against SCA, the resulting implementations are not secure. At bit level, we propose to exploit bit level parallelism of FSR-based implementations using pseudo bitslice implementation in a wireless node processor. The bitslice implementation is automatically obtained from the Algebraic Normal Form of the algorithm. The results show a performance improvement, avoiding timing information leakage, but increasing the vulnerability against differential SCA.We provide a secure version of the algorithm by randomly discarding part of the data obtained. The overhead in performance is negligible when compared to the original implementations. To summarize, we have proposed a set of original countermeasures at different levels that introduce randomness in FSR-based algorithms avoiding a heavy overhead on the resources required.

Análisis biomecánico del segmento de la carrera a pie de la competición en triatlón

El principal objetivo de la presente investigación fue el conocer el perfil de rendimiento técnico de los triatletas, desde un punto de vista biomecánica, en el segmento carrera a pie durante la competición en triatlón. Asimismo, como el genero y el nivel deportivo del triatleta podrían influir en su respuesta motriz durante la competicion. Para ello, se necesitaba desarrollar y validar una técnica experimental que fuera lo suficientemente precisa (validez interna), con una alta fiabilidad y con una gran validez externa (ecologica) debido al entorno de la competicion. La muestra la formaron un total de 64 deportistas: 32 triatletas participantes en la Copa del Mundo de Triatlon de Madrid-2008 (16 hombres y 16 mujeres) y 32 triatletas participantes en el Clasificatorio del Campeonato de Espana Elite (16 hombres y 16 mujeres). El análisis de la técnica de carrera de los deportistas se realizo mediante un sistema fotogramétrico en 2d que permitió calcular las coordenadas (x,y) de los centros articulares con un error de 1.66% en el eje x y de un 2.10% en el eje y. Las imágenes fueron obtenidas por una cámara que filmaba el movimiento en un plano antero-posterior del triatleta. Algoritmos basados en la DLT (Abdel-Aziz & Karara, 1971) permitieron conocer las coordenadas reales a partir de las coordenadas digitalizadas en el plano y posteriormente las distintas variables analizadas. El análisis biomecánica de la carrera se realizo en 4 ocasiones diferentes durante la competición, correspondiendo con cada una de las vueltas de 2,5 km, que el triatleta tenía que realizar. La velocidad de carrera resulto estar íntimamente ligada al nivel deportivo del triatleta. Del mismo modo, 3 de los 4 grupos analizados presentaron valores inferiores a 3 minutos 30 segundos por kilometro recorrido, poniendo de manifiesto el altísimo nivel de los sujetos analizados. Del mismo modo parece que las chicos consiguen una mayor velocidad gracias a una mayor longitud de ciclo en relación a las chicas, ya que estas muestran valores mayores en cuanto a frecuencia de zancada. La frecuencia de zancada presento los valores más altos en la primera vuelta en todos los deportistas analizados. Asimismo, los triatletas de nivel internacional y las chicas fueron los que mostraron los mayores valores. La longitud de zancada presento distintas tendencias en función del nivel y el género del deportista. Así pues, en los deportistas internacionales y en los chicos los mayores valores se encontraron en la primera vuelta mientras que la tendencia fue al descenso, siendo probablemente la fatiga acumulada la causante de dicha tendencia. En cambio, aquellos deportistas de nivel nacional y las chicas mostraron valores mayores en la segunda vuelta que en la primera, evidenciando que además de la fatiga, el ciclismo previo tiene una incidencia directa sobre su rendimiento. Los tiempos de vuelo permanecieron constantes durante toda la carrera, encontrando cierta evolución en los tiempos de apoyo, la cual provoca una modificación en los porcentajes relativos en los tiempos de vuelo. Los tiempos de apoyo más bajos se encontraron en la primera vuelta. Del mismo modo, los deportistas de nivel internacional y los chicos mostraron valores inferiores. También, estos grupos fueron más constantes en sus valores a lo largo de las vueltas. Por el contrario, se encontraron tendencias al aumento en los triatletas de nivel nacional y en las chicas, los cuales no fueron capaces de mantener el mismo rendimiento debido seguramente a su menor nivel deportivo. La oscilación vertical de la cadera se mostro constante en los triatletas de mayor nivel, encontrándose tendencias al aumento en los de menor nivel. Del mismo modo, los valores más altos correspondieron a las chicas y a los deportistas de nivel nacional. La distancia de la cadera al apoyo permaneció constante a lo largo de las vueltas en todos los grupos, obteniéndose valores mayores en los triatletas de nivel internacional y en los chicos. El ángulo de la rodilla apoyada en el momento del despegue no mostro una tendencia clara. Los deportistas de nivel internacional y los chicos presentaron los valores más bajos. El ángulo de la rodilla libre en el momento del despegue mostro una correlación muy alta con la velocidad de carrera. Del mismo modo, los ángulos más pequeños se encontraron en los triatletas internacionales y en los chicos, debido seguramente a los mayores valores de velocidad registrados por ambos grupos. Los ángulos de los tobillos no mostraron ninguna tendencia clara durante la competición analizada. Los cuatro grupos de población presentaron valores similares, por lo que parece que no representan una variable que pueda incidir sobre el rendimiento biomecánica del triatleta. Los resultados obtenidos en el presente estudio de investigación avalan la utilización de la fotogrametría-video en 2d para el análisis de la técnica de carrera durante la competición en triatlón. Su aplicación en una competición de máximo nivel internacional ha posibilitado conocer el perfil técnico que presentan los triatletas a lo largo del segmento de carrera a pie. Del mismo modo, se ha podido demostrar como los estudios realizados en laboratorio no reflejan la realidad competitiva de un triatlón de máximo nivel. The aim of this research was to determine the running technique profile during a triathlon competition from a biomechanical perspective. Also, to analyze the triathlete gender’s and level of performance’s influence on this profile in competition. An accurate (internal validity) and reliable methodology with a high external validity (ecological) had to be developed to get those aims in competition. Sixty-four triathletes were analyzed. 32 (16 males, 16 females) took part in the Madrid 2008 Triathlon World Cup and 32 (16 males and 16 females) took part in the Spanish Triathlon National Championships. The biomechanical analyses were carried out by a photogrammetric system that allow to calculate the landmarks coordinates (x,y) with a 1.66% error in x axis, and a 2.10% error in y axis. The frames were obtained with a camera situated perpendicular to the triathletes’ trajectory, filming the saggittal plane. DLT based algorithms (Abdel-Aziz & Karara, 1971) were used to calculate the real coordinates from the digitalized ones and the final variables afterwards. The biomechanical analisys itself was performed in four different moments during the competition, according to each 2.5 km lap the triathletes had to do. Running speed was highly related to performance level. Also, 3 of the 4 analyzed groups showed speed values under the 3 minutes and 30 seconds per kilometer. It demonstrated the very high performance level of the analized triathletes. Furthermore, it seems that men get higher speeds because their longer stride length, while women shows higher stride frequency values. The highest stride frequency values were found in the first lap. Women and the international level triathletes showed the highest values. Stride length showed different tendencies according to the gender and level of performance. Men and international level triathletes showed the highest level in the first lap and a decreasing tendency after that. The accumulated fatigue was probably the reason of this tendency. On the other hand, higher values than in first lap were found in the second one in women and national level triathletes. It demonstrated the previous cycling can affect to those groups in terms of biomechanics. Flight times remained constant during the running part, while the contact times showed an increasing tendency that caused a variation in flight times percents. The lowest contact times were found in the first lap and in men and international triathletes’ values. Also, these two groups were more consistent during the whole running. On the other hand, increasing tendencies were found in women and national level triathletes, who were not able to maintain the same values probably due to their lower level of performance. Higher level triathletes showed more consistent hip vertical oscillation values than lower level triathletes, who presented increasing tendencies. The highest values were found in women and national level triathletes. The horizontal distance hip-toe cap remained constant among the laps in all the groups. Men and international level triathletes showed the highest values. The support knee angle at toe-off did not show a clear tendency. The lowest values were found in men and international level triathletes. A high correlation was found between the non-support knee angle and the running speed. Furthermore, men and international level triathletes showed the smallest values, due to the higher velocities reached by these two groups. Ankles angles did not show any tendency during the running part. Similar values were found in the four analyzed groups, so this variable does not seem to represent an important one within the triathlete’s performance. The results obtained in the present research support the use of the bidimensional photogrammetric video-system to analyze the running technique during a triathlon competition. Its application in international triathlon meetings has allowed determining the triathletes’ technique profile during the running part. Also, it has been demonstrated the laboratory-based studies does not reproduce a top-level competition.

A hierarchical strategy for real-time tracking on-board UAVs

In this paper, we present a real-time tracking strategy based on direct methods for tracking tasks on-board UAVs, that is able to overcome problems posed by the challenging conditions of the task: e.g. constant vibrations, fast 3D changes, and limited capacity on-board. The vast majority of approaches make use of feature-based methods to track objects. Nonetheless, in this paper we show that although some of these feature-based solutions are faster, direct methods can be more robust under fast 3D motions (fast changes in position), some changes in appearance, constant vibrations (without requiring any specific hardware or software for video stabilization), and situations where part of the object to track is out the field of view of the camera. The performance of the proposed strategy is evaluated with images from real-flight tests using different evaluation mechanisms (e.g. accurate position estimation using a Vicon sytem). Results show that our tracking strategy performs better than well known feature-based algorithms and well known configurations of direct methods, and that the recovered data is robust enough for vision-in-the-loop tasks.

Response threshold models, stochastic learning automata and ant colony optimization-based decentralized self-coordination algorithms for heterogeneous multi-tasks distribution in multi-robot systems

In recent decades, there has been an increasing interest in systems comprised of several autonomous mobile robots, and as a result, there has been a substantial amount of development in the eld of Articial Intelligence, especially in Robotics. There are several studies in the literature by some researchers from the scientic community that focus on the creation of intelligent machines and devices capable to imitate the functions and movements of living beings. Multi-Robot Systems (MRS) can often deal with tasks that are dicult, if not impossible, to be accomplished by a single robot. In the context of MRS, one of the main challenges is the need to control, coordinate and synchronize the operation of multiple robots to perform a specic task. This requires the development of new strategies and methods which allow us to obtain the desired system behavior in a formal and concise way. This PhD thesis aims to study the coordination of multi-robot systems, in particular, addresses the problem of the distribution of heterogeneous multi-tasks. The main interest in these systems is to understand how from simple rules inspired by the division of labor in social insects, a group of robots can perform tasks in an organized and coordinated way. We are mainly interested on truly distributed or decentralized solutions in which the robots themselves, autonomously and in an individual manner, select a particular task so that all tasks are optimally distributed. In general, to perform the multi-tasks distribution among a team of robots, they have to synchronize their actions and exchange information. Under this approach we can speak of multi-tasks selection instead of multi-tasks assignment, which means, that the agents or robots select the tasks instead of being assigned a task by a central controller. The key element in these algorithms is the estimation ix of the stimuli and the adaptive update of the thresholds. This means that each robot performs this estimate locally depending on the load or the number of pending tasks to be performed. In addition, it is very interesting the evaluation of the results in function in each approach, comparing the results obtained by the introducing noise in the number of pending loads, with the purpose of simulate the robot's error in estimating the real number of pending tasks. The main contribution of this thesis can be found in the approach based on self-organization and division of labor in social insects. An experimental scenario for the coordination problem among multiple robots, the robustness of the approaches and the generation of dynamic tasks have been presented and discussed. The particular issues studied are: Threshold models: It presents the experiments conducted to test the response threshold model with the objective to analyze the system performance index, for the problem of the distribution of heterogeneous multitasks in multi-robot systems; also has been introduced additive noise in the number of pending loads and has been generated dynamic tasks over time. Learning automata methods: It describes the experiments to test the learning automata-based probabilistic algorithms. The approach was tested to evaluate the system performance index with additive noise and with dynamic tasks generation for the same problem of the distribution of heterogeneous multi-tasks in multi-robot systems. Ant colony optimization: The goal of the experiments presented is to test the ant colony optimization-based deterministic algorithms, to achieve the distribution of heterogeneous multi-tasks in multi-robot systems. In the experiments performed, the system performance index is evaluated by introducing additive noise and dynamic tasks generation over time.

Watching subgraphs to improve efficiency in maximum clique search

This paper describes a new technique referred to as watched subgraphs which improves the performance of BBMC, a leading state of the art exact maximum clique solver (MCP). It is based on watched literals employed by modern SAT solvers for boolean constraint propagation. In efficient SAT algorithms, a list of clauses is kept for each literal (it is said that the clauses watch the literal) so that only those in the list are checked for constraint propagation when a (watched) literal is assigned during search. BBMC encodes vertex sets as bit strings, a bit block representing a subset of vertices (and the corresponding induced subgraph) the size of the CPU register word. The paper proposes to watch two subgraphs of critical sets during MCP search to efficiently compute a number of basic operations. Reported results validate the approach as the size and density of problem instances rise, while achieving comparable performance in the general case.

Desing and development of a robotic platform for the evaluation of search algorithms

Plant diseases represent a major economic and environmental problem in agriculture and forestry. Upon infection, a plant develops symptoms that affect different parts of the plant causing a significant agronomic impact. As many such diseases spread in time over the whole crop, a system for early disease detection can aid to mitigate the losses produced by the plant diseases and can further prevent their spread [1]. In recent years, several mathematical algorithms of search have been proposed [2,3] that could be used as a non-invasive, fast, reliable and cost-effective methods to localize in space infectious focus by detecting changes in the profile of volatile organic compounds. Tracking scents and locating odor sources is a major challenge in robotics, on one hand because odour plumes consists of non-uniform intermittent odour patches dispersed by the wind and on the other hand because of the lack of precise and reliable odour sensors. Notwithstanding, we have develop a simple robotic platform to study the robustness and effectiveness of different search algorithms [4], with respect to specific problems to be found in their further application in agriculture, namely errors committed in the motion and sensing and to the existence of spatial constraints due to land topology or the presence of obstacles.

Fast 2D to 3D conversion using a clustering-based hierarchical search in a machine learning framework

Automatic 2D-to-3D conversion is an important application for filling the gap between the increasing number of 3D displays and the still scant 3D content. However, existing approaches have an excessive computational cost that complicates its practical application. In this paper, a fast automatic 2D-to-3D conversion technique is proposed, which uses a machine learning framework to infer the 3D structure of a query color image from a training database with color and depth images. Assuming that photometrically similar images have analogous 3D structures, a depth map is estimated by searching the most similar color images in the database, and fusing the corresponding depth maps. Large databases are desirable to achieve better results, but the computational cost also increases. A clustering-based hierarchical search using compact SURF descriptors to characterize images is proposed to drastically reduce search times. A significant computational time improvement has been obtained regarding other state-of-the-art approaches, maintaining the quality results.