F(k) and G(k) are the Fourier transforms of the extended sequences fe(x) and ge(x), respectively.

The diagonal elements of D in eq. (4.30) are the eigenvalues of H. Following eq. (4.23),

$D\left(k,k\right)=\lambda \left(k\right)={\displaystyle \sum _{i=0}^{M-1}{h}_e\left(i\right)\exp \left(-j\frac{2\pi }{M}ki\right)=MH\left(k\right)k=0,1,\mathrm{...},M-1\left(4.33\right)}$

where H(k) is the Fourier transforms of the extended sequences he(x).

Combining eq. (4.31) to eq. (4.33) yields

$G\left(k\right)=M\times H\left(k\right)F\left(k\right)k=0,1,\mathrm{...},M-1\left(4.34\right)$

The right side of eq. (4.34) is the convolution of fe(x) and he(x) in the frequency domain. It can be calculated with the help of FFT.

Now, consider the 2-D cases (with noise). Taking eq. (4.28) into eq. (4.20), and multiplying both sides by W–1,

${\mathbf{W}}^{-1}\mathbf{g}=\mathbf{D}{\mathbf{W}}^{-1}\mathbf{f}+{\mathbf{W}}^{-1}\mathbf{n}\left(4.35\right)$

where W–1 is an MN × MN matrix and D is an MN × MN diagonal matrix. The left side of eq. (4.35) is an MN × 1 vector, whose elements can be written as G(0, 0), G(0, 1), . . ., G(0, N– 1); G(1, 0), G(1, 1), . . ., G(1, N– 1);. . .; G(M– 1, 0), G(M– 1, 1), . . ., G(M– 1, N– 1). For u = 0, 1, . . ., M – 1 and v = 0, 1,. . ., N– 1, the following formulas exist

$G\left(u,v\right)=\frac{1}{MN}{\displaystyle \sum _{x=0}^{M-1}{\displaystyle \sum _{y=0}^{N-1}{g}_e\left(x,y\right)\exp \left[-j2\pi \left(\frac{ux}{M}+\frac{vy}{N}\right)\right]}}\left(4.36\right)$

$F\left(u,v\right)=\frac{1}{MN}{\displaystyle \sum _{x=0}^{M-1}{\displaystyle \sum _{y=0}^{N-1}{f}_e\left(x,y\right)\exp \left[-j2\pi \left(\frac{ux}{M}+\frac{vy}{N}\right)\right]\left(4.37\right)}}$

$N\left(u,v\right)=\frac{1}{MN}{\displaystyle \sum _{x=0}^{M-1}{\displaystyle \sum _{y=0}^{N-1}{n}_e\left(x,y\right)\exp \left[-j2\pi \left(\frac{ux}{M}+\frac{vy}{N}\right)\right]\left(4.38\right)}}$

$H\left(u,v\right)=\frac{1}{MN}{\displaystyle \sum _{x=0}^{M-1}{\displaystyle \sum _{y=0}^{N-1}{h}_e\left(x,y\right)\exp \left[-j2\pi \left(\frac{ux}{M}+\frac{vy}{N}\right)\right]\left(4.39\right)}}$

The MN diagonal elements of D can be represented by

