Combinations of Deformable Shape Prototypes

We propose to investigate a model-based technique for encoding non-rigid object classes in terms of object prototypes. Objects from the same class can be parameterized by identifying shape and appearance invariants of the class to devise low-level representations. The approach presented here creates a flexible model for an object class from a set of prototypes. This model is then used to estimate the parameters of low-level representation of novel objects as combinations of the prototype parameters. Variations in the object shape are modeled as non-rigid deformations. Appearance variations are modeled as intensity variations. In the training phase, the system is presented with several example prototype images. These prototype images are registered to a reference image by a finite element-based technique called Active Blobs. The deformations of the finite element model to register a prototype image with the reference image provide the shape description or shape vector for the prototype. The shape vector for each prototype, is then used to warp the prototype image onto the reference image and obtain the corresponding texture vector. The prototype texture vectors, being warped onto the same reference image have a pixel by pixel correspondence with each other and hence are "shape normalized". Given sufficient number of prototypes that exhibit appropriate in-class variations, the shape and the texture vectors define a linear prototype subspace that spans the object class. Each prototype is a vector in this subspace. The matching phase involves the estimation of a set of combination parameters for synthesis of the novel object by combining the prototype shape and texture vectors. The strengths of this technique lie in the combined estimation of both shape and appearance parameters. This is in contrast with the previous approaches where shape and appearance parameters were estimated separately.

Applied type system

We present a type system that can effectively facilitate the use of types in capturing invariants in stateful programs that may involve (sophisticated) pointer manipulation. With its root in a recently developed framework Applied Type System (ATS), the type system imposes a level of abstraction on program states by introducing a novel notion of recursive stateful views and then relies on a form of linear logic to reason about such views. We consider the design and then the formalization of the type system to constitute the primary contribution of the paper. In addition, we mention a prototype implementation of the type system and then give a variety of examples that attests to the practicality of programming with recursive stateful views.

View Registration Using Interesting Segments of Planar Trajectories

We introduce a method for recovering the spatial and temporal alignment between two or more views of objects moving over a ground plane. Existing approaches either assume that the streams are globally synchronized, so that only solving the spatial alignment is needed, or that the temporal misalignment is small enough so that exhaustive search can be performed. In contrast, our approach can recover both the spatial and temporal alignment. We compute for each trajectory a number of interesting segments, and we use their description to form putative matches between trajectories. Each pair of corresponding interesting segments induces a temporal alignment, and defines an interval of common support across two views of an object that is used to recover the spatial alignment. Interesting segments and their descriptors are defined using algebraic projective invariants measured along the trajectories. Similarity between interesting segments is computed taking into account the statistics of such invariants. Candidate alignment parameters are verified checking the consistency, in terms of the symmetric transfer error, of all the putative pairs of corresponding interesting segments. Experiments are conducted with two different sets of data, one with two views of an outdoor scene featuring moving people and cars, and one with four views of a laboratory sequence featuring moving radio-controlled cars.

Optic variables used to judge future ball arrival position in expert and novice soccer players

Although many studies have looked at the perceptual-cognitive strategies used to make anticipatory judgments in sport, few have examined the informational invariants that our visual system may be attuned to. Using immersive interactive virtual reality to simulate the aerodynamics of the trajectory of a ball with and without sidespin, the present study examined the ability of expert and novice soccer players to make judgments about the ball's future arrival position. An analysis of their judgment responses showed how participants were strongly influenced by the ball's trajectory. The changes in trajectory caused by sidespin led to erroneous predictions about the ball's future arrival position. An analysis of potential informational variables that could explain these results points to the use of a first-order compound variable combining optical expansion and optical displacement.

Detecting Deception in Movement: The Case of the Side-Step in Rugby

Although coordinated patterns of body movement can be used to communicate action intention, they can also be used to deceive. Often known as deceptive movements, these unpredictable patterns of body movement can give a competitive advantage to an attacker when trying to outwit a defender. In this particular study, we immersed novice and expert rugby players in an interactive virtual rugby environment to understand how the dynamics of deceptive body movement influence a defending player’s decisions about how and when to act. When asked to judge final running direction, expert players who were found to tune into prospective tau-based information specified in the dynamics of ‘honest’ movement signals (Centre of Mass), performed significantly better than novices who tuned into the dynamics of ‘deceptive’ movement signals (upper trunk yaw and out-foot placement) (p<.001). These findings were further corroborated in a second experiment where players were able to move as if to intercept or ‘tackle’ the virtual attacker. An analysis of action responses showed that experts waited significantly longer before initiating movement (p<.001). By waiting longer and picking up more information that would inform about future running direction these experts made significantly fewer errors (p<.05). In this paper we not only present a mathematical model that describes how deception in body-based movement is detected, but we also show how perceptual expertise is manifested in action expertise. We conclude that being able to tune into the ‘honest’ information specifying true running action intention gives a strong competitive advantage.

