Документ взят из кэша поисковой машины. Адрес оригинального документа : http://imaging.cs.msu.su/pub/Krylov_PRIA2008.pdf Дата изменения: Wed Sep 17 23:00:00 2008 Дата индексирования: Sat Apr 9 22:39:36 2016 Кодировка:

IMAGE ENHANCEMENT BY TOTAL VARIATION QUASI-SOLUTION METHOD1
A.S. Krylov, V.N. Tsibanov, A.M. Denisov

MSU, Faculty of computational mathematics and cybernetics, Leninskie Gory, Moscow, Russia, 119991 kryl@cs.msu.su, tsibanov@angel.cs.msu.su, den@cs.msu.su

New method of image restoration, based on quasi-solution method for compact set of functions with bounded total variation is introduced. Application of this method does not need an estimation of the noise level, which is necessary to choose regularization parameter in the Tikhonov regularization method. The approbation of this method with test images shows effectiveness of this method for image deringing. Introduction Image restoration is one of the classical inverse problems in image processing and computer vision, which consists of the recovering information about the original image from incomplete or degraded data. Reconstruction of an image from observed data is often an ill-posed inverse problem. The solution of these inverse problems can be achieved using regularization methods, which turn the problem into a well-posed, and prevent the amplification of noise during the reconstruction process. Many linear problems of image restoration which are not well-posed can be posed as problems of solution of equation
Az = u, z Z, u U ,

(1)

1

This research was supported by EOARD grant CRDF # RUP1 -1515-MO-06


where Z and U are Hilbert spaces, A : Z U is a linear continuous operator, and the inverse operator

A

1

exists but is unbounded. Thus, the problem (1) is ill-posed [1, 2] and the corresponding matrix for

operator , is ill-conditioned. Tikhonov regularization method [1, 2] is usually used for the stabilization of this problem. This makes the problem well-posed and prevents noise amplification during restoration when we construct an approximation ~ of unknown source function z from observed degraded (noisy) function z
u : Az u
L2

.

For image restoration tasks [3], we find function ~ , minimizing functional z

E ( z ) [( Az u ) 2 ( z )]dx ,
2

(2)

where u is initial degraded image. In image processing, the following classes of functions are usually used: (a) Tikhonov functional

(t ) t , (b) total variation (TV) (t ) t [4,5]. The paper [3] introduces other useful functions.
The utilization of Tikhonov functional leads to quadratic problem, but strongly smoothes sharp edges. TV method allows to find discontinuous solutions, so it better preserves edges during restoration. Its application for image restoration shows good results (it does not oversmooth or displace edges), but has drawbacks. We need to estimate noise level for appropriate regularization parameter selection. In this paper, we consider an alternative regularization method, based on discrepancy minimization on the set of functions with bounded TV, which is compact in L2 space. The article is organized in the following manner. TV Quasi-solution method is discussed in section 2. Section 3 presents numerical scheme. Test results for different image enhancement tasks are shown in section 4. Quasi-solution Method Quasi-solution method has been introduced by Ivanov in his papers [6].


Definition. Point z K M for which Az u reaches a minimum on a given compact set M of the space Z is called quasi-solution on M for a given u

z K arg inf Az u .
zM

(3)

If we assume that operator is continuous, the discrepancy Az u will be continuous functional, which reaches the infimum on compact set M. Thus, a quasi-solution exists for every u U . Lets note as Z

K

set of quasi-solutions (3) on compact set M for element u .

If for exact right part u the equation (1) has single solution z which belongs to the compact M, then

sup z z 0 , when u u 0 [2]. So the problem of quasi-solutions determination is well-posed.
zZ
K



Quasi-solution method for bounded total variation functions (TVQ)

We applied quasi-solution method for solving problem (1) in one-dimensional case. Definition. The total variation of a real-valued function f defined on an interval [a, b] is the value
Vab f sup f xk f xk
P k =1 n 1

, where P {x0 , , x n } is a partition of [a, b] [7].

The set of bounded functions V = z : V



b a

z

C , with variation less then constant C 0 , is a




compact set in L2 a, b space. Thus, approximate solution of a problem (1) found on the set V converge to the exact solution z Z L2 a, b, if u u 0 .

will

So we consider the following total variation quasi-solution method (TVQ) to solve problem (1) in onedimensional case: we construct the sequence that minimizes the discrepancy functional
F z = Az u
2

on the set of functions with TV less than given value .

It is necessary to underline that TVQ method does not need information on the noise level in contrast to Tikhonov regularization method. Instead of regularization parameter we use the value of signal TV as the stabilizing parameter.


Numerical Scheme For the first time the numerical method to solve TVQ problem has been considered in the book [8]. After discretization, we get the following problem: to construct a sequence of ve ctors z l R n that minimizes discrete analog of the discrepancy functional F on the convex set VC , where V of vectors z R n , which components satisfy conditions:
C

is the set

z

2

z1 + z3 z 2 ++ z n z

n 1



C

zn = 0 .
As Vab z Vab z c , it is natural to fix the value of function on an end of se gment [a, b] . Thus we assume that we know one of the boundary value z a or z b thus z n = 0 ). Since considered functional has Frechet derivative satisfying Lipschitz condition with the con stant



