Semi-global techniques in image matching and change detection with applications to civil and environmental engineering.

This work of thesis wants to present a dissertation of the wide range of modern dense matching algorithms, which are spreading in different application and research fields, with a particular attention to the innovative “Semi-Global” matching techniques. The choice of develop a semi-global numerical code was justified by the need of getting insight on the variables and strategies that affect the algorithm performances with the primary objective of maximizing the method accuracy and efficiency, and the results level of completeness. The dissertation will consist in the metrological characterization of the proprietary implementation of the semi-global matching algorithm, evaluating the influence of several matching variables and functions implemented in the process and comparing the accuracy and completeness of different results (digital surface models, disparity maps and 2D displacement fields) obtained using our code and other commercial and open-source matching programs in a wide variety of application fields.

Evaluation of confidence-driven cost aggregation strategies

In this thesis I describe eight new stereo matching algorithms that perform the cost-aggregation step using a guided filter with a confidence map as guidance image, and share the structure of a linear stereo matching algorithm. The results of the execution of the proposed algorithms on four pictures from the Middlebury dataset are shown as well. Finally, based on these results, a ranking of the proposed algorithms is presented.

QoE-aware power management in vehicle-to-grid networks:a matching-theoretic approach

Frequency, time and places of charging and discharging have critical impact on the Quality of Experience (QoE) of using Electric Vehicles (EVs). EV charging and discharging scheduling schemes should consider both the QoE of using EV and the load capacity of the power grid. In this paper, we design a traveling plan-aware scheduling scheme for EV charging in driving pattern and a cooperative EV charging and discharging scheme in parking pattern to improve the QoE of using EV and enhance the reliability of the power grid. For traveling planaware scheduling, the assignment of EVs to Charging Stations (CSs) is modeled as a many-to-one matching game and the Stable Matching Algorithm (SMA) is proposed. For cooperative EV charging and discharging in parking pattern, the electricity exchange between charging EVs and discharging EVs in the same parking lot is formulated as a many-to-many matching model with ties, and we develop the Pareto Optimal Matching Algorithm (POMA). Simulation results indicates that the SMA can significantly improve the average system utility for EV charging in driving pattern, and the POMA can increase the amount of electricity offloaded from the grid which is helpful to enhance the reliability of the power grid.

Matching theory based travel plan aware charging algorithms in V2G smart grid networks

The frequency, time and places of charging have large impact on the Quality of Experience (QoE) of EV drivers. It is critical to design effective EV charging scheduling system to improve the QoE of EV drivers. In order to improve EV charging QoE and utilization of CSs, we develop an innovative travel plan aware charging scheduling scheme for moving EVs to be charged at Charging Stations (CS). In the design of the proposed charging scheduling scheme for moving EVs, the travel routes of EVs and the utility of CSs are taken into consideration. The assignment of EVs to CSs is modeled as a two-sided many-to-one matching game with the objective of maximizing the system utility which reflects the satisfactory degrees of EVs and the profits of CSs. A Stable Matching Algorithm (SMA) is proposed to seek stable matching between charging EVs and CSs. Furthermore, an improved Learning based On-LiNe scheduling Algorithm (LONA) is proposed to be executed by each CS in a distributed manner. The performance gain of the average system utility by the SMA is up to 38.2% comparing to the Random Charging Scheduling (RCS) algorithm, and 4.67% comparing to Only utility of Electric Vehicle Concerned (OEVC) scheme. The effectiveness of the proposed SMA and LONA is also demonstrated by simulations in terms of the satisfactory ratio of charging EVs and the the convergence speed of iteration.

Fleet Management System for Search and Rescue Operations

