Abstract[1]   |   Pictures[2]   |   3D Convolution[3]   |   Wavelets[4]   |   Morphology[5]   |   Results[6]   |   Papers[7]


Hardware Accelerated Filters

[7]Abstract

Many volume analysis operations used for image enhancement, data processing, or feature extraction use three dimensional convolutions, morphological operators, or wavelet analysis. These three categories of filters are usually performed by the main processor, which is usually bound by main memory bandwidth due to the huge data sets nowadays.

Graphics memory, on the other hand, has much higher bandwidth and can be accessed in a more parallel manner. Additionally, the cache strategies used in these architectures usually suite much more the way memory has to be addressed for linear filters. By exploiting these hardware systems we are able to accelerate time consuming filtering steps.

[7]Pictures

[8]   [9]   [10]   [11]   [12]
ISO surface of a 3D tomography  filtered with gauss filter  2D head data set  filtered with gauss filter  filtered with second derivative of gauss filter 
[13]   [14]   [15]   [16]   [17]
Haar Wavelet decomposition using the VMV hardware method  Haar Wavelet decomposition using the VisSym hardware method  One bit differences of software vs. hardware decomposition  One bit differences of hardware reconstructed image to original  One bit differences of decomposition on another hardware 
[18]   [19]   [20]   [21]   [22]
The 'opened' data set  The 'closed' data set  Differences between original and opened data set  Differences between original and closed data set  Explanation of morphological operators 
Figure 1: Several examples

[22]3D Convolution

For most interactive 3D visualization techniques the data set has to be loaded to some dedicated texture memory located in the graphics subsystem. In order to be able to interactively filter these data sets, algorithms working directly on the graphics hardware are of additional benefit, because the data set does not have to be reloaded after filtering.

Most linear filters can be decomposed into a seperable convolution. Current graphics hardware is able to perform 2D convolutions. In order to extend this filter type to 3D, we have to decompose the 3D convolution into a 2D one perpendicular to the z axis, and into a 1D convolution along the z axis. The convolution itself is performed in the frame buffer while slices of the volume are read back into texture memory.

[22]Wavelet Analysis

Wavelets are a widely used multiresolution analysis. Figure 2 depicts the simplest wavelet of all, the so-called Haar wavelet. Using this mother wavelet, a data set can be decomposed lossless into a set of wavelet coefficients by performing a wavelet decomposition. The reverse step - recreating the data set from the coefficients - is called reconstruction.

Figure 2: The Haar Wavelet


Both operators, decomposition and reconstruction, can benefit greatly from the high memory bandwidth of modern graphics cards. However, the OpenGL pipeline does not completely fit the necessary operator sequence. Thus the invocation sequence of OpenGL commands with their according parameters is - while not time consuming - rather complex. The presented papers discuss in detail these aspects.

During a typical decomposition step the data set has to be filtered several times. Due to the lack of floating point data types in the graphics hardware, accuracy is quite an issue. However, wavelets seem to be relatively stable in that aspect.

[22]Morphological Operators

The disadvantage of wavelet transformation and other filters, that are based on linear combinations of the input data, is the fact that the analyzed structures become distorted. This can be seen especially on lower frequency scales, accomplished by large filter kernels. One class of special non-linear filters that do not flatten the contours of the original data set are the morphological operators. This filter type computes the minimum respectively maximum of pixel values within a given scope. Before the actual maxima are calculated, the values of the so-called structuring element are added to the pixel values.

As one can see in Figure~3 for binary operators, the erosion operator cuts away parts of the boundary of the analyzed image X. The amount that is removed is defined by the structuring element Y, which is typically much smaller than the input image. The dilation operator on the other hand enlarges the input data. By combining these basic operators to more complex ones we get the so-called opening and closing operators. The opening operator breaks up small bridges between connected regions while the closing operator tends to fill small gaps in solid components. Morphological operators on gray scale images are defined accordingly.

Figure 3: Binary morphological operators


As usual we assume that the given data set is already stored in texture memory. When filtering a volume data set with a so-called diamond shaped morphological operator, we sweep over the volume in three passes. In the first two passes we perform the filtering along the x and y axes. These steps only access data from within one single texture, which contains data perpendicular to the z axis, as defined in the previous section. In the third pass we filter along the z axis. As the data along this axis is spread in multiple textures, triangles textured with several different images have to be rendered.

[22]Results

By using standard OpenGL hardware the time needed for typical filtering applications can be significantly reduced, as it is shown in Table 1 to 3.

Filter Size 2³3³5³7³
head (128²x54) 0.33 / 0.72 s0.33 / 1.02 s0.33 / 1.56 s0.48 / 2.0 s
angio (256³) 2.5 / 6.0 s2.5 / 8.7 s2.5 / 14.7 s3.7 / 21.3 s
Table 1: Times for convolving 3D data sets, hardware vs. software


Image size 32²64²128²256²512²
Decomposition 0.65 / 0.5 s1.4 / 2.0 s4.5 / 7.8 s16 / 31 s62 / 150 s
Reconstruction 1.4 / 0.8 s2.0 / 3.6 s5.0 / 14 s18 / 55 s66 / 240 s
Table 2: Times for haar wavelet decomposition and reconstruction, hardware vs. software


Filter size 3³7³15³25³
data_1 (256³) 5.7 / 27.3 s10.1 / 32.7 s18.8 / 46.3 s29.5 / 90.6 s
data_2 (512²x154) 11.8 / 67.7 s19.5 / 101.5 s34.3 / 172.3 s54.5 / 251.2 s
Table 3: Times for morphological operators, hardware vs. software


[22]Papers and Technical Reports

Matthias Hopf[39] <Matthias.Hopf@informatik.uni-stuttgart.de>[40]

      University of Stuttgart, Institute for Computer Science,
Visualization and Interactive Systems Group

http://www.vis.uni-stuttgart.de/eng/research/fields/current/hwfilters/index.html