Implementation of Level Set Method using Reaction Diffusion with No Re-Initialization

Implementation of Level Set Method using Reaction Diffusion with No Re-Initialization

Department of Electronics & Telecommunication Engineering, Dr. B. A. T. U. Lonere, M.S., India

Abstract: The front propagating problems is an important area of application of Level Set Methods (LSMs) where moving front plays a vital role in evolution of process. In traditional LSMs, the Level Set Function (LSF) defines the evolution of boundary. But it does not apply to the object whose boundary weve to calculate after some time interval

1. the LSF becomes irregular. As a remedy to this, weve to re-define the LSF so that itll give the explicit result. The costly re-initialization is a method to do this. But this causes area loss which is one directional. Many ideas were proposed to avoid re-initialization process like Chopps methods, GDRLSE1, GDRLSE2, and GDRLSE3. But they are not applicable for both the LSMs i.e. PDE based and variational one. We are proposing reaction diffusion (RD) based method which will avoid all the disadvantages of all methods mentioned above, will be stable. There is no need to go for re- initialization of LSF. Well add a diffusion term into Level Set Evolution (LSE) equation. To have a stable numerical solution of RD based LSE, well use two step splitting method (TSSM) which will first iterate the LSE equation and then solve diffusion equation. Solving diffusion equation regularizes the LSF to ensure stability, thus avoiding costly re-initialization completely. The method is applicable for PDE based LSM as well as variational LSM. It gives very good results in terms of high boundary anti-leakage and noise immunity.

   KEYWORDS:Front propagating problems, LSMs, LSF, PDE and variational based LSMs, re-initialization, TSSM.

   I.INTRODUCTION

   Active contour models (ACMs) are being used in image processing for image segmentation. Parametric curves are used to extract objects from image in original ACM. But the drawback of this ACM is that it cannot handle topological changes and it is very much dependent on parameterization. To neglect these problems, the Level Set Method was introduced by Osher and Sethian. This LSM represents the curve by zero level set of high dimensional function.

   LSMs are divided into two categories: partial differential ones and variational ones. PDE based LSMs are used to implement parametric ACMs i.e. Kass et als snake, region competition snakes and geodesic active contours. Chan- Vese ACM, Vese and Chan piecewise smoothing ACM, local binary fitting ACM are the applications of variational

   LSM. These are obtained by minimizing certain energy functional defined on the level set.

   In traditional LSMs, LSF is initialized to be signed distance function (SDF) and for numerical stability upwind schemes are used. But near the zero level set, LSF often becomes very flat or steep and this affects numerical stability. To overcome the problem, the procedure is done periodically to enforce LSF. The procedure is called as re-initialization. It is compulsory that after re-initialization, the front or the boundary should not move. But due to numerical instability it moves from its position. This introduces error while computing and it will go on increasing in each re- initialization. This results in shifting an interface from its actual level. Chopps methods for re-initialization were time consuming as they were redefining LSF to be SDF.

   Many methods were proposed to eliminate the re- initialization procedure like GDRLSE1, GDRLSE2 and GDRLSE 3 methods. But there were problems also. The methods were having limited applications to PDE based LSMs, limited anti-leakage capability for weak boundaries and sensitive to noise.

   In this paper were going to propose reaction diffusion (RD) based LSM which is re-initialization free and gives explicit results. The RD term is added into LSE equation. The RD method is generally used in the field of texture analysis, neural image modelling and phase transition modelling. Combining RD and LSM gives the equation benefits of the both. We can have unique and stable equilibrium solution of RD-LSE equation and give an interface explicitly. A two-step splitting method is used to solve RD equation iteratively. In the first step LSE equation is iterated while in second step diffusion equation is solved. The results are very promising and validating effectiveness of RD-LSE.

   1. LEVEL SET METHOD:

      Osher and Sethian have developed Level Set Methods (LSMs) for front propagating problems. The area of applicat0ion of LSMs is very vast like crystal growth, flame propagation, multi-phase flow, motion of soap bubble and motion of multiple junctions. In these processes it is necessary to find moving fronts location and shape. Front tracking method is also used to do so. It was using

      Langarngian co-ordinate system. But it was not that useful in complex geometry and topological changes.

      Level Set Method uses Eulerian co-ordinate system for representation of interface. Basically, LSM describes (n-1)

      dimensional surface which represents moving front by zero level set of n-dimensional function. The function iscalled as level set function.

      Fig. 1: Computational Domain

      We will try to explain LSM with a simple example shown in fig. 1. The fig shows two phase flow in which there are two immiscible, incompressible fluids in domain . Two subdomains say 1 and 2 of domain are divided by interface . We will assume that describes closed surface in domain . The interface is denoted by zero level of Level Set Function (LSF) denoted by . So, the position of interface is given by ({x : (x)=0} := ). In region 1, the LSF is larger than 0 i.e. ({x : (x)>0} := 1 ) and for region 2 we have ({x : (x)<0} := 2 ). The level set is used for the description of the interface; hence the method is called as Level Set Method.

      The LSM has following advantages:

      1. The geometric characteristics of interface are completely defined by LSF. There is no need of explicit description of interface.

      2. Complex interface structure and topological changes can be captured naturally.

      3. Extension to three space dimensions can be done easily.

      4. Fixed-grid finite difference approximations can be used since there are no moving grid points are involved. Thus like front tracking method, there is no instability problem.

