CS 788H S01 Project - Semi-automatic Generation of Transfer Functions for Direct Volume Rendering
Aravind Krishnaswamy
For my final project I have implemented a portion of the algorithm presented in "Semi-automatic Generation of Transfer Functions for Direct Volume Rendering" by Gordon Kindlmann and James Durkin. The algorithm involves the automatic generation of opacity transfer functions based on the relationship between data values, their first directional derivatives and their second directional derivatives.
| Introduction | Gradient Estimators | IntelliVIS(UI) | Problems | Results | Conclusions | Future Work | Update |
Since this project uses the gradient heavily, I think perhaps a little discussion and analysis of a few gradient estimators is in order. Click Here
Assumptions
As detailed in the paper I make the following assumptions about the boundary:
Also as detailed in the paper I assume that the materials on either side of the boundary are of a constant volume value. As I progressed in implementing the algorithm I found another assumption that had to be made was that the sizes of the boundaries would be the same over the entire volume.
In order to have a user interface for my project I extended IntelliVIS, my visualization program for Win32.
The tools tabs allows the user to manipulate various rendering aspects. From here the user can select which transfer function to edit as well which ones to display on top of the histogram window (seen below). By clicking on the 'Create Hist. Vol.' button the program will compute the histogram value and the values of p(v) the position function.
From the volume histogram window the user manipulates the control points of the various transfer functions, including the Boundary Emphasis Function (displayed as purple) essential to this algorithm.
The main render window shows a render with the currently selected parameters. The UI controls allow the user to set such things as interactive rendering and down sampling during interactive renderings.
Computing the second directional derivative
There were three algorithms presented in the paper for computing the second directional derivative. I chose to implement the 'gradient of the gradient magnitude' method. The second directional derivative is then described as:
The biggest problem I found with Kindlmann's paper was the glossing over of the part involving the range of values to select for the histogram axis (in particular the f' and f'') axis. With 'real world' data sets that have a lot of noise including the full range of second derivative values shatters any hope of the algorithm correctly identifying boundaries. In his implementation and his thesis Kindlmann suggests constructing a 1D histogram of the f' and f'' values and finding a value to clip at that results in x% of the values being discarded.
I played around with applying low pass filters to eliminate the high frequency second derivative information since that is indicative of a lot of noise. However I found this wasn't totally sufficient, in real world data sets I still needed to eliminate a good majority of the outliers in the second derivative information.
I have primarily tested the algorithm with ideal data sets due to issues with noisy datasets. The histogram volumes generated from these datasets was done with the Sobel 3D gradient estimator with a nearest neighbor interpolator for the values. Since these ideal datasets contain no noise, there was no need to change the range of values for the first and second derivatives. The test datasets are broken down as follows:
Ideal sphere with linear boundaries
In this dataset the sphere's inner radius is 30mm while the other radius is 40mm. The value at 35mm is 128 with a linear scale up to +-35mm on either side. The data set is a 128x128x128 8-bit volume.
These are the summed voxel projections comparing f' with f and f'' with f.
 |
 |
