2D‐D Lifting for Shape Reconstruction

We present an algorithm for shape reconstruction from incomplete 3D scans by fusing together two acquisition modes: 2D photographs and 3D scans. The two modes exhibit complementary characteristics: scans have depth information, but are often sparse and incomplete; photographs, on the other hand, are dense and have high resolution, but lack important depth information. In this work we fuse the two modes, taking advantage of their complementary information, to enhance 3D shape reconstruction from an incomplete scan with a 2D photograph. We compute geometrical and topological shape properties in 2D photographs and use them to reconstruct a shape from an incomplete 3D scan in a principled manner. Our key observation is that shape properties such as boundaries, smooth patches and local connectivity, can be inferred with high confidence from 2D photographs. Thus, we register the 3D scan with the 2D photograph and use scanned points as 3D depth cues for lifting 2D shape structures into 3D. Our contribution is an algorithm which significantly regularizes and enhances the problem of 3D reconstruction from partial scans by lifting 2D shape structures into 3D. We evaluate our algorithm on various shapes which are loosely scanned and photographed from different views, and compare them with state‐of‐the‐art reconstruction methods.     

Virtual Video Camera: Image‐Based Viewpoint Navigation Through Space and Time

We present an image‐based rendering system to viewpoint‐navigate through space and time of complex real‐world, dynamic scenes. Our approach accepts unsynchronized, uncalibrated multivideo footage as input. Inexpensive, consumer‐grade camcorders suffice to acquire arbitrary scenes, for example in the outdoors, without elaborate recording setup procedures, allowing also for hand‐held recordings. Instead of scene depth estimation, layer segmentation or 3D reconstruction, our approach is based on dense image correspondences, treating view interpolation uniformly in space and time: spatial viewpoint navigation, slow motion or freeze‐and‐rotate effects can all be created in the same way. Acquisition simplification, integration of moving cameras, generalization to difficult scenes and space–time symmetric interpolation amount to a widely applicable virtual video camera system.     

A Sketch-Based User Interface for Reconstructing Architectural Drawings

We present a framework for interactive sketching that allows users to create three‐dimensional (3D) architectural models quickly and easily from a source drawing. The sketching process has four steps. (1) The user calibrates a viewing camera by specifying the origin and vanishing points of the drawing. (2) The user outlines surface polygons in the drawing. (3) A 3D reconstruction algorithm uses perceptual constraints to determine the closest visual fit for the polygon. (4) The user can then adjust aesthetic controls to produce several stylistic effects in the scene: a smooth transition between day and night rendering, a horizon knockout effect and entourage figures. The major advantage of our approach lies in the combination of perception‐based techniques, which allow us to minimize unnecessary interactions, and a hinging‐angle scheme, which shows significant improvement in numerical stability over previous optimization‐based 3D reconstruction algorithms. We also demonstrate how our reconstruction algorithm can be extended to work with perspective images, a feature unavailable in previous approaches.     

Coverage Path Planning with Real‐time Replanning and Surface Reconstruction for Inspection of Three‐dimensional Underwater Structures using Autonomous Underwater Vehicles

We present a novel method for planning coverage paths for inspecting complex structures on the ocean floor using an autonomous underwater vehicle (AUV). Our method initially uses a 2.5‐dimensional (2.5D) prior bathymetric map to plan a nominal coverage path that allows the AUV to pass its sensors over all points on the target area. The nominal path uses a standard mowing‐the‐lawn pattern in effectively planar regions, while in regions with substantial 3D relief it follows horizontal contours of the terrain at a given offset distance. We then go beyond previous approaches in the literature by considering the vehicle's state uncertainty rather than relying on the unrealistic assumption of an idealized path execution. Toward that end, we present a replanning algorithm based on a stochastic trajectory optimization that reshapes the nominal path to cope with the actual target structure perceived in situ. The replanning algorithm runs onboard the AUV in real time during the inspection mission, adapting the path according to the measurements provided by the vehicle's range‐sensing sonars. Furthermore, we propose a pipeline of state‐of‐the‐art surface reconstruction techniques we apply to the data acquired by the AUV to obtain 3D models of the inspected structures that show the benefits of our planning method for 3D mapping. We demonstrate the efficacy of our method in experiments at sea using the GIRONA 500 AUV, where we cover part of a breakwater structure in a harbor and an underwater boulder rising from 40 m up to 27 m depth.     

