Le travail présenté dans ce mémoire a pour objectif le développement de nouvelles approches permettant d'introduire de manière robuste des marques dans une vidéo. Il s'agira tout d'abord de sélectionner les zones des images les plus appropriées à l'introduction du tatouage. Pour cela, plusieurs critères devront être pris en compte. Tout d'abord, lorsqu'une marque est introduite dans une zone de l'image, il est nécessaire d'introduire la même marque au même endroit sur toutes les images de la séquence. En effet, dans le cas contraire, un simple filtrage temporel dans le sens du mouvement permet de détruire la marque. Il sera également important de détecter les zones moins importantes visuellement dans lesquelles des modifications pourraient être introduites plus facilement sans qu'elles soient visibles. Il s'agit notamment des zones visibles dans peu d'images différentes, ou des zones ou l'œil humain est peu susceptible de détecter des différences, telles que les zones d'ombres en mouvement. Pour parvenir à une détection efficace de telles régions, une phase d'analyse permettant notamment la création d'images mosaïques (ou sprite dans le contexte MPEG-4) et la détection des ombres en mouvement devra être réalisée. / The work presented in this thesis aims to develop new approaches to introduce, in a robust way, a marks in a video. The areas of the images which are most appropriate to the introduction of the tattoo should be selected. For that, several criteria must be taken into account. Firstly, when a mark is introduced into an area of the image, it is necessary to introduce the same mark at the same location on all images in the sequence. It is also important to detect an invisible areas where changes could be introduced easily without being seen. These are areas where the human eye is less sensitive to changes, such as shadows region of moving objects. To achieve the e#ective detection of such regions, a phase of analysis including the creation of mosaic images and the detection of shadows of moving objects will be realized.

Nous introduisons un algorithme de décomposition intrinsèque multi-vue qui permet de ré-éclairer une scène extérieure en utilisant quelques images en entrée. Plusieurs applications comme l’architecture, jeux et films exigent de manipuler un modèle 3D d’une scène. Cependant, la modification de telles scènes est limitée par les conditions d’éclairage de capture. Notre méthode estime les images intrinsèques prises dans des conditions d’éclairage identiques avec des ombres. Nous utilisons conjointement une reconstruction 3D automatique et la direction du soleil pour obtenir la décomposition de chaque image en calques de réflectance et d’éclairage malgré l’inexactitude des données du modèle 3D. Notre approche est basée sur deux idées principales. Tout d’abord, nous raffinons l’estimation des paramètres de notre modèle de formation d’image en combinant la simulation d’éclairage 3D avec des méthodes d’optimisation basée image. Deuxièmement, nous utilisons ce modèle pour exprimer la réflectance en fonction de valeur de visibilité discrète pour l’ombre et la lumière, ce qui nous permet d’introduire un classificateur d’ombre robuste pour des paires de points dans une scène. Nos calques intrinsèques sont de qualité suffisante pour manipuler les images d’entrée. Nous déplaçons les ombres portées en créant une géométrie qui préserve les silhouettes d’ombre. Notre méthode est compatible avec les approches de rendu basé image et réduit les coûts de création de contenu 3D. Enfin, nous présentons une étude sur les limites du modèle de réflectance diffus et la difficulté d’appliquer les approches existantes dans le cadre de reconstruction 3D multi vue où les données sont imprécises. / We present a multi-view intrinsic decomposition algorithm that allows relighting of an outdoor scene using just a few photographs as input. Several applications such as architecture, games and movies require a 3D model of a scene. However, editing such scenes is limited by the lighting condition at the time of capture. Our method computes intrinsic images photos taken under the same lighting condition with existing cast shadows by the sun. We use an automatic 3D reconstruction from these photos and the sun direction as input and decompose each image into reflectance and shading layers, despite the inaccuracies and missing data of the 3D model. Our approach is based on two key ideas. First, we progressively improve the accuracy of the parameters of our image formation model by performing iterative estimation and combining 3D lighting simulation with 2D image optimization methods. Second we use the image formation model to express reflectance as a function of discrete visibility values for shadow and light, which allows us to introduce a robust shadow classifier for pairs of points in a scene. Our multi-view intrinsic decomposition is of sufficient quality for relighting of the input images. We create shadow-caster geometry which preserves shadow silhouettes and using the intrinsic layers, we can perform multi-view relighting with moving cast shadows. Our method allows image-based rendering with changing illumination conditions and reduces the cost of creating 3D content for applications. Finally, we present an initial study on the limitation of diffuse reflectance models for these computations.

