Poisson Surface Reconstruction with Envelope Constraints

Reconstructing surfaces from scanned 3D points has been an important research area for several decades. One common approach that has proven efficient and robust to noise is implicit surface reconstruction, i.e. fitting to the points a 3D scalar function (such as an indicator function or signed-distance field) and then extracting an isosurface. Though many techniques fall within this category, existing methods either impose no boundary constraints or impose Dirichlet/Neumann conditions on the surface of a bounding box containing the scanned data. In this work, we demonstrate the benefit of supporting Dirichlet constraints on a general boundary. To this end, we adapt the Screened Poisson Reconstruction algorithm to input a constraint envelope in addition to the oriented point cloud. We impose Dirichlet boundary conditions, forcing the reconstructed implicit function to be zero outside this constraint surface. Using a visual hull and/or depth hull derived from RGB-D scans to define the constraint envelope, we obtain substantially improved surface reconstructions in regions of missing data.     

GPU-based Fast Ray Casting for a Large Number of Metaballs

Metaballs are implicit surfaces widely used to model curved objects, represented by the isosurface of a density field defined by a set of points. Recently, the results of particle‐based simulations have been often visualized using a large number of metaballs, however, such visualizations have high rendering costs. In this paper we propose a fast technique for rendering metaballs on the GPU. Instead of using polygonization, the isosurface is directly evaluated in a per‐pixel manner. For such evaluation, all metaballs contributing to the isosurface need to be extracted along each viewing ray, on the limited memory of GPUs. We handle this by keeping a list of metaballs contributing to the isosurface and efficiently update it. Our method neither requires expensive precomputation nor acceleration data structures often used in existing ray tracing techniques. With several optimizations, we can display a large number of moving metaballs quickly.     

Visual Analysis of Multi‐Dimensional Categorical Data Sets

We present a set of interactive techniques for the visual analysis of multi‐dimensional categorical data. Our approach is based on multiple correspondence analysis (MCA), which allows one to analyse relationships, patterns, trends and outliers among dependent categorical variables. We use MCA as a dimensionality reduction technique to project both observations and their attributes in the same 2D space. We use a treeview to show attributes and their domains, a histogram of their representativity in the data set and as a compact overview of attribute‐related facts. A second view shows both attributes and observations. We use a Voronoi diagram whose cells can be interactively merged to discover salient attributes, cluster values and bin categories. Bar chart legends help assigning meaning to the 2D view axes and 2D point clusters. We illustrate our techniques with real‐world application data.     

MultiClusterTree: Interactive Visual Exploration of Hierarchical Clusters in Multidimensional Multivariate Data

Visual analytics of multidimensional multivariate data is a challenging task because of the difficulty in understanding metrics in attribute spaces with more than three dimensions. Frequently, the analysis goal is not to look into individual records but to understand the distribution of the records at large and to find clusters of records with similar attribute values. A large number of (typically hierarchical) clustering algorithms have been developed to group individual records to clusters of statistical significance. However, only few visualization techniques exist for further exploring and understanding the clustering results. We propose visualization and interaction methods for analyzing individual clusters as well as cluster distribution within and across levels in the cluster hierarchy. We also provide a clustering method that operates on density rather than individual records. To not restrict our search for clusters, we compute density in the given multidimensional multivariate space. Clusters are formed by areas of high density. We present an approach that automatically computes a hierarchical tree of high density clusters. To visually represent the cluster hierarchy, we present a 2D radial layout that supports an intuitive understanding of the distribution structure of the multidimensional multivariate data set. Individual clusters can be explored interactively using parallel coordinates when being selected in the cluster tree. Furthermore, we integrate circular parallel coordinates into the radial hierarchical cluster tree layout, which allows for the analysis of the overall cluster distribution. This visual representation supports the comprehension of the relations between clusters and the original attributes. The combination of the 2D radial layout and the circular parallel coordinates is used to overcome the overplotting problem of parallel coordinates when looking into data sets with many records. We apply an automatic coloring scheme based on the 2D radial layout of the hierarchical cluster tree encoding hue, saturation, and value of the HSV color space. The colors support linking the 2D radial layout to other views such as the standard parallel coordinates or, in case data is obtained from multidimensional spatial data, the distribution in object space.     

A simple GPU-based approach for 3D Voronoi diagram construction and visualization

