Les travaux présentés dans le cadre de cette habilitation à diriger des recherches portent essentiellement sur l'analyse de scènes à partir de caméras mobiles avec pour application immédiate l'apport d'une vision par ordinateur efficace dans les systèmes d'aide à la conduite. L'idée initiale est que l'autonomie d'un système implique, ne serait-ce que pour raisons énergétiques, une faible variété d'opérateurs de perception, dont les algorithmes de vision. Les "primitives" extraites des images seront intrinsèquement robustes et stables vis-à-vis de perturbations variées. Elles doivent de plus anticiper, voire faciliter, un processus de décision à divers niveaux voulu systématique. Les lignes de niveaux répondent parfaitement à ces contraintes : on vérifie sans peine leur robustesse et leur abondance dans une image suggère et alimente un processus de décision cumulatif (manipulant un objet unique : l'histogramme). Nos efforts se sont alors concentrés sur deux aspects : 1) le premier concerne la définition d'une méthodologie cohérente dans laquelle un processus primaire d'extraction de lignes de niveaux est enrichi afin de permettre la construction de primitives plus complexes guidée par le modèle de déformation de l'image. Le nombre de composants donc la forme des primitives est fonction directe du nombre de variables caractérisant le mouvement (déformation) à déterminer. 2) Le second intéresse une méthode de décision cumulative unifiée permettant de traiter des thèmes applicatifs de complexité croissante. Nos travaux se déclinent alors en trois niveaux de cumul, chacun associé de manière réconfortante à un stade de l'analyse d'images. 1) Au plus bas niveau, nous retenons l'information binaire apparition/disparition d'une primitive dans le temps. La complexité se situe strictement sur l'axe temporel. Le cumul dans le temps nous permet ainsi de reconstruire la scène fixe et donc par soustraction du fond, l'image des objets mobiles. Les espaces de vote sont 1D et multiples, affectés à chaque primitive. 2) Le consensus se voudrait spatio-temporel au deuxième niveau pour identifier le mouvement. Il restera d'abord spatial en pratique pour raisons de complexité : des primitives voisines dans l'image s'associent pour former des "pré-objets" contraints exhibant ainsi des invariants exploitables : leur mouvement à instancier doit être cohérent. Le cumul s'opère donc cette fois selon un modèle de mouvement de la caméra. Les primitives votent pour la transformation globale qui les aurait conduites dans leur nouvelle position. L'espace de vote est commun à toutes les primitives et multidimensionnel (une dimension par paramètre de mouvement). 3) Au niveau le plus élevé, la sémantique accrue implique des hypothèses à la fois sur les primitives et sur l'origine du mouvement. Les primitives sont supposées appartenir à un même objet 3D (ex. un plan) présentant, pour un modèle de déplacement du capteur donné, une propriété caractéristique commune des vecteurs vitesse qui permet de l'extraire. Notamment, leurs amplitudes sont constantes le long de courbes image prédéfinies par leurs équations analytiques. Les primitives ne votent plus selon leur structure mais selon leur vitesse. Dans le cas d'une scène 3D approximée par un ensemble de plans et d'une caméra à mouvement majoritairement longitudinal, l'espace de vote (c-velocité) présente 2 dimensions : une pour la vitesse, l'autre pour le paramètre des courbes iso-vitesse. Chaque vitesse vote sur sa courbe. Les surfaces 3D émergent dans cet espace de vote comme courbes 2D connues (droites ou paraboles). Les thèmes applicatifs traités pour illustrer notre démarche sont de complexité croissante : détection et estimation du mouvement en caméra fixe, recalage d'images en caméra mobile (type de mouvement connu et profondeur des objets contrainte) puis estimation générale du mouvement propre et de la structure de la scène en caméras embarquées sur un véhicule mobile. Les résultats obtenus montrent comment un choix de primitives robustes associé à un processus de décision cumulatif permet la réutilisation des opérateurs dans tous les secteurs. Les systèmes proposés ont la particularité d'être compacts et cohérents, propriété recherchée dans les applications considérées.

