1 August 2010 Iterative adaptive hybrid image restoration for fast convergence
Abstract
We present an iterative adaptive hybrid image restoration algorithm for fast convergence. The local variance, mean, and maximum values are used to constrain the solution space. These parameters are computed at each iteration step using a partially restored image at each iteration, and they are used to impose the degree of local smoothness on the solution. The resulting iterative algorithm exhibits increased convergence speed and better performance than typical regularized constrained least-squares approach.
Hong: Iterative adaptive hybrid image restoration for fast convergence

## Introduction

An image captured by an imaging system represents the degraded version of an original image due to blurring and additive noise.1, 2 For a size $M×N$ image, a typical degradation model can be written as

## 1

$\mathbf{y}=\mathbf{H}\mathbf{x}+\mathbf{n},$
where the vectors $\mathbf{x}$ , $\mathbf{y}$ , and $\mathbf{n}$ are the lexicographically ordered original image, the observed image, and the additive noise of size $MN×1$ , respectively. In addition, $\mathbf{H}$ is the degradation matrix of size $MN×MN$ to represent a spatially invariant or spatially varying point spread function (PSF).

Regularized constrained least squares (RCLS) have been widely used to obtain a solution for Eq. 1, and the solution is obtained by minimizing the following function with respect to $\mathbf{x}$ ,1, 2

## 2

$M\left(\mathbf{x}\right)={‖\mathbf{y}-\mathbf{H}\mathbf{x}‖}^{2}+\alpha {‖\mathbf{C}\mathbf{x}‖}^{2},$
where $\alpha$ denotes the regularization parameter to control the tradeoff between fidelity to the data and smoothness, and $\mathbf{C}$ typically represents a high-pass operator.

The prior knowledge used in RCLS is that the original image is smooth. However, this is a global requirement and therefore not effective in terms of local smoothness. Also, when an iterative technique is used to obtain the solution of Eq. 2, the iterative solution may suffer from noise amplification after a certain iteration step when the additive noise is serious.2, 3, 4 Therefore, a more desirable solution can be obtained by imposing reasonable constraints into the solution space of RCLS.3, 4, 5 Projection onto convex sets (POCS) has been widely used in many areas, since it is effective to impose nonlinear local properties into the solution space.3, 6

In this work, an iterative adaptive hybrid image restoration algorithm using a local smoothing constraint is presented. We follow the formulation represented by Eq. 2 and propose to bring knowledge about local properties of the original image into the restoration process, so that prior knowledge and spatial adaptivity are incorporated in the solution. The basic motivation is to constrain local ranges of values that the restored image can take, leading to increased convergence speed of the iterative algorithm and performance improvement compared to RCLS.

This work is organized as follows. In Sec. 2, the proposed hybrid gradient-projection restoration algorithm is explained. Experimental results and conclusions are presented in Sec. 3.

## Proposed Algorithm

The gradient iteration of the regularized smoothing functional in Eq. 2 can be written as

## 3

${\mathbf{x}}_{k+1}={\mathbf{x}}_{k}+\left[{\mathbf{H}}^{\mathbf{T}}\mathbf{y}-\left({\mathbf{H}}^{\mathbf{T}}\mathbf{H}+\alpha {\mathbf{C}}^{\mathbf{T}}\mathbf{C}\right){\mathbf{x}}_{k}\right]=G{\mathbf{x}}_{k}.$
There exist various ways for determining the regularization parameter $\alpha$ .1, 2, 7 According to Ref. 7, we determine the regularization parameter by

## 4

$\alpha \left({\mathbf{x}}_{k}\right)={‖\mathbf{y}-\mathbf{H}{\mathbf{x}}_{k}‖}^{2}∕\left(\theta -{‖\mathbf{C}{\mathbf{x}}_{k}‖}^{2}\right),$
where $\theta ⩾2{‖\mathbf{y}‖}^{2}$ . The iterative solution in Eq. 3 reflects only global smoothing requirements and therefore it is not effective in terms of local smoothness. When a local smoothing constraint is imposed into the solution space of RCLS, the iteration in Eq. 3 can take the form

## 5.

${\stackrel{\mathrm{̂}}{\mathbf{x}}}_{k}=G{\mathbf{x}}_{k},$
${\mathbf{x}}_{k+1}=P{\stackrel{\mathrm{̂}}{\mathbf{x}}}_{k}=PG{\mathbf{x}}_{k},$
where $P$ represents a projection operator of a signal onto a set with desirable local properties. The proposed projection set is defined by the local statistics of the partially restored image at each iteration step. For a pixel of the partially restored image ${\stackrel{̂}{x}}_{k}\left(i,j\right)$ , the local mean and variance at coordinate $\left(i,j\right)$ with window $W$ are defined as