Algorithms for Self-Healing Networks

Many modern networks are \emph{reconfigurable}, in the sense that the topology of the network can be changed by the nodes in the network. For example, peer-to-peer, wireless and ad-hoc networks are reconfigurable. More generally, many social networks, such as a company's organizational chart; infrastructure networks, such as an airline's transportation network; and biological networks, such as the human brain, are also reconfigurable. Modern reconfigurable networks have a complexity unprecedented in the history of engineering, resembling more a dynamic and evolving living animal rather than a structure of steel designed from a blueprint. Unfortunately, our mathematical and algorithmic tools have not yet developed enough to handle this complexity and fully exploit the flexibility of these networks. We believe that it is no longer possible to build networks that are scalable and never have node failures. Instead, these networks should be able to admit small, and maybe, periodic failures and still recover like skin heals from a cut. This process, where the network can recover itself by maintaining key invariants in response to attack by a powerful adversary is what we call \emph{self-healing}. Here, we present several fast and provably good distributed algorithms for self-healing in reconfigurable dynamic networks. Each of these algorithms have different properties, a different set of gaurantees and limitations. We also discuss future directions and theoretical questions we would like to answer. %in the final dissertation that this document is proposed to lead to.

Self-healing systems and virtual structures

Modern networks are large, highly complex and dynamic. Add to that the mobility of the agents comprising many of these networks. It is difficult or even impossible for such systems to be managed centrally in an efficient manner. It is imperative for such systems to attain a degree of self-management. Self-healing i.e. the capability of a system in a good state to recover to another good state in face of an attack, is desirable for such systems. In this paper, we discuss the self-healing model for dynamic reconfigurable systems. In this model, an omniscient adversary inserts or deletes nodes from a network and the algorithm responds by adding a limited number of edges in order to maintain invariants of the network. We look at some of the results in this model and argue for their applicability and further extensions of the results and the model. We also look at some of the techniques we have used in our earlier work, in particular, we look at the idea of maintaining virtual graphs mapped over the existing network and assert that this may be a useful technique to use in many problem domains.

Resultados espectrais relacionados com a estrutura dos grafos

Nesta tese são estabelecidas novas propriedades espectrais de grafos com estruturas específicas, como sejam os grafos separados em cliques e independentes e grafos duplamente separados em independentes, ou ainda grafos com conjuntos (κ,τ)-regulares. Alguns invariantes dos grafos separados em cliques e independentes são estudados, tendo como objectivo limitar o maior valor próprio do espectro Laplaciano sem sinal. A técnica do valor próprio é aplicada para obter alguns majorantes e minorantes do índice do espectro Laplaciano sem sinal dos grafos separados em cliques e independentes bem como sobre o índice dos grafos duplamente separados em independentes. São fornecidos alguns resultados computacionais de modo a obter uma melhor percepção da qualidade desses mesmos extremos. Estudamos igualmente os grafos com um conjunto (κ,τ)-regular que induz uma estrela complementar para um valor próprio não-principal $. Além disso, é mostrado que $=κ-τ. Usando uma abordagem baseada nos grafos estrela complementares construímos, em alguns casos, os respectivos grafos maximais. Uma caracterização dos grafos separados em cliques e independentes que envolve o índice e as entradas do vector principal é apresentada tal como um majorante do número da estabilidade dum grafo conexo.

Laxity dynamics and LLF schedulability analysis on multiprocessor platforms

LLF (Least Laxity First) scheduling, which assigns a higher priority to a task with a smaller laxity, has been known as an optimal preemptive scheduling algorithm on a single processor platform. However, little work has been made to illuminate its characteristics upon multiprocessor platforms. In this paper, we identify the dynamics of laxity from the system’s viewpoint and translate the dynamics into LLF multiprocessor schedulability analysis. More specifically, we first characterize laxity properties under LLF scheduling, focusing on laxity dynamics associated with a deadline miss. These laxity dynamics describe a lower bound, which leads to the deadline miss, on the number of tasks of certain laxity values at certain time instants. This lower bound is significant because it represents invariants for highly dynamic system parameters (laxity values). Since the laxity of a task is dependent of the amount of interference of higher-priority tasks, we can then derive a set of conditions to check whether a given task system can go into the laxity dynamics towards a deadline miss. This way, to the author’s best knowledge, we propose the first LLF multiprocessor schedulability test based on its own laxity properties. We also develop an improved schedulability test that exploits slack values. We mathematically prove that the proposed LLF tests dominate the state-of-the-art EDZL tests. We also present simulation results to evaluate schedulability performance of both the original and improved LLF tests in a quantitative manner.

