NURBS surfaces are compact parametric representations widely used in Computer-Aided Design (CAD) modeling. Decomposing raw 3D data measurements into a set of such elements is a challenging problem that existing methods approach by learning from CAD databases to both segment synthetic data and fit parametric shapes on each segment. Unfortunately, these methods generalize poorly to raw data measurements, with low robustness to imperfect data and complex objects and low scalability. To address this issue, we propose NURBSFIT, an algorithm that fits NURBS surfaces to unorganized 3D point clouds, such as those generated by laser and photogrammetry acquisition systems. Starting with a fine configuration of planar patches that approximate the object geometry, our algorithm performs merging operations that progressively regroup pairs of adjacent patches into fewer, more expressive NURBS surfaces. This process is designed to be both robust and performant with a series of technical ingredients that include an energy that controls the global quality of a configuration of NURBS surfaces and an efficient ordering of the merging operations based on a cost-efficient quadric surface fitting analysis. We show the potential of our algorithm on both synthetic and real-world data and its efficiency against existing primitive fitting methods with results both simpler and geometrically more accurate. Our implementation is available at: https://github.com/lizOnly/nurbsfit

We 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 multi-objective 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.

Traditional Convolutional Neural Networks (CNN) for semantic segmentation of images use 2D convolution operations. While the spatial inductive bias of 2D convolutions allow CNNs to build hierarchical feature representations, they require that the whole feature maps are kept in memory until the end of the inference. This is not ideal for memory and latency-critical applications such as real-time on-board satellite image segmentation. In this paper, we propose a new neural network architecture for semantic segmentation, “ScannerNet”, based on a Recurrent 1D Convolutional architecture. Our network performs a segmentation of the input image line-by-line, and thus reduces the memory footprint and output latency. These characteristics make it ideal for on-the-fly segmentation of images on-board satellites equipped with push broom sensors such as Landsat 8, or satellites with limited compute capabilities, such as Cubesats. We perform cloud segmentation experiments on embedded hardware and show that our method offers a good compromise between accuracy, memory usage and latency.

Abstract We address the problem of simplifying two‐dimensional polygonal partitions that exhibit strong regularities. Such partitions are relevant for reconstructing urban scenes in a concise way. Preserving long linear structures spanning several partition cells motivates a point‐line projective duality approach in which points represent line intersections, and lines possibly carry multiple points. We propose a simplification algorithm that seeks a balance between the fidelity to the input partition, the enforcement of canonical relationships between lines (orthogonality or parallelism) and a low complexity output. Our methodology alternates continuous optimization by Riemannian gradient descent with combinatorial reduction, resulting in a progressive simplification scheme. Our experiments show that preserving canonical relationships helps gracefully degrade partitions of urban scenes, and yields more concise and regularity‐preserving meshes than common mesh‐based simplification approaches.

Converting point clouds generated by Laser scanning, multiview stereo imagery or depth cameras into compact polygon meshes is a challenging problem in vision. Existing methods are either robust to imperfect data or scalable, but rarely both. In this paper, we address this issue with an hybrid method that successively connects and slices planes detected from 3D data. The core idea consists in constructing an efficient and compact partitioning data structure. The later is i) spatially-adaptive in the sense that a plane slices a restricted number of relevant planes only, and ii) composed of components with different structural meaning resulting from a preliminary analysis of the plane connectivity. Our experiments on a variety of objects and sensors show the versatility of our approach as well as its competitiveness with respect to existing methods.

We present an algorithm for extracting and vectorizing objects in images with polygons. Departing from a polygonal partition that oversegments an image into convex cells, the algorithm refines the geometry of the partition while labeling its cells by a semantic class. The result is a set of polygons, each capturing an object in the image. The quality of a configuration is measured by an energy that accounts for both the fidelity to input data and the complexity of the output polygons. To efficiently explore the configuration space, we perform splitting and merging operations in tandem on the cells of the polygonal partition. The exploration mechanism is controlled by a priority queue that sorts the operations most likely to decrease the energy. We show the potential of our algorithm on different types of scenes, from organic shapes to man-made objects through floor maps, and demonstrate its efficiency compared to existing vectorization methods.

