4.4Techniques for Constrained Restoration

In constrained restoration, some different techniques are used.

4.4.1Constrained Restoration

The solution to eq. (4.20) can also be considered from the least square sense, which is to minimize the function of ${\Vert \mathbf{Q}\widehat{\mathbf{f}}\Vert }^2,$ where Q is a linear operator on f, subject to the constraint $\Vert g-\mathbf{H}\widehat{f}\Vert ={\Vert n\Vert }^2.$ This problem can be solved by using the method of Lagrange multipliers. Denote l as the Lagrange multiplier (a constant) and the criterion function can be written as

$L\left(\widehat{\mathbf{f}}\right){\Vert \mathbf{Q}\widehat{f}\Vert }^2+l\left({\Vert g-H\widehat{f}\Vert }^2-{\Vert n\Vert }^2\right)\left(4.68\right)$

An , which can minimize eq. (4.68) is to be found. Similar to the process for solving eq. (4.44), by solving eq. (4.68), a constrained restoration formula can be obtained as

$\widehat{\mathbf{f}}={\left[{\mathbf{H}}^T\mathbf{H}+s{\mathbf{Q}}^T\mathbf{Q}\right]}^{-1}{\mathbf{H}}^T\mathbf{g}\left(4.69\right)$

where s = 1/l.

Constrained restoration provides more flexibility in the restoration process, as shown by the two techniques discussed in the following two subsections.

4.4.2Wiener Filter

A Wiener filter is a least mean squares filter. It can be derived from eq. (4.69).

Denote E{·} as the expectation operation, let Rf and Rn be the correlation matrices of f, and n. Rf and Rn can be defined by the following two equations

${\mathbf{R}}_{\mathbf{f}}=E\left\{\mathbf{f}{\mathbf{f}}^T\right\}\left(4.70\right)$

$R_n=E\left\{n{n}^T\right\}\left(4.71\right)$

The ij-th element of Rf is given by E{fi fj}, which is the correlation between the i-th and the j-th elements of f. Similarly, the ij-th element of Rn is given by E{ninj}, which is the correlation between the i-th and the j-th elements of n. Since the elements of f and n are real, Rf and Rn are real symmetric matrices. For most image functions, the correlation between pixels does not extend beyond a distance of 20–30 pixels in the image, so a typical correlation matrix only has a strip of nonzero elements about the main diagonal and has zero elements in the right-upper and left-lower corner regions. Based on the assumption that the correlation between any two pixels is a function of the distance between the pixels but not their position, Rf and Rn can be expressed by block-circulant matrices and diagonalized by the matrix W with the procedure described previously.

${\mathbf{R}}_{\mathbf{f}}=\mathbf{W}\mathbf{A}{\mathbf{W}}^{-1}\left(4.72\right)$

${\mathbf{R}}_{\mathbf{n}}=\mathbf{W}\mathbf{B}{\mathbf{W}}^{-1}\left(4.73\right)$

where the elements in A and B correspond to the Fourier transforms of the correlation elements in Rf and Rn, respectively. The Fourier transforms of these correlation elements are called the power spectrums of fe(x, y) and ne(x, y), respectively. In the following discussion, they are denoted Sf(u, v) and Sn(u, v).

Now, defining ${\mathbf{Q}}^T\mathbf{Q}={\mathbf{R}}_{\mathbf{f}}^{-1}{\mathbf{R}}_{\mathbf{n}},$ and substituting it into eq. (4.69) yields

$\widehat{\mathbf{f}}={\left({\mathbf{H}}^T\mathbf{H}+s{\mathbf{R}}_{\mathbf{f}}^{-1}{\mathbf{R}}_{\mathbf{n}}\right)}^{-1}{\mathbf{H}}^T\mathbf{g}\left(4.74\right)$

With the help of eq. (4.28), eq. (4.29), eq. (4.72), and eq. (4.73),

