Video over the web is gaining a lot of popularity nowadays. Video is used as an information sharing mechanism in a number of spheres like communication, entertainment, and education. Video essentially transfers the visual and auditory information captured by the camera from a scene to a viewer. When videos are rendered over web browsers many opportunities emerge to provide additional information channels over the video.The Reality over Web (RoW) is an attempt at loading the video with additional information. RoW overlays a two way channel on top of the video which can transfer information between viewers of the video and actors present in the video. Using this mechanism the viewers can influence the happenings in the video or obtain additional information that is not readily available in the video about the scene.This thesis work developed an architecture for RoW and implemented a proof-of-concept prototype of RoW. One particular problem that is central to RoW is locating the devices in a video frame. This requires a locationing scheme that is highly accurate and does not require any special hardware support on the device side. Because existing schemes did not fit the requirements of RoW, this thesis research developed a new locationing scheme based on the directionality of high frequency sound waves. Once the devices have been detected, they are addressed on the video. The video is made interactive in a way that user gestures on the addressed area on the video are converted into commands and sent to the corresponding device. The experiments carried out with the prototype in a laboratory setting and inside a sound isolation room indicate thatour locationing scheme is capable of reaching the high-level of accuracy required by RoW. / De nos jours, la vidéo sur Internet se popularise de plus en plus. La vidéo est utilisée comme un mécanisme de partage d'informations dans un grand nombre des domaines, tels que la communication, le divertissement ou l'éducation. La vidéo sert essentiellement à transférer d'une scène à un spectateur, l'information visuelle et audio capturée à l'aide d'une caméra. Quand les vidéos sont rendues sur les navigateurs Web de nombreuses possibilités émergent pour fournir des canaux d'information supplémentaires sur ces vidéos.La RoW (Reality over Web) est une tentative de charger une vidéo avec des informations additionnelles. La RoW ajoute un lien bidirectionnel au dessus de la vidéo qui permet le transfert de l'information entre les spectateurs et les acteurs présents dans la vidéo. Grâce à ce mécanisme, les spectateurs peuvent influencer les évènements de la vidéo ou obtenir de l'information additionnelle qui n'est pas facilement accessible à propos de la scène. Dans ce travail nous avons développé une architecture pour la RoW et avons mis au point un système prototype de RoW, qui met en évidence le concept de l'emprise. Un problème particulier qui est au cœur de l'emprise est de localiser les périphériques dans une image vidéo. Cela nécessite un système de positionnement (locationing) qui doit être très précis et qui ne nécessite aucun support matériel spécial sur le côté de l'appareil. Puisque les systèmes existants ne répondaient pas à ces exigences, ce travail apporte une contribution au développement d'un nouveau système de positionnement (locationing) basé sur la directivité des ondes sonores à haute fréquence.Une fois les appareils détectés, ils sont appliqués (adressés) sur la vidéo. La vidéo est alors rendue interactive d'une manière qui permet de convertir les mouvements gestuels de l'utilisateur sur cette partie spécifique de la vidéo en des commandes appropriées à l'appareil correspondant. Les expériences menées avec le prototype développé dans un environnement de laboratoire et à l'intérieur d'une chambre d'isolement sonore indiquent que notre système de positionnement (locationing) est capable d'atteindre le haut niveau de précision requise par la RoW.

Kademlia [16] is one of the most widely used DHTs (Distributed Hash Table) [10] in P2P (peer-to-peer) networks. In this work, we suggest and study a modification to the standard Kademlia network - hereby referred to as m-Kademlia. We study the connectivity of the random graph induced by m-Kademlia and then look at how long it takes to locate a node in this random graph. / Kademlia [16] est l'un des les plus utilisés DHTs (Distributed Hash Tableau) [10] dans les réseaux P2P (peer-to-peer). Dans ce travail, nous proposons et étudions une modification au réseau standard Kademlia - ci-après appelé m-Kademlia. Nous étudions la connectivité du graphe aléatoire induit par m-Kademlia et nous intéressons ensuite à connaître le temps nécessaire pour localiser un noeud donné de ce graphe aléatoire.

