Assessment of four modifications of a novel indexing technique for case‐based reasoning

In this article, we investigate four variations (D‐HS^M, D‐HS^W, D‐HS^E, and D‐HS^EW) of a novel indexing technique called D‐HS designed for use in case‐based reasoning (CBR) systems. All D‐HS modifications are based on a matrix of cases indexed by their discretized attribute values. The main differences between them are in their attribute discretization stratagem and similarity determination metric. D‐HS^M uses a fixed number of intervals and simple intersection as a similarity metric; D‐HS^W uses the same discretization approach and a weighted intersection; D‐HS^E uses information gain to define the intervals and simple intersection as similarity metric; D‐HS^EW is a combination of D‐HS^E and D‐HS^W. Benefits of using D‐HS include ease of case and similarity knowledge maintenance, simplicity, accuracy, and speed in comparison to conventional approaches widely used in CBR. We present results from the analysis of 20 case bases for classification problems and 15 case bases for regression problems. We demonstrate the improvements in accuracy and/or efficiency of each D‐HS modification in comparison to traditional k‐NN, R‐tree, C4,5, and M5 techniques and show it to be a very attractive approach for indexing case bases. We also illuminate potential areas for further improvement of the D‐HS approach. © 2007 Wiley Periodicals, Inc. Int J Int Syst 22: 353–383, 2007.     

Three-dimensional surface reconstruction of tree canopy from lidar point clouds using a region-based level set method

In this article, a novel method is proposed for three-dimensional (3D) canopy surface reconstruction of trees using a region-based level set method. Both individual tree crowns and clusters of trees are first marked for further exploration. Multiple horizontal slices corresponding to different heights are obtained. The 3D structure of tree canopy is built using raw data from lidar point clouds. Also, new applications are proposed based on the new method for 3D forest reconstruction. The biomass parameters of the forest, including tree intersection area, tree equivalent crown radius, and canopy volume, can be calculated from stacking 2D slices of trees. Tree types are also identified and classified. The results indicate that this approach is effective for 3D surface reconstruction of forests including individual trees and clusters of trees, and that critical forest parameters (such as tree intersection area, tree position, and canopy volume) can be derived for the evaluation and measurement of biophysical parameters of forests.     

Accuracy-Based Sampling and Reconstruction with Adaptive Meshes for Parallel Hierarchical Triangulation

Recent advances in range finding techniques have made the task of acquiring surface data for 3-D objects easier and more accurate. With most advanced techniques, range and color data are acquired simultaneously. Since the number of such acquired data is generally very large, a surface model capable of compressing data while maintaining a specified accuracy is required. The objective of this work is to construct a polyhedral representation of input data for surfaces. This representation adapts to local intrinsic surface properties while preserving their discontinuities. In this paper, we present an accuracy-based adaptive sampling and reconstruction technique for hierarchical triangulation of 3D objects. We have developed a parallel algorithm for adaptive mesh generation that recursively bisects mesh elements by increasing the number of mesh nodes according to local surface properties, such as surface orientation, curvature, and color. The recursive subdivision based on such viewpoint-invariant properties yields a hierarchical surface triangulation that is intrinsic to the surface. This approach also satisfies the absolute accuracy criteria, since nodes are generated as required until the entire surface has been approximated within a specified level of accuracy. We have also developed a parallel algorithm that detects and preserves both depth (C⁰) and orientation (C¹) discontinuities, without the formation of cracks which normally occur during independent subdivision. The algorithm has been successfully applied to adaptive sampling and reconstruction of both range and color images of human faces and Japanese antique dolls with fine grained color-texture.     

Some applications of Loop-subdivision wavelet tight frames to?the?processing of 3D graphics

Multiresolution analysis based on subdivision wavelets is an important method of 3D graphics processing. Many applications of this method have been studied and developed, including denoising, compression, progressive transmission, multiresolution editing and so on. Recently Charina and St?ckler firstly gave the explicit construction of wavelet tight frame transform for subdivision surfaces with irregular vertices, which made its practical applications to 3D graphics became a subject worthy of investigation. Based on the works of Charina and St?ckler, we present in detail the wavelet tight frame decomposition and reconstruction formulas for Loop-subdivision scheme. We further implement the algorithm and apply it to the denoising, compression and progressive transmission of 3D graphics. By comparing it with the biorthogonal Loop-subdivision wavelets of Bertram, the numerical results illustrate the good performance of the algorithm. Since multiresolution analysis based on subdivision wavelets or subdivision wavelet tight frames requires the input mesh to be semi-regular, we also propose a simple remeshing algorithm for constructing meshes which not only have subdivision connectivity but also approximate the input mesh.     