We introduce Delaunay Point Processes, a framework for the extraction of geometric structures from images. Our approach simultaneously locates and groups geometric primitives (line segments, triangles) to form extended structures (line networks, polygons) for a variety of image analysis tasks. Similarly to traditional point processes, our approach uses Markov Chain Monte Carlo to minimize an energy that balances fidelity to the input image data with geometric priors on the output structures. However, while existing point processes struggle to model structures composed of inter-connected components, we propose to embed the point process into a Delaunay triangulation, which provides high-quality connectivity by construction. We further leverage key properties of the Delaunay triangulation to devise a fast Markov Chain Monte Carlo sampler. We demonstrate the flexibility of our approach on a variety of applications, including line network extraction, object contouring, and mesh-based image compression.

Converting point clouds into concise polygonal meshes in an automated manner is an enduring problem in computer graphics. Prior works, which typically operate by assembling planar shapes detected from input points, largely overlooked the scalability issue of processing a large number of shapes. As a result, they tend to produce overly simplified meshes with assembling approaches that can hardly digest more than 100 shapes in practice. We propose a shape assembling mechanism that is at least one order of magnitude more efficient, both in time and in number of processed shapes. Our key idea relies upon the design of a kinetic data structure for partitioning the space into convex polyhedra. Instead of slicing all the planar shapes exhaustively as prior methods, we create a partition where shapes grow at constant speed until colliding and forming polyhedra. This simple idea produces a lighter yet meaningful partition with a lower algorithmic complexity than an exhaustive partition. A watertight polygonal mesh is then extracted from the partition with a min-cut formulation. We demonstrate the robustness and efficacy of our algorithm on a variety of objects and scenes in terms of complexity, size, and acquisition characteristics. In particular, we show the method can both faithfully represent piecewise planar structures and approximate freeform objects while offering high resilience to occlusions and missing data.

The generation of 3D building models from Very High Resolution geospatial data is now an automatized procedure. However, urban areas are very complex and practitioners still have to visually assess the correctness of these models and detect reconstruction errors. We proposed an approach for automatically evaluating the quality of 3D building models. It is cast as a supervised classification task based on a hierarchical taxonomy and multimodal handcrafted features (building geometry, optical images, height data). In this paper, we evaluate how the urban area composition impacts prediction transferability and scalability of our framework to unseen scenes. This allows to define minimal feature and training sets for a problem where no benchmark data has been released so far.

Recent works showed that floating polygons can be an interesting alternative to traditional superpixels, especially for analyzing scenes with strong geometric signatures, as man-made environments. Existing algorithms produce homogeneously-sized polygons that fail to capture thin geometric structures and over-partition large uniform areas. We propose a kinetic approach that brings more flexibility on polygon shape and size. The key idea consists in progressively extending pre-detected line-segments until they meet each other. Our experiments demonstrate that output partitions both contain less polygons and better capture geometric structures than those delivered by existing methods. We also show the applicative potential of the method when used as preprocessing in object contouring.

Interpreting 3D data such as point clouds or surface meshes depends heavily on the scale of observation. Yet, existing algorithms for shape detection rely on trial-and-error parameter tunings to output configurations representative of a structural scale. We present a framework to automatically extract a set of representations that capture the shape and structure of man-made objects at different key Abstraction levels. A shape-collapsing process first generates a fine-to-coarse sequence of shape representations by exploiting local planarity. This sequence is then analyzed to identify significant geometric variations between successive representations through a supervised energy minimization. Our framework is flexible enough to learn how to detect both existing structural formalisms such as the CityGML Levels Of Details, and expert-specified levels of Abstraction. Experiments on different input data and classes of man-made objects, as well as comparisons with existing shape detection methods, illustrate the strengths of our approach in terms of efficiency and flexibility.

