Three-dimensional topology preserving reduction on the 4-subfields

This paper discusses thinning on 3D binary images with the 4-subfield approach. Although a thinning algorithm concerns binary images, the algorithm itself can be represented as a set of three-color reduction templates. A thinning algorithm is topology preserving if the set of all three-color templates is topology preserving. Sufficient and necessary conditions of time complexity O(n) were proposed for verifying the topological soundness of a 3D 4-subfield thinning algorithm of n three-color templates. Theories and techniques for computerizing such conditions were discussed. Two 4-subfield thinning algorithms on 3D images, one for generating medial curves, and the other one for generating medial surfaces, are proposed and proved to preserve topology by our sufficient and necessary conditions.     

A General Multi-step Algorithm for Voxel Traversing Along a Line

Traversing voxels along a three dimensional (3D) line is one of the most fundamental algorithms for voxel‐based applications. This paper presents a new 6‐connectivity integer algorithm for this task. The proposed algorithm accepts voxels having different sizes in x, y and z directions. To explain the idea of the proposed approach, a 2D algorithm is firstly considered and then extended in 3D. This algorithm is a multi‐step as up to three voxels may be added in one iteration. It accepts both integer and floating‐point input. The new algorithm was compared to other popular voxel traversing algorithms. Counting the number of arithmetic operations showed that the proposed algorithm requires the least amount of operations per traversed voxel. A comparison of spent CPU time using either integer or floating‐point arithmetic confirms that the proposed algorithm is the most efficient. This algorithm is simple, and in compact form which also makes it attractive for hardware implementation.     

结合体元数据结构的机载LIDAR建筑物检测

目的 目前,点云、栅格格网及不规则三角网等建筑物检测中常用的离散机载激光雷达（LIDAR）点云数据表达方式存在模型表达复杂、算法开发困难、结果表达不准确及难以表达多返回数据等缺点。为此,针对LIDAR点云体元结构模型构建及在此基础上的建筑物检测展开研究,提出一种基于体元的建筑物检测算法。方法 首先将点云数据规则化为二值（即1、0值,分别表示体元中是否包含有激光点）3D体元结构。然后利用3D滤波算法将上述体元结构中表征数据点的体元分类为地面和非地面体元。最后,依据建筑物边缘的接近直线、跳变特性从非地面体元中搜寻建筑物边缘作为种子体元进而标记与其3D连通的非地面体元集合为建筑物体元。结果 实验基于ISPRS（international society for photogrammetry and remote sensing）提供的包含了不同的建筑物类型的城区LIDAR点云数据测试了"邻域尺度"参数的敏感性及提出算法的精度。定量评价的结果表明：56邻域为最佳邻域尺度;建筑物的检测质量可达到95%以上——平均完整度可达到95.61%、平均正确率可达95.97%。定性评价的结果表明：对大型、密集、不规则形状、高低混合及其他屋顶类型比较特殊的复杂建筑物均可成功检测。结论 本文提出的建筑物检测算法采用基于体元空间邻域关系的搜索标记方式,可有效实现对各类建筑目标特别是城市建筑目标的检测,检测结果易于建模3D建筑物模型。     

Shape from incomplete silhouettes based on the reprojection error

Traditional shape from silhouette methods compute the 3D shape as the intersection of the back-projected silhouettes in the 3D space, the so called visual hull. However, silhouettes that have been obtained with background subtraction techniques often present miss-detection errors (produced by false negatives or occlusions) which produce incomplete 3D shapes. Our approach deals with miss-detections, false alarms, and noise in the silhouettes. We recover the voxel occupancy which describes the 3D shape by minimizing an energy based on an approximation of the error between the shape 2D projections and the silhouettes. Two variants of the projection – and as a result the energy – as a function of the voxel occupancy are proposed. One of these variants outperforms the other. The energy also includes a sparsity measure, a regularization term, and takes into account the visibility of the voxels in each view in order to handle self-occlusions.     

Determination of the 3D border by repeated elimination of internal surfaces

A novel approach to the 3D border determination is presented: it starts by representing the 3D object in linear octtree form, proceeds by eliminating internal boundaries between nodes of the same size while deleting internal nodes and terminates when only border voxels remain. The algorithm basically performs a mapping of the 3D object into its own border, with both input and output being represented as linear octtrees. The algorithm is shown to be executable inO(kn(N+M)) time, wherek andN are the maximum node grouping and number of nodes (respectively) of the initial linear octtree,n is the resolution of the bilevel image andM is the number of border voxels. The range of applicability of the proposed algorithm is quite wide: it can determine the external border of a simply connected region as well as the external and internal borders of a set of multiply connected objects, all at the same time.     