In this paper we propose a simple GPU-based approach for discrete incremental approximation of 3D Voronoi diagram. By constructing region maps via GPU. Nearest sites, space clustering, and shortest distance query can be quickly answered by looking up the region map. In addition, we propose another representation of the 3D Voronoi diagram for visualization.     

Approximating the Generalized Voronoi Diagram of Closely Spaced Objects

We present an algorithm to compute an approximation of the generalized Voronoi diagram (GVD) on arbitrary collections of 2D or 3D geometric objects. In particular, we focus on datasets with closely spaced objects; GVD approximation is expensive and sometimes intractable on these datasets using previous algorithms. With our approach, the GVD can be computed using commodity hardware even on datasets with many, extremely tightly packed objects. Our approach is to subdivide the space with an octree that is represented with an adjacency structure. We then use a novel adaptive distance transform to compute the distance function on octree vertices. The computed distance field is sampled more densely in areas of close object spacing, enabling robust and parallelizable GVD surface generation. We demonstrate our method on a variety of data and show example applications of the GVD in 2D and 3D.     

Generating and updating multiplicatively weighted Voronoi diagrams for point,line and polygon features in GIS

A Voronoi diagram is an interdisciplinary concept that has been applied to many fields. In geographic information systems (GIS), existing capabilities for generating Voronoi diagrams normally focus on ordinary (not weighted) point (not linear or area) features. For better integration of Voronoi diagram models and GIS, a raster-based approach is developed, and implemented seamlessly as an ArcGIS extension using ArcObjects. In this paper, the methodology and implementation of the extension are described, and examples are provided for ordinary or weighted point, line, and polygon features. Advantages and limitations of the extensions are also discussed. The extension has the following features: (1) it works for point, line, and polygon vector features; (2) it can generate both ordinary and multiplicatively weighted Voronoi diagrams in vector format; (3) it can assign non-spatial attributes of input features to Voronoi cells through spatial joining; and (4) it can produce an ordinary or a weighted Euclidean distance raster dataset for spatial modeling applications. The results can be conveniently combined with other GIS datasets to support both vector-based spatial analysis and raster-based spatial modeling.     

The Hausdorff Voronoi Diagram of Point Clusters in the Plane

We study the Hausdorff Voronoi diagram of point clusters in the plane, a generalization ofVoronoi diagrams based on the Hausdorff distance function. We derive a tight combinatorial bound on the structural complexity of this diagram and present a plane sweep algorithm for its construction. In particular, we show that the size of the Hausdorff Voronoi diagram is (n + m), where n is the number of points on the convex hulls of the given clusters, and m is the number of crucial supporting segments between pairs of crossing clusters. The plane sweep algorithm generalizes the standard plane sweep paradigm for the construction of Voronoi diagrams with the ability to handle disconnected Hausdorff Voronoi regions. The Hausdorff Voronoi diagram finds direct application in the problem of computing the critical area of a VLSI layout, a measure reflecting the sensitivity of the VLSI design to spot defects during manufacturing.     

一种基于逐点插入Delaunay三角剖分生成Voronoi图的算法

采用改进的逐点插入算法生成Voronoi图。该算法在逐点插入的过程中生成凸壳,进而生成Delaunay三角剖分。在生成Voronoi图的实现过程中,通过遍历三角形的边顶点快速识别相关的三角形组,进而生成Voronoi图。试验结果表明,该算法能实现,成功生成Voronoi图。     

基于密度峰值和近邻优化的聚类算法

针对密度峰值算法在选取聚类中心时的时间复杂度过高,需要人工选择截断距离并且处理流形数据时有可能出现多个密度峰值,导致聚类准确率下降等问题,提出一种新的密度峰值聚类算法,从聚类中心选择、离群点筛选、数据点分配三方面进行讨论和分析,并给出相应的聚类算法。在聚类中心的选择上采取KNN的思想计算数据点的密度,离群点的筛选和剪枝以及数据点分配则利用Voronoi图的性质,结合数据点的分布特征进行处理,并在最后应用层次聚类的思想以合并相似类簇,提高聚类准确率。实验结果表明:所提算法与实验对比算法相比较,具有较好的聚类效果和准确性。     

Constructing the generalized local Voronoi diagram from laser rangescanner data