大规模室外图像3维重建技术研究进展

基于图像的3维重建旨在从一组2维多视角图像中精确地恢复真实场景的几何形状,是计算机视觉和摄影测量中基础且活跃的研究课题,具有重要的理论研究意义和应用价值,在智慧城市、虚拟旅游、数字遗产保护、数字地图和导航等领域有着广泛应用。随着图像采集系统（智能手机、消费级数码相机和民用无人机等）的普及和互联网的高速发展,通过搜索引擎可以获取大量关于某个室外场景的互联网图像。利用这些图像进行高效鲁棒准确的3维重建,为用户提供真实感知和沉浸式体验已经成为研究热点,引发了学术界和产业界的广泛关注,涌现了多种方法。深度学习的出现为大规模室外图像的3维重建提供了新的契机。首先阐述大规模室外图像3维重建的基本串行过程,包括图像检索、图像特征点匹配、运动恢复结构和多视图立体。然后从传统方法和基于深度学习的方法两个角度,分别系统全面地回顾大规模室外图像3维重建技术在各重建子过程中的发展和应用,总结各子过程中适用于大规模室外场景的数据集和评价指标。最后介绍现有主流的开源和商业3维重建系统以及国内相关产业的发展现状。     

Approximate Symmetry Detection in Partial 3D Meshes

Symmetry is a common characteristic in natural and man‐made objects. Its ubiquitous nature can be exploited to facilitate the analysis and processing of computational representations of real objects. In particular, in computer graphics, the detection of symmetries in 3D geometry has enabled a number of applications in modeling and reconstruction. However, the problem of symmetry detection in incomplete geometry remains a challenging task. In this paper, we propose a vote‐based approach to detect symmetry in 3D shapes, with special interest in models with large missing parts. Our algorithm generates a set of candidate symmetries by matching local maxima of a surface function based on the heat diffusion in local domains, which guarantee robustness to missing data. In order to deal with local perturbations, we propose a multi‐scale surface function that is useful to select a set of distinctive points over which the approximate symmetries are defined. In addition, we introduce a vote‐based scheme that is aware of the partiality, and therefore reduces the number of false positive votes for the candidate symmetries. We show the effectiveness of our method in a varied set of 3D shapes and different levels of partiality. Furthermore, we show the applicability of our algorithm in the repair and completion of challenging reassembled objects in the context of cultural heritage.     

Detection of Geometric Temporal Changes in Point Clouds

Detecting geometric changes between two 3D captures of the same location performed at different moments is a critical operation for all systems requiring a precise segmentation between change and no‐change regions. Such application scenarios include 3D surface reconstruction, environment monitoring, natural events management and forensic science. Unfortunately, typical 3D scanning setups cannot provide any one‐to‐one mapping between measured samples in static regions: in particular, both extrinsic and intrinsic sensor parameters may vary over time while sensor noise and outliers additionally corrupt the data. In this paper, we adopt a multi‐scale approach to robustly tackle these issues. Starting from two point clouds, we first remove outliers using a probabilistic operator. Then, we detect the actual change using the implicit surface defined by the point clouds under a Growing Least Square reconstruction that, compared to the classical proximity measure, offers a more robust change/no‐change characterization near the temporal intersection of the scans and in the areas exhibiting different sampling density and direction. The resulting classification is enhanced with a spatial reasoning step to solve critical geometric configurations that are common in man‐made environments. We validate our approach on a synthetic test case and on a collection of real data sets acquired using commodity hardware. Finally, we show how 3D reconstruction benefits from the resulting precise change/no‐change segmentation.     

Hardware trace reconstruction of runtime compiled code