利用立体图对的三维人脸模型重建算法

利用人脸正面立体图对重建三维人脸模型。无需三维激光扫描仪和通用人脸模型．获取立体图对并校正后，利用种子像素扩张算法实现图像匹配．种子像素选取算法能使足够数量的种子像素具有可靠视差；还提出了基于视差置信度的扩张算法，降低了视差图中大面积误匹配区域出现的可能性；最后，利用碟状粒子描述和Delaunay三角剖分重建三维人脸模型．实验结果表明，文中算法能够产生光滑逼真的三维人脸模型．     

A Fully Parallel 3D Thinning Algorithm and Its Applications

A thinning algorithm is a connectivity preserving process which is applied to erode an object layer by layer until only a “skeleton” is left. Generally, it is difficult to prove that a 3D parallel thinning algorithm preserves connectivity. Sufficient conditions which can simplify such proofs were proposed recently inCVGIP: Image Understanding(59, No. 3 (1994), 328–339). One of the purposes of this paper is to propose a connectivity preserving fully parallel 3D thinning algorithm. The other purpose is to show how to use the sufficient conditions to prove a 3D parallel thinning algorithm to be connectivity preserving. By this demonstration, a new generation of 3D parallel thinning algorithms can be designed and proved to preserve connectivity relatively easily.     

基于体素构造和遗传算法的三维模型检索

以体素构造三维模型原理为基础,阐述了体素的几何信息和体素间的拓扑关系及基 准问题,建立了三维模型特征提取函数,并对其旋转、平移和尺寸变化进行了经典不变矩处理, 提出了一种基于体素构造和遗传算法的三维模型检索方法。该方法通过对遗传信息编码,以及迭 代中的遗传信息交叉与变异,减小了检索区域的收敛速度,提高了检索准确率和检索速度。     

Shape from silhouette using Dempster-Shafer theory

This work proposes a novel shape from silhouette (SfS) algorithm using the Dempster-Shafer (DS) theory for dealing with inconsistent silhouettes. Standard SfS methods makes assumptions about consistency in the silhouettes employed. However, total consistency hardly ever happens in realistic scenarios because of inaccuracies in the background subtraction or occlusions, thus leading to poor reconstruction outside of controlled environments.Our method classify voxels using the DS theory instead of the traditional intersection of all visual cones. Sensors reliability is modelled taking into account the positional relationships between camera pairs and voxels. This information is employed to determine the degree in which a voxel belongs to a foreground object. Finally, evidences collected from all sensors are fused to choose the best hypothesis that determines the voxel state.Experiments performed with synthetic and real data show that our proposal outperforms the traditional SfS method and other techniques specifically designed to deal with inconsistencies. In addition, our method includes a parameter for adjusting the precision of the reconstructions so that it could be adapted to the application requirements.     

The Digital Topology of Sets of Convex Voxels

Classical digital geometry deals with sets of cubical voxels (or square pixels) that can share faces, edges, or vertices, but basic parts of digital geometry can be generalized to sets S of convex voxels (or pixels) that can have arbitrary intersections. In particular, it can be shown that if each voxel P of S has only finitely many neighbors (voxels of S that intersect P), and if any nonempty intersection of neighbors of P intersects P, then the neighborhood N(P) of every voxel P is simply connected and without cavities, and if the topology of N(P) does not change when P is deleted (i.e., P is a “simple” voxel), then deletion of P does not change the topology of S.     

Topological equivalence between a 3D object and the reconstruction of its digital image

