proposal for Evaluation of Derivative Filters submitted to the semester project requirement for EE 4777/6773: Digital Signal Processing October 1,1998 submitted to: Dr. Joseph Picone Department of Electrical and Computer Engineering Mississippi State University MS 39762 submitted by: Brandon Butler, Phani Kumar, Nivedita Sahasrabudhe, Shivaraj Tenginakai, 1. Abstract The goal of this project is to evaluate the various reconstruction filters used in image processing. This project concentrates on a special class of filters known as the derivative filters. These filters are evaluated in the frequency domain, and both qualitative and quantitative results are obtained. 2. Introduction Images can be considered to be signals in the spatial domain. Volume data, generated during a CT, MRI or Ultrasonic scan, consists of samples of an intensity signal, sampled at discrete points in the spatial domain. In order to reconstruct the imagel, we need intensity values at arbitrary points in the domain. This implies that we need to construct from the discrete sampled intensity values, a continuous intensity function, the reconstruction function. 2.1 Filter Theory Construction of a continuous function or its derivative, from a set of discrete samples involves computation of the weighted average of these samples.The function which provides these weights is called a filter. In general there are two types of filters: Interpolation filters: These filters provide weights only to the sampled values of the signal. Derivative filters: These filters provide weights to the value of derivatives of the signal at the sampled points in addition to the values sampled. In order to derive the reconstruction function, we convolve the sampled signal with the filter. The following derivation shows how to construct filters using convolution and Taylor series (Moller et al. 1996). Let, k , be an integer. t , be the distance, symbol t is used to show the anology with the signals in the time domain. T , be the sampling distance, analogous to the sampling period for signals in the time domain. f(t), be the orignal continuous signal. fk(t),be the discrete signal obtained by sampling the orignal signal,i.e., fk (t)= f (kT). w , be the filter function, which provides the weights. frw , be the reconstructed signal. Then, if we apply convolution we get, (1) Assuming that the orignal signal function f(t) has first (N+1) derivaties, we can expand fk = f (kT) in Taylor series around f. (2) where, . Substituting this Taylor series expansion into Equation(1)and reordering the terms according to the derivative of f(t), we can rewrite Equation (1) as: where the coefficient anw and the remainder rnw are: Since we never use an infinitely long filter, we can define the filter length to be M. This implies that filter w is zero outside the interval [-M,M]. Further, we can substitute in terms of offset ,and the sampling distance T,as: Figure 1. Filter of window - 4, (drawn in red). , where , and . therefore, (3) (4) Finally the Convolution sum of Equation (1) can be expressed as, (5) Which can be approximated to, (6) or, (7) This is the basic filter eqation. It implies that we approximate the orignal signal with a polynomial of order N. We can also see that the error term rwn, is of the order of T(N+1), in other words a (N+1)EF(Error Filter) filter can reconstruct a polynomial of order N. The principal idea is to choose the largest N (so that the error term rwn is minimum), such that all awn evaluate to zero, except for aw0 for interpolation filters, and awm for m-th order derivative filters, 1.e., (8) The class of filters considered here belong to the family of cubic derivative filters (since they are obtained by differentiating cubic interpolation filters). This group of filters is described as: (9) By inserting this filter in Equation(7), and applying the Equation(8), we get different combination of values for the constants in the above filter eqation, and hence we get a family of m-th order derivative filters. The above discussion applies to filters in 1D. However the extension to 3D is quite simple, since the above set of filters belong to the family of separable filters. Hence the 3D filer is given by, (10) 2.2 Evaluation Criteria For evaluation of the class of filters given by Equation(9), we adopt both quantitative and qualitative measures. Quantitative analysis of filter qualities in the frequency domain for intepolation filters was done by Marschner and Lobb (1996) . The spatial evaluation of filter qualities based on the remainder term of the Taylor series, Equation (4), was given by Moller et al. (1997), for both drivative filters and interpolation filters. In this project we try to extend the work of Marschner and Lobb to derivative filters and compare the results with those obtained by Moller et al. Marschner and Lobb, describe three metrics for filter quality, based on: (a) Smoothing: A signal often contains some high frequency oscillations due to noise or due to the Gibb's phenomenon. The removal of these by spatial averaging is termed as smoothing . Though noisy data benefits from some smoothing , in image processing, too much of it causes the image to blur. In volume rendering smoothing leads to loss of fine density structure. The smoothing metric S of a filter w is defined as, where, , is the Nyquest Region. , is the frequency space volume of . (11) (b) Postaliasing: It comes into picture if the reconstruction filter is significantly non-zero at frequencies above the Nyquist frequency, as this causes energy from the alias spectra to "leak" into the reconstruction. The postaliasing metric P is defined as, (12) (c) Ringing: If the signal to be sampled contains discontinuities, then the reconstructed signal will contain high frequency oscillations, or ringing , just before and after the discontinuity.This defect arises as a direct consequence of using a low pass filter to band-limit the signal to be sampled; especially if the low-pass filter has a sharp cut off. The metric O is a measure of the severity of ringing when a filter w is used to bandlimit the unit step function, , (13) Qualitative analysis will be done , by showing the resulting images to a group of people. Finally filters will be ranked based on both qualitative and quantitative analysis. 3. Project Design The various tasks involved in the project design, are given in the Table 1. 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:, Filter module - image is reconstructed from the given database by this module. Evaluation module - reconstructs the image is evaluated using methods outlined in this module. Rendering module - image is rendered using standard rendering algorithms, such as ray tracing, in this module. Display module - provides the user interface. Figure 2. The Context Diagram Table 1: Tasks and Schedule Task Number Task Deadline T1 Selection of filters: For this task we choose the existing derivative filters, of cubic family. 29 September T2 Derivation of Fourier Transform of filters: This is needed for evaluation metrics , equations 11,12 and 13. 5 October T3 Selection of data bases: For evaluation for filters we choose both real databases, (obtained from CT,MRI and Ultrasonic scans) and synthetic databases. The databases are in form of 255 grayscale value at each point in the space. 28 September T4 Implementation of filter codes: Code implemented in MATLAB, is available from Dr.Torsten Mueller and this will be adapted. 10 October T5 Implementation of evaluation metrics: This code will be implemented in C. 15 October T5 Volume Rendering Code: This code is available form Drs. Klaus Mueller and Raghu Machiraju. - T6 User Interface Implementation: This will allow the user to select a image database and pass it through various filters and view their performance. The user will also be able to give qualitatively analysis of various filters. 20 October T7 Paper writing and Presentation 30 October 4. Acknowledgment We are extremely thankful to Dr. Raghu Machiraju for helping us in collecting all the material. We are also thankful to Drs. Torsten Moller and Klaus Moller for allowing us to use their codes. REFERENCES Marschner S.R., and and Lobb R.J. 1994. An evaluation of reconstruction filters for volume rendering. In the proceedings of Visualisation' 94, October, 1994. 100-107. IEEE CS Press. Moller, Torsten, Raghu Machiraju, Klaus Mueller, and Roni Yagel. 1996. Classification and Local error estimation of interpolation and derivative filters for volume rendering. In Proceedings of 1996 Symp. Volume Visualization, October,1996. 71-78. Moller, Torsten, Raghu Machiraju, Klaus Mueller and Roni Yagel. 1997. Evaluation and design of filters using a Taylor series expansion. 1997. IEEE Transaction on Visualisaion and Computer graphics 3(2): 184-199.