On marching cubes

A characterization and classification of the isosurfaces of trilinear functions is presented. Based upon these results, a new algorithm for computing a triangular mesh approximation to isosurfaces for data given on a 3D rectilinear grid is presented. The original marching cubes algorithm is based upon linear interpolation along edges of the voxels. The asymptotic decider method is based upon bilinear interpolation on faces of the voxels. The algorithm of this paper carries this theme forward to using trilinear interpolation on the interior of voxels. The algorithm described here will produce a triangular mesh surface approximation to an isosurface which preserves the same connectivity/separation of vertices as given by the isosurface of trilinear interpolation.     

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.     

Interactive point-based isosurface exploration and high-quality rendering

We present an efficient point-based isosurface exploration system with high quality rendering. Our system incorporates two point-based isosurface extraction and visualization methods: edge splatting and the edge kernel method. In a volume, two neighboring voxels define an edge. The intersection points between the active edges and the isosurface are used for exact isosurface representation. The point generation is incorporated in the GPU-based hardware-accelerated rendering, thus avoiding any overhead when changing the isovalue in the exploration. We call this method edge splatting. In order to generate high quality isosurface rendering regardless of the volume resolution and the view, we introduce an edge kernel method. The edge kernel upsamples the isosurface by subdividing every active cell of the volume data. Enough sample points are generated to preserve the exact shape of the isosurface defined by the trilinear interpolation of the volume data. By employing these two methods, we can achieve interactive isosurface exploration with high quality rendering.     

On the fractal dimension of isosurfaces

A (3D) scalar grid is a regular n1 x n2 x n3 grid of vertices where each vertex v is associated with some scalar value sv. Applying trilinear interpolation, the scalar grid determines a scalar function g where g(v) = sv for each grid vertex v. An isosurface with isovalue σ is a triangular mesh which approximates the level set g(-1)(σ). The fractal dimension of an isosurface represents the growth ;in the isosurface as the number of grid cubes increases. We define and discuss the fractal isosurface dimension. Plotting the fractal ;dimension as a function of the isovalues in a data set provides information about the isosurfaces determined by the data set. We present statistics on the average fractal dimension of 60 publicly available benchmark data sets. We also show the fractal dimension is highly correlated with topological noise in the benchmark data sets, measuring the topological noise by the number of connected components in the isosurface. Lastly, we present a formula predicting the fractal dimension as a function of noise and validate the formula with experimental results.     

VDVR: verifiable visualization of projection-based data

Practical volume visualization pipelines are never without compromises and errors. A delicate and often-studied component is the interpolation of off-grid samples, where aliasing can lead to misleading artifacts and blurring, potentially hiding fine details of critical importance. The verifiable visualization framework we describe aims to account for these errors directly in the volume generation stage, and we specifically target volumetric data obtained via computed tomography (CT) reconstruction. In this case the raw data are the X-ray projections obtained from the scanner and the volume data generation process is the CT algorithm. Our framework informs the CT reconstruction process of the specific filter intended for interpolation in the subsequent visualization process, and this in turn ensures an accurate interpolation there at a set tolerance. Here, we focus on fast trilinear interpolation in conjunction with an octree-type mixed resolution volume representation without T-junctions. Efficient rendering is achieved by a space-efficient and locality-optimized representation, which can straightforwardly exploit fast fixed-function pipelines on GPUs.     

Pursuing interactive visualization of irregular grids

Many branches of the sciences produce sample data not arranged on rectilinear grids, and visualization of such data is generally more complex than visualizing more regular data. While isosurface algorithms such as marching cubes can be adapted with relatively little performance penalty, direct volume rendering presents more difficulties. This paper explores these issues, concentrating on algorithms for a particular kind of irregular grid known as a curvilinear grid, composed of six-sided cells that may be considered a result of the deformation of a regular rectilinear grid.     

移动立方体算法的三重线性插值研究

移动立方体算法是目前最有影响的等值面构造方法,已经过了许多改进。现在采用的是三重线性插值模型,用三重线性插值计算等值面与体单元的交点。文章对三重线性插值生成的等值面进行了分析,分析了等值面的一些特点,重点讨论了等值面与边界体单元的交线的两种例外情况,基于这两种情况,给出了改进算法,最后通过实验验证了考虑这两种情况后算法的可行性。     

Ray-tracing polymorphic multidomain spectral/hp elements for isosurface rendering

The purpose of this paper is to present a ray-tracing isosurface rendering algorithm for spectral/hp (high-order finite) element methods in which the visualization error is both quantified and minimized. Determination of the ray-isosurface intersection is accomplished by classic polynomial root-finding applied to a polynomial approximation obtained by projecting the finite element solution over element-partitioned segments along the ray. Combining the smoothness properties of spectral/hp elements with classic orthogonal polynomial approximation theory, we devise an adaptive scheme which allows the polynomial approximation along a ray-segment to be arbitrarily close to the true solution. The resulting images converge toward a pixel-exact image at a rate far faster than sampling the spectral/hp element solution and applying classic low-order visualization techniques such as marching cubes.     