Cette thèse s'intègre dans le processus qui conduit de l'acquisition numérique 3D à<br />la réalisation de maquettes virtuelles destinées à l'architecture et à l'archéologie.<br />Elle débute par l'étude des techniques d'acquisition 3D utilisées, la lasergrammétrie<br />et la photogrammétrie architecturale, et se poursuit par une analyse comparative<br />détaillée de ces dispositifs, basée sur de multiples expérimentations réalisées sur le<br />terrain lors de la collaboration entre le Map-Crai et le Map-Page.<br />Ensuite une réflexion sur la morphologie architecturale est abordée autour de ses<br />variantes typologiques et architectoniques, suivie par les questions théoriques<br />soulevées par la modélisation 3D et plus spécifiquement la modélisation<br />architecturale.<br />Diverses expérimentations sont ensuite présentées, elles constituent le support<br />d'une réflexion sur le développement d'outils numériques destinés à faciliter la<br />modélisation géométrique architecturale. La principale contribution de cette thèse<br />correspond à l'association de cette réflexion empirique à une approche analytique<br />fondée sur nos connaissances théoriques en architecture, qui aboutit à l'identification<br />de primitives géométriques contraintes, les moulures. Les outils numériques ainsi<br />développés dans un logiciel de CAO définissent ces primitives géométriques<br />ajustables dont le champ d'application initial, spécifique à l'architecture classique,<br />sera étendu à l'architecture khmère.<br />Enfin une proposition plus évoluée correspondant à la téléologie de cette thèse,<br />obtenir de façon efficace un résultat conforme au cahier des charges de la<br />modélisation architecturale et archéologique, est intégrée dans un logiciel de<br />synthèse d'image.

A aplicação de técnicas baseadas em amostragem em algoritmos que envolvem o planejamento de trajetórias de robôs tem se tornado cada vez mais difundida. Deste grupo, um dos algoritmos mais utilizados é chamado Rapidly-exploring Random Tree (RRT), que se baseia na amostragem incremental para calcular de forma eficiente os planos de trajetória do robô evitando colisões com obstáculos. Vários esforços tem sido realizados a fim de reduzir o custo computacional do algoritmo RRT, visando aplicações que necessitem de respostas mais rápidas do algoritmo, como, por exemplo, em ambientes dinâmicos. Um dos dilemas relacionados ao RRT está na etapa de geração de primitivas de movimento. Se várias primitivas são geradas, permitindo o robô executar vários movimentos básicos diferentes, um grande custo computacional é gasto. Por outro lado, quando poucas primitivas são geradas e, consequentemente, poucos movimentos básicos são permitidos, o robô pode não ser capaz de encontrar uma solução para o problema, mesmo que esta exista. Motivados por este problema, um método de geração de primitivas de movimento foi proposto. Tal método é comparado com os métodos tradicional e aleatório de geração de primitivas, considerando não apenas o custo computacional de cada um, mas também a qualidade da solução obtida. O método proposto é aplicado ao algoritmo RRT, que depois é aplicado em um caso de estudo em um ambiente dinâmico. No estudo de caso, o algoritmo RRT otimizado é avaliado em termos de seus custos computacionais durante planejamentos e replanejamento de trajetória. As simulações são realizadas em dois simuladores: um desenvolvido em linguagem Python e outro em Matlab. / The application of sample-based techniques in path-planning algorithms has become year-by-year more widespread. In this group, one of the most widely used algorithms is the Rapidly-exploring Random Tree (RRT), which is based on an incremental sampling of configurations to efficiently compute the robot\'s path while avoiding obstacles. Many efforts have been made to reduce RRT computational costs, targeting, in particular, applications in which quick responses are required, e.g., in dynamic environments. One of the dilemmas posed by the RRT arises from its motion primitives generation. If many primitives are generated to enable the robot to perform a broad range of basic movements, a signicant computational cost is required. On the other hand, when only a few primitives are generated, thus, enabling a limited number of basic movements, the robot may be unable to find a solution to the problem, even if one exists. To address this quandary, an optimized method for primitive generation is proposed. This method is compared with the traditional and random primitive generation methods, considering not only computational cost, but also the quality of local and global solutions that may be attained. The optimized method is applied to the RRT algorithm, which is then used in a case study in dynamic environments. In the study, the modied RRT is evaluated in terms of the computational costs of its planning and replanning. The simulations were developed to access the effectiveness and efficiency of the proposed algorithm.

