Hierarchical part-type segmentation using voxel-based curve skeletons

We present an effective framework for segmenting 3D shapes into meaningful components using the curve skeleton. Our algorithm identifies a number of critical points on the efficiently computed curve skeleton, either fully automatically as the junctions of the curve skeleton, or based on user input. We use these points to construct a partitioning of the object surface using geodesics. Because the segmentation is based on the curve skeleton, it intrinsically reflects the shape symmetry and articulation, and can handle shapes with tunnels. We describe a voxel-based implementation of our method which is robust and noise resistant, able to handle shapes of complex articulation and topology, produces smooth segment borders, and delivers hierarchical level-of-detail segmentations. We demonstrate the framework on various real-world 3D shapes. Additionally, we discuss the use of both curve and surface skeletons to produce part-type and patch-type, respectively, segmentations of 3D shapes.     

Domain connected graph: the skeleton of a closed 3D shape for animation

In previous research, three main approaches have been employed to solve the skeleton extraction problem: medial axis transform (MAT), generalized potential field and decomposition-based methods. These three approaches have been formulated using three different concepts, namely surface variation, inside energy distribution, and the connectivity of parts. By combining the above mentioned concepts, this paper creates a concise structure to represent the control skeleton of an arbitrary object. First, an algorithm is proposed to detect the end, connection and joint points of an arbitrary 3D object. These three points comprise the skeleton, and are the most important to consider when describing it. In order to maintain the stability of the point extraction algorithm, a prong-feature detection technique and a level iso-surfaces function-based on the repulsive force field was employed. A neighborhood relationship inherited from the surface able to describe the connection relationship of these positions was then defined. Based on this relationship, the skeleton was finally constructed and named domain connected graph (DCG). The DCG not only preserves the topology information of a 3D object, but is also less sensitive than MAT to the perturbation of shapes. Moreover, from the results of complicated 3D models, consisting of thousands of polygons, it is evident that the DCG conforms to human perception.     

Shape recovery from turntable sequence using rim reconstruction

This paper makes use of both feature points and silhouettes to deliver fast 3D shape recovery. The algorithm exploits object silhouettes in two views to establish a 3D rim curve, which is defined with respect to the two frontier points arising from two views. The images of this 3D rim curve in the two views are matched using cross-correlation technique. A 3D planar rim curve is then reconstructed using point-based reconstruction method. A set of 3D rim curves enclosing the object can be obtained from an image sequence captured under circular motion. Silhouettes are further utilized to check for mismatched rim points. The proposed method solves the problem of reconstruction of concave object surface, which is usually left unresolved in general silhouette-based reconstruction methods. In addition, the property of the reconstructed 3D rim curves allows fast surface extraction. Experimental results with real data are presented.     

基于局部指纹曲面片的点云三维物体识别

提出一种新的基于局部描述符的点云物体识别算法。算法根据点云的位置信息提取出邻域以及曲率信息,进而得到形状索引信息。根据形状索引提取到特征点,在每个特征点根据样条拟合原理得到测地距离和矢量夹角分割曲面得到曲面片集。每个曲面片的等距测地线构成了曲面片指纹,通过矢量和半径的变化描述,可以把每个模型物体得到的曲面片集描述存入数据库。对于给定的一个物体,根据上面步骤同样得到其曲面片集描述,通过和数据库中模型物体曲面片集的比对,得到初始识别结果。对每对初始识别结果进行对应滤波后,通过最近点迭代方法得到最终的识别结果。最后通过具体的实验说明了算法的有效性和高效性。     

Computing hierarchical curve-skeletons of 3D objects

A curve-skeleton of a 3D object is a stick-like figure or centerline representation of that object. It is used for diverse applications, including virtual colonoscopy and animation. In this paper, we introduce the concept of hierarchical curve-skeletons and describe a general and robust methodology that computes a family of increasingly detailed curve-skeletons. The algorithm is based upon computing a repulsive force field over a discretization of the 3D object and using topological characteristics of the resulting vector field, such as critical points and critical curves, to extract the curve-skeleton. We demonstrate this method on many different types of 3D objects (volumetric, polygonal and scattered point sets) and discuss various extensions of this approach.     

一种计算空间封闭曲面正侧法向量的方法

在三维物体表面光照处理,三维曲面上曲线所围区域的计算以及三维物体体积计算等应用中,需要计算曲面正侧法向量,针对三角形网格表示的空间封闭曲面,本文设计了一种计算曲面正侧法的向量的简明算法。     

On the computation of the 〈3, 4, 5〉 curve skeleton of 3D objects