Digitization is not as easy as it looks. If one digitizes a 3D object even with a dense sampling grid, the reconstructed digital object may have topological distortions and, in general, there exists no upper bound for the Hausdorff distance. This explains why so far no algorithm has been known which guarantees topology preservation. However, as we will show, it is possible to repair the obtained digital image in a locally bounded way so that it is homeomorphic and close to the 3D object. The resulting digital object is always well-composed, which has nice implications for a lot of image analysis problems. Moreover, we will show that the surface of the original object is homeomorphic to the result of the marching cubes algorithm. This is really surprising since it means that the well-known topological problems of the marching cubes reconstruction simply do not occur for digital images of r-regular objects. Based on the trilinear interpolation, we also construct a smooth isosurface from the digital image that has the same topology as the original surface. Finally, we give a surprisingly simple topology preserving reconstruction method by using overlapping balls instead of cubical voxels. This is the first approach of digitizing 3D objects which guarantees topology preservation and gives an upper bound for the geometric distortion. Since the output can be chosen as a pure voxel presentation, a union of balls, a reconstruction by trilinear interpolation, a smooth isosurface, or the piecewise linear marching cubes surface, the results are directly applicable to a huge class of image analysis algorithms. Moreover, we show how one can efficiently estimate the volume and the surface area of 3D objects by looking at their digitizations. Measuring volume and surface area of digital objects are important problems in 3D image analysis. Good estimators should be multigrid convergent, i.e., the error goes to zero with increasing sampling density. We will show that every presented reconstruction method can be used for volume estimation and we will give a solution for the much more difficult problem of multigrid-convergent surface area estimation. Our solution is based on simple counting of voxels and we are the first to be able to give absolute bounds for the surface area.     

3D object recognition method with multiple feature extraction from LiDAR point clouds

During autonomous driving, fast and accurate object recognition supports environment perception for local path planning of unmanned ground vehicles. Feature extraction and object recognition from large-scale 3D point clouds incur massive computational and time costs. To implement fast environment perception, this paper proposes a 3D recognition system with multiple feature extraction from light detection and ranging point clouds modified by parallel computing. Effective object feature extraction is a necessary step prior to executing an object recognition procedure. In the proposed system, multiple geometry features of a point cloud that resides in corresponding voxels are computed concurrently. In addition, a scale filter is employed to convert feature vectors from uncertain count voxels to a normalized object feature matrix, which is convenient for object-recognizing classifiers. After generating the object feature matrices of all voxels, an initialized multilayer neural network (NN) model is trained offline through a large number of iterations. Using the trained NN model, real-time object recognition is realized using parallel computing technology to accelerate computation.

     

Voxel-based surface area estimation: from theory to practice

Consider a complex, highly convoluted three-dimensional object that has been digitized and is available as a set of voxels. How can one estimate the (original, continuous) area of a region of interest on the surface of the object? The problem appears in the analysis of segmented MRI brain data and in other three-dimensional imaging applications. Several difficulties arise. First, due to the complexity of the surface and its foldings, the region of interest and its intended boundary can be concealed and are therefore difficult to delineate. Second, the correct surface topology on intricate voxel sets may not be obvious. Third, the surface area of a digital voxel world is generally very different than the area of the underlying continuous surface. These problems can be partly circumvented by transforming the voxel data to a polyhedral surface representation. Our challenge is to accomplish the task while maintaining the original voxel representation. Estimators for the continuous surface area of digital objects have been available for some time. However, the known methods are limited to fairly smooth and “well-behaved” surfaces. This research bridges the gap between the available surface area estimation theory, that applies to idealized settings, and the reality of MRI brain data. Surface connectivity ambiguities are alleviated by considering the object/background boundary voxel faces rather than the border voxels themselves. The region of interest on the surface is delimited by growing geodesic paths between user-provided anchor points. Surface estimation is extended to admit surfaces with higher curvature than previously considered. Performance evaluation results are provided, and operation on MRI brain data is demonstrated.     

On the Functionality and Usefulness of Quadraginta Octants of Naive Sphere

This paper presents a novel study on the functional gradation of coordinate planes in connection with the thinnest and tunnel-free (i.e., naive) discretization of sphere in the integer space. For each of the 48-symmetric quadraginta octants of naive sphere with integer radius and integer center, we show that the corresponding voxel set forms a bijection with its projected pixel set on a unique coordinate plane, which thereby serves as its functional plane. We use this fundamental property to prove several other theoretical results for naive sphere. First, the quadraginta octants form symmetry groups and subgroups with certain equivalent topological properties. Second, a naive sphere is always unique and consists of fewest voxels. Third, it is efficiently constructible from its functional-plane projection. And finally, a special class of 4-symmetric discrete 3D circles can be constructed on a naive sphere based on back projection from the functional plane.     

Model-driven segmentation of articulating humans in Laplacian Eigenspace

