## Tools |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Certain
tools are central to the processing of digital images. These include
mathematical tools such as convolution, Fourier analysis,
and statistical descriptions, and manipulative tools such
as chain codes and run codes. We will
present these tools without any specific motivation. The motivation will
follow in later sections. ##
Convolution
There are several possible notations to indicate the convolution of two (multi-dimensional) signals to produce an output signal. The most common are:
We
shall use the first form, In
2D continuous space:
In
2D discrete space:
## Properties of Convolution
There are a number of important mathematical properties associated with convolution. *
Convolution is
*
Convolution is
*
Convolution is
where
##
Fourier Transforms
The Fourier transform produces another representation of a signal, specifically a representation as a weighted sum of complex exponentials. Because of Euler's formula:
where
The
inverse Fourier transform goes from the frequency domain back to the
spatial domain.
The
Fourier transform is a unique and invertible operation so that:
The
specific formulas for transforming back and forth between the spatial
domain and the frequency domain are given below. In
2D continuous space:
In
2D discrete space:
## Properties of Fourier Transforms
There
are a variety of properties associated with the Fourier transform and
the inverse Fourier transform. The following are some of the most
relevant for digital image processing. *
The Fourier transform is, in general, a complex function of the real
frequency variables. As such the transform can be written in terms of
its magnitude and phase.
*
A 2D signal can also be complex and thus written in terms of its
magnitude and phase.
*
If a 2D signal is real, then the Fourier transform has certain
symmetries.
The
symbol (*) indicates complex conjugation. For real signals eq. leads
directly to:
*
If a 2D signal is real and even, then the Fourier transform is real and
even.
*
The Fourier and the inverse Fourier transforms are linear operations.
where
w are arbitrary, complex constants. _{2}*
The Fourier transform in discrete space,
*
The energy,
This
"signal energy" is not to be confused with the physical energy
in the phenomenon that produced the signal. If, for example, the value *
Given three, multi-dimensional signals
In
words, convolution in the spatial domain is equivalent to multiplication
in the Fourier (frequency) domain and vice-versa. This is a central
result which provides not only a methodology for the implementation of a
convolution but also insight into how two signals interact with each
other--under convolution--to produce a third signal. We shall make
extensive use of this result later. *
If a two-dimensional signal
*
If a two-dimensional signal
*
If a two-dimensional signal
## Importance of phase and magnitude
Equation indicates that the
Fourier transform of an image can be complex. This is illustrated below
in Figures 4a-c. Figure 4a shows the original image
Both
the magnitude and the phase functions are necessary for the complete
reconstruction of an image from its Fourier transform. Figure 5a shows
what happens when Figure 4a is restored solely on the basis of the
magnitude information and Figure 5b shows what happens when Figure 4a is
restored solely on the basis of the phase information.
Neither
the magnitude information nor the phase information is sufficient to
restore the image. The magnitude-only image (Figure 5a) is
unrecognizable and has severe dynamic range problems. The phase-only
image (Figure 5b) is barely recognizable, that is, severely degraded in
quality. ## Circularly symmetric signals
An arbitrary 2D signal
where
The
Fourier transform
) and then, for a circularly symmetric signal,
rewritten as a ankel transform:
where
The
inverse
The
Fourier transform of a circularly symmetric 2D signal is a function of
only the radial frequency,
, has vanished. Further, if a(x,y)
= a(r) is real, then it is automatically even due to the
circular symmetry. According to equation , A(
_{r})
will then be real and even. ## Examples of 2D signals and transforms
Table 4 shows some basic and
useful signals and their 2D Fourier transforms. In using the table
entries in the remainder of this chapter we will refer to a spatial
domain term as the r as in eq. .
## Statistics
In
image processing it is quite common to use simple statistical
descriptions of images and sub-images. The notion of a statistic is
intimately connected to the concept of a probability distribution,
generally the distribution of signal amplitudes. For a given
region--which could conceivably be an entire image--we can define the
probability ## Probability distribution function of the brightnesses
The probability distribution
function, ## Probability density function of the brightnesses
The probability that a
brightness in a region falls between
Because of the monotonic,
non-decreasing character of
For
an image with quantized (integer) brightness amplitudes, the
interpretation of
The
brightness probability
(a) (b)
Both
the distribution function and the histogram as measured from a region
are a statistical description of that region. It must be emphasized that
both ## Average
The average brightness of a
region is defined as the
pixels
within a region (
)
is given by:
Alternatively,
we can use a formulation based upon the (unnormalized) brightness
histogram,
The
average brightness, u, of the underlying brightness probability
distribution. _{a}## Standard deviation
The
pixels
is called the sample standard deviation and is
given by:
Using
the histogram formulation gives:
The
standard deviation,
of the underlying brightness probability distribution. _{a}## Coefficient-of-variation
The dimensionless
## Percentiles
The percentile,
or equivalently
Three
special cases are frequently used in digital image processing. *
0% the *
50% the *
100% the All
three of these values can be determined from Figure 6a. ## Mode
The mode of the distribution is the most frequent brightness value. There is no guarantee that a mode exists or that it is unique. ## SignaltoNoise ratio
The signal-to-noise ratio, a
<= _{min}a <= a, then the _{max}SNR is
defined as:
If
the signal is not bounded but has a statistical distribution then two
other definitions are known:
where
s are defined above. _{a}The
various statistics are given in Table 5 for the image and the region
shown in Figure 7.
A
a,
for the image (=241-56) to calculate a global _{min}SNR (=33.3 dB). The
underlying assumptions are that 1) the signal is approximately constant
in that region and the variation in the region is therefore due to
noise, and, 2) that the noise is the same over the entire image with a
standard deviation given by s = _{n}s_{
}.
## Contour Representations
When
dealing with a region or object, several compact representations are
available that can facilitate manipulation of and measurements on the
object. In each case we assume that we begin with an image
representation of the object as shown in Figure 8a,b. Several techniques
exist to represent the region or object by describing its contour. ## Chain code
This representation is based upon the work of Freeman . We follow the contour in a clockwise manner and keep track of the directions as we go from one contour pixel to the next. For the standard implementation of the chain code we consider a contour pixel to be an object pixel that has a background (non-object) pixel as one or more of its 4-connected neighbors. See Figures 3a and 8c. The
codes associated with eight possible directions are the chain codes and,
with
## Chain code properties
* Even codes {0,2,4,6} correspond to horizontal and vertical directions; odd codes {1,3,5,7} correspond to the diagonal directions. *
Each code can be considered as the angular direction, in multiples of 45 *
The absolute coordinates [ *
When there is a change between two consecutive chain codes, then the
contour has changed direction. This point is defined as a ## Crack code
An alternative to the chain code for contour encoding is to use neither the contour pixels associated with the object nor the contour pixels associated with background but rather the line, the "crack", in between. This is illustrated with an enlargement of a portion of Figure 8 in Figure 9. The
"crack" code can be viewed as a chain code with four possible
directions instead of eight.
The
chain code for the enlarged section of Figure 9b, from top to bottom, is
{5,6,7,7,0}. The crack code is {3,2,3,3,0,3,0,0}. ## Run codes
A third representation is based on coding the consecutive pixels along a row--a run--that belong to an object by giving the starting position of the run and the ending position of the run. Such runs are illustrated in Figure 8d. There are a number of alternatives for the precise definition of the positions. Which alternative should be used depends upon the application and thus will not be discussed here. |