In this paper, we study the propagation of data uncertainty through the marching cubes algorithm for isosurface visualization for correlated uncertain data. Consideration of correlation has been shown paramount for avoiding errors in uncertainty quantification and visualization in multiple prior studies. Although the problem of isosurface uncertainty with spatial data correlation has been previously addressed, there are two major limitations to prior treatments. First, there are no analytical formulations for uncertainty quantification of isosurfaces when the data uncertainty is characterized by a Gaussian distribution with spatial correlation. Second, as a consequence of the lack of analytical formulations, existing techniques resort to a Monte Carlo sampling approach, which is expensive and difficult to integrate into visualization tools. To address these limitations, we present a closed-form framework to efficiently derive uncertainty in marching cubes level-sets for Gaussian uncertain data with spatial correlation (MAGIC). To derive closed-form solutions, we leverage the Hinkley's derivation on the ratio of Gaussian distributions. With our analytical framework, we achieve a significant speed-up and enhanced accuracy of uncertainty quantification over classical Monte Carlo methods. We further accelerate our analytical solutions using many-core processors to achieve speed-ups up to $\text{585} \times$585× and integrability with production visualization tools for broader impact. We demonstrate the effectiveness of our correlation-aware uncertainty framework through experiments on meteorology, urban flow, and astrophysics simulation datasets.

Abstract. This paper presents a framework for efficient and accurate computation of X-ray optics, a key ingredient in optimization-based computed tomography (CT) reconstruction algorithms. Based on an algebraic framework for directional convolution in image space and detector space, we construct forward models for X-ray imaging whose computational cost can be optimized for each specific CT geometry. While the framework allows for modeling various sources of blur in the X-ray imaging process for any CT geometry, we demonstrate and characterize its effectiveness in fan-beam and cone-beam geometries with flat detectors. The experiments show improvements in computational efficiency as well as accuracy, in optics calculations and reconstruction error, of the proposed projector compared to the state-of-the-art methods used in forward- and back-projection algorithms.

We present a nonparametric statistical framework for the quantification, analysis, and propagation of data uncertainty in direct volume rendering (DVR). The state-of-the-art statistical DVR framework allows for preserving the transfer function (TF) of the ground truth function when visualizing uncertain data; however, the existing framework is restricted to parametric models of uncertainty. In this paper, we address the limitations of the existing DVR framework by extending the DVR framework for nonparametric distributions. We exploit the quantile interpolation technique to derive probability distributions representing uncertainty in viewing-ray sample intensities in closed form, which allows for accurate and efficient computation. We evaluate our proposed nonparametric statistical models through qualitative and quantitative comparisons with the mean-field and parametric statistical models, such as uniform and Gaussian, as well as Gaussian mixtures. In addition, we present an extension of the state-of-the-art rendering parametric framework to 2D TFs for improved DVR classifications. We show the applicability of our uncertainty quantification framework to ensemble, downsampled, and bivariate versions of scalar field datasets.

Numerical Weather Prediction (NWP) ensembles are commonly used to assess the uncertainty and confidence in weather forecasts. Spaghetti plots are conventional tools for meteorologists to directly examine the uncertainty exhibited by ensembles, where they simultaneously visualize isocontours of all ensemble members. To avoid visual clutter in practical usages, one needs to select a small number of informative isovalues for visual analysis. Moreover, due to the complex topology and variation of ensemble isocontours, it is often a challenging task to interpret the spaghetti plot for even a single isovalue in large ensembles. In this paper, we propose an interactive framework for uncertainty visualization of weather forecast ensembles that significantly improves and expands the utility of spaghetti plots in ensemble analysis. Complementary to state-of-the-art methods, our approach provides a complete framework for visual exploration of ensemble isocontours, including isovalue selection, interactive isocontour variability exploration, and interactive sub-region selection and re-analysis. Our framework is built upon the high-density clustering paradigm, where the mode structure of the density function is represented as a hierarchy of nested subsets of the data. We generalize the high-density clustering for isocontours and propose a bandwidth selection method for estimating the density function of ensemble isocontours. We present novel visualizations based on high-density clustering results, called the mode plot and the simplified spaghetti plot. The proposed mode plot visually encodes the structure provided by the high-density clustering result and summarizes the distribution of ensemble isocontours. It also enables the selection of subsets of interesting isocontours, which are interactively highlighted in a linked spaghetti plot for providing spatial context. To provide an interpretable overview of the positional variability of isocontours, our system allows for selection of informative isovalues from the simplified spaghetti plot. Due to the spatial variability of ensemble isocontours, the system allows for interactive selection and focus on sub-regions for local uncertainty and clustering re-analysis. We examine a number of ensemble datasets to establish the utility of our approach and discuss its advantages over state-of-the-art visual analysis tools for ensemble data.

