This thesis focuses on a particular class of representations of visual form, those based on the Blum skeleton [6]. We shall argue that such a representation has a number of desirable properties, which any good shape descriptor should possess. We shall begin this discussion in Section 1.1 but will keep it on a relatively high level leaving the details to Chapter 2. We shall then, in Section 1.2, review some of the previous work on skeletonization and identify the major computational difficulties encountered in the past. Finally, in Section 1.3, we shall briefly discuss how the method presented in this thesis deals with those issues and we shall identify the contributions of this work.

The subject of this thesis is synchronous master-slave database replication, failover and distributed recovery for a cluster of database servers. Our replication solution allows updates on the master, and queries on ail sites. Updates of transactions are sent to ail sites before they are committed on the master. To do this, we take advantage of the semantics of group communication Systems. With failover, there is always a master in the group. Distributed recovery ensures that a site that has been introduced in the System brings its own copy of the database to be consistent with the rest of the other databases. It does this by getting all the transactions it missed from another site while it was not in the group. It is only after having successfully carried out failover and recovery mechanisms that a new site is ready to share in the load of the system.

This thesis presents a statistical framework and its implementation in a user-assisted rotoscoping program intended for the production of animation movies. User-assisted video segmentation of scenes with well-defined foreground and background, a special case of the general problem of rotoscoping, is used to analyze the properties of the framework and its implementation. The statistical model used in the framework is built from pairs of training images composed of a frame from the sequence to segment and of a binary image representing the associated user-specified segmentation. The segmentation for a new frame is generated by pasting in, for each image patch, the nearest neighbor from the training set. A mechanism inspired by belief propagation is used to insure consistency between neighboring patches. The algorithm is applied at different scale levels of the input images to take into account longer range interactions. A performance metric is defined for the automatic segmentation and the segmentation results are compared with a set of video sequences that have been entirely traced by hand. A new technique is also presented to automatically choose the optimal training data for the statistical model. A crude segmentation is computed from the smallest possible training set (one frame). A statistical analysis of this segmentation is then used to determine which other frames should be added to the training set in order to get the best possible segmentation. Finally, it is shown how the technique used for segmentation can be extended to perform example-based filtering of video and thus allow the creation of general-purpose rotoscoping systems. / Ce mémoire présente un modèle statistique ainsi que son implantation dans un programme de rotoscopie qui peut être utilisé pour la production de films d'animation. Le problème de la segmentation assistée de scènes video contenant un avant-plan et un arrière-plan distincts, un sous-ensemble du problème plus général que constitue la rotoscopie, est utilisé pour analyser les propriétés du modèle statistique et de son implantation. Le modèle statistique utilisé est construit à partir d'un découpage de paires d'images d'entraînement composées d'un cadre de la séquence video à segmenter et d'une image binaire qui défini la segmentation associée. La segmentation de chaque cadre de la sequence est obtenue en collant, pour chaque portion d'image, la portion d'image la plus similaire de l'ensemble d'entraînement. Un mécanisme inspiré de la "propagation de conviction"(belief propagation) est utilisé pour assurer la cohérence entre les portions de l'image de sortie qui sont voisines. L'algorithme est appliqué à plusieurs niveaux d'échelle afin de considérer la dépendance statistique de plus longue portée qui existe entre les pixels d'une image. Une métrique est définie pour mesurer la performance de la segmentation automatique. Les résultats de la segmentation sont analysés à l'aide d'une série de séquences vidéo qui ont préalablement été segmentées manuellement. Une nouvelle technique est également présentée pour permettre au logiciel de segmentation de choisir automatiquement l'ensemble d'entraînement optimal. Une segmentation grossière est d'abord obtenue en ulitisant le plus petit ensemble d'entraînement possible (1 cadre)

