Improved Random Walk Technique for LV Cavity Segmentation

Improved Random Walk Technique for LV Cavity Segmentation

Ghada A. Rakabawy, Hamdy M. Kelash, Osama S. Faragallah, Mohammed Badawy

Computer Science and Engineering, Faculty of Electronic Engineering, Menoufia University,

Menouf, Egypt

AbstractIn fact, the challenge of medical image segmentation is that how to group regions with coherent characteristics with high quality and high speed processing. In todays world, cardiovascular diseases is the major cause of death in the world. Heart failures have become of important concern to the researchers. Accurate and fast left ventricle cavity segmentation algorithms are of great importance prior to the clinical analysis of the heart condition. Random walker techniques have provable good quality segmentation of robustness to noise. In this paper, we propose a novel approach for image segmentation by mixing the advantages of the high speed Random walk technique and the extended random walk technique. In our new method, it is important to be able to integrate intensity information into the spatial algorithm. This will improve the accuracy of segmentation. The novel improved method will also calculate the pre-computations of eigenvalue – eigenvector pairs of the graph in the offline mode, to get the high speed solution of the segmentation process. Weighting function plays an important role in the segmentation process. The DroG weighting function is used in the novel method in order to get better segmentation results with blurry Cardiac Magnetic Resonance images and weak boundaries. For measuring the running time speed, we calculate the average execution time which shows the high speed segmentation of the new improved segmentation method. The quality of segmentation process is determined by using similarity measurements such as PSNR and Dice coefficient. The new improved Random walk method gives high quality left ventricle cavity segmentation. The experimental results show the best similarity measurements of the novel random walk segmentation technique that could reach 99%.

KeywordsImage segmentation; Random walks; LV cavity extraction; RW; medical images; segmentation technique

1. INTRODUCTION

   The manual segmentation and analysis for 3D cardiac MR images are difficult because of the increasing resolution and it is extremely time-consuming. Image segmentation plays an important role in computer vision, and there are many algorithms that have been presented. The Left Ventricle (LV) is considered the main cavity of the heart. The assessment of the LV function leads to good determination and measurement of the cardiovascular functions. The LV function analysis requires an accurate description of ventricular shape. In order to aid the cardiologist in the segmentation process for the extraction of LV cavity, accurate and fast semi-automated segmentation methods are needed. The goal of the segmentation algorithm is to decrease the time and improve the reliability of the process.

   Recently, Random walk methods have been more and more popular because of their accurate segmentation. Random walk is firstly proposed by Leo Grady in [1, 2]. Now Random walk has widely been applied in the image processing.

   In this paper, we propose a novel approach for image segmentation. The proposed method depends on suitable weighting function, the offline pre-computation model in the high speed random walk technique (HRW) [3] and intensity features model from the extended random walk technique (ERW) [4].

   The rest of this paper is organized as follows: Section II describes the previous work on left ventricle cavity segmentation techniques, section III describes the proposed method and its mathematical model, section IV discusses the experimental results, and finally the conclusion is discussed in section V.

