La solution la plus commune pour résoudre les problèmes de précision liés aux arithmétiques des ordinateurs est l'utilisation d'arithmétiques exactes. Nous proposons dans la première partie de cette thèse une optimisation très puissante des arithmétiques rationnelles : l'arithmétique rationnelle paresseuse. L'originalité de cette arithmétique est de retarder les calculs exacts jusqu'à ce qu'ils deviennent soit inutiles, soit inévitables. Ainsi les calculs exacts qui ne sont pas nécessaires ne sont jamais faits. L'arithmétique paresseuse se présente sous la forme d'une bibliothèque autonome prenant à sa charge les problèmes de précision et qui est indépendante des programmes qui l'utilisent. La deuxième partie de cette thèse présente un outil de modélisation dont le principal intérêt est d'utiliser l'image des objets comme support à leur modélisation sous forme d'arbre de construction. Cet outil est interactif, l'utilisateur pourra de cette manière ne modéliser que ce dont il a besoin et avec le niveau de détails le plus adapté à ses applications. Les extensions que nous proposons dans le domaine de l'incrustation d'images de synthèse dans des images naturelles permettent de traiter correctement l'ombrage de la scène finale en tenant compte de la nature des éclairages, des ombres portées et des reflets.

La résolution de l'éclairement global d'une scène par le trace de rayons implique l'élaboration de méthodes de Monté Carlo adaptées à la complexité de l'équation de rendu. Nous proposons une méthode de résolution globale et adaptative un trace de chemin spectral partant de l'il basée sur un échantillonnage d'importance permettant d'augmenter la vitesse de convergence de la résolution. Notre méthode consiste à mimer les variations de la luminance réfléchie en tenant compte de la fonction de réflectance bidirectionnelle et des caractéristiques des sources. Ce premier échantillonnage a priori est progressivement modifie par un schéma a posteriori s'adaptant à la luminance réellement réfléchie à mesure qu'elle est connue. Le deuxième aspect de nos travaux porte sur la génération des points de l'écran afin de ne calculer que ceux qui sont nécessaires à une qualité d'image donnée. Nous proposons une technique progressive basée sur une notion d'homogénéité visuelle locale de l'image. Cette homogénéité est testée à l'aide d'un procède statistique puissant utilisant l'analyse séquentielle. Notre méthode permet souvent des gains en temps de calcul très substantiels pour une bonne qualité d'image. L'ensemble de nos travaux a été inspire par la notion de réalisme. Nous montrons que le photoréalisme est insuffisant au contrôle d'une image et proposons des pistes de réflexion pour ce concept trop peu aborde en synthèse d'images