We present a method to create vector cliparts from photographs. Our approach aims at reproducing two key properties of cliparts: they should be easily editable, and they should represent image content in a clean, simplified way. We observe that vector artists satisfy both of these properties by modeling cliparts with linear color gradients, which have a small number of parameters and approximate well smooth color variations. In addition, skilled artists produce intricate yet editable artworks by stacking multiple gradients using opaque and semi-transparent layers. Motivated by these observations, our goal is to decompose a bitmap photograph into a stack of layers, each layer containing a vector path filled with a linear color gradient. We cast this problem as an optimization that jointly assigns each pixel to one or more layer and finds the gradient parameters of each layer that best reproduce the input. Since a trivial solution would consist in assigning each pixel to a different, opaque layer, we complement our objective with a simplicity term that favors decompositions made of few, semi-transparent layers. However, this formulation results in a complex combinatorial problem combining discrete unknowns (the pixel assignments) and continuous unknowns (the layer parameters). We propose a Monte Carlo Tree Search algorithm that efficiently explores this solution space by leveraging layering cues at image junctions. We demonstrate the effectiveness of our method by reverse-engineering existing cliparts and by creating original cliparts from studio photographs.

Abstract We present a method for planar shape detection and regularization from raw point sets. The geometric modelling and processing of man‐made environments from measurement data often relies upon robust detection of planar primitive shapes. In addition, the detection and reinforcement of regularities between planar parts is a means to increase resilience to missing or defect‐laden data as well as to reduce the complexity of models and algorithms down the modelling pipeline. The main novelty behind our method is to perform detection and regularization in tandem. We first sample a sparse set of seeds uniformly on the input point set, and then perform in parallel shape detection through region growing, interleaved with regularization through detection and reinforcement of regular relationships (coplanar, parallel and orthogonal). In addition to addressing the end goal of regularization, such reinforcement also improves data fitting and provides guidance for clustering small parts into larger planar parts. We evaluate our approach against a wide range of inputs and under four criteria: geometric fidelity, coverage, regularity and running times. Our approach compares well with available implementations such as the efficient random sample consensus–based approach proposed by Schnabel and co‐authors in 2007.

Vector drawing is a popular representation in graphic design because of the precision, compactness and editability offered by parametric curves. However, prior work on line drawing vectorization focused solely on faithfully capturing input bitmaps, and largely overlooked the problem of producing a compact and editable curve network. As a result, existing algorithms tend to produce overly-complex drawings composed of many short curves and control points, especially in the presence of thick or sketchy lines that yield spurious curves at junctions. We propose the first vectorization algorithm that explicitly balances fidelity to the input bitmap with simplicity of the output, as measured by the number of curves and their degree. By casting this trade-off as a global optimization, our algorithm generates few yet accurate curves, and also disambiguates curve topology at junctions by favoring the simplest interpretations overall. We demonstrate the robustness of our algorithm on a variety of drawings, sketchy cartoons and rough design sketches.

The over-segmentation of images into atomic regions has become a standard and powerful tool in Vision. Traditional superpixel methods, that operate at the pixel level, cannot directly capture the geometric information disseminated into the images. We propose an alternative to these methods by operating at the level of geometric shapes. Our algorithm partitions images into convex polygons. It presents several interesting properties in terms of geometric guarantees, region compactness and scalability. The overall strategy consists in building a Voronoi diagram that conforms to preliminarily detected line-segments, before homogenizing the partition by spatial point process distributed over the image gradient. Our method is particularly adapted to images with strong geometric signatures, typically man-made objects and environments. We show the potential of our approach with experiments on large-scale images and comparisons with state-of-the-art superpixel methods.

Many design tasks involve the creation of new objects in the context of an existing scene. Existing work in computer vision only provides partial support for such tasks. On the one hand, multi-view stereo algorithms allow the reconstruction of real-world scenes, while on the other hand algorithms for line-drawing interpretation do not take context into account. Our work combines the strength of these two domains to interpret line drawings of imaginary objects drawn over photographs of an existing scene. The main challenge we face is to identify the existing 3D structure that correlates with the line drawing while also allowing the creation of new structure that is not present in the real world. We propose a labeling algorithm to tackle this problem, where some of the labels capture dominant orientations of the real scene while a free label allows the discovery of new orientations in the imaginary scene. We illustrate our algorithm by interpreting line drawings for urban planing, home remodeling, furniture design and cultural heritage.