| f' vs. f | f'' vs.f |
From these summed voxel projects we can see that there are boundaries and we also see that the boundaries are linear (straight lines in the f' vs. f plot)
The following opacity transfer function is generated with a boundary emphasis function that is discontinuous (i.e., values in the boundary get assigned full opacity). As we can see those values near the edges get full opacity while other values in the volume get zero
Setting the boundary emphasis function to be linear we get the following opacity function.
This opacity function now fully highlights those values that are the center of a boundary while bringing those values that are in the middle of the boundary down. Thus we see that the values that are right at the boundary get the highest opacity values.
Ideal sphere with gaussian boundaries
In this dataset the sphere's inner radius is 8mm while the other radius is 248mm. The value at 35mm is 128 with the values dropping and raising at each side with a gaussian distribution (with a standard deviation of 0.5). The data set is a 128x128x128 8-bit volume.
These are the summed voxel projections comparing f' with f and f'' with f.
 |
 |
| f' vs. f | f'' vs.f |
From the f' vs. f scatter plot we see the two boundaries, we can also see they look something like the first derivative of a gaussian.
Again with a boundary emphasis function that brings all values in the boundary out we have only the values on the boundary being assigned opacity values. If we change our boundary emphasis function to linearly scale the boundary values as to create "fuzzy" boundaries we get the following opacity function:
Where we can see the centers of the two boundaries getting the highest opacity values.
Fake data set
This fake data set has multiple objects that all have the property that their boundaries are sharp and discontinuous.
These are the summed voxel projections comparing f' with f and f'' with f.
 |
 |
| f' vs. f | f'' vs. f |
From the f' vs. f plot we can see several discontinuous boundaries at various data values.
Now again with a boundary emphasis function that makes all values on a boundary opaque we get the following opacity function.
Its worth noting that though all the objects are found, the algorithm seems to be confused with the continuous change in data values, assigning boundaries as soon as the data value changes too much. If we change the boundary emphasis function such as opacity is applied linearly in relation to distance from the boundary we see some of this confusion diminish and the actual boundary values retain their full opacity level.
Visible Human CT Head
Out of a morbid sense of curiosity I decided to see how the algorithm would fare with a 'real world' data set and all the noise that comes with it. Due to the fact that the data is noisy I had to fiddle around with the range of second derivative values to use. I found that with this dataset I had to eliminate 95% of the outliers in the second derivative information to produce something even remotely worthwhile. I also had to fiddle with the boundary emphasis function (to put it mildly).
Rather than hastily discard 95% of the second derivative values I tried to run the second derivative values through a low-pass filter. I tried a simple box filter as well other interesting varieties, but to no avail. Even with filtering I needed to eliminate a good portion of the outliers.
 |
 |
| f' vs. f | f'' vs. f |
From the f' vs. f plot we can see that the algorithm has basically found two primary boundaries, which I will assume is the skin and the skull.
Note that the R, G, and B transfer functions were specified entirely by hand.
Bell Brain
In hopes that MRI data might provide better surfaces I tried out the Bell Brain data set. Without any filtering of f'' I was not able to find good boundaries. However applying a simple box filter then clipping the outliers did allow me to bring out almost exactly the major surface, the skin.
 |
 |
| f' vs. f | f'' vs. f |
These plots are somewhat confusing. We can see that there are several possible boundaries in the image and can also see that one of these boundaries is inside the other. Now its worth noting that with no fiddling the algorithm identifies two primary boundaries one near the low end ~0.2 boundary value and another near the high end (the brain). The problem is that there may be boundaries in the volume corresponding to low volume values but this is also where a significant portion of the noise is.
I am somewhat disappointed that I was not able to get the algorithm to better find boundaries in 'real world' datasets without so much user intervention. This leads me to one of three conclusions:
None of these conclusions are very appealing though from a sense of pride in my work (and the fact the algorithm works with fake data sets) I am forced to favor the first two rather than the latter.
In both Kindlmann's thesis and his reference implementation he has a few suggestions for improving the algorithm:
January 12, 2005
Thanks to Andrew Winter, who writes "[...] eliminating the upper 0.5 percentile of first derivative values and the upper and lower 1.5 percentile of second derivative values does the trick for real-world data. This works nicely for me. I suspect when you say you eliminate 95% of second derivative values, you're eliminating 95% of the range covered by the values. You will probably find that 95% of values are condensed into a very small range - this is what you need to represent in your histogram volume."
I think Andrew is correct is his observation and agree with him.
Also, I realize the scatterplot look a bit strange, but this is because of the manner in which they were generated (which if I recall was in a really cheesy manner).
When I note that "Kindlmann was very careful in his test data sets in order to generate the images he manages to generate" I really didn't want to imply that he specifically chose datasets that generated nice images but that he perhaps spent more than just a passing amount of time in tweaking his settings.