Tracking the LV in Velocity MR Images Using Fuzzy Clustering
Tracking the LV in Velocity MR Images Using FuzzyClustering
Ahmed Ismail Shihab
and Peter BurgerImperial College of Science, Technology and MedicineDepartment of Computing180 Queens Gate, London SW7 2BZ
Abstract.
Tracking the LV in cine MR cardiac images is a challenging computing application that is also relevant tothe needs of clinicians. Using fuzzy clustering as the method of segmentation, this paper reports on whethervelocity data can improve the accuracy of the results obtained through only tissue data.
1 PURPOSE
Our application consists of analysing MR image cine sequences acquired at the midventricular plane of the heart. We describe our use of the fuzzy
c
means clustering algorithm to track the LV area across a‘heartbeat’. The images we use are conventional MR tissue density images as well as velocity imagesproduced using a phasesensitive MRI technique.The cine sequences of images are aligned with the shortaxis of the left ventricle (LV). The velocity data isrendered as 3 images,
v
x
,
v
y
and
v
z
, correspondingto the cartesian componentsof the velocity vector ﬁeld
V
at each pixel. The reference coordinate system has the
x

y
plane lying on the plane of imaging (alignedwith the shortaxis of the left ventricle) and the
z
axis perpendicular to it (aligned with the LV longaxis).
Figure 1.
Examples of tissue density images: frames 0, 2, 6, 10 and 14 in an image sequence.The image sequences contain 16 frames. The sequences start at systole and end at early diastole. The timespace between each frame and the next is approximately 40 ms. Figure 1 displays example frames from asequence. Figure 2 displays only the ﬁrst frame of each of the three velocity components.
Figure 2.
Examples of velocity images, frame 0 of
v
x
,
v
y
, and
v
z
.Clustering algorithms have been used for image analysis, particularly segmentation, probably since theearly seventies. The motivation for this use is that image intensity values tend to cluster in ways that
email address: ais@doc.ic.ac.uk
correspond to the physical description of the image. So, for example, in a picture of a darkcolouredaeroplane up in the sky, the sky’s colour would cluster around “bright blue”, while the aeroplane’s colourwould cluster around “dark grey”.There are many types of clustering algorithms. In this paper, we use an objectivefunctiontypealgorithmcalled fuzzy
c
means (FCM) that outputs fuzzy descriptions of each of the clusters. See [2] for a generalreview of FCM’s use in MR image segmentation. FCM has also been used for segmentation of NuclearMedicine cardiac images [3]. A variant of FCM, called the fuzzy
c
shells (FCS) algorithm, has been usedto segment the myocardial wall in MR images [4].
2 METHOD
Fuzzy
c
Means (FCM) is an objectivefunctionbased method of clustering. It is also sometimes called
fuzzy ISODATA
. The monograph by James Bezdek [1] is the most widely cited reference for FCM.The input to any clustering algorithm is called the
data set
. There is no agreedon name for the output;this is because it depends on the type of algorithm used. In the abstract sense, the output of the algorithmis a description of the clusters it found. A suitably concise output is a set of
prototype
data points, whereeach of these prototypes represents a cluster of data points. In the simplest case, the prototype locationis the geometric
mean
of the locations of data points in the cluster it represents. This way, the aim of thealgorithm becomes ﬁnding the best placement of these prototypes. Mathematically, this can be formulatedusinganobjectivefunction. Assumingthatwe are lookingfor
c
prototypes,theobjectivefunctionmeasureshow good (or bad) the set of
c
prototypes describes the data set.The clustering suggested by FCM is a fuzzy one, i.e., each data point has a degree of membership witheach of the
c
prototypes. The value of this degree lies between 0 and 1; the closer it is to 0 the less theprototype is representative of the point, while the closer it is to 1 the more the prototype is representativeof the point. The memberships can be arranged in a matrix, called the fuzzy partition matrix, which givesfor each data point, its memberships with each of the prototypes.Now we state the problem mathematically. FCM seeks to minimise the objective function:
J
(
P;
U
)=
c
X
i
=1
N
X
k
=1
u
m ik
d
2
ik
subject to
P
c i
=1
u
ik
=1
8
k
=1
::N
where
N
is the number of points in the data set,
c
is the number of clusters,
U
=
u
ik
]
is a
c
N
fuzzy
c
partition matrix, and
P
=(
p
1
;:::;
p
c
)
is the
c
set of prototypes.
d
is the distance metric given by
k
x
k
?
p
i
k
2
A
where
kk
is any inner product induced norm. The solutioncommonly used is an iterative one based on the gradient descent technique.The algorithm iteratively minimises the value of the objective function by changing the location of theprototypes and their associated memberships according to some derived update equations. As like otheriterative optimisation methods, FCM may provide locallyoptimal solutions of the objective function. Becauseofthepossiblepresenceofoneormorelocallyoptimalsolutions,thesolutionofanFCMrundependson the initialisation of that run.An important requirementfor the applicationof the FCM algorithm and its derivativesis that
c
, the numberof prototypes, must be provided by the user. There are various options we can take when using FCMand its extensions and derivatives. The ﬁrst is the choice of metric with which points are compared tothe prototype. Another choice to make is the prototype description. Normally this is taken to be a point,however clusters may not always be shaped like point clouds (hyperellipticallyshaped), but can rathertake other shape formations. As the cluster we seek (the LV) is more or less hyperelliptical in shape wecan safely use a point prototype. To simplify computationalcalculations, the metric with which to comparepoints to prototypes is chosen to be Euclidean distance.
3 RESULTS
We assessed the impact of velocity data by clustering ﬁrst with
V
θϕ
y zvxv zv yx
Figure 3.
and
deﬁne the directionof the velocity vector at a given point.out it, and then with combinations of it. The input in the ﬁrstinstance was threedimensional:
x
and
y
, for the
x
and
y
coordinates of a pixel; and
d
, for the tissue density at that pixel.In the second experiment we added a fourth dimension,
V
, consisting of the combined magnitude of the
v
x
,
v
y
, and
v
z
velocitycomponents at each pixel, as shown in ﬁgure 3 and described by:
V
=
p
v
x
2
+
v
y
2
+
v
z
2
:
In the third experiment, we removed
V
and replaced it with
and
. These angles describe the directionof the velocity ﬁeld at a given pixel (see ﬁgure 3).The
m
fuzziness factor of the FCM algorithm was chosen to be2.0, and
c
was set to four as this gave the most intuitive segmentation of the images. The output was in the form of cluster prototypes and the membership matrix. For each frame after the ﬁrstone, we initialised FCM with the prototype locations of the previous frame. We then selected the cluster corresponding to the LVblood pool area and tracked its membership across the sequence.To count the pixels in the LV, we considered a pixel part of the LV cluster if its membership with thatcluster was higherthan its membershipswith the otherclusters. This rule is commonlycalled the
max rule
.Then we then ran a simple region growing routine to count the pixels in the LV area.In ﬁgure 4, we compare the calculated areas of the leftventricular blood pool using the three routes wetook with a ’ground truth’ established by a clinician. The cine sequence is that of a normal patient.
50010001500200025003000350040000246810121416
L V P l a n a r A r e a ( p i x e l s )
Frame NumberGround TruthMax rule: Density data onlyMax rule: Density + VMax rule: Density + directions
Figure 4.
Comparison of calculated LV area for the three data sets used.We note that clustering with velocity magnitude tends to produce quite erratic results at frames 12 and13. We ﬁnd that the density and densityanddirectional data produced almost identical results in terms of LV area (but not in terms of clustering). We also ﬁnd that, in general, the clustering results are all on theconservative side of estimating LV area.
4 CONCLUSIONS
As the aim of our research is to empower the clinician with a simpletouse tool like FCM, we did notattempt to derive a new algorithm to take account of the special nature of the velocity data. Our resultsprove that including the velocity magnitude data in the data set can actually give misleading results, butthat the directional velocity information is useful in verifying densitydata results.The FCM algorithm has proven itself to be quite robust. Given the fact that it starts with almost no priorinformation, it is quite accurate. However, we note the shortcoming of having to experiment in order toﬁnd a suitable value for
c
. We remindthe readerthat we avoided the problemof nonrepeatabilityof resultsby using the result of one frame to start off the next. However, the problem of nonrepeatability still existswhen we cluster the ﬁrst frame.Ourtechniqueiseasytouseandveryintuitive;cliniciansimmediatelygraspeditsapplication. Theaccuracyof our results show a lot of promise.
Acknowledgements
We would like to thank Dr Philip Kilner of the MR Unit, Royal Brompton Hospital for his comments onthe results of our research.
References
1. J. Bezdek.
Pattern Recognition with Fuzzy Objective Function Algorithms
. Plenum Press, 1981.2. M. C. Clark, L. O. Hall, D. B. Goldgof et al. “MRI segmentation using fuzzy clustering techniques.”
IEEE Engineering in Medicine and Biology Magazine
13(5)
, pp. 730–742, 1994.3. A. Boudraa, J.J. Mallet, J.E. Besson et al. “Left ventricle automated detection method in gated isotopic ventriculography using fuzzy clustering.”
IEEE Transactions on Medical Imaging
12(3)
, September 1993.4. H.K. Tu, D. B. Goldgof & E. Backer. “Utilizing fuzzy
c
shells for automatic approximate lv location for initialization of myocardial structure and functions analysis algorithm.” In
Medical Imaging 1994: Physiology and Function from Multidimdensional Images
. 1994.