In this thesis we detail the development of a software framework for networked augmented reality applications. We discuss vision-based tracking of planar surfaces, sensor fusion based pose estimation, and the overall implementation of our system. The primary focus of this thesis is our sensor fusion based tracking approach, which uses a novel extended Kalman filter formulation that takes advantage of the group structure of rotations. We provide an extensive derivation of this formulation, and validate the approach using both simulation and ground truth data obtained via a motion capture system. / Dans cette thèse, nous détaillons le développement d'une architecture logicielle dédiée à réalité augmentée en réseau. Nous explorons plusieurs procédés de la vision numérique tels que la détection et suivi de surfaces planes et la localisation spatiale à partir de plusieurs capteurs et discutons de la conception de notre système. Cette thèse se concentre principalement sur la combination d'information sensorielle provenant de plusieurs sources. Notre technique utilise une nouvelle extension du filtre de Kalman qui exploite la structure des rotations. Nous offrons une dérivation extensive de cette formulation et nous validons cette approche d'une part par des données simulées mais aussi par des données réelles obtenues par un système de capture de mouvement.

The concept of evolving components of an artificial intelligence (AI) has seen increased interest in recent years as the power and complexity of AI has grown. In entertainment software, this AI can impact the player's experiences and enjoyment through elements such as the level of difficulty of the player's competition. Therefore AI development is an important research topic, especially as development is considered difficult by the video game industry. This work applies the evolutionary computing paradigm to a turn-based domain by evolving team strategies. These strategies are represented as behaviour trees, a formalism found in the video game industry and well-suited to the evolutionary algorithm due to their flexibility and tree structure. During the evolutionary process, strategies are evaluated in Battle for Wesnoth, an open-source game with a stochastic nature. A fitness function is defined to assign strategies a numerical strength value, along with a second performance metric that is robust to the variance found in the domain. The evolutionary algorithm then recombines strategies with high strength values, using evolutionary operators from the literature such as crossover and mutation. Later experiments focus on evolutionary algorithm parameters, including comparing a variety of fitness functions to provide insights into their use. Starting from a number of initial states, numerous strategies are evolved using this algorithm. These initial states are a null strategy, randomly-generated strategies, and a number of hand-built strategies. The evolved strategies are then evaluated in-game, and will be shown to be measurably stronger than the initial strategies. / L'application de l'informatique évolutive au domaine de l'Intelligence Artificielle (IA) émerge naturellement. Pour l'industrie du divertissement (jeux ludiques), IA fait référence aux différents éléments visuels ou non qui déterminent une partie importante de l'expérience du joueur. Cette responsabilité fait en sorte que développer des système d'IA n'est pas une tâche simple, ce qui en fait un domaine de recherche intéressant. Ce travail applique les concepts d'informatique évolutive a un jeu par tour en lassant évoluer des stratégies d'IA. Les stratégies sont représentées par des arbres de comportement. Nous retrouvons cet automate dans l'industrie des jeux digitales, en général il est flexibles et bien adapté a l'informatique évolutive. Durant le processus d'évolution les stratégies sont évaluées dans le jeu Battle for Wesnoth, un jeu logiciel libre de nature stochastique. Une fonction d'aptitude est assignée aux stratégies afin de déterminer numériquement leur efficacité, de plus l'algorithme utilise des mesures robuste à la variance du processus. L'algorithme d'évolution recombine les stratégies efficaces utilisant des opérateurs évolutionnaires basés sur littérature par exemple, mutation ou transition. De plus amples expériences se concentrent sur différents paramètres et leurs utilités, par exemple les fonctions d'aptitudes. L'algorithme utilise de multiples états initiales : stratégie nulle, stratégie issue du hasard et stratégies de conception humaine. Les stratégies sont ensuite testées dans le jeu. Il est démontré par la suite que les stratégies évoluées par l'algorithme sont plus efficace que leurs états initiaux.