Les codes correcteurs d'erreurs sont une composante essentielle de tout système de communication, capables d’assurer le transport fiable de l’information sur un canal de communication bruité. Les systèmes de communication de nouvelle génération devront faire face à une demande sans cesse croissante en termes de débit binaire, pouvant aller de 1 à plusieurs centaines de gigabits par seconde. Dans ce contexte, les codes LDPC (pour Low-Density Parity-Check, en anglais), sont reconnus comme une des solutions les mieux adaptées, en raison de la possibilité de paralléliser massivement leurs algorithmes de décodage et les architectures matérielles associées. Cependant, si l’utilisation d’architectures massivement parallèles permet en effet d’atteindre des débits très élevés, cette solution entraine également une augmentation significative du coût matériel.L’objectif de cette thèse est de proposer des implémentations matérielles de décodeurs LDPC très haut débit, en exploitant la robustesse des algorithmes de décodage par passage de messages aux imprécisions de calcul. L’intégration dans le décodage itératif de mécanismes de calcul imprécis, s’accompagne du développement de nouvelles approches d’optimisation du design en termes de coût, débit et capacité de correction.Pour ce faire, nous avons considéré l’optimisation conjointe de (i) le bloc de quantification qui fournit l'information à précision finie au décodeur, et (ii) les unités de traitement imprécis des données, pour la mise à jour des messages échangés pendant de processus de décodage. Ainsi, nous avons tout d’abord proposé un quantificateur à faible complexité, qui peut être optimisé par évolution de densité en fonction du code LDPC utilisé et capable d’approcher de très près les performances d’un quantificateur optimal. Le quantificateur proposé a été en outre optimisé et utilisé pour chacun des décodeurs imprécis proposés ensuite dans cette thèse.Nous avons ensuite proposé, analysé et implémenté plusieurs décodeurs LDPC imprécis. Les deux premiers décodeurs sont des versions imprécises du décodeur « Offset Min-Sum » (OMS) : la surestimation des messages des nœuds de contrôle est d’abord compensée par un simple effacement du bit de poids faible (« Partially OMS »), ensuite le coût matériel est d’avantage réduit en supprimant un signal spécifique (« Imprecise Partially OMS »). Les résultats d’implémentation sur cible FPGA montrent une réduction importante du coût matériel, tout en assurant une performance de décodage très proche du OMS, malgré l'imprécision introduite dans les unités de traitement.Nous avions ensuite introduit les décodeurs à alphabet fini non-surjectifs (NS-FAIDs, pour « Non-Surjective Finite Alphabet Iterative Decoders », en anglais), qui étendent le concept d’« imprécision » au bloc mémoire du décodeur LDPC. Les décodeurs NS-FAIDs ont été optimisés par évolution de densité pour des codes LDPC réguliers et irréguliers. Les résultats d'optimisation révèlent différents compromis possibles entre la performance de décodage et l'efficacité de la mise en œuvre matérielle. Nous avons également proposé trois architectures matérielles haut débit, intégrant les noyaux de décodage NS-FAID. Les résultats d’implémentation sur cible FPGA et ASIC montrent que les NS-FAIDs permettent d’obtenir des améliorations significatives en termes de coût matériel et de débit, par rapport au décodeur Min-Sum, avec des performances de décodage meilleures ou très légèrement dégradées. / The increasing demand of massive data rates in wireless communication systems will require significantly higher processing speed of the baseband signal, as compared to conventional solutions. This is especially challenging for Forward Error Correction (FEC) mechanisms, since FEC decoding is one of the most computationally intensive baseband processing tasks, consuming a large amount of hardware resources and energy. The conventional approach to increase throughput is to use massively parallel architectures. In this context, Low-Density Parity-Check (LDPC) codes are recognized as the foremost solution, due to the intrinsic capacity of their decoders to accommodate various degrees of parallelism. They have found extensive applications in modern communication systems, due to their excellent decoding performance, high throughput capabilities, and power efficiency, and have been adopted in several recent communication standards.This thesis focuses on cost-effective, high-throughput hardware implementations of LDPC decoders, through exploiting the robustness of message-passing decoding algorithms to computing inaccuracies. It aims at providing new approaches to cost/throughput optimizations, through the use of imprecise computing and storage mechanisms, without jeopardizing the error correction performance of the LDPC code. To do so, imprecise processing within the iterative message-passing decoder is considered in conjunction with the quantization process that provides the finite-precision information to the decoder. Thus, we first investigate a low complexity code and decoder aware quantizer, which is shown to closely approach the performance of the quantizer with decision levels optimized through exhaustive search, and then propose several imprecise designs of Min-Sum (MS)-based decoders. Proposed imprecise designs are aimed at reducing the size of the memory and interconnect blocks, which are known to dominate the overall area/delay performance of the hardware design. Several approaches are proposed, which allow storing the exchanged messages using a lower precision than that used by the processing units, thus facilitating significant reductions of the memory and interconnect blocks, with even better or only slight degradation of the error correction performance.We propose two new decoding algorithms and hardware implementations, obtained by introducing two levels of impreciseness in the Offset MS (OMS) decoding: the Partially OMS (POMS), which performs only partially the offset correction, and the Imprecise Partially OMS (I-POMS), which introduces a further level of impreciseness in the check-node processing unit. FPGA implementation results show that they can achieve significant throughput increase with respect to the OMS, while providing very close decoding performance, despite the impreciseness introduced in the processing units.We further introduce a new approach for hardware efficient LDPC decoder design, referred to as Non-Surjective Finite-Alphabet Iterative Decoders (FAIDs). NS-FAIDs are optimized by Density Evolution for regular and irregular LDPC codes. Optimization results reveal different possible trade-offs between decoding performance and hardware implementation efficiency. To validate the promises of optimized NS-FAIDs in terms of hardware implementation benefits, we propose three high-throughput hardware architectures, integrating NS-FAIDs decoding kernels. Implementation results on both FPGA and ASIC technology show that NS-FAIDs allow significant improvements in terms of both throughput and hardware resources consumption, as compared to the Min-Sum decoder, with even better or only slightly degraded decoding performance.