The rising cost of unplanned hospital readmissions has sparked calls for identifying medical system failures, best practices, and interventions in order to reduce the incidence of avoidable readmission. Readmissions currently account for 18% of total hospital admissions among Medicare patients in the United States. Distinguishing avoidable from unavoidable readmissions is a complex problem, but tackling it can shed light on readmission determinants and contributing factors. The objective of this thesis is to gain knowledge about the role that dispensed drugs, medical procedures, and diagnostic information play in predicting the chance of readmission within thirty days from a hospital discharge, using machine learning techniques. The prediction of hospital readmission is formulated as a supervised learning problem. Two supervised learning models, Naïve Bayes and Decision Tree, are used in the thesis to predict the chance of readmission based on patients' demographic information, prescription drugs, diagnosis and procedure codes extracted from hospital discharge summaries. The empirical analysis improves the understanding of hospital readmission prediction and identifies patient subpopulations for which the readmission prediction is naturally more difficult. Comparing the performance of different methods, using AUC as the measure of performance, we found that the combination of Naïve Bayes classifier and Gini Index feature selection performs slightly better than other methods on this dataset. We also found that some diagnostic features play an important role in distinguishing outliers. Removing outliers from the entire data results in significant performance gains in the prediction of readmission. / La hausse des côuts associés avec les re-admissions non-planifiées à l'hôpital suggère que c'est très important d'identifier les détérminants de ces événements. Les re-admissions causent 18% des côuts de Medicare aux États-Unis, ce qui fait l'identification des re-admissions qui peuvent être évitées très importante. Nous formulons ce problème comme une tâche d'apprentissage supervisé. Nous utilisons deus méthodes, Naive Bayes et les Arbres de Décision, pour la prédiction des patients qui vont être re-admis, en fonctions de leurs données démographiques, les médicaments de préscription, et les codes de diagnostique et des procédures que les patients ont subis en hôpital. Nôtre analyse ameliore nos connaissances sur les facteurs détérminants pour les re-admissions non-planifiées et identifie de sous-populations de patients pour lesquelles la prédiction est plus difficile. Nous performons des comparaisons de différentes méthodes de prédiction. La combinaison de Naïve Bayes et séléction d'attributes basée sur l'index Gini donne les meilleurs résultats sur nos données. Nous avons aussi trouvé que certains attributs sont utiles pour distinguer les patients pour lesquels la prédiction est difficile. Si on élimine ces patients du jeu de données, les résultats de l'aprentissage sont meilleurs. La hausse des côuts associés avec les re-admissions non-planifiées à l'hôpital suggère que c'est très important d'identifier les détérminants de ces événements. Les re-admissions causent 18% des côuts de Medicare aux États-Unis, ce qui fait l'identification des re-admissions qui peuvent être évitées très importante. Nous formulons ce problème comme une tâche d'apprentissage supervisé. Nous utilisons deus méthodes, Naive Bayes et les Arbres de Décision, pour la prédiction des patients qui vont être re-admis, en fonctions de leurs données démographiques, les médicaments de préscription, et les codes de diagnostique et des procédures que les patients ont subis en hôpital. Nôtre analyse ameliore nos connaissances sur les facteurs détérminants pour les re-admissions non-planifiées et identifie de sous-populations de patients pour lesquelles la prédiction est plus difficile. Nous performons des comparaisons de différentes méthodes de prédiction. La combinaison de Naïve Bayes et séléction d'attributes basée sur l'index Gini donne les meilleurs résultats sur nos données. Nous avons aussi trouvé que certains attributs sont utiles pour distinguer les patients pour lesquels la prédiction est difficile. Si on élimine ces patients du jeu de données, les résultats de l'aprentissage sont meilleurs.

