Papoulis-Marks-Cheung Approach Explained

The Papoulis-Marks-Cheung approach^[1] 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 of the Fourier transform of the function. Applying a multidimensional generalization of a theorem by Athanasios Papoulis,^[2] the approach was first proposed by Robert J. Marks II and Kwang Fai Cheung.^{[3] [4]} The approach has been called "elegant,"^[5] "remarkably" closed,^[6] and "interesting."^[7]

The Theorem

f(x,y)  is^[8] $$F(u\_x,y\_y)\; =\; \backslash iint\backslash limits\_\; f(x,y)^\backslash operatorname\backslash !x\backslash operatorname\backslash !y$$where u _{x}  and u _{x}  are the spatial frequencies corresponding to x  and y . When x  and y are lengths, spatial frequency has units of cycles per unit length.

Prelee and Neuhoff describe the Papoulis-Marks-Cheung approach as follows.

In deriving their result, Marks and Cheung relied on Papoulis' generalized sampling expansion.^[9]

Explanation

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,

F(u _{x,u} _{y)} , is zero outside the half circle. Inside the circle, the spectrum' is arbitrary but is well behaved. The half-circle, with unit radius, has an area of  \pi / 2 = 1 . 5708 (cycles per unit length) squared.

According to the Papoulis-Marks-Cheung approach, the sampling density for the image

f(x,y)  can be reduced to 1 . 5708 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. This replication is a consequence of the multidimensional sampling theorem that shows that the sampling of a two-dimensional signal in the spatial

(x,y)  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 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 2 (cycles per unit length) squared. As confirmed by Figure 2, the sampling density required to achieve the spectral replication is therefore 2 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 2 to 1 . 5708 samples per unit area. To see how this reduction happens, consider Figure 3 where the 1 x 2 rectangular lattice cell is divided into 32 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 32 squares as spectra of 32 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 2 / 32 = 1 / 16 = 0 . 0625 . Since the samples corresponding to these squares do not have to be considered (they are all zero), the overall sampling density is reduced from 2 samples per unit area to 2-0 . 0625=1 . 9375 samples per unit area. 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 16 units. The sampling density is therefore, as also seen from the areas of two green squares in Figure 3, reduced by 1 / 16 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

(x,y)  plane such as parallelograms and hexagons.^[10]

A more detailed mathematical description of the Papoulis-Marks-Cheung approach is available in the original paper by Marks and Cheung and their derivative work.^[11]

Notes and References

1. Prelee . Matthew A. . Neuhoff . David L. . May 2016 . Multidimensional Manhattan Sampling and Reconstruction . IEEE Transactions on Information Theory . 62 . 5 . 2772–2787 . 10.1109/TIT.2016.2542081 . 3199882 . 0018-9448. free . 1502.01694 .
2. Papoulis . A. . November 1977 . Generalized sampling expansion . IEEE Transactions on Circuits and Systems . en . 24 . 11 . 652–654 . 10.1109/TCS.1977.1084284 . 0098-4094.
3. Marks . Robert J. . 1986-02-01 . Multidimensional-signal sample dependency at Nyquist densities . JOSA A . EN . 3 . 2 . 268–273 . 10.1364/JOSAA.3.000268 . 1986JOSAA...3..268M . 1520-8532.
4. Cheung . Kwan F. . Marks . Robert J. . 1990-01-01 . Imaging sampling below the Nyquist density without aliasing . JOSA A . EN . 7 . 1 . 92–105 . 10.1364/JOSAA.7.000092 . 1990JOSAA...7...92C . 1520-8532.
5. Book: Gardos . T.R. . Mersereau . R.M. . [Proceedings] ICASSP 91: 1991 International Conference on Acoustics, Speech, and Signal Processing . FIR filtering of images on a lattice with periodically deleted samples . 1991 . https://ieeexplore.ieee.org/document/151002 . 2873–2876 vol.4 . 10.1109/ICASSP.1991.151002. 0-7803-0003-3 . 121408946 .
6. Book: Bresler . Y. . Feng . Ping . Proceedings of 3rd IEEE International Conference on Image Processing . Spectrum-blind minimum-rate sampling and reconstruction of 2-D multiband signals . 1996 . https://ieeexplore.ieee.org/document/559595 . 1 . 701–704 vol.1 . 10.1109/ICIP.1996.559595. 0-7803-3259-8 . 44441155 .
7. Herley . Cormac . Wong . Ping Wah . Member . Senior . 1999 . Minimum rate sampling and reconstruction of signals with arbitrary frequency support . IEEE Trans. Inform. Theory . 45 . 5 . 1555–1564. 10.1109/18.771158 . 10.1.1.83.8638 .
8. Book: Cohen, Leon . Time-frequency analysis . 1995 . Prentice Hall PTR . 0-13-594532-1 . Englewood Cliffs, N.J . 31516509.
9. Book: Marks, Robert J. II . Handbook of Fourier analysis & its applications . 2009 . Oxford University Press . 978-0-19-533592-7 . Oxford . 227191901.
10. Book: Dudgeon, Dan E. . Multidimensional digital signal processing . 1984 . Prentice-Hall . Russell M. Mersereau . 0-13-604959-1 . Englewood Cliffs, NJ . 9282699.
11. Book: Cheung, Kwang F. . Advanced Topics in Shannon Sampling and Interpolation Theory . Dec 6, 2012 . Springer Science & Business Media . 978-1-4613-9757-1 . Marks . Robert J. II . A Multidimensional Extension of Papoulis' Generalized Sampling Expansion with Application in Minimum Sampling Density.