Rendu de matériaux semi-transparents hétérogènes en temps réel

On retrouve dans la nature un nombre impressionnant de matériaux semi-transparents tels le marbre, le jade ou la peau, ainsi que plusieurs liquides comme le lait ou les jus. Que ce soit pour le domaine cinématographique ou le divertissement interactif, l'intérêt d'obtenir une image de synthèse de ce type de matériau demeure toujours très important. Bien que plusieurs méthodes arrivent à simuler la diffusion de la lumière de manière convaincante a l'intérieur de matériaux semi-transparents, peu d'entre elles y arrivent de manière interactive. Ce mémoire présente une nouvelle méthode de diffusion de la lumière à l'intérieur d'objets semi-transparents hétérogènes en temps réel. Le coeur de la méthode repose sur une discrétisation du modèle géométrique sous forme de voxels, ceux-ci étant utilisés comme simplification du domaine de diffusion. Notre technique repose sur la résolution de l'équation de diffusion à l'aide de méthodes itératives permettant d'obtenir une simulation rapide et efficace. Notre méthode se démarque principalement par son exécution complètement dynamique ne nécessitant aucun pré-calcul et permettant une déformation complète de la géométrie.

Technique de visualisation pour l’identification de l’usage excessif d’objets temporaires dans les traces d’exécution

De nos jours, les applications de grande taille sont développées à l’aide de nom- breux cadres d’applications (frameworks) et intergiciels (middleware). L’utilisation ex- cessive d’objets temporaires est un problème de performance commun à ces applications. Ce problème est appelé “object churn”. Identifier et comprendre des sources d’“object churn” est une tâche difficile et laborieuse, en dépit des récentes avancées dans les tech- niques d’analyse automatiques. Nous présentons une approche visuelle interactive conçue pour aider les développeurs à explorer rapidement et intuitivement le comportement de leurs applications afin de trouver les sources d’“object churn”. Nous avons implémenté cette technique dans Vasco, une nouvelle plate-forme flexible. Vasco se concentre sur trois principaux axes de con- ception. Premièrement, les données à visualiser sont récupérées dans les traces d’exécu- tion et analysées afin de calculer et de garder seulement celles nécessaires à la recherche des sources d’“object churn”. Ainsi, des programmes de grande taille peuvent être vi- sualisés tout en gardant une représentation claire et compréhensible. Deuxièmement, l’utilisation d’une représentation intuitive permet de minimiser l’effort cognitif requis par la tâche de visualisation. Finalement, la fluidité des transitions et interactions permet aux utilisateurs de garder des informations sur les actions accomplies. Nous démontrons l’efficacité de l’approche par l’identification de sources d’“object churn” dans trois ap- plications utilisant intensivement des cadres d’applications framework-intensive, inclu- ant un système commercial.

A Compiler for the dependently typed language Beluga

Les structures avec des lieurs sont très communes en informatique. Les langages de programmation et les systèmes logiques sont des exemples de structures avec des lieurs. La manipulation de lieurs est délicate, de sorte que l’écriture de programmes qui ma- nipulent ces structures tirerait profit d’un soutien spécifique pour les lieurs. L’environ- nement de programmation Beluga est un exemple d’un tel système. Nous développons et présentons ici un compilateur pour ce système. Parmi les programmes pour lesquels Beluga est spécialement bien adapté, plusieurs peuvent bénéficier d’un compilateur. Par exemple, les programmes pour valider les types (les "type-checkers"), les compilateurs et les interpréteurs tirent profit du soutien spécifique des lieurs et des types dépendants présents dans le langage. Ils nécessitent tous également une exécution efficace, que l’on propose d’obtenir par le biais d’un compilateur. Le but de ce travail est de présenter un nouveau compilateur pour Beluga, qui emploie une représentation interne polyvalente et permet de partager du code entre plusieurs back-ends. Une contribution notable est la compilation du filtrage de Beluga, qui est particulièrement puissante dans ce langage.

PROTECT_U: Un système communautaire pour la protection des usagers de Facebook

Article publié dans le journal « Journal of Information Security Research ». March 2012.