Quotients d'une variété algébrique par un groupe algébrique linéairement réductif et ses sous-groupes maximaux unipotents

La construction d'un quotient, en topologie, est relativement simple; si $G$ est un groupe topologique agissant sur un espace topologique $X$, on peut considérer l'application naturelle de $X$ dans $X/G$, l'espace d'orbites muni de la topologie quotient. En géométrie algébrique, malheureusement, il n'est généralement pas possible de munir l'espace d'orbites d'une structure de variété. Dans le cas de l'action d'un groupe linéairement réductif $G$ sur une variété projective $X$, la théorie géométrique des invariants nous permet toutefois de construire un morphisme de variété d'un ouvert $U$ de $X$ vers une variété projective $X//U$, se rapprochant autant que possible d'une application quotient, au sens topologique du terme. Considérons par exemple $X\subseteq P^{n}$, une $k$-variété projective sur laquelle agit un groupe linéairement réductif $G$ et supposons que cette action soit induite par une action linéaire de $G$ sur $A^{n+1}$. Soit $\widehat{X}\subseteq A^{n+1}$, le cône affine au dessus de $\X$. Par un théorème de la théorie classique des invariants, il existe alors des invariants homogènes $f_{1},...,f_{r}\in C[\widehat{X}]^{G}$ tels que $$C[\widehat{X}]^{G}= C[f_{1},...,f_{r}].$$ On appellera le nilcone, que l'on notera $N$, la sous-variété de $\X$ définie par le locus des invariants $f_{1},...,f_{r}$. Soit $Proj(C[\widehat{X}]^{G})$, le spectre projectif de l'anneau des invariants. L'application rationnelle $$\pi:X\dashrightarrow Proj(C[f_{1},...,f_{r}])$$ induite par l'inclusion de $C[\widehat{X}]^{G}$ dans $C[\widehat{X}]$ est alors surjective, constante sur les orbites et sépare les orbites autant qu'il est possible de le faire; plus précisément, chaque fibre contient exactement une orbite fermée. Pour obtenir une application régulière satisfaisant les mêmes propriétés, il est nécessaire de jeter les points du nilcone. On obtient alors l'application quotient $$\pi:X\backslash N\rightarrow Proj(C[f_{1},...,f_{r}]).$$ Le critère de Hilbert-Mumford, dû à Hilbert et repris par Mumford près d'un demi-siècle plus tard, permet de décrire $N$ sans connaître les $f_{1},...,f_{r}$. Ce critère est d'autant plus utile que les générateurs de l'anneau des invariants ne sont connus que dans certains cas particuliers. Malgré les applications concrètes de ce théorème en géométrie algébrique classique, les démonstrations que l'on en trouve dans la littérature sont généralement données dans le cadre peu accessible des schémas. L'objectif de ce mémoire sera, entre autres, de donner une démonstration de ce critère en utilisant autant que possible les outils de la géométrie algébrique classique et de l'algèbre commutative. La version que nous démontrerons est un peu plus générale que la version originale de Hilbert \cite{hilbert} et se retrouve, par exemple, dans \cite{kempf}. Notre preuve est valide sur $C$ mais pourrait être généralisée à un corps $k$ de caractéristique nulle, pas nécessairement algébriquement clos. Dans la seconde partie de ce mémoire, nous étudierons la relation entre la construction précédente et celle obtenue en incluant les covariants en plus des invariants. Nous démontrerons dans ce cas un critère analogue au critère de Hilbert-Mumford (Théorème 6.3.2). C'est un théorème de Brion pour lequel nous donnerons une version un peu plus générale. Cette version, de même qu'une preuve simplifiée d'un théorème de Grosshans (Théorème 6.1.7), sont les éléments de ce mémoire que l'on ne retrouve pas dans la littérature.

Le roman sentimental antillais : appropriation du canon et didactisme