Abstract We present a novel approach for the decimation of triangle surface meshes. Our algorithm takes as input a triangle surface mesh and a set of planar proxies detected in a pre‐processing analysis step, and structured via an adjacency graph. It then performs greedy mesh decimation through a series of edge collapse, designed to approximate the local mesh geometry as well as the geometry and structure of proxies. Such structure‐preserving approach is well suited to planar abstraction, i.e. extreme decimation approximating well the planar parts while filtering out the others. Our experiments on a variety of inputs illustrate the potential of our approach in terms of improved accuracy and preservation of structure.

We introduce a novel approach that reconstructs 3D urban scenes in the form of levels of detail (LODs). Starting from raw datasets such as surface meshes generated by multiview stereo systems, our algorithm proceeds in three main steps: classification, abstraction, and reconstruction. From geometric attributes and a set of semantic rules combined with a Markov random field, we classify the scene into four meaningful classes. The abstraction step detects and regularizes planar structures on buildings, fits icons on trees, roofs, and facades, and performs filtering and simplification for LOD generation. The abstracted data are then provided as input to the reconstruction step which generates watertight buildings through a min-cut formulation on a set of 3D arrangements. Our experiments on complex buildings and large-scale urban scenes show that our approach generates meaningful LODs while being robust and scalable. By combining semantic segmentation and abstraction, it also outperforms general mesh approximation approaches at preserving urban structures.

The automatic extraction of line-networks from images is a well-known computer vision issue. Appearance and shape considerations have been deeply explored in the literature to improve accuracy in presence of occlusions, shadows, and a wide variety of irrelevant objects. However most existing works have ignored the structural aspect of the problem. We present an original method which provides structurally-coherent solutions. Contrary to the pixel-based and object-based methods, our result is a graph in which each node represents either a connection or an ending in the line-network. Based on stochastic geometry, we develop a new family of point processes consisting in sampling junction-points in the input image by using a Monte Carlo mechanism. The quality of a configuration is measured by a probability density which takes into account both image consistency and shape priors. Our experiments on a variety of problems illustrate the potential of our approach in terms of accuracy, flexibility and efficiency.

Abstract We present a method for reconstructing surfaces from point sets. The main novelty lies in a structure‐preserving approach where the input point set is first consolidated by structuring and resampling the planar components, before reconstructing the surface from both the consolidated components and the unstructured points. The final surface is obtained through solving a graph‐cut problem formulated on the 3D Delaunay triangulation of the structured point set where the tetrahedra are labeled as inside or outside cells. Structuring facilitates the surface reconstruction as the point set is substantially reduced and the points are enriched with structural meaning related to adjacency between primitives. Our approach departs from the common dichotomy between smooth/piecewise‐smooth and primitive‐based representations by gracefully combining canonical parts from detected primitives and free‐form parts of the inferred shape. Our experiments on a variety of inputs illustrate the potential of our approach in terms of robustness, flexibility and efficiency.

We present an original multiview stereo reconstruction algorithm which allows the 3D-modeling of urban scenes as a combination of meshes and geometric primitives. The method provides a compact model while preserving details: Irregular elements such as statues and ornaments are described by meshes, whereas regular structures such as columns and walls are described by primitives (planes, spheres, cylinders, cones, and tori). We adopt a two-step strategy consisting first in segmenting the initial meshbased surface using a multilabel Markov Random Field-based model and second in sampling primitive and mesh components simultaneously on the obtained partition by a Jump-Diffusion process. The quality of a reconstruction is measured by a multi-object energy model which takes into account both photo-consistency and semantic considerations (i.e., geometry and shape layout). The segmentation and sampling steps are embedded into an iterative refinement procedure which provides an increasingly accurate hybrid representation. Experimental results on complex urban structures and large scenes are presented and compared to state-of-the-art multiview stereo meshing algorithms.

We present a robust method for modeling cities from unstructured point data. Our algorithm provides a more complete description than existing approaches by reconstructing simultaneously buildings, trees and topologically complex grounds. Buildings are modeled by an original approach which guarantees a high generalization level while having semantized and compact representations. Geometric 3D-primitives such as planes, cylinders, spheres or cones describe regular roof sections, and are combined with mesh-patches that represent irregular roof components. The various urban components interact through a non-convex energy minimization problem in which they are propagated under arrangement constraints over a planimetric map. We experimentally validate the approach on complex urban structures and large urban scenes of millions of points.