Nous proposons dans cette thèse une nouvelle approche cumulative de recalage d'images basée sur des primitives construites à partir des lignes de niveaux. Les lignes de niveaux sont invariantes par rapport aux diverses perturbations affectant l'image tels que les changements de contraste. Par ailleurs, leur abondance dans une image suggère naturellement un processus de décision cumulatif. Nous proposons alors un algorithme récursif d'extraction des lignes de niveaux simple et efficace qui extrait les lignes par groupes rectiligne appelés ``segments''. Les segments sont ensuite groupés -- sous contrainte de proximité -- en fonction du modèle de transformation recherchée et afin de faciliter le calcul des invariants. Les primitives construites ont alors la forme de Z, Y ou W et sont classées en fonction de leur fiabilité, ce qui participe au paramétrage du processus de décision cumulatif. Le vote est multi-tours et constitué d'une phase préliminaire de construction de listes de préférences inspiré de la technique des mariages stables. Les primitives votent à une itération donnée en fonction de leur fiabilité. Chaque itération fournit ainsi un estimé de la transformation recherchée que le tour suivant peut raffiner. Ce procédé multi-tours permet, de ce fait, d'éliminer les ambiguïtés d'appariement générées par les motifs répétitifs présents dans les images. Notre approche a été validée pour recaler des images sous différents modèles de transformations allant de la plus simple (similarité) à la plus complexe (projective). Nous montrons dans cette thèse comment le choix pertinent de primitives basées sur les lignes de niveaux en conjonction avec un processus de décision cumulatif permet d'obtenir une méthode de recalage d'images robuste, générique et complète, fournissant alors différents niveaux de précision et pouvant ainsi s'appliquer à différents contextes. / In this thesis, we propose a new image registration method that relies on level-line primitives. Level-lines are robust towards contrast changes and proposed primitives inherit their robustness. Moreover, their abundance in the image is well adapted to a cumulative matching process based on a multi-stage primitive election procedure. We propose a simple recursive tracking algorithm to extract level lines by straight sets called "segments". Segments are then grouped under proximity constraints to construct primitives (Z, Y and W shapes) that are classified into categories according to their reliability. Primitive shapes are defined according to the transformation model. The cumulative process is based on a preliminary step of preference lists construction that is inspired from the stable marriage matching algorithm. Primitives vote in a given voting stage according to their reliability. Each stage provides a coarse estimate of the transformation that the next stage gets to refine. This process, in turn, eliminate gradually the ambiguity happened by incorrect correspondences. Our additional contribution is to validate further geometric transformations, from simple to complex ones, completing the path "similarity, affine, projective". We show in this thesis how the choice of level lines in conjunction with a cumulative decision process allows defining a complete robust registration approach that is tested and evaluated on several real image sequences including different type of transformations.

A aplicação de técnicas baseadas em amostragem em algoritmos que envolvem o planejamento de trajetórias de robôs tem se tornado cada vez mais difundida. Deste grupo, um dos algoritmos mais utilizados é chamado Rapidly-exploring Random Tree (RRT), que se baseia na amostragem incremental para calcular de forma eficiente os planos de trajetória do robô evitando colisões com obstáculos. Vários esforços tem sido realizados a fim de reduzir o custo computacional do algoritmo RRT, visando aplicações que necessitem de respostas mais rápidas do algoritmo, como, por exemplo, em ambientes dinâmicos. Um dos dilemas relacionados ao RRT está na etapa de geração de primitivas de movimento. Se várias primitivas são geradas, permitindo o robô executar vários movimentos básicos diferentes, um grande custo computacional é gasto. Por outro lado, quando poucas primitivas são geradas e, consequentemente, poucos movimentos básicos são permitidos, o robô pode não ser capaz de encontrar uma solução para o problema, mesmo que esta exista. Motivados por este problema, um método de geração de primitivas de movimento foi proposto. Tal método é comparado com os métodos tradicional e aleatório de geração de primitivas, considerando não apenas o custo computacional de cada um, mas também a qualidade da solução obtida. O método proposto é aplicado ao algoritmo RRT, que depois é aplicado em um caso de estudo em um ambiente dinâmico. No estudo de caso, o algoritmo RRT otimizado é avaliado em termos de seus custos computacionais durante planejamentos e replanejamento de trajetória. As simulações são realizadas em dois simuladores: um desenvolvido em linguagem Python e outro em Matlab. / The application of sample-based techniques in path-planning algorithms has become year-by-year more widespread. In this group, one of the most widely used algorithms is the Rapidly-exploring Random Tree (RRT), which is based on an incremental sampling of configurations to efficiently compute the robot\'s path while avoiding obstacles. Many efforts have been made to reduce RRT computational costs, targeting, in particular, applications in which quick responses are required, e.g., in dynamic environments. One of the dilemmas posed by the RRT arises from its motion primitives generation. If many primitives are generated to enable the robot to perform a broad range of basic movements, a signicant computational cost is required. On the other hand, when only a few primitives are generated, thus, enabling a limited number of basic movements, the robot may be unable to find a solution to the problem, even if one exists. To address this quandary, an optimized method for primitive generation is proposed. This method is compared with the traditional and random primitive generation methods, considering not only computational cost, but also the quality of local and global solutions that may be attained. The optimized method is applied to the RRT algorithm, which is then used in a case study in dynamic environments. In the study, the modied RRT is evaluated in terms of the computational costs of its planning and replanning. The simulations were developed to access the effectiveness and efficiency of the proposed algorithm.

