“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. This result, also known as the Petersen–Middleton theorem, is a generalization of the Nyquist–Shannon sampling theorem for sampling one-dimensional band-limited functions to higher-dimensional Euclidean spaces.

In essence, the Petersen–Middleton theorem shows that a wavenumber-limited function can be perfectly reconstructed from its values on an infinite lattice of points, provided the lattice is fine enough. The theorem provides conditions on the lattice under which perfect reconstruction is possible.

As with the Nyquist–Shannon sampling theorem, this theorem also assumes an idealization of any real-world situation, as it only applies to functions that are sampled over an infinitude of points. 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.

Preliminaries

The concept of a bandlimited function in one dimension can be generalized to the notion of a wavenumber-limited function in higher dimensions. Recall that the Fourier transform of an integrable function

on n-dimensional Euclidean space is defined as:

where x and ξ are n-dimensional vectors, and

is the inner product of the vectors. The function

is said to be wavenumber-limited to a set

if the Fourier transform satisfies

for

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

of the form

where {v₁, ..., v_n} is a basis for

. The reciprocal lattice

corresponding to

is defined by

where the vectors

are chosen to satisfy

. That is, if the vectors

form columns of a matrix

and

the columns of a matrix

, then

. An example of a sampling lattice in two dimensional space is a hexagonal lattice depicted in Figure 1. The corresponding reciprocal lattice is shown in Figure 2. The reciprocal lattice of a square lattice in two dimensions is another square lattice. In three dimensional space the reciprocal lattice of a

face-centered cubic (FCC) lattice is a hexagonal close-packed (HCP) lattice or a body centered cubic (BCC) lattice.

The theorem

Let

denote a lattice in

and

the corresponding reciprocal lattice. The theorem of Petersen and Middleton^[1] states that a function

that is wavenumber-limited to a set

can be exactly reconstructed from its measurements on

provided that the set

does not overlap with any of its shifted versions

where the shift x is any nonzero element of the reciprocal lattice

. In other words,

can be exactly reconstructed from its measurements on

provided that

for all

Reconstruction

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

, of the function

on the lattice

are sufficient to create a periodic summation of the function

. The result is:

where

represents the volume of the parallelepiped formed by the vectors {v₁, ..., v_n}. 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. If the original wavenumber-limited spectrum

is supported on the set

then the function

is supported on periodic repetitions of

shifted by points on the reciprocal lattice

. If the conditions of the Petersen-Middleton theorem are met, then the function

is equal to

for all

, and hence the original field can be exactly reconstructed from the samples. In this case the reconstructed field matches the original field and can be expressed in terms of the samples as

where

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

. This interpolation formula is the higher-dimensional equivalent of the Whittaker–Shannon interpolation formula.

As an example suppose that

is a circular disc. Figure 3 illustrates the support of

when the conditions of the Petersen-Middleton theorem are met. We see that the spectral repetitions do not overlap and hence the original spectrum can be exactly recovered.

Implications

Aliasing

The theorem gives conditions on sampling lattices for perfect reconstruction of the sampled. 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. In this case we say that the samples may be aliased. Again, consider the example in which

is a circular disc. 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. An example of aliasing is shown in the images of brick patterns in Figure 5. 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.

Optimal sampling lattices

One of the objects of interest in designing a sampling scheme for wavenumber-limited fields is to identify the configuration of points that leads to the minimum sampling density, i.e., the density of sampling points per unit spatial volume in

. Typically the cost for taking and storing the measurements is proportional to the sampling density employed. Often in practice, the natural approach to sample two-dimensional fields is to sample it at points on a rectangular lattice. However, this is not always the ideal choice in terms of the sampling density. 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

. For example, it can be shown that the lattice in

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

is the hexagonal lattice.^[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.^[6]^[7] Hex-splines^[8] are the generalization of B-splines for 2-D hexagonal lattices. 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.,

in above) of these lattices (which are zonotopes).^[10] This approach provides a closed-form explicit representation of

for general lattices, including optimal sampling lattices. This construction provides a generalization of the Lanczos filter in 1-D to the multidimensional setting for optimal lattices.^[10]

Applications

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.

References

1. ^¹D. P. Petersen and D. Middleton, "Sampling and Reconstruction of Wave-Number-Limited Functions in N-Dimensional Euclidean Spaces", Information and Control, vol. 5, pp. 279–323, 1962.
2. ^E. M. Stein and G. Weiss, "Introduction to Fourier Analysis on Euclidean Spaces", Princeton University Press, Princeton, 1971.
3. ^D. R. Mersereau, “The processing of hexagonally sampled two-dimensional signals,” Proceedings of the IEEE, vol. 67, no. 6, pp. 930 – 949, June 1979.
4. ^{{Cite journal | last1 = Kunsch | first1 = H. R. | last2 = Agrell | first2 = E. | last3 = Hamprecht | first3 = F. A. | doi = 10.1109/TIT.2004.840864 | title = Optimal Lattices for Sampling | journal = IEEE Transactions on Information Theory | volume = 51 | issue = 2 | pages = 634 | year = 2005 | pmid = | pmc = }}
5. ^J. H. Conway, N. J. A. Sloane. Sphere packings, lattices and groups. Springer, 1999.
6. ^A. Entezari. Optimal sampling lattices and trivariate box splines. [Vancouver, BC.]: Simon Fraser University, 2007. .
7. ^{{Cite journal | last1 = Entezari | first1 = A. | last2 = Van De Ville | first2 = D. | last3 = Moller | first3 = T. | doi = 10.1109/TVCG.2007.70429 | title = Practical Box Splines for Reconstruction on the Body Centered Cubic Lattice | journal = IEEE Transactions on Visualization and Computer Graphics | volume = 14 | issue = 2 | pages = 313–328 | year = 2008 | pmid = 18192712| pmc = | citeseerx = 10.1.1.330.3851 }}
8. ^{{Cite journal | last1 = Van De Ville | first1 = D. | last2 = Blu | first2 = T. | last3 = Unser | first3 = M. | last4 = Philips | first4 = W. | last5 = Lemahieu | first5 = I. | last6 = Van De Walle | first6 = R. | doi = 10.1109/TIP.2004.827231 | title = Hex-Splines: A Novel Spline Family for Hexagonal Lattices | journal = IEEE Transactions on Image Processing | volume = 13 | issue = 6 | pages = 758–772 | year = 2004 | pmid = 15648867| pmc = }}
9. ^{{Cite journal | last1 = Mirzargar | first1 = M. | last2 = Entezari | first2 = A. | doi = 10.1109/TSP.2010.2051808 | title = Voronoi Splines | journal = IEEE Transactions on Signal Processing | volume = 58 | issue = 9 | pages = 4572 | year = 2010 | pmid = | pmc = }}
10. ^¹{{Cite journal | last1 = Ye | first1 = W. | last2 = Entezari | first2 = A. | doi = 10.1109/TIP.2011.2162421 | title = A Geometric Construction of Multivariate Sinc Functions | journal = IEEE Transactions on Image Processing | volume = 21 | issue = 6 | pages = 2969–2979 | year = 2012 | pmid = 21775264| pmc = }}