Back top previously visited page (this function is disabled)Back to homepage (P)Back to previous page (E)Jump to next page (V)Display terms (this function is disabled)List of terms (this function is disabled)Print this page (this function is disabled)Jump to sitemap (D)Search in current page (this function is disabled)Help (S)

Building Spatial Databases – Theory / Digital filters

Learners guide

Summary

As there are many kinds of digital filters, only some popular filters will be shown in this chapter, especially those which are working in the time domain.

Requirement

To fill in the self-test successfully

Digital filters

Convolution filters

Let f1 (t) be a convolution function and f2 (t) be the kernel. By convoluting the values in the kernel to time functions, which is the convoluted value at t time, this is how convolution or linear filters operate.

As for two-dimensional cases, for example a digital image, the given formula will be changed as:

Figure 62. A square impulse is the transfer function of the low-pass filter within a given range (for simplicity we are using a one-dimensional time function).

Values within the kernel determine the characteristics of the filter's transfer function, which are actually the inverse Fourier transformation with discrete values on transfer function.

Figure 63. Converse Fourier transformation of the square impulse function within a sinc time interval.

For example let us take a closer look at a low-pass filter with f_f upper bound frequency. The transfer function is shown in Figure 62 and its converse Fourier transformation shown in Figure 63 with respectively sampled kernel data coefficients. Applying convolution on the given kernel data will result convolution filters. The transform characteristic depends on the kernel data (which is the transform function on given frequency interval). In two-dimensional data like a digital image the kernel is a 2D sinc function described in Figure 64. Figure 65 describes the movement of the kernel over a digital image.

Figure 64. A two-dimensional sinc function describing an anti-aliasing filter's kernel based on sampled data.

Figure 65. Magnified kernel moving across a LANDSAT image.

Back to table of contents (J)

Separable filters

By altering the shape of the kernel to a special form, the calculation time of convolution may increase rapidly. Let us split up a "w" kernel matrix into a product of a column and a row vector, namely w(i,j)=u(i) x v(j),), then the convolution of image with u and then with v:

resulting

Box filter

It is a special kernel-based filter, where kernel data are having the same value, namely the pixel values under the kernel will be averaged. The result of a box filter is a smoothened image. Applying the filter by itself does not give good results, however combining with other filters will be a very effective tool. Due to its simplicity, it is quite a popular filter, despite its unfavourable effect on the spectrum. If you think about it thoroughly, convolution has been carried out by a square function on a time interval with a sinc function on a frequency range as a transform function, where the upper limit frequency can be interpreted.

Gauss filter

Values inside a Gauss filter kernel are the two dimensional Gauss distribution values. Gauss distribution can be calculated as:

We will receive a sigma distributive Gauss curve with expected value 0, from which the kernel can be calculated by applying data sampling on G function over the grid points.

Therefore, the Gauss filter is separable, and the u and v vectors are calculated:

By applying the second power on values of the bell-shaped curve, we do not need to multiply during convolution, but bit shifting can be applied. This is a faster implementation for the Gauss filter. Consequently, u and v vectors change as the following:

As seen, the Gauss filter has a smoothening characteristic. The degree of smoothness greatly depends on the magnitude of distribution. However, with high distribution values, the kernel size has to be increased accordingly. Gauss filters are not really useful by themselves, they should be combined with other algorithms like Canny edge detection. Its transform method is not the best, although it is still better than that of a box filter. Chunk methods are usually used by cutting the length of the up-bound kernel, therefore improving run time qualities. (Do not forget that a sinc function has been sampled in this case).

Figure 66. From left to right: Original image. A 3x3 sized kernel, Gauss filter with sigma=1.0. Filtered image with 7x7 kernel box-filter. Filtered image with 7x7 kernel Gauss filter by sigma 2.0.

One of its disadvantages is that edges are blurred away by losing their contrasts on upper-bound frequency methods. It is not surprising if we think of the fact that high frequency values have been removed from the spectrum and that the edges are represented by high frequency values.

The physical size of images can be reduced (by half the size). The algorithm: apply the Gauss filter on the original image, after that remove every second row and columns, and the result is a Gauss pyramid. A Gauss pyramid can be used at texture detection applications, as the algorithm emphasizes heterogeneous parts of the image by subtracting the images above each other.

Non-separable filters

Non-separable filters are those whose kernel matrix cannot be defined by the product of two vectors. We have to apply summation plays in the convolution formula in these cases.

Back to table of contents (J)

Új Széchenyi terv
A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszirozásával valósul meg.

A Társadalominformatika: moduláris tananyagok, interdiszciplináris tartalom- és tudásmenedzsment rendszerek fejlesztése az Európai Unió támogatásával, az Európai Szociális Alap társfinanszírozásával, az ELTE TÁMOP 4.1.2.A/1-11/1-2011-0056 projekt keretében valósult meg.
Generated with ELTESCORM framework