## 6.

${m}_{{\stackrel{̂}{x}}_{k},W}\left(i,j\right)={W}^{-1}\sum _{p=i-U}^{i+U}\sum _{q=j-V}^{j+V}{\stackrel{̂}{x}}_{k}\left(p,q\right),$
${\sigma }_{{\stackrel{̂}{x}}_{k},W}^{2}\left(i,j\right)={W}^{-1}\sum _{p=i-U}^{i+U}\sum _{q=j-V}^{j+V}{\left[{\stackrel{̂}{x}}_{k}\left(p,q\right)-{m}_{{\stackrel{̂}{x}}_{k},W}\left(i,j\right)\right]}^{2},$
where $W=\left(2U+1\right)×\left(2V+1\right)$ is the extent of the analysis window that is symmetric about the point $\left(i,j\right)$ . In addition, the local maximum of the partially restored image at point $\left(i,j\right)$ is defined as

## 7

${\stackrel{̂}{x}}_{k,W,\mathrm{max}}\left(i,j\right)={\mathrm{max}}_{\left(p,q\right)∊{S}_{\left(i,j\right)}}{\stackrel{̂}{x}}_{k}\left(p,q\right),$
where ${S}_{\left(i,j\right)}$ is the support region that determines the local maximum about the point $\left(i,j\right)$ . In this work, it is same with the analysis window used for the local mean and variance. Using the local information in Eqs. 6, 7, a parameter controlling the degree of local smoothing is defined as

## 8.

$P\left[{\stackrel{̂}{x}}_{k}\left(i,j\right)\right]=\left\{\begin{array}{ll}{E}_{1}\left(i,j\right)& \text{if}\phantom{\rule{0.3em}{0ex}}{\stackrel{̂}{x}}_{k}\left(i,j\right)<{E}_{1}\left(i,j\right)\\ {E}_{2}\left(i,j\right)& \text{if}\phantom{\rule{0.3em}{0ex}}{\stackrel{̂}{x}}_{k}\left(i,j\right)>{E}_{2}\left(i,j\right)\\ {\stackrel{̂}{x}}_{k}\left(i,j\right)& \text{otherwise}\end{array}\phantom{\right\}},$
${E}_{1}\left(i,j\right)=\mathrm{max}\left[0,{m}_{{\stackrel{̂}{x}}_{k},\mathit{SW}}\left(i,j\right)-{T}_{k}×B\left(i,j\right)\right],$
${E}_{2}\left(i,j\right)=\mathrm{min}\left[{2}^{L}-1,{m}_{{\stackrel{̂}{x}}_{k},\mathit{SW}}\left(i,j\right)+{T}_{k}×B\left(i,j\right)\right],$
for $L$ bits per pixel. In Eq. 8, ${T}_{k}$ is a threshold to be determined and $B\left(i,j\right)$ is defined as

## 9

$B\left(i,j\right)=\frac{{\sigma }_{{\stackrel{̂}{x}}_{k},\mathit{LW}}^{2}\left(i,j\right)}{{\sigma }_{{\stackrel{̂}{x}}_{k},\mathit{SW}}^{2}\left(i,j\right)}×\frac{{\stackrel{̂}{x}}_{k,\mathit{SW},\mathrm{max}}\left(i,j\right)}{{m}_{{\stackrel{̂}{x}}_{k},\mathit{SW}}\left(i,j\right)}.$
In Eq. 9, $SW$ and $LW$ represent the relatively small and large window sizes centered at point $\left(i,j\right)$ .

In general, noise amplification contributes to the problem of restoration, and therefore desirable properties such as detection of noisy pixels and the degree of local activity should be incorporated into the restoration process to effectively suppress noise amplification. It is clear how the local statistics affect $B\left(i,j\right)$ . Let us assume that ${\stackrel{̂}{x}}_{k}\left(i,j\right)$ is a noisy pixel belonging to an element of a homogeneous activity region. In such a case, ${\sigma }_{{\stackrel{̂}{x}}_{k,SW}}^{2}\left(i,j\right)$ is greater than ${\sigma }_{{\stackrel{̂}{x}}_{k,LW}}^{2}\left(i,j\right)$ , and therefore local smoothing is necessary to suppress the noise amplification. As the noise increases, the variance ratio decreases, leading to smaller $B\left(i,j\right)$ . In addition, when the same noise is added to low and high activity regions, the noise within the low activity region is more visible than that within the high activity region. Therefore, tighter bounds should be applied to the noisy pixel within the low activity region than to that within the high activity region. ${\stackrel{̂}{x}}_{k,SW,\mathrm{max}}\left(i,j\right)∕{m}_{{\stackrel{̂}{x}}_{k,SW}}\left(i,j\right)$ in Eq. 9 is used as a way to represent the degree of local activity in this work. As the local activity decreases, $B\left(i,j\right)$ decreases. A smaller $B\left(i,j\right)$ leads to tighter bounds, while looser bounds are for a larger $B\left(i,j\right)$ , so that the noise amplification is effectively suppressed. They are in agreement with the noise masking property in areas of high spatial activity of the human visual system.8

