Both sounds and images can be considered as signals, in one or
two dimensions, respectively. Sound can be described as a
fluctuation of the acoustic pressure in time, while images are
spatial distributions of values of luminance or color, the
latter being described in its RGB or HSB components. Any
signal, in order to be processed by numerical computing
devices, have to be reduced to a sequence of discrete
samples, and each sample must be
represented using a finite number of bits. The first operation
is called sampling, and the second operation is
called quantization of the domain of real
numbers.
1-D: Sounds
Sampling is, for one-dimensional signals, the operation that
transforms a continuous-time signal (such as, for instance,
the air pressure fluctuation at the entrance of the ear
canal) into a discrete-time signal, that is a sequence of
numbers. The discrete-time signal gives the values of the
continuous-time signal read at intervals of
T T seconds. The reciprocal of the
sampling interval is called
sampling rate
F
s
=1T
F
s
1
T
. In this module we do not explain the theory of
sampling, but we rather describe its manifestations. For a a
more extensive yet accessible treatment, we point to the
Introduction to Sound Processing.
For our purposes, the process of sampling a 1-D signal can
be reduced to three facts and a theorem.
- Fact 1 The Fourier
Transform of a discrete-time signal is a function
(called spectrum) of the continuous
variable ω ω, and it
is periodic with period
2π
2
π
. Given a value of ω
ω, the Fourier transform gives back a complex
number that can be interpreted as magnitude and phase
(translation in time) of the sinusoidal component at
that frequency.
- Fact 2 Sampling the continuous-time signal
xt
x
t
with interval
T
T we get the discrete-time signal
xn=xnT
x
n
x
n
T
, which is a function of the discrete variable
n
n.
- Fact 3 Sampling a continuous-time signal
with sampling rate
F
s
F
s
produces a discrete-time signal whose frequency
spectrum is the periodic replication of the original
signal, and the replication period is
F
s
F
s
. The Fourier variable
ω ω for functions of discrete
variable is converted into the frequency variable
f f (in Hertz) by means of
f=ω2πT
f
ω
2
π
T
.
The
Figure 1 shows an example of frequency
spectrum of a signal sampled with sampling rate
F
s
F
s
. In the example, the continuous-time signal had
all and only the frequency components between
-
F
b
F
b
and
F
b
F
b
. The replicas of the original spectrum are
sometimes called
images.
Given the
facts, we can have an
intuitive understanding of the Sampling Theorem,
historically attributed to the scientists Nyquist and
Shannon.
theorem 1: Sampling Theorem
A continuous-time signal
xt
x
t
, whose spectral content is limited to
frequencies smaller than
F
b
F
b
(i.e., it is band-limited to
F
b
F
b
) can be recovered from its sampled version
xn
x
n
if the sampling rate is larger than twice the
bandwidth (i.e., if
F
s
>2
F
b
F
s
2
F
b
)
The reconstruction can only occur by means of a filter that
cancels out all spectral images except for the one directly
coming from the original continuous-time signal. In other
words, the canceled images are those having frequency
components higher than the
Nyquist frequency
defined as
F
s
2
F
s
2
. The condition required by the
sampling theorem is equivalent
to saying that no overlaps between spectral images are allowed. If
such superimpositions were present, it wouldn't be possible to design
a filter that eliminates the copies of the original spectrum. In case of overlapping, a filter
that eliminates all frequency components higher than the Nyquist
frequency would produce a signal that is affected by
aliasing. The concept of aliasing is well illustrated in
the
Aliasing Applet, where a
continuous-time sinusoid is subject to sampling. If the frequency of
the sinusoid is too high as compared to the sampling rate, we see that
the the waveform that is reconstructed from samples is not the
original sinusoid, as it has a much lower frequency. We all have
familiarity with aliasing as it shows up in moving images, for
instance when the wagon wheels in western movies start spinning
backward. In that case, the sampling rate is given by the
frame
rate, or number of pictures per second, and has to be related
with the spinning velocity of the wheels. This is one of several
stroboscopic phenomena.
In the case of sound, in order to become aware of the consequences of the
2π
2
π
periodicity of discrete-time signal spectra
(see
Figure 1) and of violations of the condition of
the sampling theorem, we examine a simple case.
Let us consider a sound that is generated by a sum of sinusoids that
are harmonics (i.e., integer multiples) of a fundamental. The spectrum
of such sound would display peaks corresponding to the fundamental
frequency and to its integer multiples.
Just to give a concrete example, imagine working at the sampling rate of
44100 44100 Hz and summing
10 10 sinusoids. From the sampling theorem we know
that, in our case, we can represent without aliasing all frequency
components up to
22050 22050 Hz. So, in
order to avoid aliasing, the fundamental frequency should be lower
than
2205 2205 Hz. The Processing (+ Sonia)
code reported in table
Table 1 implements a
generator of sounds formed by
10 10
harmonic sinusoids. To produce such sounds it is necessary to click on
a point of the display window. The x coordinate would vary with the
fundamental frequency, and the window will show the spectral peaks
corresponding to the generated harmonics. When we click on a point
whose x coordinate is larger than
110
1
10
of the window width, we still see ten spectral
peaks. Otherwise, we violate the sampling theorem and
aliasing will enter our representation.
|
Aliasing test:
Applet to experience the effect of aliasing on
sounds obtained by summation of 10 sinusoids in
harmonic ratio |
import pitaru.sonia_v2_9.*;
int L = 1024; // FFT length (positive frequency)
int L2 = int(L*4); // table length
int sr = 44100;
int H = 10; //number of harmonics
int ampiezza;
float[] Data;
float freq = 10.00; // fundamental frequency [Hz]
Sample mySample;
float oneCycle = TWO_PI/L;
void setup() {
size(1024,200);
frameRate(1);
colorMode(HSB, 360, height, height);
Sonia.start(this);
mySample = new Sample(L2); // empty sample with L2 frames.
Data = new float[L2]; // array with as many frames as samples.
//populate the array with sample data, i.e. a sine wave
for(int k = 1; k <=H; k++){ // Additive Synthesis
for(int i = 0; i < L2; i++){
Data[i] = Data[i] + sin(i*oneCycle*freq*k)/10;
}
}
mySample.write(Data); // write from 'Data' array into sample
mySample.repeat(); // loop the sample */
}
void draw()
{
background(0,20,0);
strokeWeight(0);
stroke(0,230,0);
mySample.getSpectrum(L); // FFT
stroke(255); //println();
for ( int i = 1; i < L; i++){
ampiezza = int(mySample.spectrum[i]*L);
line(i, height, i, height - 2*ampiezza/(0.003*i));
}
}
void mouseReleased()
{
freq = (float)(mouseX/2); // to change the fundamental
println(freq + " Hz");
for (int i = 0; i < L2; i++) Data[i] = 0;
for(int k = 1; k <=H; k++){ // Additive Synthesis
for(int i = 0; i < L2; i++){
Data[i] = Data[i] + sin(i*oneCycle*freq*k)/20;
}
}
mySample.write(Data); // write from 'Data' array into sample
mySample.getSpectrum(L); // initial steps
mouseReleased();
}
// safely stop the Sonia engine upon shutdown.
public void stop(){
Sonia.stop();
super.stop();
}
|
2-D: Images
Let us assume we have a continuous distribution, on a plane,
of values of luminance or, more simply stated, an
image. In order to process it using a computer we have to
reduce it to a sequence of numbers by means of
sampling. There are several ways to sample an image, or
read its values of luminance at discrete points. The
simplest way is to use a regular grid, with spatial steps
X X e
Y Y. Similarly to what we did for
sounds, we define the spatial sampling rates
F
X
=1X
F
X
1
X
and
F
Y
=1Y
F
Y
1
Y
. As in the one-dimensional case, also for
two-dimensional signals, or images, sampling can be
described by three facts and a theorem.
- Fact 1 The Fourier Transform of a
discrete-space signal is a function (called
spectrum) of two continuous variables
ω
X
ω
X
and
ω
Y
ω
Y
, and it is periodic in two dimensions with periods
2π
2
π
. Given a couple of values
ω
X
ω
X
and
ω
Y
ω
Y
, the Fourier transform gives back a
complex number that can be interpreted as magnitude and
phase (translation in space) of the sinusoidal component
at such spatial frequencies.
- Fact 2 Sampling the continuous-space signal
sxy
s
x
y
with the regular grid of steps
X
X,
Y
Y, gives a discrete-space signal
smn=smXnY
s
m
n
s
m
X
n
Y
, which is a function of the discrete variables
m
m and
n
n.
- Fact 3 Sampling a continuous-space signal
with spatial frequencies
F
X
F
X
and
F
Y
F
Y
gives a discrete-space signal whose spectrum is
the periodic replication along the grid of steps
F
X
F
X
and
F
Y
F
Y
of the original signal spectrum. The Fourier variables
ω X
ω X
and
ω
Y
ω
Y
correspond to the frequencies (in
cycles per meter) represented by the variables
f
X
=
ω
X
2πX
f
X
ω
X
2
π
X
and
f
Y
=
ω
Y
2πY
f
Y
ω
Y
2
π
Y
.
The
Figure 2 shows an example of spectrum
of a two-dimensional sampled signal. There, the
continuous-space signal had all and only the frequency
components included in the central hexagon. The hexagonal
shape of the spectral support (region of non-null spectral
energy) is merely illustrative. The replicas of the original
spectrum are often called spectral
images.
Given the above
facts, we can
have an intuitive understanding of the Sampling Theorem.
theorem 2: Sampling Theorem (in 2D)
A continuous-space signal
sxy
s
x
y
, whose spectral content is limited to spatial
frequencies belonging to the rectangle having semi-edges
F
bX
F
bX
and
F
bY
F
bY
(i.e., bandlimited) can be recovered from its sampled version
smn
s m
n
if the spatial sampling rates are larger than
twice the respective bandwidths (i.e., if
F
X
>2
F
bX
F
X
2
F
bX
and
F
Y
>2
F
bY
F
Y
2
F
bY
)
In practice, the spatial sampling step can not be larger
than the semi-period of the finest spatial frequency (or the
finest detail) that is represented in the image. The
reconstruction can only be done through a filter that
eliminates all the spectral images but the one coming
directly from the original continuous-space signal. In other
words, the filter will cut all images whose frequency
components are higher than the
Nyquist
frequency defined as
F
X
2
F
X
2
and
F
Y
2
F
Y
2
along the two axes. The condition required by the
sampling
theorem is equivalent to requiring that there are no
overlaps between spectral images. If there were such
overlaps, it wouldn't be possible to eliminate the copies of
the original signal spectrum by means of filtering. In case of overlapping, a filter
cutting all frequency components higher than the Nyquist
frequency would give back a signal that is affected by
aliasing.
We note how aliasing can be produced by down-sampling (or
decimating) a sampled image. Starting from a discrete-space
image, we can select only a subset of samples arranged in a
regular grid. This will determine the periodic repetition of
the spectral images, that will end up overlapping.
In order to explore the concepts of sampling, down-sampling,
and aliasing, run the
applet drawing ellipses
. With the keyboard arrow you can double or halve the
horizontal and vertical sampling steps.