基于Fork/Join框架的等值面快速生成并行算法

针对传统串行等值面提取算法在处理离散点数量多、网格点密度大的数据时生成效率差的问题,提出一种新的基于Fork/Join框架下的等值面快速生成并行算法。通过对传统串行算法中的关键步骤进行并行计算可行性分析,提出可以实施并行计算的四个单独步骤:离散点数据网格化处理、等值点计算、等值线追踪与光滑、等值面标记识别。通过将并行计算作用于等值面生成的这四个步骤中,减少了等值面计算的执行时间,加快了等值面的生成速度。实验结果表明,在数据计算量较大时,与传统串行算法相比,并行算法能在2秒内快速生成等值面,最大加速比高于5.0,提高了等值面的生成效率并取得了良好的绘制效果,满足了高实时性的业务需求。     

基于布局图的多物体场景新视角图像生成网络

新视角图像生成任务指通过多幅参考图像,生成场景新视角图像。然而多物体场景存在物体间遮挡,物体信息获取不全,导致生成的新视角场景图像存在伪影、错位问题。为解决该问题,提出一种借助场景布局图指导的新视角图像生成网络,并标注了全新的多物体场景数据集（multi-objects novel view Synthesis,MONVS）。首先,将场景的多个布局图信息和对应的相机位姿信息输入到布局图预测模块,计算出新视角下的场景布局图信息;然后,利用场景中标注的物体边界框信息构建不同物体的对象集合,借助像素预测模块生成新视角场景下的各个物体信息;最后,将得到的新视角布局图和各个物体信息输入到场景生成器中构建新视角下的场景图像。在MONVS和ShapeNet cars数据集上与最新的几种方法进行了比较,实验数据和可视化结果表明,在多物体场景的新视角图像生成中,所提方法在两个数据集上都有较好的效果表现,有效地解决了生成图像中存在伪影和多物体在场景中位置信息不准确的问题。     

基于互信息图像配准中的局部极值问题研究

基于互信息的图像配准方法具有自动化程度高、配准精度高等优点,近年来在医学图像配准中得到广泛应用。但是当变换后像素坐标位于非采样网格点时,插值算法有时会使目标函数产生局部极值,使得最优化搜索终止于局部极值,得到错误的配准结果。分析了两种常见的插值算法和产生局部极值的原因,在此基础上提出一种新的插值算法。实验结果表明,该算法有效地抑制了基于互信息的目标函数的局部极值问题,使目标函数更加平滑。     

CPU Ray Tracing of Tree-Based Adaptive Mesh Refinement Data

Adaptive mesh refinement (AMR) techniques allow for representing a simulation's computation domain in an adaptive fashion. Although these techniques have found widespread adoption in high-performance computing simulations, visualizing their data output interactively and without cracks or artifacts remains challenging. In this paper, we present an efficient solution for direct volume rendering and hybrid implicit isosurface ray tracing of tree-based AMR (TB-AMR) data. We propose a novel reconstruction strategy, Generalized Trilinear Interpolation (GTI), to interpolate across AMR level boundaries without cracks or discontinuities in the surface normal. We employ a general sparse octree structure supporting a wide range of AMR data, and use it to accelerate volume rendering, hybrid implicit isosurface rendering and value queries. We demonstrate that our approach achieves artifact-free isosurface and volume rendering and provides higher quality output images compared to existing methods at interactive rendering rates.     

Visualization of Isosurfaces with Parametric Cubes

To render images from volume datasets, an interpolation method also called reconstruction is needed. The level of details of the resultant image closely depends on the filter used for reconstruction. We propose here a new filter producing C ¹ continue surfaces. The provided image quality is better than current high-quality algorithms, like splatting or trilinear raycasting, where tiny details are often eliminated. In contrast with other studied high quality filters that are practically unusable, our algorithm has been implemented interactively on a modest platform thanks to an efficient implementation using parametric cubes. We also demonstrate the interest of a min-max octree in the visualization of isosurfaces interactively thresholded.     

基于图像分割的三维重构

三维重构方法是医学图像可视化系统、治疗计划系统的重要技术。基于图像分割的三维重构方法结合了图像分割、等值面抽取、网格简化三种技术,是不同于传统Marching Cubes算法的一种三维重构方法。它首先将医学图像分割为二值图,然后利用Marching Cubes方法进行等值面抽取,最后对得到的网格模型进行简化。实验结果表明,基于图像分割的三维重构方法加快了Marching Cubes的运算速度,改善了重构的效果,有利于实现对基于三维重构的大型几何模型的实时绘制和交互。     

TV图像插值的双方向扩散改进算法