Détection des chutes par calcul homographique

La vidéosurveillance a pour objectif principal de protéger les personnes et les biens en détectant tout comportement anormal. Ceci ne serait possible sans la détection de mouvement dans l’image. Ce processus complexe se base le plus souvent sur une opération de soustraction de l’arrière-plan statique d’une scène sur l’image. Mais il se trouve qu’en vidéosurveillance, des caméras sont souvent en mouvement, engendrant ainsi, un changement significatif de l’arrière-plan; la soustraction de l’arrière-plan devient alors problématique. Nous proposons dans ce travail, une méthode de détection de mouvement et particulièrement de chutes qui s’affranchit de la soustraction de l’arrière-plan et exploite la rotation de la caméra dans la détection du mouvement en utilisant le calcul homographique. Nos résultats sur des données synthétiques et réelles démontrent la faisabilité de cette approche.

Mures : Un système de recommandation de musique

Pendant la dernière décennie nous avons vu une transformation incroyable du monde de la musique qui est passé des cassettes et disques compacts à la musique numérique en ligne. Avec l'explosion de la musique numérique, nous avons besoin de systèmes de recommandation de musique pour choisir les chansons susceptibles d’être appréciés à partir de ces énormes bases de données en ligne ou personnelles. Actuellement, la plupart des systèmes de recommandation de musique utilisent l’algorithme de filtrage collaboratif ou celui du filtrage à base de contenu. Dans ce mémoire, nous proposons un algorithme hybride et original qui combine le filtrage collaboratif avec le filtrage basé sur étiquetage, amélioré par la technique de filtrage basée sur le contexte d’utilisation afin de produire de meilleures recommandations. Notre approche suppose que les préférences de l'utilisateur changent selon le contexte d'utilisation. Par exemple, un utilisateur écoute un genre de musique en conduisant vers son travail, un autre type en voyageant avec la famille en vacances, un autre pendant une soirée romantique ou aux fêtes. De plus, si la sélection a été générée pour plus d'un utilisateur (voyage en famille, fête) le système proposera des chansons en fonction des préférences de tous ces utilisateurs. L'objectif principal de notre système est de recommander à l'utilisateur de la musique à partir de sa collection personnelle ou à partir de la collection du système, les nouveautés et les prochains concerts. Un autre objectif de notre système sera de collecter des données provenant de sources extérieures, en s'appuyant sur des techniques de crawling et sur les flux RSS pour offrir des informations reliées à la musique tels que: les nouveautés, les prochains concerts, les paroles et les artistes similaires. Nous essayerons d’unifier des ensembles de données disponibles gratuitement sur le Web tels que les habitudes d’écoute de Last.fm, la base de données de la musique de MusicBrainz et les étiquettes des MusicStrands afin d'obtenir des identificateurs uniques pour les chansons, les albums et les artistes.

Evaluating Design Decay during Software Evolution