Cette thèse aborde la problématique du calcul d’ombre exact par pixel en temps réel. Ce mémoire propose une nouvelle méthode de rendu d’ombre dure avec une partition de volumes d’ombre : un arbre ternaire basés sur les plans d’ombre des volumes d’ombre de la scène est construit dans un premier temps, avant de l’interroger pour déterminer l’ombrage des pixels de l’image. Une des propriétés intéressantes de cette structure est la prédictibilité de son empreinte mémoire ; contrairement aux méthodes de calcul d’ombre, cette méthode supporte des scènes géométriquement complexes de l’ordre du million de triangles grâce au comportement logarithmique du parcours de la structure vis à vis de la complexité géométrique. / This thesis focuses on exact per pixel hard shadow computation. We propose a new method for rendering hard shadows using a partition of shadow volumes : first, a ternary tree based on the shadow planes of the shadow volumes, and then, it is traversed to determine the shading of each pixel in the image. An interesting property of this structure is the predictability of its memory footprint ; Unlike other geometric shadow methods, our approach supports complex scenes up to a million triangles thanks to the logarithmic behavior of the structure traversal with respect to the geometric complexity.

Les ombres sont un élément fondamental pour garantir le réalisme des images de synthèses. Elles donnent des informations nécessaires pour discerner correctement le positionnement relatif des objets. Le calcul d'ombre dures exactes en temps-réel reste toutefois un problème difficile en Informatique Graphique. Les Shadow Maps sont privilégiées pour leurs excellentes performances, mais elles ne peuvent garantir un résultat exact par pixel. Les volumes d'ombre sont plus lents que les Shadow Maps mais produisent des ombres exactes en toute circonstances. Bien qu'ils aient récemment atteint un haut niveau de performances, ils restent sensibles à la complexité géométrique et sont limités à des scènes de taille modeste. Dans cette thèse, nous proposons un nouvel algorithme de rendu d'ombres dures en temps réel basé sur les volumes d'ombre qui reste rapide sur des scènes de très grande tailles. De plus, nous introduisons une nouvelle stratégie de partitionnement jusque-là inexplorée en Informatique Graphique : les arbres métriques. / Shadows are a fundamental visual effect for computer generated images. They provide essential spatial hints allowing us to correctly perceive objects positions in the scene. Despite its importance, computing pixel accurate shadows in real-time is a challenging problem in Computer Graphics. Shadow Maps are still the favored solution due to their high efficiency, but they can't always provide pixel accurate results. Shadow Volumes are slower than Shadow Maps but always garantee pixel accurate shadows. While recent works significantly improved their performance, they remain sensitive to scalability, which limits their application scope. In this thesis, we propose a new algorithm based on Shadow Volumes that remains fast even on very large scenes. Furthermore, we introduce a new partitioning strategy that is yet unexplored in Computer Graphics : the metric tree.