$\widehat{\mathbf{f}}={\left(W{D}^{*}\mathbf{D}{\mathbf{W}}^{-1}+s\mathbf{W}{A}^{-1}\mathbf{B}{\mathbf{W}}^{-1}\right)}^{-1}\mathbf{W}{\mathbf{D}}^{*}{\mathbf{W}}^{-1}\mathbf{g}\left(4.75\right)$

Multiplying both sides of eq. (4.75) by W–1 gives

${\mathbf{W}}^{-1}\widehat{\mathbf{f}}={\left({\mathbf{D}}^{*}\mathbf{D}+s{\mathbf{A}}^{-1}\mathbf{B}\right)}^{-1}{\mathbf{D}}^{*}{\mathbf{W}}^{-1}\mathbf{g}\left(4.76\right)$

Since the matrices inside the parentheses are diagonal, the elements of eq. (4.76) can be written as

$\widehat{F}\left(u,v\right)=\left[\frac{1}{H\left(u,v\right)}\times \frac{\left|H\left(u,v\right)\right|}{{\left|H\left(u,v\right)\right|}^2+s\left[S_n\left(u,v\right)/S_f\left(u,v\right)\right]}\right]G\left(u,v\right)\left(4.77\right)$

Several cases of eq. (4.77) are discussed as follows:

(1)If s = 1, the term inside the brackets is the Wiener filter.

(2)If s is a variable, the term inside the brackets is called the parametric Wiener filter.

(3)If there is no noise, Sn(u, v) = 0, the Wiener filter degrades to the ideal inverse filter.

Since s must be adjusted to satisfy eq. (4.69), when s = 1, the use of eq. (4.77) no longer yields an optimal solution as defined in the above, since s must be adjusted to satisfy the constraint of ${\Vert g-\mathbf{H}\widehat{\mathbf{f}}\Vert }^2={\Vert n\Vert }^2.$ However, this solution is optimal in the sense of minimizing E{[f(x, y) – $\widehat{f}$ (x, y)]2}.

In practice, Sn(u, v) and Sf(u, v) are often unknown, so eq. (4.77) can be approximated by

$\tilde{F}\left(u,v\right)\approx \left[\frac{1}{H\left(u,v\right)}\times \frac{{\left|H\left(u,v\right)\right|}^2}{{\left|H\left(u,v\right)\right|}^2+k}\right]G\left(u,v\right)\left(4.78\right)$

where K is a constant.

Example 4.3 Some comparisons of the inverse filter and the Wiener filter

Some comparisons of the inverse filter and the Wiener filter are shown in Figure 4.9. The column images in Figure 4.9(a) are obtained by convolving the original cameraman image with a smoothing function $h\left(x,y\right)=\exp \left[\sqrt{\left(x^2+y^2\right)}/240\right],$ then adding a Gaussian noise, whose mean is zero and variance equals to 8, 16, and 32, respectively. The column images in Figure 4.9(b) are obtained by using the inverse filter and the column images in Figure 4.9(c) are obtained by using the Wiener filter. Comparing Figures 4.9(b) and (c), the superiority of the Wiener filter over the inverse filter is evident. This superiority is particularly visible with stronger noise.

4.4.3Constrained Least Square Restoration

Wiener filtering is a statistical method. The optimal criterion used by the Wiener filter is based on the correlation matrices of the image and the noise, respectively. It is thus optimal only in an average sense. The following described restoration procedure, called the constrained least square restoration, is optimal for each image. It only requires the knowledge of the noise’s mean and variance.

4.4.3.1Derivation

The constrained least square restoration starts also from eq. (4.69), and the key issue is still to determine the transform matrix Q. Equation (4.69) is an ill-conditioning equation that sometimes yields solutions that are obscured by large oscillating values. One solution used to reduce oscillation is to formulate a criterion of optimality based on a measure of smoothness. Such criteria can be based on the function of the second derivative. The second derivative of f(x, y) at (x, y) can be approximated by

