BESOV SEMI-NORM REGULARIZATION AND COMPUTATIONAL ALGORITHM FOR IMAGE RESTORATION

DAI-GYOUNG KIM

In this paper, we propose an adaptive iteration algorithm for signal/image restoration. For digital signals, this algorithm minimizes a piecewise l_{q}, 0 < q ≤ 1, functional defined on wavelet domain with single equality constraint. This minimization algorithm is from a Besov semi-norm penalty method and corresponds to a restoration process. In practice, restoration and enhancement processes have many applications in information technology areas such as digital communications, CCD/CCTV imaging, medical imaging, and astronomy telescope imaging.

Observed or acquired signal/image data through a communication system are usually blurred and noisy. The restoration and enhancement of blurred and noisy data are ill-posed inverse problems in theoretical and computational point of views. Mathematically, an acquired signal is modeled via an integral equation:

g = Af + w (1)

where g is the acquired signal which is degraded by a blurring operator A and a random noise w from original signal f. In signal/image processing applications, A is usually modeled as a convolution operator and w a Gaussian white random process (cf. [1], [9]); for instance, A is represented by the Gaussian kernel function k(x, y) = \frac{1}{\sqrt{π}σ} e^{− \frac{(x−y)}{σ^{2}}} as

Af(x) = ∫ k(x, y)f(y) dy.

In this case, A is a compact operator or generally a Fredholm first kind integral operator, so that the problems of the form (1) are ill-posed problems in the sense of Hadamard.

Many image restoration methods have been recently proposed (cf. [5]). One basic approach is to formulate the restoration problem as a constrained least squares problem. This approach is a regularization method. A general form of regularization of the problem (1) is the constrained minimization problem with respect to f:

min J(f)
subject to ∥Af − g∥_{2} = σ

(2)

where J is a certain objective functional, σ is the standard deviation of the noise w, and ∥ · ∥_{2} denotes the L_{2}-norm. There are several possible choices of the objective functional J, for instance, the L_{2}-norm of the gradient ∇f or some higher derivatives of f. For signal/image processing applications, Rudin et al. [8], [9] have recently suggested the use of the bounded variation (BV) semi-norm J(f) = |f|_{BV}. With this choice, a solution of (2) provides an image with the least total variation among all the images with the standard deviation σ, so that the bounded variation based restoration algorithm has a great success in the recovery of corrupted piecewise constant images such as blocky images.

Rudin et al.’s BV based method has, however, a disadvantage for the piecewise smooth signals/images. In this paper, a numerical simulation is presented to demonstrate the BV based method fails. In addition, we propose a Besov semi-norm regularization method for the problem (2) to overcome the disadvantage while keeping non-oscillatory (minimal ringing) and non-invasive (edge preserving) reconstruction.

The minimization problem (2) with J(f) = |f|_{BV} can be solved by finding the steady state of the nonlinear diffusion process driven by the Euler-Lagrange equation (cf. [8], [9]). Because of the complicate nonlinear structure of Besov semi-norm(cf. [10]), the minimization problem (2) with Besov semi-norm:

min |f|_{B_{q}^{α}}
subject to ∥Af − g∥_{2} = σ

(3)

can not be handled by the Euler-Lagrange formulation. However, in computation, the minimization problem (3) can be considered as an l_{q}-norm minimization problem. In [4], [3], the Besov semi-norm is characterized in terms of a weighted l_{q}-norm of wavelet coefficients. Using the wavelet coefficient characterization of the signal f, we reformulate the minimization problem (3) as a weighted l_{q}-norm problem with single equality constraint.

For 0 < q ≤ 1, the l_{q}-norm problem is a nonlinear piecewise differentiable minimization problem with singularity at the origin. So, it is difficult to reach an optimal solution to the minimization problem. There has recently been reports [6], [2] for a globally convergent method for l_{q}-norm problems. In [7], the authors have proposed a reliable and efficient computational algorithm based on the BV semi-norm reguarization method. This algorithm basically minimizes a piecewise linear l_{1} objective functional (a measure of bounded variation). For solving this constrained l_{1} minimization problem, an affine scaling Newton method is employed in [6], [7]. We adapt the affine scaling Newton method for solving our l_{q}-norm minimization problem.

References

1. A. Bakushinsky and A. Goncharsky, Ill-Posed Problems: Theory and Applications, MIA Series, Kluwer Academic Publ., Norwell, MA 1994.

2. T. Coleman and Y. Li, A Globally and Quadratically Convergent Affine Scaling Method for Linear l_{q} problem, Mathematical Programming, 56, 189–222 (1992).

3. R. DeVore, B. Jawerth, and V. Popov, Compression of Wavelet Decomposition, Amer. J. Math., 114, 737–785 (1992).

4. D.-G. Kim, Littlewood-Paley Type Estimates for Besov spaces on a Cube by Wavelet Coefficients, J. of Kor. Math. Soc., 36(6), 1075–1090 (1999).

5. R. Lagendijk and J. Biemond, Iterative Identification and Restoration of Images, Kluwer Academic Publ., Norwell, MA 1991.

6. Y. Li, A Globally Convergent Method for l_{q} Problems, Mathematical Programming, 3, 609–629 7. Y. Li and F. Santosa, Computational Algorithm for Minimizing Total Variation in Image Restora-

tion, IEEE Trans. on Image Processing, (to appear).

8. L. Rudin, S. Osher, and C. Fatemi, Nonlinear Total Variation Based Noise Removal Algorithm, Physica D., 60, 259–268 (1992).

9. L. Rudin, S. Osher, and C. Fu, Total Variation Based Restoration of Noisy Blurred Images, SIAM J. Numer. Anal., (to appear).

10. H. Triebel, Theory of Function Spaces II, Birkhauser Verlag, Basel, 1992.

Department of Mathematics, Hanyang University, Ansan, 425-791 Korea

  E-mail address: kim@banach.hanyang.ac.kr