$D\left(k,i\right)=\{\begin{array}{l}MN\times H\left(\lfloor \frac{k}{N}\rfloor \right),k\mathrm{mod}N\text{if}i=k\\ 0\text{if}\text{i}\ne \text{k}\end{array}\left(4.40\right)$

where $\lfloor \cdot \rfloor$ is a flooring function (see Section 3.2).

Combining eq. (4.36) to eq. (4.40) and merging MN into H(u, v) gives

$G\left(u,v\right)=H\left(u,v\right)F\left(u,v\right)+N\left(u,v\right)\begin{array}{c}u=0,1,\mathrm{...},M-1\\ v=0,1,\mathrm{...},N-1\end{array}\left(4.41\right)$

To solve eq. (4.20), only a few discrete Fourier transforms of size M × N are needed.

4.3Techniques for Unconstrained Restoration

Image restoration can be classified into unconstrained restoration and constrained restoration categories.

4.3.1Unconstrained Restoration

From eq. (4.20), it can obtain

$\mathbf{n}=\mathbf{g}-\mathbf{H}\mathbf{f}\left(4.42\right)$

When there is no a priori knowledge of n, an estimation of f, $\widehat{f}$ is to be found to assure that H approximates g in a least squares sense. In other words, it makes the norm of n as small as possible

${\Vert \mathbf{n}\Vert }^2={\mathbf{n}}^T\mathbf{n}={\Vert \mathbf{g}-\mathbf{H}\widehat{\mathbf{f}}\Vert }^2={\left(\mathbf{g}-\mathbf{H}\widehat{\mathbf{f}}\right)}^T\left(\mathbf{g}-\mathbf{H}\widehat{\mathbf{f}}\right)\left(4.43\right)$

According to eq. (4.43), the problem of image restoration can be considered a problem of minimizing the following function

$L\left(\widehat{\mathbf{f}}\right)={\Vert \mathbf{g}-\mathbf{H}\widehat{\mathbf{f}}\Vert }^2\left(4.44\right)$

To solve eq. (4.44), differentiation of L with respect to is needed, and the result should equal the zero vector. Assuming that H–1 exists and letting M = N, the unconstrained restoration can be represented as

$\widehat{\mathbf{f}}={\left({\mathbf{H}}^T\mathbf{H}\right)}^{-1}{\mathbf{H}}^T\mathbf{g}={\mathbf{H}}^{-1}{\left({\mathbf{H}}^T\right)}^{-1}{\mathbf{H}}^T\mathbf{g}={\mathbf{H}}^{-1}g\left(4.45\right)$

4.3.1.1Inverse Filtering

Taking eq. (4.28) into eq. (4.45) yields

$\widehat{\mathbf{f}}={\mathbf{H}}^{-1}\mathbf{g}={\left(\mathbf{W}D{\mathbf{W}}^{-1}\right)}^{-1}\mathbf{g}=\mathbf{W}{\mathbf{D}}^{-1}{\mathbf{W}}^{-1}\mathbf{g}\left(4.46\right)$

Pre-multiplying both sides of eq. (4.46) by W–1 yields

${\mathbf{W}}^{-1}\widehat{\mathbf{f}}={\mathbf{D}}^{-1}{\mathbf{W}}^{-1}\mathbf{g}\left(4.47\right)$

According to the discussion about diagonalization in Section 4.2, the elements comprising eq. (4.47) may be written as

$\widehat{F}\left(u,v\right)=\frac{G\left(u,v\right)}{H\left(u,v\right)}u,v=0,1,\mathrm{...},M-1\left(4.48\right)$

Equation (4.48) provides a restoration approach often called inverse filtering. When considering H(u, v) as a filter function that multiplies F(u, v) to produce the transform of the degraded image g(x, y), the division of G(u, v) by H(u, v) as shown in eq. (4.48) is just an inverse filtering operation. The final restored image can be obtained using the inverse Fourier transform

$\widehat{f}\left(x,y\right)=F^{-1}\left[\widehat{F}\left(u,v\right)\right]=F^{-1}\left[\frac{G\left(u,v\right)}{H\left(u,v\right)}\right]x,y=0,1,\mathrm{...},M-1\left(4.49\right)$

The division of G(u, v) by H(u, v) may encounter problems when H(u, v) approaches 0 in the UV plane. On the other hand, noise can cause more serious problems. Substituting eq. (4.41) into eq. (4.48) yields

$\widehat{F}\left(u,v\right)=F\left(u,v\right)+\frac{N\left(u,v\right)}{H\left(u,v\right)}u,v=0,1,\mathrm{...},M-1\left(4.50\right)$

Equation (4.50) indicates that if H(u, v) is zero or very small in the UV plane, the term N(u, v)/H(u, v) could dominate the restoration result and make the result quite different from the expected result. In practice, H(u, v) often drops off rapidly as a function of the distance from the origin of the UV plane, while the noise usually drops at a much slower speed. In such situations, a reasonable restoration is possible to a small region around the origin point.

4.3.1.2Restoration Transfer Function

For real applications, the inverse filter is not taken as 1/H(u, v), but as a function of the coordinates u and v. This function is often called the restoration transfer function and is denoted M(u, v). The image degradation and restoration models are jointly represented in Figure 4.6.

A commonly used M(u, v) is given by

$M\left(u,v\right)=\{\begin{array}{l}1/H\left(u,v\right)\text{if}{u}^2+v^2\le w_0^2\\ 1\text{if}{u}^2+v^2\le w_0^2\end{array}\left(4.51\right)$

where w0 is selected to eliminate the points at which H(u, v) equals zero. However, the restoration results obtained by this method often have a visible “ring effect.” An improved method is to take M(u, v) as

$M\left(u,v\right)=\{\begin{array}{l}k\text{if}\text{H}\left(u,v\right)\le d\\ 1/H\left(u,v\right)\text{otherwise}\end{array}\left(4.52\right)$

where k and d are both constants that are less than 1.

Example 4.1 Blurring a point image to obtain the transfer function and restore the image

The transfer function H(u, v) of a degraded image can be approximated using the Fourier transform of the degraded image. One full image can be considered a combined set of point images. If a point image is taken as the approximation of a unit impulse function $\left(F\left[\delta \left(x,y\right)\right]=1\right),\text{then}G\left(u,v\right)=\mathrm{H}\left(u,v\right)F\left(u,v\right)\approx \mathrm{H}\left(u,v\right).$

Figure 4.7 illustrates the results of the restoration. Figure 4.7(a) is a simulated degradation image, which is obtained by applying a low-pass filter to an ideal image. The Fourier transform of the used low-pass filter is shown in Figure 4.7(b). The restoration results obtained using eq. (4.51) and eq. (4.52) are shown in Figures 4.7(c) and (d), respectively. Comparing these two results, the “ring effect” in Figure 4.7(d) is less visible.

4.3.2Removal of Blur Caused by Uniform Linear Motion

In some applications, H(u, v) can be obtained analytically. One example is the application used to restore blurred images, which is caused by uniform linear motion.

First, consider the continuous case. Suppose that an image f(x, y) is captured for a uniform moving object on the plane and the moving components of the object in X and Y directions are denoted x0(t) and y0(t), respectively. The duration for image capturing is T. The real blurred image g(x, y), which is caused by the motion is

$g\left(x,y\right)={\displaystyle \underset{0}{\overset{T}{\int }}f\left[x-x_0\left(t\right),y-y_0\left(t\right)dt\right]\left(4.53\right)}$

The Fourier transform of g(x, y) is

$\begin{array}{l}G\left(u,v\right)={\displaystyle \underset{-\infty }{\overset{\infty }{\int }}{\displaystyle \underset{-\infty }{\overset{\infty }{\int }}g\left(x,y\right)\exp \left[-j2\pi \left(ux+vy\right)\right]dxdy}}\\ ={\displaystyle \underset{0}{\overset{T}{\int }}\left[{\displaystyle \underset{-\infty }{\overset{\infty }{\int }}{\displaystyle \underset{-\infty }{\overset{\infty }{\int }}f\left[x-x_0\left(t\right),y-y_0\left(t\right)\right]\exp \left[-j2\pi \left(ux+vy\right)\right]dxdy}}\right]}dt\left(4.54\right)\\ =F\left(u,v\right){\displaystyle \underset{0}{\overset{T}{\int }}\exp \left\{-j2\pi \left[u{x}_0\left(t\right)+v{y}_0\left(t\right)\right]\right\}}dt\end{array}$

By defining

$H\left(u,v\right)={\displaystyle \underset{0}{\overset{T}{\int }}\exp \left\{-j2\pi \left[u{x}_0\left(t\right)+v{y}_0\left(t\right)\right]\right\}dt\left(4.55\right)}$

Equation (4.54) can be written as

$G\left(u,v\right)=H\left(u,v\right)F\left(u,v\right)\left(4.56\right)$

If the motion components are given, the transfer function H(u, v) can be obtained from eq. (4.55).

A simple example is discussed below. Suppose that there is only motion along the X direction; that is, t = T and y0(t) = 0. When x0(t) = ct/T, the distance moved by f(x, y) is c,

$H\left(u,v\right)={\displaystyle \underset{0}{\overset{T}{\int }}\exp \left[-j2\pi u\frac{ct}{T}\right]dt=\frac{T}{\pi uc}\sin \left(\pi uc\right)\exp \left[-j\pi uc\right]\left(4.57\right)}$

when n takes an integer value, then H is zero at u = n/c.

When f(x, y) is zero or is known to be outside of the region 0 ≤ x ≤ L, the problem caused by H = 0 can be avoided and the image can be completely reconstructed from the knowledge of g(x, y) in this region.

Substituting x0(t) = ct/T into eq. (4.53), suppressing the time invariant variable y, and ignoring the scale parameters give

$g\left(x\right)={\displaystyle \underset{0}{\overset{T}{\int }}f\left[x-\frac{ct}{T}\right]dt={\displaystyle \underset{x-c}{\overset{x}{\int }}f\left(\tau \right)d\tau 0\le x\le L\left(4.58\right)}}$

Taking the differentiation with respect to x can provide an iterative formula

$f\left(x\right)=g\text{'}\left(x\right)+f\left(x-c\right)0\le x\le L\left(4.59\right)$

Assuming that L = Kc, K is an integer, and p(z) is the part of scene moved in 0 ≤ z < c during the capturing period,

$p\left(z\right)=f\left(z-c\right)0\le z\le c\left(4.60\right)$

It can be proven that eq. (4.59) can be written as

$f\left(x\right)={\displaystyle \sum _{k=0}^{m}g\text{'}\left(x-kc\right)+p\left(x-mc\right)0\le x\le L\left(4.61\right)}$

where m is the integer part of x/c. Since g′(x) is known, only p(x) is estimated to obtain f(x). A method to directly estimate p(x) from the blurred image is presented in the following.

First, define

$\tilde{f}\left(x\right)={\displaystyle \sum _{j=0}^{m}g\text{'}\left(x-jc\right)\left(4.62\right)}$

Substituting eq. (4.62) into eq. (4.63), eq. (4.64) becomes

$p\left(x-mc\right)=f\left(x\right)-\tilde{f}\left(x\right)\left(4.63\right)$

Note that m ranges from 0 to K – 1 as x varies from 0 to L. Thus, p is repeated K times during the evaluation of f(x) from 0 to L. For each kc ≤ x < (k + 1)c, eq. (4.62) is calculated. Adding the results for k = 0, 1, ..., K − 2 gives

$p\left(x\right)=\frac{1}{K}{\displaystyle \sum _{k=0}^{K-1}f\left(x+kc\right)-\frac{1}{K}}{\displaystyle \sum _{k=0}^{K-1}\tilde{f}\left(x+kc\right)\left(4.64\right)}$

The first sum on the right-hand side of eq. (4.64) is unknown, but it approaches the mean value of f(·) for large values of K. Suppose that the sum is taken as a constant A. Substitute eq. (4.62) into eq. (4.64), then

$\begin{array}{l}p\left(x-mc\right)\approx A-\frac{1}{K}{\displaystyle \sum _{k=0}^{K-1}\tilde{f}\left(x+kc-mc\right)}\\ \left(4.65\right)\\ \approx A-\frac{1}{K}{\displaystyle \sum _{k=0}^{K-1}{\displaystyle \sum _{j=0}^{k}g\text{'}\left(x+kc-mc-jc\right)0\le x\le L}}\end{array}$

Combined with eq. (4.62) and eq. (4.63),

$f\left(x\right)\approx A-\frac{1}{K}{\displaystyle \sum _{k=0}^{K-1}{\displaystyle \sum _{j=0}^{k}g\text{'}\left[x-mc+\left(k-j\right)c\right]+{\displaystyle \sum _{j=0}^{m}g\text{'}\left(x-jc\right)\left(4.66\right)}}}$

Reintroducing the suppressed variable y yields the final result

$\begin{array}{l}f\left(x,y\right)\approx A-\frac{1}{K}{\displaystyle \sum _{k=0}^{K-1}{\displaystyle \sum _{j=0}^{k}g\text{'}\left[m-mc+\left(k-j\right)c,y\right]}}+{\displaystyle \sum _{j=0}^{m}g\text{'}\left(x-jc,y\right)\left(4.67\right)}\\ \end{array}$

Example 4.2 Removing the blur caused by uniform linear motion

A restoration example for removing the blur caused by uniform linear motion is presented in Figure 4.8. Figure 4.8(a) is a 256 × 256 image, which is captured when there is uniform linear motion between the camera and the object in a scene. Suppose that the moving distance along the horizontal direction is 1/8 of the image size, which is 32 pixels. This image can be restored using eq. (4.66). When the moving distance is 32, the result is very good as shown in Figure 4.8(b). When the moving distance is 24 and 40, the results are rather poor as shown in Figures 4.8(c) and (d). The poor results are due to the inaccurate estimation of the moving speed.