2. PREVIOUS WORK

   The main methods for cardiac LV segmentation can be generally categorized as: bottom-up methods, active contour methods (ACM), deformable templates, active shape models (ASM), active appearance models (AAM), level-set approaches and Random walk segmentation techniques [5].

   Level-set segmentation methods are recent and well- established methods to segment objects in noisy data [6- 8]. It may have some problems such as determining the stopping term, the strong initialization of segmenting objects and it can have high computational costs. Some algorithms use prior models to solve these problems. Level-set models have shown good segmentation results in medical image analysis, but, prior knowledge that is defined in the optimization function, such as the definition of the LV border and the prior shape can be either designed by hand or learned using a training set. Unfortunately, when the segmentation model is highly dependent on prior models, segmenting details and cardiac abnormalities might be lost.

   Random walk is a multi-label image segmentation method used for medical applications and based on Graph-Theoretic Electrical Potentials [1, 2].

   1. Basic Random Walk (BRW) technique

      In this technique, user defined marked labels are used which are also called seeds. We determine the probability that a random walker starting at each unlabeled pixel will first reach one of the marked pixels. High-quality image segmentation may be obtained by calculating the greatest

      probability for each pixel to the label. This algorithm is formulated in discrete space (i.e., on a graph) using combinatorial analogues of standard operators and principles from continuous potential theory. The random walker algorithm requires the solution of a sparse, symmetric positive-definite system of linear equations [1, 2].

      The M-labeled marked nodes are established to have a unit potential and all seed points belonging to labels other than M are grounded. The electric potentials established at each unmarked node provide the probabilities that a random walker starting from that node will first reach the seed with label M. Although such a method of computation would be completely impractical but established connections between random walks and graph-theoretic electrical potentials provide us with a simple, convenient method for analytically computing the desired probabilities [9]. The function that solves the Dirichlet problem for a given set of boundary conditions is known as harmonic function. The harmonic function that satisfies the boundary conditions minimizes the Dirichlet integral since the Laplace equation is the Euler-Lagrange equation for the Dirichlet integral.

      A graph consists of a pair G= V, E with vertices (nodes) V and edges e E, EV×V. An edge e, spanning two vertices, i and j, is denoted by eij. A weighted graph assigns a value to each edge called a weight. The weight of an

      • µ is the field and is the region of Dirichlet integral D[µ]

      • Lij is indexed by vertices and [1, 2].

      • Partition the vertices into two sets, (marked nodes) and (unmarked nodes) such that = and

      = .

      X =

      and correspond to the potentials of the marked and unmarked nodes, respectively.

   2. Approximate High-speed Random Walk

      Random walk with pre-computations is a fast approximate random walk method. In high speed random walk method (HRW), the purpose is to shift the computational burden to an offline procedure that may be performed before any user interaction has taken place. Pre-computation via an offline procedure is difficult because seeds locations are unknown. Pre-computing a small number of eigenvectors of the graph Laplacian matrix can give a good and fast approxmation of the segmentation solution, regardless of where the seeds are placed. Gaussian weighting function is used in this method [3, 12].

      • The eigenvalue decomposition of L is: L=QQT

      • We define by: LX=f

        Decomposition of corresponding to marked / unmarked

        edge eij , is denoted by w ( eij) or wij. The degree of a vertex is di= w eij for all edges eij incident on i. In order to

        nodes: =

        f

        M

        fU

        interpret wij as the bias affecting a random walkers choice,

        we require that wij> 0 [10].

      • Let is eigenvector of L with corresponding eigenvalue

        zero and it is a constant vector since Ls column sum to 0. Decompose the in corresponding to marked and

        unmarked nodes:

        =

        Fig. 1. The Basic Random Walk Algorithm steps

        Where:

        • indicates the image intensity at node and Ij indicates the image intensity at node j . The value of represents the free parameter in the Gaussian weighting function [2, 11].

          Fig. 2. High speed random walk algorithm steps

          Where:

      • is a diagonal matrix of the laplacian K smallest eigenvalues of L.

      • Q is a matrix whose columns are the K corresponding eigenvectors.

   3. Extended Random Walk (ERW) technique

   In some segmentation cases, the objects of interest may be reasonably characterized by an intensity distribution. It is important to be able to integrate intensity information into a spatial algorithm [1, 4]. Gaussian weighting function is used in this method. ERW method is an extended method from the basic random walk BRW approach by employing image priors.

   We define by:

   LX=f (1)

   Laplacian matrix L depends on weights of the graph [1]. CMR images are obscure and the difficulty in segmentation is multiplied with the addition of noises. Most of the algorithms find it hard to perform well in these conditions. Derivative of Gaussian (DroG) weighting function has been proved to be a better choice over Gaussian weighting function in these situations [14].

   DroG weighting function,

   DroG

   x = x

   2 23

   x2

   e 22 (2)

   Where is the usual standard deviation

   The characteristic function due to DroG weighting Function,

   t x2

   (x t)2 t x2

   x

   E =

   e 22 e

   22 dx + x

   e 22 dx (3)

   DroG

   2 23

   0

   s

   2 23

   0

   Where:

   Fig. 3. Extended random walk algorithm steps

   Random Walk approach can be good in segmenting the blood pool (LV cavity) if DroG function is used as its weighting function to calculate the graph laplacian matrix.

   In extended random walk method of [4], we can divide the Laplacian matrix:

   LM B 0

   L= BT LU+ IU (4)

   0 IU

   Where is introduced as a vector of the prior probabilities for each node, weighted by a scalar,

   We can divide X and f into three components

   • A set of real-valued priors, i that represents the probability density based on the intensity at node i

     corresponding to marked, unmarked, and auxiliary nodes as follow:

   • is introduced as a vector of the prior probabilities for each node, weighted by a scalar, [4].