A New Class of Guided C2 Subdivision Surfaces Combining Good Shape with Nested Refinement

Converting quadrilateral meshes to smooth manifolds, guided subdivision offers a way to combine the good highlight line distribution of recent G‐spline constructions with the refinability of subdivision surfaces. This avoids the complex refinement of G‐spline constructions and the poor shape of standard subdivision. Guided subdivision can then be used both to generate the surface and hierarchically compute functions on the surface. Specifically, we present a C² subdivision algorithm of polynomial degree bi‐6 and a curvature bounded algorithm of degree bi‐5. We prove that the common eigenstructure of this class of subdivision algorithms is determined by their guide and demonstrate that their eigenspectrum (speed of contraction) can be adjusted without harming the shape. For practical implementation, a finite number of subdivision steps can be completed by a high‐quality cap. Near irregular points this allows leveraging standard polynomial tools both for rendering of the surface and for approximately integrating functions on the surface.     

结合插值细分和径向基函数的3维扫描数据孔洞修补

目的 逆向工程中3维扫描数据通常产生孔洞影响逆向造型精度.针对已有算法补洞会导致的边界突变问题,提出基于插值细分和基于径向基函数的孔洞修复算法。方法 首先,对有噪声孔洞边界进行拉普拉斯平滑预处理;其次,通过快速重心插值细分孔洞;然后,结合孔洞周围曲率信息,利用边界和法线约束点进行隐式曲面求解;最后,利用求得的隐式曲面方程,利用梯度下降法调整孔洞插值点,获得平滑修补孔洞结果。结果 对3维经典造型以及实际机械工件等两类不同的数据进行扫描并进行孔洞修补实验。由于算法针对有噪声孔洞结合了孔洞周围曲率信息并通过插值细分进行约束求解,保证了补洞效果的平滑性。实验结果表明,本文算法使得基于径向基函数隐式曲面对有噪声孔洞的适应性更强,其修补结果更加平滑,符合周围曲率变化,改进了已有孔洞修补的边缘突变和修补痕迹明显问题。结论 本文算法针对基于径向基函数的隐式曲面求解对噪声敏感的局限性,进行平滑预处理,结合孔洞周围曲率,提高了孔洞修补效果。由于基于径向基函数的隐式曲面对光顺的流形曲面模拟较好,所以算法对特征孔洞的修补存在一定的不足,快速重心插值法针对不规则孔洞也有一定的局限性。     

A comparison of three shadow volume algorithms

This paper describes and compares three different approaches to computing shadows. Each is based on the idea of shadow volumes: basic algorithm, Shadow Volume BSP Tree algorithm, and Shadow Tiling, based on 2D space subdivision. Binary Space Partition trees are used to organise the polygons in the scene in a front-toback order from the point of view of the light source, and then shadows on a polygon are computed by clipping the polygon to the shadow volumes of polygons closer to the light source. The three algorithms differ in their approach to minimising the number of comparisons of a polygon with the shadow volumes of its predecessors, and one of the algorithms represents the total shadow volume itelf by a BSP tree. The algorithms are compared analytically and statistically.     

A hierarchical stochastic modelling approach for reconstructing lung tumour geometry from 2D CT images

ABSTRACT

Lung cancer is one of the deadliest cancers in both men and women. Nowadays, several methods are used to cure this cancer including surgery and radiotherapy. These methods require prior knowledge about the shape of tumours. This type of knowledge may also help physicians to determine the cancer type. In this paper we propose a novel approach for 3D reconstruction of tumour geometry from a sequence of 2D images. The proposed approach consists of two phases: tumour segmentation from computed tomography (CT) images and 3D shape reconstruction. Segmentation is conducted using snake optimisation and Gustafson–Kessel clustering. For 3D reconstruction, first, we propose a new approach to interpolate some intermediate slices between original slices. Then, the well-known marching cubes algorithm is used for surface reconstruction. Eventually, we smoothen the surface using an explicit fairing algorithm. Experiments show that our new approach can highly improve the quality and the accuracy of the reconstructed tumour shape.     

Reconstructing Animated Meshes from Time‐Varying Point Clouds