Developers invest a large portion of their development time exploring program source code to find task-related code elements and to understand the context of their task. The task context is usually not recorded at the end of the task and is forgotten over time. Similarly, it is not possible to share the task context with other developers working on related tasks. Proposed solutions to automatically record the summary of the code investigation suffer from methodological limitations related to the techniques and the data sources used to generate the summary as well as the granularity at which it is generated. To overcome these limitations, we investigate the use of machine learning techniques, in particular decision tree learning, to predict automatically the task context from session navigation transcripts obtained from developers performing tasks on the source code. We conducted a user study to collect navigation transcripts from developers engaged in source code exploration tasks. We used the data from the user study to train and test decision tree classifiers. We compared the decision tree algorithm with two existing approaches, and found that it compares positively in most cases. Additionally, we developed an Eclipse plug-in that generates automatically a developer session summary using the decision tree classifier learned from the data collected during the user study. We provide qualitative analysis of the effectiveness of this plug-in. / Les d\'eveloppeurs de logiciels investissent une grande partie de leur temps \`a explorer le code source pour trouver des \'el\'ements du code reli\'es \`a leurs t\^aches, et aussi pour mieux comprendre le contexte de leur t\^ache. Le contexte de leur t\^ache n'est g\'en\'eralement pas enregistr\'ee \`a la fin de leur s\'eance d'exploration de code et est oubli\'e au fil du temps. De m\^eme, il n'est pas possible de partager le contexte de leur t\^ache avec d'autres d\'eveloppeurs travaillant sur des t\^aches reli\'ees. Les solutions propos\'ees pour enregistrer automatiquement le r\'esum\'e de leur exploration du code souffrent de limitations m\'ethodologiques li\'ees aux techniques et aux sources de donn\'ees utilis\'ees pour g\'en\'erer le r\'esum\'e, ainsi qu'\`a la granularit\'e \`a laquelle il est g\'en\'er\'e. Pour surmonter ces limitations, nous \'etudions l'emploi de techniques d'apprentissage machine, en particulier l'arbre de d\'ecision d'apprentissage, pour pr\'evoir automatiquement le contexte de la t\^ache \`a partir des transcriptes de navigation d'une session d'exploration de code du d\'eveloppeur. Nous avons effectu\'e une \'etude de cas afin de recueillir des transcriptions de navigation g\'en\'er\'es par des d\'eveloppeurs lors de l'exploration du code source. Nous avons utilis\'e les donn\'ees de cette \'etude pour tester les classifications de l'arbre de d\'ecision. Nous avons compar\'e l'algorithme \`a arbre \`a d\'ecision avec deux approches existantes, et avons d\'emontr\'e que cette nouvelle approche se compare favorablement dans la plupart des cas. Additionnellement, nous avons d\'evelopp\'e un plug-in Eclipse qui g\'en\`ere automatiquement un

This thesis deals with the study of performer-instrument interaction during the performance of novel digital musical instruments (DMIs). Unlike acoustic instruments, digital musical instruments have no coupling between the sound generation system and the physical interface with which the performer interacts. As a result of this, such instruments also lack the direct physical feedback to the performer which is present in an acoustic instrument. In fact in contrast to acoustic musical instruments, haptic and vibrotactile feedback is generally not present in a DMI contributing to a poor feel for the instrument. The main goal of this thesis is to propose ways to improve the overall feel of digital musical instruments through the study and design of its physical interface: the instrument body, sensors and feedback actuators. It includes a detailed study of the existing theory and practice of the design on physical interfaces for digital musical instruments, including a survey of 266 existing DMIs presented since the inception of the NIME conference. From this, a number of differences become apparent between the existing theory and practice, particularly in the areas of sensors and feedback. The research in this thesis then addresses these differences. It includes a series of experiments on the optimal choice of sensors for a digital musical instrument. This is followed by research into the provision of vibrotactile feedback in a digital musical instrument, including the choice of actuator, modification of actuator frequency response, and the effects of response modification on human vibrotactile frequency discrimination. Following this, a number of new digital musical instruments are presented, which were created during the course of this work. This includes an instrument designed specifically to follow the results of research in this thesis and also instruments designed as part of larger collaborative projects involving engineers, composers and performers. Fro / Cette thèse porte sur l'étude de l'interaction ayant lieu, en situation de jeu,entre un(e) instrumentiste et un instrument musical numérique (IMN).A l'inverse des instruments acoustiques traditionnels, il n'existe aucun couplageentre le dispositif de production du son et l'interface sur laquelle agit l'instrumentistedans le cas des IMN. L'une des implications de cette observation est que cesinstruments ne procurent pas la rétroaction tactile normalement présente dans lesinstruments de musique traditionels. Par conséquent, les IMN sont souvent perçuspar leurs interprètes comme manquant d'âme, de personnalité.Le but de ce travail de thèse est d'avancer quelques solutions permettant d'insuer un peu plus âme à un instrument musical numérique. Le point focal de larecherche étant l'étude et la conception de l'interface physique (corps de l'instrument,capteurs et dispositifs de rétroaction utilisés) d'un tel instrument.Ce mémoire présente, en premier lieu, une étude détaillée de la théorie et de lapratique actuelles dans le domaine de la conception d'interfaces physiques pour lesIMN. L'inventaire des 266 instruments recensés depuis la création de la conférenceNIME constitue l'un des points majeurs de cette partie du travail. En effet, ce tour d'horizon permet de faire ressortir les incohérences entre théorie et pratique. Cesdifférences sont particulièrement frappantes en ce qui concerne les capteurs et lesdispositifs de rétroaction.Le travail de recherche de cette thèse a donc pour objectif de mieux comprendrecomment réduire ces incohérences. Des expériences portant sur le choix optimaldes capteurs à utiliser dans un IMN ont donc été menées. Différents dispositifs derétroaction vibrotactile ont aussi été étudiés en regardant d'abord quels actuateursutiliser, et en évaluant les effets de la modication de leur réponse en fréquencesur la discrimination fréquentielle de stimuli vibrotactiles chez des sujets humains.Des exemp

The spread of Information and Communication Technologies (ICTs) has transformed the way we deliver services, and has made them in general more efficient and more accessible to users. With these improvements however came new challenges. The extensive use of electronic services in our daily life, and the massive gathering of transactional data have led to serious privacy violations. / In this thesis we provide techniques to enhance users' privacy, and to give them greater control over their data. We propose a protocol allowing users to authorize access to their remotely-stored records, according to a self-chosen privacy policy, and without the storage server learning the access pattern to their records, or the index of the queried records. This prevents the storage server from linking the identity of the party retrieving a record to that of the record owner. In many applications, the association between the identity of the record retriever and that of the record owner represents sensitive information, and needs to be kept private. The proposed protocol is called Accredited Symmetrically Private Information Retrieval (ASPIR), and uses Brands's Anonymous Credentials [Bra00] and a Symmetrically Private Information Retrieval (SPIR) scheme by Lipmaa [Lip05], as building blocks. / Next, we extend the above ASPIR protocol to a setting where the stored records belong to multiple owners simultaneously. The new protocol, called Multi-Authorizer ASPIR, allows the owners of a record to authorize access to their data according to a self-chosen privacy policy, without the storage server learning the access pattern to their record. We present constructions for settings where the retrieving party has to provide authorizations either from all the owners of the target record, or from a subset of them of size greater that a certain threshold. We also consider the case of a General Access Structure, where the retrieval is allowed only if authorizations from certain pre-defined subsets of the owners are provided. The Multi-authorizer ASPIR protocol is more efficient than ASPIR, and can be built with any SPIR primitive. / Finally, we dedicate the last part of the thesis to applying privacy preserving techniques to a real world problem. In particular, we consider the area of e-health, and provide a privacy-preserving protocol for handling prescriptions in the Belgian healthcare system. / La prolifération des services électroniques a eu des retombées positives sur nos sociétés. Les technologies de l'information ont révolutionné divers domaines clé de notre vie, notamment les services gouvernementaux, les affaires, la santé, les transports, les communications et l'éducation. Souvent, le passage au numérique, a rendu les services plus accessibles, plus rapides, plus faciles à utiliser et socialement plus inclusifs. Cependant, avec ces améliorations sont apparus aussi de nouveaux problèmes. En effet, l'utilisation des services électroniques au quotidien, et la collecte massives de données transactionnelles sur les utilisateurs, ont conduit à l'établissement de ce qu'on appelle communément les "dossiers électroniques". Un dossier électronique est une compilation de données personnelles récoltées lorsqu'un individu effectue des transactions électroniques ou reçoit des services. Ces dossiers sont de plus en plus utilisés par le gouvernement et les corporations pour prendre des décisions importantes sur les individus, sans que ces derniers ne soient capables d'y participer. / Cette thèse présente des techniques pour protéger davantage la vie privée des citoyens et leur donner plus de contrôle sur leurs données. On propose, entre autres, un protocole pour permettre à des utilisateurs d'autoriser l'accès à leurs données, sauvegardées sur un serveur distant, sans que celui-ci n'apprenne d'informations sur la fréquence et la distribution des accès, ou même sur l'indice des données récupérées. Ceci empêche le serveur d'établir des liens entre l'identité d'un propriétaire de données, et celle de l'agent qui a demandé l'accès à ses données. On peut penser à une multitude de scénarios où la divulgation de l'existence d'un tel lien est non souhaitable. Le protocole qu'on propose est nommé ASPIR de l'Anglais (Accredited Symmetrically Private Information Retrieval), et utilise les systèmes de certification de Brands [Bra00], ainsi que le système SPIR de Lipmaa [Lip05]. / Dans un deuxième temps, on généralise le protocole ASPIR initial à un environnement où les entrées appartiennent à plusieurs parties. Le nouveau protocole, nommé Multi-Authorizer ASPIR, permet aux propriétaires d'autoriser l'accès à leurs données selon une politique qu'ils ont eux même choisie, et sans que le serveur n'apprenne des informations sur la fréquence et la distribution des accès. On présente des constructions pour des scénarios où le demandeur de données doit fournir une autorisation de la part de tous les (respectivement une partie des) propriétaires. Le protocole, Multi-authorizer ASPIR, est plus performant, et peut être implanté avec n'importe quel système SPIR. / Enfin, la dernière partie de la thèse est dédiée à l'application des techniques de protection de la vie privée à un exemple concret de la vie courante. L'exemple qu'on traite appartient au domaine de la santé. On présente alors un protocole pour gérer les ordonnances médicales, qui est compatible avec le système de santé Belge. Le protocole proposé préserve la vie privée des patients et des médecins.

The history of the Time Warp protocol, one of the most commonly used synchronization protocols in parallel and distributed simulation, has been a history of optimizations. Usually the optimization problems are solved by creating an analytical model for the simulation system through careful analysis of the behavior of Time Warp. The model is expressed as a closed-form function that maps system state variables to a control parameter. At run-time, the system state variables are measured and then utilized to derive the value for the control parameter. This approach makes the quality of the optimization heavily dependent on how closely the model actually reflects the simulation reality. Because of the simplifications that are necessary to make in the course of creating such models, it is not certain the control strategies are optimal. Furthermore, models based on a specific application cannot be readily adopted for other applications. / In this thesis, as an alternative approach, we present a number of model-free direct-search algorithms based on techniques from system control, machine learning, and evolutionary computing, namely, learning automata, reinforcement learning, and genetic algorithms. What these methods have in common is the notion of learning. Unlike the traditional methods used in Time Warp optimization, these learning methods treat the Time Warp simulator as a black box. They start with a set of candidate solutions for the optimization parameter and try to find the best solution through a trial-and-error process: learning automata give a better solution a higher probability to be tried; reinforcement learning keeps a value for each candidate that reflects the candidate's quality; genetic algorithms have a dynamic set of candidates and improves the quality of the set by mimicking the evolutionary process. We describe how some optimization problems in Time Warp can be transformed into a search problem, and how the learning methods can be utilized to directly search for the optimal value for the system control parameter. Compared with the analytical model-based approach, these methods are more generic in nature. Since the search is based on actual run-time performance of different values for the control parameter, the learning methods also better reflect the simulation reality. / L'histoire du protocole Time Warp, l'un des protocoles de synchronisation le plus couramment utilise en matiere de simulation parallele et distribue, a ete une histoire de optimisations. Habituellement, la problemes d'optimisation sont resolus par creer un modele analytique pour le systeme de simulation par une analyse minutieuse de la comportement de Time Warp. Le modele est exprime comme une fonction de la forme ferme entre les variables d'etat du systeme et un parametre de controle. Au moment de l'execution, les variables d'etat du systeme sont mesures et servent ensuite à calculer la valeur du parametre de controle. Cette approche rend la qualite de l'optimisation dépend fortement sur la maniere de pres le modele reflete reellement la realite de simulation. En raison de la simplications qui sont necessaires de faire dans le courant de creer de tels modeles, il n'est pas certain que les strategies de controle sont optimale. En outre, les modeles bases sur une application specifique ne peut etre facilement adopte pour d'autres applications. / Dans cette these, comme une approche alternative, nous presentons un certain nombre de algorithmes de direct recherche sans modeles base sur des techniques de controle du systeme, l'apprentissage automatique et evolutive l'informatique, a savoir, l'apprentissage des automates, apprentissage par renforcement, et genetique algorithmes. Ce que ces methodes ont en commun est la notion d'apprentissage. Contrairement aux methodes traditionnelles utilisees dans d'optimisation de Time Warp, ces apprentissages méthodes traitent le simulateur Time Warp comme une boite noire. Ils commencent par une ensemble de solutions candidates pour le parametre d'optimisation et essayer de trouver la meilleure solution grace a un essai-erreur de processus: l'apprentissage d'automates donner un meilleur solution d'une plus grande probabilite d'etre juge; apprentissage par renforcement garde un valeur pour chaque candidat qui reflete la qualite du candidat; genetiques algorithmes ont un ensemble dynamique de candidats et ameliore la qualite de la mis en imitant le processus evolutif. Nous decrivons comment certains probl`emes d'optimisation dans Time Warp peut etre transforme en un probleme de recherche, et comment les methodes d'apprentissage peut etre utilise pour directement recherche de la valeur optimale pour le parametre de controle du systeme. En comparaison avec le modele analytique approche, ces methodes sont plus generiques dans la nature. Comme la recherche est basee sur l'ecoulement des performances en temps reel des differents valeurs pour le parametre de controle, les methodes d'apprentissage aussi de mieux refleter la realite de la simulation.