Security and privacy of photos stored in the clear in third party servers has been the biggest concern for customers in recent years. One way of enhancing the privacy and security of photos stored in third party servers is to encrypt the photos before storing them. However, using encryption to secure the information held in the photos precludes applying any image processing operations while they are held in the third party servers. To address this issue, we have designed and implemented a distributed image storage system that is based on the Chord protocol which enhances privacy using chaotic map transformations and image segmentation. The distributed system we use has two types of resources: trusted server resources and untrusted peer-to-peer resources. The images are encrypted using an Arnold's cat map algorithm and split into strips before uploaded to the destination machines. The cat map algorithm shuffles an image pixels and produces a noise-like image. A pixelated (a group of nearby pixels are made the same color) image of the original image is generated to represent it in the central server. From the pixelated image we generate the key parameters that control the cat map transformations. A variety of pixel-level, block-level and binary filters have been implemented to support image processing on encrypted images in the system. One of the concerns of using cat maps for security purposes is the quality of shuffling provided by these transformations. For certain parameter values and image sizes cat map transformations reveal the original image as ghosts or clusters. As part of my thesis, I studied the ghost and cluster formation scenarios. I performed many experiments and proposed simple tests that can be used to detect the parameter values that should be avoided. / La sécurité et l'intimité des images électronique stockée dans des serveurs tierces est une des plus grandes préoccupations de nos jours. L'une des manières d'améliorée la sécurité est de crypter les données contenu dans les images avant de les télécharger vers le serveur en question. Cependant, le fait d'utiliser des techniques cryptographiques pour assurer la sécurité des images, ce la empêche l'application d'opérations de traitement d'images pendant qu'ils résident sur les serveurs. Pour résoudre ce problème, nous avons conçu et mis en œuvre un système distribué pour télécharger les images sur les serveurs qui est basée sur le protocole "Chord", améliorant la sécurité en utilisant des techniques de la théorie du chaos pour transformer l'image puis finalement la segmenter. Le système distribué que nous utilisons contient deux types de ressources : des ressources de serveur fiable et des ressources non fiables paires à pair. Les images sont cryptées avec l'application de l'algorithme chat d'Arnold, l'image résultante est divisée en morceaux avant d'être télécharger aux machines destinataires. L'algorithme de chat d'Arnold produit une image bruyante. Une image pixélisé (un groupe de pixels voisines sont changer de façon que les couleurs soient les même entre eux) est aussi créé de l'image originale. L'image pixélisée est utilisé pour représenter l'image originale sur le serveur central. A partir de l'image pixélisée, nous créerons les paramètres de la clé qui contrôlent la transformation chaotique. Une variété de filtres au niveau des pixels, blocs des pixels et de la représentation binaire ont été mis en œuvre pour permettre des opérations de traitement sur les images cryptées dans le système. La qualité du brouillement en utilisant les transformations chaotiques est un souci par rapport à la sécurité. Pour certaines valeurs de paramètres et dimensions d'images, on peut percevoir des fantômes de l'image originale. Pour ma thèse de maitrise, J'ai étudié les scenarios qui donnent naissance à des formations de fantômes. J'ai effectué de nombreuses méthodes expérimentales et proposer des simples testes pour pouvoir détecter les valeurs de paramètres qui doivent être évité.

