The goal of urban building mesh simplification is to generate a compact representation of a building from a given mesh. Local smoothness and sharp contours of urban buildings are important features for converting unstructured data into solid models, which should be preserved during the simplification. In this paper, we present a general method to filter and simplify 3D building mesh models, capable of preserving piecewise planar structures and sharp features. Given a building mesh model, a mesh filtering technique is firstly designed to yield piecewise planar regions and extract crease contours. The planar regions are used to constrain the simplification of the mesh. Mesh decimation is achieved through a series of edge collapse operations, which uses regional structural constraints and local geometric error metrics to handle planar and non-planar areas respectively. The proposed method preserves the mesh structure with meaningful levels of detail while reducing the number of faces. The effectiveness of this method is evaluated on various building models generated from different observation scales, and the performance is validated by extensive comparisons to state-of-the-art techniques.
Forest above-ground biomass (AGB) can be estimated based on light detection and ranging (LiDAR) point clouds. This paper introduces an accurate and detailed quantitative structure model (AdQSM), which can estimate the AGB of large tropical trees. AdQSM is based on the reconstruction of 3D tree models from terrestrial laser scanning (TLS) point clouds. It represents a tree as a set of closed and complete convex polyhedra. We use AdQSM to model 29 trees of various species (total 18 species) scanned by TLS from three study sites (the dense tropical forests of Peru, Indonesia, and Guyana). The destructively sampled tree geometry measurement data is used as reference values to evaluate the accuracy of diameter at breast height (DBH), tree height, tree volume, branch volume, and AGB estimated from AdQSM. After AdQSM reconstructs the structure and volume of each tree, AGB is derived by combining the wood density of the specific tree species from destructive sampling. The AGB estimation from AdQSM and the post-harvest reference measurement data show a satisfying agreement. The coefficient of variation of root mean square error (CV-RMSE) and the concordance correlation coefficient (CCC) are 20.37% and 0.97, respectively. AdQSM provides accurate tree volume estimation, regardless of the characteristics of the tree structure, without major systematic deviations. We compared the accuracy of AdQSM and TreeQSM in modeling the volume of 29 trees. The tree volume from AdQSM is compared with the reference value, and the determination coefficient (R2), relative bias (rBias), and CV-RMSE of tree volume are 0.96, 6.98%, and 22.62%, respectively. The tree volume from TreeQSM is compared with the reference value, and the R2, relative Bias (rBias), and CV-RMSE of tree volume are 0.94, −9.69%, and 23.20%, respectively. The CCCs between the volume estimates based on AdQSM, TreeQSM, and the reference values are 0.97 and 0.96. AdQSM also models the branches in detail. The volume of branches from AdQSM is compared with the destructive measurement reference data. The R2, rBias, and CV-RMSE of the branches volume are 0.97, 12.38%, and 36.86%, respectively. The DBH and height of the harvested trees were used as reference values to test the accuracy of AdQSM’s estimation of DBH and tree height. The R2, rBias, and CV-RMSE of DBH are 0.94, −5.01%, and 9.06%, respectively. The R2, rBias, and CV-RMSE of the tree height were 0.95, 1.88%, and 5.79%, respectively. This paper provides not only a new QSM method for estimating AGB based on TLS point clouds but also the potential for further development and testing of allometric equations.
We introduce a novel approach for the polygonization of Multi-view Stereo (MVS) meshes of buildings,
which results in compact and topologically valid models. The main characteristic of our method is structure
awareness, i.e., the recovery and preservation of the initial mesh primitives and their adjacencies. Our proposed
methodology consists of three main stages: (a) primitive detection via mesh segmentation, (b) encoding of
primitive adjacencies into a graph, and (c) polygonization. Polygonization is based on the approximation of
the original mesh with a candidate set of planar polygonal faces. On this candidate set, we apply a binary
labelling formulation to select and assemble an optimal set of faces under hard constraints that ensure that
the final model is both manifold and watertight. Experiments on various building models demonstrate that
our simplification method can produce simpler representations for both closed and open building meshes.
Furthermore, these representations highly conform to the initial structure and are ready to be used for
spatial analysis. The source code of this work is freely available at https://github.com/VasileiosBouzas/MeshPolygonization.
Traditional point cloud registration methods require
large overlap between scans, which imposes strict constraints on
data acquisition. To facilitate registration, users have to carefully
position scanners to ensure sufficient overlap. In this work, we
propose to use high-level structural information (i.e., plane/line
features and their inter-relationship) for registration, which is
capable of registering point clouds with small overlap, allowing
more freedom in data acquisition. We design a novel plane/linebased descriptor dedicated to establishing structure level correspondences between point clouds. Based on this descriptor,
we propose a simple but effective registration algorithm. We
also provide a dataset of real-world scenes containing a larger
number of scans with a wide range of overlap. Experiments and
comparisons with state-of-the-art methods on various datasets
reveal that our method is superior to existing techniques. Though
the proposed algorithm outperforms state-of-the-art methods
on the most challenging dataset, the point cloud registration
problem is still far from being solved, leaving significant room
for improvement and future work.
Laser scanning is an effective tool for acquiring geometric attributes of trees and vegetation,
which lays a solid foundation for 3-dimensional tree modelling. Existing studies on tree modelling
from laser scanning data are vast. However, some works cannot guarantee sufficient modelling
accuracy, while some other works are mainly rule-based and therefore highly depend on user inputs.
In this paper, we propose a novel method to accurately and automatically reconstruct detailed 3D
tree models from laser scans. We first extract an initial tree skeleton from the input point cloud by
establishing a minimum spanning tree using the Dijkstra shortest-path algorithm. Then, the initial tree
skeleton is pruned by iteratively removing redundant components. After that, an optimization-based
approach is performed to fit a sequence of cylinders to approximate the geometry of the tree branches.
Experiments on various types of trees from different data sources demonstrate the effectiveness and
robustness of our method. The overall fitting error (i.e., the distance between the input points and the
output model) is less than 10 cm. The reconstructed tree models can be further applied in the precise
estimation of tree attributes, urban landscape visualization, etc. The source code of this work is freely
available at https://github.com/tudelft3d/adtree
In 3D printing, it is critical to use as few as possible supporting materials for efficiency
and material saving. Multiple model decomposition methods and multi-DOF (degrees
of freedom) 3D printers have been developed to address this issue. However, most
systems utilize model decomposition and multi-DOF independently. Only a few
existing approaches combine the two, i.e. partitioning the models for multi-DOF
printing. In this paper, we present a novel model decomposition method for multidirectional 3D printing, allowing consistent printing with the least cost of supporting
materials. Our method is based on a global optimization that minimizes the surface
area to be supported for a 3D model. The printing sequence is determined inherently
by minimizing a single global objective function. Experiments on various complex
3D models using a five-DOF 3D printer have demonstrated the effectiveness of our
This paper presents a method for generative design of decorative architectural parts such as corbel,moulding and panel, which
usually have clear structure and aesthetic details. The method is composed of two components: offline learning and online
generation. The offline learning trains a 2D CurveInfoGAN and a 3D VoxelVAE that learn the feature representations of the
parts in a dataset. The online generation proceeds with an evolution procedure that evolves to product new generation of
part components by selecting, crossing over and mutating features, followed by a feature-driven deformation that synthesizes
the 3D mesh representation of new models. Built upon these technical components, a generative design tool is developed,
which allows the user to input a decorative architectural model as a reference and then generates a set of new models that
are “more of the same” as the reference and meanwhile exhibit some “surprising” elements. The experiments demonstrate
the effectiveness of the method and also showcase the use of classic geometric modelling and advanced machine learning
techniques in modelling of architectural parts.
Wenqing OuyangUniversity of Science and Technology of ChinaYue PengUniversity of Science and Technology of ChinaYuxin YaoUniversity of Science and Technology of ChinaJuyong ZhangUniversity of Science and Technology of China Bailin DengCardiff University
Geometric Modeling and Processingmathscidoc:2012.16004
Computer Graphics Forum (Symposium on Geometry Processing), 39, (5), 2020.8
The alternating direction multiplier method (ADMM) is widely used in computer graphics for solving optimization problems that can be nonsmooth and nonconvex. It converges quickly to an approximate solution, but can take a long time to converge to a solution of high‐accuracy. Previously, Anderson acceleration has been applied to ADMM, by treating it as a fixed‐point iteration for the concatenation of the dual variables and a subset of the primal variables. In this paper, we note that the equivalence between ADMM and Douglas‐Rachford splitting reveals that ADMM is in fact a fixed‐point iteration in a lower‐dimensional space. By applying Anderson acceleration to such lower‐dimensional fixed‐point iteration, we obtain a more effective approach for accelerating ADMM. We analyze the convergence of the proposed acceleration method on nonconvex problems, and verify its effectiveness on a variety of computer graphics including geometry processing and physical simulation.
The alternating direction method of multipliers (ADMM) is a popular approach for solving optimization problems that are potentially non-smooth and with hard constraints. It has been applied to various computer graphics applications, including physical simulation, geometry processing, and image processing. However, ADMM can take a long time to converge to a solution of high accuracy. Moreover, many computer graphics tasks involve non-convex optimization, and there is often no convergence guarantee for ADMM on such problems since it was originally designed for convex optimization. In this paper, we propose a method to speed up ADMM using Anderson acceleration, an established technique for accelerating fixed-point iterations. We show that in the general case, ADMM is a fixed-point iteration of the second primal variable and the dual variable, and Anderson acceleration can be directly applied. Additionally, when the problem has a separable target function and satisfies certain conditions, ADMM becomes a fixed-point iteration of only one variable, which further reduces the computational overhead of Anderson acceleration. Moreover, we analyze a particular non-convex problem structure that is common in computer graphics, and prove the convergence of ADMM on such problems under mild assumptions. We apply our acceleration technique on a variety of optimization problems in computer graphics, with notable improvement on their convergence speed.
Juyong ZhangUniversity of Science and Technology of ChinaBailin DengCardiff UniversityYang HongUniversity of Science and Technology of ChinaYue PengUniversity of Science and Technology of ChinaWenjie QinUniversity of Science and Technology of ChinaLigang LiuUniversity of Science and Technology of China
Geometric Modeling and Processingmathscidoc:2012.16002
IEEE Transactions on Visualization and Computer Graphics, 25, (4), 2019.4
The joint bilateral filter, which enables feature-preserving signal smoothing according to the structural information from a guidance, has been applied for various tasks in geometry processing. Existing methods either rely on a static guidance that may be inconsistent with the input and lead to unsatisfactory results, or a dynamic guidance that is automatically updated but sensitive to noises and outliers. Inspired by recent advances in image filtering, we propose a new geometry filtering technique called static/dynamic filter, which utilizes both static and dynamic guidances to achieve state-of-the-art results. The proposed filter is based on a nonlinear optimization that enforces smoothness of the signal while preserving variations that correspond to features of certain scales. We develop an efficient iterative solver for the problem, which unifies existing filters that are based on static or dynamic guidances. The filter can be applied to mesh face normals followed by vertex position update, to achieve scale-aware and feature-preserving filtering of mesh geometry. It also works well for other types of signals defined on mesh surfaces, such as texture colors. Extensive experimental results demonstrate the effectiveness of the proposed filter for various geometry processing applications such as mesh denoising, geometry feature enhancement, and texture color filtering.
Yue PengUniversity of Science and Technology of ChinaBailin DengCardiff UniversityJuyong ZhangUniversity of Science and Technology of ChinaFanyu GengUniversity of Science and Technology of ChinaWenjie QinUniversity of Science and Technology of ChinaLigang LiuUniversity of Science and Technology of China
Geometric Modeling and Processingmathscidoc:2012.16001
ACM Transactions on Graphics (SIGGRAPH), 37, (4), 42, 2018.8
Many computer graphics problems require computing geometric shapes subject to certain constraints. This often results in non-linear and non-convex optimization problems with globally coupled variables, which pose great challenge for interactive applications. Local-global solvers developed in recent years can quickly compute an approximate solution to such problems, making them an attractive choice for applications that prioritize efficiency over accuracy. However, these solvers suffer from lower convergence rate, and may take a long time to compute an accurate result. In this paper, we propose a simple and effective technique to accelerate the convergence of such solvers. By treating each local-global step as a fixed-point iteration, we apply Anderson acceleration, a well-established technique for fixed-point solvers, to speed up the convergence of a local-global solver. To address the stability issue of classical Anderson acceleration, we propose a simple strategy to guarantee the decrease of target energy and ensure its global onvergence. In addition, we analyze the connection between Anderson acceleration and quasi-Newton methods, and show that the canonical choice of its mixing parameter is suitable for accelerating local-global solvers. Moreover, our technique is effective beyond classical local-global solvers, and can be applied to iterative methods with a common structure. We evaluate the performance of our technique on a variety of geometry optimization and physics simulation problems. Our approach significantly reduces the number of iterations required to compute an accurate result, with only a slight increase of computational cost per iteration. Its simplicity and effectiveness makes it a promising tool for accelerating existing algorithms as well as designing efficient new algorithms.
In this paper, we develop a novel blind source separation (BSS) method for nonnegative and correlated data, particularly for the nearly degenerate data. The motivation lies in nuclear magnetic resonance (NMR) spectroscopy, where a multiple mixture NMR spectra are recorded to identify chemical compounds with similar structures (degeneracy).
Image matching is a fundamental problem in computer vision. One of the well-known techniques is SIFT (scale-invariant feature transform). SIFT searches for and extracts robust features in hierarchical image scale spaces for object identification. However it often lacks efficiency as it identifies many insignificant features such as tree leaves and grass tips in a natural building image. We introduce a content adaptive image matching approach by preprocessing the image with a color-entropy based segmentation and harmonic inpainting. Natural structures such as tree leaves have both high entropy and distinguished color, and so such a combined measure can be both discriminative and robust. The harmonic inpainting smoothly interpolates the image functions over the tree regions and so blurrs and reduces the features and their unnecessary matching there. Numerical experiments on building images show
Rapid and reliable detection and identification of unknown chemical substances are critical to homeland security. It is challenging to identify chemical components from a wide range of explosives. There are two key steps involved. One is a non-destructive and informative spectroscopic technique for data acquisition. The other is an associated library of reference features along with a computational method for feature matching and meaningful detection within or beyond the library.
The human eye can perceive a vast array of colors. Whether light or dark, the colors that our eyes can see are supposedly unlimited. However, this is not the case. In reality, every image has two aspects or descriptors to it, a reflectance and an illumination. While the reflectance essentially shows an images true color, the illumination is what causes the colors to seem different to the human eye. This effect, originally discovered by Helmholtz, is known as Color Constancy. Color Constancy ensures that the color the Human Visual System (HVS) receives is the true color of the image, regardless of illumination. As a result of this effect, in 1971, Land and McCann created the Retinex theory. Using the pixels in the image, Land tried to estimate the value of the reflectances and thus reveal the true color of the image. This theory was basically a color constancy algorithm that tried to explain why colors look different when exposed to lighting. By calculating the pixels, Land was able to depict the sameness in a gradient of colors in an image. However, the algorithm is both inefficient and complicated. Following their footsteps, many other people have tried to formulate new algorithms around the Lands original Retinex algorithm. In this paper, different methods such as least squares and discrete cosine transform are explained as well as how to enhance images using both Lands idea and histogram equalization.
Face tracking is an important computer vision technology that has been widely adopted in many areas, from cell phone applications to industry robots. In this paper, we introduce a novel way to parallelize a face contour detecting application based on the color-entropy preprocessed ChanVese model utilizing a total variation G-norm. This particular application is a complicated and unsupervised computational method requiring a large amount of calculations. Several core parts therein are difficult to parallelize due to heavily correlated data processing among iterations and pixels.
Speech signals are often produced or received in the presence of noise, which is known to degrade the performance of a speech recognition system. In this paper, a perception-and PDE-based nonlinear transformation was developed to process spoken words in noisy environment. Our goal is to distinguish essential speech features and suppress noise so that the processed words are better recognized by a computer software. The nonlinear transformation was made on the spectrogram (short-term Fourier spectra) of speech signals, which reveals the signal energy distribution in time and frequency. The transformation reduces noise through time adaptation (reducing temporally slowly varying portions of spectra) and enhances spectral peaks (formants) by evolving a focusing quadratic fourth-order PDE. Short-term spectra of speech signals were initially divided into three (low, mid and high) frequency bands based
A model based sound amplification method is proposed and studied to enhance the ability of the hearing impaired. The model consists of mechanical equations on basilar membrane and outer hair cell (OHC). The OHC is described by a nonlinear nonlocal feedforward model. In addition, a perceptive correction is defined to account for the lumped effect of higher level auditory processing, motivated by the intelligibility function of the hearing impaired. The gain functions are computed by matching the impaired model output to the perceptively weighted normal output, and qualitative agreement is achieved with NAL-NL1 prescription on clean signals. For noisy signals, an adaptive gain strategy is proposed based on the signal to noise ratios (SNR) computed by the model. The adaptive gain functions provide less gain as SNRs decrease so that the intelligibility can be higher with the adaptivity.
A nonlocally weighted soft-constrained natural gradient iterative method is introduced for robust blind separation in reverberant environment. The nonlocal weighting of the iterations promotes stability and convergence of the algorithm for long demixing filters. The scaling degree of freedom is controlled by soft-constraints built into the auxiliary difference equations. The small divisor problem of iterations in silence durations of speech is resolved. Computations on synthetic speech mixtures based on measured binaural room impulse responses show that the algorithm achieves higher signal-to-inteference ratio improvement than existing method (natural gradient time domain algorithm) in an office size room with reverberation time over 0.5 second.
Given a set of mixtures, blind source separation attempts to retrieve the source signals without or with very little information of the mixing process. We present a geometric approach for blind separation of nonnegative linear mixtures termed <i>facet component analysis</i>. The approach is based on facet identification of the underlying cone structure of the data. Earlier works focus on recovering the cone by locating its vertices (vertex component analysis) based on a mutual sparsity condition which requires each source signal to possess a stand-alone peak in its spectrum. We formulate alternative conditions so that enough data points fall on the facets of a cone instead of accumulating around the vertices. To find a regime of unique solvability, we make use of both geometric and density properties of the data points and develop an efficient facet identification method by combining data classification and linear
Motivated by the nuclear magnetic resonance (NMR) spectroscopy of biofluids (urine and blood serum), we present a recursive blind source separation (rBSS) method for nonnegative and correlated data. BSS problem arises when one attempts to recover a set of source signals from a set of mixture signals without knowing the mixing process. Various approaches have been developed to solve BSS problems relying on the assumption of statistical independence of the source signals. However, signal independence is not guaranteed in many real-world data like the NMR spectra of chemical compounds. The rBSS method introduced in this paper deals with the nonnegative and correlated signals arising in NMR spectroscopy of biofluids. The statistical independence requirement is replaced by a constraint which requires dominant interval(s) from each source signal over some of the other source signals in a
Motivated by applications in nuclear magnetic resonance (NMR) spectroscopy, we introduce a novel blind source separation (BSS) approach to treat nonnegative and correlated data. We consider the (over)-determined case where n sources are to be separated from n linear mixtures (n). Among the n source signals, there are n partially overlapping (Po) sources and one positive everywhere (Pe) source. This condition is applicable for many real-world signals such as NMR spectra of urine and blood serum for metabolic fingerprinting and disease diagnosis. The geometric properties of the mixture matrix and the sparseness structure of the source signals (in a transformed domain) are crucial to the identification of the mixing matrix and the sources. The method first identifies the mixing coefficients of the Pe source by exploiting geometry in data clustering. Then subsequent elimination of variables leads to a sub
A convex speech enhancement (CSE) method is presented based on convex optimization and pause detection of the speech sources. Channel spatial difference is identified for enhancing each speech source individually while suppressing other interfering sources. Sparse unmixing filters indicating channel spatial differences are sought by <i>l</i> <sub>1</sub> norm regularization and the split Bregman method. A subdivided split Bregman method is developed for efficiently solving the problem in severely reverberant environments. The speech pause detection is based on a binary mask source separation method. The CSE method is evaluated objectively and subjectively, and found to outperform a list of existing blind speech separation approaches on both synthetic and room recorded speech mixtures in terms of the overall computational speed and separation quality.
We study an efficient dynamic blind source separation algorithm of convolutive sound mixtures based on updating statistical information in the frequency domain, and minimizing the support of time domain demixing filters by a weighted least square method. The permutation and scaling indeterminacies of separation, and concatenations of signals in adjacent time frames are resolved with optimization of l 1 l norm on cross-correlation coefficients at multiple time lags. The algorithm is a direct method without iterations, and is adaptive to the environment. Computations on recorded benchmark mixtures of speech and music signals show excellent performance. The method in general separates a foreground source from a background of sounds as often encountered in realistic situations.