Efficient level of detail for texture‐based flow visualization

In this paper, we present an efficient level of detail algorithm for texture‐based flow visualization. Our goal is to enhance visual perception and performance and generate smooth animation. To achieve our goal, we first model an adaptive input texture taking into account flow patterns to output view‐dependent high‐quality images. Then, we compute field lines only from sparse sampling points of the input noise texture for outputting volume line integral convolution textures and skip empty space utilizing two quantized binary histograms. To improve image quality, we implement anti‐aliasing through adjusting the line integral convolution step size and thickness of trajectory lines with an opacity function. We further extend our solution to unsteady flow. Flow structures and evolution are clearly shown through smooth animation achieved with coherent evolution of particles, handling of discontinuous flow lines, and spatio‐temporal linear constraint of the underlying noise volume. In the result section, we show high‐quality level of detail of three‐dimensional texture‐based flow visualization with high performance. We also demonstrate that our algorithm can achieve smooth evolution for unsteady flow with spatio‐temporal coherence. Copyright © 2015 John Wiley & Sons, Ltd.     

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.     

3D Shape Segmentation and Labeling via Extreme Learning Machine

We propose a fast method for 3D shape segmentation and labeling via Extreme Learning Machine (ELM). Given a set of example shapes with labeled segmentation, we train an ELM classifier and use it to produce initial segmentation for test shapes. Based on the initial segmentation, we compute the final smooth segmentation through a graph‐cut optimization constrained by the super‐face boundaries obtained by over‐segmentation and the active contours computed from ELM segmentation. Experimental results show that our method achieves comparable results against the state‐of‐the‐arts, but reduces the training time by approximately two orders of magnitude, both for face‐level and super‐face‐level, making it scale well for large datasets. Based on such notable improvement, we demonstrate the application of our method for fast online sequential learning for 3D shape segmentation at face level, as well as realtime sequential learning at super‐face level.     

Multi-scale tensor voting for feature extraction from unstructured point clouds

Identifying sharp features in a 3D model is essential for shape analysis, matching and a wide range of geometry processing applications. This paper presents a new method based on the tensor voting theory to extract sharp features from an unstructured point cloud which may contain random noise, outliers and artifacts. Our method first takes the voting tensors at every point using the corresponding neighborhoods and computes the feature weight to infer the local structure via eigenvalue analysis of the tensor. The optimal scale for a point is automatically determined by observing the feature weight variation in order to deal with both a noisy smooth region and a sharp edge. We finally extract the points at sharp features using adaptive thresholding of the feature weight and the feature completion process. The multi-scale tensor voting of a given point set improves noise sensitivity and scale dependency of an input model. We demonstrate the strength of the proposed method in terms of efficiency and robustness by comparing it with other feature detection algorithms.     

Efficient surface reconstruction using generalized coulomb potentials

We propose a novel, geometrically adaptive method for surface reconstruction from noisy and sparse point clouds, without orientation information. The method employs a fast convection algorithm to attract the evolving surface towards the data points. The force field in which the surface is convected is based on generalized Coulomb potentials evaluated on an adaptive grid (i.e., an octree) using a fast, hierarchical algorithm. Formulating reconstruction as a convection problem in a velocity field generated by Coulomb potentials offers a number of advantages. Unlike methods which compute the distance from the data set to the implicit surface, which are sensitive to noise due to the very reliance on the distance transform, our method is highly resilient to shot noise since global, generalized Coulomb potentials can be used to disregard the presence of outliers due to noise. Coulomb potentials represent long-range interactions that consider all data points at once, and thus they convey global information which is crucial in the fitting process. Both the spatial and temporal complexities of our spatially-adaptive method are proportional to the size of the reconstructed object, which makes our method compare favorably with respect to previous approaches in terms of speed and flexibility. Experiments with sparse as well as noisy data sets show that the method is capable of delivering crisp and detailed yet smooth surfaces.     

多先验形状的图割分割方法*

