proposal for Evaluation of Gradient Filters for Volume Rendering submitted to fulfill the semester project requirement for EE 4777/6773: Digital Signal Processing November 15,1998 submitted to: Dr. Joseph Picone Department of Electrical and Computer Engineering 413 Simral, Hardy Road Mississippi State University BOX 9571 MS State, MS 39762 submitted by: Brandon Butler, Phani Kumar, Nivedita Sahasrabudhe, Shivaraj Tenginakai. Mississippi State University Mississippi State, Mississippi 39762 email: {brb1, pkm2}@ra.msstate.edu {nive,shiva}@erc.msstate.edu I. Abstract The process of volume rendering involves the reconstruction of a continuous function and its gradients from a discrete set of samples. An interpolation filter is used for the function reconstruction, while a gradient filter is used for the gradient reconstruction. In this project we propose to investigate the impact of the gradient filter on the rendered volume. We also perform a frequency domain analysis of the various filters used for the gradient reconstruction. We use the result of this analysis to evaluate and classify these filters on the basis of their performance on three main image artifacts: smoothing, postaliasing and overshoot. We also propose a new metric for filter quality. Finally, we compare the results of our theoretical analysis with the quality of the actual rendered image. II. Introduction Background Images can be considered to be intensity signals in the spatial domain. Volume data, generated using a CT, MRI or Ultrasonic scan, consists of intensity samples at discrete points in the spatial domain. To reconstruct an image, we need the intensity values at arbitrary points in the domain and to render the image we need the gradient values at these points. Motivation Gradient estimation is required in volume rendering. An inaccurate estimation of the gradient will yield wrong colors and opacities along a ray and thus severely affect the quality of the rendered image [7]. Hence, the choice of the gradient filter is critical. The motivation behind this project is two fold. First, we try to investigate the importance of the gradient filters in determining the quality of the rendered image. This we propose to do by using various filters for gradient reconstruction and observing the difference in the quality of the rendered image. Second, we propose to extend the existing metrics for evaluation of interpolation filters to gradient filters. Finally, we would like to compare the results obtained from the theoretical analysis with the images rendered previously. Previous Research Many researchers have shown that the Sinc function is an ideal interpolation filter and the Cosc function which is the analytic derivative of the Sinc is an ideal gradient filter [1] . These filters completely cut off frequencies above the Nyquist frequency. Because of this discontinuity, these filters have infinite window extent in the spatial domain. Therefore these filters are impractical to use for digital signals. A comparative study by Marschner and Lobb [6] proposed the use of different error metrics for various reconstructon artifacts of interpolation filters. These metrics analyze filters in the frequency domain and measure the smoothing, postaliasing and overshoot attributes of an interpolation filter. Their study showed that a windowed Sinc has the best behavior. However these filters are expensive to use because of their size. They showed that from a practical point of view Catmull-Roll filter of cubic interpolation filter family produced best results Equation (12). III. Theory Filter Equation In order to reconstruct a continuous function f(t) or its derivative/gradient f'(t) from a set of sampled points fk , we convolve the sampled signal values fk , with the filter kernel w [3]. Let, k , be an integer. t , be the distance. T , be the sampling distance. f(t), be the orignal continuous signal. fk(t), represents the samples of the orignal signal, i.e., fk (t) = f (kT). w, be the filter kernel, which provides the weights. frw , be the reconstructed signal. Then, if we apply the convolution sum we get, (1) This is the basic filter equation. If frw in Equation (1) represents reconstruction of the orignal function f(t) from the sample values then the filter w is called an interpolation filter. If frw in Equation (1) represents reconstruction of the derivative of the orignal function f'(t) from the sample values then the filter w is called a gradient filter. Equation (1) represents an infinite window filter, however in practice we never use an infinitely long filter. We usually define the filter extent to be M. This implies that w is zero outside the interval [-M, M]. Gradient Estimation There are numerous schemes to compute the derivatives [4]. The most common ones are summarized below: A. Derivative First: In this approach, we first compute the derivatives at the grid points using a gradient filter d and then interpolate these gradients using an interpolation filter h. (2) B. Interpolation First: In this methodology we first reconstruct the continuous function using an interpolation filter and then apply the gradient filter to obtain the gradients. (3) C. Continues Derivative: In this method we convolve the interpolation filter and the gradient filter to obtain a new continuous gradient filter. We can then use this filter to construct gradients at any arbitrary point. (4) D. Analytical Derivative: In this method we compute the gradients by convolving the samples with the derivative of the interpolation filter. (5) Filter Quality Metrics In order to evaluate various practical gradient filters we compare them with an ideal gradient filter. We extend the metrics developed by Marschner and Lobb for interpolation filters. We also propose a new metrics to take care of the issues which are not addressed by the Marschner and Lobb [6]. Extension of the Marschner and Lobb Metrics Marschner and Lobb proposed three metrics to analyze a given filter with respect to an ideal filter, for three main image artifacts: postaliasing, smoothing and overshoot. An ideal gradient filter can be shown to be characterized by a line with a constant slope in the frequency domain [1]. A. Postaliasing: arises when the energy from the aliases spectra "leaks through" into the reconstructon, due to the filter being significantly non zero at frequencies beyond the Nyquist range. Figure 1. Postaliasing. We define postaliasing metrics P(w), to be (6) where, A is the area under the filer beyond the Nyquist region (indicated by blue shading in the above figure). wr is the real filter kernel. B. Smoothing: measures the attenuation of high frequency terms by the filter. Though smoothing is desirable since it attenuates noise, but excess smoothing leads to blurred images. . Figure 2. Smoothing. We define smoothing metrics S(w) to be (7) where, A is the area between the ideal and the real filers within the Nyquist region (indicated by blue shading in the above figure). wr is the real filter. wi is the ideal filter. C. Overshoot: measures how much overshoot a given filter produces. Figure 3. Overshoot. We define the overshoot metrics O(w) to be (8) where, A is the area between the ideal and the real filers within the Nyquist region (indicated by blue shading in the above figure). wr is the real filter. wi is the ideal filter. New Filter Quality Metrics The above metrics have some inadequacies; they measure the overall energy difference between an ideal and a real filter, but they fail to take into account the distribution of this difference. For example the filters shown in figure 4.a and4. b, will evaluate to same value for the Marschner and Lobb metrics, since the energy difference (proportional to the shaded area) is same in either case. However, perceptually a gradually varying filter , as in figure 4.a is found to be more preferable than a filter with sharp variations. To measure this important factor we propose a new metrics using an norm. Figure 4. Postaliasing. We call this new metrics as Steepness Metrics M(w) and define it to be, (9) Filter Selection The filters we wish to analyze, include those well known in literature and those that were developed by Moller et. al. using a Taylor series expansion of the Equation (1). The following filters are considered in our analysis: A. Ideal Interpolation and Gradient Filters: According to the sampling theorem a signal can be accurately reconstructed using an ideal interpolation filter if it is bandwidth limited and is sampled at the Nyquist rate or higher. The ideal interpolation filter is the sinc function. (10) Gradient is defined as the derivative of the orignal function. Ideal interpolation with Sinc will reconstruct the orignal function accurately. It follows that the gradient can be reconstructed exactly by using the derivative of the Sinc function. Thus the ideal gradient reconstruction filter is analytic derivative of the ideal interpolation filter. The ideal gradient filter is defined as [1]: (11) The frequency domain representation of the ideal filters is shown in the following figures: Figure 5. Ideal Filters. The ideal filters are defined over an infinite spatial interval, and therefore cannot be used in practical applications. However, practical filters are compared against the ideal filters for evaluation. B. Cubic Interpolation Filters: The "Two Parameter Family" of cubic filters, with parameters B and C, defined by the following set of equations[6]: (12) This family includes well known B-spline(B=1, C=0), Catmull-Rom Spline (B=0, C=0.5) and Cardinal splines (B=0 and C = ). C. Cubic Gradient Filters: These class of filters are obtained by differentiating the above class of filters. They are defined by the following set of equations[3]: (13) D. Trilinear Interpolation Filter: This filter is defined by the following equation[6]: (14) E. Smooth Interpolation and Gradient Filters: Using a Taylor series expansion of the convolution sum Equation (1) , Moller et. al [3]. proposed a new series of smooth interpolation and gradient filters. Their derivation is explained below. We assume that the orignal signal function f(t) has at least first N derivaties, i.e. it is a member of the class of smooth functions CN. This condition is generally met in practise. This allows us to expand fk = f (kT) in Taylor series around f. (15) where, . Substituting this Taylor series expansion into Equation(1) and reordering the terms we can rewrite Equation (5) as: (16) where, (17) (18) (19) (20) The relation between the distance t , the offset , and the sampling distance T, is shown in the following figure: Figure 6. Filter of Window 4. To design an accurate filter for reconstructing the k-th derivative, we employ the following conditions on the coefficient , defined by the Equation (7): Condition 1: (21) Condition 2: (22) These two conditions define an N-EF class of filters (that is, Error function is of the Nth order), that reconstruct the k-th gradient. After applying these two conditions we get a piecewise filter kernel. For an interpolation filter an application of these conditions reduces the reconstruction function in Equation (7) to , thus the reconstruction function reconstructs the orignal function. Similarly for the first order gradient filter we get . The next condition arises from the fact we want the filter kernel w and the reconstructed function frw , to be part of same smooth function space CM [5]. This is necessary to obtain a continuous reconstructed function else the image may have undesirable artifacts. This leads to condition 3: Condition 3: (23) To satisfy this condition we represent filter w, by a basis smooth function of CM space, Equation (11). An obvious choice for basis function are polynomials since polynomials are members of . (24) Once we have selected a basis function we apply conditions 1 and 2 and solve for the constants involved in the polynomial. If the above set of conditions lead to a under determined system we treat the unsolved constants as the design parameters. By varying M and N and fixing k we get a family of filters that accurately reconstruct the k-th derivative, within an error factor of degree N. The choice of number of filter weights is rather arbitrary. If we chose too many, the resulting filter becomes computationaly inefficient. If too few are chosen the above equation system might not lead to a solution at all. IV. Evaluation In order to render volume data we have to select an interpolation filter, a gradient filter and a gradient estimation methodology Equations (2 -5). Since we are mainly interested in the gradient filters we keep the interpolation filter and the gradient estimation methodology constant and vary the gradient filter. We fix our interpolation filter to Catmull-Rom, since this filter is found to be the best practical reconstruction filter [6]. For gradient estimation methodology we choose the method of analytical derivative Equation (5), since this method is computationaly most efficient [4]. For evaluation of the various gradient filters. We adopt the strategy followed by Marschner and Lobb [6]. The use of a real database may lead to erroneous evaluation results, since the database may contain noise. Hence ,we use a synthetic database generated using the following test signal: (25) We sample the signal on a 40 x 40 x 40 lattice in the range with fM = 6 and . It can be shown that a significant amount of the energy of the function lies near the Nyquist frequency, making this signal very demanding on reconstruction filters. The following figure shows the image of the test volume for an isosurface . Figure 7. The unsampled test signal. Next, these gradient filters will be analyzed using the proposed metrics Equations (6 -9). The results of the analysis shall then be compared with the images obtained previously. This shall enable us to verify the relation between the theoretical prediction of a filter's quality and the quality of the image produced by it. Finally, real MRI datasets shall be used to validate the results of the analysis. These data sets are available in pubic domain at the Engineering Research Center (ERC) , Mississippi State University. They contain information on the volume lattice size and the grayscale values of intensity at the various points in the lattice. V. Project Overview The project context diagram is shown in the following figure. The project basically consists of four modules. The database is acquired from external sources. The function of each module is given below:, A. Filter module - image is reconstructed from the given database by this module. B. Evaluation module - reconstruction of the image is evaluated using methods outlined in this module. C. Rendering module - image is rendered using standard rendering algorithms, such as ray tracing, in this module. D. GUI module - provides the user interface. The user shall be able to select various interpolation and gradient filters and a gradient estimation scheme and observe the resultant rendered image. The user shall also have the option of selecting a filter and evaluating its performance on the various quality metrics described above ( Equatons (6 -9)). Figure 8. The Context Diagram. VI. References [1] M. J. Bentum, T. Malzbender, B. B. Lichtenbelt, "Frequency Analysis of Gradient Estimators in Volume Rendering," IEEE Transactions on Visualization and Computer Graphics, vol. 2, no. 3, pp. 242-254, September 1996. [2] T. Moller, R. Machiraju, K. Mueller, and R. Yagel, "Classification and Local Error Estimation of Interpolation and Derivative Filters for Volume Rendering," Proceedings of 1996 Symposium on Volume Visualization, pp. 71-78, San Francisco, CA, USA ,October 1996. [3] T. Moller, R. Machiraju, K. Mueller, R. Yagel, "Evaluation and Design of Filters Using a Taylor Series Expansion," IEEE Transactions on Visualization and Computer Graphics, vol. ITVCG-3, no. 2, pp. 184-199, June 1997. [4] T. Moller, R. Machiraju, K. Mueller, and R. Yagel, "A Comparison of Normal Estimation Schemes," Proceedings of IEEE Conference on Visualization '97, pp. 19-26, Phoenix, AZ, USA, October 1997. [5] T. Moller, R. Machiraju, K. Mueller, and R. Yagel, "Design of Accurate and Smooth Filters for Function and Derivative Reconstruction," Proceedings of 1998 Symposium on Volume Visualization, pp. 200-209, Chapel Hill, NC, USA, October 1998. [6] S.R. Marschner, and R.J. Lob, "An Evaluation of Reconstruction Filters for Volume Rendering," Proceedings of Visualization '94, pp. 100-107, Washington D.C., USA, October 1994. [7] R.A. Derbin, L. Carpenter, P. Hanrahan, "Volume Rendering," Computer Graphics, vol. 22, no. 4, pp. 51-58, August 1988.