Digital Images and Sampling

A continuous image can be modeled as a function $I(x, y)$ giving irradiance (brightness) at every real-valued position $(x, y)$ on the image plane produced by the pinhole projection. To store this in a computer we must convert it into a digital image, a two-dimensional array $I[m, n]$ of numbers, where $m$ and $n$ are integer row/column indices and each stored value comes from a finite set (e.g. integers $0$–$255$). This conversion has two logically separate parts.

Sampling is the process of evaluating (in practice, integrating over a small sensor cell) the continuous function at a discrete set of locations, typically a regular grid with spacing $\Delta x$ in $x$ and $\Delta y$ in $y$. The sampling rate is $1/\Delta x$ samples per unit length. Sampling is a spatial discretization: it decides which points are measured but assumes, for now, that the measured value itself is stored exactly.

Quantization is the process of mapping the (in principle continuous, real-valued) measured brightness at each sample to one of a finite set of levels — for an 8-bit grayscale image, one of $256$ integers. This is a discretization of value, orthogonal to the discretization of position. Quantization always introduces some error, called quantization error or quantization noise, because a continuum of possible brightnesses is being collapsed onto finitely many representable numbers. The central theoretical tool for understanding sampling is the Fourier transform. Any image can be decomposed into a sum (integral) of sinusoidal gratings of different spatial frequencies and orientations. Sampling and reconstruction behave in a way that is easy to state exactly in this frequency domain but hard to reason about directly in the spatial domain — this is why the frequency-domain analysis is not a mere curiosity but the load-bearing argument behind the entire theory.

Step 1 — The continuous image and its spectrum

Model the image plane signal as $I(x,y)$, and let $\hat I(u,v)$ denote its 2D Fourier transform, where $(u, v)$ are spatial frequencies (cycles per unit length). Real optical systems act as low-pass filters (finite aperture, diffraction, lens blur), so in practice $\hat I$ decays at high frequency, but it is rarely exactly zero above some cutoff — sharp scene edges and fine textures contain arbitrarily high frequencies in principle.

Step 2 — Sampling as multiplication by a comb

Sampling on a grid with spacing $\Delta$ is modeled as multiplying $I(x,y)$ by a 2D Dirac comb (an infinite grid of impulses spaced $\Delta$ apart):

The key fact from Fourier theory: multiplication in the spatial domain corresponds to convolution in the frequency domain, and the Fourier transform of a Dirac comb with spacing $\Delta$ is another Dirac comb with spacing $1/\Delta$. Therefore:

Convolving a spectrum with a comb of impulses simply replicates that spectrum at every comb location. So the sampled signal's spectrum is the original spectrum $\hat I$, copied and stacked side by side, once every $1/\Delta$ in frequency.

Step 3 — The Nyquist criterion

If $\hat I(u,v)$ is zero outside a disk of radius $f_{max}$ (the signal is band-limited), the replicated copies do not overlap provided the copies are spaced far enough apart:

This is the Nyquist–Shannon sampling theorem. The quantity $2f_{max}$ is the Nyquist rate; $f_{max}$ itself (half the sampling rate) is the Nyquist frequency. When this holds, the original continuous spectrum can be recovered exactly by multiplying the sampled spectrum by an ideal low-pass filter (a box of radius $f_{max}$) — an operation that corresponds, in the spatial domain, to convolving the samples with a sinc interpolation kernel. This gives perfect reconstruction: not an approximation, but mathematically exact recovery of $I(x,y)$ from its samples.

Step 4 — Aliasing when Nyquist is violated

If $1/\Delta < 2f_{max}$, the shifted spectral copies overlap. In the overlap region, energy that truly belongs to a high frequency $f > f_{max}$ gets added on top of energy that belongs to some lower frequency, and the sum is indistinguishable from a signal that never had high frequencies at all. A high spatial frequency component is thereby aliased — relabeled — as a different, lower apparent frequency:

This is not noise in the sense of randomness — it is a deterministic, structured corruption, which is why aliasing produces coherent visual artifacts (moiré fringes, false low-frequency stripes, jagged staircase edges) rather than random-looking speckle.

Step 5 — Anti-aliasing (pre-filtering)

Since aliasing arises only from frequencies above $f_{max} = 1/(2\Delta)$, it can be prevented by removing those frequencies from the continuous signal before sampling — this is what an anti-aliasing filter (optical low-pass filter in cameras, or a blur kernel in software resampling) does. It cannot be fixed after sampling, because after sampling, the aliased and true low-frequency content are already summed together and are no longer separable.