Les logiciels sont en constante évolution, nécessitant une maintenance et un développement continus. Ils subissent des changements tout au long de leur vie, que ce soit pendant l'ajout de nouvelles fonctionnalités ou la correction de bogues dans le code. Lorsque ces logiciels évoluent, leurs architectures ont tendance à se dégrader avec le temps et deviennent moins adaptables aux nouvelles spécifications des utilisateurs. Elles deviennent plus complexes et plus difficiles à maintenir. Dans certains cas, les développeurs préfèrent refaire la conception de ces architectures à partir du zéro plutôt que de prolonger la durée de leurs vies, ce qui engendre une augmentation importante des coûts de développement et de maintenance. Par conséquent, les développeurs doivent comprendre les facteurs qui conduisent à la dégradation des architectures, pour prendre des mesures proactives qui facilitent les futurs changements et ralentissent leur dégradation. La dégradation des architectures se produit lorsque des développeurs qui ne comprennent pas la conception originale du logiciel apportent des changements au logiciel. D'une part, faire des changements sans comprendre leurs impacts peut conduire à l'introduction de bogues et à la retraite prématurée du logiciel. D'autre part, les développeurs qui manquent de connaissances et–ou d'expérience dans la résolution d'un problème de conception peuvent introduire des défauts de conception. Ces défauts ont pour conséquence de rendre les logiciels plus difficiles à maintenir et évoluer. Par conséquent, les développeurs ont besoin de mécanismes pour comprendre l'impact d'un changement sur le reste du logiciel et d'outils pour détecter les défauts de conception afin de les corriger. Dans le cadre de cette thèse, nous proposons trois principales contributions. La première contribution concerne l'évaluation de la dégradation des architectures logicielles. Cette évaluation consiste à utiliser une technique d’appariement de diagrammes, tels que les diagrammes de classes, pour identifier les changements structurels entre plusieurs versions d'une architecture logicielle. Cette étape nécessite l'identification des renommages de classes. Par conséquent, la première étape de notre approche consiste à identifier les renommages de classes durant l'évolution de l'architecture logicielle. Ensuite, la deuxième étape consiste à faire l'appariement de plusieurs versions d'une architecture pour identifier ses parties stables et celles qui sont en dégradation. Nous proposons des algorithmes de bit-vecteur et de clustering pour analyser la correspondance entre plusieurs versions d'une architecture. La troisième étape consiste à mesurer la dégradation de l'architecture durant l'évolution du logiciel. Nous proposons un ensemble de m´etriques sur les parties stables du logiciel, pour évaluer cette dégradation. La deuxième contribution est liée à l'analyse de l'impact des changements dans un logiciel. Dans ce contexte, nous présentons une nouvelle métaphore inspirée de la séismologie pour identifier l'impact des changements. Notre approche considère un changement à une classe comme un tremblement de terre qui se propage dans le logiciel à travers une longue chaîne de classes intermédiaires. Notre approche combine l'analyse de dépendances structurelles des classes et l'analyse de leur historique (les relations de co-changement) afin de mesurer l'ampleur de la propagation du changement dans le logiciel, i.e., comment un changement se propage à partir de la classe modifiée è d'autres classes du logiciel. La troisième contribution concerne la détection des défauts de conception. Nous proposons une métaphore inspirée du système immunitaire naturel. Comme toute créature vivante, la conception de systèmes est exposée aux maladies, qui sont des défauts de conception. Les approches de détection sont des mécanismes de défense pour les conception des systèmes. Un système immunitaire naturel peut détecter des pathogènes similaires avec une bonne précision. Cette bonne précision a inspiré une famille d'algorithmes de classification, appelés systèmes immunitaires artificiels (AIS), que nous utilisions pour détecter les défauts de conception. Les différentes contributions ont été évaluées sur des logiciels libres orientés objets et les résultats obtenus nous permettent de formuler les conclusions suivantes: • Les métriques Tunnel Triplets Metric (TTM) et Common Triplets Metric (CTM), fournissent aux développeurs de bons indices sur la dégradation de l'architecture. La d´ecroissance de TTM indique que la conception originale de l'architecture s’est dégradée. La stabilité de TTM indique la stabilité de la conception originale, ce qui signifie que le système est adapté aux nouvelles spécifications des utilisateurs. • La séismologie est une métaphore intéressante pour l'analyse de l'impact des changements. En effet, les changements se propagent dans les systèmes comme les tremblements de terre. L'impact d'un changement est plus important autour de la classe qui change et diminue progressivement avec la distance à cette classe. Notre approche aide les développeurs à identifier l'impact d'un changement. • Le système immunitaire est une métaphore intéressante pour la détection des défauts de conception. Les résultats des expériences ont montré que la précision et le rappel de notre approche sont comparables ou supérieurs à ceux des approches existantes.

Intégration de services de raisonnement automatique basés sur les logiques de description dans les applications d’entreprise