Hardware tracing has emerged as a low‐cost technique to analyze systems at a very fine granularity, thus mitigating the need for software‐only trace approaches for performance analysis. State‐of‐the‐art trace hardware on modern Intel and ARM processors allows recording change‐of‐flow instructions in executable binaries, such as branches, for off‐line reconstruction. This conventional userspace–based trace reconstruction, however, is not robust enough in the common scenarios where runtime code is being generated, compiled, and executed. We therefore propose a novel kernel‐assisted mechanism called FlowJIT to reconstruct hardware traces with a low overhead of around 1.3 μs per code page modification event. We further show the efficacy or our technique with the help of 2 illustrative usecases that cover the JIT compiled code scenario and a same‐page instruction modification scenario. Our implementation has been open sourced as a patch for the Linux kernel.     

A computational model of bounded developable surfaces with application to image‐based three‐dimensional reconstruction

Developable surfaces have been extensively studied in computer graphics because they are involved in a large body of applications. This type of surfaces has also been used in computer vision and document processing in the context of three‐dimensional (3D) reconstruction for book digitization and augmented reality. Indeed, the shape of a smoothly deformed piece of paper can be very well modeled by a developable surface. Most of the existing developable surface parameterizations do not handle boundaries or are driven by overly large parameter sets. These two characteristics become issues in the context of developable surface reconstruction from real observations. Our main contribution is a generative model of bounded developable surfaces that solves these two issues. Our model is governed by intuitive parameters whose number depends on the actual deformation and including the “flat shape boundary”. A vast majority of the existing image‐based paper 3D reconstruction methods either require a tightly controlled environment or restricts the set of possible deformations. We propose an algorithm for reconstructing our model's parameters from a general smooth 3D surface interpolating a sparse cloud of 3D points. The latter is assumed to be reconstructed from images of a static piece of paper or any other developable surface. Our 3D reconstruction method is well adapted to the use of keypoint matches over multiple images. In this context, the initial 3D point cloud is reconstructed by structure‐from‐motion for which mature and reliable algorithms now exist and the thin‐plate spline is used as a general smooth surface model. After initialization, our model's parameters are refined with model‐based bundle adjustment. We experimentally validated our model and 3D reconstruction algorithm for shape capture and augmented reality on seven real datasets. The first six datasets consist of multiple images or videos and a sparse set of 3D points obtained by structure‐from‐motion. The last dataset is a dense 3D point cloud acquired by structured light. Our implementation has been made publicly available on the authors' web home pages. Copyright © 2012 John Wiley & Sons, Ltd.     

Feature Preserving Mesh Generation from 3D Point Clouds

We address the problem of generating quality surface triangle meshes from 3D point clouds sampled on piecewise smooth surfaces. Using a feature detection process based on the covariance matrices of Voronoi cells, we first extract from the point cloud a set of sharp features. Our algorithm also runs on the input point cloud a reconstruction process, such as Poisson reconstruction, providing an implicit surface. A feature preserving variant of a Delaunay refinement process is then used to generate a mesh approximating the implicit surface and containing a faithful representation of the extracted sharp edges. Such a mesh provides an enhanced trade‐off between accuracy and mesh complexity. The whole process is robust to noise and made versatile through a small set of parameters which govern the mesh sizing, approximation error and shape of the elements. We demonstrate the effectiveness of our method on a variety of models including laser scanned datasets ranging from indoor to outdoor scenes.     

Visibility‐Aware Progressive Farthest Point Sampling on the GPU

In this paper, we present the first algorithm for progressive sampling of 3D surfaces with blue noise characteristics that runs entirely on the GPU. The performance of our algorithm is comparable to state‐of‐the‐art GPU Poisson‐disk sampling methods, while additionally producing ordered sequences of samples where every prefix exhibits good blue noise properties. The basic idea is, to reduce the 3D sampling domain to a set of 2.5D images which we sample in parallel utilizing the rasterization hardware of current GPUs. This allows for simple visibility‐aware sampling that only captures the surface as seen from outside the sampled object, which is especially useful for point‐based level‐of‐detail rendering methods. However, our method can be easily extended for sampling the entire surface without changing the basic algorithm. We provide a statistical analysis of our algorithm and show that it produces good blue noise characteristics for every prefix of the resulting sample sequence and analyze the performance of our method compared to related state‐of‐the‐art sampling methods.     

