Content deleted Content added
Shantham11 (talk | contribs) No edit summary |
Shantham11 (talk | contribs) Restructuring. Adding reconstruction formula. |
||
Line 25:
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"></ref> states that a function ''f(.)'' 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, ''f(.)'' can be exactly reconstructed from its measurements on <math>\Lambda</math> provided that <math>\Omega \cap \{x+y:y\in\Omega\} = \phi </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(.)</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 ''f(.)'' on the lattice <math>\Lambda</math> are sufficient to create a [[periodic summation]] of the function <math>\hat f(.)</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}}}}▼
where <math>|\Lambda| </math> represents the volume of the [[parallelepiped]] formed by the vectors {''v''<sub>1</sub>, ..., ''v''<sub>''n''</sub>}. 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 <math>\hat f(.)</math> is supported on the set <math>\Omega</math> then the function <math>\hat f_s(.)</math> is supported on periodic repetitions of <math>\Omega</math> shifted by points on the reciprocal lattice <math>\Gamma</math>. If the conditions of the Petersen-Middleton theorem are met, then the function <math>\hat f_s(\xi)</math> is equal to <math>\hat f(\xi)</math> for all <math>\xi \in \Omega</math>, and hence the original field can be exactly reconstructed from the samples. In this case
{{NumBlk|:|<math>f(x) = \sum_{y \in \Lambda} |\Lambda| f(y) \check \chi_\Omega(x - y)</math>,|{{EquationRef|Eq.2}}}}
where <math>\check \chi_\Omega(.)</math> is the inverse Fourier transform of the [[Indicator function|characteristic function]] of the set <math>\Omega</math>. This interpolation formula is the higher-dimensional equivalent of the [[Whittaker–Shannon interpolation formula]].
As an example suppose that <math>\Omega</math> is a circular disc. Figure 3 illustrates the support of <math>\hat f_s(.)</math> 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==
Line 30 ⟶ 42:
===Aliasing===
{{main|Aliasing}}
▲[[Image:Unaliased_sampled_spectrum_in_2D.png|thumb|Fig. 3: Support of the sampled spectrum <math>\hat f_s(.)</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]]
[[Image:Aliased_sampled_spectrum_in_2D.png|thumb|Fig. 4: Support of the sampled spectrum <math>\hat f_s(.)</math> obtained by hexagonal sampling of a two-dimensional function wavenumber-limited to a circular disc. In this example, the sampling lattice is not fine enough and hence the discs overlap in the sampled spectrum. Thus the spectrum within <math>\Omega</math> represented by the blue circle cannot be recovered exactly due to the overlap from the repetitions (shown in green), thus leading to aliasing.|right|300px]]
[[File:Moire pattern of bricks small.jpg|thumb|205px|Fig. 5: Spatial aliasing in the form of a [[Moiré pattern]].]]
[[File:Moire pattern of bricks.jpg|thumb|205px|Fig. 6: Properly sampled image of brick wall.]]
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 [[Aliasing|aliased]]. Again, consider the example in which <math>\Omega</math> 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.
▲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 ''f(.)'' on the lattice <math>\Lambda</math> are sufficient to create a [[periodic summation]] of the function <math>\hat f(.)</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}}}}
▲where <math>|\Lambda| </math> represents the volume of the [[parallelepiped]] formed by the vectors {''v''<sub>1</sub>, ..., ''v''<sub>''n''</sub>}. 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 <math>\hat f(.)</math> is supported on the set <math>\Omega</math> then the function <math>\hat f_s(.)</math> is supported on periodic repetitions of <math>\Omega</math> shifted by points on the reciprocal lattice <math>\Gamma</math>. If the conditions of the Petersen-Middleton theorem are met, then the function <math>\hat f_s(\xi)</math> is equal to <math>\hat f(\xi)</math> for all <math>\xi \in \Omega</math>, and hence the original field can be exactly reconstructed from the samples. In this case there is no aliasing in the reconstruction. As an example suppose that <math>\Omega</math> is a circular disc. Figure 3 illustrates the support of <math>\hat f_s(.)</math> when the conditions of the Petersen-Middleton theorem are met. We see that the spectral repetitions do not overlap. Figure 4 shows the scenario where the conditions are not met. 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.
| |||