Le développement de la "3D" dans l'industrie cinématographique ainsi que la mise sur le marché de consoles telles que la Nintendo 3DS et d'écrans stéréoscopiques utilisant des lunettes (actives ou passives) accrédite la démocratisation du relief dans notre rapport à l'image. L'une des dernières technologies en matière de restitution relief est l'écran auto-stéréoscopique : il permet l'affichage simultané de plusieurs vues d'une même scène (généralement entre 2 ou 9) et ne nécessite pas le port de lunettes pour percevoir le relief. Les séquences auto-stéréoscopiques représentent un volume conséquent de données (lié au nombre de points de vue) qui est encore accentué par le fait que la technologie associée aux écrans est en constante évolution. En effet, les écrans actuels proposent des résolutions et des fréquences d'affichage de plus en plus élevées avec, notamment, l'arrivée prochaine sur le marché du standard UHDTV. Ces différents facteurs tendent à produire des volumes de données toujours plus conséquents qui doivent être compressés pour permettre leur transmission sur des réseaux ou pour faciliter leur stockage. Le travail de thèse, qui a été mené dans le cadre du projet "Cam-Relief", a pour objectif le développement de solutions logicielles dédiées à la compression multi-vues de séquences auto-stéréoscopiques. Chacune de nos contributions vise à répondre à un des besoins spécifiques suivant : la compression temps réel des séquences issues de nos systèmes d'acquisition, la compression sans perte de séquences destinées à la post-production ainsi qu'une alternative au standard de compression multi-vues actuel : H.264/MultiView-Coding. Nous présentons dans ce mémoire trois méthodes de compression multi-vues, chacune répondant aux trois besoins respectifs énoncés ci-dessus. La première, appelée MICA (Multirvew Image Compression Algortihm), est un algorithme de compression multi-vues temps réel qui exploite la corrélation inter-vues présente au sein des séquences auto-stéréoscopiques en utilisant le principe d'images de différence. Ces images de différence vont aussi nous permettre de mettre en avant les zones de l'images soumises à la parallaxe et ainsi permettre de les préserver le plus possible d'importantes distorsions. La deuxième contribution, nommé Multiview-LS (Lossless), est une adaptation au cas multi-vues de l'algorithme JPEG-LS. En modifiant la structure du schéma de prédiction de JPEG-LS, notre algorithme permet l'exploitation des corrélations temporelles et inter-vues spécifiques aux séquences auto-stéréoscopiques. Le troisième schéma de compression, enfin, propose un algorithme de compression basé sur l'approche LDI (Layered-Depth Image). La génération de celui-ci est basée sur une approche innovante utilisant des cartes de disparités entières. Nous proposons deux schémas dédiés à la compression de l'information chromatique du LDI : un basé sur l’utilisation de la DCT et l'autre basé sur l'utilisation de la DWT. L'information de disparité est quant à elle codée à l'aide d'un algorithme de compression sans perte. / The development of the "3D" in the film industry, the marketing of consoles suche as the Nintendo 3DS ans screens using stereoscopic glasses (active or passive) accredits the democratization of the 3DTV. One of the latest technologies associated to 3D resides in auto-stereoscopic displays which allow the simultaneous display of multiple views from a scene (usually between 2 and 9) and do not require glasses to perceive the depth impression. These auto-stereoscopic sequences represent a significant volume of data (related to the number of views) which is further accentuated by the fact that the technology associated with screens is constanly changing. Indeed, the current screens offer higher and higher resolutions and display frequencies, notably with the arrival of the UHDTV standard on the market. These factors tend to produce high amounts of data which have to be compressed in order to allow transmission over networks or for easy storage. The thesis, which was conducted under the project "CamRelief", aims to develop software solutions for the muli-view compression of these auto-stereoscopic sequences. Each of our contributions addresses a special need from the following : real-time compression of multi-view sequences produced but our acquisition systems, lossless compression of multi-view sequences for post-production and an alternative to the multi-view compression standard : H.264/MultiView-Coding. In this paper, we present three multi-view compression methods which meet the three respective needs outlined above. The first method, called MICA (Multiview Image Compression Algortihm) is a real-time multi-view compression algorithm which exploits the inter-view correlation by using the concept of much as possible from major distoritions. The second contribution, called Multiview-LS (Lossless), is a multi-view adaptation of the JPEG-LS algortihm. By changing the structure of the JPEG-LS prediction scheme, our algorithm allows the exploitation of temporal and interview correlations specific to auto-stéréoscopic sequences. Finally, the third compression scheme is based ont the LDI (Layered-Depth Image) concept. The LDI generation is based on an innovative approach using integer-valued disparity maps. We propose two schemes dedicated to the chromatic LDI information compression : one based on the use of the DCT and the other based on the use of the DWT. The disparity information is encoded using a lossless compression algorithm.

