Efficient normal estimation using variable‐size operator

Shading an object is to simulate the behaviour of light incident on its surfaces. It is necessary to calculate normal vectors on the surfaces of the object for shading it. Since objects do not contain surface inclination in voxel‐based representation, a normal vector for each voxel must be estimated from the relative position of its neighbouring voxels that have the same data value. The previously devised methods that use fixed‐size gradient operators can estimate normal vectors accurately only in a limited area and may cause some errors and artefacts. In this paper we propose an efficient normal estimation method using an extended central difference operator whose size can vary according to the arrangement of surface‐comprising voxels. This method calculates normals more accurately than the previous methods and its computation time is shorter than that of methods that guarantee the same image quality. In order to show the improvement, we compare the quality of resulting images and processing time by implementing the newly proposed method and the previous methods and then applying them to some volume data. Copyright © 1999 John Wiley & Sons, Ltd.     

A new method for analyzing local shape in three-dimensional images based on medial axis transformation

In this paper, we propose a new approach based on three-dimensional (3-D) medial axis transformation for describing geometrical shapes in three-dimensional images. For 3-D-images, the medial axis, which is composed of both curves and medial surfaces, provides a simplified and reversible representation of structures. The purpose of this new method is to classify each voxel of the three-dimensional images in four classes: boundary, branching, regular and arc points. The classification is first performed on the voxels of the medial axis. It relies on the topological properties of a local region of interest around each voxel. The size of this region of interest is chosen as a function of the local thickness of the structure. Then, the reversibility of the medial axis is used to deduce a labeling of the whole object. The proposed method is evaluated on simulated images. Finally, we present an application of the method to the identification of bone structures from 3-D very high-resolution tomographic images.     

Digital surfaces

A three-dimensional digital object is a union of voxels, i.e., upright unit cubes whose vertices have integer coordinates. The surface of such an object thus consists of surface pixels, i.e., unit squares parallel to the coordinate planes and whose vertices have integer coordinates. This paper discusses some basic properties of digital surfaces.     

Interactive visualization of 3D medical data

Techniques for rendering 3-D medical data are described. They consist of (1) surface-based techniques, which apply a surface detector to the sample array, then fit geometric primitives to the detected surfaces, and finally render the resulting geometric representation; (2) binary voxel techniques, which begin by thresholding the volume data to produce a three-dimensional binary array; the cuberille algorithm then renders this array by treating 1's as opaque cubes having six polygonal faces; and (3) volume-rendering techniques, a variant of the binary voxel techniques in which a color and a partial opacity are assigned to each voxel; images are formed from the resulting colored, semitransparent volume by blending together voxels projecting to the same pixel on the picture plane. Specialized display devices (stereo viewers, varifocal mirrors, cine sequences, real-time image-generation systems, and head-mounted displays) are described. Topics for future research are identified     

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

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

Discrete ray tracing

Discrete ray tracing, or 3-D raster ray tracing (RRT), which, unlike existing ray tracing methods that use geometric representation for the 3-D scene employs a 3-D discrete raster of voxels for representing the 3-D scene in the same way a 2-D raster of pixels represents a 2-D image, is discussed. Each voxel is a small quantum unit of volume that has numeric values associated with it representing some measurable properties or attributes of the real object or phenomenon at that voxel. It is shown that RRT operates in two phases: preprocessing voxel and discrete ray tracing. In the voxel phase, the geometric model is digitized using 3-D scan-conversion algorithms that convert the continuous representation of the model into a discrete representation within the 3-D raster. In the second phase, RRT employs a discrete variation of the conventional recursive ray tracer in which 3-D discrete rays are traversed through the 3-D raster to find the first surface voxel. Encountering a nontransparent voxel indicates a ray-surface hit. Results obtained by running the RRT software one one 20-MIPS (25-GHz) processor of a Silicon Graphics 4D/240GTX are presented in terms of CPU time     

Volume graphics

Volume graphics, which employs a volume buffer of voxels for 3D scene representation, is discussed. Volume graphics offers advantages over surface graphics: it is viewpoint independent, insensitive to scene and object complexity, and suitable for the representation of sampled and simulated data sets. Moreover, geometric objects can be mixed with these data sets. Volume graphics supports the visualization of internal structures and lends itself to the realization of block operations, constructive solid geometry modeling, irregular voxel sizes, and hierarchical representation. The problems associated with the volume buffer representation (such as discreteness, memory size, processing time, and loss of geometric representation) are discussed     

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.     

