60 research outputs found
Reconstruction et correction de modèles urbains à l'aide de structures de données cinétiques
No full textCompact and accurate digital 3D models of buildings are commonly used by practitioners for the visualization of existing or imaginary environments, the physical simulations or the fabrication of urban objects. Generating such ready-to-use models is however a difficult problem. When created by designers, 3D models usually contain geometric errors whose automatic correction is a scientific challenge. When created from data measurements, typically laser scans or multiview images, the accuracy and complexity of the models produced by existing reconstruction algorithms often do not reach the requirements of the practitioners. In this thesis, I address this problem by proposing two algorithms: one for repairing the geometric errors contained in urban-specific formats of 3D models, and one for reconstructing compact and accurate models from input point clouds generated from laser scanning or multiview stereo imagery. The key component of these algorithms relies upon a space-partitioning data structure able to decompose the space into polyhedral cells in a natural and efficient manner. This data structure is used to both correct geometric errors by reassembling the facets of defect-laden 3D models, and reconstruct concise 3D models from point clouds with a quality that approaches those generated by Computer-Aided-Design interactive tools.My first contribution is an algorithm to repair different types of urban models. Prior work, which traditionally relies on local analysis and heuristic-based geometric operations on mesh data structures, is typically tailored-made for specific 3D formats and urban objects. We propose a more general method to process different types of urban models without tedious parameter tuning. The key idea lies on the construction of a kinetic data structure that decomposes the 3D space into polyhedra by extending the facets of the imperfect input model. Such a data structure allows us to re-build all the relations between the facets in an efficient and robust manner. Once built, the cells of the polyhedral partition are regrouped by semantic classes to reconstruct the corrected output model. I demonstrate the robustness and efficiency of the algorithm on a variety of real-world defect-laden models and show its competitiveness with respect to traditional mesh repairing techniques from both Building Information Modeling (BIM) and Geographic Information Systems (GIS) data.My second contribution is a reconstruction algorithm inspired by the Kinetic Shape Reconstruction method, that improves the later in different ways. In particular, I propose a data fitting technique for detecting planar primitives from unorganized 3D point clouds. Departing from an initial configuration, the technique refines both the continuous plane parameters and the discrete assignment of input points to them by seeking high fidelity, high simplicity and high completeness. The solution is found by an exploration mechanism guided by a multi-objective energy function. The transitions within the large solution space are handled by five geometric operators that create, remove and modify primitives. I demonstrate its potential, not on buildings only, but on a variety of scenes, from organic shapes to man-made objects.Les modèles numériques 3D compacts et précis de bâtiments sont couramment utilisés par les praticiens pour la visualisation d'environnements existants ou imaginaires, les simulations physiques ou la fabrication d'objets urbains. La génération de tels modèles prêts à l'emploi est cependant un problème difficile. Lorsqu'ils sont créés par des designers, les modèles 3D contiennent généralement des erreurs géométriques dont la correction automatique est un défi scientifique. Lorsqu'ils sont créés à partir de mesures de données, généralement des balayages laser ou des images multivues, la précision et la complexité des modèles produits par les algorithmes de reconstruction existants n'atteignent souvent pas les exigences des praticiens. Dans cette thèse, j'aborde ce problème en proposant deux algorithmes : l'un pour réparer les erreurs géométriques contenues dans les formats spécifiques de modèles de bâtiments, et l'autre pour reconstruire des modèles compacts et précis à partir de nuages de points générés à partir d'un balayage laser ou d'images stéréo multivues. Le composant clé de ces algorithmes repose sur une structure de données de partitionnement d'espace capable de décomposer l'espace en cellules polyédriques de manière naturelle et efficace. Cette structure de données permet à la fois de corriger les erreurs géométriques en réassemblant les facettes de modèles 3D chargés de défauts, et de reconstruire des modèles 3D à partir de nuages de points avec une précision et complexité proche de celles générées par les outils interactifs de Conception Assistée par Ordinateur.Ma première contribution est un algorithme pour réparer différents types de modèles urbains. Les travaux antérieurs, qui reposent traditionnellement sur une analyse locale et des heuristiques géométriques sur des maillages, sont généralement conçus sur-mesure pour des formats 3D et des objets urbains spécifiques. Nous proposons une méthode plus générale pour traiter différents types de modèles urbains sans réglage fastidieux des paramètres. L'idée clé repose sur la construction d'une structure de données cinétiques qui décompose l'espace 3D en polyèdres en étendant les facettes du modèle d'entrée imparfait. Une telle structure de données permet de reconstruire toutes les relations entre les facettes de manière efficace et robuste. Une fois construites, les cellules de la partition polyédrique sont regroupées par classes sémantiques pour reconstruire le modèle de sortie corrigé. Je démontre la robustesse et l'efficacité de l'algorithme sur une variété de modèles réels chargés de défauts et montre sa compétitivité par rapport aux techniques traditionnelles de réparation de maillage à partir de données de modélisation des informations du bâtiment (BIM) et de systèmes d'information géographique (SIG). Ma deuxième contribution est un algorithme de reconstruction inspiré de la méthode Kinetic Shape Reconstruction, qui améliore cette dernière de différentes manières. En particulier, je propose une technique pour détecter des primitives planaires à partir de nuages de points 3D non organisés. Partant d'une configuration initiale, la technique affine à la fois les paramètres du plan continu et l'affectation discrète de points d'entrée à ceux-ci en recherchant une haute fidélité, une grande simplicité et une grande complétude. La solution est trouvée par un mécanisme d'exploration guidé par une fonction énergétique à objectifs multiples. Les transitions dans le grand espace des solutions sont gérées par cinq opérateurs géométriques qui créent, suppriment et modifient les primitives. Je démontre son potentiel, non seulement sur des bâtiments, mais sur une variété de scènes, des formes organiques aux objets fabriqués par l'homme
Reconstructing and repairing urban models with kinetic data structures
No full textLes modèles numériques 3D compacts et précis de bâtiments sont couramment utilisés par les praticiens pour la visualisation d'environnements existants ou imaginaires, les simulations physiques ou la fabrication d'objets urbains. La génération de tels modèles prêts à l'emploi est cependant un problème difficile. Lorsqu'ils sont créés par des designers, les modèles 3D contiennent généralement des erreurs géométriques dont la correction automatique est un défi scientifique. Lorsqu'ils sont créés à partir de mesures de données, généralement des balayages laser ou des images multivues, la précision et la complexité des modèles produits par les algorithmes de reconstruction existants n'atteignent souvent pas les exigences des praticiens. Dans cette thèse, j'aborde ce problème en proposant deux algorithmes : l'un pour réparer les erreurs géométriques contenues dans les formats spécifiques de modèles de bâtiments, et l'autre pour reconstruire des modèles compacts et précis à partir de nuages de points générés à partir d'un balayage laser ou d'images stéréo multivues. Le composant clé de ces algorithmes repose sur une structure de données de partitionnement d'espace capable de décomposer l'espace en cellules polyédriques de manière naturelle et efficace. Cette structure de données permet à la fois de corriger les erreurs géométriques en réassemblant les facettes de modèles 3D chargés de défauts, et de reconstruire des modèles 3D à partir de nuages de points avec une précision et complexité proche de celles générées par les outils interactifs de Conception Assistée par Ordinateur.Ma première contribution est un algorithme pour réparer différents types de modèles urbains. Les travaux antérieurs, qui reposent traditionnellement sur une analyse locale et des heuristiques géométriques sur des maillages, sont généralement conçus sur-mesure pour des formats 3D et des objets urbains spécifiques. Nous proposons une méthode plus générale pour traiter différents types de modèles urbains sans réglage fastidieux des paramètres. L'idée clé repose sur la construction d'une structure de données cinétiques qui décompose l'espace 3D en polyèdres en étendant les facettes du modèle d'entrée imparfait. Une telle structure de données permet de reconstruire toutes les relations entre les facettes de manière efficace et robuste. Une fois construites, les cellules de la partition polyédrique sont regroupées par classes sémantiques pour reconstruire le modèle de sortie corrigé. Je démontre la robustesse et l'efficacité de l'algorithme sur une variété de modèles réels chargés de défauts et montre sa compétitivité par rapport aux techniques traditionnelles de réparation de maillage à partir de données de modélisation des informations du bâtiment (BIM) et de systèmes d'information géographique (SIG). Ma deuxième contribution est un algorithme de reconstruction inspiré de la méthode Kinetic Shape Reconstruction, qui améliore cette dernière de différentes manières. En particulier, je propose une technique pour détecter des primitives planaires à partir de nuages de points 3D non organisés. Partant d'une configuration initiale, la technique affine à la fois les paramètres du plan continu et l'affectation discrète de points d'entrée à ceux-ci en recherchant une haute fidélité, une grande simplicité et une grande complétude. La solution est trouvée par un mécanisme d'exploration guidé par une fonction énergétique à objectifs multiples. Les transitions dans le grand espace des solutions sont gérées par cinq opérateurs géométriques qui créent, suppriment et modifient les primitives. Je démontre son potentiel, non seulement sur des bâtiments, mais sur une variété de scènes, des formes organiques aux objets fabriqués par l'homme.Compact and accurate digital 3D models of buildings are commonly used by practitioners for the visualization of existing or imaginary environments, the physical simulations or the fabrication of urban objects. Generating such ready-to-use models is however a difficult problem. When created by designers, 3D models usually contain geometric errors whose automatic correction is a scientific challenge. When created from data measurements, typically laser scans or multiview images, the accuracy and complexity of the models produced by existing reconstruction algorithms often do not reach the requirements of the practitioners. In this thesis, I address this problem by proposing two algorithms: one for repairing the geometric errors contained in urban-specific formats of 3D models, and one for reconstructing compact and accurate models from input point clouds generated from laser scanning or multiview stereo imagery. The key component of these algorithms relies upon a space-partitioning data structure able to decompose the space into polyhedral cells in a natural and efficient manner. This data structure is used to both correct geometric errors by reassembling the facets of defect-laden 3D models, and reconstruct concise 3D models from point clouds with a quality that approaches those generated by Computer-Aided-Design interactive tools.My first contribution is an algorithm to repair different types of urban models. Prior work, which traditionally relies on local analysis and heuristic-based geometric operations on mesh data structures, is typically tailored-made for specific 3D formats and urban objects. We propose a more general method to process different types of urban models without tedious parameter tuning. The key idea lies on the construction of a kinetic data structure that decomposes the 3D space into polyhedra by extending the facets of the imperfect input model. Such a data structure allows us to re-build all the relations between the facets in an efficient and robust manner. Once built, the cells of the polyhedral partition are regrouped by semantic classes to reconstruct the corrected output model. I demonstrate the robustness and efficiency of the algorithm on a variety of real-world defect-laden models and show its competitiveness with respect to traditional mesh repairing techniques from both Building Information Modeling (BIM) and Geographic Information Systems (GIS) data.My second contribution is a reconstruction algorithm inspired by the Kinetic Shape Reconstruction method, that improves the later in different ways. In particular, I propose a data fitting technique for detecting planar primitives from unorganized 3D point clouds. Departing from an initial configuration, the technique refines both the continuous plane parameters and the discrete assignment of input points to them by seeking high fidelity, high simplicity and high completeness. The solution is found by an exploration mechanism guided by a multi-objective energy function. The transitions within the large solution space are handled by five geometric operators that create, remove and modify primitives. I demonstrate its potential, not on buildings only, but on a variety of scenes, from organic shapes to man-made objects
Reconstruction et correction de modèles urbains à l'aide de structures de données cinétiques
No full textCompact and accurate digital 3D models of buildings are commonly used by practitioners for the visualization of existing or imaginary environments, the physical simulations or the fabrication of urban objects. Generating such ready-to-use models is however a difficult problem. When created by designers, 3D models usually contain geometric errors whose automatic correction is a scientific challenge. When created from data measurements, typically laser scans or multiview images, the accuracy and complexity of the models produced by existing reconstruction algorithms often do not reach the requirements of the practitioners. In this thesis, I address this problem by proposing two algorithms: one for repairing the geometric errors contained in urban-specific formats of 3D models, and one for reconstructing compact and accurate models from input point clouds generated from laser scanning or multiview stereo imagery. The key component of these algorithms relies upon a space-partitioning data structure able to decompose the space into polyhedral cells in a natural and efficient manner. This data structure is used to both correct geometric errors by reassembling the facets of defect-laden 3D models, and reconstruct concise 3D models from point clouds with a quality that approaches those generated by Computer-Aided-Design interactive tools.My first contribution is an algorithm to repair different types of urban models. Prior work, which traditionally relies on local analysis and heuristic-based geometric operations on mesh data structures, is typically tailored-made for specific 3D formats and urban objects. We propose a more general method to process different types of urban models without tedious parameter tuning. The key idea lies on the construction of a kinetic data structure that decomposes the 3D space into polyhedra by extending the facets of the imperfect input model. Such a data structure allows us to re-build all the relations between the facets in an efficient and robust manner. Once built, the cells of the polyhedral partition are regrouped by semantic classes to reconstruct the corrected output model. I demonstrate the robustness and efficiency of the algorithm on a variety of real-world defect-laden models and show its competitiveness with respect to traditional mesh repairing techniques from both Building Information Modeling (BIM) and Geographic Information Systems (GIS) data.My second contribution is a reconstruction algorithm inspired by the Kinetic Shape Reconstruction method, that improves the later in different ways. In particular, I propose a data fitting technique for detecting planar primitives from unorganized 3D point clouds. Departing from an initial configuration, the technique refines both the continuous plane parameters and the discrete assignment of input points to them by seeking high fidelity, high simplicity and high completeness. The solution is found by an exploration mechanism guided by a multi-objective energy function. The transitions within the large solution space are handled by five geometric operators that create, remove and modify primitives. I demonstrate its potential, not on buildings only, but on a variety of scenes, from organic shapes to man-made objects.Les modèles numériques 3D compacts et précis de bâtiments sont couramment utilisés par les praticiens pour la visualisation d'environnements existants ou imaginaires, les simulations physiques ou la fabrication d'objets urbains. La génération de tels modèles prêts à l'emploi est cependant un problème difficile. Lorsqu'ils sont créés par des designers, les modèles 3D contiennent généralement des erreurs géométriques dont la correction automatique est un défi scientifique. Lorsqu'ils sont créés à partir de mesures de données, généralement des balayages laser ou des images multivues, la précision et la complexité des modèles produits par les algorithmes de reconstruction existants n'atteignent souvent pas les exigences des praticiens. Dans cette thèse, j'aborde ce problème en proposant deux algorithmes : l'un pour réparer les erreurs géométriques contenues dans les formats spécifiques de modèles de bâtiments, et l'autre pour reconstruire des modèles compacts et précis à partir de nuages de points générés à partir d'un balayage laser ou d'images stéréo multivues. Le composant clé de ces algorithmes repose sur une structure de données de partitionnement d'espace capable de décomposer l'espace en cellules polyédriques de manière naturelle et efficace. Cette structure de données permet à la fois de corriger les erreurs géométriques en réassemblant les facettes de modèles 3D chargés de défauts, et de reconstruire des modèles 3D à partir de nuages de points avec une précision et complexité proche de celles générées par les outils interactifs de Conception Assistée par Ordinateur.Ma première contribution est un algorithme pour réparer différents types de modèles urbains. Les travaux antérieurs, qui reposent traditionnellement sur une analyse locale et des heuristiques géométriques sur des maillages, sont généralement conçus sur-mesure pour des formats 3D et des objets urbains spécifiques. Nous proposons une méthode plus générale pour traiter différents types de modèles urbains sans réglage fastidieux des paramètres. L'idée clé repose sur la construction d'une structure de données cinétiques qui décompose l'espace 3D en polyèdres en étendant les facettes du modèle d'entrée imparfait. Une telle structure de données permet de reconstruire toutes les relations entre les facettes de manière efficace et robuste. Une fois construites, les cellules de la partition polyédrique sont regroupées par classes sémantiques pour reconstruire le modèle de sortie corrigé. Je démontre la robustesse et l'efficacité de l'algorithme sur une variété de modèles réels chargés de défauts et montre sa compétitivité par rapport aux techniques traditionnelles de réparation de maillage à partir de données de modélisation des informations du bâtiment (BIM) et de systèmes d'information géographique (SIG). Ma deuxième contribution est un algorithme de reconstruction inspiré de la méthode Kinetic Shape Reconstruction, qui améliore cette dernière de différentes manières. En particulier, je propose une technique pour détecter des primitives planaires à partir de nuages de points 3D non organisés. Partant d'une configuration initiale, la technique affine à la fois les paramètres du plan continu et l'affectation discrète de points d'entrée à ceux-ci en recherchant une haute fidélité, une grande simplicité et une grande complétude. La solution est trouvée par un mécanisme d'exploration guidé par une fonction énergétique à objectifs multiples. Les transitions dans le grand espace des solutions sont gérées par cinq opérateurs géométriques qui créent, suppriment et modifient les primitives. Je démontre son potentiel, non seulement sur des bâtiments, mais sur une variété de scènes, des formes organiques aux objets fabriqués par l'homme
Finding Good Configurations of Planar Primitives in Unorganized Point Clouds
No full textInternational audienceWe present an algorithm for detecting planar primitives from unorganized 3D point clouds. Departing from an initial configuration, the algorithm refines both the continuous plane parameters and the discrete assignment of input points to them by seeking high fidelity, high simplicity and high completeness. Our key contribution relies upon the design of an exploration mechanism guided by a multiobjective energy function. The transitions within the large solution space are handled by five geometric operators that create, remove and modify primitives. We demonstrate the potential of our method on a variety of scenes, from organic shapes to man-made objects, and sensors, from multiview stereo to laser. We show its efficacy with respect to existing primitive fitting approaches and illustrate its applicative interest in compact mesh reconstruction, when combined with a plane assembly method
Finding Good Configurations of Planar Primitives in Unorganized Point Clouds
Get PDFInternational audienceWe present an algorithm for detecting planar primitives from unorganized 3D point clouds. Departing from an initial configuration, the algorithm refines both the continuous plane parameters and the discrete assignment of input points to them by seeking high fidelity, high simplicity and high completeness. Our key contribution relies upon the design of an exploration mechanism guided by a multiobjective energy function. The transitions within the large solution space are handled by five geometric operators that create, remove and modify primitives. We demonstrate the potential of our method on a variety of scenes, from organic shapes to man-made objects, and sensors, from multiview stereo to laser. We show its efficacy with respect to existing primitive fitting approaches and illustrate its applicative interest in compact mesh reconstruction, when combined with a plane assembly method
Sharp Feature Consolidation from Raw 3D Point Clouds via Displacement Learning
No full textInternational audienceDetecting sharp features in raw point clouds is an essential step in designing efficient priors in several 3D Vision applications. This paper presents a deep learning-based approach that learns to detect and consolidate sharp feature points on raw 3D point clouds. We devise a multi-task neural network architecture that identifies points near sharp features and predicts displacement vectors toward the local sharp features. The so-detected points are thus consolidated via relocation. Our approach is robust against noise by utilizing a dynamic labeling oracle during the training phase. The approach is also flexible and can be combined with several popular point-based network architectures. Our experiments demonstrate that our approach outperforms the previous work in terms of detection accuracy measured on the popular ABC dataset. We show the efficacy of the proposed approach by applying it to several 3D Vision tasks
Exploring genetic associations with ceRNA regulation in the human genome
Get PDFabstract: Competing endogenous RNAs (ceRNAs) are RNA molecules that sequester shared microRNAs (miRNAs) thereby affecting the expression of other targets of the miRNAs. Whether genetic variants in ceRNA can affect its biological function and disease development is still an open question. Here we identified a large number of genetic variants that are associated with ceRNA's function using Geuvaids RNA-seq data for 462 individuals from the 1000 Genomes Project. We call these loci competing endogenous RNA expression quantitative trait loci or ‘cerQTL’, and found that a large number of them were unexplored in conventional eQTL mapping. We identified many cerQTLs that have undergone recent positive selection in different human populations, and showed that single nucleotide polymorphisms in gene 3΄UTRs at the miRNA seed binding regions can simultaneously regulate gene expression changes in both cis and trans by the ceRNA mechanism. We also discovered that cerQTLs are significantly enriched in traits/diseases associated variants reported from genome-wide association studies in the miRNA binding sites, suggesting that disease susceptibilities could be attributed to ceRNA regulation. Further in vitro functional experiments demonstrated that a cerQTL rs11540855 can regulate ceRNA function. These results provide a comprehensive catalog of functional non-coding regulatory variants that may be responsible for ceRNA crosstalk at the post-transcriptional level.The final version of this article, as published in Nucleic Acids Research, can be viewed online at: https://academic.oup.com/nar/article-lookup/doi/10.1093/nar/gkx33
cepip: context-dependent epigenomic weighting for prioritization of regulatory variants and disease-associated genes
Get PDFabstract: It remains challenging to predict regulatory variants in particular tissues or cell types due to highly context-specific gene regulation. By connecting large-scale epigenomic profiles to expression quantitative trait loci (eQTLs) in a wide range of human tissues/cell types, we identify critical chromatin features that predict variant regulatory potential. We present cepip, a joint likelihood framework, for estimating a variant’s regulatory probability in a context-dependent manner. Our method exhibits significant GWAS signal enrichment and is superior to existing cell type-specific methods. Furthermore, using phenotypically relevant epigenomes to weight the GWAS single-nucleotide polymorphisms, we improve the statistical power of the gene-based association test.The electronic version of this article is the complete one and can be found online at: https://genomebiology.biomedcentral.com/articles/10.1186/s13059-017-1177-
Robust and rapid algorithms facilitate large-scale whole genome sequencing downstream analysis in an integrative framework
Get PDFabstract: Whole genome sequencing (WGS) is a promising strategy to unravel variants or genes responsible for human diseases and traits. However, there is a lack of robust platforms for a comprehensive downstream analysis. In the present study, we first proposed three novel algorithms, sequence gap-filled gene feature annotation, bit-block encoded genotypes and sectional fast access to text lines to address three fundamental problems. The three algorithms then formed the infrastructure of a robust parallel computing framework, KGGSeq, for integrating downstream analysis functions for whole genome sequencing data. KGGSeq has been equipped with a comprehensive set of analysis functions for quality control, filtration, annotation, pathogenic prediction and statistical tests. In the tests with whole genome sequencing data from 1000 Genomes Project, KGGSeq annotated several thousand more reliable non-synonymous variants than other widely used tools (e.g. ANNOVAR and SNPEff). It took only around half an hour on a small server with 10 CPUs to access genotypes of ∼60 million variants of 2504 subjects, while a popular alternative tool required around one day. KGGSeq's bit-block genotype format used 1.5% or less space to flexibly represent phased or unphased genotypes with multiple alleles and achieved a speed of over 1000 times faster to calculate genotypic correlation.The final version of this article, as published in Nucleic Acids Research, can be viewed online at: https://academic.oup.com/nar/article-lookup/doi/10.1093/nar/gkx01
KIBS: 3D detection of planar roof sections from a single satellite image
No full textInternational audienceReconstructing urban areas in 3D from satellite raster images has been a longstanding problem for both academical and industrial research. While automatic methods achieving this objective at a Level Of Detail (LOD) 1 are mostly efficient today, producing LOD2 models is still a scientific challenge. In particular, the quality and resolution of satellite data is too low to infer accurately the planar roof sections in 3D by using traditional plane detection algorithms. Existing methods rely upon the exploitation of both strong urban priors that reduce their applicability to a variety of environments and multi-modal data, including some derived 3D products such as Digital Surface Models. In this work, we address this issue with KIBS (Keypoints Inference By Segmentation), a method that detects planar roof sections in 3D from a single-view satellite image. By exploiting largescale LOD2 databases produced by human operators with efficient neural architectures, we manage to both segment roof sections in images and extract keypoints enclosing these sections in 3D to form 3D-polygons with a low-complexity. The output set of 3D-polygons can be used to reconstruct LOD2 models of buildings when combined with a plane assembly method. While conceptually simple, our method manages to capture roof sections as 3D-polygons with a good accuracy, from a single satellite image only by learning indirect 3D information contained in the image, in particular from the view inclination, the distortion of facades, the building shadows, roof peak and ridge perspective. We demonstrate the potential of KIBS by reconstructing large urban areas in a few minutes, with a Jaccard index for the 2D segmentation of individual roof sections of approximately 80%
- …