Transfer function (TF) design is a central topic in direct volume rendering. The TF fundamentally translates data values into optical properties to reveal relevant features present in the volumetric data. We propose a semi-automatic TF design scheme which consists of two steps: First, we present a clustering process within 1D/2D TF domain based on the proximities of the respective volumetric features in the spatial domain. The presented approach provides an interactive tool that aids users in exploring clusters and identifying features of interest (FOI). Second, our method automatically generates a TF by iteratively refining the optical properties for the selected features using a novel feature visibility measurement. The proposed visibility measurement leverages the similarities of features to enhance their visibilities in DVR images. Compared to the conventional visibility measurement, the proposed feature visibility is able to efficiently sense opacity changes and precisely evaluate the impact of selected features on resulting visualizations. Our experiments validate the effectiveness of the proposed approach by demonstrating the advantages of integrating feature similarity into the visibility computations. We examine a number of datasets to establish the utility of our approach for semi-automatic TF design.

Sparse signal recovery from limited and/or degraded samples is fundamental to many applications, such as medical imaging, remote sensing, astronomical and seismic imaging. Discrete wavelet transform (DWT) has been commonly used for sparse representation of signals; nevertheless, due to its shift-variant nature, pseudo-Gibbs artifacts are present in the recovered signals. Using the redundant shift-invariant wavelet transform (SWT) is the ideal solution to obtain shift invariance; however, high redundancy factor of SWT limits its application in practical settings. We propose a dictionary splitting approach for sparse recovery from incomplete data, which leverages the ideas of cycle spinning in combination with Bregman splitting. The proposed method significantly improves the conventional signal reconstruction with DWT, offers the advantages of SWT, and overcomes high redundancy factor of SWT. We solve parallel sparse recovery problems with orthogonal dictionaries (DWT and its permuted versions), while we impose consistency between the results by updating the recovered image at each iteration. Our experiments demonstrate that few shifts are sufficient to achieve reconstruction accuracy as high as recovery with SWT, and significantly reduces its computational cost and redundancy factor.

With uncertainty present in almost all modalities of data acquisition, reduction, transformation, and representation, there is a growing demand for mathematical analysis of uncertainty propagation in data processing pipelines. In this paper, we present a statistical framework for quantification of uncertainty and its propagation in the main stages of the visualization pipeline. We propose a novel generalization of Irwin-Hall distributions from the statistical viewpoint of splines and box-splines, that enables interpolation of random variables. Moreover, we introduce a probabilistic transfer function classification model that allows for incorporating probability density functions into the volume rendering integral. Our statistical framework allows for incorporating distributions from various sources of uncertainty which makes it suitable in a wide range of visualization applications. We demonstrate effectiveness of our approach in visualization of ensemble data, visualizing large datasets at reduced scale, iso-surface extraction, and visualization of noisy data.