We propose a general approach using Laplacian Eigenmaps and a graphical model of the human body to segment 3D voxel data of humans into different articulated chains. In the bottom-up stage, the voxels are transformed into a high-dimensional (6D or less) Laplacian Eigenspace (LE) of the voxel neighborhood graph. We show that LE is effective at mapping voxels on long articulated chains to nodes on smooth 1D curves that can be easily discriminated, and prove these properties using representative graphs. We fit 1D splines to voxels belonging to different articulated chains such as the limbs, head and trunk, and determine the boundary between splines using the spline fitting error. A top-down probabilistic approach is then used to register the segmented chains, utilizing their mutual connectivity and individual properties. Our approach enables us to deal with complex poses such as those where the limbs form loops. We use the segmentation results to automatically estimate the human body models. While we use human subjects in our experiments, the method is fairly general and can be applied to voxel-based segmentation of any articulated object composed of long chains. We present results on real and synthetic data that illustrate the usefulness of this approach.     

Dividing Cubes算法生成的物体表面的法向量方向的光顺操作

在用DividingCubes算法提取的边界体素所构造的物体表面上,可能会存在法向量方向突变,使得物体表面光照图显示粗糙,文中提出了一种的领域加权平均法,对物体表面的法向量方向进行光顺处理,光顺操作只在相关边界体素间进行,并且对有多个等值面交汇的边界体素将不进行光顺操作,以避免模糊位于多个区域处的边界和保持物体表面光照图的细节,为避免在屏幕上产生孔洞,用光线投射法显示物体表面,文中所采用的光顺操作可以消除物体表面的法向量方向突变,使物体表面光照图光谱细腻,最后,给出一个医学图像的测试实例。     

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.     

Geometry-shader-based real-time voxelization and applications

This work proposes a new voxelization algorithm based on newly available GPU functionalities and designs several real-time applications to render complex lighting effects with the voxelization result. The voxelization algorithm can efficiently transform a highly complex scene in a surface-boundary representation into a set of voxels in one GPU pass using the geometry shader. Newly available 3D textures are used to directly record the surficial and volumetric properties of objects such as opaqueness, refraction, and transmittance. In the first, the usage of 3D textures can remove those strenuous efforts required to modify the encoding and decoding scheme when adjusting the voxel resolution. Second, surficial and volumetric properties recorded in 3D textures can be used to interactively compute and render more realistic lighting effects including the shadow of objects with complex occlusion and the refraction and transmittance of transparent objects. The shadow can be rendered with an absorption coefficient which is computed according to the number of surfaces drawing in each voxel during voxelization and used to compute the amount of light passing through partially occluded complex objects. The surface normal, transmittance coefficient and refraction index recorded in each voxel can be used to simulate the refraction and transmittance lighting effects of transparent objects using our multiple-surfaced refraction algorithm. Finally, the results demonstrate that our algorithm can transform a dynamic scene into a set of voxels and render complex lighting effects in real time without any pre-processing.     

从二维系列摄影图片提取剪影重构三维实体的光线跟踪算法

给出了利用二维系列摄影图片提取剪影重构三维实体的一种新算法,即围绕一个三维实体从多个角度拍摄照片,然后从照片中提取出实体的边界,通过基于光线跟踪的、对二维影像的合成得到原物体近似表面的三维点坐标,与传统的基于体像素的算法相比,该算法节省存储空间,近似精度与三维分辨率无直接关系,而且速度有所提高,特别当实体体积较大时,效果明显。     

Fast connected-component labelling in three-dimensional binary images based on iterative recursion

We propose two new methods to label connected components based on iterative recursion: one directly labels an original binary image while the other labels the boundary voxels followed by one-pass labelling of non-boundary object voxels. The novelty of the proposed methods is a fast labelling of large datasets without stack overflow and a flexible trade-off between speed and memory. For each iterative recursion: (1) the original volume is scanned in the raster order and an initially unlabelled object voxel v is selected, (2) a sub-volume with a user-defined size is formed around the selected voxel v, (3) within this sub-volume all object voxels 26-connected to v are labelled using iterations; and (4) subsequent iterative recursions are initiated from those border object voxels of the sub-volume that are 26-connected to v. Our experiments show that the time-memory trade-off is that the decrease in the execution time by one-third requires the increase in memory size by 3 orders. This trade-off is controlled by the user by changing the size of the sub-volume. Experiments on large three-dimensional brain phantom datasets (362 × 432 × 362 voxels of 56 MB (megabytes)) show that the proposed methods are three times faster on the average (with the maximum speedup of 10) than the existing iterative methods based on label equivalences with less than 1 MB memory consumption. Moreover, our algorithms are applicable to any dimensional data and are less dependant on the geometric complexity of connected components.