The success of P2P file sharing applications prompted new efforts to explore the applicability of using P2P overlays in other applications, for example, to build computing clusters. These new genres of P2P applications necessitate mechanisms for discovering resources (not contents) in P2P systems. Existing solutions address this issue by converting the resource descriptions into contents and then use content discovery overlays to store and retrieve these descriptions. They use structured P2P overlays that provides the best search efficiency for content discovery. Even though this approach works well, it suffers from a number of drawbacks. For example, structured overlays are designed for discovering specific contents and querying to find a range of content makes the system inefficient. Unfortunately, it is highly likely for resources queries to include range specification like "memory ≥ 3GB." Further, these research efforts discover resources based on their attributes, but neglect connectivity metrics, latency and bandwidth. These issues warrant another look at resource discovery in distributed systems. I introduce a new resource discovery scheme called resource addressable network (RAN) to address these issues. The inability to support range queries in structured overlays is a result from assigning the nodes with random node IDs. The mechanisms introduced in this thesis produce non-random node IDs such that, while they provide a structured search space, they also retain the characteristics of the unstructured metric space where the resources are naturally located, for example, the attribute–value space; the proximity between two resources in terms of their attributes is reflected also in their node IDs. Producing such a mapping from a unstructured metric space to a structured search space and designing supporting architecture is the key contribution of this thesis. RAN is multi-tier discovery substr / Le succès des applications de partage de fichier P2P a suscité de nouveaux efforts dans l'exploration de l'utilisation des réseaux logiques P2P dans d'autres applications, telle que la construction des grilles de calcul. Ce nouveau genre d'applications P2P nécessitent des mécanismes de découverte de ressources (et non du contenu) dans les systèmes P2P. Les solutions existantes convertissent la description des ressources en contenu et utilisent les réseaux logiques de découverte pour stocker et rechercher ces descriptions. Elles exploitent ainsi les réseaux logiques structurés P2P qui permettent d'obtenir les meilleurs résultats de recherche en terme de contenu. Bien que cette approche fonctionne correctement, elle souffre d'un certain nombre de defauts. Par exemple, les réseaux logiques structurés sont conçus pour découvrir des contenus spécifiques et une requête par plage de contenu rend le système inefficace. Malheureusement, il est très commun d'inclure dans les requêtes de ressources des plages de spécification telle que "3 Go de mémoire." En outre, ces efforts de recherche découvrent des ressources fondées sur leurs attributs, mais négligent les paramètres de connectivité, de latence et de bande passante. Ces questions justifient un autre regard sur la découverte de ressources dans les systèmes distribués.Je présente un nouveau système de découverte de ressource appelé Réseau Adressable de Ressources / Resource Addressable Network (RAN) afin de répondre à ces questions. L'incapacité de supporter les requêtes par plage dans les réseaux logiques est dûe à l'assignation aléatoire d'identifiant pour les noeuds. Les mécanismes introduits dans cette thèse fournissent des identifiants non aléatoires de noeuds : en plus de l'espace de recherche structuré, ils mémorisent les caractéristiques de connectivité de l'espace non structuré sous-jacent où les r

In this thesis, we present a new model for higher-order quantum programming languages. The proposed model is an adaptation of the probabilistic game semantics developed by Danos and Harmer: we expand it with quantum strategies which enable one to represent quantum states and quantum operations. Some of the basic properties of these strategies are established and then used to construct denotational semantics for three quantum programming languages. The first of these languages is a formalisation of the measurement calculus proposed by Danos et al. The other two are new: they are higher-order quantum programming languages. Previous attempts to define a denotational semantics for higher-order quantum programming languages have failed. We identify some of the key reasons for this and base the design of our higher-order languages on these observations. The game semantics proposed in this thesis is the first denotational semantics for a lambda-calculus equipped with quantum types and with extra operations which allow one to program quantum algorithms. The results presented validate the two different approaches used in the design of these two new higher-order languages: a first one where quantum states are used through references and a second one where they are introduced as constants in the language. The quantum strategies presented in this thesis allow one to understand the constraints that must be imposed on quantum type systems with higher-order types. The most significant constraint is the fact that abstraction over part of the tensor product of many unknown quantum states must not be allowed. Quantum strategies are a new mathematical model which describes the interaction between classical and quantum data using system-environment dialogues. The interactions between the different parts of a quantum system are described using the rich structure generated by composition of strategies. This approach has enough generality to be put in relation with other work in qu / Nous présentons dans cette thèse un nouveau modèlepour les langages de programmation quantique. Notre modèle est uneadaptation de la sémantique de jeux probabilistes définie par Danos etHarmer: nous y ajoutons des stratégies quantiquespour permettre la représentation des états et des opérations quantiques.Nous établissons quelques propriétés de base de ces stratégies. Cespropriétés sont ensuite utilisées pour construire des sémantiquesdénotationnelles pour trois langages de programmation quantique. Le premierlangage est une formalisation du calcul par mesures proposé par Danoset al. Les deux autres langages sont nouveaux: ce sont deslangages quantiques d'ordre supérieur dont la syntaxe a été construiteà partir d'observations expliquant l'échec des tentatives précédentespour construire une sémantique dénotationnelle pour de tels langages. La sémantique de jeux présentée dans cette thèseest la première sémantique dénota­tionnelle pour de telslambda-calculs équipés de types et d'opérations supplémentairespermettant la programmation d'algorithmes quantiques. Les résultatsprésentés valident les deux approches différentes utilitées dans laconception de ces deux nouveaux languages d'ordre supérieur: une premièreoù les états quantiques sont indirectement accessibles via desréférences et une seconde où ils sont introduit directement comme desconstantes dans le langage. Les stratégies quantiques présentéespermettent de comprendre les contraintes devant êtreimposées aux systèmes de type quantique comportant des types d'ordresupérieurs. La contrainte la plus importante est le fait que l'abstractionsur une partie d'un état quantique comportant plusieurs qbits inconnus doitêtre prohibée. Les stratégies quantiques constituent un nouveau modèle mathématique quidécrit l'interaction entre les données classiques et quantiques par desdialogues entre système et environnement. L'interaction entre les differentespar

