** **

** **

The Fourier transform of a sequence is in general complex-valued, and the unique representation of a sequence in the Fourier transform domain requires both the phase and magnitude of the Fourier transform. It is often desirable to synthesize or reconstruct a signal from only partial Fourier domain information.

The Fourier transform of h(n_{1},
n_{2}) is said to converge to _{} in the mean square sense when

_{}

Consider a 2-D sequence x(n_{1},n_{2})
with Fourier transform _{}so that

_{}
(1.42)

It has been observed that a straightforward signal
synthesis from the Fourier transform phase _{} alone often
captures most of the intelligibility of the original signal x(n_{1},n_{2}).
A straightforward synthesis from the Fourier transform magnitude _{} alone,
however, does not generally capture the original signal’s intelligibility. To
illustrate this, we synthesize the phase-only signal x_{P}(n_{1},n_{2})
and the magnitude-only signal x_{m}(n_{1},n_{2}) by

_{}
(1.43)

_{}
(1.44)

where F^{-1}[.] represents the inverse Fourier
transform operation. In phase-only signal synthesis, the correct phase is
combined with an arbitrary constant magnitude. In the magnitude-only signal
synthesis, the correct magnitude is combined with an arbitrary constant phase.
In this synthesis, _{} often
preserves the intelligibility of _{} while _{}does not. An example of this is shown in
Figure 1.31. Figure 1.31(a) shows an original image _{}, and Figures 1.31(b) and (c)
show _{}** **and
_{}, respectively.

An experiment which more dramatically illustrates the
observation that phase-only signal synthesis captures more of the signal
intelligibility than magnitude-only synthesis can be performed as follows.
Consider two images _{}and
_{}. From these
two images. we synthesize two other images _{}and _{}by

_{}
(1.45)

_{}
(1.46)

In this experiment, _{} captures the intelligibility of _{}, while _{}captures the
intelligibility of _{}.
An example is shown in Figure 1.32.

Figures 1.32(a) and (b) show the two images _{}and _{} and Figures 1.32(c)
and (d) show the two images _{} and _{}.

The high intelligibility of phase-only synthesis
raises the possibility of exactly reconstructing a signal _{} from its Fourier transform
phase _{}. This is known as the **magnitude-retrieval problem**. In fact,
it has been shown that a sequence _{} is uniquely specified within a scale
factor if x(n_{1},n_{2}) is real and has finite extent, and if
its Fourier transform cannot be factored as a product of lower-order
polynomials in _{} and _{}. Typical images _{} are real and have
finite regions of support. In addition, the fundamental theorem of algebra does
not apply to 2-D polynomials, and their Fourier transforms cannot generally be
factored as products of lower-order polynomials in _{} and _{}. Typical
images, then, are uniquely specified within a scale factor by the Fourier transform
phase alone.

Two approaches to reconstructing a
sequence from its Fourier transform phase alone have been considered. The first
approach leads to a closed-form solution and the second to an iterative
procedure. In the first approach, _{} is expressed as

_{}
(1.47)

where R_{x} is the region of support of _{}. Rewriting (1.47), we
have

_{}(1.48)

Equation (1.48) is a linear equation for the unknown
values in _{} for
each frequency _{}. If there are N^{2 }unknown
values in _{},
we can obtain a set of N^{2 }linear equations for _{} by sampling _{} at N^{2
}points. If the frequencies are sampled at distinctly different points,
noting that _{} is an odd function and is periodic with a period of 2p x 2p. The solution to the set
of N linear equations can be shown to be k_{}, where k is an arbitrary real scaling
factor. An example of signal reconstruction from phase using (1.48) is shown in
Figure 1.33. Figure 1.33(a) shows an image of 16 x 16 pixels, and Figure
1.33(b) shows the reconstruction. The scaling factor of the reconstructed
sequence in the figure is chosen such that the reconstruction will match the
original sequence.

