=Paper=
{{Paper
|id=Vol-1710/paper24
|storemode=property
|title=The Study of Applicability of the Decision Tree Method for Contouring of the Left Ventricle Area in Echographic Video Data
|pdfUrl=https://ceur-ws.org/Vol-1710/paper24.pdf
|volume=Vol-1710
|authors=Andrey Mukhtarov,Sergey Porshnev,Vasiliy Zuzin,Anastasia Bobkova,Vladimir Bobkov
|dblpUrl=https://dblp.org/rec/conf/aist/MukhtarovPZBB16
}}
==The Study of Applicability of the Decision Tree Method for Contouring of the Left Ventricle Area in Echographic Video Data==
https://ceur-ws.org/Vol-1710/paper24.pdf
The Study of Applicability of the Decision Tree
Method for Contouring of the Left Ventricle
Area in Echographic Video Data
Porshnev S.V.1 , Mukhtarov A.A.1 , Bobkova A.O.1 , Zyuzin V.V.1 , and
Bobkov V.V.2
1
Ural Federal University
named after First President of Russia B.N. Yeltsin,
Ekaterinburg, Russia (620002, Ekaterinburg, Mira Str., 19)
sergey_porshnev@mail.ru,andrew443209993@yandex.ru,
iconismo@gmail.com,zvvzuzin@gmail.com
2
Ural State University of Economics and Ural Institute of Business,
Ekaterinburg, Russia, (620144, Ekaterinburg, 8 th of March Str. 62)
btow@yandex.ru
Abstract. Echocardiography is a widespread method for analysing of
the heart muscle, in which a consistent set of frames with instant images
of the heart are recieved. Cardiologists build a contour, which bound an
area of the left ventricle for each frame, because its state gives the infor-
mation to diagnose diseases of the heart muscle. Doctors have an idea
about the regular contour shape. They sometimes ignore some contrasing
tissue on the picture and they construct parts of the contour on not con-
trasting areas of the image. Thus, the analysis results are dependent on
the experience of the particular doctor, and therefore, to some extent,
are subjective. In this context, the task of automating contouring of the
left ventricle on an ultrasound image is relevant. The article discusses
the experience of using machine learning method (decision trees) for the
automatic identification of the left ventricle region on ultrasound images
of the apical four-chamber-projection of the human heart. The list of
pixels attributes used in machine learning are submitted. The results of
the application of decision trees, as well as quantitative assessments of
the quality of delineation of the left ventricle, are shown.
Keywords: contouring, left ventricle, echocardiographic images, image
processing, machine learning, decision trees.
1 Introduction
Echocardiography is one of the cheapest non-invasive methods of diagnosing
heart disease using ultrasound (US) images. The left ventricle (LV) of the heart
represents a particular interest to cardiologists, since most of various pathologies
and heart diseases change, primarily, its state.
2 The Study of Applicability of the Decision Tree Method
For assessment the state of LV, cardiologist builds the contour, bounding
region of LV, for each frame of the ultrasound images sequence, usually in manual
mode.
There are many different ultrasound scanners, each of which is equipped
with toolkit for the LV contouring (Philips, Aloka Hitachi, Toshiba, Siemens,
General Electric, and others.). However, as the analysis of commercial offers the
above-mentioned companies, there is no devices for echocardiography with built-
in programs, which would allow to carry out delineation of LV in fully automatic
mode.
Also, numerous studies have been conducted and various contouring algo-
rithms have been developed. However, these articles [17, 7, 3, 6, 8] describe a
problem to delineate MRI image data only. This task is more simple, because
the MRI image is clear, the amount of noise is minimized. Also in [9] showed
an algorithm to highlight the contour on the 3D ultrasound image. These algo-
rithms can not be used to solve our problem. Studies have been conducted on the
automation of the process of left ventricle delineation using tracking algorithms
[4, 10, 13]. However it was managed to develop only a semi-automatic algorithm
, which requires the participation of an expert. Thus, today the task of fully
automatic LV contouring algorithm for the 2-D ultrasound images is relevant.
The purpose of this paper is to analyze the applicability of the decision tree
method to automate the process of the delineation of the left ventricle on the
video sequence.
2 Classification of Data
2.1 Statement of the Problem
There is a set of ultrasound images in RGB space (hereinafter referred to as
frames) 640 480 pixels of apical four-chamber heart projection. For each frame
there is a corresponding binary frame with expert area of LV. The example of
frame with LV boundaries, designated by expert, is shown in figure 1.
Each frame is a set of pixels with known coordinates (x, y) and the halftone
intensities I ∈ [0, 255] :
I = 0, 2989 · R + 0, 5870 · G + 0, 1140 · B, (1)
where R, G, B - are the brightness components of a pixel in RGB-space.
The analysis of expert experiment of LV area contouring showed, that the
doctor builds a border, relying on their own understanding of the correct shape
of the contour, ignoring some of the contrasting fabric of images and construct-
ing additions to the border areas of the frame with a low signal to noise ratio.
However, algorithmization action of expert in the construction of some of the
boundaries of the LV circuit fails. For the automation of procedures of the LV
contouring, it requires an additional frames analysis algorithms, such as ma-
chine learning, which can be used in this task in accordance with the following
algorithm:
The Study of Applicability of the Decision Tree Method 3
Fig. 1. The example of ultrasound image of the heart with the expert contour of LV
1. Training of the classifier:
– Formation of the initial set of pixels X=x1 , ..., xL (training sample), be-
longing to the corresponding frames in which experts noted the LV bor-
der.
– Selecting the features that characterize the pixel: f¯ = (f1 , f2 , . . . , fJ ) ,
including signs of belonging of pixel to LV area (fi )
– Marking pixels as belonging to LV area ( fi = 1, if the pixel belongs to
the field of LV and fi = 0 in the opposite case).
– Forming a set of features F = f¯1 , . . . , f¯L , where fi - is the vector
containing characteristic values of i-th pixel.
– Construction of the classifier in the form of a decision tree [2, 14, 16]
using the set of features F pixels training sample.
2. Classification of frame pixels:
– Calculation of the features values, characterizing pixel, for each classified
pixel of a frame: f¯ = (f1 , f2 , . . . , fL−1 ) .
– The calculation of the features values of belonging to the LV area fL for
each pixel of the frame based on a decision tree.
– Isolation of the left ventricle contour on the frame as the boundaries of
classified area.
Of the above algorithm it can be seen that one of the most important stages
is the stage of the classifier training. Methods of the classifier training based on
decision tree, that takes into account the features of analyzed images, considered
in the next section.
4 The Study of Applicability of the Decision Tree Method
3 Methods of Learning
As the vector coordinates of the pixel features were selected Cartesian coordi-
nates of the pixel x, y (f1 = x, f2 = y), and the values of the intensity of the
pixel in the frame, treated with one of following image processing methods [11,
12]:
1. Histogram equalization of the image pixels intensity;
2. Adaptive transformation of local contrasts;
3. Local range of image(rangefilt);
4. Local standard deviation of image;
5. The boundaries detection using the Sobel operator;
6. The boundaries detection using the Prewitt operator;
7. The boundaries detection using the Roberts operator;
8. The boundaries detection by looking for zero-crossings after filtering the
original image with a Laplacian of Gaussian filter;
9. The boundaries detection by looking for zero-crossings after filtering the
original image with a Canny operator;
10. The boundaries detection using the Canny operator.
Thus, the selected vector of features F belongs to a 13-D space (J = 13):
F = (x, y, Ik , f13 ) ; k = 1, 10
The results of applying these methods to the image in Figure 1, shown in
Figure 2. To train the classifier a data set was used consisting of 662 frames
with a resolution of 640 × 480 , since the dimension of the feature space is very
large, the density of each of frame was reduced by 100 times (64 × 48) while
maintaining the geometric dimensions of the frame. As a result, the cardinality
of set of frames is equal to 26437632. Typical features pixels values of classified
images are presented in table 1.
Table 1. Example of a table with features
Feature
Pixel
1 2 3 4 5 6 7 8 9 10 11 12 13
628401 27 49 42 5.68 30 11.8 0 0 0 0 0 0 1
628402 27 50 34 5.60 22 7.3 0 0 0 0 0 1 1
628403 27 51 38 5.29 48 12.7 0 0 0 0 0 1 0
628404 27 52 30 4.90 35 14.4 0 0 1 1 1 1 0
The Study of Applicability of the Decision Tree Method 5
Fig. 2. Image processing results, a) histogram equalization of the image pixels in-
tensity, b) The entropy of the image, c) Local range of image, d) Local standard
deviation of image, e) Sobel operator, f) Prewitt operator, g) Roberts operator, h)
- The boundaries detection by looking for zero-crossings after filtering the original
image with a Laplacian of Gaussian filter, i) - The boundaries detection by looking
for zero-crossings after filtering the original image with a Canny operator, k)- Canny
operator
Evaluation of training using the decision tree method was done using the
cross-validation procedure:
1. The resulting table of features was divided into 10 equal-sized blocks
{Bi } , i = 1, 10.
2. Test block Bk , k = 1, 10 has consistently selected from {Bi }, and a plurality
of blocks {Bi } \Bk used as a training sample.
3. The estimate of the average values of the error (the share of misclassified
pixels) of all tested samples was calculated using cross-validation.
When classifying pixels resulting errors can be divided into two groups:
– error of the first kind - a pixel belonging to the area of the left ventricle, is
classified as not belonging to it;
– error of the second kind - the pixel does not belonging to the area of the left
ventricle, is classified as belonging to her.
A numerical estimate of error includes errors both the first and the second
kinds.
Average classification accuracy of pixels by 10 blocks was 0.9866, respectively,
the average error of classification was - 0.0134.
There is the ROC-curve, constructed for this classifier, shown in Figure 3.
The index of AUC was 0.9715.
6 The Study of Applicability of the Decision Tree Method
Fig. 3. ROC-curve for a decision tree classifier
4 Assessment of the Quality of Construction LV Area
Assessment of the quality of construction of the LV area was done based on the
same sample of 662 frames (17 patients). To train the classifier 620 frames were
used of 16 patients (94%). Testing was conducted on the remaining 42 frames of
the last (17) patient (6%).
Example of the LV region, formed by qualified pixels using a decision tree,
is shown in Figure 4.
Fig. 4. Example of LV area, built with the help of the decision tree
The Study of Applicability of the Decision Tree Method 7
Classified area was transformed into LV contour for further evaluation as
follows:
1. The removal of pixels distant from the main area;
2. Morphological processing by operation ”closure” with the structuring ele-
ment ”disk” a radius of 3 for smoothing the area;;
3. Detecting the contour from the resulting area.
Examples of the contour and the corresponding expert contour presented in
Figure 5.
Fig. 5. Image of the expert contour (green) and the contour constructed according to
the algorithm (red).
Figure 5 shows that the contours are significantly different. In this context,
the quantitative assessment of the quality of the left ventricle contouring was
held. For this purpose the following criteria were used:
– cross validation [1, 5]
– area under the curve
– precision
S∩
K= ,
Scont
were S∩ - is the intersection of square of area, limited by expert contour,
and area, formed from classified pixels, Scont - square of the area, formed
from the classified pixels.
– recall
S∩
Recall =
Sexp
were Sexp - is the area of the region bounded by the expert contour.
8 The Study of Applicability of the Decision Tree Method
– F-measure
2 · P recision · Recall
F =
P recision + Recall
– is the coefficient of the kinematic center of mass (CM) of the left ventricle
area in the video sequence of frames with flexing of the heart muscle of
patient
Sellipse
K=
Sdiast cont
were Sellipse - is the area of the ellipse, bounding CM LV, Sdiast cont - is the
area of the region contour in diastole.
Estimates for the coefficient of CM motion in patients with pathologies and
without pathologies are given [15].
The results of these criteria are presented in table 2.
Table 2. Quantitative assessment of the quality of contouring.
Criteria Assessment
Recall 0.77±0.01
Precision 0.92±0.02
F 0.84
K 0.001
Validation 0.9865
AUC 0.9715
5 Conclusions
In the studies examined the use of one of the machine learning methods (decision
tree) in the problem of the development of the automatic delineation algorithm
of the heart left ventricle to the echographic video sequences.
Quantitative assessment of the quality of learning were made. The following
values of criteria were received: Precision - 0.92, Recall - 0.77, F-measure - 0.84
coefficient of kinematics CM - 0.001.
According to the results it can be concluded that the contour, derived from
the classified LV region, is unsatisfactory due to the fact that it significantly
differs from the expert contour. (Values of precision, recall and F-measure for
satisfactory contour close to 1.) In this regard, the algorithm requires further
research, the purpose of which:
The Study of Applicability of the Decision Tree Method 9
– determine the usefulness of each feature in the training set and reduce the
dimension of feature space using only the most informative features;
– explore the use of other well-known machine learning algorithms within the
task.
References
1. Cross validation, https://www.cs.cmu.edu/~schneide/tut5/node42.html
2. Decision trees, http://hdl.handle.net/10995/36261
3. van Assen, H.C., Danilouchkine, M.G., Behloul, F., Lamb, H.J., van der Geest,
R.J., Reiber, J.H.C., Lelieveldt, B.P.F.: Cardiac lv segmentation using a 3d active
shape model driven by fuzzy inference. Medical image computing and computer-
assisted intervention - MICCAI 2003 2878, 533–540 (2003)
4. Bardinet, E., Ayache, N., Cohen, L.D.: Tracking and motion analysis of the left ven-
tricle with deformable superquadrics. Medical image analysis 1(2), 129–149 (1996)
5. Blockeel, H., Struyf, J.: Efficient algorithms for decision tree cross-validation. Jour-
nal of Machine Learning Research 3, 621–650 (2002)
6. Guttman, M.A., Prince, J.L., McVeigh, E.R.: Tag and contour detection in tagged
mr images of the left ventricle. IEEE Transactions on Medical Imaging 13(1), 74–88
(1994)
7. Jolly, M.P.: Automatic segmentation of the left ventricle in cardiac mr and ct
images. International journal of computer vision 70(2), 151–163 (2006)
8. Lee, H.Y., Codella, N.C.F., Cham, M.D., Weinsaft, J.W.: Automatic left ventricle
segmentation using iterative thresholding and an active contour model with adap-
tation on short-axis cardiac mri. IEEE Transactions on Biomedical Engineering
57(4), 905–913 (2009)
9. Milletari, Yigitsoy, Navab, Ahmadi: Left ventricle segmentation in cardiac ul-
trasound using hough-forests with implicit shape and appearance priors (2014),
http://hdl.handle.net/10380/3485
10. Mukhtarov, A.A., Zuzin, V.V.: Software development for automating the contour-
ing process of the left ventricle of the heart on the echographic video sequences
(2016), http://hdl.handle.net/10995/36261
11. Porshnev, S., Kublanov, V., Bobkova, A.: Evaluation of informative of features,
used for the treatment of echocardiographic images. Biomedical electronics (4),
19–26 (2013)
12. Porshnev, S., Zyuzin, V., Bobkov, V., Bobkova, A.: Factor analysis of the features
used to automatically analyze the results of echocardiography. Proceedings of the
23rd International Crimean Conference ”Microwave equipment and telecommuni-
cation technology” pp. 1071–1072 (2013)
13. Porshnev, S., Zyuzin, V., Bobkov, V., Bobkova, A.: Semi-automatic contouring
algorithm of the left ventricle on the echocardiographic images. Fundamental re-
search 8(1) (2013)
14. Porshnev, S., Zyuzin, V., Bobkov, V., Bobkova, A.: The application of decision
trees algorithm for selecting the area of the left ventricle on echocardiographic
images. 15th International Academic Conference on Development in Science and
Technology (IACDST-2015) (4) (2015)
15. Porshnev, S., Zyuzin, V., Mukhtarov, A., Bobkova, A.: The study of the mass center
motion of the left ventrical area in echocardiographic videos. In: Supplementary
Proceedings of the 4th International Conference on Analysis of Images, Social
Networks and Texts (AIST-SUP 2015) (April), 9–11 (2015)
10 The Study of Applicability of the Decision Tree Method
16. Shampandar, A.: Arti
cial intelligence in computer games: how to teach virtual characters react to exter-
nal in uences (2007)
17. Ying-Li, Connelly, K.A., Dick, A.J., Wright, G.A., Radau, P.E.: Automatic func-
tional analysis of left ventricle in cardiac cine mri. Quantitative Imaging in medicine
and surgery pp. 200–209 (2013)