We present an automatic approach for modeling buildings from aerial LiDAR data. The method produces accurate, watertight and compact meshes under planar constraints which are especially designed for urban scenes. The LiDAR point cloud is classified through a non-convex energy minimization problem in order to separate the points labeled as building. Roof structures are then extracted from this point subset, and used to control the meshing procedure. Experiments highlight the potential of our method in term of minimal rendering, accuracy and compactness.

We propose a multi-view stereo reconstruction algorithm which recovers urban scenes as a combination of meshes and geometric primitives. It provides a compact model while preserving details: irregular elements such as statues and ornaments are described by meshes whereas regular structures such as columns and walls are described by primitives (planes, spheres, cylinders, cones and tori). A Jump-Diffusion process is designed to sample these two types of elements simultaneously. The quality of a reconstruction is measured by a multi-object energy model which takes into account both photo-consistency and semantic considerations (i.e. geometry and shape layout). The sampler is embedded into an iterative refinement procedure which provides an increasingly accurate hybrid representation. Experimental results on complex urban structures and large scenes are presented and compared to multi-view based meshing algorithms.

We present a new approach for building reconstruction from a single Digital Surface Model (DSM). It treats buildings as an assemblage of simple urban structures extracted from a library of 3D parametric blocks (like a LEGO set). First, the 2D-supports of the urban structures are extracted either interactively or automatically. Then, 3D-blocks are placed on the 2D-supports using a Gibbs model which controls both the block assemblage and the fitting to data. A Bayesian decision finds the optimal configuration of 3D-blocks using a Markov Chain Monte Carlo sampler associated with original proposition kernels. This method has been validated on multiple data set in a wide-resolution interval such as 0.7 m satellite and 0.1 m aerial DSMs, and provides 3D representations on complex buildings and dense urban areas with various levels of detail.

This paper presents a new stochastic marked point process for describing images in terms of a finite library of geometric objects. Image analysis based on conventional marked point processes has already produced convincing results but at the expense of parameter tuning, computing time, and model specificity. Our more general multimarked point process has simpler parametric setting, yields notably shorter computing times, and can be applied to a variety of applications. Both linear and areal primitives extracted from a library of geometric objects are matched to a given image using a probabilistic Gibbs model, and a Jump-Diffusion process is performed to search for the optimal object configuration. Experiments with remotely sensed images and natural textures show that the proposed approach has good potential. We conclude with a discussion about the insertion of more complex object interactions in the model by studying the compromise between model complexity and efficiency.

We propose an original hybrid modeling process of urban scenes that represents 3-D models as a combination of mesh-based surfaces and geometric 3-D-primitives. Meshes describe details such as ornaments and statues, whereas 3-D-primitives code for regular shapes such as walls and columns. Starting from an 3-D-surface obtained by multiview stereo techniques, these primitives are inserted into the surface after being detected. This strategy allows the introduction of semantic knowledge, the simplification of the modeling, and even correction of errors generated by the acquisition process. We design a hierarchical approach exploring different scales of an observed scene. Each level consists first in segmenting the surface using a multilabel energy model optimized by -expansion and then in fitting 3-D-primitives such as planes, cylinders or tori on the obtained partition where relevant. Experiments on real meshes, depth maps and synthetic surfaces show good potential for the proposed approach.

Lidar waveforms are 1-D signals representing a train of echoes caused by reflections at different targets. Modeling these echoes with the appropriate parametric function is useful to retrieve information about the physical characteristics of the targets. This paper presents a new probabilistic model based upon a marked point process which reconstructs the echoes from recorded discrete waveforms as a sequence of parametric curves. Such an approach allows to fit each mode of a waveform with the most suitable function and to deal with both, symmetric and asymmetric, echoes. The model takes into account a data term, which measures the coherence between the models and the waveforms, and a regularization term, which introduces prior knowledge on the reconstructed signal. The exploration of the associated configuration space is performed by a reversible jump Markov chain Monte Carlo (RJMCMC) sampler coupled with simulated annealing. Experiments with different kinds of lidar signals, especially from urban scenes, show the high potential of the proposed approach. To further demonstrate the advantages of the suggested method, actual laser scans are classified and the results are reported.

