Connexions

You are here: Home » Content » Signal Processing in Processing: Sampling and Quantization
Content Actions

Signal Processing in Processing: Sampling and Quantization

Module by: Davide Rocchesso, Pietro Polotti Based on: Signal Processing in Processing: Sampling and Quantization by Davide Rocchesso, Pietro Polotti

Summary: Fundamentals of sampling, reconstruction, and quantization of 1D (sounds) and 2D (images) signals, especially oriented at the Processing language.

Sampling

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.
Frequency spectrum of a sampled signal
repeti.png
Figure 1
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.
Spectrum of a sampled image
repeti2D.png
Figure 2
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.
A simple introduction to the first elements of image processing is found in Digital Image Processing Basics.

Quantization

With the adjective "digital" we indicate those systems that work on signals that are represented by numbers, with the (finite) precision that computing systems allow. Up to now we have considered discrete-time and discrete-space signals as if they were collections of infinite-precision numbers, or real numbers. Unfortunately, computers only allow to represent finite subsets of rational numbers. This means that our signals are subject to quantization.
For our purposes, the most interesting quantization is the linear one, which is usually occurring in the process of conversion of an analog signal into the digital domain. If the memory word dedicated to storing a number is made of b b bits, then the range of such number is discretized into 2b 2 b quantization levels. Any value that is found between two quantization levels can be approximated by truncation or rounding to the closest value. The Figure 3 shows an example of quantization with representation on 3 3 bits in two's complement.
Sampling and quantization of an analog signal
quant.png
Figure 3
The approximation introduced by quantization manifests itself as a noise, called quantization noise. Often, for the analysis of sound-processing circuits, such noise is assumed to be white and de-correlated with the signal, but in reality it is perceptually tied to the signal itself, in such an extent that quantization can be perceived as an effect.
To have a visual and intuitive exploration of the phenomenon of quantization, consider the applet that allows to vary between 1 1 and 8 8 the number of bits dedicated to the representation of each of the RGB channels representing color. The same number of bits is dedicated to the representation of an audio signal coupled to the image. The visual effect that is obtained by reducing the number of bits is similar to a solarization.
Problem 1
Extend the code of the applet Table 1 to add some interaction features:
  • Make the fundamental frequency of the automatically-generated sound changing randomly at each frame (see random()).
  • Make the framerate (and the metronome for generating notes) dependent on the horizontal position of the mouse (mouseX).
  • Make the number of harmonics of the sound (i.e., its brightness) dependent on the vertical position of the mouse (mouseY).
  • Paint the window background in such a way that moving from left to right the tint changes from blue to red. In this way, a blue color will correspond to a slow tempo, and a red color to a fast tempo.
  • Make the color saturation of the background dependent on the vertical position of the mouse. In this way a sound with a few harmonics (low brightness) will correspond to a grayish color, while a sound rich of harmonics (high brightness) will correspond to a saturated color.
  • Add a control to stop the computation and display of the spectrum and create an effect of image freezing, while sound continues to be generated (for instance by keeping the mouse button pressed).
  • Add a control to cancel the dependence of tempo, brightness, and color saturation on mouse position (for instance by pressing a key).
  • Add a control that, in case of image freezing (mouse button pressed), will stop the generation of new notes while "freezing" the current note.
  • Finally, add a control that, in case of image freezing, will stop the sound generation and make the application silent.
[ Click for Solution 1 ]
Solution 1
The proposed extensions are implemented in the Processing code.
[ Hide Solution 1 ]
References
  1. Davide Rocchesso. (2003). Introduction to Sound Processing. [http://www.mondo-estremo.com]. Mondo Estremo.

Comments, questions, feedback, criticisms?

Send feedback