Positron emission tomography (PET) imaging is becoming increasingly popular for understanding brain function. This thesis addresses two problems related to PET images: binding potential (BP) computation and pairwise PET image registration. We first investigate the influence of several computational choices on the calculation of binding potential maps in brain PET. Our work uses simulated data and allows us to provide some benchmarks for the choices to make for BP computation, which is an important step towards fully automated MR independent BP estimation. We then introduce a new method for pairwise dynamic PET image registration that is derived from the 3D diffeomorphic log-demons algorithm, and demonstrate an improvement over existing methods. We also present a high-resolution [11C]raclopride PET template built from 35 subjects scanned on the High Resolution Research Tomograph. As this is the highest resolution PET scanner available at the time, to the best of our knowledge, this template is the best quality representation of a PET [11C]raclopride image produced to date. / L'imagerie à émission de positrons est de plus en plus utilisée pour comprendre le fonctionnement du cerveau. Ce mémoire aborde deux sujets liés àces images: le calcul du potentiel de liaison et l'alignement de deux images. Nous étudions tout d'abord l'influence de certains choix d'implémentation sur les estimations de potentiel de liaison. Ces travaux effectués sur des données simulées nous permettent de donner des points de repère concernant les choix à faire pour calculer le potentiel de liaison, ce qui constitue un pas important vers un calcul du potentiel de liaison entièrement automatisé etindépendant d'images à résonance magnétique. Nous introduisons ensuite une nouvelle méthode pour l'alignement de deux images de tomographie à émission de positrons. Cette méthode est adaptée de l'algorithme des log-démons difféomorphiques 3D. Nous montrons que notre méthode donne de meilleurs résultats que des méthodes existantes. Nous présentons aussi un modèle de haute résolution pour l'imagerie à émissionde positrons utilisant la [11C]raclopride. Ce modèle est construit à partir de 35sujets scannés sur le tomographe de recherche à haute résolution (High Resolution Research Tomograph). Comme il s'agit du tomographe de plus haute résolution disponible à ce jour, à notre connaissance, notre modèle est l'image de raclopride de plus haute résolution jamais produite.

Using procedural narrative generation in video games provides a flexible way to extend gameplay and provide more depth to the game world at low cost to the developers. Current examples of narrative generation in commercial games, however, tend to be simplistic, resulting in repetitive and uninteresting stories. We approach these challenges and develop a system for narrative generation that uses a context-aware graph rewriting framework. We use a graph representation of the game world to create narratives which reflect and modify the current world state. These narratives are all validated to ensure that they are completable and we design a novel set of metrics which provide an approximation of narrative quality by analyzing the structure of the narratives generated. We apply these metrics throughout the generation process to ensure a certain level of quality. These metrics are then used to examine the relations between the scale of the game world with the quality of narratives generation. Additionally, we validate our graph-rewriting approach by comparing our generated narratives to other procedurally generated stories, as well as to authored narratives from commercially successful and critically praised games. The results show that our narratives compare favourably to the authored narratives. Our metrics provide a new approach to narrative analysis, and our system provides a unique and practical approach to story generation. / La génération procédurale d'histoire dans les jeux vidéo commerciaux permettre d'étendre le « gameplay » et d'approfondir l'univers du jeu à bas coup. Les jeux commerciaux qui utilisent ce genre de technologie le font de manière simpliste dont le résultat est souvent répétitif et ennuyeux. Nous avons développé un système qui crée des histoires procéduralement, ce système utilise une représentation de l'univers graphique (graphe) et réécrit cette structure afin de la faire évoluer. Cette représentation permet à notre système de comprendre l'univers, d'y modifier ce dernier et du fait créer des histoires qui respectent l'univers. Les histoires générées par le système sont validées afin d'assurer qu'elles sont logiques. De plus, nous avons défini des procédures innovatrices afin de mesurer la qualité des histoires générées. Ceci est accompli par l'entremise d'analyse de graphe. Ces procédures sont utilisées afin d'assurer une qualité minimale lors de la génération d'histoires. Par la suite, nous examinons les relations entre les histoires générées et la grandeur de l'univers ludique. Afin de valider notre approche, nous avons comparé nos histoires procédurales à d'autres systèmes procéduraux et d'histoires de jeux vidéo générées par la plume d'auteur. Nos résultats montrent que notre système se compare favorablement avec les histoires venant d'auteur humain. En sommes, notre approche permet d'analyser et mesurer des histoires en plus d'offrir une approche pratique et fonctionnelle à la génération procédurale d'histoire.