Ce manuscrit présente une approche novatrice au problème du traitement d'images omnidirectionnelles. Elle se démarque des autres approches par le fait que les traitements sont adaptés à la géométrie de l'image et effectués directement dans l'espace de l'image afin d'interpoler le moins possible les données originales de l'image. L'originalité de ce travail repose sur l'utilisation d'un ensemble de techniques de représentation de l'imprécision de la mesure de luminance induite par l'échantillonnage spatial de l'image. Ces techniques s'appuient sur une représentation par partition floue de l'image. Afin de traiter les images issues de capteurs omnidirectionnels catadioptriques, nous proposons une approche basée sur l'utilisation d'un espace projectif virtuel appelé le cylindre englobant. Ce cylindre nous permet de définir les différents opérateurs de convolution dans un espace quasi identique à celui de l'image perspective. Les opérateurs ainsi définis sont ensuite projetés sur l'image omnidirectionnelle pour tenir compte de la géométrie du capteur. Dans un premier temps, nous avons proposé une adaptation des masques de convolution aux images omnidirectionnelles prenant en compte les imprécisions sur la localisation du niveau de gris des pixels. Dans un second temps, nous nous sommes intéressés plus précisément aux détecteurs de contours. Nous avons développé une nouvelle approche d'estimation de gradient utilisant des noyaux possibilistes. L'estimation du gradient est fournie sous la forme d'un intervalle de valeurs. Cet intervalle permet de seuiller naturellement les valeurs de gradient obtenues. La validité de nos approches est établie par des expérimentations sur des images omnidirectionnelles synthétiques et réelles. Les images synthétiques sont utilisées afin de tester la robustesse de nos détecteurs de contours en présence de bruit et d'étudier la bonne détection, bonne localisation et réponse unique du contour. Les images réelles permettent d'observer le comportement de nos méthodes vis à vis des variations d'illumination et des bruits d'acquisition.

Beaucoup de programmes de visualisation, de planification de trajectoire, etc., utilisent intensivement des calculs de visibilité. Si ces calculs de visibilité ne constituent qu'une petite partie de ces programmes, ils sont en revanche responsables d'une grande partie du temps d'exécution de ces programmes: leur efficacité est donc cruciale. Les algorithmes traditionnels de calculs de visibilité ont deux défauts: ils effectuent - inutilement - des calculs sur des objets non visibles et refont tous ces calculs à chaque nouvelle requête, même si les changements avec la requête précédente sont minimes. Pour remédier à ces inconvénients dans le cadre de scènes polygonales bidimensionnelles, nous nous servons d'une structure de données - le complexe de visibilité - qui code toutes les relations de visibilité entre objets d'une scène. Après avoir montré comment construire de façon optimale le complexe de visibilité, nous montrons comment il permet d'utiliser la cohérence spatiale de la scène dans les calculs de polygones de visibilité. Nous montrons aussi comment il permet d'utiliser la cohérence temporelle dans le maintien d'une vue autour d'un point se déplaçant dans la scène. Nous étudions ces algorithmes non seulement d'un point de vue théorique mais aussi d'un point de vue pratique. Nous avons programmé ces algorithmes et effectué des comparaisons expérimentales entre algorithmes. Nous nous sommes aussi intéressés aux problèmes de dégénérescences et d'imprécisions des calculs numériques qui se posent dès que les programmes sont exécutés sur des données «réelles»