Plusieurs études récentes démontrent que la prolifération de la végétation dans le Nord a augmenté sous un climat en réchauffement lors des quatres dernières décennies, surtout dans la zone de transition entre toundra et taïga. L’accroissement des arbustes a un effet sur les propriétés de la neige et du bilan d’énergie de surface. L’objectif de cette recherche est d’améliorer la caractérisation de l’impact des arbustes sur l’évolution de la neige (accumulation et fonte) en utilisant des données terrains et la télédétection. La recherche a été réalisée sur le site d’Umiujaq, au Nunavik, représentatif de la zone de transition entre l’Arctique de basse latitude et les zones subarctiques. La profondeur de neige, mesurée le long de nombreux transects qui couvrent plusieurs types de végétation (toundra arbustive, toundra de lichen, forêt ouverte et forêt fermée d’épinettes) démontre l’effet d’emprisonnement de la neige dans la zone de transition entre une zone de toundra arbustive vers une zone de forêt d’épinettes. Cet effet est lié à la hauteur de la végétation et à la perte de densité (la profondeur de neige augmente par des facteurs de 2,5 à 3). De plus, des mesures de profondeur de neige en continue ont été prises par deux stations météorologiques situées l'une en zone de toundra arbustive et l'autre en zone de forêt. Les résultats montrent que la neige réagit de façons très différentes selon la couverture du sol, mais reste très dépendante des sites considérés. Des analyses spatiales à très haute résolution (Pléiades) et à moyenne résolution (Landsat et MODIS) suggèrent un délai dans la fonte entre les zones de forêts et les zones de toundra de lichen et arbustives. Une technique de mesure de profondeur de neige par télédétection à haute résolution est aussi discutée. / Abstract : Recent studies have shown that northern vegetation has been growing in relation to a warming climate over the last four decades, especially across the transition zone between tundra and taiga. Shrub growth affects snow properties and the surface energy budget, which must be better studied to quantify shrub-snow-climate feedbacks. The objective of this research is to improve the characterization of the impact of shrubs on snow evolution, from its accumulation to its melt, using in-situ and satellite measurements. The research is presented for the Umiujaq site, Nunavik, representative of the low Arctic – Subarctic transition zone. Snow depth, measured along numerous transects spanning different land cover types is found to increase by a factor 2.5 to 3 between tundra and forest, while snow density decreases. This illustrates the trapping effect of vegetation well. Complementary continuous snow depth measurements using weather stations from two sites (tundra with low shrubs and a small clearing with shrubs within the forest) show different site-dependent behaviors. Spatial analysis from high-resolution Pleiades images combined with Landsat (Normalized Difference Snow Index) and MODIS (Fractional Snow Cover) images suggest a slight delay in melt over open and dense forest areas compared to tundra and dense high shrubs. A technic to measure snow depth using high resolution is also discussed.

La modélisation géométrique et la sémantisation de scènes intérieures à partir d'échantillon de points et un sujet de recherche qui prend de plus en plus d'importance. Cependant, le traitement d'un ensemble volumineux de données est rendu difficile d'une part par le nombre élevé d'objets parasitant la scène et d'autre part par divers défauts d'acquisitions comme par exemple des données manquantes ou un échantillonnage de la scène non isotrope. Cette thèse s'intéresse de près à de nouvelles méthodes permettant de modéliser géométriquement un nuage de point non structuré et d’y donner de la sémantique. Dans le chapitre 2, nous présentons deux méthodes permettant de transformer le nuage de points en un ensemble de formes. Nous proposons en premier lieu une méthode d'extraction de lignes qui détecte des segments à partir d'une coupe horizontale du nuage de point initiale. Puis nous introduisons une méthode par croissance de régions qui détecte et renforce progressivement des régularités parmi les formes planaires. Dans la première partie du chapitre 3, nous proposons une méthode basée sur de l'analyse statistique afin de séparer de la structure de la scène les objets la parasitant. Dans la seconde partie, nous présentons une méthode d'apprentissage supervisé permettant de classifier des objets en fonction d'un ensemble de formes planaires. Nous introduisons dans le chapitre 4 une méthode permettant de modéliser géométriquement le volume d'une pièce (sans meubles). Une formulation énergétique est utilisée afin de labelliser les régions d’une partition générée à partir de formes élémentaires comme étant intérieur ou extérieur de manière robuste au bruit et aux données. / Geometric modeling and semantization of indoor scenes from sampled point data is an emerging research topic. Recent advances in acquisition technologies provide highly accurate laser scanners and low-cost handheld RGB-D cameras for real-time acquisition. However, the processing of large data sets is hampered by high amounts of clutter and various defects such as missing data, outliers and anisotropic sampling. This thesis investigates three novel methods for efficient geometric modeling and semantization from unstructured point data: Shape detection, classification and geometric modeling. Chapter 2 introduces two methods for abstracting the input point data with primitive shapes. First, we propose a line extraction method to detect wall segments from a horizontal cross-section of the input point cloud. Second, we introduce a region growing method that progressively detects and reinforces regularities of planar shapes. This method utilizes regularities common to man-made architecture, i.e. coplanarity, parallelism and orthogonality, to reduce complexity and improve data fitting in defect-laden data. Chapter 3 introduces a method based on statistical analysis for separating clutter from structure. We also contribute a supervised machine learning method for object classification based on sets of planar shapes. Chapter 4 introduces a method for 3D geometric modeling of indoor scenes. We first partition the space using primitive shapes detected from permanent structures. An energy formulation is then used to solve an inside/outside labeling of a space partitioning, the latter providing robustness to missing data and outliers.