Learning agents that interact with complex environments often cannot predict the exact outcome of their actions due to noisy sensors or incomplete knowledge of the world. Learning the internal representation of such partially observable environments has proven to be a difficult problem. In order to simplify this task, the agent can choose to give up building an exact model which is able to predict all possible future behaviours, and replace it with a more modest goal of predicting only specific quantities of interest. / In this thesis we are primarily concerned with ways of representing the agent's state that allows it to predict the conditional probability of a restricted set of future events, given the agent's past experience. Because of memory limitations, the agent's experience must be summarized in such a way as to make these restricted predictions possible. We introduce the novel idea of history representations, which allow us to condition the predictions on ``interesting'' behaviour, and present a simple algorithmic implementation of this framework. The learned model abstracts away the unnecessary details of the agent's experience and focuses only on making certain predictions of interest. We illustrate our approach empirically in small computational examples, demonstrating the data efficiency of the algorithm. / L'apprentissage d'agents artificiels confrontés à un environnement complexe est souvent difficile dû à leur incapacité à prédire le résultat de leurs actions et à une description incomplète du système. L'apprentissage d'une représentation interne d'un environnement partiellement observable est particulièrement malaisé. Afin de simplifier cette tâche, l'agent peut, plutôt que de constuire un modèle exact capable de prédire tout comportement futur, chercher à ne prédire que quelque phénomènes en particulier. / Dans cet ouvrage, nous nous intéressons à la question de représenter l'état du système de manière à predire la probabilité conditionnelle d'un ensemble restreint d'événements, étant donné l'expérience précédente de l'agent. Dû à une limite quant à la capacité mémoire de l'agent, cette expérience doit être résumée quant à rendre atteignable cet ensemble restreint de prédictions. Nous proposons ici l'idée d'employer des représentations basées sur un historique afin de produire des prédictions conditionnelles à des comportements ``intéressants''. Nous développons cette idée par le bias d'un algorithme. Nous illustrons notre approche de manière empirique à travers de simples exemples computationnels, démontrant ainsi l'efficacité de l'algorithme quant à la quantitée de données requises.

