Curvature-aware simplification for point-sampled geometry

We propose a novel curvature-aware simplification technique for point-sampled geometry based on the locally optimal projection(LOP) operator.Our algorithm includes two new developments.First,a weight term related to surface variation at each point is introduced to the classic LOP operator.It produces output points with a spatially adaptive distribution.Second,for speeding up the convergence of our method,an initialization process is proposed based on geometry-aware stochastic sampling.Owing to the initialization,the relaxation process achieves a faster convergence rate than those initialized by uniform sampling.Our simplification method possesses a number of distinguishing features.In particular,it provides resilience to noise and outliers,and an intuitively controllable distribution of simplification.Finally,we show the results of our approach with publicly available point cloud data,and compare the results with those obtained using previous methods.Our method outperforms these methods on raw scanned data.     

A dynamic balanced flow for filtering point-sampled geometry

3D point data acquisition has become a practical approach for generating complex 3D shapes. Subsequent smoothing or denoising operations on these raw data sets are required before performing sophisticated modeling operations. Based on covariance analysis and constructed directional curvature, a new approach of anisotropic curvature flow is developed for filtering the point data set. By introducing a forcing term, a balanced flow equation is constructed, which allows the anisotropic diffusion flow to be restricted in the flow diffusion band of the original surface. Thus, the common problem of shape shrinkage that puzzles most current denoising approaches for point-sampled geometry is avoided. Applying dynamic balance techniques, the equation converges to the solution quickly with appealing physical interpretations. The algorithms operate directly on the discrete sample points, requiring no vertex connectivity information. They are shown to be computationally efficient, robust and simple to implement.     

GPU-based rendering of point-sampled water surfaces

Particle-based simulations are widely used to simulate fluids. We present a real-time rendering method for the results of particle-based simulations of water. Traditional approaches to visualize the results of particle-based simulations construct water surfaces that are usually represented by polygons. To construct water surfaces from the results of particle-based simulations, a density function is assigned to each particle and a density field is computed by accumulating the values of the density functions of all particles. However, the computation of the density field is time consuming. To address this problem, we propose an efficient calculation of density field using a graphics processing unit (GPU). We present a rendering method for water surfaces sampled by points. The use of the GPU permits efficient simulation of optical effects, such as refraction, reflection, and caustics.     

High frequency geometric detail manipulation and editing for point-sampled surfaces

In this paper, based on the new definition of high frequency geometric detail for point-sampled surfaces, a new approach for detail manipulation and a detail-preserving editing framework are proposed. Geometric detail scaling and enhancement can always produce fantastic effects by directly manipulating the geometric details of the underlying geometry. Detail-preserving editing is capable of preserving geometric details during the shape deformation of point-sampled model. For efficient editing, the point set of the model is first clustered by a mean shift scheme, according to its anisotropic geometric features and each cluster is abstracted as a simplification sample point (SSP). Our editing operation is implemented by manipulating the SSP first and then diffusing the deformation to all sample points on the underlying geometry. As a postprocessing step, a new up-sampling and relaxation procedure is proposed to refine the deformed model. The effectiveness of the proposed method is demonstrated by several examples.     

Detail-generating geometry completion for point-sampled geometry

In this paper, we present a novel method for detail-generating geometry completion over point-sampled geometry. The main idea consists of converting the context-based geometry completion into the detail-based texture completion on the surface. According to the influence region of boundary points surrounding a hole, a smooth patch covering the hole is first constructed using radial base functions. By applying region-growing clustering to the patch, the patching units for further completion with geometry details is then produced, and using the trilateral filtering operator formulated by us, the geometry-detail texture of each sample point on the input geometry is determined. The geometry details on the smooth completed patch are finally generated by optimizing a constrained global texture energy function on the point-sampled surfaces. Experimental results demonstrate that the method can achieve efficient completed patches that not only conform with their boundaries, but also contain the plausible 3D surface details.     

A quasi-Monte Carlo method for computing areas of point-sampled surfaces

A novel and efficient quasi-Monte Carlo method for computing the area of a point-sampled surface with associated surface normal for each point is presented. Our method operates directly on the point cloud without any surface reconstruction procedure. Using the Cauchy-Crofton formula, the area of the point-sampled surface is calculated by counting the number of intersection points between the point cloud and a set of uniformly distributed lines generated with low-discrepancy sequences. Based on a clustering technique, we also propose an effective algorithm for computing the intersection points of a line with the point-sampled surface. By testing on a number of point-based models, experiments suggest that our method is more robust and more efficient than those conventional approaches based on surface reconstruction.     

Defining, contouring, and visualizing scalar functions on point-sampled surfaces