为了分割图像中的多个目标,提出多先验形状约束的多目标图割分割方法。首先,使用离散水平集框架的形状距离定义先验形状模型,并将这一模型合并到图割框架的区域项中,同时通过加入多类形状先验扩展形状先验能量。然后,通过自适应调节形状先验项的权重系数,实现自适应控制形状项在能量函数中所占的比重,克服人工选择参数的困难,提高分割效率。最后,为使方法对于形状仿射变换具有不变性,使用尺度不变特征变换和随机抽样一致结合的方法进行对准。实验表明,文中方法能够较好分割图像中的多个目标,且能较好克服图像的噪声污染、目标被遮挡等信息缺失问题。     

Multi-Level Partition of Unity Algebraic Point Set Surfaces

We present a multi-level partition of unity algebraic set surfaces (MPU-APSS) for surface reconstruction which can be represented by either a projection or in an implicit form. An algebraic point set surface (APSS) defines a smooth surface from a set of unorganized points using local moving least-squares (MLS) fitting of algebraic spheres. However, due to the local nature, APSS does not work well for geometry editing and modeling. Instead, our method builds an implicit approximation function for the scattered point set based on the partition of unity approach. By using an octree subdivision strategy, we first adaptively construct local algebraic spheres for the point set, and then apply weighting functions to blend together these local shape functions. Finally, we compute an error-controlled approximation of the signed distance function from the surface. In addition, we present an efficient projection operator which makes our representation suitable for point set filtering and dynamic point resampling. We demonstrate the effectiveness of our unified approach for both surface reconstruction and geometry modeling such as surface completion.     

On the estimation of a convex set with corners

In robotic vision using laser-radar measurements, noisy data on convex sets with corners are derived in terms of the set's support function. The corners represent abutting edges of manufactured items, and convey important information about the items' shape. However, simple methods for set estimation, for example based on fitting random polygons or smooth sets, either add additional corners as an artifact of the algorithm, or approximate corners by smooth curves. It might be argued, however, that corners have special significance in the interpretation of a set, and should not be introduced as an artifact of the estimation procedure. In this paper we suggest a corner-diagnostic approach, in the form of a three-step algorithm which (a) identifies the number and positions of corners, (b) fits smooth curves between corners, and (c) splices together the smooth curves and the corners, to produce an over-all estimate of the convex set. The corner-finding step is parametric in character, and although it is based on detecting change points in high-order derivatives of the support function, it produces root-n consistent estimators of the locations of corners. On the other hand, the smooth-curve fitting step is entirely nonparametric. The splicing step marries these two disparate approaches into a single, practical method     

Multiscale Biharmonic Kernels

