View source for Papoulis-Marks-Cheung Approach

{{Short description|Theorem in sampling theory}}

The Papoulis-Marks-Cheung approach<ref name=":0">{{Cite journal |last1=Prelee |first1=Matthew A. |last2=Neuhoff |first2=David L. |date=May 2016 |title=Multidimensional Manhattan Sampling and Reconstruction |journal=IEEE Transactions on Information Theory |volume=62 |issue=5 |pages=2772–2787 |doi=10.1109/TIT.2016.2542081 |s2cid=3199882 |issn=0018-9448|doi-access=free |arxiv=1502.01694 }}</ref> is a theorem in multidimensional Shannon sampling theory that shows that the sampling density of a two-dimensional bandlimited function can be reduced to the [[Support (mathematics)|support]] of the [[Fourier transform]] of the function. Applying a multidimensional generalization of a theorem by [[Athanasios Papoulis]],<ref name=":1">{{Cite journal |last=Papoulis |first=A. |date=November 1977 |title=Generalized sampling expansion |url=https://ieeexplore.ieee.org/document/1084284 |journal=IEEE Transactions on Circuits and Systems |language=en |volume=24 |issue=11 |pages=652–654 |doi=10.1109/TCS.1977.1084284 |issn=0098-4094}}</ref> the approach was first proposed by [[Robert J. Marks II]] and Kwang Fai Cheung.<ref>{{Cite journal |last=Marks |first=Robert J. |date=1986-02-01 |title=Multidimensional-signal sample dependency at Nyquist densities |url=https://opg.optica.org/josaa/abstract.cfm?uri=josaa-3-2-268 |journal=JOSA A |language=EN |volume=3 |issue=2 |pages=268–273 |doi=10.1364/JOSAA.3.000268 |bibcode=1986JOSAA...3..268M |issn=1520-8532}}</ref><ref name=":2">{{Cite journal |last1=Cheung |first1=Kwan F. |last2=Marks |first2=Robert J. |date=1990-01-01 |title=Imaging sampling below the Nyquist density without aliasing |url=https://opg.optica.org/josaa/abstract.cfm?uri=josaa-7-1-92 |journal=JOSA A |language=EN |volume=7 |issue=1 |pages=92–105 |doi=10.1364/JOSAA.7.000092 |bibcode=1990JOSAA...7...92C |issn=1520-8532}}</ref> The approach has been called "elegant,"<ref>{{Cite book |last1=Gardos |first1=T.R. |last2=Mersereau |first2=R.M. |title=&#91;Proceedings&#93; ICASSP 91: 1991 International Conference on Acoustics, Speech, and Signal Processing |chapter=FIR filtering of images on a lattice with periodically deleted samples |date=1991 |chapter-url=https://ieeexplore.ieee.org/document/151002 |pages=2873–2876 vol.4 |doi=10.1109/ICASSP.1991.151002|isbn=0-7803-0003-3 |s2cid=121408946 }}</ref> "remarkably" closed,<ref>{{Cite book |last1=Bresler |first1=Y. |last2=Feng |first2=Ping |title=Proceedings of 3rd IEEE International Conference on Image Processing |chapter=Spectrum-blind minimum-rate sampling and reconstruction of 2-D multiband signals |date=1996 |chapter-url=https://ieeexplore.ieee.org/document/559595 |volume=1 |pages=701–704 vol.1 |doi=10.1109/ICIP.1996.559595|isbn=0-7803-3259-8 |s2cid=44441155 }}</ref> and "interesting."<ref>{{Cite journal |last1=Herley |first1=Cormac |last2=Wong |first2=Ping Wah |last3=Member |first3=Senior |date=1999 |title=Minimum rate sampling and reconstruction of signals with arbitrary frequency support |journal=IEEE Trans. Inform. Theory |volume=45 |issue=5 |pages=1555–1564|doi=10.1109/18.771158 |citeseerx=10.1.1.83.8638 }}</ref>

== The Theorem ==
The [[Multidimensional transform|two-dimensional Fourier transform]], or frequency spectrum, of a [[Function (mathematics)|function]] <math>f(x,y)</math> is<ref>{{Cite book |last=Cohen |first=Leon |title=Time-frequency analysis |date=1995 |publisher=Prentice Hall PTR |isbn=0-13-594532-1 |location=Englewood Cliffs, N.J |oclc=31516509}}</ref> <math display="block">F(u_x,y_y) = \iint\limits_{x,y} f(x,y){\rm e}^{-i2\pi(xu_x+yu_y)}\operatorname{d}\!x\operatorname{d}\!y</math>where <math>u_x</math> and <math>u_x</math> are the spatial frequencies corresponding to <math>x</math> and <math>y</math>. When <math>x</math> and <math>y</math> are lengths, spatial frequency has units of cycles per unit length.

Prelee and Neuhoff<ref name=":0" /> describe the Papoulis-Marks-Cheung approach as follows.

{{Blockquote|text="Marks and Cheung focused on images with a given spectral support region and an initial base sampling lattice such that the induced spectral replicas of this support region do not overlap. They then showed that cosets of some sublattice could be removed from the base lattice until the sampling density was minimal … or approached minimal ... [This] allows the sampling rate to be reduced until it equals or approaches … [a] minimum." In this context, the limit is the area of the support of the spectrum."}}

In deriving their result, Marks and Cheung relied on Papoulis' generalized sampling expansion.<ref name=":1" /><ref name=":3">{{Cite book |last=Marks |first=Robert J. II |title=Handbook of Fourier analysis & its applications |date=2009 |publisher=Oxford University Press |isbn=978-0-19-533592-7 |location=Oxford |oclc=227191901}}</ref>

== Explanation ==
[[File:Papoulis-Marks-Cheung_Approach_Figure_1.jpg|thumb|Figure 1: (Left) Half circle spectral [[Support (mathematics)|support]]. Outside of the half circle, the spectrum is identically zero. (Right) Nonoverlapping [[Aliasing|nonaliased]] rectangular replication of the support of the spectrum on the left.]]
The Papoulis-Marks-Cheung approach is best explained by example. Consider from Figure 1 the half circle shown on the right half plane. A signal's spectrum, <math>F(u_x,u_y)</math>, is zero outside the half circle. Inside the circle, the spectrum' is arbitrary but is well behaved.<ref name=":3" /> The half-circle, with unit radius, has an area of  <math>\pi / 2 = 1.5708</math> (cycles per unit length) squared.

According to the Papoulis-Marks-Cheung approach, the sampling density for the image <math>f(x,y)</math> can be reduced to <math>1.5708</math> samples per unit area. The Papoulis-Marks-Cheung approach informs how to do this.

To the right in Figure 1 is pictured a rectangular replication of the half circle which occurs when the two-dimensional function is sampled at spatial locations shown in Figure 2. 
[[File:Papoulis-Marks-Cheung_Approach_Figure_2.jpg|thumb|Figure 2: This sampling geometry gives rise to the spectral replication on the right in Figure 1.]]
This replication is a consequence of the [[Multidimensional sampling|multidimensional sampling theorem]] that shows that the sampling of a two-dimensional signal in the spatial <math>(x,y)</math> domain results in spectrum replication in the Fourier domain. If the uniform sampling density were lower, the replications would overlap and an attempt at reconstruction of the original function would result in image [[aliasing]]. The [[Nyquist rate|sampling density]] to achieve this is equal to the area of the rectangular lattice cell of the spectrum replication. The corresponding area of the rectangle used in the replication is equal to <math>2</math> (cycles per unit length) squared. As confirmed by Figure 2, the sampling density required to achieve the spectral replication is therefore <math>2</math> samples per unit area. The Papoulis-Marks-Cheung approach says that this sampling density can be reduced to the area of the half circle, namely from <math>2</math> to <math>1.5708</math> samples per unit area. 
[[File:Papoulis-Marks-Cheung_Approach_Figure_3.jpg|thumb|Figure 3: The half-circle spectrum support divided into 32 squares.]]
To see how this reduction happens, consider Figure 3 where the <math>1\times 2</math> rectangular lattice cell is divided into <math>32</math> identical squares. Note that two of these squares lie totally in an area where the spectral replication is identically zero. These squares are shaded light green. Think of each of <math>32</math> squares as spectra of <math>32</math> different two-dimensional signals. All of the samples for the signals corresponding to the light green areas are zero and do not have to be considered. The area of the two green squares is <math>2/32 = 1/16 = 0.0625</math>. Since the samples corresponding to these squares do not have to be considered (they are all zero), the overall sampling density is reduced from <math>2</math> samples per unit area to <math>2-0.0625=1.9375</math> samples per unit area. 
[[File:Papoulis-Marks-Cheung_Approach_Figure_4.jpg|thumb|Figure 4: Reduction in sampling density: The red dots are locations where samples need not be taken.]]
The corresponding reduction in sampling density is shown in Figure 4 where the red dots are locations where samples need not be taken. A single cell containing one red dot is shown shaded. The area of the cell is The corresponding reduction in sampling density is shown in Figure 4 where the red dots are locations where samples need not be taken. A single cell containing one red dot is shown shaded. The area of the cell is <math>16</math> units. The sampling density is therefore, as also seen from the areas of two green squares in Figure 3, reduced by <math>1/16</math> samples per unit area.

== Extension ==
In the previous example, the squares in Figure 3 can be made arbitrarily small and increased in number so that, asymptotically, all of the area equal to zero can be covered. Thus, the sampling density can be reduced to the support of the spectrum, i.e., to the area where the spectrum is not identically zero.

The Papoulis-Marks-Cheung approach can straightforwardly be generalized to higher dimensions. Also, replication geometry need not be rectangular but can be any shape that will tile the entire <math>(x,y)</math> plane such as parallelograms and hexagons.<ref>{{Cite book |last=Dudgeon |first=Dan E. |title=Multidimensional digital signal processing |date=1984 |publisher=Prentice-Hall |others=Russell M. Mersereau |isbn=0-13-604959-1 |location=Englewood Cliffs, NJ |oclc=9282699}}</ref>

A more detailed mathematical description of the Papoulis-Marks-Cheung approach is available in the original paper by Marks and Cheung<ref name=":2" /> and their derivative work.<ref>{{cite book |last=Cheung |first=Kwang F. |title=Advanced Topics in Shannon Sampling and Interpolation Theory |date=Dec 6, 2012 |publisher=Springer Science & Business Media |isbn=978-1-4613-9757-1 |editor-last=Marks |editor-first=Robert J. II |chapter=A Multidimensional Extension of Papoulis' Generalized Sampling Expansion with Application in Minimum Sampling Density}}</ref><ref name=":3" />

== References ==
{{reflist}}

[[Category:Theorems in Fourier analysis]]