Over one million people lost their lives in the last twenty years from natural disasters like wildfires, earthquakes and man-made disasters. In such scenarios the usage of a fleet of robots aims at the parallelization of the workload and thus increasing speed and capabilities to complete time sensitive missions. This work focuses on the development of a dynamic fleet management system, which consists in the management of multiple agents cooperating in order to accomplish tasks. We presented a Mixed Integer Programming problem for the management and planning of mission’s tasks. The problem was solved using both an exact and a heuristic approach. The latter is based on the idea of solving iteratively smaller instances of the complete problem. Alongside, a fast and efficient algorithm for estimation of travel times between tasks is proposed. Experimental results demonstrate that the proposed heuristic approach is able to generate quality solutions, within specific time limits, compared to the exact one.

Real-time scheduling with resource sharing on uniform multiprocessors

Consider the problem of scheduling a set of implicit-deadline sporadic tasks to meet all deadlines on a uniform multiprocessor platform where each task may access at most one of |R| shared resources and at most once by each job of that task. The resources have to be accessed in a mutually exclusive manner. We propose an algorithm, GIS-vpr, which offers the guarantee that if a task set is schedulable to meet deadlines by an optimal task assignment scheme that allows a task to migrate only when it accesses or releases a resource, then our algorithm also meets the deadlines with the same restriction on the task migration, if given processors 4 + 6|R| times as fast. The proposed algorithm, by design, limits the number of migrations per job to at most two. To the best of our knowledge, this is the first result for resource sharing on uniform multiprocessors with proven performance guarantee.

Employment by lotto revisited

We study employment by lotto (Aldershof et al., 1999), a matching algorithm for the so-called stable marriage problem. We complement Aldershof et al.'s analysis in two ways. First, we give an alternative and intuitive description of employment by lotto. Second, we disprove Aldershof et al.'s conjectures concerning employment by lotto for general matching markets.

Consistency and optimality

Assume that the problem Qo is not solvable in polynomial time. For theories T containing a sufficiently rich part of true arithmetic we characterize T U {ConT} as the minimal extension of T proving for some algorithm that it decides Qo as fast as any algorithm B with the property that T proves that B decides Qo. Here, ConT claims the consistency of T. Moreover, we characterize problems with an optimal algorithm in terms of arithmetical theories.

Characterization of myocardial deformation in patients with different etiologies of left ventricular hypertrophy by using strain distribution from Magnetic Resonance Imaging

Introducción y objetivos. Se ha señalado que, en la miocardiopatía hipertrófica (MCH), la desorganización de las fibras regionales da lugar a segmentos en los que la deformación es nula o está gravemente reducida, y que estos segmentos tienen una distribución no uniforme en el ventrículo izquierdo (VI). Esto contrasta con lo observado en otros tipos de hipertrofia como en el corazón de atleta o la hipertrofia ventricular izquierda hipertensiva (HVI-HT), en los que puede haber una deformación cardiaca anormal, pero nunca tan reducida como para que se observe ausencia de deformación. Así pues, proponemos el empleo de la distribución de los valores de strain para estudiar la deformación en la MCH. Métodos. Con el empleo de resonancia magnética marcada (tagged), reconstruimos la deformación sistólica del VI de 12 sujetos de control, 10 atletas, 12 pacientes con MCH y 10 pacientes con HVI-HT. La deformación se cuantificó con un algoritmo de registro no rígido y determinando los valores de strain sistólico máximo radial y circunferencial en 16 segmentos del VI. Resultados. Los pacientes con MCH presentaron unos valores medios de strain significativamente inferiores a los de los demás grupos. Sin embargo, aunque la deformación observada en los individuos sanos y en los pacientes con HVI-HT se concentraba alrededor del valor medio, en la MCH coexistían segmentos con contracción normal y segmentos con una deformación nula o significativamente reducida, con lo que se producía una mayor heterogeneidad de los valores de strain. Se observaron también algunos segmentos sin deformación incluso en ausencia de fibrosis o hipertrofia. Conclusiones. La distribución de strain caracteriza los patrones específicos de deformación miocárdica en pacientes con diferentes etiologías de la HVI. Los pacientes con MCH presentaron un valor medio de strain significativamente inferior, así como una mayor heterogeneidad de strain (en comparación con los controles, los atletas y los pacientes con HVI-HT), y tenían regiones sin deformación.