We should consider disadvantages also:

1. High order accuracy is lost as compared to front tracking method.

2. The area of subdomains should be conserved. There is no guarantee of such in advance in numerical computation.

3. If we extend one more space dimension, computational expenses increases.

But, these disadvantages are not that serious as of front tracking method.

1. RE-INITIALIZATION AND ITS NEED:

   While computing following activities may happen:

   1. The LSF weve defined can become too flat or steep near interface, which leads to serious numerical errors.

   2. The level set method breaks down if the interface is close to discontinuity.

   Suppose 0 is initial LSF, due to activities mentioned above LSF becomes irregular in finite time. Therefore, te interface calculated by the LSF will be rough. To avoid these problems, weve to redefine the LSF for clear

   interface. The process of redefining LSF is called as re- initialization. The process should be repeated after small interval of evolution time.

   There are many approaches to make re-initialization happen like Harmonic Approach, Eikonal Equation Approach and Distance Function Approach. But these methods are also not good enough due to reasons below:

   1. Some approaches were based on directly computing SDF which was very time consuming.

   2. In some cases, LSF is far away from SDF which leads to shift the interface by some degree causing area loss.

   3. All methods have a risk of preventing new contours from emerging, which may give undesirable results in image segmentation.

   There are some methods by which we can avoid costly re- initialization process and have higher accuracy and easier implementation. Some global minimizing methods combines total variational model with Chan-Vese model or Vese-Chans piecewise smoothing model. These methods are limited to some variational LSF. There are other methods like Generalized Distance Regulated Level Set Evolution (GDRLSE) methods i.e. GDRLSE1, GDRLSE2 and GDRLSE3 depending on diffusion rates. These methods face problems like limited applications to PDE based LSMs, limited anti-leakage capability for weak boundaries and sensitive to noise.

2. REACTION-DIFFUSION BASED LSF:

   In this method, we add diffusion term in conventional LSE equation to make it RD based LSF. By adding this diffusion term, we can make LSE stable without re- initialization. The two step splitting method (TSSM) is employed in order to solve RD-LSE equation. In first step LSE equation is iterated while in second step diffusion equation is solved. Solving diffusion equation gives piecewise constant solution of LSE equation.

   Consider a closed moving front C(t)=x Rn and it is represented by zero level set of LSF (x,t) i.e.

   C(t)={x|(C(t),t)=0}. As (C(t),t)=0, taking derivation on both sides gives following eq.:

   t+ Ct = t+ FN = 0 (x,t=0)= 0(x) (1)

   Since, inward normal direction is given by N=/||, eq.

   (1) can be rewritten as

   t=F| | (x,t=0)= 0(x)

   (2)

   In traditional LSMs F is written as F=+F1, where =div(/||) is curvature, is fixed parameter and F1 is constant.

   Eq. (2) is LSE equation of PDE based LSMs and derived from geometric consideration of motion equation. For variational based LSMs, LSE equation is given by:

   t =-E()=F()

   (x,t=0)= 0(x) (3)

   Where E() is Gateaux derivative of energy functional, ()is Dirac functional and F is as mentioned.

   By add diffusion term into eq. (2) or (3), we can get following RD equation of LSM:

   t=-(L()/), x Rn

   subject to (x,t=0, )= 0(x) (4)

   where is positive constant L()=- F| | for PDE based LSM and L()=- F () for variational based LSM. There are two dynamic processes in eq. (4): the diffusion term regularizes LSF to be a piecewise constant in each segment domain i, and final solution of eq. (4) is forced to L()=0 by the reaction term -1L(). Based on Van Der Waals-Cahn-Hilliard theory of phase transition [12], the equilibrium solution of eq. (4) is analysed when 0+ for variational LSM and then generalized the analysis into unified framework for both PDE and variational based LSM.

