A linear shift-invariant imaging system is completely characterised by its

impulse response (point spread function)

By the convolution theorem, convolving an image with a kernel in the spatial domain is equivalent, in the frequency domain, to

multiplying their Fourier transforms

adding their Fourier transforms

convolving their Fourier transforms

dividing the image transform by the kernel transform

Which of the following statements about convolution and correlation of images are correct?

Convolution flips the kernel before sliding it; correlation does not

For a symmetric kernel, convolution and correlation give the same result

Convolution flips the kernel before sliding it; correlation does not

For a symmetric kernel, convolution and correlation give the same result

For a Sobel gradient kernel, convolution and correlation always give identical signs

Which of the following statements about sampling and quantization are correct?

Sampling discretises position; quantization discretises brightness

Too few quantization levels produce false contouring

Aliasing introduced at sampling cannot be removed afterwards by filtering the digital image

Sampling discretises position; quantization discretises brightness

Too few quantization levels produce false contouring

Aliasing introduced at sampling cannot be removed afterwards by filtering the digital image

Adding one bit halves the number of grey levels

Which of the following systems, mapping an input image f to an output g, are linear?

g(i, j) = f(i, j) − f(i, j − 1)

g(i, j) = the mean of the 3 × 3 neighbourhood of f

g(i, j) = f(i, j) − f(i, j − 1)

g(i, j) = the mean of the 3 × 3 neighbourhood of f

Data Quantization and Processing: Sampling, Quantization, Linear Systems and Convolution

This is a section of Part B2, Image Processing and Analysis, of the Geomatics Engineering (GE) paper. Part B2, Image Processing and Analysis, starts from the signal: “Data Quantization and Processing: Sampling and quantization theory, Principle of Linear System, Convolution”. A digital image is a continuous scene sampled on a grid and quantised to integers, and almost every later operation — filtering, resampling, enhancement — is a linear system applied by convolution. This chapter states the sampling theorem and what aliasing does to an image; quantisation into 2ⁿ levels, the quantisation step and its error, and the signal-to-noise ratio it allows; the two properties that define a linear shift-invariant system and why its impulse response (the point spread function) describes it completely; and discrete convolution in one and two dimensions, its output size and cost, the convolution theorem, and how convolution differs from correlation. The numericals are Nyquist intervals, aliased frequencies, grey levels and short convolutions.

1. Sampling theory and aliasing