An algorithm to compute the curve skeleton of 3D objects in voxel images is presented. The skeleton is stable under isometric transformations of the object, since the algorithm is based on the use of the 〈3, 4, 5〉 weighted distance transform, which is a good approximation of the Euclidean distance transform. The 〈3, 4, 5〉 weighted distance transform is used both to identify suitable anchor points, and to efficiently check object voxels according to their distance to the background. The curve skeleton is symmetrically placed within the object, is topologically equivalent to the object, is unit-wide and provides a satisfactory representation of the object. Though the size of the object reconstructed from the curve skeleton via the reverse distance transformation is not as thick as that of the input, shape information is mostly retained by the skeleton, since all regions perceived as significant in the input can still be found in the reconstructed object.     

A topology-preserving parallel 3D thinning algorithm for extracting the curve skeleton

We introduce a new topology-preserving 3D thinning procedure for deriving the curve voxel skeleton from 3D binary digital images. Based on a rigorously defined classification procedure, the algorithm consists of sequential thinning iterations each characterized by six parallel directional sub-iterations followed by a set of sequential sub-iterations. The algorithm is shown to produce concise and geometrically accurate 3D curve skeletons. The thinning algorithm is also insensitive to object rotation and only moderately sensitive to noise. Although this thinning procedure is valid for curve skeleton extraction of general elongated objects, in this paper, we specifically discuss its application to the orientation modeling of trabecular biological tissues.     

一种基于矢量场结构的等值面构造方法

为得到非结构矢量场中的等值面图像,给出了一种基于矢量场曲线结构的等值面构造新方法.算法利用矢量可视化映射过程中获得的曲线结构来组织数据并计算等值点,采取自适应聚类划分方法获得各个等值面包含的数据点集合后利用曲面重建算法来构造等值面.在计算等值点时,不但利用了数据场中各个数据点处的空间位置与场值大小,而且充分考虑了数据点处的矢量方向信息.实验表明,该方法能够稳定、有效地构造出非结构矢量数据场中的等值面.与基于体元的传统等值面构造方法相比,可以有效加快计算进程,得到更为准确的计算结果.     

基于一维标定物的多摄像机标定

一维标定物是由三个或三个以上彼此距离已知的共线点构成的. 现有文献指出只有当一维标定物做平面运动或者绕固定点转动时，才能实现摄像机的标定. 本文的研究结果表明，当多个摄像机同时观察作任意刚体运动的一维标定物时，则该摄像机组能被线性地标定. 本文给出一种线性标定算法，并使用最大似然准则对线性算法结果进行精化. 模拟实验和真实图像实验都表明本文的算法是有效可行的.     

一种提取物体线形骨架的新方法

提出了一种提取物体线形骨架的新方法. 该方法首先计算物体距离变换的梯度, 从而得到一个矢量场. 距离变换的梯度对提取物体线形骨架具有重要意义, 可据此获得物体内部的关键点, 其中每一个关键点代表了物体的一个凸部分. 之后, 用搜索梯度最短路径的方法连接关键点, 得到物体的线形骨架. 本文方法得到的线形骨架能很好地反映物体拓扑和形状特征, 并不易受边界噪声干扰. 此外, 本文方法克服了基于距离变换的骨架提取算法的固有缺点, 获得了具有良好连通性的骨架. 因此, 基于本文方法得到的骨架能用于物体识别和匹配等领域. 对大量二维、三维物体的实验取得了令人满意的效果.     

Finding and classifying critical points of 2D vector fields: a cell-oriented approach using group theory

We present a novel approach to finding critical points in cell-wise barycentrically or bilinearly interpolated vector fields on surfaces. The Poincaré index of the critical points is determined by investigating the qualitative behavior of 0-level sets of the interpolants of the vector field components in parameter space using precomputed combinatorial results, thus avoiding the computation of the Jacobian of the vector field at the critical points in order to determine its index. The locations of the critical points within a cell are determined analytically to achieve accurate results. This approach leads to a correct treatment of cases with two first-order critical points or one second-order critical point of bilinearly interpolated vector fields within one cell, which would be missed by examining the linearized field only. We show that for the considered interpolation schemes determining the index of a critical point can be seen as a coloring problem of cell edges. A complete classification of all possible colorings in terms of the types and number of critical points yielded by each coloring is given using computational group theory. We present an efficient algorithm that makes use of these precomputed classifications in order to find and classify critical points in a cell-by-cell fashion. Issues of numerical stability, construction of the topological skeleton, topological simplification, and the statistics of the different types of critical points are also discussed.     

基于特征点和最小面积的曲线描述和匹配

为了对关键特征点相同而子曲线曲率不同的曲线进行识别,提出一种新的平面曲线的描述和匹配方法。基于关键特征点进行粗匹配,根据精度要求设定最小面积阈值在子曲线上重新采样点,定义了一种新的采样点的识别向量,并根据子曲线上采样点的识别向量构造了新的识别向量矩阵,最后根据识别向量矩阵的差异度度量子曲线的相似性。通过对所有子曲线的识别实现对整条曲线的识别。该识别方法逐层筛选、由粗到精,避免了冗余操作。实验表明该方法高效、可行。     