We consider the problem of building local free space representation by a circular-base robot, operating in an unknown bounded planar environment populated by obstacles of arbitrary shape. In the unknown environment, the robot depends on its sensors; in our case, this is the laser range scanner. A new structure is represented, termed the generalized local Voronoi diagram (GLVD), constructed directly from sensory data, obtained from an observation of the local environment, that is from the visible region, GLVD is obtained by deleting some edges from the ordinary Voronoi diagram, which is generated by the measured scanned points from the visible region. Crucial for the acquisition of the GLVD is the clusterization of the scanned points. Clusterization means grouping of the scanned points into distinct clusters, each having a specific property, e.g., for a particular point in the cluster, the nearest neighboring point should not lie further than a prescribed distance away. The relevant part of GLVD, the portion of GLVD which is in accordance with the generalized Voronoi diagram of the environment, is determined. Eventual differences between these two structures are discussed and experimental results are presented. With the superposition of several GLVDs we show that this structure can be used to construct a global map of the environment, for which the position and the orientation of the robot is needed     

基于空间邻近的点目标聚类方法

空间聚类是空间数据挖掘和知识发现领域的主要研究方向之一,但点目标空间分布密度的不均匀、分布形状的多样化,以及"多桥"链接问题的存在,使得基于距离和密度的聚类算法不能高效且有效地识别聚集性高的点目标。提出了基于空间邻近的点目标聚类方法,通过Voronoi建模识别点目标间的空间邻近关系,并以Voronoi势力范围来定义相似度准则,最终构建树结构以实现点目标的聚集模式识别。实验将所提算法与K-means、具有噪声的基于密度的聚类(DBSCAN)算法进行比较分析,结果表明算法能够发现密度不均且任意形状分布的点目标集群,同时准确划分"桥"链接的簇,适用于空间点目标异质分布下的聚集模式识别。     

基于层次Voronoi图的点群相似度算法

通过对空间点群的自适应聚类方法构建层次Voronoi图,以此层次Voronoi图为切入点,计算点群的拓扑、密度和范围的相似度,结合有关标准差的数理统计方法,计算角度、距离的相似度。在各维度的相似度基础上,使用其几何平均值作为点群整体相似度的度量标准,优化点群相似度的计算方法,并通过实验证明算法的可行性     

Approximate medial axis as a Voronoi subcomplex

Medial axis as a compact representation of shapes has evolved as an essential geometric structure in a number of applications involving 3D geometric shapes. Since exact computation of the medial axis is difficult in general, efforts continue to approximate them. One line of research considers the point cloud representation of the boundary surface of a solid and then attempts to compute an approximate medial axis from this point sample. It is known that the Voronoi vertices converge to the medial axis for a curve in 2D as the sample density approaches infinity. Unfortunately, the same is not true in 3D. Recently, it is discovered that a subset of Voronoi vertices called poles converge to the medial axis in 3D. However, in practice, a continuous approximation as opposed to a discrete one is sought.Recently few algorithms have been proposed which use the Voronoi diagram and its derivatives to compute this continuous approximation. These algorithms are scale or density dependent. Most of them do not have convergence guarantees, and one of them computes it indirectly from the power diagram of the poles. Recently, we proposed a new algorithm that approximates the medial axis straight from the Voronoi diagram in a scale and density independent manner with convergence guarantees. In this paper, we present several experimental results with this algorithm that support our theoretical claims and also show its effectiveness on practical data sets.     

Approximation of fruit skin patterns using spherical Voronoi diagrams

In nature, there are many tessellation patterns on curved surfaces that look like Voronoi diagrams. Typical examples are the patterns found on fruit skins. Verifying that a given tessellation is a Voronoi diagram will be useful for constructing mathematical models of polygonal patterns. However, the data are usually obtained as a 2D projected image, and hence it is not easy to compare it with a Voronoi diagram on a curved surfaces. We propose a framework for using a photograph of a fruit to measure the difference between the pattern on its skin and a spherical Voronoi diagram. The problem of finding the spherical Voronoi diagram that best fits the fruit skin pattern is reduced to an optimization problem. The validity of this formulation is evaluated using jackfruit and lychee. We also propose generalizations of our problem for further research.     

An algorithm for point cluster generalization based on the Voronoi diagram