(hereinafter we assume, that z b = 0 ,

L = 2 A , the conditional gradient method can be used to solve this problem [9].

2

The Conditional Gradient Method

The conditional gradient method generates a sequence {z l } of approximations according to the following procedure. 1. First we choose an arbitrarily vector z 0 VC . 2. Along with minimizing sequence z l , we construct auxiliary sequence z
l

F' z l , z l
zVC

=

min zVC

F' z l , z

.

(4)

The solution vector z l arg min F' z l , z exists, but it is not necessary unique. Vector z l belongs to the boundary of the VC .


In our case, the considered set of vectors VC represents convex polyhedron with 2 n 1 vertices in

R

n

space. Polyhedron vertices

j

, j = n 1,, 1, 1,, n 1 can be found out analytically and

look like:

T

j
T

C, = i 0,
j

i j , i > j
j

j = 1, 2, , n 1

= T

,

j = 1, 2,, n 1

So the problem (4) can be solved by simple enumeration of these vertices. 3. After construction of the auxiliary vector z l we build vector z
l +1

by the formula

z

l +1

= z l + l z l z l ,

where l 0,1 is the solution of one-dimensional minimizing problem
F z
l +1



= F z l + l z l z

l



=

min 0 ,1

F z l + z l z

l



.

(5)

In our case, operator A is linear, so F ( z ) is a quadratic functional. Thus the problem (5) is trivial: to find parabola minimum on the segment [0,1]. The set VC is convex, so z
l +1

VC . Thus, after beginning of iteration process with the vector z 0 VC ,
C

we will not fall outside the limits of the set V

during minimization. If operator A is linear, the

constructed sequence z l is minimizing sequence for functional F ( z ) on the set VC . Applications The proposed TVQ regularization method is applicable in different areas like image restoration, super resolution and interpolation. Below the TVQ method is applied to image deringing. Gibbs phenomenon (ringing effect) is caused by the quantization or truncation of the high frequency information by approximation method. It can be seen for the cut off of the coefficients of Fourier or wavelet transform [10]. Ringing caused by iterative deconvolution algorithms is analyzed in [11]. In the spatial domain, this effect produces spurious oscillations near sharp edges.


To reduce Gibbs phenomenon we have applied TVQ method with unit operator A. In this case the constant of TVQ method is a smoothing parameter. Decreasing of leads to Gibbs effect suppression but also smoothes the result. It is obvious, that constant C selection equal to the source undisturbed function TV value promotes the best results. In real situations, we do not know information on TV of the undisturbed function and we set parameter equal to TV value of the given function multiplied by a decimation coefficient. Fig. 1 shows Gibbs effect reduction for the result of function approximation by 100 functions of Fourier series.

Fig. 1. Gibbs effect reduction

.

Source signal (with Gibbs effect) (dots) and smoothed signal (decimation coe fficient is equal to 0.75) (solid line).

As we can see TVQ method eliminates ringing effects and practically does not decrease edge strength. For image processing (see a result in Fig. 2) we perform one dimensional TVQ procedures for every row and every column of image. The resulting image is average of these two obtained images. Conclusion In this paper, we have considered novel image restoration procedure based on quasi-solution method for the compact set of functions with bounded TV. The application of this method does not need an estimation of the noise level , which is necessary to choose regularization parameter in the Tikhonov functional. This information on the level of noise is usually unavailable and the selected regularization parameter does not have a reasonable explanation. In our case, we use the information on image TV


value. The approbation of this method with test images shows effectiveness of this method for image deringing. This quasi-solution method looks also promising to be used in other areas of TV fun ctional successful applications.

a) Source image

b) Smoothed image (decimation coefficient equal to 0.75)

c) Detail of a source image Fig. 2. Gibbs effect reduction.

d) Detail of a smoothed image

References
1. Tikhonov A.N., Arsenin V.Y.: Solutions of Ill Posed Problems. WH Winston, Washington DC (1977)


2. Denisov A.M.: Elements of the Theory of Inverse Problems. VSP, Netherlands (1999) 3. Teboul S. et.al.: Variational approach for edge-preserving regularization using coupled PDE's. IEEE Transactions on Image Processing, Vol.7, No. 3 (1998) 387­396 4. Rudin L., Osher S.J., Fatemi E.: Nonlinear total variation based noise removal algorithms. Physica D. (1992) 60, 259­ 268 5. Chambolle A., Lions P.: Image Recovery via Total Variation Minimization and Related Problems. Numer. Math. 76 (1997) 167­188 6. Ivanov V. K.: On linear ill-posed problems. Dokl. Acad. Nauk. SSSR, vol. 145 (1962) 270 ­272 (in Russian) 7. Natanson I.P.: Theory of functions of a real variable. Ungar Pub Co , New York (1961) 8. Tikhonov A.N., Goncharsky A.V., Stepanov V.V., Yagola A.G.: Regularizing algorithms and apriori information. Nauka, Moscow (1983) (in Russian) 9. Vasiliev F.P.: Numerical Methods for Solving Extremum Problems. Nauka, Mo scow (1988) (in Russian) 10. Mallat S.: A Wavelet Tour of Signal Processing. Academic Press (1999). 11. Balasubramanian M. et al: A ringing metric to evaluate the quality of images restored using iterative deconvolution algorithms. ICSEng (2005), 483 ­ 488.