Transcription factor binding sites are essential components of the machinery that controls gene expression. In the absence of experimental data, computational approaches are used to predict binding sites based on promoter DNA sequence. However transcription factor binding depends not just on sequence but also the packaging of the DNA molecule. Nucleosomes, as the smallest unit of DNA packaging, affect transcription factor binding by obstructing protein-DNA interactions. / We use an empirically-derived relationship between binding sites and nucleosome positioning to augment an existing computational approach to predicting transcription factor binding sites. We demonstrate that the inclusion of experimentally-derived nucleosome positioning data improves the prediction capabilities of the basic computational approach using a large dataset of experimentally confirmed transcription factor binding sites. / Les sites de liaison de facteurs de transcription sont des composants essentiels du méchanisme de contrôle de l'expression génique. En l'absence de données expérimentales, les approches informatiques sont utilisées pour prédire les sites de liaison basée sur la séquence d'ADN promoteur. Toutefois la liaison de facteurs de transcription dépend non seulement de la séquence mais également de l'emballage biologique de la molécule d'ADN. Les nucléosomes, en tant qu'unité d'emballage de base de l'ADN, ont un effet marqué sur le positionnement des sites de liaison de facteurs de transcription. / Nous dérivons une relation empirique entre les sites de liaison et le positionnement des nucléosomes pour améliorer un algorithme de prédiction de sites de liaison. Nous démontrons que l'inclusion de données de positionnement de nucléosome améliore la performance de l'algorithme de base en utilisant un ensemble de données de sites de liaison confirmé expérimentalement.

Designers of software components can use finite-state properties to denote behavioral interface specifications which enforce client-side programming rules that state how the components ought to be used. This allows users of these components to check their client code for compliance with these rules, both statically and at runtime. / In this dissertation we explain the design and implementation of Clara, a framework for specifying and verifying finite-state properties of large-scale programs. With Clara, programmers specify finite-state properties together with runtime monitors, using a syntactic extension to the aspect-oriented programming language AspectJ. Clara then uses a sequence of three increasingly detailed static analyses to determine if the program satisfies the finite-state properties, i.e., is free of property violations. / Clara produces a list of program points at which the program may violate the properties, ranked by a confidence value. If violations are possible, Clara also instruments the program with the supplied runtime monitor, which will capture property violations when the program executes. Due to its static analyses, Clara can omit the instrumentation at program locations which the analyses proved safe, and so optimize the instrumented program. When much instrumentation remains, Clara partitions the instrumentation into subsets, so that one can distribute multiple partially instrumented program versions that each run with a low overhead. / We validated the approach by applying Clara to finite-state properties denoted in multiple formalisms over several large-scale Java programs. Clara proved that most of the programs fulfill our example properties. For most other programs, Clara could remove the monitoring overhead to below 10%. We also found multiple property violations by manually inspecting the top entries in Clara's ranked result list. / Les concepteurs des différentes composantes logicielles peuvent utiliser les propriétés des automates finis pour fixer les spécifications de l'interface comportementale qui contrôleront les règles de programmations définissant l'utilisation des composantes. Ceci permet aux utilisateurs de ces composantes de vérifier le respect de ses règles par leurs codes sources, à la fois lors d'une analyse statique qu'à l'exécution. / Dans cette dissertation, nous montrerons la conception de Clara, une structure qui permet de spécifier et de vérifier les propriétés des automates finis dans des programmes étendus, puis expliquerons son implantation. Le programmeur, à l'aide de Clara, peut définir les propriétés des automates finis en complément aux processus de vérification à l'exécution, en utilisant une extension de la syntaxe d'AspectJ, un langage de programmation orienté aspect. Clara utilise alors, en séquence, trois analyses statiques de précision croissante pour déterminer si le programme respecte les propriétés des automates finis. / Clara produit une liste des positions dans le code source où il y a risque de violation de ces «propriétés», en ordre décroissant de certitude d'une violation. Quand cela est possible, Clara ajoute au programme des processus de vérification permettant d'étudier la violation de «propriétés» lors de son exécution. Grâce à son analyse statique, Clara n'ajoute pas au code ces processus dans les portions de code qui n'ont pas la possibilité de violer les propriétés des automates finis, ce qui limite les ralentissements dus aux processus de vérification. Lorsque ses ajouts restent considérables, Clara organise les processus de vérification à l'exécution en sous-groupe, de sorte qu'il soit possible de distribuer différentes versions du programme contenant seulement une partie de ceux-ci, limitant ainsi l'utilisation des ressources système à l'exécution. / Nous avons validé cette approche en soumettant à Clara les propriétés des automates finis sous différents modèles à appliquer sur différents programmes Java. Clara a permis de prouver que la plupart de ces programmes respectaient déjà les propriétés définies. Dans les autres cas, Clara a pu réduire le coût des processus de vérification à moins de 10%. De plus, nous avons pu localiser de nombreuses violations de propriété manuellement, en inspectant les entrées en importance dans la liste produite par Clara.

