DOI : 10.17577/IJERTV3IS090404
- Open Access
- Total Downloads : 127
- Authors : Veena A M, Dr Muralidhara B
- Paper ID : IJERTV3IS090404
- Volume & Issue : Volume 03, Issue 09 (September 2014)
- Published (First Online): 17-09-2014
- ISSN (Online) : 2278-0181
- Publisher Name : IJERT
- License:
This work is licensed under a Creative Commons Attribution 4.0 International License
A Majorize – Minimize Strategy for Subspace Optimization Applied to Image Restoration
Veena A. M .
Assistant Professor, Department of EEE Sri Venkateshwara College of Engineering Bangalore, India.
AbstractImage restoration by sub-space optimization is discussed in this paper which is based on majorize- minimize principle using a multidimensional search strategy this includes Subspace Constructions, Multidimensional search procedures, Majorize-minimize technique for step size calculation, Convergence properties for overall subspace algorithms. Subspace optimization method belongs to class of iterative descent algorithms for unconstrained optimization. At each iteration of such methods, a step size vector allowing the best combination of reversal search directions is computed through a multi- dimensional search it is usually obtained by an inner iterative 2nd order method. The choice of subspace depends on convergence and cost of computation per iteration. Geman and Yang (GY) and Geman and Reynolds (GR) matrices are used in the multidimensional step-size strategy. MM linear search yields the convergence of standard descent algorithms without stopping condition. A final convergence analysis is done for the iterative subspace algorithm. Comparison between the linear search and the multi- dimensional search is illustrated in context their effectiveness and efficiency in restoring the image.
Keywords Image Restoration, Optimization, GY and GR matrices, convergence.
-
INTRODUCTION
Image processing is a method to convert an image into digital form and performs some image processing operations on it, in order to get an enhanced image or to extract some useful information from it. It is a type of dispensation in which input is an image, like photograph and output may be image or characteristic associated with that image. Usually image processing system includes treating images as two dimensional signals while applying already set signal processing methods on to them.
Image is a picture or illustration, often taken from sensible objects and used to illustrate an object.
Pixel (Picture element) is the smallest controllable element of a picture represented on the screen.
In this, we will consider the following basic classes of problems
-
Image representation and modeling.
-
Image enhancement.
-
Image restoration.
-
Image analysis.
-
Image data compression.
Dr. Muralidhara B.
Professor and Head, Department of EEE Sri Venkateshwara College of Engineering Bangalore, India.
Image Representation and Modeling is concerned with characterization of the quantity that each picture element represents. An image could represent luminance of object in scene. Image models give a logical or quantitative description of the properties of this function.
Image Enhancement goal is to accentuate certain image features for subsequent analysis or image display.
Image Restoration refers to removal or minimization of known degradation in an image.
Image Analysis is concerned with making quantitative measurements from an image to produce a description of it.
Image data compression techniques are concerned with reduction of the number of bits required to store or transmit images without any appreciable loss of information.
Purpose of image processing
Image processing is rapidly growing technology with its applications in various aspects.
Purpose of image processing is divided into five groups. They are
-
Visualization observe the objects that are not visible clearly.
-
Image sharpening and restoration- to create better image.
-
Image retrieval- seeks for the image of interest.
-
Measurement of pattern- measures various objects in an image.
-
Image recognition- distinguishes the objects in an image.
-
The purpose of image restoration is to compensate for defects which degrade an image. Degradation comes in many forms such as motion blur, noise and improper focus of camera. In cases like motion blur, it is possible to come up with a very good estimate of the actual blurring function and "undo" the blur to restore the original image. In cases where the image is corrupted by noise, the best we may hope to do is to compensate for the degradation it caused. In this project, we will introduce and implement several methods used in the image processing world to restore images.
-
-
IMAGE RESTORATION
Image Restoration refers to a class of methods that aim to remove or reduce the degradations that have occurred while the digital image was being obtained. An image is restored after it has lost its most important features or degraded. An image could be degraded during digitization or during transmission.
During digitization or transmission a noise may be included in a digital image from the environment around it. For example, while taking a picture using a camera a noise is added by the camera fault, the image sensor or from the environment where the image is taken. When it is from the camera fault it means if the shutter speed of the camera is too long. This causes a noise type called salt-and-pepper.
Image sensors are made to collect light. During collection of light more light might be collected and causes high temperature which would result in Gaussian noise type. But when it is from the environment where the image is taken it might be from light reflections.
During image transmission the noise might be caused by a small bandwidth which causes the image not to transmit fully making it blur. A noise is caused by the environment around us. Therefore it is important to restore the images to their original features by removing the noise. In order to remove the noise someone has to know the noise itself so that it would be easy to remove it. Different types of noises are studied by adding them to an original image and use certain ways to remove those noises.
All natural images when displayed have gone through some sort of degradation.
The degradations may be due to Sensor noise, Blur due to improper focus of camera, Relative object- camera motion and Random atmospheric turbulence.
Image Restoration can be done depends on how much we know about
-
The original image
-
The degradation
Image restoration and image enhancement-differences:
Image restoration differs from image enhancement in that the latter is concerned more with accentuation or extraction of image features rather than restoration of degradations.
Image restoration problems can be quantified precisely, whereas enhancement criteria are difficult to represent mathematically.
-
-
MAJORIZE MINIMIZE TECHNIQUES
This has been analyzed and implemented into two parts as given below.
-
Subspace Optimization
-
Multidimensional step size strategies.
-
Subspace Optimization
Here we have two more classification/algorithms:
-
Subspace Construction
-
Step size Strategies
-
-
Subspace Construction
Choosing subspaces of dimensions larger than one may allow faster convergence in terms of iteration number. However, it requires a multidimensional stepsize strategy, which can be substantially more complex and computationally costly than the usual line search. Therefore, the choice of the subspace must achieve a tradeoff between the iteration number to reach convergence and the cost per iteration.
wo families of algorithms are distinguished.
-
Memory Gradient Algorithms.
-
Newton type Subspace Algorithm
To accelerate optimization algorithms, a common practice is to use a preconditioning matrix. The principle is to introduce a linear transform on the original variables, so that the new variables have a Hessian matrix with more clustered Eigen values. Preconditioned versions of subspace algorithms are easily defined by using instead of in the previous direction sets.
-
-
Stepsize Strategies
The aim of the multidimensional stepsize search (5) is to determine that ensures a sufficient decrease of function defined in order to guarantee the convergence of recurrence (4). In the scalar case, typical line search procedures generate a series of step size values until the fulfillment of sufficient convergence conditions. An extension of these of these conditions to the multidimensional case can easily be obtained. However, it is difficult to design practical multidimensional step size search algorithms allowing checking these conditions. Instead, in several subspace algorithms, the stepsize results from an iterative descent algorithm applied to function stopped before convergence. In Sequential subspace optimization (SESOP), the minimization is performed by a Newton method. However, unless the minimize is found exactly, the resulting subspace algorithms are not proved to converge. The proposed step size search is proved to ensure the convergence of the whole algorithm, under low assumptions on the subspace, and to require low computational cost.
Multidimensional step size strategies
-
GR and GY Majorizing Approximations.
-
Majorize-Minimize Line search.
-
MM Multidimensional Search.
-
Convergence Analysis.
-
GR and GY Majorizing Approximations: –
Let us first introduce Geman and Yang[3] and Geman and Reynolds[2] matrices AGY and AGR, which play a central role in the multidimensional step size strategy proposed in this project.
= 2 + (1)
= 2 + { }(, ) (2)
Majorize Minimize Line search:-
The distinctive feature of the MM line search is to yield the convergence of standard descent algorithms without any stopping condition whatever the number of MM sub iterations J and relaxation parameter
(0,2). Here, we propose to extend this
strategy to the determination of the multidimensional stepsize, and we prove
the convergence of the resulting family of subspace algorithms.
MM Multidimensional search:-
Let us define the M×M symmetric positive definite
Figure 2- Restoration model
The application that we will study is based on various types of image restoration methods.
Description of the method:
Suppose to solve the following system of
(SPD) matrix
linear equations
= , = + +
Ax = b
1
T
2 (3)
Convergence analysis:-
It establishes the convergence of the iterative subspace algorithm when step size is chosen according to the majorize-minimize strategy.
Methodology:-
It consider three image processing problems, namely image deblurring, tomography and compressive sensing, the synthesis based approach is used for the reconstruction. The image is assumed to be well described as with a known dictionary and a sparse vector. The restored image is then defined as where minimizes the PLS criterion (4) is given as
Where the n-by-n matrix A is symmetric (i.e., A
= A), positive definite (i.e., xTAx> 0 for all non-zero vectors x in Rn) and real. We denote the unique solution of this system by x*.
The conjugate gradient method as a direct method
We say that two non-zero vectors u and v are conjugate (with respect to A) if
(5)
Since A is symmetric and positive definite, the left- hand side defines an inner product
=1
= 2+
( ) (4)
[, ]= , = , = , = (6)
A model of image degradation and restoration The block diagram on general degradation
model
Two vectors are conjugate if they are orthogonal with respect to this inner product. Being conjugate is a symmetric relation: if u is conjugate to v, then v is conjugate to u.
=1
Suppose that {pk} is a sequence of n mutually conjugate directions. Then the pk form a basis of Rn, so we can expand the solution x* of Ax = b in this basis:
Figure 1- General degradation model
=
(7)
Where y is the corrputed image obtained by passing the original image x through a low pass filter (blurring fuction) h and adding noise to it as shown in
The coefficients are given by
= = = =
Fig 1. We present four different ways of restoring the image.
=
=1
=1
(8)
Where h(x,y) is a spatial representation of the degradation function and the symbol * indicates
(because , , )
convolution. Note that we only have the degraded image g (x,y), the objective of restoration is to obtain an estimate f| (x,y) of the original image. We want the estimate to be as close as possible to the
=
= [ , ] =
[ , ] [ , ]2
(9)
original input image and in general the more we know about H and n the closer f|'(x,y) will be close to f(x,y) as shown in Figure 2.
This result is perhaps most transparent by considering the inner product defined above. This gives the following method for solving the equation Ax = b find a sequence of n conjugate directions and then compute the coefficients k.
The conjugate gradient method as an iterative method:
If it choose the conjugate vectors pk carefully, then
we may not need all of them to obtain a good approximation to the solution x*. So, it has to regard the conjugate gradient method as an iterative method. This also allows us to solve systems where n is so large that the direct method would take too much time.
It denote the initial guess for x* by x0 and can assume without loss of generality that x0 = 0 (otherwise, consider the system Az = b Ax0 instead). Starting with x0 we search for the solution and in each iteration we need a metric to tell us whether we are closer to the solution x* (that is unknown to us). This metric comes from the fact that the solution x* is also the unique minimizer of the following quadratic function; so if f(x) becomes smaller in an iteration it means that we are closer to x*.
= 1 , (10)
2
This suggests taking the first basis vector p1 to be the negative of the gradient of f at x = x0. This gradient equals Ax0b. Since x0 = 0, this means we take p1 = b. The other vectors in the basis will be conjugating to the gradient, hence the name conjugate gradient method.
Let rk be the residual at the kth step:
= (11)
Note that rk is the negative gradient of f at x = xk, so the gradient descent method would be to move in the direction rk. Here, we insist that the directions pk be conjugate to each other. We also require the next search direction is built out of the current residue and all previous search directions, which is reasonable enough in practice.
This gives the following expression:
Advantages
-
The project is to test the convergence speed of the algorithms when the Newton procedure is replaced by the proposed MM step strategy.
-
This strategy is efficient as far as N has a small number of columns. Moreover, the cost of the latter product does not depend on the subspace dimension, y contrast with the direct computation.
-
The proposed step size search is proved to ensure the convergence of the whole algorithm, under low computational cost.
-
-
SIMULATION &RESULTS: Table 1-Shows various parameters and its values
Iterations
10000
Lambda
20
Delta
20
Shai
1
Shai1
2
Xmin
0
Xmax
255
Tau
1e-5
Eta
0.2
Tnit
Zeros(xdim*ydim,1);
The experiment is conducted for various images, it compares the time and number of iterations of different methods to solve degradation problem to an accurate solution with two optimization algorithm and it converges to good results. Good results are defined when final signal to noise ratio is better than initial signal to noise ratio.
The most important result in this case is that MM stepsize method converged faster than SESOP.
+1 =
(12)
In this case input image is Peppers, the same
Following this direction, the next optimal location is given by
+1 = + +1 +1 (13)
With
+ +
1 1( + )
+1
= =
+1
+1
+1 +1
+
1
= ) (14)
+1
+1
Where the last equality holds because pk+1 and xk are conjugate. a sparse vector. The restored image is then defined as where minimizes the PLS criterion is given below
=1
F(z) = 2+ ( ) (15)
image is blurred by adding noise and restoring the same image and also showing number of iterations performed and calculating CPU consumed time by using sequential subspace optimization algorithm and majorize minimize strategy.
Enter the input figure name: peppers IMAGE_input =peppers Selecting Input Image in data format peppers Create Blurred Image from Input Image Apply Restoration Strategy Shai(u) = (1-exp(-u^2/(2*delta^2)))
Lambda = 20, delta = 20, eta = 0.2 and tau = 1e-005 Xmin = 0 and Xmax = 255
———————————————
—–Number of Iterations Performed
= 782 Total CPU Consumed Time
=130.881
———————————————
—–Shai(u) = (u^2)/(2*delta^2 + u^2)
lambda = 20, delta = 20, eta = 0.2 and tau =
1e-005 Xmin = 0 and Xmax = 255
———————————————
—–Number of Iterations Performed
= 1536 Total CPU Consumed Time
=224.1736
———————————————
—–Initial SNR = 22.0429
Final SNR using SESOP = 24.9643
Final SNR1 using SESOP-MM = 24.9662
Figure 3- Original image.
The original image of word is shown in Figure 3.
Figure 4- Image after blurring.
The original image of word is blurred due to adding noise and its signal to noise ratio is shown in Figure 4.
Figure 5- Image after restoration using SESOP.
The blurred image is restored by using sequential subspace optimization method and its signal to noise ratio is shown in figure 5.
Figure 6- Image after restoration using SESOP-MM.
The blurred image is restored by using sequential subspace optimization majorize-minimize method and its signal to noise ratio is shown in figure 6.
Figure 7- Val-criteria showing iteration numbers and run time by SESOP
In this figure 7 Val-criteria showing number of iterations and run time by sequential subspace optimization method.
Figure 8- Val-criteria showing iteration numbers and run time by
SESOP.
In this figure 8 Val- criteria showing number of iterations and run time by using sequential subspace
optimization majorize-minimize method.
Figure 9- Grad-norm showing iteration numbers and run time by
SESOP.
In this figure 9 Grad-norm showing number of iterations and run time by using sequential subspace optimization method.
Figure 10- Grad-norm showing iteration numbers and run time by SESOP-MM.
In this figure 10 Grad-norm showing number of iterations and run time by using sequential subspace optimization majorize-minimize method.
Applications
The multi-dimensional step size strategy is useful in video applications; the motion-blur estimation can be performed in order to improve the video resolution of the real time video image processing application.
The proposed technique can be very much useful for enhancing the images captured by low cost and low configuration digital cameras.
The proposed method is also useful in medical imaging such as computer tomography (CT) and magnetic resonance imaging (MRI) since the acquisition of multiple images is possible while the resolution quality is limited. The surgeon can operate more successfully over the exact fractured part of the body with more care.
-
CONCLUSION
This paper explores the minimization of penalized least squares criteria in the context of image restoration, using the subspace algorithm approach. It is pointed out that the existing strategies for computing the multidimensional stepsize suffer either from a lack of convergence results or from a high computational cost. As an alternative, now proposed an original stepsize strategy based on a MM recurrence. The stepsize results from the minimization of a half- quadratic approximation over the subspace. This project benefits from mathematical convergence results, whatever the number of MM iterations. Moreover, it can be implemented efficiently.
The proposed multidimensional stepsize strategy is significantly faster than the Newton method, in terms of computational time before convergence. The best performances have almost always been obtained by proposed algorithm.
-
REFERENCES
-
M. Elad, P. Milanfar, and R. Rubinstein, Analysis versus synthesis in signal priors, Inverse Prob., vol. 23, no. 3, pp. 947968, 2007.
-
S. Geman and G. Reynolds, Constrained restoration and the recovery of discontinuities, IEEE Trans. Pattern Anal. Mach. Intell., vol. 14, no. 3, pp. 367383, Mar. 1992.
-
D. Geman and C. Yang, Nonlinear image recovery with half- quadratic regularization, IEEE Trans. Image Process., vol. 4, no. 7, pp. 932946, Jul. 1995.
-
A. Chambolle, R. A. De Vore, L. Nam-Yong, and B. Lucier,
Nonlinear wavelet image processing: Variational problems, compression, and noise removal through wavelet shrinkage, IEEE Trans. Image Process., vol. 7, no. 3, pp. 319335, Mar. 1998.
-
M. Figueiredo, J. Bioucas-Dias, and R. Nowak,
Majorization-minimization algorithms for wavelet-based image restoration, IEEE Trans. Image Process., vol. 16, no. 12, pp. 29802991, 2007.
6] M. Zibulevsky and M. Elad, l2-l1 optimization in signal and image processing, IEEE Signal. Process. Mag., vol. 27, no. 3, pp. 7688, May 2010.
-
G. Demoment, Image reconstruction and restoration: Overview of common estimation structure and problems, IEEE Trans. Acoust. Speech, Signal Process., vol. 37, no. 12, pp. 20242036, Dec. 1989.
-
P. Charbonnier, L. Blanc-Feraud, G. Aubert, and M. Barlaud,
Deterministic edge-preserving regularization in computed imaging, IEEE Trans. Image Process., vol. 6, no. 2, pp. 298 311, Feb. 1997.