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.     

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.     

Adaptive fuzzy c-means clustering algorithm for interval data type based on interval-dividing technique

Clustering for symbolic data type is a necessary process in many scientific disciplines, and the fuzzy c-means clustering for interval data type (IFCM) is one of the most popular algorithms. This paper presents an adaptive fuzzy c-means clustering algorithm for interval-valued data based on interval-dividing technique. This method gives a fuzzy partition and a prototype for each fuzzy cluster by optimizing an objective function. And the adaptive distance between the pattern and its cluster center varies with each algorithm iteration and may be either different from one cluster to another or the same for all clusters. The novel part of this approach is that it takes into account every point in both intervals when computing the distance between the cluster and its representative. Experiments are conducted on synthetic data sets and a real data set. To compare the comprehensive performance of the proposed method with other four existing methods, the corrected rand index, the value of objective function and iterations are introduced as the evaluation criterion. Clustering results demonstrate that the algorithm proposed in this paper has remarkable advantages.     

A New Fuzzy Set Merging Technique Using Inclusion-Based Fuzzy Clustering

This paper proposes a new method of merging parameterized fuzzy sets based on clustering in the parameters space, taking into account the degree of inclusion of each fuzzy set in the cluster prototypes. The merger method is applied to fuzzy rule base simplification by automatically replacing the fuzzy sets corresponding to a given cluster with that pertaining to cluster prototype. The feasibility and the performance of the proposed method are studied using an application in mobile robot navigation. The results indicate that the proposed merging and rule base simplification approach leads to good navigation performance in the application considered and to fuzzy models that are interpretable by experts. In this paper, we concentrate mainly on fuzzy systems with Gaussian membership functions, but the general approach can also be applied to other parameterized fuzzy sets.     

Feature-Preserving Surface Reconstruction and Simplification from Defect-Laden Point Sets

We introduce a robust and feature-capturing surface reconstruction and simplification method that turns an input point set into a low triangle-count simplicial complex. Our approach starts with a (possibly non-manifold) simplicial complex filtered from a 3D Delaunay triangulation of the input points. This initial approximation is iteratively simplified based on an error metric that measures, through optimal transport, the distance between the input points and the current simplicial complex—both seen as mass distributions. Our approach is shown to exhibit both robustness to noise and outliers, as well as preservation of sharp features and boundaries. Our new feature-sensitive metric between point sets and triangle meshes can also be used as a post-processing tool that, from the smooth output of a reconstruction method, recovers sharp features and boundaries present in the initial point set.     

一种基于椭圆体聚类的高维索引方法

提出一种在椭圆体聚类上进行主分量排序的高维索引方法, 线性访问较少的数据点就可完成k近邻搜索过程。该方法对数据集进行椭圆体聚类划分,在KL变换域上建立近似向量。在k近邻搜索过程中,采用部分失真搜索算法,按照距离下界由小到大的顺序依次搜索各个椭圆体聚类。在大型高维图像特征库上的实验表明,与其他向量近似方法相比,该索引结构降低近似向量的访问数量,能够较显著提高k近邻搜索速度。     

A symmetry based multiobjective clustering technique for automatic evolution of clusters

In this paper the problem of automatic clustering a data set is posed as solving a multiobjective optimization (MOO) problem, optimizing a set of cluster validity indices simultaneously. The proposed multiobjective clustering technique utilizes a recently developed simulated annealing based multiobjective optimization method as the underlying optimization strategy. Here variable number of cluster centers is encoded in the string. The number of clusters present in different strings varies over a range. The points are assigned to different clusters based on the newly developed point symmetry based distance rather than the existing Euclidean distance. Two cluster validity indices, one based on the Euclidean distance, XB-index, and another recently developed point symmetry distance based cluster validity index, Sym-index, are optimized simultaneously in order to determine the appropriate number of clusters present in a data set. Thus the proposed clustering technique is able to detect both the proper number of clusters and the appropriate partitioning from data sets either having hyperspherical clusters or having point symmetric clusters. A new semi-supervised method is also proposed in the present paper to select a single solution from the final Pareto optimal front of the proposed multiobjective clustering technique. The efficacy of the proposed algorithm is shown for seven artificial data sets and six real-life data sets of varying complexities. Results are also compared with those obtained by another multiobjective clustering technique, MOCK, two single objective genetic algorithm based automatic clustering techniques, VGAPS clustering and GCUK clustering.     

基于顶点聚类的多面体模型简化方法

本文介绍一种基于顶点聚类的多面体模型简化方法 ,该方法主要由三部分组成 :( 1 )把多面体模型划分成若干个小单元 ;( 2 )落在同一单元中的一组网格顶点用一个代表顶点表示 ;( 3)由代表顶点进行消去操作 ,得到简化的三角形网格模型。该方法实现简单、速度快 ,并且具有通用性。     

Visual exploration of high dimensional scalar functions