Mechanisms of Symptomatic Spinal Cord Ischemia After TEVAR: Insights From the European Registry of Endovascular Aortic Repair Complications (EuREC).

Abstract Purpose: To test the hypothesis that simultaneous closure of at least 2 independent vascular territories supplying the spinal cord and/or prolonged hypotension may be associated with symptomatic spinal cord ischemia (SCI) after thoracic endovascular aortic repair (TEVAR). Methods: A pattern matching algorithm was used to develop a risk model for symptomatic SCI using a prospective 63-patient single-center cohort to test the positive predictive value (PPV) of prolonged intraoperative hypotension and/or simultaneous closure of at least 2 of 4 the vascular territories supplying the spinal cord (left subclavian, intercostal, lumbar, and hypogastric arteries). This risk model was then applied to data extracted from the multicenter European Registry on Endovascular Aortic Repair Complications (EuREC). Between 2002 and 2010, the 19 centers participating in EuREC reported 38 (1.7%) cases of symptomatic spinal cord ischemia among the 2235 patients in the database. Results: In the single-center cohort, direct correlations were seen between the occurrence of symptomatic SCI and both prolonged intraoperative hypotension (PPV 1.00, 95% CI 0.22 to 1.00, p = 0.04) and simultaneous closure of at least 2 independent spinal cord vascular territories (PPV 0.67, 95% CI 0.24 to 0.91, p = 0.005). Previous closure of a single vascular territory was not associated with an increased risk of symptomatic spinal cord ischemia (PPV 0.07, 95% CI 0.01 to 0.16, p = 0.56). The combination of prolonged hypotension and simultaneous closure of at least 2 territories exhibited the strongest association (PPV 0.75, 95% CI 0.38 to 0.75, p<0.0001). Applying the model to the entire EuREC cohort found an almost perfect agreement between the predicted and observed risk factors (kappa 0.77, 95% CI 0.65 to 0.90). Conclusion: Extensive coverage of intercostal arteries alone by a thoracic stent-graft is not associated with symptomatic SCI; however, simultaneous closure of at least 2 vascular territories supplying the spinal cord is highly relevant, especially in combination with prolonged intraoperative hypotension. As such, these results further emphasize the need to preserve the left subclavian artery during TEVAR.

How to measure cortical folding from MR images: a step-by-step tutorial to compute local gyrification index.