International audience

Lidar waveforms are 1D signal consisting of a train of echoes where each of them correspond to a scattering target of the Earth surface. Modeling these echoes with the appropriate parametric function is necessary to retrieve physical information about these objects and characterize their properties. This paper presents a marked point process based model to reconstruct a lidar signal in terms of a set of parametric functions. The model takes into account both a data term which measures the coherence between the models and the waveforms, and a regularizing term which introduces physical knowledge on the reconstructed signal. We search for the best configuration of functions by performing a Reversible Jump Markov Chain Monte Carlo sampler coupled with a simulated annealing. Results are finally presented on different kinds of signals in urban areas.

Our goal is to represent images in terms of geometric objects acting as primitive elements of an image description. Similar representations obtained by stochastic marked point processes have already led to convincing image analysis results but suffer from serious drawbacks such as complex and unstable parameter tuning, large computing time, and lack of generality. We propose an alternative descriptive model based on a Jump-Diffusion process which can be performed in shorter computing times and applied to a variety of applications without changing the model or modifying the tuning parameters. In our approach, a probabilistic Gibbs model is adapted to a library of geometric objects and is sampled by a Jump-Diffusion process in order to closely match an underlying texture. Experiments with natural textures and remotely sensed images show good potentialities of the proposed approach 1 .

We present a new approach for building reconstruction from a single Digital Elevation Model (DEM). It treats buildings as an assemblage of simple urban structures extracted from a library of 3D parametric blocks (like a LEGOregset). This method works on various data resolutions such as 0.7 m satellite and 0.1 m aerial DEMs and allows us to obtain 3D representations with various levels of detail. First, the 2D supports of the urban structures are extracted either interactively or automatically. Then, 3D blocks are placed on the 2D supports using a Gibbs model. A Bayesian decision finds the optimal configuration of 3D blocks using a RJMCMC sampler. Experimental results on complex buildings and dense urban areas are presented using data at various resolutions.

In this paper, we present an automatic method for the 3D building reconstruction from satellite images. The proposed approach consists in reconstructing buildings by assembling simple urban structures extracted from a grammar of 3D parametric models, as a "LEGO" game. First, the building footprints are extracted through sequences of quadrilaterals: it allows to define the problem as a causal process. Then, the 3D reconstruction stage is realized through a Hidden Markov Model and the optimal sequences of 3D parametric objects are found using the Viterbi algorithm.

We propose a parametric model for automatic 3D reconstruction of urban areas from high resolution satellite data. An automatic building extraction method based on marked point processes is used to provide rectangular building footprints. Based on a parametric model with rectangular ground footprint, the proposed method is developed using a Bayesian approach : we search for the best configuration of parametric models with respect to both a priori knowledge of models and their interactions, and a likelihood which fits models to the DEM. A simulated annealing is used to find the configuration which maximizes the a posteriori density of the Bayesian expression

We present an automatic 3D city model of dense urban areas from HR satellite data. The proposed method is developed using a structural approach: we construct complex buildings by merging simple parametric models with rectangular ground footprint. To do so, an automatic building extraction method based on marked point processes is used to provide rectangular building footprints. A collection of 3D parametric models is defined in order to be fixed onto these building footprints. A Bayesian framework including both prior knowledge of models and their interactions, and a likelihood fitting them to the digital elevation model, is then used. A simulated annealing scheme allows to find the configuration which maximizes the posterior density of the Bayesian expression.

We present a textural kernel for "support vector machines" classification applied to remote sensing problems. SVMs constitute a method of supervised classification well adapted to deal with data of high dimension, such as images. We introduce kernel functions in order to favor the distinction between our class of interest and the other classes: it gives information of similarity. In our case this similarity is based on radiometric and textural characteristics. One of the main difficulties is to elaborate textural parameters which are relevant and characterize as well as possible the joint distribution of a set of connected pixels. We apply this method to remote sensing problems: the detection of forest fires and the extraction of urban areas in high resolution images.