The problem of isosurface extraction in uncertain data is an important research problem and may be approached in two ways. One can extract statistics (e.g., mean) from uncertain data points and visualize the extracted field. Alternatively, data uncertainty, characterized by probability distributions, can be propagated through the isosurface extraction process. We analyze the impact of data uncertainty on topology and geometry extraction algorithms. A novel, edge-crossing probability based approach is proposed to predict underlying isosurface topology for uncertain data. We derive a probabilistic version of the midpoint decider that resolves ambiguities that arise in identifying topological configurations. Moreover, the probability density function characterizing positional uncertainty in isosurfaces is derived analytically for a broad class of nonparametric distributions. This analytic characterization can be used for efficient closed-form computation of the expected value and variation in geometry. Our experiments show the computational advantages of our analytic approach over Monte-Carlo sampling for characterizing positional uncertainty. We also show the advantage of modeling underlying error densities in a nonparametric statistical framework as opposed to a parametric statistical framework through our experiments on ensemble datasets and uncertain scalar fields.

Signal reconstruction from the smallest possible Fourier measurements has been a key motivation in the compressed sensing research. We present an approach that exploits the interdependency and structural sparsity of partial derivatives for lowering the sampling rates necessary for accurate reconstruction. Our experiments show that for signals that are sparse in the gradient domain our proposed method significantly outperforms the existing approaches including the total variation (TV) based CS reconstruction.

Abstract In this paper, we investigate compressed sensing principles to devise an in‐situ data reduction framework for visualization of volumetric datasets. We exploit the universality of the compressed sensing framework and show that the proposed method offers a refinable data reduction approach for volumetric datasets. The accurate reconstruction is obtained from partial Fourier measurements of the original data that are sensed without any prior knowledge of specific feature domains for the data. Our experiments demonstrate the superiority of surfacelets for efficient representation of volumetric data. Moreover, we establish that the accuracy of reconstruction can further improve once a more effective basis for a sparser representation of the data becomes available.

We examine different sampling lattices and their respective bandlimited spaces for reconstruction of irregularly sampled multidimensional images. Considering an irregularly sampled dataset, we demonstrate that the non-tensor-product bandlimited approximations corresponding to the body-centered cubic and face-centered cubic lattices provide a more accurate reconstruction than the tensor-product bandlimited approximation associated with the commonly-used Cartesian lattice. Our practical algorithm uses multidimensional sinc functions that are tailored to these lattices and a regularization scheme that provides a variational framework for efficient implementation. Using a number of synthetic and real data sets we record improvements in the accuracy of reconstruction in a practical setting.

We present a study of linear interpolation when applied to uncertain data. Linear interpolation is a key step for isosurface extraction algorithms, and the uncertainties in the data lead to non-linear variations in the geometry of the extracted isosurface. We present an approach for deriving the probability density function of a random variable modeling the positional uncertainty in the isosurface extraction. When the uncertainty is quantified by a uniform distribution, our approach provides a closed-form characterization of the mentioned random variable. This allows us to derive, in closed form, the expected value as well as the variance of the level-crossing position. While the former quantity is used for constructing a stable isosurface for uncertain data, the latter is used for visualizing the positional uncertainties in the expected isosurface level crossings on the underlying grid.

This paper introduces a new way of constructing 2-D wavelets which generalizes the univariate sinc wavelets to images sampled on arbitrary lattices. For lattices other than Cartesian, such wavelets are no longer tensor products of the univariate version. The proposed construction method is based on the zonotope decomposition of the Brillouin zone of the lattice and can be generalized to all 2-D or 3-D lattices. While our construction allows for the derivation of sinc wavelets for any 2-D lattice, we particularly study the case for the hexagonal lattice. We present experiments that contrast Cartesian tensor-product wavelet decomposition against the non-separable hexagonal wavelet decomposition and demonstrate the increased isotropy in the latter case.