Nos travaux portent sur les Expressions Numériques Approximatives (ENA), définies comme des expressions linguistiques impliquant des valeurs numériques et un adverbe d'approximation, telles que "environ 100". Nous nous intéressons d’abord à l’interprétation d’ENA non contextualisées, dans ses aspects humain et computationnel. Après avoir formalisé des dimensions originales, arithmétiques et cognitive, permettant de caractériser les ENA, nous avons conduit une étude empirique pour collecter les intervalles de plages de valeurs dénotées par des ENA, qui nous a permis de valider les dimensions proposées. Nous avons ensuite proposé deux modèles d'interprétation, basés sur un même principe de compromis entre la saillance cognitive des bornes des intervalles et leur distance à la valeur de référence de l’ENA, formalisé par un front de Pareto. Le premier modèle estime l’intervalle dénoté, le second un intervalle flou représentant l’imprécision associée. Leur validation expérimentale à partir de données réelles montre qu’ils offrent de meilleures performances que les modèles existants. Nous avons également montrél’intérêt du modèle flou en l’implémentant dans le cadre des requêtes flexibles de bases de données. Nous avons ensuite montré, par une étude empirique, que le contexte et les interprétations, implicite vs explicite, ont peu d’effet sur les intervalles. Nous nous intéressons enfin à l’addition et à la multiplication d’ENA, par exemple pour évaluer la surface d’une pièce d’"environ 10" par "environ 20 mètres". Nous avons mené une étude dont les résultats indiquent que les imprécisions liées aux opérandes ne sont pas prises en compte lors des calculs. / Approximate Numerical Expressions (ANE) are imprecise linguistic expressions implying numerical values, illustrated by "about 100". We first focus on ANE interpretation, both in its human and computational aspects. After defining original arithmetical and cognitive dimensions allowing to characterize ANEs, we conducted an empirical study to collect the intervals of values denoted by ANEs. We show that the proposed dimensions are involved in ANE interpretation. In a second step, we proposed two interpretation models, based on the same principle of a compromise between the cognitive salience of the endpoints and their distance to the ANE reference value, formalized by Pareto frontiers. The first model estimates the denoted interval, the second one generates a fuzzy interval representing the associated imprecision. The experimental validation of the models, based on real data, show that they offer better performances than existing models. We also show the relevance of the fuzzy model by implementing it in the framework of flexible database queries. We then show, by the mean of an empirical study, that the semantic context has little effect on the collected intervals. Finally, we focus on the additions and products of ANE, for instance to assess the area of a room whose walls are "about 10" and "about 20 meters" long. We conducted an empirical study whose results indicate that the imprecisions associated with the operands are not taken into account during the calculations.

La localisation de séismes induits ainsi que les mécanismes au foyer associés sont des outils fréquemment utilisés afin, entre autres, d’imager la structure d’un réservoir. Cette thèse présente une technique permettant de quantifier les erreurs associées à ces deux paramètres. Par cette méthode, incertitudes et imprécisions sont distinguées. La méthode a été appliquée aux sites de Soultz et de Rittershoffen pour étudier l’impact de plusieurs critères sur la localisation de la sismicité induite. Ainsi, il a été montré que l’utilisation de capteurs installés profondément dans des puits et qu’une bonne couverture sismique azimutale réduit sérieusement les incertitudes de localisation. Les incertitudes du modèle de vitesse, représentées par une distribution gaussienne des modèles avec un écart de 5% autour du modèle de référence, multiplient les incertitudes de localisation par un facteur 2 à 3. Des simplifications utilisées pour le calcul ou une mauvaise connaissance du milieu peuvent mener à des imprécisions de l’ordre de 10% spatialement non isotropes. Ainsi, les structures du sous-sol peuvent être déformées dans les interprétations. L’application d’un tir de calibration peut néanmoins corriger ce fait en grande partie. L’étude d’erreurs associées aux mécanismes au foyer ne semble cependant pas conduire aux mêmes conclusions. Le biais angulaire peut certes être augmenté par l’omission de la faille dans le modèle de vitesse, mais dans plusieurs cas il est le même que dans le cas idéal voire diminué. En outre, une meilleure couverture sismique améliorerait toujours le mécanisme au foyer obtenu. Ainsi, il n’est pas conseillé d’imager un réservoir en n’utilisant que la localisation de séismes, mais une combinaison de plusieurs paramètres sismiques pourrait s’avérer efficace. La méthode appliquée dans le cadre de cette thèse pourra servir pour d’autres sites à condition d’en avoir une bonne connaissance a priori. / Induced seismicity location and focal mechanisms are commonly used to image the sub-surface designin reservoirs among other tasks. In this Ph.D. the inaccuracies and uncertainties on earthquake location and focal mechanisms are quantified using a three-step method. The technique is applied to the geothermal sites of Soultz and Rittershoffen to investigate the effect of several criteria on thee arthquake location. A good azimuthal seismic coverage and the use of seismic down-hole sensors seriously decrease the location uncertainty. On the contrary, velocity model uncertainties, represented by a 5% Gaussian distribution of the velocity model around the reference model, will multiply location uncertainties by a factor of 2 to 3. An incorrect knowledge of the sub-surface or the simplifications performed before the earthquake location can lead to biases of 10% of the vertical distance separating the source and the stations with a non-isotropic spatial distribution. Hence the sub-surface design maybe distorted in the interpretations. To prevent from that fact, the calibration shot method was proved to be efficient. The study on focal mechanism errors seems to lead to different conclusions. Obviously, the angular bias may be increased by neglecting the fault in the velocity. But, it may also be the same as or even smaller than the bias calculated for the case simulating a perfect knowledge of the medium of propagation. Furthermore a better seismic coverage always leads to smaller angular biases. Hence,it is worth advising to use more than only earthquake location in order to image a reservoir. Other geothermal sites and reservoirs may benefit from the method developed here. / Die korrekte Lokalisierung von induzierter Seismizität und den dazugehörigen Herdflächenlösungensind sehr wichtige Parameter. So werden zum Beispiel die Verteilung der Erdbeben und die Orientierung ihrer Herdflächenlösungen dazu benutzt um in der Tiefe liegende Reservoirs zulokalisieren und abzubilden. In dieser Doktorarbeit wird eine Technik vorgeschlagen um diemethodisch bedingten Fehler zu quantifizieren. Mit dieser Methode werden die verschiedenen Fehlerquellen, die Unsicherheiten und die Fehler im Modell getrennt. Die Technik wird für die geothermischen Felder in Soultz und in Rittershoffen benutzt um den Einfluss verschiedener Parameter (Annahmen) auf die Lokalisierung der induzierten Seismizität zu bestimmen. Es wurde festgestellt, dass Bohrlochseismometer und eine gute azimutale Verteilung der seismischen Stationen die Unbestimmtheiten verkleinern. Die Geschwindigkeitsunbestimmheiten, die durch eine Gauss-Verteilung mit 5% Fehler dargestellt werden, vervielfachen die Lokalisierungsungenauigkeiten um einen Faktor 2 bis 3. Eine ungenaue Kenntnis des Untergrunds oder die verwendete vereinfachte Darstellung der Geschwindigkeitsverhältnisse im Untergrund (notwendig um die synthetischen Rechnungen durchführen zu können) führen zu anisotropen Abweichungen und Fehlern in der Herdtiefe von bis zu 10%. Diese können die Interpretationen des Untergrunds deutlich verfälschen. Ein “calibration shot” kann diese Fehler korrigieren. Leider können die Fehler für die Herdflächenlösungen nicht in derselben Weise korrigiert werden. Es erscheint daher als keine gute Idee, ein Reservoir nur über die Lokalisierung von Erdbeben zu bestimmen. Eine Kombination mehrerer seismischer Methoden scheint angezeigt. Die hier besprochene Methode kann als Grundlage dienen für die Erkundung anderer (geothermischer)