This paper addresses the definition, contouring, and visualization of scalar functions on unorganized point sets, which are sampled from a surface in 3D space; the proposed framework builds on moving least-squares techniques and implicit modeling. Given a scalar function f:P→R, defined on a point set P, the idea behind our approach is to exploit the local connectivity structure of the k-nearest neighbor graph of P and mimic the contouring of scalar functions defined on triangle meshes. Moving least-squares and implicit modeling techniques are used to extend f from P to the surface M underlying P. To this end, we compute an analytical approximation of f that allows us to provide an exact differential analysis of , draw its iso-contours, visualize its behavior on and around M, and approximate its critical points. We also compare moving least-squares and implicit techniques for the definition of the scalar function underlying f and discuss their numerical stability and approximation accuracy. Finally, the proposed framework is a starting point to extend those processing techniques that build on the analysis of scalar functions on 2-manifold surfaces to point sets.     

基于分层聚类及重采样的大规模数据分类

针对大规模数据的分类问题,将监督学习与无监督学习结合起来,提出了一种基于分层聚类和重采样技术的支持向量机(SVM)分类方法。该方法首先利用无监督学习算法中的k-means聚类分析技术将数据集划分成不同的子集,然后对各个子集进行逐类聚类,分别选出各类中心邻域内的样本点,构成最终的训练集,最后利用支持向量机对所选择的最具代表样本点进行训练建模。实验表明,所提方法可以大幅度降低支持向量机的学习代价,其分类精度比随机欠采样更优,而且可以达到采用完整数据集训练所得的结果     

Direct boolean intersection between acquired and designed geometry

In this paper, a new shape modeling approach that can enable direct Boolean intersection between acquired and designed geometry without model conversion is presented. At its core is a new method that enables direct intersection and Boolean operations between designed geometry (objects bounded by NURBS and polygonal surfaces) and scanned geometry (objects represented by point cloud data).We use the moving least-squares (MLS) surface as the underlying surface representation for acquired point-sampled geometry. Based on the MLS surface definition, we derive closed formula for computing curvature of planar curves on the MLS surface. A set of intersection algorithms including line and MLS surface intersection, curvature-adaptive plane and MLS surface intersection, and polygonal mesh and MLS surface intersection are successively developed. Further, an algorithm for NURBS and MLS surface intersection is then developed. It first adaptively subdivides NURBS surfaces into polygonal mesh, and then intersects the mesh with the MLS surface. The intersection points are mapped to the NURBS surface through the Gauss-Newton method.Based on the above algorithms, a prototype system has been implemented. Through various examples from the system, we demonstrate that direct Boolean intersection between designed geometry and acquired geometry offers a useful and effective means for the shape modeling applications where point-cloud data is involved.     

Feature sensitive re-sampling of point set surfaces with Gaussian spheres

Feature sensitive simplification and re-sampling of point set surfaces is an important and challenging issue for many computer graphics and geometric modeling applications.Based on the regular sampling of the Gaussian sphere and the surface normals mapping onto the Gaussian sphere,an adaptive re-sampling framework for point set surfaces is presented in this paper,which includes a naive sampling step by index propagation and a novel cluster optimization step by normalized rectification.Our proposed re-sampling scheme can generate non-uniformly distributed discrete sample points for the underlying point sets in a feature sensitive manner.The intrinsic geometric features of the underlying point set surfaces can be preserved efficiently due to our adaptive re-sampling scheme.A novel splat rendering technique is adopted to illustrate the efficiency of our re-sampling scheme.Moreover,a numerical error statistics and surface reconstruction for simplified models are also given to demonstrate the effectiveness of our algorithm in term of the simplified quality of the point set surfaces.     

基于期望最大化算法的音频取证中的篡改检测

音频取证中的插值检测是信号篡改检测的重要方面。因为信号的篡改经常伴随着重采样操作,而重采样后的插值信号会引入周期性信息。应用期望最大化（EM）算法能针对这种周期信息估计参数,从而检测出信号是否被篡改。为了使EM算法迭代效果更好,更适用于音频信号的插值检测问题,提出针对音频信号的特点,引入音频幅度直方图,排除短时静音和增加样本点数的方法。另外还提出了用频谱统计矩作为特征的方法,使统计分类稳定有效。最后通过音频取证中检测信号是否重采样的统计分类实验,表明整个检测流程能达到较高的准确率,并且在局部篡改实验中也同样有效。     

Managing complex data and geometry in parallel structured AMR applications

Adaptive mesh refinement (AMR) is an increasingly important simulation methodology for many science and engineering problems. AMR has the potential to generate highly resolved simulations efficiently by dynamically refining the computational mesh near key numerical solution features. AMR requires more complex numerical algorithms and programming than uniform fixed mesh approaches. Software libraries that provide general AMR functionality can ease these burdens significantly. A major challenge for library developers is to achieve adequate flexibility to meet diverse and evolving application requirements. In this paper, we describe the design of software abstractions for general AMR data management and parallel communication operations in SAMRAI, an object-oriented C++ structured AMR (SAMR) library developed at Lawrence Livermore National Laboratory (LLNL). The SAMRAI infrastructure provides the foundation for a variety of diverse application codes at LLNL and elsewhere. We illustrate SAMRAI functionality by describing how its unique features are used in these codes which employ complex data structures and geometry. We highlight capabilities for moving and deforming meshes, coupling multiple SAMR mesh hierarchies, and immersed and embedded boundary methods for modeling complex geometrical features. We also describe how irregular data structures, such as particles and internal mesh boundaries, may be implemented using SAMRAI tools without excessive application programmer effort. This work was performed under the auspices of the US Department of Energy by University of California Lawrence Livermore National Laboratory under contract number W-7405-Eng-48 and is released under UCRL-JRNL-214559.     