Reinforcement Learning is a branch of Artificial Intelligence addressing the problem of single-agent autonomous sequential decision making. It proposes computational models which do not rely on the complete knowledge of the dynamics of stochastic environments. Options are a formalism used to temporally extend actions towards hierarchically organized behaviour, a concept used to improve learning in large-scale problems. In this thesis we propose a new approach for generating options. Given controllers or behaviour policies as prior knowledge, we learn how to switch between these policies by optimizing the expected total discounted reward of the hierarchical behaviour. We derive gradient descent-based algorithms for learning optimal termination conditions of options, based on a new option termination representation. We provide theoretical guarantees and extentions of widely used Reinforcement Learning algorithms when options have variable time-scales. Finally, we incorporate the proposed approach into policy-gradient methods with linear function approximation. / L'apprentissage par renforcement est une branche de l'intelligence artificielle qui traite la problème de la prise de décision autonome des agents-individuels. Celui-ci fournit des modèles de calcul qui ne sont pas dépendants sur la connaissance complète de la dynamique des environnement stochastique. Les options présentent un formalisme utilisé à rallonger temporellement les actions pour obtenir des façons d'agir organisées dans une hiérarchie. Dans cette thèse, on propose une nouvelle approche pour générer des options. Étant donné q'on a des contrôleurs ou façons d'agir comme connaissances préalables, on apprend a commuter l'utilisation des contrôleurs en optimisant l'espérace de la récompence totale escomptée du façon d'agir hiérarchique. On dérive des algorithmes basés sur la descente de gradient pour apprendre les conditions de terminaison optimales, en utilisant une nouvelle représentation de la terminaison. On fournit des garanties théorétiques et des variations des algorithmes largement utilisés dans l'apprentisage par renforcement, en employant des options avec échelles de temps variables. Enfin, on intègrent l'approche proposée dans des méthodes qui utilisent la descente de gradient pour les façon d'agir avec l'approximation linéaire de fonction.