Local information has the limit to effectively suppress noise amplification. Therefore, global information about the noise can help to effectively reduce noise amplification. For example, tighter bounds are more desirable as the additive noise increases. ${T}_{k}$ in Eq. 8 is used to incorporate global information into the restoration process, so that it can control the degree of bounds that is computed at each iteration step, such as

## 10

${T}_{k}=\mathrm{exp}\left[Z×\frac{\sum _{i}\sum _{j}|{x}_{k-1}\left(i,j\right)|}{\sum _{i}\sum _{j}|{n}_{k-1}\left(i,j\right)|}\right],$
where $Z$ represents a constant, and ${\mathbf{n}}_{k-1}=\mathbf{y}-\mathbf{H}{\mathbf{x}}_{k-1}$ .

The proposed algorithm is used to obtain a solution that is an element of the intersection set between a solution space using the gradient approach reflecting the global smoothing constraint, and a projection set incorporating the local smoothing constraint.

## Experimental Results and Conclusions

The proposed adaptive hybrid image restoration algorithm is tested with various noisy blurred images and degradation, and it is compared to typical RCLS. In the set of such experiments, the $256×256\phantom{\rule{0.3em}{0ex}}\text{pixels}$ Lena and Cameraman images are described here. The original images were blurred by $7×7$ motion blur and Gaussian blur with variance of 5. A Gaussian-distributed noise signal was added to the blurred images. We tested the proposed algorithm for various SNRs. In addition, a 2-D Laplacian operator was used for the high-pass operator in Eq. 2.2 For evaluating the objective and subjective performance of the algorithm, the mean squared error (MSE) and structural similarity index (SSIM) in Ref. 9 were used, where SSIM takes a value between $-1$ (the worst value) and 1 (the best value). Also,

## 11

$\frac{{‖{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}‖}^{2}}{{‖{\mathbf{x}}_{k}‖}^{2}}⩽{10}^{-m}$
was used for terminating the iteration. In these experiments, $m=5$ was used for 5- and $10\text{-}\mathrm{dB}$ noises. Also, $m=6$ and $m=7$ were used for 20- and $30\text{-}\mathrm{dB}$ noises, respectively. In addition, $SW=3$ and $LW=7$ were used for small and large size windows in Eq. 9.

Figures 1, 1, 1 show the degraded Lena image ( $7×7$ Gaussian blur with variance of 5- and $10\text{-}\mathrm{dB}$ Gaussian noise), the restored image with RCLS, and the restored image with the proposed method, respectively. For $Z=0.07$ , the proposed algorithm converges after ten iterations ( $\mathrm{MSE}=260$ and $\mathrm{SSIM}=0.677$ ), while RCLS requires 39 iterations ( $\mathrm{MSE}=493$ and $\mathrm{SSIM}=0.432$ ). The results show that RCLS leads to noise amplification in the restored image. On the other hand, the proposed hybrid algorithm effectively suppresses the noise amplification. When tighter bounds (smaller $Z$ ) are used, the convergence becomes faster. However, tighter bounds result in oversmoothed images. On the basis of our experiments, $0.05⩽Z⩽0.1$ is a good range with convergence speed and performance.

## Fig. 1

Experimental results with Lena image: (a) noisy blurred image ( $7×7$ Gaussian blur with variance of 5- and $10\text{-}\mathrm{dB}$ Gaussian noise), (b) restored image with RCLS (39 iterations, $\mathrm{MSE}=493$ , and $\mathrm{SSIM}=0.432$ ), and (c) restored image with proposed hybrid method (ten iterations, $\mathrm{MSE}=260$ , and $\mathrm{SSIM}=0.677$ ).

Figures 2 and 2 show MSE and convergence speed comparisons as a function of iteration number for Lena image when $10\text{-}\mathrm{dB}$ Gaussian noise is added. The results show that the proposed algorithm has the capability to keep a minimum mean squared error, while RCLS is very sensitive to the terminating criterion, since the noise is amplified after a certain iteration number. Also, it is verified that the proposed algorithm is faster than RCLS for all cases.

## Fig. 2

Performance comparisons with Lena image: (a) MSE as a function of iteration number, and (b) convergence rate as a function of iteration number.

