Multidimensional sampling

In digital signal processing, multidimensional sampling is the process of converting a function of a multidimensional variable into a discrete collection of values of the function measured on a discrete set of points.

This article presents the basic result due to Petersen and Middleton[1] on conditions for perfectly reconstructing a wavenumber-limited function from its measurements on a discrete lattice of points.

The theorem provides conditions on the lattice under which perfect reconstruction is possible.

Perfect reconstruction is mathematically possible for the idealized model but only an approximation for real-world functions and sampling techniques, albeit in practice often a very good one.

Similarly, the configuration of uniformly spaced sampling points in one-dimension can be generalized to a lattice in higher dimensions.

The generalization of the Poisson summation formula to higher dimensions[2] can be used to show that the samples,

represents the volume of the parallelepiped formed by the vectors {v1, ..., vn}.

This periodic function is often referred to as the sampled spectrum and can be interpreted as the analogue of the discrete-time Fourier transform (DTFT) in higher dimensions.

is the inverse Fourier transform of the characteristic function of the set

If the lattices are not fine enough to satisfy the Petersen-Middleton condition, then the field cannot be reconstructed exactly from the samples in general.

If the Petersen-Middleton conditions do not hold, the support of the sampled spectrum will be as shown in Figure 4.

In this case the spectral repetitions overlap leading to aliasing in the reconstruction.

A simple illustration of aliasing can be obtained by studying low-resolution images.

A gray-scale image can be interpreted as a function in two-dimensional space.

The image shows the effects of aliasing when the sampling theorem's condition is not satisfied.

If the lattice of pixels is not fine enough for the scene, aliasing occurs as evidenced by the appearance of the Moiré pattern in the image obtained.

The image in Figure 6 is obtained when a smoothened version of the scene is sampled with the same lattice.

In this case the conditions of the theorem are satisfied and no aliasing occurs.

Typically the cost for taking and storing the measurements is proportional to the sampling density employed.

The theorem of Petersen and Middleton can be used to identify the optimal lattice for sampling fields that are wavenumber-limited to a given set

with minimum spatial density of points that admits perfect reconstructions of fields wavenumber-limited to a circular disc in

[3] As a consequence, hexagonal lattices are preferred for sampling isotropic fields in

Optimal sampling lattices have been studied in higher dimensions.

[4] Generally, optimal sphere packing lattices are ideal for sampling smooth stochastic processes while optimal sphere covering lattices[5] are ideal for sampling rough stochastic processes.

Since optimal lattices, in general, are non-separable, designing interpolation and reconstruction filters requires non-tensor-product (i.e., non-separable) filter design mechanisms.

Box splines provide a flexible framework for designing such non-separable reconstruction FIR filters that can be geometrically tailored for each lattice.

Similarly, in 3-D and higher dimensions, Voronoi splines[9] provide a generalization of B-splines that can be used to design non-separable FIR filters which are geometrically tailored for any lattice, including optimal lattices.

Explicit construction of ideal low-pass filters (i.e., sinc functions) generalized to optimal lattices is possible by studying the geometric properties of Brillouin zones (i.e.,

This construction provides a generalization of the Lanczos filter in 1-D to the multidimensional setting for optimal lattices.

[10] The Petersen–Middleton theorem is useful in designing efficient sensor placement strategies in applications involving measurement of spatial phenomena such as seismic surveys, environment monitoring and spatial audio-field measurements.

Fig. 1: A hexagonal sampling lattice and its basis vectors v 1 and v 2
Fig. 2: The reciprocal lattice corresponding to the lattice of Fig. 1 and its basis vectors u 1 and u 2 (figure not to scale).
Fig. 3: Support of the sampled spectrum obtained by hexagonal sampling of a two-dimensional function wavenumber-limited to a circular disc. The blue circle represents the support of the original wavenumber-limited field, and the green circles represent the repetitions. In this example the spectral repetitions do not overlap and hence there is no aliasing. The original spectrum can be exactly recovered from the sampled spectrum.
Fig. 4: Support of the sampled spectrum obtained by hexagonal sampling of a two-dimensional function wavenumber-limited to a circular disc. In this example, the sampling lattice is not fine enough and hence the discs overlap in the sampled spectrum. Thus the spectrum within represented by the blue circle cannot be recovered exactly due to the overlap from the repetitions (shown in green), thus leading to aliasing.
Fig. 5: Spatial aliasing in the form of a Moiré pattern .
Fig. 6: Properly sampled image of brick wall.