Duality theory is an important topic within automata theory which leads to a tight relationship between automata and modal logics. These dualities are very much in the spirit of the classical Stone type dualities. In a recent paper by Hundt et al. this was explored in the context of probabilistic automata equipped with a notion of observations. The motivation there was to understand how to reason about systems with hidden state. It turned out to be problematic to formalise this properly in categorical terms and the intuitive notion of duality presented there did not seem to correspond well with what was expected. / We study this putative duality coalgebraically. Towards this, we review coalgebras and view automata as coalgebras for a functor. This provides a natural way to consider categories of automata. We give an alternative construction of the final Kripke automaton of Cordy, which allows us to make the connection to duality. We show that the duality construction of Hundt et al. is in fact a finality construction, and demonstrate an analogous correspondence in the probabilistic case. / La théorie de la dualité est un sujet important dans la théorie des automates qui mène à une étroite relation entre les automates et les logiques modales. Ces dualités sont tout à fait dans l'esprit des dualités classiques de type Stone. Dans un document récent de Hundt et al. cela a été étudié dans le cadre des automates probabilistes équipés d'une notion d'observation. Leur motivation a été de comprendre comment raisonner sur les systèmes avec des états cachés. Il s'est avéré difficile de formaliser cela correctement en utilisant la théorie des catégories, et la notion intuitive de la dualité qui a été présenté ne semblent pas bien correspondre à ce qui était attendu. / Nous étudions cette dualité coalgébriquement. à cette fin, nous passons en revue les coalgèbres et nous regardons les automates comme coalgèbres pour un foncteur. Cela fournit un moyen naturel de considérer les catégories d'automates. Nous donnons une construction alternative de l'automate Kripke final de Cordy, qui nous permet de faire la connexion à la dualité. Nous montrons que la construction de la dualité de Hundt et al. est en fait une construction de finalité, et démontrons une correspondance analogue dans la cas probabiliste.

Semantic background knowledge is crucial for many intelligent applications. A classical way to represent such knowledge is through semantic networks. Wikipedia's hyperlink graph can be considered a primitive semantic network, since the links it contains usually correspond to semantic relationships between the articles they connect. However, Wikipedia is rather noisy in this function. We propose Wikispeedia, an online human-computation game that can effectively filter this noise, furnishing data that can be leveraged to define a robust measure of semantic relatedness between concepts. While the resulting measure is very precise, it has the limitation of being sparse, i.e., undefined for many pairs of concepts. Therefore, we develop algorithms based on principal component analysis to increase coverage to the set of all pairs of Wikipedia concepts. These methods can also be generalized to other sparse measures of semantic relatedness, which we demonstrate by applying our approach to the Wikipedia adjacency matrix. Building on the same techniques, we finally propose an algorithm for finding missing hyperlinks in Wikipedia, which results in increased human usability. / Des connaissances d'arrière-plan sémantiques sont essentielles pour de nombreuses applications intelligentes. Les réseaux sémantiques constituent une façon classique de représenter de telles connaissances. On peut comprendre le graphe défini par les hyperliens de Wikipédia comme un réseau sémantique primitif, car les liens qu'il contient correspondent habituellement à des relations sémantiques entre les articles qu'ils joignent. Cependant, si on considère Wikipédia comme un réseau sémantique, le niveau de bruit est relativement élevé. Nous proposons Wikispeedia, un jeu de calcul humain en ligne qui peut effectivement filtrer ce bruit, en fournissant des données que nous utilisons pour définir une mesure de proximité sémantique entre les concepts. Bien que la mesure qui s'ensuit soit très précise, elle est creuse, c'est-à-dire indéfinie sur de nombreuses paires de concepts. Pour couvrir l'ensemble de toutes les paires de concepts que contient Wikipédia, nous développons des algorithmes basés sur l'Analyse en composantes principales. Ces méthodes peuvent être généralisées aux autres mesures de proximité sémantique creuses, ce que nous démontrons en appliquant notre approche à la matrice d'adjacence de Wikipédia. Enfin, nous utilisons les mêmes techniques en proposant un algorithme qui est capable de trouver les liens manquants dans Wikipédia, donnant lieu à un système de meilleure convivialité. fr