Ce mémoire présente un patron d’architecture permettant, dans un contexte orientéobjet, l’exploitation d’objets appartenant simultanément à plusieurs hiérarchies fonctionnelles. Ce patron utilise un reasoner basé sur les logiques de description (web sémantique) pour procéder à la classification des objets dans les hiérarchies. La création des objets est simplifiée par l’utilisation d’un ORM (Object Relational Mapper). Ce patron permet l’utilisation effective du raisonnement automatique dans un contexte d’applications d’entreprise. Les concepts requis pour la compréhension du patron et des outils sont présentés. Les conditions d’utilisation du patron sont discutées ainsi que certaines pistes de recherche pour les élargir. Un prototype appliquant le patron dans un cas simple est présenté. Une méthodologie accompagne le patron. Finalement, d’autres utilisations potentielles des logiques de description dans le même contexte sont discutées.

Sécurité polynomiale en cryptographie

Dans ce mémoire, nous proposons des protocoles cryptographiques d'échange de clef, de mise en gage, et de transfert équivoque. Un premier protocole de transfert équivoque, primitive cryptographique universelle pour le calcul multi-parties, s'inspire du protocole d'échange de clef par puzzle de Merkle, et améliore les résultats existants. Puis, nous montrons qu'il est possible de construire ces mêmes primitives cryptographiques sans l'hypothèse des fonctions à sens unique, mais avec le problème 3SUM. Ce problème simple ---dans une liste de n entiers, en trouver trois dont la somme a une certaine valeur--- a une borne inférieure conjecturée de Omega(n^2).

Amorçage cognitif pour amélioration de l’acquisition de la connaissance dans un système tutoriel intelligent

Cette thèse vise à définir une nouvelle méthode d’enseignement pour les systèmes tutoriels intelligents dans le but d’améliorer l’acquisition des connaissances. L’apprentissage est un phénomène complexe faisant intervenir des mécanismes émotionnels et cognitifs de nature consciente et inconsciente. Nous nous intéressons à mieux comprendre les mécanismes inconscients du raisonnement lors de l’acquisition des connaissances. L’importance de ces processus inconscients pour le raisonnement est bien documentée en neurosciences, mais demeure encore largement inexplorée dans notre domaine de recherche. Dans cette thèse, nous proposons la mise en place d’une nouvelle approche pédagogique dans le domaine de l’éducation implémentant une taxonomie neuroscientifique de la perception humaine. Nous montrons que cette nouvelle approche agit sur le raisonnement et, à tour de rôle, améliore l’apprentissage général et l’induction de la connaissance dans un environnement de résolution de problème. Dans une première partie, nous présentons l’implémentation de notre nouvelle méthode dans un système tutoriel visant à améliorer le raisonnement pour un meilleur apprentissage. De plus, compte tenu de l’importance des mécanismes émotionnels dans l’apprentissage, nous avons également procédé dans cette partie à la mesure des émotions par des capteurs physiologiques. L’efficacité de notre méthode pour l’apprentissage et son impact positif observé sur les émotions a été validée sur trente et un participants. Dans une seconde partie, nous allons plus loin dans notre recherche en adaptant notre méthode visant à améliorer le raisonnement pour une meilleure induction de la connaissance. L’induction est un type de raisonnement qui permet de construire des règles générales à partir d’exemples spécifiques ou de faits particuliers. Afin de mieux comprendre l’impact de notre méthode sur les processus cognitifs impliqués dans ce type de raisonnement, nous avons eu recours à des capteurs cérébraux pour mesurer l’activité du cerveau des utilisateurs. La validation de notre approche réalisée sur quarante-trois volontaires montre l’efficacité de notre méthode pour l’induction de la connaissance et la viabilité de mesurer le raisonnement par des mesures cérébrales suite à l’application appropriée d’algorithmes de traitement de signal. Suite à ces deux parties, nous clorons la thèse par une discussion applicative en décrivant la mise en place d’un nouveau système tutoriel intelligent intégrant les résultats de nos travaux.

Plateforme pour se protéger tant de soi-même que de ses "amis" sur Facebook