3. THE PROPOSED METHOD

   xM fM

   X= xU , = 0

   xR fR

   The proposed method is improved Random Walk technique for image segmentation. This novel method depends on the offline pre-computation model in the high speed random walk technique (HRW) [3] and mixes it with the intensity prior model from the extended random walk technique (ERW) [4] to get fast and accurate segmentation

   Substitute from (4) into (1),

   LM B 0 xM fM

   BT LU+ IU xU = 0 ,

   0 IU xR fR

   LM B xM fM

   (5)

   results. The importance of weighting function is to maximize the entropy. The performance of standard Gaussian weighting

   BT LU

   xU

   = xU

   , (6)

   function [13] is perfect on clean images where the objects are homogeneous and well separated. This is already used in [1- 4]. The objects in the Cardiac MR (CMR) images are neither homogeneous nor well distinct [14]. Therefore, in this new method, we will use the derivative of Gaussian (DroG) weighting function to produce good segmentation results on blurry edged CMR images in the novel Random Walk approach.

   From [3], E is the pseudo inverse of L:

   E =Q 1QT (7)

   Decompose the E, in corresponding to marked and unmarked nodes:

   E= EM R (8)

   M

   U

   RT EU

   A. Mathematical Model

   When L is the laplacian matrix of the graph and X is the probability for each pixel being a member of the labels.

   RT= Q

   1QT (9)

   Let g is eigenvector of L with corresponding eigenvalue zero and it is a constant vector since Ls column sum to 0.

   Decompose the g in corresponding to marked and unmarked

   Z Q IK+ 1 QT (29)

   1

   Z 1 Q IK+ 1 QT (30)

   U

   nodes:

   g = gM (10)

   ZU 1 Q

   U

   1

   IK

   + 1 1QT (31)

   gU Since IK+

   is a diagonal matrix with all positive entries,

   EL= I ggT (11)

   Multiplying E by both sides of (6),

   it is easily invertible Online. Substitute in (17), we finally get,

   U

   E LM B xM = E fM

   (12)

   xU = ZU 1 (g

   + RTfM+ EU) (32)

   BT LU xU

   From (8) and (11),

   xU

   I ggT xM

   = EM R fM (13)

   xU

   From (12) and (13),

   RT EU xU

   LMxM+ BxU = fM (14)

   g gT xM+ xU g gT xU= RTfM+ EU xU (15)

   U M U U

   let = gT xU , neglect ( g gT xM), (15) will be,

   U U M

   U

   xU g = RTfM+ EU( xU) (16) Then we get:

   U

   IU+ EU xU g = RTfM+ EU (17)

   U

   To get xU , let = I+ E (18) ZUxU g = RTfM+ EU (19)

   From [3],

   U

   Let C = BZ-1

   LMxM+ BxU= fM (20)

   Multiplying C by (18), then subtract it from (20),

   T

   LMxM+ CgU= IM CR fM CEU (21) Let fM= f M + f M and D= IM CRT

   Df M = LMxM+ CEU (22)

   Fig. 4. The proposed method steps