Hybrid mesh‐volume LoDs for all‐scale pre‐filtering of complex 3D assets

We address the problem of constructing appearance‐preserving level of details (LoDs) of complex 3D models such as trees. We propose a hybrid method that combines the strengths of mesh and volume representations. Our main idea is to separate macroscopic (i.e. larger than the target spatial resolution) and microscopic (sub‐resolution) surfaces at each scale and to treat them differently, because meshes are very efficient at representing macroscopic surfaces while sub‐resolution geometry benefits from volumetric approximations. We introduce a new algorithm that detects the macroscopic surfaces of a mesh for a given resolution. We simplify these surfaces with edge collapses and we provide a method for pre‐filtering their normal distributions and albedos. To approximate microscopic details, we use a heterogeneous microflake participating medium and we introduce a new artifact‐free voxelization algorithm that preserves local occlusion. Thanks to our macroscopic surface analysis, our algorithm is fully automatic and it generates seamless LoDs at arbitrarily coarse resolutions for a wide range of 3D models.     

Motion Blur for EWA Surface Splatting

This paper presents a novel framework for elliptical weighted average (EWA) surface splatting with time‐varying scenes. We extend the theoretical basis of the original framework by replacing the 2D surface reconstruction filters by 3D kernels which unify the spatial and temporal component of moving objects. Based on the newly derived mathematical framework we introduce a rendering algorithm that supports the generation of high‐quality motion blur for point‐based objects using a piecewise linear approximation of the motion. The rendering algorithm applies ellipsoids as rendering primitives which are constructed by extending planar EWA surface splats into the temporal dimension along the instantaneous motion vector. Finally, we present an implementation of the proposed rendering algorithm with approximated occlusion handling using advanced features of modern GPUs and show its capability of producing motion‐blurred result images at interactive frame rates.     

A reverse engineering system for rapid manufacturing of complex objects

This paper presents a reverse engineering system for rapid modeling and manufacturing of products with complex surfaces. The system consists of three main components: a 3D optical digitizing system, a surface reconstruction software and a rapid prototyping machine. The unique features of the 3D optical digitizing system include the use of white-light source, and cost-effective and quick image acquisition. The surface reconstruction process consists of three major steps: (1) range view registration by an iterative closed-form solution, (2) range surface integration by reconstructing an implicit function to update the volumetric grid, and (3) iso-surface extraction by the Marching Cubes algorithm. The modeling software exports models in STL format, which are used as input to an FDM 2000 machine to manufacture products. The examples are included to illustrate the systems and the methods.     

接触式多关节三维扫描仪研究

论述了拥有自主知识产权的接触式多关节三维扫描仪3DLCS-400的硬件系统和软件系统的基本构成、主要特点和实现方法。在此基础上,研究了接触式三维信息获取中的一些关键技术———数据采集与三维显示的同步、坐标计算和误差校正、三维构型重建。采用基于API函数的异步多线程串行通信和OpenGL三维显示技术,提出了一种修正最小二乘法和基因可变限改进遗传算法相结合的参数标定方法和运用轮廓线的三维散乱数据构型方法。该产品的研制成功填补了国产三维信息获取系统的一个空白。     

Chamber Recognition in Cave Data Sets