Hole filling of a 3D model by flipping signs of a signed distance field in adaptive resolution

When we use range finders to observe the shape of an object, many occluded areas may occur. These become holes and gaps in the model and make it undesirable for various applications. We propose a novel method to fill holes and gaps to complete this incomplete model. As an intermediate representation, we use a Signed Distance Field (SDF), which stores Euclidean signed distances from a voxel to the nearest point of the mesh model. By using an SDF, we can obtain interpolating surfaces for holes and gaps. The proposed method generates an interpolating surface that becomes smoothly continuous with real surfaces by minimizing the area of the interpolating surface. Since the isosurface of an SDF can be identified as being a real or interpolating surface from the magnitude of signed distances, our method computes the area of an interpolating surface in the neighborhood of a voxel both before and after flipping the sign of the signed distance of the voxel. If the area is reduced by flipping the sign, our method changes the sign for the voxel. Therefore, we minimize the area of the interpolating surface by iterating this computation until convergence. Unlike methods based on Partial Differential Equations (PDE), our method does not require any boundary condition, and the initial state that we use is automatically obtained by computing the distance to the closest point of the real surface. Moreover, because our method can be applied to an SDF of adaptive resolution, our method efficiently interpolates large holes and gaps of high curvature.We tested the proposed method with both synthesized and real objects and evaluated the interpolating surfaces.     

肝脏血管的医学图象三维重建

提出了一种体素三维重建快速算法，它根据三维空间中体素相邻的定义，把体素表面元素的相邻与环绕体素表面的环路相关，重新进行了目标表面的描述，并对人体肝脏ＣＴ图象进行了三维重建和显示，得到了直观的肝脏门静脉的分支和走向图象，达到了无损伤的解剖的目的。为肝脏病变的ＣＴ、ＭＲＩ等定位诊断，定向介入治疗以及规则性肝叶、肝段切除提供了实验依据和理论基础。     

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.     

Asymptotic bayesian surface estimation using an image sequence

A new approach is introduced to estimating object surfaces in three-dimensional space from a sequence of images. A 3D surface of interest here is modeled as a function known up to the values of a few parameters. Surface estimation is then treated as the general problem of maximum-likelihood parameter estimation based on two or more functionally related data sets. In our case, these data sets constitute a sequence of images taken at different locations and orientations. Experiments are run to illustrate the various advantages of using as many images as possible in the estimation and of distributing camera positions from first to last over as large a baseline as possible. In order to extract all the usable information from the sequence of images, all the images should be available simultaneously for the parameter estimation. We introduce the use of asymptotic Bayesian approximations in order to summarize the useful information in a sequence of images, thereby drastically reducing both the storage and the amount of processing required. This leads to a sequential Bayesian estimator for the surface parameters, where the information extracted from previous images is summarized in a quadratic form. The attractiveness of our approach is that now all the usual tools of statistical signal analysis, for example, statistical decision theory for object recognition, can be brought to bear; the information extraction appears to be robust and computationally reasonable; the concepts are geometric and simple; and essentially optimal accuracy should result. Experimental results are shown for extending this approach in two ways. One is to model a highly variable surface as a collection of small patches jointly constituting a stochastic process (e.g., a Markov random field) and to reconstruct this surface using maximum a posteriori probability (MAP) estimation. The other is to cluster together those patches constituting the same primitive object through the use of MAP segmentation. This provides a simultaneous estimation and segmentation of a surface into primitive constituent surfaces.     

Brain reading using full brain support vector machines for object recognition: there is no "face" identification area