Constructing a 3D trunk model from two images

Trees stand for a key component in the natural environment, thus modeling realistic trees has received much attentions of researchers in computer graphics. However, most trees in computer graphics are generated according to some procedural rules in conjunction with some random perturbations, thus they are generally different from the real trees in the natural environment. In this paper, we propose a systematic approach to create a 3D trunk graphical model from two images so that the created trunk has a similar 3D trunk structure to the real one. In the proposed system, the trunk is first segmented from the image via an interactive segmentation tool and its skeleton is then extracted. Some points on the skeleton are selected and their context relations are established for representing the 2D trunk structure. A camera self-calibration algorithm appropriate for the two-view case is developed, and a minimum curvature constraint is employed to recover the 3D trunk skeleton from the established 2D trunk structure and the calibrated camera. The trunk is then modeled by a set of generalized cylinders around the recovered 3D trunk skeleton. A polygonal mesh representing the trunk is finally generated and a textured 3D trunk model is also produced by mapping the image onto the surface of the 3D trunk model. We have conducted some experiments and the results demonstrated that the proposed system can actually yield a visually plausible 3D trunk model which is similar to the real one in the image.     

Context preserving maps of tubular structures

When visualizing tubular 3D structures, external representations are often used for guidance and display, and such views in 2D can often contain occlusions. Virtual dissection methods have been proposed where the entire 3D structure can be mapped to the 2D plane, though these will lose context by straightening curved sections. We present a new method of creating maps of 3D tubular structures that yield a succinct view while preserving the overall geometric structure. Given a dominant view plane for the structure, its curve skeleton is first projected to a 2D skeleton. This 2D skeleton is adjusted to account for distortions in length, modified to remove intersections, and optimized to preserve the shape of the original 3D skeleton. Based on this shaped 2D skeleton, a boundary for the map of the object is obtained based on a slicing path through the structure and the radius around the skeleton. The sliced structure is conformally mapped to a rectangle and then deformed via harmonic mapping to match the boundary placement. This flattened map preserves the general geometric context of a 3D object in a 2D display, and rendering of this flattened map can be accomplished using volumetric ray casting. We have evaluated our method on real datasets of human colon models.     

骨架驱动的三维模型变形方法

为发展三维网格模型的变形技术,研究了多种三维模型变形算法,通过对骨架驱动变形算法的深入研究,针对现行算法多是以单一骨架驱动变形的不足,提出了一种新的基于多骨架点驱动的交互式局部变形方法.有效结合模型的骨架图结构,确定各骨架点对应的局部区域.并将骨架点拟合为二次Bézier曲线,通过交互式拖动任意骨架点计算与之相连的多骨架点的动态变化,实现模型局部区域的自然形变.实验结果表明了该算法的有效性和直观性.     

Extraction of the Euclidean skeleton based on a connectivity criterion

The skeleton is essential for general shape representation. The commonly required properties of a skeletonization algorithm are that the extracted skeleton should be accurate; robust to noise, position and rotation; able to reconstruct the original object; and able to produce a connected skeleton in order to preserve its topological and hierarchical properties. However, the use of a discrete image presents a lot of problems that may influence the extraction of the skeleton. Moreover, most of the methods are memory-intensive and computationally intensive, and require a complex data structure.In this paper, we propose a fast, efficient and accurate skeletonization method for the extraction of a well-connected Euclidean skeleton based on a signed sequential Euclidean distance map. A connectivity criterion is proposed, which can be used to determine whether a given pixel is a skeleton point independently. The criterion is based on a set of point pairs along the object boundary, which are the nearest contour points to the pixel under consideration and its 8 neighbors. Our proposed method generates a connected Euclidean skeleton with a single pixel width without requiring a linking algorithm or iteration process. Experiments show that the runtime of our algorithm is faster than the distance transformation and is linearly proportional to the number of pixels of an image.     

利用角度签名进行3维表面配准

3维表面的配准在3维物体重建、场景检测和物体识别过程中起着重要的作用。为此提出了一种新的3维表面表示方法——角度签名(angle signature),并将其用于3维表面配准。该表示方法将表面的局部几何信息表示成为1维的向量,具有对刚体变换的不变性。由于其简洁的表示方式,可以实现表面的快速配准。此外,该方法较其他3维表面的表示方法具有更强的鲁棒性。在实际应用中,为了提高表面配准的速度,首先筛选出特征点,然后利用特征点寻找表面之间的对应关系,从而将刚体变换的参数求出,实现表面的配准。实验结果表明,采用角度签名实现物体表面配准具有较快的速度和较高的精度。