The high-level array programming language MATLAB is widely used for prototyping algorithms and applications of scientific computations. However, its dynamically-typed nature, which means that MATLAB programs are usually executed via an interpreter, leads to poor performance. An alternative approach would be converting MATLAB programs to equivalent Fortran 95 programs. The resulting programs could be compiled using existing high-performance Fortran compilers and thus could provide better performance. This thesis presents techniques that are developed for our MATLAB-to-Fortran compiler, McFor, for extracting information from the high-level semantics of MATLAB programs to produce efficient and reusable Fortran code. / The McFor compiler includes new type inference techniques for inferring intrinsic type and shape of variables and uses a value-propagation analysis to precisely estimate the sizes of arrays and to eliminate unnecessary array bounds checks and dynamic reallocations. In addition to the techniques for reducing execution overhead, McFor also aims to produce programmer-friendly Fortran code. By utilizing Fortran 95 features, the compiler generates Fortran code that keeps the original program structure and preserves the same function declarations. / We implemented the McFor system and experimented with a set of benchmarks with different kinds of computations. The results show that the compiled Fortran programs perform better than corresponding MATLAB executions, with speedups ranging from 1.16 to 102, depending on the characteristics of the program. / Le langage de programmation de tableaux de haut niveau MATLAB est largement utilisé afin de faire du prototypage d'algorithmes et des applications de calculs scientifiques. Cependant, sa nature de type dynamique, ce qui veut dire que les programmes MATLAB sont habituellement exécutés par un interpréteur, amène une mauvaise performance. Une approche alternative serait de convertir les programmes MATLAB aux programmes Fortran 95 équivalents. Les programmes résultants pourraient être compilés en utilisant les compilateurs de haute performance Fortran, ainsi ils peuvent fournir une meilleure performance. Cette thèse présente les techniques qui sont développées pour notre compilateur MATLAB-à-Fortran, McFor, pour extraire l'information des hauts niveaux des sémantiques des programmes MATLAB afin de produire un code Fortran efficace et réutilisable. / Le compilateur McFor inclut de nouvelles techniques de déduction pour inférer les types et formes intrinsèques des variables et utilise une analyse à propagation de valeurs pour estimer avec précision la tailles des tableaux de variables et pour éliminer les vérifications des limites et les réallocations dynamiques superflues de ces tableaux. En plus de ces techniques de réduction des temps d'exécution, McFor vise aussi a génèrer du code Fortran convivial pour les développeurs. En utilisant les avantages de Fortran 95, le compilateur génère du code Fortran qui préserve la structure originale du programme ainsi que les mêmes déclarations de fonctions. / Nous avons mis en oeuvre le système McFor et l'avons expérimenté avec un ensemble de tests de performance avec différentes sortes de calculs. Les résultats montrent que les programmes de Fortran compilés offrent une meilleure performance que les exécutions MATLAB correspondantes, avec une cadence accélérée de l'ordre de 1.16 à 102, selon les caractéristiques du programme.

