Misplaced Pages

The Papoulis-Marks-Cheung approach 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, the approach was first proposed by Robert J. Marks II and Kwang Fai Cheung. The approach has been called "elegant," "remarkably" closed, and "interesting."

The Theorem

The two-dimensional Fourier transform, or frequency spectrum, of a function ${\displaystyle f(x,y)}$ is $${\displaystyle 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}$$where ${\displaystyle u_{x}}$ and ${\displaystyle u_{x}}$ are the spatial frequencies corresponding to ${\displaystyle x}$ and ${\displaystyle y}$. When ${\displaystyle x}$ and ${\displaystyle y}$ are lengths, spatial frequency has units of cycles per unit length.

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

"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 ... allows the sampling rate to be reduced until it equals or approaches … 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.

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, ${\displaystyle 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  ${\displaystyle \pi /2=1.5708}$ (cycles per unit length) squared.

According to the Papoulis-Marks-Cheung approach, the sampling density for the image ${\displaystyle f(x,y)}$ can be reduced to ${\displaystyle 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 ${\displaystyle (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 ${\displaystyle 2}$ (cycles per unit length) squared. As confirmed by Figure 2, the sampling density required to achieve the spectral replication is therefore ${\displaystyle 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 ${\displaystyle 2}$ to ${\displaystyle 1.5708}$ samples per unit area.

To see how this reduction happens, consider Figure 3 where the ${\displaystyle 1\times 2}$ rectangular lattice cell is divided into ${\displaystyle 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 ${\displaystyle 32}$ squares as spectra of ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 2}$ samples per unit area to ${\displaystyle 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 ${\displaystyle 16}$ units. The sampling density is therefore, as also seen from the areas of two green squares in Figure 3, reduced by ${\displaystyle 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 ${\displaystyle (x,y)}$ plane such as parallelograms and hexagons.

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.

References

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

• Theorems in Fourier analysis