$\frac{{\partial }^{2}f}{\partial x^2}+\frac{{\partial }^{2}f}{\partial y^2}\approx 4f\left(x,y\right)-\left[f\left(x+1,y\right)+f\left(x-1,y\right)+f\left(x,y+1\right)+f\left(x,y-1\right)\right]\left(4.79\right)$

The second derivative of f(x, y) in eq. (4.79) can be obtained by convolving f(x, y) with the following operator

$p\left(x,y\right)=\left[\begin{array}{ccc}0& -1& 0\\ -1& 4& -1\\ 0& -1& 0\end{array}\right]\left(4.80\right)$

One optimal criterion based on the above second derivative is

$\min {\left[\frac{{\partial }^{2}f\left(x,y\right)}{\partial x^2}+\frac{{\partial }^{2}f\left(x,y\right)}{\partial y^2}\right]}^2\left(4.81\right)$

To avoid wraparound error in the discrete convolution process, p(x, y) needs to be extended to

$p_e\left(x,y\right)=\{\begin{array}{l}p\left(x,y\right)0\le x\le 2and0\le y\le 2\\ 03\le x\le M-1or3\le y\le N-1\end{array}\left(4.82\right)$

The extension of f(x, y) can be referred to eq. (4.16). If the size of f(x, y) is A × B and the size of p(x, y) is 3 × 3, the selection of M and N are M ≥ A + 3 – 1 and N ≥ B + 3 – 1, respectively.

The above smoothness criterion can be expressed in matrix form. First, a block-circulant matrix is constructed as

$C=\left[\begin{array}{cccc}{C}_0& C_{M-1}& \cdots & C_1\\ C_1& C_0& \cdots & C_2\\ ⋮& ⋮& \ddots & ⋮\\ C_{M-1}& C_{M-2}& \cdots & C_0\end{array}\right]\left(4.83\right)$

where each sub-matrix Cj is an N × N circulant constructed from the j-th row of pe(x, y)

$C_j=\left[\begin{array}{cccc}{p}_e\left(j,0\right)& p_e\left(j,N-1\right)& \cdots & p_e\left(j,1\right)\\ p_e\left(j,0\right)& p_e\left(j,0\right)& \cdots & p_e\left(j,2\right)\\ ⋮& ⋮& \ddots & ⋮\\ p_e\left(j,N-1\right)& p_e\left(j,N-2\right)& \cdots & p_e\left(j,0\right)\end{array}\right]\left(4.84\right)$

According to the discussion in Section 4.2, C can be diagonalized by the matrix W

$\mathbf{E}={\mathbf{W}}^{-1}\mathbf{C}\mathbf{W}\left(4.85\right)$

where E is a diagonal matrix whose elements are given by

$E\left(k,i\right)=\{\begin{array}{l}\begin{array}{ccc}P\left(\lfloor k/NN\rfloor ,k\mathrm{mod}N\right)& \text{if}& i=k\end{array}\\ \begin{array}{ccc}0& \text{if}& i\ne k\end{array}\end{array}\left(4.86\right)$

where P(u, v) is the 2-D Fourier transform of pe(x, y).

If it is required that the following constraint

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

should be satisfied, then the optimal solution is given by eq. (4.69) with Q = C. This is given by

$\widehat{\mathbf{f}}={\left({\mathbf{H}}^T\mathbf{H}+s{\mathbf{C}}^T\mathbf{C}\right)}^{-1}{\mathbf{H}}^T\mathbf{g}={\left(\mathbf{W}{\mathbf{D}}^{*}\mathbf{D}{\mathbf{W}}^{-1}+s\mathbf{W}{\mathbf{E}}^{*}\mathbf{E}{\mathbf{W}}^{-1}\right)}^{-1}\mathbf{W}{\mathbf{D}}^{*}{\mathbf{W}}^{-1}\mathbf{g}\left(4.88\right)$

Multiplying both sides of eq. (4.88) by W–1 gives

$W^{-1}\widehat{f}={\left(D^{*}D+s{E}^{*}E\right)}^{-1}{D}^{*}{W}^{-1}g\left(4.89\right)$

According to the discussion in Section 4.2, the elements of eq. (4.89) can be expressed in the following form

$\widehat{F}\left(u,v\right)=\left[\frac{H^{*}\left(u,v\right)}{{\left|H\left(u,v\right)\right|}^2+s{\left|P\left(u,v\right)\right|}^2}\right]G\left(u,v\right)u,v=0,\mathrm{1...},M-1\left(4.90\right)$

Equation (4.90) resembles the parametric Wiener filter. The main difference is that no explicit knowledge of the statistical parameters other than an estimation of the noise’s mean and variance is required.

4.4.3.2Estimation

Equation (4.69) indicates that s needs to be adjusted to satisfy the constraint ${\Vert g-\mathrm{H}\widehat{f}\Vert }^2={\Vert n\Vert }^2.$ In other words, only when s satisfies this condition, is eq. (4.90) optimal. A procedure for estimating s is introduced below. First, a residual vector r is defined

$\mathbf{r}=\mathbf{g}-\mathbf{H}\widehat{\mathbf{f}}=\mathbf{g}-\mathbf{H}{\left({\mathbf{H}}^T\mathbf{H}+s{\mathbf{C}}^T\mathbf{C}\right)}^{-1}{\mathbf{H}}^T\mathbf{g}\left(4.91\right)$

where r is a function of s. It can be proven that q(s) = rT r = ||r||2 and q(s) is a monotonically increasing function of s. It is now expected to adjust s to satisfy

${\left|\left|r\right|\right|}^2={\left|\left|n\right|\right|}^2\pm a\left(4.92\right)$

where a is an accuracy factor. If ||r||2 = ||n||2, the constraint ||g – H ||2 = ||n||2 will be strictly satisfied. One simple approach to find an s that satisfies eq. (4.92) is to:

(1)Specify an initial value of s.

(2)Compute and ||r||2.

(3)Stop if eq. (4.92) is satisfied; otherwise return to step 2 after increasing s if ||r||2 < ||n||2 − a or decreasing s if ||r||2 > ||n||2 + a.

To implement the above procedure for the constrained least square restoration, some knowledge of ||r||2 and ||n||2 are required. According to the definition of the residual vector r in eq. (4.91), its Fourier transform is

$R\left(u,v\right)=G\left(u,v\right)-H\left(u,v\right)\widehat{F}\left(u,v\right)\left(4.93\right)$

Computing the inverse Fourier transform of R(u, v), r(x, y) can be obtained. From r(x, y), ||r||2 can be computed

$\left|\left|r\right|\right|={\displaystyle \sum _{x=0}^{M-1}{\displaystyle \sum _{y=0}^{N-1}{r}^2\left(x,y\right)}}$

Now consider the computation of ||n||2. The noise variance of the whole image can be estimated using the expected value

${\sigma }_n^2=\frac{1}{MN}{\displaystyle \sum _{x=0}^{M-1}{\displaystyle \sum _{y=0}^{N-1}{\left[n\left(x,y\right)-m_n\right]}^2}}\left(4.95\right)$

where

$m_n=\frac{1}{MN}{\displaystyle \sum _{x=0}^{M-1}{\displaystyle \sum _{y=0}^{N-1}n\left(x,y\right)}}\left(4.96\right)$

Similar to eq. (4.95), the two summations in eq. (4.96) are just ||n||2, which means

${\left|\left|n\right|\right|}^2=MN\left[{\sigma }_n^2+m_n^2\right]\left(4.97\right)$

Example 4.4 Comparisons of the Wiener filter and the constrained least square filter Some comparisons of the Wiener filter and the constrained least square restoration are shown in Figure 4.10. The image in Figure 4.10(a) is obtained by filtering the original cameraman image with a blurring filter. The images in Figures 4.10(b) and (c) are the restoration results of Figure 4.10(a), obtained by using the Wiener filter and the constrained least square filter, respectively. The image in Figure 4.10(d) is obtained by adding some random noise to Figure 4.10(a). The images in Figures 4.10(e) and (f) are the restoration results of Figure 4.10(d) obtained by using the Wiener filter and the constrained least square filter, respectively. From Figure 4.10, when an image is degraded only by blurring (no noise), the performances of the Wiener filter and the constrained least square filter are similar. When an image is degraded by both blurring and adding noise, the performance of the constrained least square filter is better than that of the Wiener filter.

4.5Interactive Restoration

The above discussion is for automatic restoration. In practical applications, the advantage of human intuition can be used. By interactive restoration, the human knowledge is used to control the restoration process and to obtain some special effects. One example is presented below.

One of the simplest image degradations that can be dealt with by interactive restoration is the case when a 2-D sinusoidal interference pattern (coherent noise) is superimposed on an image. Let η(x, y) denote a sinusoidal interference pattern whose amplitude is A and frequency component is denoted (u0, v0), that is,

$\eta \left(x,y\right)=A\sin \left(u_{0}x+v_{0}y\right).\left(4.98\right)$

The Fourier transform of η(x, y) is

$N\left(u,v\right)=\frac{-jA}{2}\left[\delta \left(u-\frac{u_0}{2\pi },v-\frac{v_0}{2\pi }\right)-\delta \left(u+\frac{u_0}{2\pi },v+\frac{v_0}{2\pi }\right)\right]\left(4.99\right)$

The transform has only imaginary components. This indicates that a pair of impulses of strength –A/2 and A/2 are located at coordinates (u0/2π, v0/2π) and (–u0/2π, –v0/2π) in the frequency plane, respectively. When the degradation is caused only by the additive noise, it has

$G\left(u,v\right)=F\left(u,v\right)+N\left(u,v\right)\left(4.100\right)$

In the display of the magnitude of G(u, v) in the frequency domain, which contains the sum of F(u, v) and N(u, v), two noise impulses of N(u, v) would appear as bright dots if they are located far enough from the origin and A is large enough. By visually identifying the locations of these two impulses and using an appropriate band-pass filter at the locations, the interference can be removed from the degraded image.

Example 4.5 Removing sinusoidal interference patterns interactively

One example of removing sinusoidal interference patterns interactively is shown in Figure 4.11. Figure 4.11(a) shows the result of covering the original cameraman image by the sinusoidal interference pattern defined in eq. (4.98). The Fourier spectrum magnitude is shown in Figure 4.11(b), in which a pair of impulses appears in the cross points of the bright lines. These two impulses can be removed by interactively putting two band-rejecting filters at the locations of the impulses. Taking the inverse Fourier transform of the filtering result, the restored image can be obtained as shown in Figure 4.11(d). Note that the diameter of the band-rejecting filter should be carefully selected. If two band-rejecting filters as shown in Figure 4.11(e) are used, in which the diameter of the filter is five times larger than that of the one used in Figure 4.11(c), the filtered image will be the one as shown in Figure 4.11(f). The ring effect is clearly visible as shown in Figure 4.11(f).

In real applications, many sinusoidal interference patterns exist. If many band-rejecting filters are used, too much image information will be lost. In this case, the principal frequency of the sinusoidal interference patterns should be extracted. This can be made by placing, at each bright point, a band-pass filter H(u, v). If an H(u, v) can be constructed, which only permit the components related to the interference pattern to pass, the Fourier transform of this pattern is

$P\left(u,v\right)=\mathrm{H}\left(u,v\right)G\left(u,v\right)\left(4.101\right)$

The construction of H(u, v) requires judgment of whether a bright point is an interference spike or not. For this reason, the band-pass filter generally is constructed interactively by observing the spectrum of G(u, v). After a particular filter has been selected, the corresponding pattern in this spatial domain is obtained from the expression.

$p\left(x,y\right)=F^{-1}\left\{\mathrm{H}\left(u,v\right)G\left(u,v\right)\right\}\left(4.102\right)$