Dans ce travail, on étudie quelques problèmes d'équations aux dérivées partielles elliptiques que l'on rencontre dans la modélisation d'écoulements réels, comme par exemple la circulation océanique globale. La thèse est divisée en trois parties. La partie 1 est consacrée à l'étude du problème de Stokes dit « hydrostatique » en dimension trois posé dans un domaine borné non nécessairement cylindrique. L'originalité de ces travaux provient du fait que l'on considère des données non homogènes, tant dans l'équation de conservation de la masse que sur la condition aux limites portée sur la vitesse verticale. Pour traiter cette nouvelle situation, on se ramène par équivalence à résoudre un système d'équations primitives linéarisées non homogènes, que l'on résout avec une approche entièrement fonctionnelle et optimale grâce au cadre fonctionnel que l'on considère. Par conséquent, on montre deux cas d'existence et d'unicité d'une solution faible au problème de Stokes hydrostatique avec conditions non homogènes. Les partie 2 et 3 sont consacrées à l'étude d'un modèle elliptique avec un coefficient de diffusion qui peut dégénérer. Ce type d'équations intervient également dans des problèmes géophysiques, que ce soit dans des questions de modélisation de circulation globale, mais aussi dans des problèmes d'infiltration et de milieux poreux. On étudie le cas du demi-espace pour lequel on obtient une théorie optimale de régularité des solutions faibles. On traite enfin le cas général pour lequel on obtient un cas d'existence et d'unicité de solution faible et un résultat de régularité associé.

Réalisation d'un outil de base pour la mise en œuvre des systèmes relationnels. Présentation du projet MICROBE, visant à l'implantation d'un SGBD relationnel sur micro-ordinateurs. Aperçu sur l'état de l'art en matière de mémoires relationnelles. Etude des methodes d'accès aux données, en particulier la methode des B*-arbres.