An important goal of scientific data analysis is to understand the behavior of a system or process based on a sample of the system. In many instances it is possible to observe both input parameters and system outputs, and characterize the system as a high-dimensional function. Such data sets arise, for instance, in large numerical simulations, as energy landscapes in optimization problems, or in the analysis of image data relating to biological or medical parameters. This paper proposes an approach to analyze and visualizing such data sets. The proposed method combines topological and geometric techniques to provide interactive visualizations of discretely sampled high-dimensional scalar fields. The method relies on a segmentation of the parameter space using an approximate Morse-Smale complex on the cloud of point samples. For each crystal of the Morse-Smale complex, a regression of the system parameters with respect to the output yields a curve in the parameter space. The result is a simplified geometric representation of the Morse-Smale complex in the high dimensional input domain. Finally, the geometric representation is embedded in 2D, using dimension reduction, to provide a visualization platform. The geometric properties of the regression curves enable the visualization of additional information about each crystal such as local and global shape, width, length, and sampling densities. The method is illustrated on several synthetic examples of two dimensional functions. Two use cases, using data sets from the UCI machine learning repository, demonstrate the utility of the proposed approach on real data. Finally, in collaboration with domain experts the proposed method is applied to two scientific challenges. The analysis of parameters of climate simulations and their relationship to predicted global energy flux and the concentrations of chemical species in a combustion simulation and their integration with temperature.     

改进的蚂蚁聚类算法*

提出了一种改进的基于对称点距离的蚂蚁聚类算法。该算法不再采用Euclidean距离来计算类内对象的相似性,而是使用新的对称点距离来计算相似性,在处理带有对称性质的数据集时,可以有效地识别给定数据集的聚类数目和合适的划分。在该算法中,用人工蚂蚁代表数据对象,根据算法给定的聚类规则来寻找最合适的聚类划分。最后用本算法与标准的蚂蚁聚类算法分别对不同的数据集进行了聚类实验。实验结果证实了算法的有效性。     

A general stochastic clustering method for automatic cluster discovery

Finding clusters in data is a challenging problem. Given a dataset, we usually do not know the number of natural clusters hidden in the dataset. The problem is exacerbated when there is little or no additional information except the data itself. This paper proposes a general stochastic clustering method that is a simplification of nature-inspired ant-based clustering approach. It begins with a basic solution and then performs stochastic search to incrementally improve the solution until the underlying clusters emerge, resulting in automatic cluster discovery in datasets. This method differs from several recent methods in that it does not require users to input the number of clusters and it makes no explicit assumption about the underlying distribution of a dataset. Our experimental results show that the proposed method performs better than several existing methods in terms of clustering accuracy and efficiency in majority of the datasets used in this study. Our theoretical analysis shows that the proposed method has linear time and space complexities, and our empirical study shows that it can accurately and efficiently discover clusters in large datasets in which many existing methods fail to run.     

面向轨迹数据发布的个性化差分隐私保护机制

移动互联网和智能手机的普及大大方便了人们的生活,并由此产生了大量的轨迹数据.通过对发布的轨迹数据进行分析,能够有效提高基于位置服务的质量,进而推动智慧城市相关应用的发展,例如智能交通管理、基础设计规划以及道路拥塞预警与检测.然而,由于轨迹数据中包含用户的敏感信息,直接发布原始的轨迹数据会对个人隐私造成严重威胁.差分隐私作为一种具备严格形式化定义、强隐私性保证的安全机制,已经被广泛应用于轨迹数据的发布中.但是,现有的方法假定用户具有相同的隐私偏好,并且为所有用户提供相同级别的隐私保护,这会导致对某些用户提供的隐私保护级别不足,而某些用户则获得过多的隐私保护.为满足不同用户的隐私保护需求,提高数据可用性,本文假设用户具备不同的隐私需求,提出了一种面向轨迹数据的个性化差分隐私发布机制.该机制利用Hilbert曲线提取轨迹数据在各个时刻的分布特征,生成位置聚簇,使用抽样机制和指数机制选择各个位置聚簇的代表元,进而利用位置代表元对原始轨迹数据进行泛化,从而生成待发布轨迹数据.在真实轨迹数据集上的实验表明,与基于标准差分隐私的方法相比,本文提出的机制在隐私保护和数据可用性之间提供了更好的平衡.     

A multivariate fuzzy c-means method

Fuzzy c-means (FCMs) is an important and popular unsupervised partitioning algorithm used in several application domains such as pattern recognition, machine learning and data mining. Although the FCM has shown good performance in detecting clusters, the membership values for each individual computed to each of the clusters cannot indicate how well the individuals are classified. In this paper, a new approach to handle the memberships based on the inherent information in each feature is presented. The algorithm produces a membership matrix for each individual, the membership values are between zero and one and measure the similarity of this individual to the center of each cluster according to each feature. These values can change at each iteration of the algorithm and they are different from one feature to another and from one cluster to another in order to increase the performance of the fuzzy c-means clustering algorithm. To obtain a fuzzy partition by class of the input data set, a way to compute the class membership values is also proposed in this work. Experiments with synthetic and real data sets show that the proposed approach produces good quality of clustering.     

Distribution Free Decomposition of Multivariate Data

