Page 129 -

108 3 Image processing

(a) (b) (c) (d)

(e) (f) (g) (h)

Figure 3.18 Median and bilateral filtering: (a) original image with Gaussian noise; (b) Gaussian filtered; (c)
median filtered; (d) bilaterally filtered; (e) original image with shot noise; (f) Gaussian filtered; (g) median filtered;
(h) bilaterally filtered. Note that the bilateral filter fails to remove the shot noise because the noisy pixels are too
different from their neighbors.

3.3 More neighborhood operators

As we have just seen, linear filters can perform a wide variety of image transformations.
However non-linear filters, such as edge-preserving median or bilateral filters, can sometimes
perform even better. Other examples of neighborhood operators include morphological oper-
ators that operate on binary images, as well as semi-global operators that compute distance
transforms and find connected components in binary images (Figure 3.11f–h).

3.3.1 Non-linear filtering
The filters we have looked at so far have all been linear, i.e., their response to a sum of two
signals is the same as the sum of the individual responses. This is equivalent to saying that
each output pixel is a weighted summation of some number of input pixels (3.19). Linear
filters are easier to compose and are amenable to frequency response analysis (Section 3.4).
In many cases, however, better performance can be obtained by using a non-linear com-
bination of neighboring pixels. Consider for example the image in Figure 3.18e, where the
noise, rather than being Gaussian, is shot noise, i.e., it occasionally has very large values. In
this case, regular blurring with a Gaussian filter fails to remove the noisy pixels and instead
turns them into softer (but still visible) spots (Figure 3.18f).

Median filtering

A better filter to use in this case is the median filter, which selects the median value from each
pixel’s neighborhood (Figure 3.19a). Median values can be computed in expected linear time
using a randomized select algorithm (Cormen 2001) and incremental variants have also been