In this paper, we describe a novel approach for the reconstruction of animated meshes from a series of time‐deforming point clouds. Given a set of unordered point clouds that have been captured by a fast 3‐D scanner, our algorithm is able to compute coherent meshes which approximate the input data at arbitrary time instances. Our method is based on the computation of an implicit function in ?⁴ that approximates the time‐space surface of the time‐varying point cloud. We then use the four‐dimensional implicit function to reconstruct a polygonal model for the first time‐step. By sliding this template mesh along the time‐space surface in an as‐rigid‐as‐possible manner, we obtain reconstructions for further time‐steps which have the same connectivity as the previously extracted mesh while recovering rigid motion exactly. The resulting animated meshes allow accurate motion tracking of arbitrary points and are well suited for animation compression. We demonstrate the qualities of the proposed method by applying it to several data sets acquired by real‐time 3‐D scanners.     

自适应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,均小于栅格法和曲率法。结论 本文提出的散乱点云精简算法可应用于封闭及片状点云,精简后的数据点分布均匀无空洞,对片状点云进行精简时能够保护模型的边界数据点。     

A framework for quad/triangle subdivision surface fitting: Application to mechanical objects

In this paper we present a new framework for subdivision surface approximation of three‐dimensional models represented by polygonal meshes. Our approach, particularly suited for mechanical or Computer Aided Design (CAD) parts, produces a mixed quadrangle‐triangle control mesh, optimized in terms of face and vertex numbers while remaining independent of the connectivity of the input mesh. Our algorithm begins with a decomposition of the object into surface patches. The main idea is to approximate the region boundaries first and then the interior data. Thus, for each patch, a first step approximates the boundaries with subdivision curves (associated with control polygons) and creates an initial subdivision surface by linking the boundary control points with respect to the lines of curvature of the target surface. Then, a second step optimizes the initial subdivision surface by iteratively moving control points and enriching regions according to the error distribution. The final control mesh defining the whole model is then created assembling every local subdivision control meshes. This control polyhedron is much more compact than the original mesh and visually represents the same shape after several subdivision steps, hence it is particularly suitable for compression and visualization tasks. Experiments conducted on several mechanical models have proven the coherency and the efficiency of our algorithm, compared with existing methods.     

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.     

Continuous Global Optimization in Multiview 3D Reconstruction

In this article, we introduce a new global optimization method to the field of multiview 3D reconstruction. While global minimization has been proposed in a discrete formulation in form of the maxflow-mincut framework, we suggest the use of a continuous convex relaxation scheme. Specifically, we propose to cast the problem of 3D shape reconstruction as one of minimizing a spatially continuous convex functional. In qualitative and quantitative evaluation we demonstrate several advantages of the proposed continuous formulation over the discrete graph cut solution. Firstly, geometric properties such as weighted boundary length and surface area are represented in a numerically consistent manner: The continuous convex relaxation assures that the algorithm does not suffer from metrication errors in the sense that the reconstruction converges to the continuous solution as the spatial resolution is increased. Moreover, memory requirements are reduced, allowing for globally optimal reconstructions at higher resolutions. We study three different energy models for multiview reconstruction, which are based on a common variational template unifying regional volumetric terms and on-surface photoconsistency. The three models use data measurements at increasing levels of sophistication. While the first two approaches are based on a classical silhouette-based volume subdivision, the third one relies on stereo information to define regional costs. Furthermore, this scheme is exploited to compute a precise photoconsistency measure as opposed to the classical estimation. All three models are compared on standard data sets demonstrating their advantages and shortcomings. For the third one, which gives the most accurate results, a more exhaustive qualitative and quantitative evaluation is presented.     

Silhouette‐Aware Warping for Image‐Based Rendering

Image‐based rendering (IBR) techniques allow capture and display of 3D environments using photographs. Modern IBR pipelines reconstruct proxy geometry using multi‐view stereo, reproject the photographs onto the proxy and blend them to create novel views. The success of these methods depends on accurate 3D proxies, which are difficult to obtain for complex objects such as trees and cars. Large number of input images do not improve reconstruction proportionally; surface extraction is challenging even from dense range scans for scenes containing such objects. Our approach does not depend on dense accurate geometric reconstruction; instead we compensate for sparse 3D information by variational image warping. In particular, we formulate silhouette‐aware warps that preserve salient depth discontinuities. This improves the rendering of difficult foreground objects, even when deviating from view interpolation. We use a semi‐automatic step to identify depth discontinuities and extract a sparse set of depth constraints used to guide the warp. Our framework is lightweight and results in good quality IBR for previously challenging environments.     

Multiresolution analysis on irregular surface meshes