Ce rapport présente les différentes étapes suivies afin de définir une nouvelle approche de modélisation et de simulation à évènements discrets pour les systèmes à paramètres imprécis. Cette étude a débuté avec des travaux sur la formalisation d'un système de production de fromage Corse. Suite à ces recherches, et en particulier, suite à la phase de modélisation du processus, nous avons pu constater l'influence de paramètres imparfaitement définis. Ces paramètres entrent en compte au cours des différentes phases de conception, et sont difficiles à représenter et surtout à manipuler. Dans le but de les prendre en compte de manière générique, nous nous sommes naturellement tournés vers l'utilisation de la Logique Floue. En effet, elle permet de représenter des informations imprécises (théorie des sous ensembles flous), incertaines (théorie des possibilités), et inexacte (raisonnement approximatif). Son avantage principal est de fournir un grand nombre d'outils mathématiques afin de manipuler de telles informations sous forme numérique ou linguistique, c'est-à-dire de manière relativement proche du mode de représentation, et surtout d'expression utilisé par l'homme. A partir des théories du flou, nous pouvons donc user de concepts mathématiques complexes tout en conservant un rapport privilégié (lien) entre représentation numérique et mode de description humain. Nous avons choisi d'intégrer ces différents outils dans un multi formalisme de modélisation et de simulation afin de pouvoir spécifier de manière générique n'importe quel type de système à paramètres imprécis. Le formalisme employé est nommé DEVS (Discrete EVents system Specification). Ses principaux avantages sont : sa capacité à être étendu à de nouveaux domaines d'étude, dans notre cas les systèmes flous ; la séparation des phases de modélisation et de simulation, de ce fait, lors de la conception d'un modèle DEVS les algorithmes de simulation sont automatiquement générés en fonction du modèle ; enfin, il permet de représenter un système sous sa forme fonctionnelle et structurelle. Notre but est d'associer le formalisme DEVS et une partie des théories du flou afin de définir une nouvelle approche de modélisation approximative.