Quantitative analysis of cave systems represented as 3D models is becoming more and more important in the field of cave sciences. One open question is the rigorous identification of chambers in a data set, which has a deep impact on subsequent analysis steps such as size calculation. This affects the international recognition of a cave since especially record‐holding caves bear significant tourist attraction potential. In the past, chambers have been identified manually, without any clear definition or guidance. While experts agree on core parts of chambers in general, their opinions may differ in more controversial areas. Since this process is heavily subjective, it is not suited for objective quantitative comparison of caves. Therefore, we present a novel fully‐automatic curve skeleton‐based chamber recognition algorithm that has been derived from requirements from field experts. We state the problem as a binary labeling problem on a curve skeleton and find a solution through energy minimization. A thorough evaluation of our results with the help of expert feedback showed that our algorithm matches real‐world requirements very closely and is thus suited as the foundation for any quantitative cave analysis system.     

Optimal Algorithm for Shape from Shading and Path Planning

An optimal algorithm for the reconstruction of a surface from its shading image is presented. The algorithm solves the 3D reconstruction from a single shading image problem. The shading image is treated as a penalty function and the height of the reconstructed surface is a weighted distance. A consistent numerical scheme based on Sethian's fast marching method is used to compute the reconstructed surface. The surface is a viscosity solution of an Eikonal equation for the vertical light source case. For the oblique light source case, the reconstructed surface is the viscosity solution to a different partial differential equation. A modification of the fast marching method yields a numerically consistent, computationally optimal, and practically fast algorithm for the classical shape from shading problem. Next, the fast marching method coupled with a back tracking via gradient descent along the reconstructed surface is shown to solve the path planning problem in robot navigation.     

Three‐dimensional reconstruction of underwater objects using wide‐aperture imaging SONAR

The estimation of the geometric structure of objects located underwater underpins a plethora of applications such as mapping shipwrecks for archaeology, monitoring the health of coral reefs, detecting faults in offshore oil rigs and pipelines, detection and identification of potential threats on the seabed, etc. Acoustic imaging is the most popular choice for underwater sensing. Underwater exploratory vehicles typically employ wide‐aperture Sound Navigation and Ranging (SONAR) imaging sensors. Although their wide aperture enables scouring large volumes of water ahead of them for obstacles, the resulting images produced are blurry due to integration over the aperture. Performing three‐dimensional (3D) reconstruction from this blurry data is notoriously difficult. This challenging inverse problem is further exacerbated by the presence of speckle noise and reverberations. The state‐of‐the‐art methods in 3D reconstruction from sonar either require bulky and expensive matrix‐arrays of sonar sensors or additional narrow‐aperture sensors. Due to its low footprint, the latter induces gaps between reconstructed scans. Avoiding such gaps requires slow and cumbersome scanning by the vehicles that carry the scanners. In this paper, we present two reconstruction methods enabling on‐site 3D reconstruction from imaging sonars of any aperture. The first of these presents an elegant linear formulation of the problem, as a blind deconvolution with a spatially varying kernel. The second method is a simple algorithmic approach for approximate reconstruction, using a nonlinear formulation. We demonstrate that our simple approximation algorithms perform 3D reconstruction directly from the data recorded by wide‐aperture systems, thus eliminating the need for multiple sensors to be mounted on underwater vehicles for this purpose. Additionally, we observe that the wide aperture may be exploited to improve the coverage of the reconstructed samples (on the scanned object's surface). We demonstrate the efficacy of our algorithms on simulated as well as real data acquired using two sensors, and we compare our work to the state of the art in sonar reconstruction. Finally, we show the employability of our reconstruction methods on field data gathered by an autonomous underwater vehicle.     

Weak-perspective structure from motion by fast alternation

This paper addresses the problem of moving object reconstruction. Several methods have been published in the past 20 years including stereo reconstruction as well as multi-view factorization methods. In general, reconstruction algorithms compute the 3D structure of the object and the camera parameters in a non-optimal way, and then a nonlinear and numerical optimization algorithm refines the reconstructed camera parameters and 3D coordinates. In this paper, we propose an adjustment method which is the improved version of the well-known Tomasi–Kanade factorization method. The novelty, which yields the high speed of the algorithm, is that the core of the proposed method is an alternation and we give optimal solutions to the subproblems in the alternation. The improved method is discussed here and it is compared to the widely used bundle adjustment algorithm.