Graphics Reference
In-Depth Information
This is one form of the
Shannon sampling theorem
[Sha49] or simply
sam-
pling theorem.
We can apply this to real-valued functions, whose Fourier trans-
forms are even functions. This means that
c
−
1
=
c
1
, and
c
−
2
=
c
2
, etc. So, of
the 2
k
0
+
1 degrees of freedom, we have only
k
0
+
1 degrees of freedom for a
real-valued function. In this case, the sampling theorem says:
Suppose that
f
and
g
are real-valued functions on
[
1
2
,
2
]
, and
−
x
0
,
...
,
x
k
0
are
k
0
+
1 evenly spaced points in that interval, for example,
1
2
+
j
k
0
+
1
,
x
j
=
−
(18.51)
,
k
0
, and y
j
=
g
(
x
j
)
.
If
y
j
=
y
j
for all
j
, then
f
and
g
are equal, that is, a function band-
limited at
k
0
is completely determined by
k
0
+
1 equally spaced samples.
Furthermore, given any set of values
and y
j
=
f
(
x
j
)
for j
=
0,
...
k
0
j
=
0
, there is a unique function,
f
, band-limited at
k
0
, with
f
(
x
j
)=
y
j
for every
j
.
{
y
j
}
The sampling theorem was proved by Shannon in 1949, but Borel stated part
of it as early as 1897. Part of it was also suggested by Nyquist in 1928. Sev-
eral others appear to have developed all or part of it independently. Meijer-
ing [Mei02] gives some of the history.
Peeking ahead, this theorem is important because we generally build an image
by taking equispaced samples of some function
f
, and we hope that the image
really “captures” whatever information is in
f
. The sampling theorem says that
if f
is band-limited at some frequency, and
if
we take an appropriate number of
samples for that frequency, then we can reconstruct
f
from the samples, that is,
the image is a faithful representation of the function
f
.
This should make you ask, “Well, what happens if I take
k
0
samples of a real-
valued function that's
not
band-limited at
k
0
? What band-limited function do those
correspond to?” We'll address this soon.
1
2
,
2
]
, consider the three points
Inline Exercise 18.4:
On the interval
H
=(
−
3
, 0, and
3
.
(a) What real-valued function,
f
1
, band-limited at
k
0
=
1, has values 1, 0, and
0 at these points? What functions
f
2
and
f
3
correspond to value sets 0, 1, 0 and
0, 0, 1? (You may want to use a computer algebra system to solve these parts.)
(b) Now find a band-limited function whose values at the three points are
−
1
−
1
1
2
.
(c) What are the samples of
x
2
,1,
−
→
cos(
4
π
x
)
at these three points? Does this
contradict the sampling theorem?
The sampling theorem can be read in reverse: If I'm taking samples with a
spacing
h
between them, what's the highest frequency I can tolerate in my signal
if I want to be able to reconstruct it from the samples? The answer is that the
wavelength of the signal must be greater than twice
h
. The frequency, known as
the
Nyquist frequency,
is therefore
π/
h
.
Inline Exercise 18.5:
Suppose you prefer the convention that
x
sin(
x
)
has
frequency 1. What's the Nyquist frequency if the sample spacing is
h
?
→