This paper introduces a general principle for constructing multiscale kernels on surface meshes, and presents a construction of the multiscale pre‐biharmonic and multiscale biharmonic kernels. Our construction is based on an optimization problem that seeks to minimize a smoothness criterion, the Laplacian energy, subject to a sparsity inducing constraint. Namely, we use the lasso constraint, which sets an upper bound on the l₁ ‐norm of the solution, to obtain a family of solutions parametrized by this upper‐bound parameter. The interplay between sparsity and smoothness results in smooth kernels that vanish away from the diagonal. We prove that the resulting kernels have gradually changing supports, consistent behavior over partial and complete meshes, and interesting limiting behaviors (e.g. in the limit of large scales, the multiscale biharmonic kernel converges to the Green's function of the biharmonic equation); in addition, these kernels are based on intrinsic quantities and so are insensitive to isometric deformations. We show empirically that our kernels are shape‐aware, are robust to noise, tessellation, and partial object, and are fast to compute. Finally, we demonstrate that the new kernels can be useful for function interpolation and shape correspondence.     

Quantized Point‐Based Global Illumination

Point‐based global illumination (PBGI) uses a dense point sampling of the scene's surfaces to approximate indirect light transport and is intensively used in 3D motion pictures and special effects. Each point caches the reflected light using a spherical function and is typically used in a subsequent rasterization process to compute color bleeding and ambient occlusion in an economic, noise‐free fashion. The entire point set is organized in a spatial tree structure which models the light transport hierarchically, enabling fast adaptive shading on receivers (e.g., unprojected pixels). One of the major limitations of PBGI is related to the size of this tree, which can quickly become too large to fit in memory for complex scenes. However, we observe that, just as with natural images, this point data set is extremely redundant. In this paper, we present a new method exploiting this redundancy by factorizing PBGI data over the tree nodes. In particular, we show that a k‐means clustering in the parameter space of the spherical functions allows to define a small number of representative nodes against which any new one can be classified. These representative functions, gathered in a pre‐process over a subset of the actual points, form a look‐up table which allows to substitute node's data by quantized integers in a streaming process, avoiding building the full tree before compressing it. Depending on the nodes' spherical function variance in the scene and the desired accuracy, our indexed PBGI representation achieves between one and two orders of magnitude compression of the nodes spherical functions, with negligible numerical and perceptual error in the final image. In the case of a binary tree with one surfel per leaf and no spherical functions in the leaves, this leads to compression rates ranging from 3× to 5× for the whole tree.     

Extracting Sharp Features from RGB‐D Images

Sharp edges are important shape features and their extraction has been extensively studied both on point clouds and surfaces. We consider the problem of extracting sharp edges from a sparse set of colour‐and‐depth (RGB‐D) images. The noise‐ridden depth measurements are challenging for existing feature extraction methods that work solely in the geometric domain (e.g. points or meshes). By utilizing both colour and depth information, we propose a novel feature extraction method that produces much cleaner and more coherent feature lines. We make two technical contributions. First, we show that intensity edges can augment the depth map to improve normal estimation and feature localization from a single RGB‐D image. Second, we designed a novel algorithm for consolidating feature points obtained from multiple RGB‐D images. By utilizing normals and ridge/valley types associated with the feature points, our algorithm is effective in suppressing noise without smearing nearby features.     

Discrete Critical Values: a General Framework for Silhouettes Computation

Many shapes resulting from important geometric operations in industrial applications such as Minkowski sums or volume swept by a moving object can be seen as the projection of higher dimensional objects. When such a higher dimensional object is a smooth manifold, the boundary of the projected shape can be computed from the critical points of the projection. In this paper, using the notion of polyhedral chains introduced by Whitney, we introduce a new general framework to define an analogous of the set of critical points of piecewise linear maps defined over discrete objects that can be easily computed. We illustrate our results by showing how they can be used to compute Minkowski sums of polyhedra and volumes swept by moving polyhedra.     

Interior Distance Using Barycentric Coordinates

This paper introduces a framework for defining a shape-aware distance measure between any two points in the interior of a surface mesh. Our framework is based on embedding the surface mesh into a high-dimensional space in a way that best preserves boundary distances between vertices of the mesh, performing a mapping of the mesh volume into this high-dimensional space using barycentric coordinates, and defining the interior distance between any two points simply as their Euclidean distance in the embedding space. We investigate the theoretical properties of the interior distance in relation to properties of the chosen boundary distances and barycentric coordinates, and we investigate empirical properties of the interior distance using diffusion distance as the prescribed boundary distance and mean value coordinates. We prove theoretically that the interior distance is a metric, smooth, interpolating the boundary distances, and reproducing Euclidean distances, and we show empirically that it is insensitive to boundary noise and deformation and quick to compute. In case the barycentric coordinates are non-negative we also show a maximum principle exists. Finally, we use it to define a new geometric property, barycentroid of shape, and show that it captures the notion of semantic center of the shape.     

参数自适应的条件随机场视频分割方法

针对已有算法需要采用一系列参数经验值得到最优视频分割结果的问题,提出根据视频特征自适应地计算视频邻域关系的特征强度函数,构造参数自适应的条件随机场视频分割模型。算法的核心思想是采用视频中像素之间的邻域关系自适应计算各个模型的特征函数,通过条件随机场模型对这些特征能量函数进行约束并利用Gibbs采样算法对该模型进行求解,获得全局优化的分割结果。针对不同环境下的视频分割实验表明,该算法能够很好地逼近最优经验参数所得到的视频分割结果,从而避免定义经验值所导致的算法局限性问题。     

Mumford-Shah on the Move: Region-Based Segmentation on Deforming Manifolds with Application to 3-D Reconstruction of Shape and Appearance from Multi-View Images

We address the problem of estimating the shape and appearance of a scene made of smooth Lambertian surfaces with piecewise smooth albedo. We allow the scene to have self-occlusions and multiple connected components. This class of surfaces is often used as an approximation of scenes populated by man-made objects. We assume we are given a number of images taken from different vantage points. Mathematically this problem can be posed as an extension of Mumford and Shah’s approach to static image segmentation to the segmentation of a function defined on a deforming surface. We propose an iterative procedure to minimize a global cost functional that combines geometric priors on both the shape of the scene and the boundary between smooth albedo regions. We carry out the numerical implementation in the level set framework.     

Efficient RANSAC for Point-Cloud Shape Detection

In this paper we present an automatic algorithm to detect basic shapes in unorganized point clouds. The algorithm decomposes the point cloud into a concise, hybrid structure of inherent shapes and a set of remaining points. Each detected shape serves as a proxy for a set of corresponding points. Our method is based on random sampling and detects planes, spheres, cylinders, cones and tori. For models with surfaces composed of these basic shapes only, for example, CAD models, we automatically obtain a representation solely consisting of shape proxies. We demonstrate that the algorithm is robust even in the presence of many outliers and a high degree of noise. The proposed method scales well with respect to the size of the input point cloud and the number and size of the shapes within the data. Even point sets with several millions of samples are robustly decomposed within less than a minute. Moreover, the algorithm is conceptually simple and easy to implement. Application areas include measurement of physical parameters, scan registration, surface compression, hybrid rendering, shape classification, meshing, simplification, approximation and reverse engineering.     

An Optimal Transport Approach to Robust Reconstruction and Simplification of 2D Shapes

We propose a robust 2D shape reconstruction and simplification algorithm which takes as input a defect‐laden point set with noise and outliers. We introduce an optimal‐transport driven approach where the input point set, considered as a sum of Dirac measures, is approximated by a simplicial complex considered as a sum of uniform measures on 0‐ and 1‐simplices. A fine‐to‐coarse scheme is devised to construct the resulting simplicial complex through greedy decimation of a Delaunay triangulation of the input point set. Our method performs well on a variety of examples ranging from line drawings to grayscale images, with or without noise, features, and boundaries.     

Feature‐Preserving Surface Reconstruction From Unoriented,Noisy Point Data

We propose a robust method for surface mesh reconstruction from unorganized, unoriented, noisy and outlier‐ridden 3D point data. A kernel‐based scale estimator is introduced to estimate the scale of inliers of the input data. The best tangent planes are computed for all points based on mean shift clustering and adaptive scale sample consensus, followed by detecting and removing outliers. Subsequently, we estimate the normals for the remaining points and smooth the noise using a surface fitting and projection strategy. As a result, the outliers and noise are removed and filtered, while the original sharp features are well preserved. We then adopt an existing method to reconstruct surface meshes from the processed point data. To preserve sharp features of the generated meshes that are often blurred during reconstruction, we describe a two‐step approach to effectively recover original sharp features. A number of examples are presented to demonstrate the effectiveness and robustness of our method.     

基于轮廓重构和特征点弦长的图像检索

轮廓描述法作为形状检索中最为关键的步骤,应体现目标的整体形状信息和重要特征点信息,并具备对噪声干扰的鲁棒性.提出一种基于轮廓重构和特征点弦长的图像检索算法,首先在目标轮廓提取的基础上分析轮廓的能量保持率,并进行轮廓的降维重构处理,从而减少了随机噪声造成的轮廓畸变.然后,通过新定义的支持域来计算轮廓点的特征强度,并分析了支持域半径与特征点提取结果的关系,从而筛选出有效的轮廓特征点.最后,根据轮廓点和相应特征点间的弦长关系构造轮廓特征函数,经相应处理后,最终得到的形状描述子满足不变性要求.大量实验结果表明,该算法无论是在常规样本库中,还是在噪声样本库中都具有更优的检索性能.