We present a framework of specularity pattern to interpret the interaction between specularities and short-wave specular planes as well as light sources at infinity. The specularity on a short-wave plane is treated as a special kind of texture (specularity pattern) mapping on a flat carrier plane. This concept of specularity pattern acts as an intermediate layer between the 3D scene setting and the 2D image of the scene. Under the framework of specularity pattern, the information on specularities is divided into two parts, appearance and statistics. The appearance provides a texture for mapping to invoke impression of specularities. The statistics is the properties to generate such a plausible appearance. The statistics of specularity pattern contains the highlight occurrence probabilities on different locations in the specularity pattern and the size and shape of individual highlight particles. These statistics are derived from the surface roughness, the lightening condition, and the camera position. In addition, we have developed an algorithm to generate a plausible specularity pattern without going through the process of ray-tracing. Since this specularity pattern rendering method does not focus on any specific family of short-wave plane, it works well on surfaces without closed-form expressions and surfaces without exact height or normal maps. Also, we outline a potential application of the framework of specularity pattern in computer vision. / Nous présentons un modèle de cadre de la spécularité d'interpréter l'interaction entre spécularités et ondes courtes plans spéculaires ainsi que des sources de lumière à l'infini. La spécularité sur un plan de court-ondes est considérée comme une forme particulière de texture (spécularité motif) la cartographie sur un plan porteur plat. Ce concept de modèle de spécularité agit comme une couche intermédiaire entre la mise en scène 3D et 2D de l'image de la scène. Dans le cadre du modèle de la spécularité, les informations sur spécularités est divisé en deux parties, l'apparence et les statistiques. L'aspect donne une texture pour la cartographie d'invoquer impression de spécularités. Les statistiques sont les propriétés pour générer une telle apparence plausible. Les statistiques du modèle de la spécularité contient les probabilités d'occurrence mettre en évidence à différents endroits dans la configuration spécularité et de la taille et la forme des particules individuelles en évidence. Ces statistiques sont tirées de la rugosité de surface, l'état d'allégement, et la position de la caméra. En outre, nous avons développé un algorithme pour générer un motif plausible spécularité sans passer par le processus de ray-tracing. Depuis cette méthode motif spécularité rendu ne porte pas sur toute la famille spécifique de l'avion à ondes courtes, il fonctionne bien sur des surfaces sans expressions forme fermée et surfaces sans hauteur exacte ou des cartes normales. En outre, nous présentons une application potentielle du cadre de modèle spécularité en vision par ordinateur.