Tables 1, 2 summarize the performance comparisons (MSE, SSIM, and iteration number) at convergence for Gaussian blur and motion blur, respectively. As expected, the performance gain of the proposed algorithm increases as the additive noise increases. However, as the additive noise decreases, looser bounds are necessary to avoid oversmoothed images. As shown in Tables 1, 2, the proposed algorithm performs similarly to RCLS for additive noise less than $30\phantom{\rule{0.3em}{0ex}}\mathrm{dB}$ .

## Table 1

Performance comparisons at convergence (Lena).

Noise(dB)MethodGaussian blurMotion blur
MSESSIMIteration NumberMSESSIMIteration Number
5RCLS17990.2306623360.20466
Hybrid3030.612102880.6339
10RCLS4930.432397970.35249
Hybrid2600.677102450.7039
20RCLS2120.647642410.59874
Hybrid1890.730381740.73453
30RCLS1390.7721231250.773127
Hybrid1390.7721231250.773127

## Table 2

Performance comparisons at convergence (Cameraman).

Noise(dB)MethodGaussian blurMotion blur
MSESSIMIteration NumberMSESSIMIteration Number
5RCLS24230.1616430710.15063
Hybrid4710.49594580.5068
10RCLS6910.3043810490.25247
Hybrid4090.59293930.6058
20RCLS3240.490663500.44674
Hybrid3050.642352800.63654
30RCLS2020.6771351820.671134
Hybrid2010.6781331810.671134

The novelty of the proposed algorithm is that it leads to faster convergence speed, and subjectively and objectively better performance than typical RCLS without prior information of an original image by incorporating the local smoothing constraint.

We propose an iterative adaptive hybrid image restoration algorithm using a local smoothing constraint. Each pixel in an image is projected onto a local smoothing set determined by the local mean, variance, and maximum intensity value of the partially restored image. The ratio of these parameters is used to define the convex set, resulting in effective suppression of the noise amplification and faster convergence speed.

## Acknowledgments

This research was supported by the Korea Science and Engineering Foundation (KOSEF) grant funded by the Korea government (MEST) (number 2010-0000397) and the Ministry of Knowledge Economy, Korea under the Information Technology Research Center support program supervised by the National IT Industry Promotion Agency [NIPA-2010-(C1090-1011-0003)].

## References

1.  H. C. Andrews and B. R. Hunt, Digital Image Restoration, Prentice Hall, New York (1977). Google Scholar

2.  M. R. Banham and A. K. Katsaggelos, “Digital image restoration,” IEEE Signal Process. Mag.1053-5888 14(2), 24–41 (Mar. 1997). 10.1109/79.581363 Google Scholar

3. Image Recovery; Theory and Application, H. Stark, Ed., Academic Press, San Diego, CA (1987). Google Scholar

4.  M. E. Zervakis and T. M. Kwon, “Robust estimation techniques in regularized image restoration,” Opt. Eng.0091-3286 31(10), 2174–2190 (Oct. 1992). 10.1117/12.59978 Google Scholar

5.  M. C. Hong, T. Stathaki, and A. K. Katsaggelos, “Iterative regularized least-mean mixed-norm image restoration,” Opt. Eng.0091-3286 41(10), 2515–2524 (Oct. 2002). 10.1117/1.1503072 Google Scholar

6.  S. W. Jung, T. H. Kim, and S. J. Ko, “A novel multiple image deblurring technique using fuzzy projection onto convex sets,” IEEE Signal Process. Lett.1070-9908 15(3), 192–195 (2009). 10.1109/LSP.2008.2012227 Google Scholar

7.  M. G. Kang and A. K. Katsaggelos, “General choice of the regularization functional in regularized image restoration,” IEEE Trans. Image Process.1057-7149 4(5), 594–602 (May 1995). 10.1109/83.382494 Google Scholar

8.  G. L. Anderson and A. N. Netravali, “Image restoration based on a subject criterion,” IEEE Trans. Syst. Man Cybern.0018-9472 SMC-6, 845–853 (Dec. 1976). 10.1109/TSMC.1976.4309481 Google Scholar

9.  Z. Wang, C. Bovik, H. R. Sheikh, and E. P. Simoncelli, “Image quality assessment: From error visibility to structural similarity,” IEEE Trans. Image Process.1057-7149 13(4), 600–612 (Apr. 2004). 10.1109/TIP.2003.819861 Google Scholar

Min-Cheol Hong, "Iterative adaptive hybrid image restoration for fast convergence," Optical Engineering 49(8), 080503 (1 August 2010). https://doi.org/10.1117/1.3479935
JOURNAL ARTICLE
3 PAGES

SHARE
KEYWORDS