Multiplayer, online computer games often distribute game-object state to client machines in order to improve game scalability and responsiveness. Network latency and jitter are concerns in this context, although the impact is reduced by the use of predictive techniques such as dead reckoning. These techniques, however, introduce consistency concerns for important and hard to predict behaviours, such as object collisions. In these cases a centralized authority or client/server architecture is typically used to ensure strong consistency, limiting game scalability. In this work we propose a motion-lock protocol for distributed game collision detection and resolution. The motion-lock protocol improves performance of motion prediction by giving stations time to communicate and agree on the detected collisions. This reduces the divergence of object states and post-collision trajectories. Offline and online simulation results show the motion-lock protocol is able to maintain strong consistency in collision count and reduces post-collision deviation with a small sacrifice of 3-4% in responsiveness of player controls. Qualitatively, the visual result of the collision response is greatly improved. With the motion-lock protocol, multiplayer online games can offload basic collision detection and resolution to game clients, increasing scalability without overly sacrificing consistency. / Multijoueurs, des jeux informatiques en ligne distribuent souvent tat du jeu-objet aux ordinateurs clients afin d'amliorer l'extensibilit de jeu et ractivit. Temps de latence et la gigue sont des proccupations dans ce contexte, bien que l'impact est rduit par l'utilisation de techniques de prdiction, comme dead reckoning. Ces techniques, toutefois, d'introduire des proccupations importantes pour la cohrence et difficile prdire les comportements, tels que les collisions d'objets. Dans ces cas, l'architecture d'une autorit centralise ou client/serveur est gnralement utilis pour assurer la cohrence forte, limiter l'volutivit jeu. Dans cette texte, nous proposons un protocole de motion-lock pour la dtection de collision jeu distribu et de la rsolution. Le motion-lock protocole amliore les performances de prdiction de mouvement en donnant stations temps de communiquer et de s'entendre sur les collisions dtectes. Cela rduit la divergence des tats de lobjet et trajectoires post-collision. Les rsultats de simulation en mode den ligne et hors ligne montrent le protocole motion-lock est en mesure de maintenir la cohrence forte du nombre de collisions et rduit l'cart aprs la collision avec un petit sacrifice de 3-4% de la ractivit des commandes du lecteur. Qualitativement, le rsultat visuel de la raction de collision est grandement amliore. Avec le protocole de motion-lock, les jeux multijoueurs en ligne peut dcharger la dtection de collision et la rsolution de base aux clients de jeu, ce qui augmente l'volutivit sans trop sacrifier la cohrence.

