 Open Access
 Total Downloads : 352
 Authors : Ghada A. Rakabawy, Hamdy M. Kelash, Osama S. Faragallah, Mohammed Badawy
 Paper ID : IJERTV4IS010064
 Volume & Issue : Volume 04, Issue 01 (January 2015)
 Published (First Online): 05012015
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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 precomputations 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

INTRODUCTION
The manual segmentation and analysis for 3D cardiac MR images are difficult because of the increasing resolution and it is extremely timeconsuming. 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 semiautomated 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 precomputation 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.

PREVIOUS WORK
The main methods for cardiac LV segmentation can be generally categorized as: bottomup methods, active contour methods (ACM), deformable templates, active shape models (ASM), active appearance models (AAM), levelset approaches and Random walk segmentation techniques [5].
Levelset 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. Levelset 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 multilabel image segmentation method used for medical applications and based on GraphTheoretic Electrical Potentials [1, 2].

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. Highquality 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 positivedefinite system of linear equations [1, 2].
The Mlabeled 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 graphtheoretic 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 EulerLagrange 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.


Approximate Highspeed Random Walk
Random walk with precomputations 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. Precomputation via an offline procedure is difficult because seeds locations are unknown. Precomputing 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.


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 realvalued 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].


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 precomputation 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 = BZ1
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

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 levelset based curve evolution algorithm [8], Variational Bspline
0= gTLx= gT gT fM (24)
M U xU
gT fM = gT xU (25)
levelset 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 cineMRI 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 1015 second breathholds 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
Levelset based curve evolution
Variational Bspline 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

(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.


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

L. Grady and G. FunkaLea, Multilabel image segmentation for medical applications based on graphtheoretic electrical potentials, Proc. Workshop Computer Vision and Math. Methods in Medical and Biomedical Image Analysis, pp. 230245, May 2004.

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

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

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

Osama S. Faragallah, An enhanced semiautomated method to identify the endocardium and epicardium borders, J. Electron. Imaging, 21(2), April 2012.

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

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.

Y. Shi and W. C. Karl, A realtime algorithm for the approximation of levelset based curve evolution, IEEE Trans. Image Process., volume 17, no.05, pp.645 656, 2008.

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

F. Harary, Graph theory, AddisonWesley, 1994.

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

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

X. Zhu, J. Lafferty, and Z. Ghahramani, Combining active learning and semisupervised 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.

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

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.