We present a practical approach to nonparametric cluster analysis of large data sets. The number of clusters and the cluster centres are automatically derived by mode seeking with the mean shift procedure on a reduced set of points randomly selected from the data. The cluster boundaries are delineated using a k-nearest neighbour technique. The proposed algorithm is stable and efficient, a 10,000 point data set being decomposed in only a few seconds. Complex clustering examples and applications are discussed, and convergence of the gradient ascent mean shift procedure is demonstrated for arbitrary distribution and cardinality of the data. Received: 7 October 1998?Accepted: 9 October 1998     

Clustering categorical data sets using tabu search techniques

Clustering methods partition a set of objects into clusters such that objects in the same cluster are more similar to each other than objects in different clusters according to some defined criteria. The fuzzy k-means-type algorithm is best suited for implementing this clustering operation because of its effectiveness in clustering data sets. However, working only on numeric values limits its use because data sets often contain categorical values. In this paper, we present a tabu search based clustering algorithm, to extend the k-means paradigm to categorical domains, and domains with both numeric and categorical values. Using tabu search based techniques, our algorithm can explore the solution space beyond local optimality in order to aim at finding a global solution of the fuzzy clustering problem. It is found that the clustering results produced by the proposed algorithm are very high in accuracy.     

基于相似查询树的快速密文检索方法

随着云计算的广泛应用,数据中心的数据量急速增加,同时,用户文档通常包含隐私敏感信息,需要先加密然后上传到云服务器,面对如此大量的密文数据,现有技术在大数据量的密文数据上的检索效率很低.针对此问题,本文提出在大数据下的基于相似查询树的密文检索方法(MRSE-SS),该方法通过设置聚类中心和成员之间的最大距离对文档向量进行聚类,并把中心向量看成n维超球体的球心,最大距离作为半径,再逐步将小聚类聚合成大聚类.使用该方法构建的密文文档集合,在查询阶段仅需检索查询向量相邻的聚类即可获得理想的查询结果集合,从而提高了密文检索的效率.本文还以《软件学报》期刊最近10年的论文作为样本进行了实验,数据集中选取2900篇文章和4800个关键词,实验结果显示,当文档集个数呈指数增长的时候,检索时间仅呈线性增长,并且检索结果的关联性比传统检索方法更强.     

基于DSC的多文本自动摘要

多文本摘要的目标是对给定的查询和多篇文本（文本集）,创建一个简洁明了的摘要,要求该摘要能够表达这些文本的关键内容,同时和给定的查询相关。一个给定的文本集通常包含一些主题,而且每个主题由一类句子来表示,一个优秀的摘要应该要包含那些最重要的主题。如今大部分的方法是建立一个模型来计算句子得分,然后选择得分最高的部分句子来生成摘要。不同于这些方法,我们更加关注文本的主题而不是句子,把如何生成摘要的问题看成一个主题的发现,排序和表示的问题。我们首次引入dominant sets cluster（DSC）来发现主题,然后建立一个模型来对主题的重要性进行评估,最后兼顾代表性和无重复性来从各个主题中选择句子组成摘要。我们在DUC2005、2006、2007三年的标准数据集上进行了实验,最后的实验结果证明了该方法的有效性。     

自适应K-means聚类的散乱点云精简

目的 点云精简是曲面重建等点云处理的一个重要前提,针对以往散乱点云精简算法的精简结果存在失真较大、空洞及不适用于片状点云的问题,提出一种自适应K-means聚类的点云精简算法。方法 首先,根据k邻域计算每个数据点的曲率、点法向与邻域点法向夹角的平均值、点到邻域重心的距离、点到邻域点的平均距离,据此运用多判别参数混合的特征提取方法识别并保留特征点,包括曲面尖锐点和边界点;然后,对点云数据建立自适应八叉树,为K-means聚类提供与点云密度分布相关的初始化聚类中心以及K值;最后,遍历整个聚类,如果聚类结果中含有特征点则剔除其中的特征点并更新聚类中心,计算更新后聚类中数据点的最大曲率差,将最大曲率差大于设定阈值的聚类进行细分,保留最终聚类中距聚类中心最近的数据点。结果 在聚类方面,将传统的K-means聚类和自适应K-means聚类算法应用于bunny点云,后者在聚类的迭代次数、评价函数值和时间上均优于前者;在精简方面,将提出的精简算法应用于封闭及片状两种不同类型的点云,在精简比例为1/5时fandisk及saddle模型的精简误差分别为0.29×10^-3、-0.41×10^-3和0.037、-0.094,对于片状的saddle点云模型,其边界收缩误差为0.030 805,均小于栅格法和曲率法。结论 本文提出的散乱点云精简算法可应用于封闭及片状点云,精简后的数据点分布均匀无空洞,对片状点云进行精简时能够保护模型的边界数据点。     

保留几何特征的散乱点云简化方法

针对散乱点云简化时经常丢失过多的几何特征,提出一种保留几何特征的简化方法。首先采用均匀栅格法划分点云空间;然后分别以点云中的数据点为球心构建包围球,并在包围球中查找数据点的K邻域;随后构造一个非负函数用于度量重建曲面在各点处的曲率,进而提取并保留点云中的特征点;最后根据法向量的内积阈值对包围球中的非特征点进行适度简化。实验结果表明该方法不仅能够充分保留点云中的几何特征,而且具有速度快的特点。