L'introduction du transistor à un électron (SET) a secoué l'industrie des semi-conducteurs, avec des promesses d'efficacité inégalée. Cependant, le coût et la complexité associés à la réalisation d'un fonctionnement stable ont fortement entravé leur adoption. Après être tombé en dehors des grâces de l'industrie, la recherche universitaire a continué à pousser, démontrant des techniques novatrices pour la création de SET. Au cœur de ce problème de stabilité, il y a le besoin de construire de manière contrôlable des nanoislands de moins de 10 nm. Parmi les méthodes disponibles pour cette formation nanoisland, le dépôt de couche atomique (ALD) se distingue comme un processus hautement contrôlable industriellement. La deuxième barrière à l'entrée est la création d'électrodes nanogap, utilisées pour injecter du courant à travers ces nanoislands, pour lesquelles les chercheurs se sont largement appuyés sur des techniques de fabrication non évolutives comme la lithographie par faisceau d'électrons et le faisceau ionique focalisé. La technique d'évaporation de bord d'ombre surmonte les problèmes de complexité et d'échelle de la fabrication de nanogap, ouvrant de nouvelles possibilités. Dans ce travail, ALD sera démontré comme une superbe technique pour la culture de vastes réseaux 3D de nanoparticules de platine sous 2nm encapsulées dans Al2O3. ALD a fourni un moyen de faire croître ces matrices de nanoparticules en un seul processus, sous vide et à basse température. Grâce à l'évaporation du bord d'ombre, la lithographie UV a ensuite été utilisée pour former des électrodes nanogap avec des largeurs latérales élevées (100μm), avec des écarts démontrés au-dessous de 7 nm. La combinaison de ces techniques aboutit à un procédé de fabrication à haut rendement et à faible besoin pour la construction de SET complets. A partir des transistors résultants, de fines lamelles ont été préparées à l'aide de FIB et des modèles 3D ont été reconstruits par tomographie TEM pour analyse. La caractérisation électrique a été effectuée jusqu'à 77K, avec une modélisation révélant le transport de Poole-Frenkel en parallèle à un éventuel cotunneling. Des blocus de Coulomb stables, la signature des SET, ont été observés avec une périodicité régulière et étaient identifiables jusqu'à 170K. L'optimisation de ce processus pourrait produire des SETs de surface élevée capables de fonctionner de manière stable à température ambiante. / The introduction of the single electron transistor (SET) shook the semiconductor industry, with promises of unrivaled efficiency. However, the cost and complexity associated with achieving stable operation have heavily hindered their adoption. Having fallen out of the graces of industry, academic research has continued to push, demonstrating novel techniques for SET creation. At the core of this stability issue is a need to controllably build nanoislands smaller than 10nm. Among the methods available for this nanoisland formation, atomic layer deposition (ALD) sets itself apart as an industrially scalable, highly controllable process. The second barrier to entry is the creation of nanogap electrodes, used to inject current through these nanoislands, for which researchers have leaned heavily on non-scalable fabrication techniques such as electron beam lithography and focused ion beam. The shadow edge evaporation technique overcomes the complexity and scaling issues of nanogap fabrication, opening new possibilities. In this work, ALD will be demonstrated as a superb technique for growing vast 3D arrays of sub 2nm platinum nanoparticles encapsulated in Al2O3. ALD provided a means of growing these nanoparticle matrices in a single process, under vacuum, and at low temperatures. Through shadow edge evaporation, UV lithography was then utilized to form nanogap electrodes with high lateral widths (100µm), with gaps demonstrated below 7nm. The combination of these techniques results in a high yield, low requirement fabrication process for building full SETs. From the resulting transistors, thin lamellas were prepared using FIB and 3D models were reconstructed via TEM tomography for analysis. Electrical characterization was performed down to 77K, with modeling revealing Poole-Frenkel transport alongside possible cotunneling. Stable Coulomb blockades, the signature of SETs, were observed with regular periodicity and were identifiable up to 170K. Optimization of this process could yield high surface area SETs capable of stable operation at room temperature.