An adaptive framework for 3D graphics over networks

Access to and transmission of 3D models over networks becomes increasingly popular. However, the performance and quality of access to remote 3D models strongly depends on system load conditions and the capabilities of the various system components, such as clients, servers, and interconnect. The network graphics framework (NGF) integrates various transmission methods for downloading 3D models in a client–server environment. The NGF automatically selects the optimal transmission method for a given pair of client and server, taking into account characteristics of the model to be transmitted, critical environment conditions, user preferences and the capabilities of the client and the server. The NGF aims to provide constant quality of service across different clients and under varying environment conditions.     

Data spread-based entropy clustering method using adaptive learning

Clustering analysis is to identify inherent structures and discover useful information from large amount of data. However, the decision makers may suffer insufficient understanding the nature of the data and do not know how to set the optimal parameters for the clustering method. To overcome the drawback above, this paper proposes a new entropy clustering method using adaptive learning. The proposed method considers the data spreading to determine the adaptive threshold within parameters optimized by adaptive learning. Four datasets in UCI database are used as the experimental data to compare the accuracy of the proposed method with the listing clustering methods. The experimental results indicate that the proposed method is superior to the listing methods.     

节点密度自适应的传感器网络加权分簇算法

无线传感器网络的分簇密度不确定会导致网络的有效性降低、生存周期减少等问题.提出了一种节点密度自适应的传感器网络加权分簇算法,通过设定权值.将节点的节点度、与邻节点的平均距离及节点的剩余能量考虑在内,保证综合性能最好的节点成为簇头.再通过控制簇头发射功率使簇内节点密度控制在合理范围内.该分簇算法优化了簇头选择,均衡了网络节点的能量消耗,延长了网络的生命周期.最后通过仿真进一步验证该分簇算法的性能.     

A workbench for computational geometry

We describe the design and implementation of a workbench for computational geometry. We discuss issues arising from this implementation, including comparisons of different algorithms for constant factors, code size, and ease of implementation. The workbench is not just a library of computational geometry algorithms and data structures, but is designed as a geometrical programming environment, providing tools for: creating, editing, and manipulating geometric objects; demonstrating and animating geometric algorithms; and, most importantly, for implementing and maintaining complex geometric algorithms.This research was partially supported by the Natural Sciences and Engineering Research Council of Canada, Carleton University, and the Univeristy of Passau. Work on this project was carried out in part while A. Knight and J.-R. Sack were at the University of Passau.     

An adaptive spatial clustering algorithm based on delaunay triangulation

In this paper, an adaptive spatial clustering algorithm based on Delaunay triangulation (ASCDT for short) is proposed. The ASCDT algorithm employs both statistical features of the edges of Delaunay triangulation and a novel spatial proximity definition based upon Delaunay triangulation to detect spatial clusters. Normally, this algorithm can automatically discover clusters of complicated shapes, and non-homogeneous densities in a spatial database, without the need to set parameters or prior knowledge. The user can also modify the parameter to fit with special applications. In addition, the algorithm is robust to noise. Experiments on both simulated and real-world spatial databases (i.e. an earthquake dataset in China) are utilized to demonstrate the effectiveness and advantages of the ASCDT algorithm.     

Localized adaptive bounds for approximation-based backstepping

Recent research has established the utility of adaptive bounds on model uncertainty in adaptive approximation-based control. Such bounds have utility both for robust control law design and for self-organizing approximators that could adjust the number of basis elements N by adding additional approximation resources in the regions where the approximation error bound is large. Existing adaptive bounding methods utilize algorithms with global forgetting. In this article, we investigate methods to develop bounds on approximation accuracy that involve local forgetting. The importance of local versus global forgetting is motivated in the text and illustrated with an example.     

Control Lyapunov functions for adaptive nonlinear stabilization

For the problem of stabilization of nonlinear systems linear in unknown constant parameters, we introduce the concept of an adaptive control Lyapunov function (aclf) and use Sontag's constructive proof of Artstein's theorem to design an adaptive controller. In this framework the problem of adaptive stabilization of a nonlinear system is reduced to the problem of nonadaptive stabilization of a modified system. To illustrate the construction of aclf's we give an adaptive backstepping lemma which recovers our earlier design.     

基于聚类分析与几何的目标特征敏感性评估算法

为克服在较少先验知识的情况下,人为选择目标特征进行分类识别的盲目性,提出一种基于聚类分析与几何学的目标特征评估方法.该方法在类内类间距离的基础上引入几何学中有关圆的知识,定义了样本在特征空间中分布的＂紧密度＂、＂分离度＂函数和＂松紧度＂权重,以考察目标特征对目标样本之间的分类敏感性,并根据评估结果选取适当特征构成一个新的联合特征,以提高对目标的分类识别效率.最后通过仿真验证了该方法的有效性.