We present a geometric framework for explicit derivation of multivariate sampling functions (sinc) on multidimensional lattices. The approach leads to a generalization of the link between sinc functions and the Lagrange interpolation in the multivariate setting. Our geometric approach also provides a frequency partition of the spectrum that leads to a nonseparable extension of the 1-D Shannon (sinc) wavelets to the multivariate setting. Moreover, we propose a generalization of the Lanczos window function that provides a practical and unbiased approach for signal reconstruction on sampling lattices. While this framework is general for lattices of any dimension, we specifically characterize all 2-D and 3-D lattices and show the detailed derivations for 2-D hexagonal body-centered cubic (BCC) and face-centered cubic (FCC) lattices. Both visual and numerical comparisons validate the theoretical expectations about superiority of the BCC and FCC lattices over the commonly used Cartesian lattice.

B-splines are attractive basis functions for the continuous-domain representation of biomedical images and volumes. In this paper, we prove that the extended family of box splines are closed under the Radon transform and derive explicit formulae for their transforms. Our results are general; they cover all known brands of compactly-supported box splines (tensor-product B-splines, separable or not) in any number of dimensions. The proposed box spline approach extends to non-Cartesian lattices used for discretizing the image space. In particular, we prove that the 2-D Radon transform of an N-direction box spline is generally a (nonuniform) polynomial spline of degree N-1. The proposed framework allows for a proper discretization of a variety of tomographic reconstruction problems in a box spline basis. It is of relevance for imaging modalities such as X-ray computed tomography and cryo-electron microscopy. We provide experimental results that demonstrate the practical advantages of the box spline formulation for improving the quality and efficiency of tomographic reconstruction algorithms.

We present a variational framework for the reconstruction of irregularly-sampled volumetric data in, nontensor-product, spline spaces. Motivated by the sampling-theoretic advantages of body centered cubic (BCC) lattice, this paper examines the BCC lattice and its associated box spline spaces in a variational setting. We introduce a regularization scheme for box splines that allows us to utilize the BCC lattice in a variational reconstruction framework. We demonstrate that by choosing the BCC lattice over the commonly-used Cartesian lattice, as the shift-invariant representation, one can increase the quality of signal reconstruction. Moreover, the computational cost of the reconstruction process is reduced in the BCC framework due to the smaller bandwidth of the system matrix in the box spline space compared to the corresponding tensor-product B-spline space. The improvements in accuracy are quantified numerically and visualized in our experiments with synthetic as well as real biomedical datasets.

In this paper, we propose an interlaced multi-shell sampling scheme for the reconstruction of the diffusion propagator from diffusion weighted magnetic resonance imaging (DW-MRI). In standard multi-shell sampling schemes, sample points are uniformly distributed on several spherical shells in q-space. The distribution of sample points is the same for all shells, and is determined by the vertices of a selected polyhedron. We propose a more efficient interlaced scheme where sample points are different on alternating shells and are determined by the vertices of a pair of dual polyhedra. Since it samples more directions than the standard scheme, this method offers increased angular discrimination. Another contribution of this work is the application of optimal sampling lattices to q-space data acquisition and the proposal of a model-free reconstruction algorithm, which uses the lattice dependent sinc interpolation function. It is shown that under this reconstruction framework, the body centered cubic (BCC) lattice provides increased accuracy. The sampling scheme and the reconstruction algorithms were evaluated on simulated data as well as rat brain data collected on a 600 MHz (14.1T) Bruker imaging spectrometer.

The Body-Centered Cubic (BCC) and Face-Centered Cubic (FCC) lattices have been analytically shown to be more efficient sampling lattices than the traditional Cartesian Cubic (CC) lattice, but there has been no estimate of their visual comparability. Two perceptual studies (each with N = 12 participants) compared the visual quality of images rendered from BCC and FCC lattices to images rendered from the CC lattice. Images were generated from two signals: the commonly used Marschner-Lobb synthetic function and a computed tomography scan of a fish tail. Observers found that BCC and FCC could produce images of comparable visual quality to CC, using 30-35 percent fewer samples. For the images used in our studies, the L(2) error metric shows high correlation with the judgement of human observers. Using the L(2) metric as a proxy, the results of the experiments appear to extend across a wide range of images and parameter choices.