4. RESULTS

   In this paper we have proposed a novel improved random walk method (IRW) for LV segmentation. A number of

   Df M = CgU To find the value of ,

   (23)

   measurements are done on different images to demonstrate the effect of the improvement of the novel segmentation method. The proposed method has been also compared to the level-set based curve evolution algorithm [8], Variational B-spline

   0= gTLx= gT gT fM (24)

   M U xU

   gT fM = gT xU (25)

   level-set algorithm [6], basic random walk with seeds [1], approximate high speed random walk [3] and extended random walk algorithm [4] in regard to the similarity of segmentation and running time.

   M U

   gT f = gT f + gT (26)

   Here following is a representative sample of the results

   M M M M U

   gT fM+ gT = M U

   M

   gT f M

   (27)

   obtained using Short Axis (SAX) Cardiac MRI dataset provided by Sunnybrook Health Sciences Centre, Toronto, Canada [15]. The database contains 45 cardiac cine-MRI datasets from a range of patients and pathology. Cine steady state free precession (SSFP) short axis CMR images were

   From (7), and (18),

   = I+ E QQT+ Q 1QT (28)

   obtained with a 1.5T GE Signa MRI. All the images were obtained during 10-15 second breath-holds of 20 cardiac phases over the heart cycle, and scanned from the ED phase. (Thickness=8mm, gap=8mm, FOV=320mm×320mm, matrix=

   256×256). In these SAX CMR Acquisitions, contours were manually drawn by an experienced cardiologist in all slices at ED and ES phases. All images were stored in the standard digital imaging and communications in medicine (DCOM) format.

   The segmentation accuracy is estimated via similarity measurements. Similarity is computed between the result image of the algorithm and the manual segmented image as a reference. Where A, B are the reference mask region and the result mask region of an algorithm:

   PSNR=10 log10

   d (33)

   MSE(A, B)

   Fig. 6. Column chart of PSNR average measurements

   Where d is the maximum possible value of the image and MSE (A, B) is the mean square error computed between A and B.

   Fig. 8 indicates LV cavity segmentation results using the Improved Random Walk technique on different CMRI sample images. In Fig. 9 the LV cavity is shaded in red while the rest of the image is shaded in green. These shaded images are

   1 M N resulted from the same images of Fig. 8. It is obvious from the

   MSE A, B =

   A m, n B(m, n) 2

   MN

   m=1 n=1

   (34)

   resulted images and from table 1, that this new technique can result in accurate LV cavity segmentation in a short time.

   2(A B) DICE = A+B

   (35)

   The average of Execution time per slice is calculated in seconds to measure the running time speed are as shown in Fig. 7. The experimental results show that the proposed method has higher speed in segmentation process than level- set techniques, basic random walk and extended random walk techniques. High speed random walk is faster than the novel method but it has less accurate results.

   Fig. 5. Column chart of Dice similarities.

   Fig. 5 is a column chart showing the results of comparison between different previous segmentation techniques and the novel improved random walk technique (IRW) using DICE similarities. It shows that novel random walk method has Dice coefficient of 0.98704.

   Fig. 6 is a column chart showing the high average PSNR of the improved random walk technique.

   Fig. 7. Average execution time

   The results are implemented in MATLAB on Microsoft windows 64 bit, processor 2.27 GHz Intel ® core i3 CPU and 3 GB memory. Where K = 80 and = 0.001.

   TABLE I. TABLE OF SEGMENTATION RESULTS

   Measurement of segmentation	Level-set based curve evolution	Variational B-spline level- set	Basic Random walk	High Speed Random Walk	Extended Random Walk	Proposed method
   Dice Coefficient	0.39325	0.86562	0.94672	0.94481	0.97270	0.98704
   PSNR	6.41325	22.67325	25.82928	25.49958	27.96782	29.44165
   Execution time	5.04325	0.47365	0.84849	0.09057	0.85895	0.13971

   1. (b) (c)

   (d) (e) (f)

   (g) (h) (i)

   (j) (k) (l)

   Fig. 8. Segmented images resulted from the new improved random walk technique. Left Ventricle cavity boundary is coloured.

   (a) (b) (c)

   (d) (e) (f)

   (g) (h) (i)

   (j) (k) (l)

   Fig. 9. Shaded segmented Cardiac MRI images using the improved random walk segmentation technique. The Left ventricle is segmented in each slice accurately and it is shaded in red colour.

