Contents

Bitmap Representation of Terrain and Elevation Data Basic Image Processing and Elevation Smoothing Smoothing Using Curved Surfaces

Basic Image Processing and Elevation Smoothing

Many image processing operations can be modeled as a linear system:

where f(x, y) and h(x, y) are the input and output images, respectively, and g(x, y) is the system's impulse response. To put it another way, g(x, y) is the operation upon f(x, y) that creates h(x, y). For such a system, the output h(x, y) is the convolution of f(x, y) with the impulse response g(x, y), defined in discrete terms, for an NxM image, as:

If f and h are images, convolution becomes the computation of weighted sums of the image pixels. This computation is performed using an arbitrarily-sized square table of values called a convolution mask. This computation is what performs the actual filtering.

One of the simplest filters is implemented by a local averaging operation where the value of each pixel is replaced by the average of all the values in its local neighborhood, as determined by the size of our convolution mask. For example, taking a 3x3 neighborhood about the pixel (i, j) yields:

If g[i, j] = 1/9 for every [i, j] in the convolution mask, the convolution operation reduces to a local averaging of the 3x3 grid of pixels centered on pixel [i, j]. Notice that for the 9 pixels involved in the operation, the sum of the weights is equal to 1 (9x1/9 = 1). When an NxN convolution mask is used as an averaging filter, the size of N controls the amount of filtering. As N becomes larger, the image noise is reduced, but you also lose more image detail. So there's a trade-off in choosing a particular size N, and choosing the size of your convolution mask will depend on the amount of filtering you need and level of detail your final image requires. An example of an average filter applied to a height field is shown in Figure 3b.

Figure 3b. Scaled height data, filtered using the averaging filter.

A Gaussian filter is similar to the averaging filter. In the Gaussian filter, the values in the mask are chosen according to the shape of a Gaussian function. For reference, a zero-mean Gaussian function in one dimension is:

where the Gaussian spread parameter determines the width of the Gaussian. For image processing, a two-dimensional zero-mean discrete Gaussian function,

is used as a smoothing filter. The Gaussian filter has a few properties that make it particularly useful for smoothing purposes.

First, the Gaussian function is rotationally symmetric. In other words, the function does not favor any particular direction when it smooths, which is particularly useful when the areas needing smoothing are oriented in an arbitrary direction (not known in advance), and there is no reason to smooth in any specific direction.

Second, the Gaussian function has a single lobe, which means that the Gaussian filter replaces each pixel with a weighted average of the neighboring pixels around it (like the averaging filter), such that a pixel's weight decreases monotonically with distance from the central pixel.

The filter centers on one pixel (i, j). This pixel is modified by: 1) Multiplying each surrounding pixel, including the center pixel by its respective filter weight, and adding the resulting products together. 2) Dividing the sum from step one by the sum of the filter weights. This is the new value for pixel (i,j). This allows local features in the height bitmap to remain in the filtered image. Finally, the width (and thus the degree of smoothing) is linked directly to s, so that as s increases, so does the degree of smoothing. One can control this parameter to achieve a balance between the amount of smoothing and blurring in the final image.

There are a couple of techniques that one can employ to determine what kind of Gaussian filter to use. If the filter is being calculated directly from the discrete Gaussian distribution

where c is a normalizing constant, the equation can be rewritten as

Once a value for s2 is chosen, the function can be evaluated over the NxN area desired for the mask. For example, choosing s = 2 and N = 7, the above equation yields the grid of values in Table 1. However, if integer values are desired inside the mask, you can divide every value inside the mask by the value at one of the corners in the array (the smallest value in the mask). With this completed, and assuming the values are rounded appropriately, a table is created like that shown in Table 2.

Table 1. Grid of values. Click on the table for a larger version.

 

Table 2. Resulting table of values. Click on the table for a larger version.

Notice that the sum of all the weights contained in the above Gaussian masks do not equal one. Thus, the result given from convolving a given section of the image by the mask should be divided by the sum of the weights contained in the mask. This ensures that the mask does not affect regions of uniform intensity. An example of the Gaussian filter shown above applied to a height field is seen in Figure 3c.

Figure 3c. Scaled height data, filtered using a Gaussian filter.

Another useful aspect of the Gaussian function is the fact that it is a separable function. In other words, a two-dimensional Gaussian convolution can be obtained by convolving the bitmap with a one-dimensional Gaussian and then convolving the result with the same one-dimensional Gaussian-oriented orthogonal to the Gaussian used in the first step. Therefore, another way to create a Gaussian filter is to approximate it by using the coefficients of the binomial expansion (you might remember the binomial series from calculus, where it was used to estimate integrals and roots of numbers):

In other words, use row n from Pascal's triangle (Figure 4) as the values for your Gaussian filter. For example, a five-point approximation of a Gaussian filter is:

1 4 6 4 1

Figure 4. Pascal's triangle. (Click on the image for a larger version). At the tip is the number 1, which makes up the zeroth row. The first row (1 & 1) contains two 1s, both formed by adding the two numbers above them to the left and the right, in this case 1 and 0 (all numbers outside the triangle are zeros). Do the same to create the second row: 0 + 1 = 1; 1 + 1 = 2; 1 + 0 = 1. And the third: 0 + 1 = 1; 1 + 2 = 3; 2 + 1 = 3; 1 + 0 = 1. In this way, the rows of the triangle go on infinitely. A number in the triangle can also be found by n Choose r (nCr) where n is the number of the row and r is the element in that row. For example, in Row 3, 1 is the zeroth element, 3 is element number 1, the next 3 is the second element, and the last 1 is the third element. The formula for nCr is shown below. The ! symbol means factorial, or the preceding number multiplied by all the positive integers that are smaller than the number. 5! = 5 x 4 x 3 x 2 x 1 = 120.

This corresponds to the fifth row in Pascal's triangle, as shown in Figure 4. This method works for filter sizes up to around n = 10. For larger filters, the binomial coefficients become too large for most images. Of course, if floating-point values can be used, you could always normalize the row by the largest value.

Depending on how much you scaled the original height bitmap, the above smoothing methods should produce satisfactory results. However, for higher amounts of scaling, the amount of smoothing needed (provided by either of the methods above) might be too high to produce a smooth height bitmap (depending on what kind of terrain model will be satisfactory). In doing so, there is a trade-off between losing local detail from the original height bitmap (since smoothing reduces noise by spreading it over a larger area, making it more difuse) and generating more terrain data from a bitmap of given size.

________________________________________________________

Smoothing Using Curved Surfaces