Le roman sentimental est un des genres les plus lus, les plus traduits et les plus diffusés. Malgré sa mauvaise réputation, il est étonnant de constater le nombre de ces romans vendus, tous pays confondus. Dans les Antilles, ce phénomène est particulièrement palpable : la présence, et la réception de ces œuvres témoignent de l’engouement pour le genre. Notre étude a pour objectif de dégager d’un corpus sentimental antillais les aspects les plus significatifs. Nous analyserons, d’une part, le schéma narratif élaboré en marge de celui proposé par le roman sentimental classique et, d’autre part, l’esthétique du quotidien mise en place pour créer un sentiment d’appartenance chez le lectorat. Il nous sera ainsi possible de mettre en évidence le discours socioculturel propre à ce genre et plus spécifiquement aux femmes antillaises. Par ailleurs, cette recherche postule que l'appropriation des invariants romanesques et l'élaboration d'une visée didactique participent à l'intégration du roman sentimental antillais dans la sphère des littératures « sérieuses ». Enfin, ce mémoire défend l’idée selon laquelle l’écriture romanesque des auteures étudiées contribue au projet littéraire antillais de réappropriation identitaire.

Classification analytique de systèmes différentiels linéaires déployant une singularité irrégulière de rang de Poincaré 1

Cette thèse traite de la classification analytique du déploiement de systèmes différentiels linéaires ayant une singularité irrégulière. Elle est composée de deux articles sur le sujet: le premier présente des résultats obtenus lors de l'étude de la confluence de l'équation hypergéométrique et peut être considéré comme un cas particulier du second; le deuxième contient les théorèmes et résultats principaux. Dans les deux articles, nous considérons la confluence de deux points singuliers réguliers en un point singulier irrégulier et nous étudions les conséquences de la divergence des solutions au point singulier irrégulier sur le comportement des solutions du système déployé. Pour ce faire, nous recouvrons un voisinage de l'origine (de manière ramifiée) dans l'espace du paramètre de déploiement $\epsilon$. La monodromie d'une base de solutions bien choisie est directement reliée aux matrices de Stokes déployées. Ces dernières donnent une interprétation géométrique aux matrices de Stokes, incluant le lien (existant au moins pour les cas génériques) entre la divergence des solutions à $\epsilon=0$ et la présence de solutions logarithmiques autour des points singuliers réguliers lors de la résonance. La monodromie d'intégrales premières de systèmes de Riccati correspondants est aussi interprétée en fonction des éléments des matrices de Stokes déployées. De plus, dans le second article, nous donnons le système complet d'invariants analytiques pour le déploiement de systèmes différentiels linéaires $x^2y'=A(x)y$ ayant une singularité irrégulière de rang de Poincaré $1$ à l'origine au-dessus d'un voisinage fixé $\mathbb{D}_r$ dans la variable $x$. Ce système est constitué d'une partie formelle, donnée par des polynômes, et d'une partie analytique, donnée par une classe d'équivalence de matrices de Stokes déployées. Pour chaque valeur du paramètre $\epsilon$ dans un secteur pointé à l'origine d'ouverture plus grande que $2\pi$, nous recouvrons l'espace de la variable, $\mathbb{D}_r$, avec deux secteurs et, au-dessus de chacun, nous choisissons une base de solutions du système déployé. Cette base sert à définir les matrices de Stokes déployées. Finalement, nous prouvons un théorème de réalisation des invariants qui satisfont une condition nécessaire et suffisante, identifiant ainsi l'ensemble des modules.

Continuité et métamorphoses du surréalisme bruxellois : la poétique de l’illisible chez Christian Dotremont

Cette thèse pose la question de la fortune remarquable du surréalisme en Belgique et porte particulièrement attention à la poétique de Christian Dotremont qui, après une période surréaliste, trace le premier logogramme en 1962. La partie initiale de notre recherche interroge ses rapports avec le groupe surréaliste bruxellois (Paul Nougé et René Magritte), préoccupé par le refus de l’œuvre. Cette démarche subversive se transforme dans l’art expérimental du groupe Cobra (communauté artistique fondée en 1948 par Dotremont). Nous nous intéressons à cette évolution d’une préoccupation logocentrique (où le mot compte pour le contenu qu’il véhicule : il s’agit de la poétique « primitive » de Nougé et des objets bouleversants de Magritte) vers l’exploration du mot comme trace, comme scription et, par là même, comme source de poésie. La deuxième partie de notre recherche traite de l’époque Cobra où se forge ce que nous appelons la poétique du visible chez Dotremont dont le résultat est la découverte du pouvoir créatif du mot en tant que matière, en tant que trace manuscrite. Ces expérimentations centrées sur la matérialité du langage préparent le cheminement artistique de Dotremont vers l’invention du logogramme (objet d’analyse de la troisième partie de la thèse). Dans l’idée d’une légitimation du logogramme en tant que nouveau genre poético-pictural, nous relevons ses invariants créateurs : sans pour autant se soumettre au modèle pictural, celui-ci n’est ni peinture des mots, ni mot-tableau, il exploite la matérialité de la lettre comme source poétique : genre transfrontalier qui ne cesse de mettre en question et d’inclure dans sa cinétique la métamorphose de sa réception.