Social networks play an increasingly important role on the behavior of communication on the Internet. We present a general framework called socially governed networks that provides a network protection scheme at the level of social individual/social organization instead of the traditional level of physical address. The functionalities of socially governed networks are mainly composed of two parts: social accountability and social computation based security policy generation. For social accountability part, we design Gates (Personal Gate and Social Gate) binding users' actions on the Internet with users' social identities issued by given online social network (such as Facebook) instead of physical IP address, so that users are trackable throughout the Internet avoiding being impersonated. Gates are incrementally deployable without modifying the existing operating system running on the endpoints on the Internet and can be used to monitor, control, and report accountable communications betweenusers. For social computation based policy generation part, the framework is flexible and extensible to generate and attach new security policies to Gates. We introduce an Analysis Center for collecting traffic report data from Gates and generating a real-time social graph which can be used by a social computation model to compute the social power, a kind of individual capability used to control resource access. Security policy strings are then populated with the social power values and plugged into Gates to control the communication among the accountable users on the Internet. In this thesis, we provide the design of the whole framework and analyze the social computation results: which factors impact the social power value. Additionally, to reduce the computation complexity, we extract small sub-graphs being able to reflect the major properties of the original social graph and discuss which extraction method is the best among BFS, RW and MHRW. / Les réseaux sociaux jouent un rôle de plus en plus important sur notre façon de communiquer sur Internet. Nous présentons un modèle général intitulé "réseaux dirigés socialement" qui contient une mesure de protection de réseau au niveau de l'organisation individuelle et sociale plutôt qu'au niveau traditionnel d'adresse physique. La fonction de ces réseaux socialement dirigés est principalement composée de deux parties: la responsabilité sociale et la génération de mesures de sécurité basée sur la computation sociale. Pour la partie de responsabilité sociale, nous désignons des Identités (Identité Personnelle et Identité Sociale) liant les actions des utilisateurs sur Internet à leur identité sociale conférée par un certain réseau social (tel que Facebook) plutôt qu'à leur adresse physique (IP), pour que les utilisateurs soient reconnus partout sur Internet sans qu'on leur emprunte leur identité. Ce système d'Identités est déployable progressivement sur Internet et peut être utilisées pour surveiller et contrôler les échanges entre utilisateurs. Pour la partie de génération de mesures de sécurité, le modèle est flexible et extensible pour générer et ajouter des nouvelles mesures de sécurité aux Identités. Nous introduisons un Centre d'Analyse pour collecter les rapports de données provenant des Identités et pour générer un graphe social en temps réel, qui peut être utilisé par un modèle de computation sociale pour calculer le pouvoir social, une sorte de capacité individuelle utilisée pour contrôler l'accès d'un individu à certaines ressources. Les mesures de sécurité sont ensuite assignées aux valeurs de pouvoir sociale puis associées aux Identités pour contrôler les communications entre les utilisateurs responsables sur Internet. Dans cette thèse, nous donnons le design du modèle au complet puis analysons les résultats de la computation sociale: Quels facteurs impactent le pouvoir social et lequel est le plus important. De plus, pour réduire la complexité du calcul, nous extrayons un petit sous-graphe représentatif des propriétés majeurs du graphe social original, puis discutons de la meilleure méthode d'extraction entre BFS, RW et MHRW.

Line-of-sight networks were introduced by Frieze et al. to model wireless communications in an urban setting. Their model is based on a two-dimensional grid of points in the shape of a torus. Two grid points are said to be mutually visible if they lie in the same row or column of the torus and if the distance between them is within a certain predetermined range. Distance is measured using the L1 norm. A random graph is obtained by placing a node at each grid point independently with the same placement probability and connecting all mutually visible pairs of nodes. Among the results proven by Frieze et al. is a threshold for the connectivity of the graph.In this thesis we extend the model of Frieze et al. to higher dimensions and the general Lp norm. Specifically we consider an underlying d-dimensional grid in the shape of a torus and we define two points to be mutually visible if they differ in at most k coordinates, and the distance between them is within a certain range. We then prove corresponding asymptotically tight connectivity thresholds for this generalized model. / Les réseaux de lignes de visée ont été introduits par Frieze et al. pour modéliser les communications sans fil en milieu urbain. Leur modèle est basé sur une grille bidimensionnelle de points en forme de tore. Deux points de la grille sont dits mutuellement visibles si ils sont situés sur la même ligne ou la même colonne du tore et si la distance entre eux est dans un certain intervalle prédéterminé. La distance est mesurée en utilisant le norme L1. Un graphe aléatoire est obtenu en plaçant un noeud à chaque point de la grille indépendamment avec la même probabilité de placement et en reliant toutes les paires de noeuds qui sont mutuellement visible. En particulier, Frieze et. al déterminent le seuil de connectivité du graphe.Dans cette thèse, nous généralisons le modèle de Frieze et al. à dimensions supérieures. Plus précisément, nous considérons comme un réseau sous-jacent une grille à d dimensions et nous disons que deux points sont mutuellement visibles si ils ont un maximum de k coordonnées différentes, et si la distance entre eux est dans un certain intervalle. Ensuite, nous prouvons un seuil pour la connectivité de ce modèle généralisé.