Les réseaux sociaux accueillent chaque jour des millions d’utilisateurs. Les usagers de ces réseaux, qu’ils soient des particuliers ou des entreprises, sont directement affectés par leur fulgurante expansion. Certains ont même développé une certaine dépendance à l’usage des réseaux sociaux allant même jusqu’à transformer leurs habitudes de vie de tous les jours. Cependant, cet engouement pour les réseaux sociaux n’est pas sans danger. Il va de soi que leur expansion favorise et sert également l’expansion des attaques en ligne. Les réseaux sociaux constituent une opportunité idéale pour les délinquants et les fraudeurs de porter préjudice aux usagers. Ils ont accès à des millions de victimes potentielles. Les menaces qui proviennent des amis et auxquelles font face les utilisateurs de réseaux sociaux sont nombreuses. On peut citer, à titre d’exemple, la cyberintimidation, les fraudes, le harcèlement criminel, la menace, l’incitation au suicide, la diffusion de contenu compromettant, la promotion de la haine, l’atteinte morale et physique, etc. Il y a aussi un « ami très proche » qui peut être très menaçant sur les réseaux sociaux : soi-même. Lorsqu’un utilisateur divulgue trop d’informations sur lui-même, il contribue sans le vouloir à attirer vers lui les arnaqueurs qui sont à la recherche continue d’une proie. On présente dans cette thèse une nouvelle approche pour protéger les utilisateurs de Facebook. On a créé une plateforme basée sur deux systèmes : Protect_U et Protect_UFF. Le premier système permet de protéger les utilisateurs d’eux-mêmes en analysant le contenu de leurs profils et en leur proposant un ensemble de recommandations dans le but de leur faire réduire la publication d’informations privées. Le second système vise à protéger les utilisateurs de leurs « amis » dont les profils présentent des symptômes alarmants (psychopathes, fraudeurs, criminels, etc.) en tenant compte essentiellement de trois paramètres principaux : le narcissisme, le manque d’émotions et le comportement agressif.

Construction d'un Atlas 3D numérique de la cornée humaine par recalage d'images

Nous proposons de construire un atlas numérique 3D contenant les caractéristiques moyennes et les variabilités de la morphologie d’un organe. Nos travaux seront appliqués particulièrement à la construction d'un atlas numérique 3D de la totalité de la cornée humaine incluant la surface antérieure et postérieure à partir des cartes topographiques fournies par le topographe Orbscan II. Nous procédons tout d'abord par normalisation de toute une population de cornées. Dans cette étape, nous nous sommes basés sur l'algorithme de recalage ICP (iterative closest point) pour aligner simultanément les surfaces antérieures et postérieures d'une population de cornée vers les surfaces antérieure et postérieure d'une cornée de référence. En effet, nous avons élaboré une variante de l'algorithme ICP adapté aux images (cartes) de cornées qui tient compte de changement d'échelle pendant le recalage et qui se base sur la recherche par voisinage via la distance euclidienne pour établir la correspondance entre les points. Après, nous avons procédé pour la construction de l'atlas cornéen par le calcul des moyennes des élévations de surfaces antérieures et postérieures recalées et leurs écarts-types associés. Une population de 100 cornées saines a été utilisée pour construire l'atlas cornéen normal. Pour visualiser l’atlas, on a eu recours à des cartes topographiques couleurs similairement à ce qu’offrent déjà les systèmes topographiques actuels. Enfin, des observations ont été réalisées sur l'atlas cornéen reflétant sa précision et permettant de développer une meilleure connaissance de l’anatomie cornéenne.

Construction interactive de BRDFs par simulation 2D de micro-géométries en couches multiples

Les modèles de réflexion complexes, avec leurs nombreux paramètres dont certains restent non intuitifs, sont difficiles à contrôler pour obtenir une apparence désirée. De plus, même si un artiste peut plus aisément comprendre la forme de la micro-géométrie d'une surface, sa modélisation en 3D et sa simulation en 4D demeurent extrêmement fastidieuses et coûteuses en mémoire. Nous proposons une solution intermédiaire, où l'artiste représente en 2D une coupe dans un matériau, en dessinant une micro-géométrie de surface en multi-couches. Une simulation efficace par lancer de rayons en seulement 2D capture les distributions de lumière affectées par les micro-géométries. La déviation hors-plan est calculée automatiquement de façon probabiliste en fonction de la normale au point d'intersection et de la direction du rayon incident. Il en résulte des BRDFs isotropes complètes et complexes, simulées à des vitesses interactives, et permettant ainsi une édition interactive de l'apparence de réflectances riches et variées.