Aspects géométriques et intégrables des modèles de matrices aléatoires

Travail réalisé en cotutelle avec l'université Paris-Diderot et le Commissariat à l'Energie Atomique sous la direction de John Harnad et Bertrand Eynard.

Trois essais en économie des ressources naturelles

Cette thèse est composée de trois articles en économie des ressources naturelles non-renouvelables. Nous considérons tour à tour les questions suivantes : le prix in-situ des ressources naturelles non-renouvelables ; le taux d’extraction optimal et le prix des res- sources non-renouvelables et durables. Dans le premier article, nous estimons le prix in-situ des ressources naturelles non-renouvelables en utilisant les données sur le coût moyen d’extraction pour obtenir une approximation du coût marginal. En utilisant la Méthode des Moments Généralisés, une dynamique du prix de marché derivée des conditions d’optimalité du modèle d’Hotelling est estimée avec des données de panel de 14 ressources naturelles non-renouvelables. Nous trouvons des résultats qui tendent à soutenir le modèle. Premièrement, le modèle d’Hotelling exhibe un bon pouvoir explicatif du prix de marché observé. Deuxièmement, bien que le prix estimé présente un changement structurel dans le temps, ceci semble n’avoir aucun impact significatif sur le pouvoir explicatif du modèle. Troisièmement, on ne peut pas rejeter l’hypothèse que le coût marginal d’extraction puisse être approximé par les données sur le coût moyen. Quatrièmement, le prix in-situ estimé en prenant en compte les changements structurels décroît ou exhibe une forme en U inversé dans le temps et semble être corrélé positivement avec le prix de marché. Cinquièmement, pour neuf des quatorze ressources, la différence entre le prix in-situ estimé avec changements structurels et celui estimé en négligeant les changements structurels est un processus de moyenne nulle. Dans le deuxième article, nous testons l’existence d’un équilibre dans lequel le taux d’extraction optimal des ressources non-renouvelables est linéaire par rapport au stock de ressource en terre. Tout d’abord, nous considérons un modèle d’Hotelling avec une fonction de demande variant dans le temps caractérisée par une élasticité prix constante et une fonction de coût d’extraction variant dans le temps caractérisée par des élasticités constantes par rapport au taux d’extraction et au stock de ressource. Ensuite, nous mon- trons qu’il existe un équilibre dans lequel le taux d’extraction optimal est proportionnel au stock de ressource si et seulement si le taux d’actualisation et les paramètres des fonctions de demande et de coût d’extraction satisfont une relation bien précise. Enfin, nous utilisons les données de panel de quatorze ressources non-renouvelables pour vérifier empiriquement cette relation. Dans le cas où les paramètres du modèle sont supposés invariants dans le temps, nous trouvons qu’on ne peut rejeter la relation que pour six des quatorze ressources. Cependant, ce résultat change lorsque nous prenons en compte le changement structurel dans le temps des prix des ressources. En fait, dans ce cas nous trouvons que la relation est rejetée pour toutes les quatorze ressources. Dans le troisième article, nous étudions l’évolution du prix d’une ressource naturelle non-renouvelable dans le cas où cette ressource est durable, c’est-à-dire qu’une fois extraite elle devient un actif productif détenu hors terre. On emprunte à la théorie de la détermination du prix des actifs pour ce faire. Le choix de portefeuille porte alors sur les actifs suivant : un stock de ressource non-renouvelable détenu en terre, qui ne procure aucun service productif ; un stock de ressource détenu hors terre, qui procure un flux de services productifs ; un stock d’un bien composite, qui peut être détenu soit sous forme de capital productif, soit sous forme d’une obligation dont le rendement est donné. Les productivités du secteur de production du bien composite et du secteur de l’extraction de la ressource évoluent de façon stochastique. On montre que la prédiction que l’on peut tirer quant au sentier de prix de la ressource diffère considérablement de celle qui découle de la règle d’Hotelling élémentaire et qu’aucune prédiction non ambiguë quant au comportement du sentier de prix ne peut être obtenue de façon analytique.