This project enables image enhancement by using the solution of non linear heat equation (diffusion) running forward and backward with time.
Abstract
This project enables image enhancement by using the solution of non linear heat equation (diffusion) running forward and backward with time.
Introduction
We think of an image, characterized by a different gray level at each point, as an initial condition in a heat problem defined on the image region. Running the heat equation with time causes transfer of heat from warmer areas to colder areas and vice versa, namely the changes will take place in regions in which there is a gradient in temperature, similarly running the heat equation defined on image with time, causes changes at areas characterized by a gradient in the gray level (gradient between two gray levels defined by their absolute difference value).
There is a major significance whether the diffusion equation runs forward or backward with time. The forward diffusion process causes smoothing of the image similarly to a heat transfer from warmer to colder areas. Backward diffusion process does exactly the opposite.
These two processes (forward and backward) can be exploited to image enhancement: We can enhance blurred image by trying to compensate the blurring using the opposite process, the backward diffusion process.
Linear and Non-Linear Diffusion
The two dimensional linear diffusion equation:
Where c is a constant (0<|c|<1) called the diffusion coefficient. The initial condition is the original image stated as (I(x,y,t=0)=I(x,y)). If c>0 the solution describes the behavior of the image for times greater than the time specified as initial condition (t>0) (forward process).
c0 (backward process).
For positive and constant c the solution is equivalent to convolution of the original image with a Gaussian kernel (similar to LPF). As long as we advance in time (or do more iterations) we will get convolution with a broader Gaussian .
According to the ideas presented so far, can we enhance an image, blurred by a LPF, using the linear backward diffusion process?
The answer is basically yes, but this method has a major disadvantage:
The backward diffusion process is extremely unstable and without an appropriate restraint mechanism it will result in significant addition of noise to the image. To overcome this obstacle a new approach is suggested: non-linear diffusion mechanism.
Non linear diffusion equation:
As we can see we allow c to be dependent in the coordinates and time.
This idea enables us to choose the diffusion coefficient more wisely:
For instance, we can choose c to be a function of the image gradient at each point, were c takes large values for areas characterized by small values of gradients and small values for areas characterized by large values of gradients. This will assure that the diffusion process will be more dominant at areas characterized by small gradients and less dominant at areas characterized by large gradients.
This results in keeping the image edges (that are associated with large gradient values)
The non-linear diffusion equation where c is a function of the gradient image as suggested by PERONA and MALIK:
In This project we choose c to be dependent on image gradients at each point, that enables us to use the diffusion process for image enhancement and to overcome the disadvantage of the linear backward diffusion process, assuring that the backward process will be carefully controlled.
The suggested diffusion coefficient:
Where Kf,Kb,W (Kf>Kb-W) are constants to be determined.
n,m were chosen to be 4,1 respectively.
Kf is the limit gradients to be smoothed mainly for noise reduction.
Kb,W are parameters that specify a range of gradients to be emphasized (backward diffusion process – negative diffusion coefficient).
Alpha is bounded by Kf/2Kb.This parameter controls the power of the backward diffusion process to avoid noise addition.
Finally we have to determine the number of iterations for the process end (N).
A plot of the diffusion coefficient is given below:
The aim of this project is to determine automatically these parameters to a certain image.
Parameter Selection and Project Structure
We come into conclusion that we have to use the non-linear diffusion coefficient and to determine the specified parameters for a certain image.
The main idea is to choose the diffusion coefficient as specified before with the following changes:
According to the original idea we can emphasize only one range of gradients (specified by Kb,W). Here we choose a different diffusion coefficient that enable us to emphasize more than one range of gradients as schematically shown in the figure below:
The parameters selection:
Kf – chosen to be 1, since this value is large enough for noise reduction and small enough for “over smoothing” that can damage our attempt to reconstruct the image.
Kb – the minimum and maximum values of the gradient image were calculated and the interval defined by the difference of these values was divided into segments of length “step”.
Kb was chosen to be equal to step*n where n is the number of the segment, all these with the necessary changes to make sure that the segments defined by Kb,W will not overlap with the segment defined by Kf.
W – the selection of this parameter done to assure that the segments defined by a different Kb,W will overlap. We choosed this parameter to be equal to “step” (see the figure above).
Alpha – this parameter choosed to be Kf/Kb which is greater than the bounded value. Alpha controls the backward diffusion process. We usually prefer alpha to be a small constant so the changes in the image between one iteration to another will be as controlled as possible .We can see that as long as Kb increased, alpha decreased meaning that for large gradients (large Kb) alpha decreases and might be too small for image enhancement. This can be solved by significant increase in the number of iterations. Therefore the number of iteration choosed to be equal to 1/alpha. Since the backward diffusion process might be unstable another restraint mechanism is suggested:
This mechanism assures that a certain pixel in the original image will not change its value by more than a certain constant determined empirically.
Addition – Optional:
The algorithm that implements the ideas presented so far gives reasonable results. In this project we suggest another idea when combined with the former, the results may be improved .The idea is to divide an image into small images that contain the information from the original image with the addition of blurring caused naturally by the division. Applying the diffusion process on the small images and unify them back to perform the original sized image improves the results of the algorithm. This statement has been proved mainly empirically.
Example:
Conclusion
After examining these ideas we can state the following conclusion:
This algorithm enables us to reconstruct images reasonably, mostly those that do not contain texture.
Acknowledgements
We would like to thank our supervisor Guy Gilboa and the VISL laboratory for their support and guidance and to the Ollendorff Minerva Center Fund which supported this project.