Reliable Solid Modelling Using Subdivision Surfaces

Les surfaces de subdivision fournissent une méthode alternative prometteuse dans la modélisation géométrique, et ont des avantages sur la représentation classique de trimmed-NURBS, en particulier dans la modélisation de surfaces lisses par morceaux. Dans ce mémoire, nous considérons le problème des opérations géométriques sur les surfaces de subdivision, avec l'exigence stricte de forme topologique correcte. Puisque ce problème peut être mal conditionné, nous proposons une approche pour la gestion de l'incertitude qui existe dans le calcul géométrique. Nous exigeons l'exactitude des informations topologiques lorsque l'on considère la nature de robustesse du problème des opérations géométriques sur les modèles de solides, et il devient clair que le problème peut être mal conditionné en présence de l'incertitude qui est omniprésente dans les données. Nous proposons donc une approche interactive de gestion de l'incertitude des opérations géométriques, dans le cadre d'un calcul basé sur la norme IEEE arithmétique et la modélisation en surfaces de subdivision. Un algorithme pour le problème planar-cut est alors présenté qui a comme but de satisfaire à l'exigence topologique mentionnée ci-dessus.

Automates à contraintes semilinéaires = Automata with a semilinear constraint

Cette thèse présente une étude dans divers domaines de l'informatique théorique de modèles de calculs combinant automates finis et contraintes arithmétiques. Nous nous intéressons aux questions de décidabilité, d'expressivité et de clôture, tout en ouvrant l'étude à la complexité, la logique, l'algèbre et aux applications. Cette étude est présentée au travers de quatre articles de recherche. Le premier article, Affine Parikh Automata, poursuit l'étude de Klaedtke et Ruess des automates de Parikh et en définit des généralisations et restrictions. L'automate de Parikh est un point de départ de cette thèse; nous montrons que ce modèle de calcul est équivalent à l'automate contraint que nous définissons comme un automate qui n'accepte un mot que si le nombre de fois que chaque transition est empruntée répond à une contrainte arithmétique. Ce modèle est naturellement étendu à l'automate de Parikh affine qui effectue une opération affine sur un ensemble de registres lors du franchissement d'une transition. Nous étudions aussi l'automate de Parikh sur lettres: un automate qui n'accepte un mot que si le nombre de fois que chaque lettre y apparaît répond à une contrainte arithmétique. Le deuxième article, Bounded Parikh Automata, étudie les langages bornés des automates de Parikh. Un langage est borné s'il existe des mots w_1, w_2, ..., w_k tels que chaque mot du langage peut s'écrire w_1...w_1w_2...w_2...w_k...w_k. Ces langages sont importants dans des domaines applicatifs et présentent usuellement de bonnes propriétés théoriques. Nous montrons que dans le contexte des langages bornés, le déterminisme n'influence pas l'expressivité des automates de Parikh. Le troisième article, Unambiguous Constrained Automata, introduit les automates contraints non ambigus, c'est-à-dire pour lesquels il n'existe qu'un chemin acceptant par mot reconnu par l'automate. Nous montrons qu'il s'agit d'un modèle combinant une meilleure expressivité et de meilleures propriétés de clôture que l'automate contraint déterministe. Le problème de déterminer si le langage d'un automate contraint non ambigu est régulier est montré décidable. Le quatrième article, Algebra and Complexity Meet Contrained Automata, présente une étude des représentations algébriques qu'admettent les automates contraints et les automates de Parikh affines. Nous déduisons de ces caractérisations des résultats d'expressivité et de complexité. Nous montrons aussi que certaines hypothèses classiques en complexité computationelle sont reliées à des résultats de séparation et de non clôture dans les automates de Parikh affines. La thèse est conclue par une ouverture à un possible approfondissement, au travers d'un certain nombre de problèmes ouverts.