In recent years, dependent type systems have gathered interest because they make it possible to express stronger properties about programs. However, they are also very verbose. In this thesis, we show how to eliminate some of this verbosity (for the user) by doing reconstruction over dependent types. More precisely, we present the work done in the implementation of the Beluga programming language. Our goal is to present the key issues arising in reconstruction and give a formal and accessible description of ideas that have been around for some time but never given the spotlight. We also prove the soundness of our reconstruction algorithm. / Au cours des dernières années, les types dépendants ont reçu un intérêt particulier parce qu'ils permettent d'exprimer des propriétés plus précises sur les programmes. Cependant, ces systèmes de typage sont aussi très redondants. Dans cette thèse, nous allons expliquer comment éliminer une partie de cette redondance en reconstruisant ces types dépendants. Plus précisément, nous présenterons le travail fait sur l'implémentation du langage Beluga. Notre but est de présenter les problématiques importantes liées à la reconstruction de types dépendants et de présenter de façon formelle et accessible certaines idées qui, malgré le fait qu'elle ne sont pas toutes récentes, sont toujours restées dans l'ombre jusqu'à maintenant. Une preuve de correction de notre algorithme de reconstruction est aussi donnée.

There has been relatively little work done in the compiler research community for incorporating aspect-oriented features in scientific and dynamic programming languages. / MATLAB is a dynamic scientific programming language that is commonly used by scientists because of its convenient and high-level syntax for arrays, the fact that type declarations are not required, and the availability of a rich set of application libraries. This thesis introduces a new aspect-oriented scientific language, AspectMatlab. / AspectMatlab introduces key aspect-oriented features in a way that is both accessible to scientists and where the aspect-oriented features concentrate on array accesses and loops, the core computation elements in scientific programs. One of the main contributions of this thesis is to provide a compiler implementation of the AspectMatlab language. It is supported by a collection of scientific use cases, which portray the potential of the aspectorientation for scientific problems. / Introducing aspects into a dynamic language such as MATLAB also provides some new challenges. In particular, it is difficult to statically determine precisely where patterns match, resulting in many dynamic checks in the woven code. The AspectMatlab compiler uses flow analyses to eliminate many of those dynamic checks. / This thesis reports on the language design of AspectMatlab, the amc compiler implementation, and also provides an overview of the use cases that are specific to scientific programming. By providing clear extensions to an already popular language, AspectMatlab will make aspect-oriented programming accessible to a new group of programmers including scientists and engineers. / Relativement peu de travail a été accomplis dans le milieu de la recherche du compilateur pour l'intégration des caractéristiques orientées à l'aspect dans les domaines scientifique et dynamique des langages de programmation. Matlab est un langage de programmation scientifique dynamique qui est couramment utilisé par les scientifiques en raison de sa pratique et la syntaxe de qualité pour des tableaux ; du fait que les déclarations de type ne sont pas nécessaires, et de la disponibilité de vastes bibliothèques d'applications. Cette thèse introduit un nouvel aspect de langue de recherche scientifique : AspectMatlab. / AspectMatlab introduit fonctionnalités d'aspect orientées d'une manière qui est à la fois accessible aux scientifiques et où les fonctionnalités d'aspect orientées se concentrent sur les accès réseau et des boucles, les éléments de calcul de base dans les programmes scientifiques. L'une des principales contributions de cette thèse est de fournir une implémentation du compilateur du langage AspectMatlab. Il est soutenu d'une collection de cas d'utilisation scientifique, qui montre le potentiel de l'orientation aspect pour des problèmes scientifiques. / L'introduction des aspects dans un langage dynamique comme Matlab représente aussi quelques nouveaux défis. En particulier, il est difficile de déterminer statiquement où les modèles coïncident, résultant dans de nombreux contrôles dynamiques dans le code tissé. Le compilateur d'AspectMatlab utilise le flux d'analyses pour éliminer un grand nombre de ces contrôles dynamiques. / Cette thèse signale la conception du language d'AspectMatlab et l'implementation du compilateur amc. Elle fournit également un aperçu de l'utilisation des cas qui sont spécifiques à la programmation scientifique. En fournissant des extensions claires avec un langage déjà populaire, AspectMatlab rendra la programmation orientée à l'aspect accessible à un nouveau groupe de programmeurs y compris des scientifiques et des ingénieurs.