Sampling records a continuous signal at discrete intervals — in an image, one value per pixel on a regular grid. The sampling theorem (Nyquist–Shannon): a signal containing no frequencies above f_max is completely recoverable from samples taken at a rate f_s ≥ 2f_max; equivalently, the sampling interval must be at most half the shortest period present. The limit f_s/2 is the Nyquist frequency. For a ground pattern whose finest period is 10 m, pixels of 5 m or smaller are needed to represent it. Sampling below the Nyquist rate causes aliasing: a frequency f above f_s/2 appears as a false lower frequency |f − k f_s|; a 10 Hz signal sampled at 12 Hz shows up at 2 Hz. In images aliasing produces moiré patterns on regular structures (rows of crops, roof tiles, fences) and jagged edges. It cannot be removed after sampling; it is prevented by optical blur (the sensor's point spread function acts as an anti-aliasing filter) or by sampling more finely.

⚠️ The pixel must be half the period, not equal to it

To see a pattern of 10 m stripes (5 m bright, 5 m dark, period 10 m), 10 m pixels can land exactly on the boundaries and average every stripe to grey. At least two samples per period are needed; in practice somewhat more, because real sensors blur.

2. Quantization

Quantization maps each sampled value to one of a finite set of integers, the digital numbers (DN). With n bits there are 2ⁿ levels, DN = 0 … 2ⁿ − 1: 8 bits give 256, 10 bits 1024, 11 bits 2048, 12 bits 4096. Over an input range R the quantization step is Δ = R/2ⁿ; a radiance range of 30.72 units quantised to 10 bits has Δ = 0.03. Rounding to the nearest level leaves a quantization error between −Δ/2 and +Δ/2; modelled as uniform, its RMS value is Δ/√12. For a full-scale sinusoidal signal the ideal signal-to-quantization-noise ratio is about 6.02n + 1.76 dB — each extra bit adds about 6 dB. Too few levels give false contouring: smooth gradients break into visible bands.

Sampling against quantization
Aspect	Sampling	Quantization
Discretises	position (x, y) or time	amplitude (brightness)
Governs	spatial resolution	radiometric resolution
Too coarse gives	aliasing, moiré, lost detail	false contours, lost subtle differences

3. The principle of linear systems

A system T that turns an input f into an output g = T[f] is linear if it obeys superposition: additivity T[f₁ + f₂] = T[f₁] + T[f₂] and homogeneity T[a f] = a T[f]. It is shift-invariant (space-invariant) if shifting the input shifts the output by the same amount and changes nothing else. A linear shift-invariant (LSI) system is completely described by its impulse response h — the output for a single point of light, which in imaging is the point spread function (PSF): because any image is a sum of shifted, scaled impulses, the output is the same sum of shifted, scaled PSFs, which is exactly convolution, g = f ∗ h. The Fourier transform of the PSF is the system's transfer function; its magnitude is the modulation transfer function (MTF), which says how much contrast survives at each spatial frequency.

Which common operations are linear?
Operation	Linear?	Why
Mean (box) filter, Gaussian blur, Laplacian, Sobel	yes, and shift-invariant	weighted sums with fixed weights
Median filter	no	the median of a sum is not the sum of the medians
g = 2f + 3 (gain and offset)	no (affine)	doubling f does not double g; zero input gives 3
Squaring, thresholding, histogram equalisation	no	fail additivity

4. Convolution

Discrete convolution in one dimension: y[n] = Σₖ x[k] h[n − k]. For x = [1, 2, 3] and h = [1, 1], y = [1, 3, 5, 3]: the output has length N + M − 1 = 3 + 2 − 1 = 4, and the sum of the output (12) equals the product of the input sums (6 × 2). In two dimensions, g(i, j) = Σₘ Σₙ f(i − m, j − n) h(m, n): the kernel is flipped in both directions and slid over the image, and at each position the overlapping values are multiplied and summed. Correlation is the same without the flip; for a symmetric kernel (mean, Gaussian, Laplacian) the two are identical, but for an antisymmetric kernel such as a Sobel gradient they give outputs of opposite sign. Border pixels need a rule — zero padding, replication or reflection — or are left undefined.

Cost: an M × M kernel on an N × N image needs about N²M² multiplications — 9 × 10⁶ for a 3 × 3 kernel on a 1000 × 1000 image. A separable kernel (an outer product of two 1D kernels, like the box or Gaussian) can be applied as two 1D passes, 2M instead of M² operations per pixel.
Convolution theorem: convolution in the spatial domain is multiplication in the frequency domain, F{f ∗ h} = F{f}·F{h}. Large kernels are therefore applied faster through the FFT, and filters are designed by the frequencies they pass: low-pass smooths, high-pass sharpens.
Convolution is commutative, associative and distributive over addition: two filters in sequence equal one filter whose kernel is their convolution.

🧠 A kernel whose weights sum to 1 keeps the mean; one that sums to 0 finds edges

Because output sum = input sum × kernel sum, a smoothing kernel normalised to 1 leaves flat areas unchanged, while a derivative kernel summing to 0 returns zero on any flat area and responds only where brightness changes.

Key takeaways

Sampling theorem: sample at least twice the highest frequency (pixel ≤ half the finest period); under-sampling aliases a frequency f to |f − k f_s|, seen as moiré.
n bits give 2ⁿ levels; step Δ = R/2ⁿ; RMS quantization error Δ/√12; SNR ≈ 6.02n + 1.76 dB.
Linear = additive and homogeneous; LSI systems are described completely by the impulse response (PSF), and act by convolution.
Convolution flips the kernel (correlation does not); output length N + M − 1; output sum = input sum × kernel sum.
Convolution theorem: spatial convolution = frequency-domain multiplication; separable kernels cost 2M instead of M² per pixel.

Practice questions (14)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

The finest periodic pattern in a scene repeats every 10 m on the ground. The largest pixel size, in metres, that satisfies the sampling theorem is ____.
Numerical answer — type the value.
Show answer
Answer: 5
The sampling interval must be at most half the shortest period: 10/2 = 5 m, i.e. at least two samples per cycle. A 10 m pixel samples once per cycle and can average the pattern away completely.
A 10 Hz sinusoid is sampled at 12 samples per second. The apparent (aliased) frequency in the samples, in Hz, is ____.
Numerical answer — type the value.
Show answer
Answer: 2
The Nyquist frequency is 12/2 = 6 Hz, below 10 Hz, so the signal aliases to |f − f_s| = |10 − 12| = 2 Hz. At 20 or more samples per second the 10 Hz signal would be recorded correctly.
A radiance range of 0 to 30.72 units is quantised with 10 bits. The quantization step, in radiance units, is ____.
Numerical answer — type the value.
Show answer
Answer: 0.03
10 bits give 2¹⁰ = 1024 levels; Δ = 30.72/1024 = 0.03 units. Dividing by 1023 (the maximum DN) gives 0.03003, a negligible difference here, but the level count is 2ⁿ.
For the same quantizer (step 0.03 units), treating the rounding error as uniformly distributed, the RMS quantization error, in radiance units (to four decimal places), is ____.
Numerical answer — type the value.
Show answer
Answer: 0.0087
A uniform error on (−Δ/2, +Δ/2) has variance Δ²/12, so the RMS error is Δ/√12 = 0.03/3.4641 = 0.00866 ≈ 0.0087. The maximum error is Δ/2 = 0.015; the RMS is smaller because most errors are not at the extreme.
Using SNR ≈ 6.02n + 1.76 dB for a full-scale sinusoid, the ideal signal-to-quantization-noise ratio of an 8-bit quantizer, in dB (to two decimal places), is ____.
Numerical answer — type the value.
Show answer
Answer: 49.92
6.02 × 8 + 1.76 = 48.16 + 1.76 = 49.92 dB. Each extra bit adds 6.02 dB, i.e. halves the quantization noise amplitude.
Which of the following image operations is NOT linear?
1. Median filtering
2. 3 × 3 mean filtering
3. Gaussian smoothing
4. Laplacian filtering
Show answer
Answer: A — Median filtering
The median is a rank (order) statistic: the median of the sum of two images is not in general the sum of their medians, so superposition fails. The mean, Gaussian and Laplacian are fixed weighted sums and are linear and shift-invariant.
A linear shift-invariant imaging system is completely characterised by its
1. impulse response (point spread function)
2. output histogram
3. maximum output value
4. number of bits per pixel
Show answer
Answer: A — impulse response (point spread function)
Any input is a superposition of shifted, weighted impulses; linearity and shift invariance make the output the same superposition of shifted, weighted impulse responses, i.e. input ∗ PSF. The histogram and bit depth describe the data, not the system.
The sequence x = [1, 2, 3] is convolved with h = [1, 1]. The third element of the output y (y[2], counting from y[0]) is ____.
Numerical answer — type the value.
Show answer
Answer: 5
y[n] = Σ x[k]h[n − k]: y[0] = 1, y[1] = 2 + 1 = 3, y[2] = 3 + 2 = 5, y[3] = 3. So y = [1, 3, 5, 3], of length 3 + 2 − 1 = 4, and its sum 12 = 6 × 2 checks the result.
A signal of 100 samples is convolved with a 5-tap filter using full convolution. The number of output samples is ____.
Numerical answer — type the value.
Show answer
Answer: 104
Full convolution has length N + M − 1 = 100 + 5 − 1 = 104. Keeping only positions where the kernel fully overlaps gives N − M + 1 = 96, and “same” mode keeps 100.
A separable 5 × 5 Gaussian kernel is applied to an image as two 1D passes instead of one 2D pass. The number of multiplications per pixel with the separable form is ____.
Numerical answer — type the value.
Show answer
Answer: 10
A 5-tap row pass and a 5-tap column pass cost 5 + 5 = 10 multiplications per pixel, against 5 × 5 = 25 for the direct 2D kernel. The saving grows with kernel size: 2M against M².
By the convolution theorem, convolving an image with a kernel in the spatial domain is equivalent, in the frequency domain, to
1. multiplying their Fourier transforms
2. adding their Fourier transforms
3. convolving their Fourier transforms
4. dividing the image transform by the kernel transform
Show answer
Answer: A — multiplying their Fourier transforms
F{f ∗ h} = F{f}·F{h}: each frequency of the image is scaled by the filter's response at that frequency. Division is the idea behind inverse filtering (deconvolution); convolution in frequency corresponds to multiplication in space.
Which of the following statements about convolution and correlation of images are correct?
1. Convolution flips the kernel before sliding it; correlation does not
2. For a symmetric kernel, convolution and correlation give the same result
3. Convolution is commutative
4. For a Sobel gradient kernel, convolution and correlation always give identical signs
Show answer
Answer: A — Convolution flips the kernel before sliding it; correlation does not; B — For a symmetric kernel, convolution and correlation give the same result; C — Convolution is commutative
The flip is the definition of convolution; a symmetric kernel is unchanged by the flip, so the two agree; and f ∗ h = h ∗ f. A Sobel kernel is antisymmetric, so flipping it negates it and the two operations give opposite signs — the magnitude is the same, the direction reversed.
Which of the following statements about sampling and quantization are correct?
1. Sampling discretises position; quantization discretises brightness
2. Too few quantization levels produce false contouring
3. Aliasing introduced at sampling cannot be removed afterwards by filtering the digital image
4. Adding one bit halves the number of grey levels
Show answer
Answer: A — Sampling discretises position; quantization discretises brightness; B — Too few quantization levels produce false contouring; C — Aliasing introduced at sampling cannot be removed afterwards by filtering the digital image
Sampling sets the grid, quantization the grey scale; too few levels band smooth gradients; and once a high frequency has been folded onto a low one it is indistinguishable from a real low frequency, so no later filter can separate them. Adding a bit doubles the number of levels (2ⁿ⁺¹ = 2 × 2ⁿ).
Which of the following systems, mapping an input image f to an output g, are linear?
1. g(i, j) = f(i, j) − f(i, j − 1)
2. g = 0.5 f
3. g(i, j) = the mean of the 3 × 3 neighbourhood of f
4. g = 2f + 3
Show answer
Answer: A — g(i, j) = f(i, j) − f(i, j − 1); B — g = 0.5 f; C — g(i, j) = the mean of the 3 × 3 neighbourhood of f
A difference of pixels, a scaling and a neighbourhood mean are all fixed weighted sums of input values, so they satisfy additivity and homogeneity. g = 2f + 3 fails both: a zero input gives 3, and doubling f does not double g — it is affine, not linear.