Wavelet-based methods have proven their efficiency for visualization at different levels of detail, progressive transmission, and compression of large data sets. The required core of all wavelet-based methods is a hierarchy of meshes that satisfies subdivision-connectivity. This hierarchy has to be the result of a subdivision process starting from a base mesh. Examples include quadtree uniform 2D meshes, octree uniform 3D meshes, or 4-to-1 split triangular meshes. In particular, the necessity of subdivision-connectivity prevents the application of wavelet-based methods on irregular triangular meshes. In this paper, a “wavelet-like” decomposition is introduced that works on piecewise constant data sets over irregular triangular surface meshes. The decomposition/reconstruction algorithms are based on an extension of wavelet-theory allowing hierarchical meshes without property. Among others, this approach has the following features: it allows exact reconstruction of the data set, even for nonregular triangulations, and it extends previous results on Haar-wavelets over 4-to-1 split triangulations     

Hierarchical Convex Approximation of 3D Shapes for Fast Region Selection

Given a 3D solid model S represented by a tetrahedral mesh, we describe a novel algorithm to compute a hierarchy of convex polyhedra that tightly enclose S. The hierarchy can be browsed at interactive speed on a modern PC and it is useful for implementing an intuitive feature selection paradigm for 3D editing environments. Convex parts often coincide with perceptually relevant shape components and, for their identification, existing methods rely on the boundary surface only. In contrast, we show that the notion of part concavity can be expressed and implemented more intuitively and efficiently by exploiting a tetrahedrization of the shape volume. The method proposed is completely automatic, and generates a tree of convex polyhedra in which the root is the convex hull of the whole shape, and the leaves are the tetrahedra of the input mesh. The algorithm proceeds bottom‐up by hierarchically clustering tetrahedra into nearly convex aggregations, and the whole process is significantly fast. We prove that, in the average case, for a mesh of n tetrahedra O(n log² n) operations are sufficient to compute the whole tree.     

A new unsupervised cube-based algorithm for iso-surface generation

This paper introduces a new algorithm which automatically produces polygonal representations of 3D structures within a volume data set built from a stack of parallel cross-sections. Several methods of 3D surface reconstruction have already been proposed ranging from heuristic approaches for constructing 3D surfaces from 2D contours to the Marching Cubes (MC) approach where the different configurations are checked systematically. Instead, we define a cube-to-cube connection based upon geometrical closeness provided by convex hulls computation. We further evaluate the precision of 3D models reconstructed from synthetic and real data obtained in confocal microscopy and compare it with the conventional MC algorithm. We also discuss improvements that allow to reduce the number of generated surface patches and the ability to be used in 3D quantitative tasks.     

Curve skeleton extraction by coupled graph contraction and surface clustering

In this paper, we present a practical algorithm to extract a curve skeleton of a 3D shape. The core of our algorithm comprises coupled processes of graph contraction and surface clustering. Given a 3D shape represented by a triangular mesh, we first construct an initial skeleton graph by directly copying the connectivity and geometry information from the input mesh. Graph contraction and surface clustering are then performed iteratively. The former merges certain graph nodes based on computation of an approximate centroidal Voronoi diagram, seeded by subsampling the graph nodes from the previous iteration. Meanwhile, a coupled surface clustering process serves to regularize the graph contraction. Constraints are used to ensure that extremities of the graph are not shortened undesirably, to ensure that skeleton has the correct topological structure, and that surface clustering leads to an approximately-centered skeleton of the input shape. These properties lead to a stable and reliable skeleton graph construction algorithm.Experiments demonstrate that our skeleton extraction algorithm satisfies various desirable criteria. Firstly, it produces a skeleton homotopic with the input (the genus of both shapes agree) which is both robust (results are stable with respect to noise and remeshing of the input shape) and reliable (every boundary point is visible from at least one curve-skeleton location). It can also handle point cloud data if we first build an initial skeleton graph based on k-nearest neighbors. In addition, a secondary output of our algorithm is a skeleton-to-surface mapping, which can e.g. be used directly for skinning animation.Highlights(1) An algorithm for curve skeleton extraction from 3D shapes based on coupled graph contraction and surface clustering. (2) The algorithm meets various desirable criteria and can be extended to work for incomplete point clouds.     

Surface Reconstruction from Unstructured 3D Data

Building 3 0 models from unstructured data is a problem that arises increasingly as new 30 scanning technology is able to produce large and complex databases of full 3 0 information. Huge efforts put into segmenting entire sets of 20 images demand robust tools that are then able to reconstruct any arbitrary 30 surface segmented from the images. In this paper we propose an algorithmic methodology that automatically produces a surface from a set of points in ?³ about which we have no topological knowledge. Our method uses a spatial decomposition and a surface tracking algorithm to produce a rough approximation S' of the unknown manifold S. The produced surface S' serves as a robust initialisation for a physically based modeling technique that yields the fine details of S and so improves the quality of the reconstruction.