3. RESULTS:

   Fig. 2: Segmentation results on a synthetic image.

   From left to right: results by re-initialization method, RD, GDRLSE1, GDRLSE2 and GDRLSE3. The red curves represent the initial contours, and the blue solid curves represent the final contours.

4. CONCLUSION:

   The Reaction-Diffusion (RD) method weve proposed is applicable to both PDE and variational based LSMs. It has much better performance in terms of boundary anti- leakage. Implementation is simple and it does not require upwind scheme at all. The noise immunity of this method is very good. It gives promising results in synthetic and real images. The main advantage is weve avoided costly re- initialization process and its drawbacks.

5. REFERENCES:

1. M. Kass, A. Witkin, and D.Terzopoulos, Snakes: Active contour models, Int. J. Comput. Vis., vol.1, pp. 321331, 1987.

2. S. Osher and J. Sethian, Fronts propagating with curvature dependent speed: Algorithms based on Hamilton-Jacobi formulations, J. Comp. Phys., vol. 79, pp. 12-49, 1988.

3. R. Malladi, J. Sethian, and B. Vemuri, Shape Modelling with Front Propagation: A Level Set Approach, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 27, no. 5, pp. 793800, 1995.

4. V. Caselles, R. Kimmel, and G. Sapiro, Geodesic Active Contours, Int. J. Comput. Vis., vol. 22, no. 1 pp.6179,1997.

5. H. Zhao, T. Chan, B. Merriman, and S. Osher, A Variational Level Set Approach to Multiphase Motion, J. Comp. Phys., vol. 127, pp. 179-195, 1996.

6. D. Peng, B. Merriman, S. Osher, H. Zhao, and M. Kang, A PDE- Based Fast Local Level Set Method, J. Comp. Phys., vol. 155, pp. 410-438, 1999.

7. C. Li, C. Xu, C. Gui, and M. D. Fox, Level set evolution without re- initialization: A new variational formulation,Proc. IEEE Conf. Computer Vision and Pattern Recognition, vol. 1, pp. 430436, 2005.

8. S. Osher and R. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces, Springer-Verlag, New York, 2002.

9. M. Sussman, P. Smereka, S. Osher, A Level Set Approach for Computing Solutions toIncompressible Two-Phase Flow, J. Comp. Phys., vol. 114, pp. 146-159, 1994.

10. D. Adalsteinsson and J. Sethian, A fast level set method for propagating interfaces, J. Comput. Phys., vol. 118, no. 2, pp. 269- 277, 1995.

11. R. Tsai, and S. Osher, Level Set Methods and Their Applications in Image Science, COMM.MATH.SCI., vol.1, no. 4, pp. 623656, 2003.

12. S. Baldo, Minimal Interface Criterion for Phase Transitions in Mixtures of Cahn-Hilliard Fluids, Annals Inst. Henri Poincare., vol. 7, pp. 67-90, 1990.

13. G. Barles, L. Bronsard, and P. Souganidis, Front Propagation for Reaction-Diffusion Equations of Bistable Type, Annals Inst. Henri Poincare., vol. 9, pp. 479-496, 1992.

14. D. Chopp, Computing Minimal Surface via Leve l Set Curvature Flow, J.Comput.Phys., vol. 106, pp. 77-91,1993.

15. C. Li, C. Xu, C. Gui, and M. D. Fox, Distance Regularized Level Set Evolution and Its Application to Image Segmentation, IEEE Trans. Image Processing , vol. 19, no. 12, pp. 154-164, Dec. 2010.