A NOVEL ALGORITHM FOR CLASSIFICATION OF SPECT IMAGES
OF A HUMAN HEART
Krzysztof J. Cios, Lucy S. Goodenday*, Kanu K. Shah, and Gursel Serpen
The University of Toledo, Toledo, OH 43606
*The Medical College of Ohio, Toledo, OH 43607
Abstract
This paper describes a semi-automated procedure for analyzing single photon emission computed
tomography (SPECT) images of a human heart and classifying the images into one of several categories:
normal, infarct, ischemia, infarct and ischemia, reverse re-distribution, artifact and equivocal. The procedure
aids the physician in the interpretation of SPECT images and consists of two steps. The first step processes
the reconstructed SPECT images. These images contain multiple slices of 64x64 pixels with 16 bits
resolution. Scanned images are converted into numerical format by using boundary extraction, region of
interest (ROI) selection, and segmentation techniques. A new algorithm was developed to extract a
rectangular ROI from each image. The second step involves automatic classification of the processed
images into one of the seven categories, listed above, using a knowledge-based system employing machine
learning algorithms (C4.5 and CLIP3) and fuzzy logic modeling, to generate classification rules. The
performance of the system is measured in terms of accuracy, the gold standard being interpretation of the
images by experienced cardiologists. Accuracy of the system using the rules generated by the machine
learning algorithms were 94% and 81%, respectively. Accuracy, after the fuzzy linguistic variables were
specified from the rules generated by the C4.5 and CLIP3 algorithms, was 91% and 86%, respectively.
Overall, the system performance closely approximated that of an experienced cardiologist.
Introduction
The traditional way to build a knowledge-based system is to represent a domain's expert knowledge
using a set of IF-THEN rules. Experts are known for not being able to explain how they make decisions, and
the explanation as to how they make decisions is at best fuzzy (Wellbank, M., 1983). Extracting knowledge
from a human expert and representing that knowledge in a symbolic form has proved to be an arduous and
labor intensive effort (Forsyth, R., 1984), also known as the 'knowledge acquisition bottleneck'. This paper
proposes to employ machine learning to solve this bottleneck problem by discovering new concepts and
rules from examples.
Since much of the human knowledge including the expert's is vague, the facts and rules are neither
totally certain nor totally consistent. One way to describe the vague concepts is to use fuzzy set-theoretic
modeling of data (Zadeh, 1965). Fuzzy set theory provides a natural approach to manipulating problems
where the transition between membership and nonmembership of the classes of objects is gradual.
Image recognition by computer requires at least two kinds of algorithms: one for extracting the
features which are representative of the class in question, and another for recognizing the original object
conceptually based on knowledge of the object, its pattern, and how it is used. A pattern can be
transformed into a structural representation by using rules. These rules can be either generated by a
machine learning algorithm or formulated by experts. This paper describes a system for detecting
abnormalities in myocardial perfusion. The system analyzes the reconstructed single photon emission
computerized tomography (SPECT) images using machine learning algorithms and fuzzy logic modeling.
Specifically, we shall use C4.5 (Quinlan, 1993) and CLIP3 (Cios et al., 1996) machine learning algorithms.
The input to the system are the reconstructed SPECT gray level scintigraphic images of the heart and the
output is the classification of heart images into several classes of abnormalities in myocardial perfusion, if
an abnormality exists.
The problem of diagnosing abnormalities of myocardial perfusion due to coronary artery stenosis
from SPECT Thallium-201 scintigraphs has been a major area for research over the last few years. SPECT
uses ordinary gamma ray-emitting radionuclides. Cardiac SPECT images are tomographic images which are
reconstructed from multiple planar views to form images of myocardial perfusion along three axes. There are
three views in SPECT images. The horizontal long axis and the vertical long axis views are taken from
longitudinal axes which are parallel to the long axis of the heart, Figure 1. The short axis view is taken in a
transaxial axis which is perpendicular to the long axis of the heart. For this study , the SPECT images were
taken under two conditions, "STRESS" and "REST-REINJECTION". First, the patient is asked to perform
physical exercise walking on the treadmill) to increase the pulse rate and blood pressure, and cause an
increase of the flow of blood to the heart muscle. Next, the patient is injected, at maximal tolerated exercise,
with a radionuclide myocardial blood tracer (Thallium 201). Images that are taken after performing physical
exercise are known as "STRESS" images. "REST-REINJECTION" images are taken after the radionuclide
injected during the stress imaging redistributes in the heart at rest and after a new injection of radionuclide
has been administered at rest. To find significant abnormalities in myocardial perfusion, cardiologists
compare the images of STRESS and REST-REINJECTION. By looking at the images, they locate the
perfusion defects in the myocardium and diagnose the patient into one of seven classes: normal, infarct and
ischemia, infarct, ischemia, reverse redistribution, artifact, or equivocal.
Figure 1: Various Axes Intersecting the Heart
The core of this paper forms the basis for the development of a computer system which simulates a
portion of the work of a nuclear cardiologist, namely that of detecting abnormalities of myocardial perfusion
due to coronary artery stenosis. The proposed system classifies the heart images into one of the six
diagnostic classes: normal, infarct, ischemia, infarct & ischemia, reverse redistribution and artifact. If the
system is not able to classify the heart images into one of the six classes, then it will classify the heart
images into a separate class called equivocal, i.e. a category for which the system is not able to determine
any one of the five abnormalities in the myocardial perfusion such as infarct, ischemia, infarct and ischemia,
reverse redistribution and artifact defects, nor is able to classify an image as normal.
Image Processing and Classification System
Reconstructed tomographic image slices contain the image of a heart in cross-section as well as
artifacts which can be seen in the background of the images. Since we are interested only in the cross-
section image of a heart, we need to subtract the background and noise from the image. In this work, noise
and background image may be very strong (i.e. intensity of noise may be almost the same as that of the
heart image). Since changing only the contrast value does not help in differentiating background from the
heart image, a region of interest (ROI) was selected to differentiate between the background image and the
heart cross section image. As the size of ROI is about 20 20 pixels, which is much smaller than the size of
the original images, significant savings in memory requirements and processing time are realized.
In recognition of images, it is important to detect boundary lines that distinguish an object from its
background, or two surfaces of an object. Detection of a boundary is usually done by grouping many small
edges of a pattern. The edge of an object corresponds to a part of the pattern where the value of the pattern
function changes drastically. Once boundary lines are detected, they can be used to extract the region
surrounded by these lines. We developed an algorithm based on the splitting method (Anzai Y., 1992 ) for
region extraction. A formal definition of the algorithm is presented in the following paragraphs. A region is
a set of pattern elements defined as follows:
Definition 1. Let D be the finite set of pattern elements from a given pattern function, and let 2
D
be the set
of subset of D. Let Q(D) be a predicate on 2
D
such that, for any subset of pattern elements, D
D
e2 ,
returns TRUE if the elements in the subset have uniform values and returns FALSE otherwise. A set of
pattern element sets D D
n 1
, , is called a partition of I for a predicate Q if
I D
i
i
n
=
=1
where D D j k
j k
= C = for , ( ) Q D TRUE i i n
i
= = , ,2,..., 1 and Q D D FALSE j k
j k
( ) = = .
Each set of pattern elements, D
i
, is called a "region."
As noted in Definition 1, in order to determine a region, we need a predicate for judging whether
the pattern elements included in that region have uniform values or not. Let us consider the following
predicate Qas an example:
Q D
TRUE x D f x c
FALSE x D f x c
( )
( )
( )
=
e >
e s
x, and
x, and
where f(x) is a pattern function and c is a given constant. For this predicate Q, we are only considering a
pattern element set D where either for all x e D it holds that f(x) > c, or for all x D it holds that f(x) < c.
Therefore, Q is a predicate applicable only when the value of a pattern function distinguishes an object from
its background. In other words, if we let D1 and D2 be the sets of pattern elements for an object and its
background, respectively, then Q is a predicate for extracting D1 and D2 so that Q(D1)=TRUE and
Q(D2)=FALSE.
Region extraction of this kind can be done approximately by setting an appropriate threshold value
c. For example, if we make a histogram for the value of a pattern element, f(x), and remove small variation of
values by smoothing it, then we can use the minimal value as the value of c. A histogram can be smoothed
a histogram, for example, by using the histogram of sum of intensities row-wise and column-wise and
determining the threshold value from the estimated parameter values. The method thus presented is called
the splitting method (Anzai Y., 1992). The splitting method can be applied recursively to a given problem for
extraction of smaller regions. The developed algorithm for recursive splitting is outlined below:
1) Let the domain, D, of a given pattern function, f(x), be the initial region. Set D = {D}.
2) Construct the histogram of the values of f(x) on the pattern elements.
3) Smooth the histogram and determine the threshold value, c, as the minimal value.
4) If there is no minimal value in the histogram, stop. D is the extracted region. Otherwise, go to
step 5 using c as the threshold value.
5) Let { } D x f x c
1
= > | ( ) , { } D x f x c
2
= < | ( ) and D D D D D = { , } { }
1 2
.
6) Repeat steps 2 through 5 for another function f(x) if it exists.
7) Repeat steps 2 through 5 for all D eD.
The above algorithm is a global method for extracting regions based on the distribution of intensity
values of a pattern function.
Machine Learning Algorithms
We have employed two machine learning algorithms, C4.5 (Quinlan, 1979; 1983) and CLIP3 (Cios et
al., 1996), in this paper. CLIP3 is an improvement and extension of the CLIP2 algorithm (Cios and Liu N.,
1995a and 1995b ). The CLIP3 algorithm generates multiple rule hypotheses in order to increase the chance
of capturing the true meaning of concept. At the same time it tries to solve the problem of overfitting while
learning from noisy data. That is done by combining the tree-pruning technique of ID3 (Quinlan, 1979)
family of algorithms, and cover generation idea of AQ (Michalski, 1990) family of algorithms. CLIP3
partitions training examples into noise free subsets and then generates multiple rules from each of the
subsets. It generates concept description by solving several Integer Linear Programming models from a
decision tree. The CLIP3 algorithm works only on discrete data. As SPECT data are continuous, they need
to be converted into discrete form: this conversion greatly affects the performance of the proposed system.
Results
The analysis was performed on three sets of data using rules generated by the C4.5 and CLIP3
machine learning algorithms. Each test set consists of 9 normal, 8 infarct and ischemia, 7 infarct, 3 ischemia,
2 reverse redistribution, 2 artifact and 2 equivocal patients data, diagnosed as such by a cardiologist.
Accuracy performance of the proposed method is presented in Table 1.
ALGORITHMS
DIAGNOSIS C4.5 CLIP3 C4.5 w/Fuzzy CLIP3 w/Fuzzy
Normal 93/84/96 65/52/69 83/56/92 77/52/85
Infarct & Ischemia 91/70/93 73/44/82 79/22/96 82/57/89
Infarct 91/77/95 73/32/84 91/86/92 81/59/87
Ischemia 96/70/99 87/20/94 97/80/99 85/30/91
Reverse Redistribution 94/71/99 91/43/95 96/86/97 94/43/97
Artifact 94/67/98 88/0/94 96/50/99 90/17/95
Equivocal 95/50/98 90/67/91 95/50/98 93/50/96
Table 1. Accuracy/Sensitivity/Specificity Results Comparison in %
Conclusions
The developed system takes heart SPECT images, which contain multiple slices, as inputs and
classifies them into one of the seven classes at the output. An algorithm for extracting rectangular ROI from
noisy and low quality images was developed based on the splitting method. The C4.5 and CLIP3 machine
learning algorithms were used to generate the rules and these rules were used to classify heart images. The
34 rules generated by the C4.5 algorithm and 38 rules generated by the CLIP3 algorithm offered performance
which was comparable with that of an experienced cardiologist.
The performance of the system was measured in terms of sensitivity, specificity, and accuracy. The
accuracy of the system using the rules generated by the C4.5 and CLIP3 machine learning algorithm was
94% and 81%, respectively. Since the continuous data was converted into discrete data, the accuracy of
CLIP3 algorithm was not as good as the accuracy of the C4.5 algorithm. The accuracy of the system using
the fuzzy linguistic variables and fuzzy membership functions defined from the rules generated these
machine learning algorithms was 91 % and 86%, respectively. Fuzzy logic implementation improved the
results for the CLIP3 algorithm, which may be explained by the fact that the ranges used for discrimination of
the data were themselves fuzzy.
Since our data base was small (99 patients) we divided it into three subsets and rotated them for training
and testing. The rules thus generated gave acceptable results. As the system displays images along
various axes at all times, its major advantage is that a cardiologist can verify the results of the system by
looking at the images while using our system. The reliability of the rules depends heavily on the amount of
sample data from which they are generated. As the size of the training data will increase in the future so will
the reliability of the rules.
References
[1] Cios K. J., Wedding D. and Liu N., CLIP3: Cover Learning Using Integer Linear Programming,
Submitted to a journal.
[2] Cios, K. J. and Liu, N. 1995a., An Algorithm which Learns Multiple Covers via Integer Linear
Programming, Part-I: The CLIP2 Algorithm, Kybernetes, MCB University Press, U.K., Vol. 24(2), pp 29-50,
1995.
[3] Cios, K. J. and Liu, N. 1995b., An Algorithm which Learns Multiple Covers via Integer Linear
Programming, Part-II Experimental results and Conclusions, Kybernetes, MCB University Press, U.K., Vol.
24(3), pp 28-40, 1995.
[4] Forsyth and Richard., Expert systems Principles and Case Studies, Chapman and Hall, 1984.
[5] Michalski, R. S., Learning Flexible Concepts: Fundamental Ideas and a Method Based on Two-Tired
Representation, in Y. Kodratoff and R. S. Michalski (Eds.) Machine Learning: An Artificial Intelligence
Approach, Vol. III, pp. 63-102, Morgan Kaufmann, San Mateo, 1990.
[6] Quinlan J. R., C4.5 Programs for Machine Learning, Morgan Kaufmann, 1993.
[7] Quinlan J. R., Discovering Rules by Induction from Large Collection of Examples, Knowledge-base
systems in the Micro Electronic Age, Edinburgh University Press, 1979.
[8] Wellbank, M., A Review of Knowledge Acquisition Techniques for Expert Systems, British Telecom
Research, Ipswich, England, 1983.
[9] Zadeh L., Fuzzy Sets, Information and Control, Vol. 8, pp. 338-353, 1965.