Multidimensional sampling: Difference between revisions

Revision as of 20:13, 7 February 2020

Latest revision as of 05:44, 12 July 2024

(8 intermediate revisions by 7 users not shown)

Line 1:

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<ref name="petmid62">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.</ref> on conditions for perfectly reconstructing a [[wavenumber]]-limited function from its measurements on a discrete [[Lattice (group)|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 space]]s.

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.

Line 22:

</math>

where the vectors <math>u_i</math> are chosen to satisfy <math>\langle u_i, v_j \rangle = \delta_{ij}</math>. That is, if the vectors <math>u_i</math> form columns of a matrix <math>A</math> and <math>v_i</math> the columns of a matrix <math>B</math>, then <math>A=B^{-T}</math>. 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

[[Close-packing of equal spheres#FCC_and_HCP_Lattices|face-centered cubic (FCC) lattice]] is a [[Close-packing of equal spheres#FCC_and_HCP_Lattices|hexagonal close-packed (HCP) lattice]] or a body centered cubic (BCC) lattice.

==The theorem==

Let <math>\Lambda</math> denote a lattice in <math>\Re^n</math> and <math>\Gamma</math> the corresponding reciprocal lattice. The theorem of Petersen and Middleton<ref name="petmid62" /> states that a function <math>f(\cdot)</math> that is wavenumber-limited to a set <math>\Omega \subset \Re^n</math> can be exactly reconstructed from its measurements on <math>\Lambda</math> provided that the set <math>\Omega</math> does not overlap with any of its shifted versions <math>\Omega + x </math> where the shift ''x'' is any nonzero element of the reciprocal lattice <math>\Gamma</math>. In other words, <math>f(\cdot)</math> can be exactly reconstructed from its measurements on <math>\Lambda</math> provided that <math>\Omega \cap \{x+y:y\in\Omega\} = \phiemptyset </math> for all <math>x \in \Gamma\setminus\{0\}</math>.

==Reconstruction==

[[Image:Unaliased sampled spectrum in 2D.png|thumb|Fig. 3: Support of the sampled spectrum <math>\hat f_s(\cdot)</math> obtained by hexagonal sampling of a two-dimensional function wavenumber-limited to a circular disc. The blue circle represents the support <math>\Omega</math> 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.|right|300px]]

The generalization of the [[Poisson summation formula]] to higher dimensions <ref name="stewei71">E. M. Stein and G. Weiss, "Introduction to Fourier Analysis on Euclidean Spaces", Princeton University Press, Princeton, 1971.</ref> can be used to show that the samples, <math>\{f(x): x \in \Lambda\} </math>, of the function <math>f(\cdot)</math> on the lattice <math>\Lambda</math> are sufficient to create a [[periodic summation]] of the function <math>\hat f(\cdot)</math>. The result is:

{{NumBlk|:|<math>\hat f_s(\xi)\ \stackrel{\mathrm{def}}{=} \sum_{y \in \Gamma} \hat f\left(\xi - y\right) = \sum_{x \in \Lambda} |\Lambda|f(x) \ e^{-i 2\pi \langle x, \xi \rangle},</math>|{{EquationRef|Eq.1}}}}

Line 52:

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.

S. P. Efimov from [[Bauman Moscow State Technical University]] in 1978 y. found an approach to ease the restrictions for spectrum ___domain.<ref>{{cite journal |last1=Efimov |first1=Sergei |title=Reconstruction of a field with finite-spectrum by samples of signals of filters |journal=Problemy Peredaci Informacii |date=1978 |volume=14 |issue=2 |pages=53-60 |url=https://mi.mathnet.ru/eng/ppi/p1534}}</ref> He considered N identical sampling lattices to be shifted arbitrarily to each other. Optimal sampling is valid for spectrum ___domain that shifted versions of is close-packed N times on reciprocal lattice. Therefore, ring can be overlapped by a set of hexagons instead of one. [[JWST]] telescope array consists from 18 hexagons. Sampling on 18 shifted lattices is possible for 2-d Fourier transform of the array signal (i. e. for emitted signal).

===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 <math>\Re^n</math>. 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 [[Lattice (group)|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 <math>\Omega \subset \Re^d</math>. For example, it can be shown that the lattice in <math>\Re^2</math> with minimum spatial density of points that admits perfect reconstructions of fields wavenumber-limited to a circular disc in <math>\Re^2</math> is the hexagonal lattice.<ref name="mer79">D. R. Mersereau, “The processing of hexagonally sampled two-dimensional signals,” Proceedings of the IEEE, vol. 67, no. 6, pp. 930 – 949, June 1979.</ref> As a consequence, hexagonal lattices are preferred for sampling [[Isotropy|isotropic fields]] in <math>\Re^2</math>.

Optimal sampling lattices have been studied in higher dimensions.<ref>{{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 = | url = https://research.chalmers.se/en/publication/11977 }}</ref> Generally, optimal [[sphere packing]] lattices are ideal for sampling smooth stochastic processes while optimal sphere covering lattices<ref>J. H. Conway, N. J. A. Sloane. Sphere packings, lattices and groups. Springer, 1999.</ref> are ideal for sampling rough stochastic processes.

Since optimal lattices, in general, are non-separable, designing [[interpolation]] and [[reconstruction filter]]s requires non-tensor-product (i.e., non-separable) filter design mechanisms. [[Box spline]]s provide a flexible framework for designing such non-separable reconstruction [[Finite impulse response|FIR]] filters that can be geometrically tailored for each lattice.<ref>A. Entezari. Optimal sampling lattices and trivariate box splines. [Vancouver, BC.]: Simon Fraser University, 2007. <http://summit.sfu.ca/item/8178>.</ref><ref name="fourDir">{{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 }}</ref> Hex-splines<ref>{{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| pmcbibcode = 2004ITIP...13..758V | url = http://infoscience.epfl.ch/record/63112 }}</ref> are the generalization of [[B-splines]] for 2-D hexagonal lattices. Similarly, in 3-D and higher dimensions, Voronoi splines<ref>{{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 | pmidbibcode = | pmc =2010ITSP...58.4572M }}</ref> 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 zone]]s (i.e., <math>\Omega</math> in above) of these lattices (which are [[zonohedron|zonotopes]]).<ref name="mdsinc">{{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| pmcbibcode = 2012ITIP...21.2969Y }}</ref> This approach provides a closed-form explicit representation of <math>\check \chi_\Omega(\cdot)</math> 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.<ref name="mdsinc" />

==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.<ref>{{Cite book |last=Bardan |first=V. |title=69th EAGE Conference and Exhibition incorporating SPE EUROPEC 2007 |date=2007-06-11 |chapter=The Petersen-Middleton Theorem and Sampling of Seismic Data |chapter-url=https://www.earthdoc.org/content/papers/10.3997/2214-4609.201401831 |language=en |publisher=European Association of Geoscientists & Engineers |pages=cp |doi=10.3997/2214-4609.201401831 |isbn=978-90-73781-54-2}}</ref>

==References==