提出了一种双方向扩散图像插值方法,有效地减小了插值图像的边缘宽度,从而获得清晰而光滑的图像边缘.这种双方向扩散在图像边缘斜坡较亮一侧进行前向扩散,而在边缘斜坡较暗一侧进行后向扩散.同时,它能根据图像边缘的特征自适应地调整前向、后向扩散强度,从而避免了在插值的图像中产生虚的纹理或边缘.数值实验结果显示,该方法既能很好地减小插值图像的边缘宽度,又不会产生其他人工虚像.     

边导向的双三次彩色图像插值

提出了一个新的边导向的双三次卷积(Cubic convolution, CC)彩色图像插值算法. 对于待插值的像素, 首先在其邻域检测两个正交方向边的强度. 如果该 像素在一个强边上, 则沿着强边的方向执行CC插值估计该像素;否则, 该像素 在弱边或纹理区域, 通过加权平均两个正交方向的CC插值估计该像素. 本文方法也考虑了彩色平面之间的相关性. 实验结果显示, 本文方法显著优于经 典的CC插值和其他一些插值方法.     

Novel approach to development of direct volume rendering algorithms based on visualization quality assessment

A novel approach to the development of direct volume rendering algorithms is proposed. The approach is based on the assessment of the visualization quality. Analysis of rendering artifacts and various assessment methods is done using 3D reconstructed medical tomograms as test datasets. Analysis of the previous research on methods of 3D visualization quality assessment and quality improvement is presented. 3D visualization artifacts and quality measurement method (quantitative estimation) is proposed. The method does not require any ground truth image; hence, it is a universal approach to measure the quality of the 3D-reconstruction by any ray casting technique. The method is based on generation of the reference image as a mathematical expectation for a set of 3D visualizations obtained via the jittering technique. Start position of the rays are being shifted randomly towards their directions. To estimate the deviation of a pixel value from mathematical expectation, we use PSNR metrics, which is traditional metrics in signal and image processing and measures deviation in the decibel scale. The conditions of a proper use of the technique are discussed. A new virtual samplings method with preintegration is proposed to reduce sampling artifacts in the ray casting algorithm. The novelty of the method consists in using pre-integrated classification instead of post-classification in the virtual sampling method. A novel approach to 3D visualization algorithms development based on analysis of a ray casting method in quality-performance space is demonstrated by comparing the state-of-the-art ray casting methods and the proposed method. The comparative analysis revealed an advantage of the classical pre-integrated method in the case of using trilinear filtering without local shading. It also showed the advantage of the proposed virtual sampling method with pre-integration in the case of using tricubic filtering with local lighting.     

An invariant approach for image registration in digital subtraction angiography

In modern medicine, digital subtraction angiography is a powerful technique for the visualization of blood vessels in a sequence of X-ray images. A serious problem encountered in this technique is misregistration of images due to patient motion. The resulting artifacts which arise from the misalignment of successive images in the sequence frequently reduce the diagnostic value of the images. In this paper, a new approach to the registration of digital angiographic image sequences is proposed. It is based on local similarity detection by means of template matching according to a combined invariants-based similarity measure and on thin-plate spline image warping. This technique is fully automatic and very efficient to correct for patient motion artifacts. The proposed algorithm for this technique has been successfully applied to register several clinical data sets including coronary applications. It works perfectly well for both slow and sudden motions and is both effective and fast.     

Stereoscopic view-dependent visualization of terrain height fields

Visualization of large geometric environments has always been an important problem of computer graphics. We present a framework for the stereoscopic view-dependent visualization of large scale terrain models. We use a quadtree based multiresolution representation for the terrain data. This structure is queried to obtain the view-dependent approximations of the terrain model at different levels of detail. In order not to lose depth information, which is crucial for the stereoscopic visualization, we make use of a different simplification criterion, namely, distance-based angular error threshold. We also present an algorithm for the construction of stereo pairs in order to speed up the view-dependent stereoscopic visualization. The approach we use is the simultaneous generation of the triangles for two stereo images using a single draw-list so that the view frustum culling and vertex activation is done only once for each frame. The cracking problem is solved using the dependency information stored for each vertex. We eliminate the popping artifacts that can occur while switching between different resolutions of the data using morphing. We implemented the proposed algorithms on personal computers and graphics workstations. Performance experiments show that the second eye image can be produced approximately 45 percent faster than drawing the two images separately and a smooth stereoscopic visualization can be achieved at interactive frame rates using continuous multiresolution representation of height fields     

基于局部梯度的WaDi图像插值

线性插值算法容易产生细节模糊和边缘锯齿效应,为了较好地保持图像的边缘信息,改善图像的主观视觉效果,提出了一种改进的Warped Distance（WaDi）图像插值方法。传统的WaDi算法是对空间线性插值的改进,但它仅仅利用了图像边缘的局部不对称特征来计算WaDi。除了局部不对称特征,局部梯度特征也是图像边缘的一种重要特征。文中采用将局部不对称特征和局部梯度特征相结合的方法来计算WaDi,可同时保持图像边缘的细节特征和非边缘的光滑性。实验结果表明,用该方法能获得高精度的插值图像。