5. CONCLUSION

We have presented a novel technique for cardiac image segmentation based on a small set of marked pixels. The proposed novel method of image segmentation improves the original random walk methods. The whole segmentation online time consuming becomes much less and the segmentation results show much better quality. DICE similarity of the proposed method may reach up to 99%. We have demonstrated this approach on short Axis Cardiac MRI dataset and shown that it provides a unique, high quality solution that is robust to weak object boundaries. Finally, the algorithm considers the intensity absolute values and performs efficiently with blur images and weak edges.

REFERENCES

1. L. Grady and G. Funka-Lea, Multi-label image segmentation for medical applications based on graph-theoretic electrical potentials, Proc. Workshop Computer Vision and Math. Methods in Medical and Biomedical Image Analysis, pp. 230-245, May 2004.

2. L. Grady, Random walks for image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, no. 11, pp. 17681783, November 2006.

3. L. Grady and AK Sinop, Fast approximate random walker segmentation using eigenvector precomputation, In IEEE Conf. CVPR, pages 18, 2008.

4. L. Grady, Multilabel random walker image segmentation using prior models, IEEE Conf. CVPR, 1:763770, June 2005.

5. Osama S. Faragallah, An enhanced semi-automated method to identify the endo-cardium and epi-cardium borders, J. Electron. Imaging, 21(2), April 2012.

6. O. Bernard, D. Friboulet, P. Thevenaz, and M. Unser, Variational B- spline level-set: A linear filtering approach for fast deformable model evolution, IEEE Trans. Image Process., vol. 18, no. 6, pp. 11791191, Jun. 2009.

7. Ben Ayed, S. Li, and I. Ross, Embedding overlap priors in variational left ventricle tracking, IEEE Trans.Med. Imag., vol. 28, no. 12, pp. 19021913, Dec. 2009.

8. Y. Shi and W. C. Karl, A real-time algorithm for the approximation of level-set based curve evolution, IEEE Trans. Image Process., volume 17, no.05, pp.645 -656, 2008.

9. P. Doyle and L. Snell, Random walks and electric networks, no. 22, Washington, D.C.: Math. Assoc. of Am., 1984.

10. F. Harary, Graph theory, Addison-Wesley, 1994.

11. S. P. Dakua, J. S. Sahambi, Effect of in random walk approach for LV contour extraction, World Congress on Nature & Biologically Inspired Computing, 2009.

12. Y. Boykov and M. P. Jolly, Interactive graph cuts for optimal boundary and region segmentation of objects in n-D images, Proc. ICCV, pages 105112, 2001.

13. X. Zhu, J. Lafferty, and Z. Ghahramani, Combining active learning and semi-supervised learning using gaussian fields and harmonic functions, in ICML 2003 workshop on The Continuum from Labeled to Unlabeled Data in Machine Learning and Data Mining, pp. 5865, 2003.

14. S. P. Dakua and J. S. Sahambi, Weighting function in random walk based left ventricle segmentation, IEEE international conference of image processing, 2011.

15. Radau P, Lu Y, Connelly K, Paul G, Dick AJ, Wright GA, Evaluation framework for algorithms segmenting short axis cardiac MRI, The MIDAS Journal – Cardiac MR Left Ventricle Segmentation Challenge.