Over the past decade, object recognition work has confounded voxel response detection with potential voxel class identification. Consequently, the claim that there are areas of the brain that are necessary and sufficient for object identification cannot be resolved with existing associative methods (e.g., the general linear model) that are dominant in brain imaging methods. In order to explore this controversy we trained full brain (40,000 voxels) single TR (repetition time) classifiers on data from 10 subjects in two different recognition tasks on the most controversial classes of stimuli (house and face) and show 97.4% median out-of-sample (unseen TRs) generalization. This performance allowed us to reliably and uniquely assay the classifier's voxel diagnosticity in all individual subjects' brains. In this two-class case, there may be specific areas diagnostic for house stimuli (e.g., LO) or for face stimuli (e.g., STS); however, in contrast to the detection results common in this literature, neither the fusiform face area nor parahippocampal place area is shown to be uniquely diagnostic for faces or places, respectively.     

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.     

Frame-sliced voxel representation: An accurate and memory-efficient modeling method for workpiece geometry in machining simulation

This paper presents a new and enhanced voxel representation format for modeling the machined workpiece geometry in simulating machining operations involving repeated update of the workpiece model volume. The modeling format is named as the Frame-Sliced Voxel representation (FSV-rep) as it uses a novel concept of frame-sliced voxels to represent the boundary of the workpiece volume. The FSV-rep uses a multi-level surface voxel representation for sparse and memory-efficient implementations. The utilization of frame-sliced voxels enables approximation of the workpiece surface to only loosely depend on the grid resolution but achieve sub-voxel resolution updates for the model volume. It can, thus, provide a boundary representation of the workpiece model at an accuracy that is much higher than a basic voxel model of the same grid resolution and a similar model size. Quantitative comparisons of the FSV-rep with the traditional voxel representations at the same finest grid resolution show improvement up to two orders of magnitude in accuracy with only marginal increases in the model size. This confirms the effectiveness of the FSV-rep in simulating machined workpiece geometry in complex machining processes such as multi-axis milling.     

三角网格模型体素特征分割

针对现有机械制造领域网格模型分割结果缺少工程含义的现状,提出了一种三角网格模型体素特征分割方法。首先在对三角网格模型分割的基础上,对由网格分割得到的每个子网格进行曲面类型识别,然后在基本体素及典型结构显著特征表示的基础上,把识别出的曲面集合与基本体素及典型结构进行匹配,从而将分割结果分类为自由曲面、基本体素和复杂体素,实现具有工程含义的体素特征分割。该方法可以降低模型重构的难度,加快模型重构的速度。     

3D line voxelization and connectivity control

Voxelization algorithms that convert a 3D continuous line representation into a discrete line representation have a dual role in graphics. First, these algorithms synthesize voxel-based objects in volume graphics. The 3D line itself is a fundamental primitive, also used as a building block for voxelizing more complex objects. For example, sweeping a 3D voxelized line along a 3D voxelized circle generates a voxelized cylinder. The second application of 3D line voxelization algorithms is for ray traversal in voxel space. Rendering techniques that cast rays through a volume of voxels are based on algorithms that generate the set of voxels visited (or pierced) by the continuous ray. Discrete ray algorithms have been developed for traversing a 3D space partition or a 3D array of sampled or computed data. These algorithms produce one discrete point per step, in contrast to ray casting algorithms for volume rendering, which track a continuous ray at constant intervals, and to voxelization algorithms that generate nonbinary voxel values (for example, partial occupancies). Before considering algorithms for generating discrete lines, we introduce the topology and geometry of discrete lines     

Extended linked voxel structure for point-to-mesh distance computation and its application to NC collision detection

When working with milling or polishing robots and large workpieces it is necessary to check not only the milling or polishing tool for collision, but it is also necessary to check the remaining arms of the robot for collision. In most of the cases the arms of the robot do not collide with the workpiece and so applying an existing collision detection algorithm to the arms of the robot slows the process down. In this paper, we present an algorithm for quickly assuring non-collisions, which is especially targeted at collisions of the arms of the robot with a workpiece. The algorithm is based on an extended voxel structure. More precisely, we extend a voxel structure by adding distance values to the corner of the voxels and by linking empty voxels to non-empty voxels to accelerate finding the desired voxel. This ensures that we only need to consider a small subset of the triangles describing the workpiece’s surface, namely those triangles that are close to the possible collision area. The triangles within each non-empty voxel are stored in a bsp-tree. For empty voxels, we save information about the distances to the mesh. This setup speeds up the point-to-mesh distance calculation, especially for points close to the mesh. The extra distance information in empty voxels enables a fast distance estimation and hence a fast early collision check.     

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

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