This paper presents an algorithm for point cluster generalization. Four types of information, i.e. statistical, thematic, topological, and metric information are considered, and measures are selected to describe corresponding types of information quantitatively in the algorithm, i.e. the number of points for statistical information, the importance value for thematic information, the Voronoi neighbors for topological information, and the distribution range and relative local density for metric information. Based on these measures, an algorithm for point cluster generalization is developed. Firstly, point clusters are triangulated and a border polygon of the point clusters is obtained. By the border polygon, some pseudo points are added to the original point clusters to form a new point set and a range polygon that encloses all original points is constructed. Secondly, the Voronoi polygons of the new point set are computed in order to obtain the so-called relative local density of each point. Further, the selection probability of each point is computed using its relative local density and importance value, and then mark those will-be-deleted points as ‘deleted’ according to their selection probabilities and Voronoi neighboring relations. Thirdly, if the number of retained points does not satisfy that computed by the Radical Law, physically delete the points marked as ‘deleted’ forming a new point set, and the second step is repeated; else physically deleted pseudo points and the points marked as ‘deleted’, and the generalized point clusters are achieved. Owing to the use of the Voronoi diagram the algorithm is parameter free and fully automatic. As our experiments show, it can be used in the generalization of point features arranged in clusters such as thematic dot maps and control points on cartographic maps.     

基于轮廓对红松雌雄花特征的提取

在红松结实量的各种预测方法中,红松雌雄花的形态特征是主要参数之一。依托原野服务器采集的红松图像,对红松雌雄花进行图像分割,提取红松雌雄花的特征值,为红松结实量的预测方法提供精确的数据。改进了宽长比的提取方法,将轮廓图中不连通的区域通过最短距离的计算,使得不连通的区域假定连通,计算得到最小外接矩,在轮廓图中成功地提取出了宽长比,并通过实验验证了该方法。     

Delaunay meshing of isosurfaces

We present an isosurface meshing algorithm, DelIso, based on the Delaunay refinement paradigm. This paradigm has been successfully applied to mesh a variety of domains with guarantees for topology, geometry, mesh gradedness, and triangle shape. A restricted Delaunay triangulation, dual of the intersection between the surface and the three-dimensional Voronoi diagram, is often the main ingredient in Delaunay refinement. Computing and storing three-dimensional Voronoi/Delaunay diagrams become bottlenecks for Delaunay refinement techniques since isosurface computations generally have large input datasets and output meshes. A highlight of our algorithm is that we find a simple way to recover the restricted Delaunay triangulation of the surface without computing the full 3D structure. We employ techniques for efficient ray tracing of isosurfaces to generate surface sample points, and demonstrate the effectiveness of our implementation using a variety of volume datasets.     

Robust and efficient surface reconstruction from contours

We propose a new approach for surface recovery from planar sectional contours. The surface is reconstructed based on the so-called “equal importance criterion,” which suggests that every point in the region contributes equally to the reconstruction process. The problem is then formulated in terms of a partial differential equation, and the solution is efficiently calculated from distance transformation. To make the algorithm valid for different application purposes, both the isosurface and the primitive representations of the object surface are derived. The isosurface is constructed by means of a partial differential equation, which can be solved iteratively. The traditional distance interpolating method, which was used by several researchers for surface reconstruction, is an approximate solution of the equation. The primitive representations are approximated by Voronoi diagram transformation of the surface space. Isosurfaces have the advantage that subsequent geometric analysis of the object can be easily carried out while primitive representation is easy to visualize. The proposed technique allows for surface recovery at any desired resolution, thus avoiding the inherent problems of correspondence, tiling, and branching.     

A Point Symmetry-Based Clustering Technique for Automatic Evolution of Clusters

In this article, a new symmetry based genetic clustering algorithm is proposed which automatically evolves the number of clusters as well as the proper partitioning from a data set. Strings comprise both real numbers and the don't care symbol in order to encode a variable number of clusters. Here, assignment of points to different clusters are done based on a point symmetry based distance rather than the Euclidean distance. A newly proposed point symmetry based cluster validity index, {em Sym}-index, is used as a measure of the validity of the corresponding partitioning. The algorithm is therefore able to detect both convex and non-convex clusters irrespective of their sizes and shapes as long as they possess the point symmetry property. Kd-tree based nearest neighbor search is used to reduce the complexity of computing point symmetry based distance. A proof on the convergence property of variable string length GA with point symmetry based distance clustering (VGAPS-clustering) technique is also provided. The effectiveness of VGAPS-clustering compared to variable string length Genetic K-means algorithm (GCUK-clustering) and one recently developed weighted sum validity function based hybrid niching genetic algorithm (HNGA-clustering) is demonstrated for nine artificial and five real-life data sets.