Cortical folding (gyrification) is determined during the first months of life, so that adverse events occurring during this period leave traces that will be identifiable at any age. As recently reviewed by Mangin and colleagues(2), several methods exist to quantify different characteristics of gyrification. For instance, sulcal morphometry can be used to measure shape descriptors such as the depth, length or indices of inter-hemispheric asymmetry(3). These geometrical properties have the advantage of being easy to interpret. However, sulcal morphometry tightly relies on the accurate identification of a given set of sulci and hence provides a fragmented description of gyrification. A more fine-grained quantification of gyrification can be achieved with curvature-based measurements, where smoothed absolute mean curvature is typically computed at thousands of points over the cortical surface(4). The curvature is however not straightforward to comprehend, as it remains unclear if there is any direct relationship between the curvedness and a biologically meaningful correlate such as cortical volume or surface. To address the diverse issues raised by the measurement of cortical folding, we previously developed an algorithm to quantify local gyrification with an exquisite spatial resolution and of simple interpretation. Our method is inspired of the Gyrification Index(5), a method originally used in comparative neuroanatomy to evaluate the cortical folding differences across species. In our implementation, which we name local Gyrification Index (lGI(1)), we measure the amount of cortex buried within the sulcal folds as compared with the amount of visible cortex in circular regions of interest. Given that the cortex grows primarily through radial expansion(6), our method was specifically designed to identify early defects of cortical development. In this article, we detail the computation of local Gyrification Index, which is now freely distributed as a part of the FreeSurfer Software (http://surfer.nmr.mgh.harvard.edu/, Martinos Center for Biomedical Imaging, Massachusetts General Hospital). FreeSurfer provides a set of automated reconstruction tools of the brain's cortical surface from structural MRI data. The cortical surface extracted in the native space of the images with sub-millimeter accuracy is then further used for the creation of an outer surface, which will serve as a basis for the lGI calculation. A circular region of interest is then delineated on the outer surface, and its corresponding region of interest on the cortical surface is identified using a matching algorithm as described in our validation study(1). This process is repeatedly iterated with largely overlapping regions of interest, resulting in cortical maps of gyrification for subsequent statistical comparisons (Fig. 1). Of note, another measurement of local gyrification with a similar inspiration was proposed by Toro and colleagues(7), where the folding index at each point is computed as the ratio of the cortical area contained in a sphere divided by the area of a disc with the same radius. The two implementations differ in that the one by Toro et al. is based on Euclidian distances and thus considers discontinuous patches of cortical area, whereas ours uses a strict geodesic algorithm and include only the continuous patch of cortical area opening at the brain surface in a circular region of interest.

New kernel functions and learning methods for text and data mining

Recent advances in machine learning methods enable increasingly the automatic construction of various types of computer assisted methods that have been difficult or laborious to program by human experts. The tasks for which this kind of tools are needed arise in many areas, here especially in the fields of bioinformatics and natural language processing. The machine learning methods may not work satisfactorily if they are not appropriately tailored to the task in question. However, their learning performance can often be improved by taking advantage of deeper insight of the application domain or the learning problem at hand. This thesis considers developing kernel-based learning algorithms incorporating this kind of prior knowledge of the task in question in an advantageous way. Moreover, computationally efficient algorithms for training the learning machines for specific tasks are presented. In the context of kernel-based learning methods, the incorporation of prior knowledge is often done by designing appropriate kernel functions. Another well-known way is to develop cost functions that fit to the task under consideration. For disambiguation tasks in natural language, we develop kernel functions that take account of the positional information and the mutual similarities of words. It is shown that the use of this information significantly improves the disambiguation performance of the learning machine. Further, we design a new cost function that is better suitable for the task of information retrieval and for more general ranking problems than the cost functions designed for regression and classification. We also consider other applications of the kernel-based learning algorithms such as text categorization, and pattern recognition in differential display. We develop computationally efficient algorithms for training the considered learning machines with the proposed kernel functions. We also design a fast cross-validation algorithm for regularized least-squares type of learning algorithm. Further, an efficient version of the regularized least-squares algorithm that can be used together with the new cost function for preference learning and ranking tasks is proposed. In summary, we demonstrate that the incorporation of prior knowledge is possible and beneficial, and novel advanced kernels and cost functions can be used in algorithms efficiently.

Statistiques appliquées en chirurgie cardiaque adulte : analyses de survie et applications du “propensity score”

L'objectif principal de ce travail est d’étudier en profondeur certaines techniques biostatistiques avancées en recherche évaluative en chirurgie cardiaque adulte. Les études ont été conçues pour intégrer les concepts d'analyse de survie, analyse de régression avec “propensity score”, et analyse de coûts. Le premier manuscrit évalue la survie après la réparation chirurgicale de la dissection aigüe de l’aorte ascendante. Les analyses statistiques utilisées comprennent : analyses de survie avec régression paramétrique des phases de risque et d'autres méthodes paramétriques (exponentielle, Weibull), semi-paramétriques (Cox) ou non-paramétriques (Kaplan-Meier) ; survie comparée à une cohorte appariée pour l’âge, le sexe et la race utilisant des tables de statistiques de survie gouvernementales ; modèles de régression avec “bootstrapping” et “multinomial logit model”. L'étude a démontrée que la survie s'est améliorée sur 25 ans en lien avec des changements dans les techniques chirurgicales et d’imagerie diagnostique. Le second manuscrit est axé sur les résultats des pontages coronariens isolés chez des patients ayant des antécédents d'intervention coronarienne percutanée. Les analyses statistiques utilisées comprennent : modèles de régression avec “propensity score” ; algorithme complexe d'appariement (1:3) ; analyses statistiques appropriées pour les groupes appariés (différences standardisées, “generalized estimating equations”, modèle de Cox stratifié). L'étude a démontrée que l’intervention coronarienne percutanée subie 14 jours ou plus avant la chirurgie de pontages coronariens n'est pas associée à des résultats négatifs à court ou long terme. Le troisième manuscrit évalue les conséquences financières et les changements démographiques survenant pour un centre hospitalier universitaire suite à la mise en place d'un programme de chirurgie cardiaque satellite. Les analyses statistiques utilisées comprennent : modèles de régression multivariée “two-way” ANOVA (logistique, linéaire ou ordinale) ; “propensity score” ; analyses de coûts avec modèles paramétriques Log-Normal. Des modèles d’analyse de « survie » ont également été explorés, utilisant les «coûts» au lieu du « temps » comme variable dépendante, et ont menés à des conclusions similaires. L'étude a démontrée que, après la mise en place du programme satellite, moins de patients de faible complexité étaient référés de la région du programme satellite au centre hospitalier universitaire, avec une augmentation de la charge de travail infirmier et des coûts.

Variabilité des souches de Escherichia coli provenant de divers poulaillers au Québec

La technique d’empreinte génétique par rep-PCR, qui utilise des séquences d’ADN répétitives, a été utilisée pour mettre en évidence la présence de groupes d’Escherichia coli signatures pour divers poulaillers et d’évaluer leur évolution suite au détassement. L’amorce (GTG)5 a été utilisée pour générer des empreintes d’ADN de 522 isolats provenant de 7 poulaillers échantillonnés deux fois : juste avant et 5 jours après le détassement. Les empreintes d’ADN ont été analysées selon l’algorithme de correspondance de bandes de Jaccard. Les analyses de Jackknife des coefficients de similitude ont révélé qu’entre 73% et 93% des isolats ont pu être correctement regroupés selon leur poulailler d’origine. Un dendrogramme construit à partir des coefficients de similitude de Jaccard a groupé les isolats dans 42 grappes avec près de la moitié dans une seule grappe. Environ 80% des isolats ont été groupés dans les 6 plus grosses grappes. Quatre de ces grappes été constituées majoritairement d’isolats provenant d’un seul site. Ces grappes pourraient être des grappes signatures qui permettraient d’identifier des poulaillers en particulier. La comparaison des nombres de grappes présentes avant et après le détassement a révélé une variabilité de l’impact du détassement sur les populations fécales d’E. coli. Pour certains sites, il y avait peu d’agrégats présents tant avant qu’après le détassement alors que pour d’autres sites c’était le contraire. Quoique plus de recherches soient nécessaires afin de valider les conclusions, nos résultats suggèrent la présence de sous-populations signatures d’E. coli pour certains poulaillers et une réponse variable à l’effet du détassement.

Effectiveness Of Feature Detection Operators On The Performance Of Iris Biometric Recognition System

Iris Recognition is a highly efficient biometric identification system with great possibilities for future in the security systems area.Its robustness and unobtrusiveness, as opposed tomost of the currently deployed systems, make it a good candidate to replace most of thesecurity systems around. By making use of the distinctiveness of iris patterns, iris recognition systems obtain a unique mapping for each person. Identification of this person is possible by applying appropriate matching algorithm.In this paper, Daugman’s Rubber Sheet model is employed for irisnormalization and unwrapping, descriptive statistical analysis of different feature detection operators is performed, features extracted is encoded using Haar wavelets and for classification hammingdistance as a matching algorithm is used. The system was tested on the UBIRIS database. The edge detection algorithm, Canny, is found to be the best one to extract most of the iris texture. The success rate of feature detection using canny is 81%, False Accept Rate is 9% and False Reject Rate is 10%.