Step 6 — Quantization

Independently of sampling, each measured (and averaged over the sensor's finite area) sample value $v \in [v_{min}, v_{max}]$ must be mapped to one of $L = 2^b$ discrete levels for $b$-bit storage. The simplest scheme is uniform quantization:

Each quantization step has width $\Delta_q = (v_{max}-v_{min})/L$; the quantization error $|v - Q(v)|$ is at most $\Delta_q/2$.

Full pipeline pseudocode

``` function DIGITIZE_IMAGE(ContinuousScene, sensor_grid, bits_per_pixel):

# sensor_grid: array of (x, y) sample centers, spacing Δ

# Step 0: optical/physical anti-aliasing pre-filter

# models lens blur + finite pixel aperture as a low-pass filter FilteredScene = LOW_PASS_FILTER(ContinuousScene, cutoff = 1 / (2 * Δ)) RawSamples = empty array sized like sensor_grid

# Step 1: SAMPLING — integrate irradiance over each sensor cell for each (m, n) in sensor_grid: cell_region = PIXEL_AREA(m, n, Δ) RawSamples[m, n] = INTEGRATE(FilteredScene, over = cell_region) / AREA(cell_region) DigitalImage = empty array sized like RawSamples L = 2 ** bits_per_pixel v_min, v_max = RANGE(RawSamples) # e.g. sensor's dynamic range

# Step 2: QUANTIZATION — map continuous value to nearest of L levels for each (m, n) in RawSamples: v = RawSamples[m, n] level = floor( (v - v_min) / (v_max - v_min) L ) level = clamp(level, 0, L - 1) # guard the top edge v == v_max DigitalImage[m, n] = level return DigitalImage ``` Two edge cases matter here and are easy to get wrong. First, `v == v_max` must not map to level `L` (out of range) — hence the `clamp`. Second, the low-pass pre-filter's cutoff must be tied to the sampling* spacing $\Delta$, not chosen arbitrarily; choosing it too high defeats anti-aliasing, and too low needlessly blurs the image.

Time and space complexity. For an image with $N = W \times H$ pixels and $b$ bits per channel, the sampling step performs one local integral per pixel; if each pixel's footprint integral is approximated by summing over a constant-size neighborhood (as with a small anti-aliasing kernel of size $k \times k$), sampling costs $O(N \cdot k^2)$ time and $O(N)$ space to store the result. Quantization is a single pass per pixel, $O(N)$ time, $O(N \cdot b / 8)$ bytes of storage (e.g. $O(N)$ bytes for 8-bit images). Both are linear in the number of pixels, which is why digitization is cheap compared to later vision algorithms; the theoretical subtlety is entirely in correctness, not speed.

Correctness of the sampling theorem. The proof sketch rests on two facts from Fourier analysis. (1) The Fourier transform of an impulse train (Dirac comb) with spacing $\Delta$ is itself an impulse train, with spacing $1/\Delta$ — this follows from the comb being a periodic distribution, and Fourier transforms of periodic functions are supported on a discrete lattice (essentially a Fourier series argument in the limit). (2) Multiplication in the spatial domain is convolution in frequency, a direct consequence of the linearity and shift properties of the Fourier transform. Combining these, sampling replicates the spectrum on a $1/\Delta$-spaced lattice. If the original spectrum's support (radius $f_{max}$) is smaller than half the lattice spacing, the copies are disjoint, so an ideal low-pass filter with cutoff $f_{max}$ applied to the sampled spectrum recovers exactly the central copy — which is $\hat I(u,v)$ itself. Taking the inverse Fourier transform recovers $I(x,y)$ exactly. This is why the theorem gives perfect, not merely approximate, reconstruction under the band-limited assumption — the assumption is doing all the work, and it is precisely the assumption real-world edges and textures violate (they are not perfectly band-limited), which is why anti-aliasing pre-filters are still needed in practice even though the math is exact.

Correctness/behavior of quantization. Uniform quantization with $L$ levels over range $R = v_{max}-v_{min}$ guarantees maximum absolute error $\Delta_q/2 = R/(2L)$ for every sample, by construction of `floor`. Under the common modeling assumption that the true value is uniformly distributed within each quantization bin, the quantization error is itself approximately uniform on $[-\Delta_q/2, \Delta_q/2]$, giving mean-squared error $\Delta_q^2/12$ — the standard derivation of quantization noise power, useful for reasoning about a coarse SNR estimate:

(the classic "6 dB per bit" rule), which is why dropping from 8 to 4 bits per channel is not a mild loss but roughly a 24 dB drop in fidelity, visible as banding.

Honest tradeoffs. Sampling above Nyquist is necessary but real cameras cannot pre-filter perfectly (optical anti-aliasing filters are imperfect, and removing them, as many modern cameras do, trades some aliasing risk for sharper output when scene content is usually benign). Quantization always loses information regardless of bit depth; more bits reduce, but never eliminate, quantization error, and cost linearly more storage and bandwidth. There is no "correct" sampling rate or bit depth in the abstract — both are chosen relative to the frequency content of the scene and the perceptual/task tolerance for error.

Consider imaging a fine striped shirt (a common source of visible camera artifacts) whose stripe pattern has a true spatial frequency of $f = 30$ cycles/mm on the sensor plane after the pinhole projection. The camera's sensor has pixel spacing $\Delta = 0.02$ mm (a sampling rate of $50$ samples/mm).

Step 1 — Nyquist frequency of the sensor.

Step 2 — Compare to signal frequency. The stripe pattern at $30$ cycles/mm exceeds $f_{Nyquist} = 25$ cycles/mm, so Nyquist is violated — aliasing will occur.

Step 3 — Compute the aliased frequency. Using $f_{alias} = |f - k/\Delta|$ with sampling rate $1/\Delta = 50$ cycles/mm, choose $k=1$:

Since $20 < 25$ this is a valid, visible alias frequency, so the photo shows fine stripes replaced by a coarser, incorrect $20$-cycles/mm pattern — a moiré artifact, and it will shift and shimmer as the camera or fabric moves slightly, changing $f$ relative to $\Delta$.

Fix: anti-aliasing pre-filter. If an optical low-pass filter blurs the image before it reaches the sensor, attenuating content above $25$ cycles/mm, the $30$-cycle/mm stripe energy is suppressed before sampling, so it cannot fold down to $20$ cycles/mm — the shirt instead appears slightly blurred rather than incorrectly striped. This is the exact tradeoff every camera anti-aliasing filter makes: sacrifice some true high-frequency detail to prevent worse, structured aliasing errors.

Quantization side-check. Suppose the sensor's dynamic range is $v \in [0, 1]$ (normalized irradiance) and it uses $b = 8$ bits, so $L = 256$, $\Delta_q = 1/256 \approx 0.0039$. A true value $v = 0.503$ quantizes to level $\lfloor 0.503 \times 256 \rfloor = 128$, i.e. reconstructed value $128/256 = 0.5$, an error of $0.003$ — well under the max error bound $\Delta_q/2 \approx 0.00195$... note this only checks out because $128/256=0.5$ is the bin start; the correctly reported maximum error per bin is indeed $\Delta_q/2$, and $0.503$ falls near a bin boundary, illustrating that worst-case error is bounded but not zero even for "round" values.

The mathematics of sampling emerged from communications engineering decades before digital imaging existed, then was carried directly into computer vision once cameras became digital.

Every digital camera, from smartphone sensors to satellite imaging systems, must respect this theory: sensor pixel pitch, lens optics, and optional anti-aliasing filters are jointly engineered around the Nyquist rate implied by the optics' resolving power. Video game rendering engines apply supersampling and multisample anti-aliasing (MSAA/FXAA) precisely to suppress jagged edges — a direct application of pre-filtering before rasterization "samples" the scene at pixel centers. Medical imaging (CT, MRI, ultrasound) relies on the sampling theorem to determine the minimum number of projections or k-space samples needed to reconstruct images without artifacts. Audio and video codecs use the same mathematics (1D and 3D analogues) for lossless and lossy compression pipelines. Deep convolutional networks that downsample feature maps (strided convolutions, pooling) can themselves reintroduce aliasing internally, motivating recent architecture work on anti-aliased downsampling layers. Downstream, Color Spaces define what quantized channel values represent perceptually, Image Histograms summarize the resulting quantized value distribution, Point Operations like contrast stretching operate directly on quantization levels, and Image Resampling and Warping must re-apply this exact sampling theory whenever an image is resized, rotated, or reprojected.

Ask the tutor: How does this same Nyquist argument change when we resample (resize or rotate) an already-digital image, rather than digitizing a continuous scene for the first time?