We present a quasi interpolation framework that attains the optimal approximation-order of Voronoi splines for reconstruction of volumetric data sampled on general lattices. The quasi interpolation framework of Voronoi splines provides an unbiased reconstruction method across various lattices. Therefore this framework allows us to analyze and contrast the sampling-theoretic performance of general lattices, using signal reconstruction, in an unbiased manner. Our quasi interpolation methodology is implemented as an efficient FIR filter that can be applied online or as a preprocessing step. We present visual and numerical experiments that demonstrate the improved accuracy of reconstruction across lattices, using the quasi interpolation framework.

Abstract This paper introduces a quasi‐interpolation method for reconstruction of data sampled on the Body Centered Cubic (BCC) lattice. The reconstructions based on this quasi‐interpolation achieve the optimal approximation order offered by the shifts of the quintic box spline on the BCC lattice. We also present a local FIR filter that is used to filter the data for quasi‐interpolation. We document the improved quality and fidelity of reconstructions after employing the introduced quasi‐interpolation method. Finally the resulting quasi‐interpolation on the BCC sampled data are compared to the corresponding quasi‐interpolation method on the Cartesian sampled data.

In this paper, we extend the single relaxation time Lattice-Boltzmann Method (LBM) to the 3D body-centered cubic (BCC) lattice. We show that the D3bQ15 lattice defined by a 15 neighborhood connectivity of the BCC lattice is not only capable of more accurately discretizing the velocity space of the continuous Boltzmann equation as compared to the D3Q15 Cartesian lattice, it also achieves a comparable spatial discretization with 30 percent less samples. We validate the accuracy of our proposed lattice by investigating its performance on the 3D lid-driven cavity flow problem and show that the D3bQ15 lattice offers significant cost savings while maintaining a comparable accuracy. We demonstrate the efficiency of our method and the impact on graphics and visualization techniques via the application of line-integral convolution on 2D slices as well as the extraction of streamlines of the 3D flow. We further study the benefits of our proposed lattice by applying it to the problem of simulating smoke and show that the D3bQ15 lattice yields more detail and turbulence at a reduced computational cost.

We introduce a family of box splines for efficient, accurate and smooth reconstruction of volumetric data sampled on the Body Centered Cubic (BCC) lattice, which is the favorable volumetric sampling pattern due to its optimal spectral sphere packing property. First, we construct a box spline based on the four principal directions of the BCC lattice that allows for a linear C(0) reconstruction. Then, the design is extended for higher degrees of continuity. We derive the explicit piecewise polynomial representation of the C(0) and C(2) box splines that are useful for practical reconstruction applications. We further demonstrate that approximation in the shift-invariant space---generated by BCC-lattice shifts of these box splines---is {twice} as efficient as using the tensor-product B-spline solutions on the Cartesian lattice (with comparable smoothness and approximation order, and with the same sampling density). Practical evidence is provided demonstrating that not only the BCC lattice is generally a more accurate sampling pattern, but also allows for extremely efficient reconstructions that outperform tensor-product Cartesian reconstructions.

We introduce and analyze an efficient reconstruction algorithm for FCC-sampled data. The reconstruction is based on the 6-direction box spline that is naturally associated with the FCC lattice and shares the continuity and approximation order of the triquadratic B-spline. We observe less aliasing for generic level sets and derive special techniques to attain the higher evaluation efficiency promised by the lower degree and smaller stencil-size of the C1 6-direction box spline over the triquadratic B-spline.

This paper presents a user study of the visual quality of an imaging pipeline employing the optimal body-centered cubic (BCC) sampling lattice. We provide perceptual evidence supporting the theoretical expectation that sampling and reconstruction on the BCC lattice offer superior imaging quality over the traditionally popular Cartesian cubic (CC) sampling lattice. We asked 12 participants to choose the better of two images: one image rendered from data sampled on the CC lattice and one image that is rendered from data sampled on the BCC lattice. We used both synthetic and CT volumetric data, and confirm that the theoretical advantages of BCC sampling carry over to the perceived quality of rendered images. Using 25% to 35% fewer samples, BCC sampled data result in images that exhibit comparable visual quality to their CC counterparts.