La matérialisation de vues est une technique très utilisée dans les systèmes de gestion de bases de données ainsi que dans les entrepôts de données pour améliorer les performances des requêtes. Elle permet de réduire de manière considérable le temps de réponse des requêtes en pré-calculant des requêtes coûteuses et en stockant leurs résultats. De ce fait, l'exécution de certaines requêtes nécessite seulement un accès aux vues matérialisées au lieu des données sources. En contrepartie, la matérialisation entraîne un surcoût de maintenance des vues. En effet, les vues matérialisées doivent être mises à jour lorsque les données sources changent a fin de conserver la cohérence et l'intégrité des données. De plus, chaque vue matérialisée nécessite également un espace de stockage supplémentaire qui doit être pris en compte au moment de la sélection. Le problème de choisir quelles sont les vues à matérialiser de manière à réduire les coûts de traitement des requêtes étant donné certaines contraintes tel que l'espace de stockage et le coût de maintenance, est connu dans la littérature sous le nom du problème de la sélection de vues. Trouver la solution optimale satisfaisant toutes les contraintes est un problème NP-complet. Dans un contexte distribué constitué d'un ensemble de nœuds ayant des contraintes de ressources différentes (CPU, IO, capacité de l'espace de stockage, bande passante réseau, etc.), le problème de la sélection de vues est celui de choisir un ensemble de vues à matérialiser ainsi que les nœuds du réseau sur lesquels celles-ci doivent être matérialisées de manière à optimiser les coût de maintenance et de traitement des requêtes. Notre étude traite le problème de la sélection de vues dans un environnement centralisé ainsi que dans un contexte distribué. Notre objectif est de fournir une approche efficace dans ces contextes. Ainsi, nous proposons une solution basée sur la programmation par contraintes, connue pour être efficace dans la résolution des problèmes NP-complets et une méthode puissante pour la modélisation et la résolution des problèmes d'optimisation combinatoire. L'originalité de notre approche est qu'elle permet une séparation claire entre la formulation et la résolution du problème. A cet effet , le problème de la sélection de vues est modélisé comme un problème de satisfaction de contraintes de manière simple et déclarative. Puis, sa résolution est effectuée automatiquement par le solveur de contraintes. De plus, notre approche est flexible et extensible, en ce sens que nous pouvons facilement modéliser et gérer de nouvelles contraintes et mettre au point des heuristiques pour un objectif d'optimisation. Les principales contributions de cette thèse sont les suivantes. Tout d'abord, nous dé finissons un cadre qui permet d'avoir une meilleure compréhension des problèmes que nous abordons dans cette thèse. Nous analysons également l'état de l'art des méthodes de sélection des vues à matérialiser en en identifiant leurs points forts ainsi que leurs limites. Ensuite, nous proposons une solution utilisant la programmation par contraintes pour résoudre le problème de la sélection de vues dans un contexte centralisé. Nos résultats expérimentaux montrent notre approche fournit de bonnes performances. Elle permet en effet d'avoir le meilleur compromis entre le temps de calcul nécessaire pour la sélection des vues à matérialiser et le gain de temps de traitement des requêtes à réaliser en matérialisant ces vues. Enfin, nous étendons notre approche pour résoudre le problème de la sélection de vues à matérialiser lorsque celui-ci est étudié sous contraintes de ressources multiples dans un contexte distribué. A l'aide d'une évaluation de performances extensive, nous montrons que notre approche fournit des résultats de qualité et fi ables.

Diss.--Fakultät für Architektur--München--Technische Universität, 1994. / Bibliogr. p. 193-204.

Dans cette thèse nos contributions à la résolution de deux problématiques rencontrées en vision numérique et en photogrammétrie, qui sont le calibrage de caméras et la stéréovision, sont présentées. Ces deux problèmes font l’objet de très nombreuses recherches depuis plusieurs années. Les techniques de calibrage existantes diffèrent beaucoup suivant le type de caméras à calibrer (classique ou panoramique, à focale fixe ou à focale variable, ..). Notre première contribution est un banc de calibrage, à l’aide des éléments d’optique diffractive, qui permet de calibrer avec une bonne précision une très grande partie des caméras existantes. Un modèle simple et précis qui décrit la projection de la grille formée sur l’image et une méthode de calibrage pour chaque type de caméras est proposé. La technique est très robuste et les résultats pour l’ensemble des caméras calibrées sont optimaux. Avec la multiplication des types de caméras et la diversité des modèles de projections, un modèle de formation d'image générique semble très intéressant. Notre deuxième contribution est un modèle de projection unifié pour plusieurs caméras classiques et panoramiques. Dans ce modèle, toute caméra est modélisée par une projection rectiligne et des splines cubiques composées permettant de représenter toutes sortes de distorsions. Cette approche permet de modéliser géométriquement les systèmes de stéréovision mixtes ou panoramiques et de convertir une image panoramique en une image classique. Par conséquent, le problème de stéréovision mixte ou panoramique est transformé en un problème de stéréovision conventionnelle. Mots clés : calibrage, vision panoramique, distorsion, fisheye, zoom, panomorphe, géométrie épipolaire, reconstruction tridimensionnelle, stéréovision hybride, stéréovision panoramique. / This thesis aims to present our contributions to the resolution of two problems encountered in the field of computer vision and photogrammetry, which are camera calibration and stereovision. These two problems have been extensively studied in the last years. Different camera calibration techniques have been developed in the literature depending on the type of camera (classical or panoramic, with zoom lens or fixed lens..). Our first contribution is a compact and accurate calibration setup, based on diffractive optical elements, which is suitable for different kind of cameras. The technique is very robust and optimal results were achieved for different types of cameras. With the multiplication of camera types and the diversity of the projection models, a generic model has become very interesting. Our second contribution is a generic model, which is suitable for conventional and panoramic cameras. In this model, composed cubic splines functions provide more realistic model of both radial and tangential distortions. Such an approach allows to model either hybrid or panoramic stereovision system and to convert panoramic image to classical image. Consequently, the processing challenges of a hybrid stereovision system or a panoramic stereovision system are turned into simple classical stereovision problems. Keywords: Calibration, panoramic vision, distortions, fisheye, zoom, panomorph, epipolar geometry, three-dimensional reconstruction, hybrid stereovision, panoramic stereovision.

De nos jours, des masses de données sont publiées à grande échelle dans des formats numériques. Une part importante de ces données a une structure complexe, typiquement organisée sous la forme d'arbres (les documents du web, comme HTML et XML, étant les plus représentatifs) ou de graphes (en particulier, les bases de données du Web Sémantique structurées en graphes, et exprimées en RDF). Exploiter ces données complexes, qu'elles soient dans un format d'accès Open Data ou bien propriétaire (au sein d'une compagnie), présente un grand intérêt. Le faire de façon efficace pour de grands volumes de données reste encore un défi. Les vues matérialisées sont utilisées depuis longtemps pour améliorer considérablement l'évaluation des requêtes. Le principe est q'une vue stocke des résultats pre-calculés qui peuvent être utilisés pour évaluer (une partie d') une requête. L'adoption des techniques de vues matérialisées dans le contexte de données du web que nous considérons est particulièrement exigeante à cause de la complexité structurelle et sémantique des données. Cette thèse aborde deux problèmes liés à la gestion des données du web basée sur des vues matérialisées. D'abord, nous nous concentrons sur le problème de sélection des vues pour des ensembles de requêtes RDF. Nous présentons un algorithme original qui, basé sur un ensemble de requêtes, propose les vues les plus appropriées à matérialiser dans la base des données. Ceci dans le but de minimiser à la fois les coûts d'évaluation des requêtes, de maintenance et de stockage des vues. Bien que les requêtes RDF contiennent typiquement un grand nombre de jointures, ce qui complique le processus de sélection de vues, notre algorithme passe à l'échelle de centaines de requêtes, un nombre non atteint par les méthodes existantes. En outre, nous proposons des techniques nouvelles pour tenir compte des données implicites qui peuvent être dérivées des schémas RDF sans complexifier davantage la sélection des vues. La deuxième contribution de notre travail concerne la réécriture de requêtes en utilisant des vues matérialisées XML. Nous commençons par identifier un dialecte expressif de XQuery, correspondant aux motifs d'arbres avec des jointures sur la valeur, et nous étudions des propriétés importantes de ces requêtes, y compris l'inclusion et la minimisation. En nous fondant sur ces notions, nous considérons le problème de trouver des réécritures minimales et équivalentes d'une requête exprimée dans ce dialecte, en utilisant des vues matérialisées exprimées dans le même dialecte, et nous fournissons un algorithme correct et complet à cet effet. Notre travail dépasse l'état de l'art en permettant à chaque motif d'arbre de renvoyer un ensemble d'attributs, en prenant en charge des jointures sur la valeur entre les motifs, et en considérant des réécritures qui combinent plusieurs vues. Enfin, nous montrons comment notre méthode de réécriture peut être appliquée dans un contexte distribué, pour la dissémination efficace d'un corpus de documents XML annotés en RDF. / Data is being published in digital formats at very high rates nowadays. A large share of this data has complex structure, typically organized as trees (Web documents such as HTML and XML being the most representative) or graphs (in particular, graph-structured Semantic Web databases, expressed in RDF). There is great interest in exploiting such complex data, whether in an Open Data access model or within companies owning it, and efficiently doing so for large data volumes remains challenging. Materialized views have long been used to obtain significant performance improvements when processing queries. The principle is that a view stores pre-computed results that can be used to evaluate (possibly part of) a query. Adapting materialized view techniques to the Web data setting we consider is particularly challenging due to the structural and semantic complexity of the data. This thesis tackles two problems in the broad context of materialized view-based management of Web data. First, we focus on the problem of view selection for RDF query workloads. We present a novel algorithm, which, based on a query workload, proposes the most appropriate views to be materialized in the database, in order to minimize the combined cost of query evaluation, view maintenance and view storage. Although RDF query workloads typically feature many joins, hampering the view selection process, our algorithm scales to hundreds of queries, a number unattained by existing approaches. Furthermore, we propose new techniques to account for the implicit data that can be derived by the RDF Schemas and which further complicate the view selection process. The second contribution of our work concerns query rewriting based on materialized XML views. We start by identifying an expressive dialect of XQuery, corresponding to tree patterns with value joins, and study some important properties for these queries, such as containment and minimization. Based on these notions, we consider the problem of finding minimal equivalent rewritings of a query expressed in this dialect, using materialized views expressed in the same dialect, and provide a sound and complete algorithm for that purpose. Our work extends the state of the art by allowing each pattern node to return a set of attributes, supporting value joins in the patterns, and considering rewritings which combine many views. Finally, we show how our view-based query rewriting algorithm can be applied in a distributed setting, in order to efficiently disseminate corpora of XML documents carrying RDF annotations.

De nos jours, dans plusieurs domaines, tels que la bio-informatique ou le multimédia, les données peuvent être représentées par plusieurs ensembles d'attributs, appelés des vues. Pour une tâche de classification donnée, nous distinguons deux types de vues : les vues fortes sont celles adaptées à la tâche, les vues faibles sont adaptées à une (petite) partie de la tâche ; en classification multi-classes, chaque vue peut s'avérer forte pour reconnaître une classe, et faible pour reconnaître d’autres classes : une telle vue est dite déséquilibrée. Les travaux présentés dans cette thèse s'inscrivent dans le cadre de l'apprentissage supervisé et ont pour but de traiter les questions d'apprentissage multi-vue dans le cas des vues fortes, faibles et déséquilibrées. La première contribution de cette thèse est un algorithme d'apprentissage multi-vues théoriquement fondé sur le cadre de boosting multi-classes utilisé par AdaBoost.MM. La seconde partie de cette thèse concerne la mise en place d'un cadre général pour les méthodes d'apprentissage de classes déséquilibrées (certaines classes sont plus représentées que les autres). Dans la troisième partie, nous traitons le problème des vues déséquilibrées en combinant notre approche des classes déséquilibrées et la coopération entre les vues mise en place pour appréhender la classification multi-vues. Afin de tester les méthodes sur des données réelles, nous nous intéressons au problème de classification d'appels téléphoniques, qui a fait l'objet du projet ANR DECODA. Ainsi chaque partie traite différentes facettes du problème. / Nowadays, in many fields, such as bioinformatics or multimedia, data may be described using different sets of features, also called views. For a given classification task, we distinguish two types of views:strong views, which are suited for the task, and weak views suited for a (small) part of the task; in multi-class learning, a view can be strong with respect to some (few) classes and weak for the rest of the classes: these are imbalanced views. The works presented in this thesis fall in the supervised learning setting and their aim is to address the problem of multi-view learning under strong, weak and imbalanced views, regrouped under the notion of uneven views. The first contribution of this thesis is a multi-view learning algorithm based on the same framework as AdaBoost.MM. The second part of this thesis proposes a unifying framework for imbalanced classes supervised methods (some of the classes are more represented than others). In the third part of this thesis, we tackle the uneven views problem through the combination of the imbalanced classes framework and the between-views cooperation used to take advantage of the multiple views. In order to test the proposed methods on real-world data, we consider the task of phone calls classifications, which constitutes the subject of the ANR DECODA project. Each part of this thesis deals with different aspects of the problem.

Le langage XML, proposé par le W3C, est aujourd’hui utilisé comme un modèle de données pour le stockage et l’interrogation de grands volumes de données dans les systèmes de bases de données. En dépit d’importants travaux de recherche et le développement de systèmes efficace, le traitement de grands volumes de données XML pose encore des problèmes des performance dus à la complexité et hétérogénéité des données ainsi qu’à la complexité des langages courants d’interrogation XML. Les vues matérialisées sont employées depuis des décennies dans les bases de données afin de raccourcir les temps de traitement des requêtes. Elles peuvent être considérées les résultats de requêtes pré-calculées, que l’on réutilise afin d’éviter de recalculer (complètement ou partiellement) une nouvelle requête. Les vues matérialisées ont fait l’objet de nombreuses recherches, en particulier dans le contexte des entrepôts des données relationnelles.Cette thèse étudie l’applicabilité de techniques de vues matérialisées pour optimiser les performances des systèmes de gestion de données Web, et en particulier XML, dans des environnements distribués. Dans cette thèse, nos apportons trois contributions.D’abord, nous considérons le problème de la sélection des meilleures vues à matérialiser dans un espace de stockage donné, afin d’améliorer la performance d’une charge de travail des requêtes. Nous sommes les premiers à considérer un sous-langage de XQuery enrichi avec la possibilité de sélectionner des noeuds multiples et à de multiples niveaux de granularités. La difficulté dans ce contexte vient de la puissance expressive et des caractéristiques du langage des requêtes et des vues, et de la taille de l’espace de recherche de vues que l’on pourrait matérialiser.Alors que le problème général a une complexité prohibitive, nous proposons et étudions un algorithme heuristique et démontrer ses performances supérieures par rapport à l’état de l’art.Deuxièmement, nous considérons la gestion de grands corpus XML dans des réseaux pair à pair, basées sur des tables de hachage distribuées. Nous considérons la plateforme ViP2P dans laquelle des vues XML distribuées sont matérialisées à partir des données publiées dans le réseau, puis exploitées pour répondre efficacement aux requêtes émises par un pair du réseau. Nous y avons apporté d’importantes optimisations orientées sur le passage à l’échelle, et nous avons caractérisé la performance du système par une série d’expériences déployées dans un réseau à grande échelle. Ces expériences dépassent de plusieurs ordres de grandeur les systèmes similaires en termes de volumes de données et de débit de dissémination des données. Cette étude est à ce jour la plus complète concernant une plateforme de gestion de contenus XML déployée entièrement et testée à une échelle réelle.Enfin, nous présentons une nouvelle approche de dissémination de données dans un système d’abonnements, en présence de contraintes sur les ressources CPU et réseau disponibles; cette approche est mise en oeuvre dans le cadre de notre plateforme Delta. Le passage à l’échelle est obtenu en déchargeant le fournisseur de données de l’effort de répondre à une partie des abonnements. Pour cela, nous tirons profit de techniques de réécriture de requêtes à l’aide de vues afin de diffuser les données de ces abonnements, à partir d’autres abonnements.Notre contribution principale est un nouvel algorithme qui organise les vues dans un réseau de dissémination d’information multi-niveaux ; ce réseau est calculé à l’aide d’outils techniques de programmation linéaire afin de passer à l’échelle pour de grands nombres de vues, respecter les contraintes de capacité du système, et minimiser les délais de propagation des information. L’efficacité et la performance de notre algorithme est confirmée par notre évaluation expérimentale, qui inclut l’étude d’un déploiement réel dans un réseau WAN. / XML was recommended by W3C in 1998 as a markup language to be used by device- and system-independent methods of representing information. XML is nowadays used as a data model for storing and querying large volumes of data in database systems. In spite of significant research and systems development, many performance problems are raised by processing very large amounts of XML data. Materialized views have long been used in databases to speed up queries. Materialized views can be seen as precomputed query results that can be re-used to evaluate (part of) another query, and have been a topic of intensive research, in particular in the context of relational data warehousing. This thesis investigates the applicability of materialized views techniques to optimize the performance of Web data management tools, in particular in distributed settings, considering XML data and queries. We make three contributions.We first consider the problem of choosing the best views to materialize within a given space budget in order to improve the performance of a query workload. Our work is the first to address the view selection problem for a rich subset of XQuery. The challenges we face stem from the expressive power and features of both the query and view languages and from the size of the search space of candidate views to materialize. While the general problem has prohibitive complexity, we propose and study a heuristic algorithm and demonstrate its superior performance compared to the state of the art.Second, we consider the management of large XML corpora in peer-to-peer networks, based on distributed hash tables (or DHTs, in short). We consider a platform leveraging distributed materialized XML views, defined by arbitrary XML queries, filled in with data published anywhere in the network, and exploited to efficiently answer queries issued by any network peer. This thesis has contributed important scalability oriented optimizations, as well as a comprehensive set of experiments deployed in a country-wide WAN. These experiments outgrow by orders of magnitude similar competitor systems in terms of data volumes and data dissemination throughput. Thus, they are the most advanced in understanding the performance behavior of DHT-based XML content management in real settings.Finally, we present a novel approach for scalable content-based publish/subscribe (pub/sub, in short) in the presence of constraints on the available computational resources of data publishers. We achieve scalability by off-loading subscriptions from the publisher, and leveraging view-based query rewriting to feed these subscriptions from the data accumulated in others. Our main contribution is a novel algorithm for organizing subscriptions in a multi-level dissemination network in order to serve large numbers of subscriptions, respect capacity constraints, and minimize latency. The efficiency and effectiveness of our algorithm are confirmed through extensive experiments and a large deployment in a WAN.

Dans cette thèse, nous nous intéressons au problème de la confidentialité des données. Nous proposons une nouvelle approche pour faciliter l'administration des règles de contrôle d'accès pour assurer la confidentialité des données au niveau des vues matérialisées. Dans les bases de données relationnelles, une vue est une table virtuelle représentant le résultat d'une requête. À la différence d'une vue simple, une vue matérialisée stocke le résultat de la requête dans une table. Cette dernière peut être alors interrogée comme une table quelconque. Il est donc important d'y contrôler l'accès. Parmi les différents modèles proposés pour contrôler l'accès aux relations de base, nous nous basons dans notre approche sur l'utilisation des vues d'autorisations pour exprimer des règles de contrôle d'accès à grains fins. Nous proposons d'inférer, à partir des vues d'autorisations attachées aux tables de base, les vues d'autorisations qui doivent être attachées aux vues matérialisées. Répondre à ce problème revient à répondre à un problème fondamental dans les bases de données relationnelles : Comment caractériser les informations calculables à partir de deux ensembles de vues ? Nous répondons à cette question en nous appuyant sur la réécriture de requêtes. Nous adaptons l'algorithme de réécriture de requêtes M iniCon aux spécificités de notre problème et nous proposons l'algorithme 1-l M iniCon+ qui se base sur un enchainement de réécritures. Nous nous intéressons aux vues représentées par des requêtes conjonctives en autorisant les égalités. Nous nous sommes intéressés par la suite aux propriétés de cet algorithme. Nous démontrons que cet algorithme permet de calculer un ensemble de vues correctes, c.-à-d. toute information calculable à partir de l'ensemble de vues générées est cal­ culable à partir de chacun des deux ensembles de vues de départ / In this thesis, we address the problem of data confidentiality. We propose a new approach to facilitate the administration of access control policies to ensure confidentiality of data in materialized views. In relational databases, a view is a virtual table representing the result of a query. Unlike a simple view, a materialized view persistently stores the data in a table. The latter can be queried like any other database table. We then need to control the access to the materialized view. Among the various models proposed for controlling access to base relations, we choose to express fine-grained access control through authorization views. We propose to infer, from the basic authorization views attached to the base tables, authorization views that will be attached to the materialized views. Tackling this problem amounts to address a fundamental problem in relational databases : How to characterize computable information from two sets of views ? We handle this problem by resorting to query rewriting. We adapt the query rewriting algorithm MiniCon to the context of materialized views with access control and propose the H MiniCon+ algorithm which is based on successive rewritings. We mainly consider conjunctive queries with equalities. We study the properties of our approach. We show that our algorithm can calculate a correct set of views, i.e. any computable information from the generated views is calculable from the two sets of views. In order to prove the termination of our algorithm, we define rewriting trees generated by the application of 1-l MiniCon+ and we study their features. We characterize in which case a tree is finite and show that the approach is maximal, i.e., any derivable information from the two sets of views can be derived from the set of generated views. We characterize in which case the algorithm could not terminate i.e., infinite application of the query rewriting algorithm. In this case, it is impossible to determine the maximality of results and this remains an open problem. We implemented a prototype of the approach and we led some experiments by using synthetic data sets

La matérialisation de vues est une technique très utilisée dans les systèmes de gestion bases de données ainsi que dans les entrepôts de données pour améliorer les performances des requêtes. Elle permet de réduire de manière considérable le temps de réponse des requêtes en pré-calculant des requêtes coûteuses et en stockant leurs résultats. De ce fait, l'exécution de certaines requêtes nécessite seulement un accès aux vues matérialisées au lieu des données sources. En contrepartie, la matérialisation entraîne un surcoût de maintenance des vues. En effet, les vues matérialisées doivent être mises à jour lorsque les données sources changent afin de conserver la cohérence et l'intégrité des données. De plus, chaque vue matérialisée nécessite également un espace de stockage supplémentaire qui doit être pris en compte au moment de la sélection. Le problème de choisir quelles sont les vues à matérialiser de manière à réduire les coûts de traitement des requêtes étant donné certaines contraintes tel que l'espace de stockage et le coût de maintenance, est connu dans la littérature sous le nom du problème de la sélection de vues. Trouver la solution optimale satisfaisant toutes les contraintes est un problème NP-complet. Dans un contexte distribué constitué d'un ensemble de noeuds ayant des contraintes de ressources différentes (CPU, IO, capacité de l'espace de stockage, bande passante réseau, etc.), le problème de la sélection des vues est celui de choisir un ensemble de vues à matérialiser ainsi que les noeuds du réseau sur lesquels celles-ci doivent être matérialisées de manière à optimiser les coût de maintenance et de traitement des requêtes.Notre étude traite le problème de la sélection de vues dans un environnement centralisé ainsi que dans un contexte distribué. Notre objectif est de fournir une approche efficace dans ces contextes. Ainsi, nous proposons une solution basée sur la programmation par contraintes, connue pour être efficace dans la résolution des problèmes NP-complets et une méthode puissante pour la modélisation et la résolution des problèmes d'optimisation combinatoire. L'originalité de notre approche est qu'elle permet une séparation claire entre la formulation et la résolution du problème. A cet effet, le problème de la sélection de vues est modélisé comme un problème de satisfaction de contraintes de manière simple et déclarative. Puis, sa résolution est effectuée automatiquement par le solveur de contraintes. De plus, notre approche est flexible et extensible, en ce sens que nous pouvons facilement modéliser et gérer de nouvelles contraintes et mettre au point des heuristiques pour un objectif d'optimisation.Les principales contributions de cette thèse sont les suivantes. Tout d'abord, nous définissons un cadre qui permet d'avoir une meilleure compréhension des problèmes que nous abordons dans cette thèse. Nous analysons également l'état de l'art des méthodes de sélection des vues à matérialiser en en identifiant leurs points forts ainsi que leurs limites. Ensuite, nous proposons une solution utilisant la programmation par contraintes pour résoudre le problème de la sélection de vues dans un contexte centralisé. Nos résultats expérimentaux montrent notre approche fournit de bonnes performances. Elle permet en effet d'avoir le meilleur compromis entre le temps de calcul nécessaire pour la sélection des vues à matérialiser et le gain de temps de traitement des requêtes à réaliser en matérialisant ces vues. Enfin, nous étendons notre approche pour résoudre le problème de la sélection de vues à matérialiser lorsque celui-ci est étudié sous contraintes de ressources multiples dans un contexte distribué. A l'aide d'une évaluation de performances extensive, nous montrons que notre approche fournit des résultats de qualité et fiable. / View selection is important in many data-intensive systems e.g., commercial database and data warehousing systems to improve query performance. View selection can be defined as the process of selecting a set of views to be materialized in order to optimize query evaluation. To support this process, different related issues have to be considered. Whenever a data source is changed, the materialized views built on it have to be maintained in order to compute up-to-date query results. Besides the view maintenance issue, each materialized view also requires additional storage space which must be taken into account when deciding which and how many views to materialize.The problem of choosing which views to materialize that speed up incoming queries constrained by an additional storage overhead and/or maintenance costs, is known as the view selection problem. This is one of the most challenging problems in data warehousing and it is known to be a NP-complete problem. In a distributed environment, the view selection problem becomes more challenging. Indeed, it includes another issue which is to decide on which computer nodes the selected views should be materialized. The view selection problem in a distributed context is now additionally constrained by storage space capacities per computer node, maximum global maintenance costs and the communications cost between the computer nodes of the network.In this work, we deal with the view selection problem in a centralized context as well as in a distributed setting. Our goal is to provide a novel and efficient approach in these contexts. For this purpose, we designed a solution using constraint programming which is known to be efficient for the resolution of NP-complete problems and a powerful method for modeling and solving combinatorial optimization problems. The originality of our approach is that it provides a clear separation between formulation and resolution of the problem. Indeed, the view selection problem is modeled as a constraint satisfaction problem in an easy and declarative way. Then, its resolution is performed automatically by the constraint solver. Furthermore, our approach is flexible and extensible, in that it can easily model and handle new constraints and new heuristic search strategies for optimization purpose. The main contributions of this thesis are as follows. First, we define a framework that enables to have a better understanding of the problems we address in this thesis. We also analyze the state of the art in materialized view selection to review the existing methods by identifying respective potentials and limits. We then design a solution using constraint programming to address the view selection problem in a centralized context. Our performance experimentation results show that our approach has the ability to provide the best balance between the computing time to be required for finding the materialized views and the gain to be realized in query processing by materializing these views. Our approach will also guarantee to pick the optimal set of materialized views where no time limit is imposed. Finally, we extend our approach to provide a solution to the view selection problem when the latter is studied under multiple resource constraints in a distributed context. Based on our extensive performance evaluation, we show that our approach outperforms the genetic algorithm that has been designed for a distributed setting.

Un des modèles les plus simples de surface de réfraction est une surface plane. Bien que sa présence soit omniprésente dans notre monde sous la forme de vitres transparentes, de fenêtres, ou la surface d'eau stagnante, très peu de choses sont connues sur la géométrie multi-vues causée par la réfraction d'une telle surface. Dans la première partie de cette thèse, nous analysons la géométrie à vues multiple d'une surface réfractive. Nous considérons le cas où une ou plusieurs caméras dans un milieu (p. ex. l'air) regardent une scène dans un autre milieu (p. ex. l'eau), avec une interface plane entre ces deux milieux. Le cas d'une photo sous-marine, par exemple, correspond à cette description. Comme le modèle de projection perspectif ne correspond pas à ce scenario, nous dérivons le modèle de caméra et sa matrice de projection associée. Nous montrons que les lignes 3D de la scène correspondent à des courbes quartiques dans les images. Un point intéressant à noter à propos de cette configuration est que si l'on considère un indice de réfraction homogène, alors il existe une courbe unique dans l'image pour chaque ligne 3D du monde. Nous décrivons et développons ensuite des éléments de géométrie multi-vues telles que les matrices fondamentales ou d'homographies liées à la scène, et donnons des éléments pour l'estimation de pose des caméras à partir de plusieurs points de vue. Nous montrons également que lorsque le milieu est plus dense, la ligne d'horizon correspond à une conique qui peut être décomposer afin d'en déduire les paramètres de l'interface. Ensuite, nous étendons notre approche en proposant des algorithmes pour estimer la géométrie de plusieurs surfaces planes refractives à partir d'une seule image. Un exemple typique d'un tel scenario est par exemple lorsque l'on regarde à travers un aquarium. Nous proposons une méthode simple pour calculer les normales de telles surfaces étant donné divers scenari, en limitant le système à une caméra axiale. Cela permet dans notre cas d'utiliser des approches basées sur ransac comme l'algorithme “8 points” pour le calcul de matrice fondamentale, d'une manière similaire à l'estimation de distortions axiales de la littérature en vision par ordinateur. Nous montrons également que le même modèle peut être directement adapté pour reconstruire des surfaces réflectives sous l'hypothèse que les surfaces soient planes par morceaux. Nous présentons des résultats de reconstruction 3D encourageants, et analysons leur précision. Alors que les deux approches précédentes se focalisent seulement sur la reconstruction d'une ou plusieurs surfaces planes réfractives en utilisant uniquement l'information géométrique, les surfaces spéculaires modifient également la manière dont l'énergie lumineuse à la surface est redistribuée. Le modèle sous-jacent correspondant peut être expliqué par les équations de Fresnel. En exploitant à la fois cette information géométrique et photométrique, nous proposons une méthode pour reconstruire la forme de surfaces spéculaires arbitraires. Nous montrons que notre approche implique un scenario d'acquisition simple. Tout d'abord, nous analysons plusieurs cas minimals pour la reconstruction de formes, et en déduisons une nouvelle contrainte qui combine la géométrie et la théorie de Fresnel à propos des surfaces transparentes. Ensuite, nous illustrons la nature complémentaire de ces attributs qui nous aident à obtenir une information supplémentaire sur l'objet, qu'il est difficile d'avoir autrement. Finalement, nous proposons une discussion sur les aspects pratiques de notre algorithme de reconstruction, et présentons des résultats sur des données difficiles et non triviales. / The task of understanding, 3D reconstruction and analysis of the multiple view geometry related to transparent objects is one of the long standing challenging problems in computer vision. In this thesis, we look at novel approaches to analyze images of transparent surfaces to deduce their geometric and photometric properties. At first, we analyze the multiview geometry of the simple case of planar refraction. We show how the image of a 3D line is a quartic curve in an image, and thus derive the first imaging model that accounts for planar refraction. We use this approach to then derive other properties that involve multiple cameras, like fundamental and homography matrices. Finally, we propose approaches to estimate the refractive surface parameters and camera poses, given images. We then extend our approach to derive algorithms for recovering the geometry of multiple planar refractive surfaces from a single image. We propose a simple technique to compute the normal of such surfaces given in various scenarios, by equating our setup to an axial camera. We then show that the same model could be used to reconstruct reflective surfaces using a piecewise planar assumption. We show encouraging 3D reconstruction results, and analyse the accuracy of results obtained using this approach. We then focus our attention on using both geometric and photometric cues for reconstructing transparent 3D surfaces. We show that in the presence of known illumination, we can recover the shape of such objects from single or multiple views. The cornerstone of our approach are the Fresnel equations, and we both derive and analyze their use for 3D reconstruction. Finally, we show our approach could be used to produce high quality reconstructions, and discuss other potential future applications.