The reconstruction algorithm discussed above is reasonable for a small size image, but is not practical for an image of typical size. For example, reconstructing an image of 512 x 512 pixels using (1.48) requires the solution of approximately a quarter of a million linear equations. An alternate approach is to recognize that the solution to the phase-only reconstruction problem must satisfy constraints in both the spatial and frequency domains. Specifically, the solution

· must be real,

· must be zero outside the known region of support, and

· must have a nonfactorable Fourier transform.

In addition, the phase of the Fourier transform of the
solution must be the same as the _{} given. A useful
approach to solving such a problem is an iterative procedure, in which we
impose the spatial and frequency domain constraints separately in each domain.
An iterative procedure for the phase-only reconstruction is shown in Figure
1.34. In the procedure, we begin with an initial estimate of the signal. This
can be any real sequence with the same region of support as x(n_{1},n_{2}).
We next compute its Fourier transform. We then replace the Fourier transform
with the given _{}. The Fourier transform
magnitude is not affected. We then compute the inverse Fourier transform of the
modified Fourier transform. Due to the modification in the Fourier transform
domain, the sequence is no longer zero outside the known region of support of x(n_{1},n_{2}).
We now impose the spatial domain constraint by setting the sequence to zero
outside the known region of support. The resulting sequence is a new estimate
of the solution. This completes one iteration in the iterative procedure. When
the initial estimate of the sequence chosen is real, the constraint that the
solution is real will automatically be satisfied. The above algorithm can be
shown to converge to the desired solution. An example of signal reconstruction
from phase using the iterative procedure in Figure 1 .34 is shown in Figure
1.35. Figure 1.35(a) shows an original imageof 128 x 128 pixels. Figures
1.35(b), (c), and (d) show the results of the iterative procedure after one
iteration [phase-only synthesis of (1.39)], 10 iterations, and 50 iterations.
The initial estimate used is d(n_{1},n_{2}).

Although the magnitude-only
synthesis of (1.44) does not capture the intelligibility of typical signals,
almost all typical images are also uniquely specified by the Fourier transform
magnitude. Specifically, if x(n_{1},n_{2}) is real, has finile
extent, and has a nonfactorable Fourier transform, then x(n_{1},n_{2})
is uniquely specified by its Fourier transform magnitude _{} within
a sign factor, translation, and rotation by 180° degrees. This raises the
possibility of exactly reconstructing x(n_{1},n_{2}) from _{} within
a sign factor, translation and rotation by 180° degrees. This is known in
the literature as the **phase-retrieval problem**, and has many more
potential applications than the phase-only reconstruction problem.
Unfortunately, none of the algorithms developed to date are as straightforward
or well-behaved as the algorithms developed for the phase-only reconstruction
problem. It is possible to derive a closed-form algorithm or a set of linear
equations that can be used in solving for x(n_{1},n_{2}) from _{}, but
their derivation is quite involved. In addition, the closed-form solution is
not practical for an image of reasonable size due to the large number of linear
equations that must be solved. It is also possible to derive an iterative
procedure similar to that in Figure 1.34, which was developed for the
phase-only reconstruction. The only modification required is to replace the
Fourier transform magnitude with the given _{} rather than to replace
the Fourier transform phase with the given _{} when the frequency
domain constraints are imposed. The algorithm has been observed to converge to
the desired solution when the initial estimate used is quite accurate or the
signal x(n_{1},n_{2}) has a special characteristic such as a
triangular region of support. The magnitude-only reconstruction problem
specifies x(n_{1},n_{2}) within a sign factor, translation, and
rotation by 180°, and, therefore, more than one solution is possible. Imposing an
initial estimate sufficiently close to a possible solution or imposing
additional constraints such as a triangular region of support appear to prevent
the iterative procedure from wandering around from one possible solution to
another, in general, however, the algorithm does not converge to the desired
solution. Figure 1.36 shows an example of signal reconstruction from the
magnitude using a closed-form algorithm. Figures 1.36(a) and (b) show the
original and the reconstruction respectively. Developing a practical procedure
that can be used to reconstruct x(n_{1},n_{2}) from _{} remains
a problem for further research.