We propose a three dimensional multi-resolution scheme to represent volumetric data in resolutions which are powers of two, resolving the rigidity of the commonly used separable Cartesian multi-resolution schemes in 3D that only allow for change of resolution by a power of eight. Through in-depth comparisons with the counterpart resampling solutions on the Cartesian lattice, we demonstrate the superiority of our subsampling scheme. We derive and document the Fourier domain analysis of this representation. Using such an analysis one can obtain ideal and discrete multidimensional filters for this multi-resolution scheme.

In this article we propose a box spline and its variants for reconstructing volumetric data sampled on the Cartesian lattice. In particular we present a tri-variate box spline reconstruction kernel that is superior to tensor product reconstruction schemes in terms of recovering the proper Cartesian spectrum of the underlying function. This box spline produces a C2 reconstruction that can be considered as a three dimensional extension of the well known Zwart-Powell element in 2D. While its smoothness and approximation power are equivalent to those of the tri-cubic B-spline, we illustrate the superiority of this reconstruction on functions sampled on the Cartesian lattice and contrast it to tensor product B-splines. Our construction is validated through a Fourier domain analysis of the reconstruction behavior of this box spline. Moreover, we present a stable method for evaluation of this box spline by means of a decomposition. Through a convolution, this decomposition reduces the problem to evaluation of a four directional box spline that we previously published in its explicit closed form.

In this work we present a hardware-accelerated direct volume rendering system for visualizing multivariate wave functions in semiconducting quantum dot (QD) simulations. The simulation data contains the probability density values of multiple electron orbitals for up to tens of millions of atoms, computed by the NEMO3-D quantum device simulator software run on large-scale cluster architectures. These atoms form two interpenetrating crystalline face centered cubic lattices (FCC), where each FCC cell comprises the eight corners of a cubic cell and six additional face centers. We have developed compact representation techniques for the FCC lattice within PC graphics hardware texture memory, hardware-accelerated linear and cubic reconstruction schemes, and new multi-field rendering techniques utilizing logarithmic scale transfer functions. Our system also enables the user to drill down through the simulation data and execute statistical queries using general-purpose computing on the GPU (GPGPU).

We derive piecewise linear and piecewise cubic box spline reconstruction filters for data sampled on the body centered cubic (BCC) lattice. We analytically derive a time domain representation of these reconstruction filters and using the Fourier slice-projection theorem we derive their frequency responses. The quality of these filters, when used in reconstructing BCC sampled volumetric data, is discussed and is demonstrated with a raycaster. Moreover, to demonstrate the superiority of the BCC sampling, the resulting reconstructions are compared with those produced from similar filters applied to data sampled on the Cartesian lattice.

This work derives a family of dilation matrices for the body-centered cubic (BCC) lattice, which is optimal in the sense of spectral sphere packing. While satisfying the necessary conditions for dilation, these matrices are all cube roots of an integer scalar matrix. This property offers theoretical advantages for construction of wavelet functions in addition to the practical advantages when iterating through a perfect reconstruction filter bank based on BCC downsampling. Lastly, we factor the BCC matrix into two matrices that allow us to cascade two two-channel perfect reconstruction filter banks in order to construct a four-channel perfect reconstruction filter bank based on BCC downsampling.

In this paper, we introduce algorithms to voxelize polygonal meshes in common sampling lattices. In the case of Cartesian lattices, we complete the separability and minimality proof for the voxelization method presented by Huang et al. We extend the ideas to general 2D lattices, including hexagonal lattices, and 3D body-centred cubic lattices. The notion of connectedness in the two lattice structures is discussed along with a novel voxelization algorithm for such lattices. Finally, we present the proof that meshes voxelized with our proposed algorithm satisfy the separability and minimality criteria.