Ce travail s'insère dans un projet global de modélisation de scènes urbaines à partir d'images satellitaires très haute résolution. Le projet a été proposé dans le cadre d'une collaboration entre l'IGN et le CNES et l'université de Paris 5. L'objectif final du projet sera de fournir un système automatique permettant de classifier la scène en deux thèmes ; bâti et routes et de reconstruire les bâtiments en 3D. Dans le cadre de cette thèse, on s'intéresse uniquement à la modélisation des bâtiments. <br />On dispose en entrée de couples stéréoscopiques panchromatiques à [50-70 cm] de résolution et de faible rapport Base sur Hauteur B/H [0.05-0.2]. On exclut la multiscopie.<br />Étant donnée la complexité d'une extraction fine et détaillée des toits en contexte satellitaire, on propose de modéliser la scène urbaine par une surface 3D hybride fournissant différents niveaux de description en fonction de la fiabilité des primitives extraites : points 3D, segments 3D et surfaces planes. <br />Une stratégie mixte a été adoptée. Tout d'abord, une stratégie ascendante basée sur les images permet d'extraire les primitives 3D (segments 3D et facettes 3D). Deux stratégies complémentaires d'extractions de primitives seront détaillées. Une description multi-échelles est utilisée pour la segmentation des images. Notre apport consiste essentiellement dans l'appariement global de deux segmentations multi-échelles du couple stéréoscopique.<br /><br />L'ensemble des primitives sera validé par une approche descendante et permettra de contraindre la modélisation de la surface 3D.<br />Le problème de modélisation de surface 3D peut être formulé comme un problème de minimisation d'énergie. Il sera résolu par optimisation à base de flots de graphes, contrainte par les primitives 3D. Le graphe 3D hybride sera construit à partir d'un volume de corrélation sur la scène 3D et des primitives 3D extraites. La surface finale est obtenue par recherche de la coupe de capacité minimale dans ce graphe 3D.<br /> La majeure contribution de notre approche consiste à utiliser des primitives 3D extraites et des données externes telles que le réseau routier ou les plans cadastraux pour contraindre le problème d'optimisation et modéliser de manière explicite les occultations et les discontinuités.<br />Le produit final, sera un Modèle Numérique d'Élévation hybride « raster/vecteur », permettant d'exploiter à chaque endroit de la scène, les primitives du niveau le plus élevé que l'on a pu reconstruire de manière fiable.<br /><br />Mots-clés : images satellitaires haute résolution, stéréoscopie, Modèle Numérique d'Élévation, primitives 3D, mise en correspondance de régions, appariement multi-échelles, optimisation à base de flots de graphes.

Dans ce travail nous nous sommes intéressés à des problèmes de modélisation et d'assimilation de données en océanographie, tant d'un point de vue théorique que numérique. L'étude de l'océan est cruciale pour de nombreuses raisons (changement climatique, météorologie, navigation commerciale et militaire, etc.). Dans une première partie nous étudions les équations primitives linéaires tridimensionnelles de l'océan, et nous donnons des résultats nouveaux de régularité en calculant explicitement le terme de pression. Dans une deuxième partie nous étudions l'assimilation variationnelle de données lagrangiennes dans un modèle d'océan. L'assimilation de données est l'ensemble des méthodes qui permettent de combiner de façon optimale, en vue d'effectuer des prévisions, deux sortes d'informations disponibles sur un système physique : les observations d'une part et les équations du modèle d'autre part. Nous utilisons une méthode variationnelle pour assimiler des données lagrangiennes, à savoir les positions de flotteurs dérivant dans l'océan. Nous commençons par établir de nouvelles estimations a priori pour les équations primitives afin d'étudier le problème théorique de contrôle optimal associé. Puis nous décrivons l'implémentation de la méthode variationnelle dans un modèle réaliste d'océan aux équations primitives. Enfin nous effectuons de nombreuses expériences numériques et notamment plusieurs études de sensibilité, qui montrent que l'assimilation de données lagrangiennes est techniquement réalisable et pertinente d'un point de vue océanographique.

CertiCrypt est une bibliothèque qui permet de vérifier la sécurité exacte de primitives cryptographiques dans l'assistant à la preuve Coq. CertiCrypt instrumente l'approche des preuves par jeux, et repose sur de nombreux domaines comme les probabilités, la complexité, l'algèbre, la sémantique des langages de programmation, et les optimisations de programmes. Dans cette thèse, nous présentons deux exemples d'utilisation d'EasyCrypt: le schéma d'encryption Hashed ElGamal, et les protocoles à connaissance nulle. Ces exemples, ainsi que les travaux antérieurs sur CertiCrypt, démontrent qu'il est possible de formaliser des preuves complexes; toutefois, l'utilisation de CertiCrypt demande une bonne expertise en Coq, et demeure laborieuse. Afin de faciliter l'adoption des preuves formelles par la communauté cryptographique, nous avons développé EasyCrypt, un outil semi-automatique capable de reconstruire des preuves formelles de sécurité à partir d'une ébauche formelle de preuve. EasyCrypt utilise des outils de preuves automatiques pour vérifier les ébauches de preuves, puis les compiles vers des preuves vérifiables avec CertiCrypt. Nous validons EasyCrypt en prouvant à nouveau Hashed ElGamal, et comparons cette nouvelle preuve avec celle en CertiCrypt. Nous prouvons également le schéma d'encryption Cramer-Shoup. Enfin, nous expliquerons comment étendre le langage de CertiCrypt à des classes de complexité implicite, permettant de modéliser la notion de fonctions en temps polynomial.