Ant Colony based Feature Selection Heuristics
for Retinal Vessel Segmentation

arXiv:1403.1735v1 [cs.NE] 7 Mar 2014

Ahmed.H.Asad, Ahmad Taher Azar, Nashwa El-Bendary, Aboul Ella Hassaanien

Abstract Features selection is an essential step for successful data classification,
since it reduces the data dimensionality by removing redundant features. Consequently, that minimizes the classification complexity and time in addition to maximizing its accuracy. In this article, a comparative study considering six features
selection heuristics is conducted in order to select the best relevant features subset.
The tested features vector consists of fourteen features that are computed for each
pixel in the field of view of retinal images in the DRIVE database. The comparison is assessed in terms of sensitivity, specificity, and accuracy measurements of
the recommended features subset resulted by each heuristic when applied with the
ant colony system. Experimental results indicated that the features subset recommended by the relief heuristic outperformed the subsets recommended by the other
experienced heuristics.
Ahmed.H.Asad
ISSR, Computer Sciences and Information Dept., Cairo University, Cairo - Egypt,
Scientific Research Group in Egypt (SRGE), http://www.egyptscience.net
e-mail: ah_assad@hotmail.com
Ahmad Taher Azar
Faculty of computers and information, Benha University, Egypt,
Scientific Research Group in Egypt (SRGE), http://www.egyptscience.net
e-mail: ahmad_T_azar@ieee.org
Nashwa El-Bendary
Arab Academy for Science,Technology, and Maritime Transport, Cairo - Egypt,
Scientific Research Group in Egypt (SRGE), http://www.egyptscience.net
e-mail: nashwa.elbendary@ieee.org
Aboul Ella Hassanien
Information Technology Dept., Faculty of Computers and Information, Cairo University,
Cairo - Egypt,
Scientific Research Group in Egypt (SRGE), http://www.egyptscience.net
e-mail: aboitcairo@gmail.com

1

2

Ahmed.H.Asad, Ahmad Taher Azar, Nashwa El-Bendary, Aboul Ella Hassaanien

1 Introduction
Retinal blood vessels are important structures in many ophthalmological images.
The automated extraction of blood vessels in retinal images is an important step in
computer aided diagnosis (CAD) and treatment of diabetic retinopathy [1, 2, 3, 4,
5, 6], hypertension [7], glaucoma [8], obesity [9], arteriosclerosis and retinal artery
occlusion, etc. These diseases often result in changes on reflectivity, bifurcations,
tortuosity as well as other patterns of blood vessels. Vessel tortuosity, characterizes hypertension retinopathy [10] and diabetic retinopathy, which usually leads to
neovascularization. The diabetic retinopathy is one of the most common causes of
vision defects or even blindness worldwide [11], as it spreads diabetes on the retina
vessels, thus they lose blood supply that causes blindness in short time. Hence, analyzing vessel features gives new insights to diagnose the corresponding disease
early. So, if abnormal signs of diabetic retinopathy could be detected early, effective
treatment before their initial onset can be performed and blindness can be prevented
in more than 50% of cases [12, 13]. However, manual segmentation of retinal blood
vessels is a long and tedious task, which also requires training and skill. Hence, the
early detection can be achieved via automatic segmentation of retinal blood vessels,
which is the critical component of circulatory blood vessel analysis systems [14].
Also, retinal blood vessels segmentation is the core stage in automated registration
of two retinal blood vessels images of a certain patient to follow and diagnose disease progress at different periods of time [15].
In this article, an improvement of previous work [1] is presented by conducting a
comparative study for six feature selection heuristics; namely, correlation-based feature selection (CFS), Fisher score, Gini index, Relief, sequential forward selection
(SFS), and sequential backward selection (SBS). The aim of this article is to recommend the best relevant features subset from features vector consists of fourteen
features that are computed for each pixel in the field of view (FOV) of retinal image
in the DRIVE database [6]. The six experimented feature selection algorithms are
compared in terms of sensitivity, specificity, and accuracy of their recommended
features subsets when applied with ant colony system (ACS) algorithm [16]. The
rest of this article is organized as follows: Section 2 describes in more details the
used database, samples selection, selected features, and the ant colony system. Section 3 presents the six features selection heuristics in more details. Section 4 reports
the results and experimental evaluations of the proposed approach. Finally, in Section 5, conclusions and directions for future research are discussed.

Ant Colony based Feature Selection Heuristics for Retinal Vessel Segmentation

3

2 Methods
2.1 Retinal Image Database and Samples Selection
The Digital Retinal Images for Vessel Extraction (DRIVE) database [6], which consists of a total of JPEG 40 color fundus images; including 7 abnormal pathology
cases, is used in this article. The images were obtained from a diabetic retinopathy screening program in the Netherlands. The images were acquired using Canon
CR5 non-mydriatic 3CCD camera with FOV equals to 45 degrees. Each image resolution is 584*565 pixels with eight bits per color channel (3 channels). The set
of 40 images was equally divided into 20 images for the training set and 20 images for the testing set. Inside both sets, for each image, there is circular field of
view (FOV) mask of diameter that is approximately 540 pixels. Inside training set,
for each image, one manual segmentation by an ophthalmological expert has been
applied. Inside testing set, for each image, two manual segmentations have been applied by two different observers, where the first observer segmentation is accepted
as the ground-truth for performance evaluation.
Images in DRIVE training set contain 569415 vessel pixels and 3971591 nonvessel pixels, where samples are needed to be selected for features computation.
Since the ratio of vessel pixels to non-vessel pixels in each image and overall images
is 1:7 as an average, the samples set consists of 1000 vessel pixels and 7000 nonvessel pixels from each image. So, for 20 images, it will be 160000 total samples. In
the previous work [1], the samples set consisted of 100000 vessel and 100000 nonvessels pixels selected randomly from the whole training set using correlation-based
feature selection (CFS) heuristic.

2.2 Selected Features
The selected features are the gray-level of green channel of RGB retinal image,
group of five features based on gray-level ( f1 , f2 , f3 , f4 , f5 ) and group of eight
features based on Hu moment-invariants (Hu1 , Hu2 , Hu3 , Hu4 , Hu5 , Hu6 , Hu7 , Hu8 )
[1]. Most of the vessels segmentation approaches extracted and used the green color
image of RGB retinal image for further processing, since it has the best contrast between vessels and background. The five gray-level based features group is presented
by Marin et al. in [17] and its features describe the gray-level variation between
vessel pixel and its surrounding pixels. The Hu moment-invariants [18] are the best
shape descriptors, as they are invariant to translation, scale, and rotation change.
So, they are used by the second group of eight features to describe vessels having variant widths and angles. The selected features are simple, well-discriminating
between vessel and non-vessel classes and don’t need to be computed at multiple
scales or orientations. The features computation is more detailed in [1].

4

Ahmed.H.Asad, Ahmad Taher Azar, Nashwa El-Bendary, Aboul Ella Hassaanien

2.3 Ant Colony System (ACS)
For solving the travelling sales man problem of exploring the shortest path, ACS was
first proposed in [16]. It simulates the foraging behavior of real ants in nature, where
multiple ants are going out in random paths when they are searching for foods. As
the ant is moving, it is depositing a chemical substance, called ”pheromone” on its
path to attract other subsequent ants to follow that path. As the time passes, the
pheromone evaporates so that the pheromone on the shorter path only remains for
a longer time causing other ants to be attracted to it. Thus, the shortest path is the
only path that attracts other ants to follow it.

3 Features Selection Heuristics
Feature selection plays an important role in building classification systems [19],
as it can not only reduce the dimension of data, but also lower the computation
consumption so that good classification performance can be obtained. In general,
feature selection algorithms, designed with different evaluation criteria, are divided
into two categories; namely filter methods, which rank features or select a subset
of them based on evaluation criterion, and wrappers methods, which use predetermined learning algorithms (classifiers) to select those features with high prediction
performance [20, 21]. This section briefly describes the six feature selection heuristics experienced in this article; namely, correlation-based feature selection (CFS),
Fisher score, Gini index, Relief, sequential forward selection (SFS), and sequential
backward selection (SBS).

3.1 Correlation-based feature selection (CFS)
It is a heuristic approach for evaluating the worth or merit of a subset of features [22,
23]. The main idea behind this selection method is that the most effective features for
classification are those that are most highly correlated with the classes (intensifiers
and dissipaters). At the same time, these features are the least correlated with other
features. The CFS method is therefore used to choose a subset of features that highly
represents these qualities. The best individual feature based on the merit metric
calculated by equation (1)
Ms = p

kr̄c f
k + k(k + 1)r̄ f f

(1)

where Ms is the heuristic merit of a features subset S containing k features, r̄c f
is the average feature-class correlation, and r̄ f f is the average feature-feature inter-

Ant Colony based Feature Selection Heuristics for Retinal Vessel Segmentation

5

correlation. The numerator gives an indication of how predictive a group of features
are, while the denominator represents how much redundancy existed among them.

3.2 Fisher Score
Fisher Score [24] is a type of supervised feature selection methods for examining
the correlation between projected data samples and their class labels on each feature
axis. It looks for features on which the classes are compact and far from each others.
By considering the sample coordinates on the feature fr , each class ω, ω = 1,. . ., c,
populated with nω labeled samples is characterized by its mean µωr and its variance
2 . Moreover, assume that µ is the mean of all data samples on the feature f , the
σωr
r
r
Fisher score Fr used to evaluate the relevance of the feature fr is defined as shown
in equation (2):
Fr =

∑cω=1 nω (µωr − µr )2
2
∑cω=1 nω σωr

(2)

In order to select the most relevant features, they are sorted according to the
decreasing order of their Fisher score Fr .

3.3 Gini Index
Gini index is a non-purity split method that fits sorting, binary systems, continuous
numerical values, etc. [25]. It is based on iterative splitting of the data samples into
subsets based on their feature values and so on until gaining coherent samples subset
[26]. This approach belongs to the filter class and it ranks the features in ascending
order, where the one with the smallest index is the more relevant. Suppose S is the
set of s samples. These samples have m different classes (Ci , i = 1,. . ., m) based on
its feature values. So, S can be divided into m subsets (Si , i = 1,. . ., m). Then Si is
the samples subset that belongs to class Ci and si is the samples number of subset
Si , then the Gini index of set S is computed as shown in equation (3)
m

Gini(S) = 1 − ∑ Pi2

(3)

i=1

where Pi is the probability that any sample belongs to Ci and estimating with si \s.

6

Ahmed.H.Asad, Ahmad Taher Azar, Nashwa El-Bendary, Aboul Ella Hassaanien

3.4 Relief
This heuristic estimates the features according to how well their values discriminate
among instances of different classes that are near each other [27]. It’s one of filter
class that weight features. The relief operates as follows: for a user-specified number
of instances m and for each instance X, relief searches for its two nearest neighbours;
one from the same class (called nearest hit H) and the other from a different class
(called nearest miss M). For each feature, it calculates its relevance score according
to equation (4)
W (A) = W (A) − di f f (A, X, H)/m + di f f (A, X, M)/m

(4)

where W (A) represents the relevance scores for any feature A, diff(A, X, H) is the
difference between the values of feature A for the two instances X and H, and m is
the number of instances sampled.

3.5 Sequential Forward/Backward Selection
The sequential forward selection (SFS) and sequential backward selection (SBS) are
two examples of the wrapper class. SFS [28] starts with an empty set and each time
it sequentially adds new feature to the set as this feature minimizes the classifier
prediction error. Otherwise, it removes this feature and tries another one. It remains
in this greedy behavior until the prediction error becomes fixed in certain range.
Conversely, SBS [29] starts with the full set of features and each time it sequentially
removes a feature from it as this removal minimizes the classifier prediction error
and so on as SFS.

4 Experimental Results and Analysis
Three measures are calculated for evaluating the classification performance of selected features subset with ACS. The first measure is the sensitivity (SN), which
is the ratio of well-classified vessel pixels. The second measure is the specificity
(SP), which is the ratio of well-classified non-vessel pixels. The third measure is the
accuracy (ACC), which is the ratio of well-classified vessel and non-vessel pixels.
The features subsets resulted via applying the previously stated feature selection
heuristics are shown in table 1.
As shown in table1, there are some features that have been never selected by
any heuristic (Hu6 , Hu7 and Hu8 ), features that have been selected by minority of
heuristics (Green gray-level, f1 , Hu2 , Hu3 and Hu5 ), features that have been selected by majority of heuristics ( f3 , f4 , f5 and Hu4 ), and features that have been
selected by all heuristics ( f2 and Hu1 ). Since f2 and Hu1 features are the most com-

Ant Colony based Feature Selection Heuristics for Retinal Vessel Segmentation

7

mon features between all recommended features subsets, it’s strongly indicated that
using both of them together can highly discriminate between the vessels and nonvessels pixels. This indication is also emphasized by the last row of table 2, which
shows the segmentation performance of each recommended features subset by each
heuristic. Fig.1 also depicts the segmentation performance of all recommended features subsets.
Table 1 Features subset recommended by feature selection heuristics
Feature Selection Heuristic
Selected Features Subsets
Relief
{ f1 , f2 , f3 , f4 , f5 , Hu1 }
CFS
{ f2 , f3 , f4 , f5 , Hu1 , Hu4 }
Fisher Score
{ f2 , f3 , Hu1 , Hu2 , Hu3 , Hu4 }
Gini Index
{ f2 , f4 , f5 , Hu1 , Hu4 , Hu5 }
SFS
{Greengray − level, f2 , f3 , f5 , Hu1 }
SBS
{Greengray − level, f2 , f5 , Hu1 }

Table 2 Classification performance values of ACS with features subset recommended by feature
selection heuristics
Features Selection Heuristic SN (%) SP (%) ACC (%)
Relief
75.84 93.88
91.55
CFS
75.41 93.81
91.43
Fisher Score
73.88 93.49
90.94
Gini Index
73.50 93.36
90.78
SFS
74.66 93.42
91.01
SBS
74.97 93.40
91.04
Common Features f5 , Hu1 70.78 92.65
89.86

As shown from table 2, there’s slight difference between relief and CFS heuristics, which is expected since they intersect in five common features according
to table 1. Also, a higher difference between all heuristics is in sensitivity measure than in specificity measure, which means that all recommended features subsets are capable of discriminating vessels pixels more than non-vessels pixels.
The current six-feature subset recommended by CFS gives better performance
(SN=75.41%, SP=93.81% and ACC=91.43%) than the previous eight-feature subset recommended by CFS, in the previous work [1] (SN=73.88%, SP=92.66% and
ACC=90.25%). That’s due to applying different samples selection technique.
Table 3 shows the computation time of each features subset recommended by
each heuristic. As illustrated, there’s no significant difference among them and the
features computation for each recommended features subset takes about one minute
and half on PC with Intel Core-i3 CPU at 2.53 GHz and 3 GB of RAM. The features
subsets of SFS and SBS takes the lowest computation time, since their features are
the fewest and the green gray-level that isn’t computed is one of their features. The
features subsets of fisher score and gini index takes the longest computation time,

8

Ahmed.H.Asad, Ahmad Taher Azar, Nashwa El-Bendary, Aboul Ella Hassaanien

Fig. 1 Segmentation performance of ACS with the features subset recommended by each heuristic

because they contain more Hu moment-invariants based features that take more time
in computation than gray-level based features and they are computed on two stages.
Although this slight difference between these two groups of features in computation,
but both take lower computation time when compared against other features used in
retinal blood vessels segmentation. That’s because both groups are needn’t to be
computed at multiple scales or orientations.
Table 3 Computation Time of each features subset recommended by feature selection heuristics
Features Selection Heuristic Relief CFS Fisher Score Gini Index SFS SBS
Computation Time in Seconds 90
91
92
92
89 88

5 Conclusions and Future Works
The automatic segmentation of blood vessels is an approach for pixels classification
that is based on the computation of many features from the retinal image. The large
number of computed features increases the classification complexity and time and
reduces its accuracy, so features selection is an essential step for successful classification. This article has evaluated six features selection heuristics to select the best
relevant features subset from feature vector consisting of fourteen features. The features are computed for each pixel in the FOV of retinal image in DRIVE database
for blood vessels segmentation by ACS. The results indicated that the recommended

Ant Colony based Feature Selection Heuristics for Retinal Vessel Segmentation

9

features subset by the relief heuristic gives the best segmentation performance with
sensitivity of 75.84%, specificity of 93.88% and accuracy of 91.55%.
For future work, there are three concurrent directions for improving the accuracy
of ACS-based segmentation: the first one is via adding other new features that are
as easy to compute as the current features. The second direction is via evaluating
other features selection heuristics in order to obtain better features subsets. Finally,
the third direction is through applying the segmentation approach, proposed in this
article, on other retinal images databases.

References
1. Asad, A.H., Azar, A.T., Hassanien, A.E.: Ant Colony-based System for Retinal Blood Vessels
Segmentation. Proceedings of the 7th International Conference on Bio-Inspired Computing:
Theories and Application (BIC-TA 2012), Gwalior, India, pp. 441–452, (2012) .
2. Vijayakumari V., Suriyanarayanan N.: Survey on the Detection Methods of Blood Vessel in
Retinal Images. Eur. J. Sci. Res. vol. 68, no. 1, pp. 83–92, (2012).
3. Serrarbassa P.D., Dias A.F., Vieira M.F.: New concepts on diabetic retinopathy: neural versus
vascular damage. Arq Bras Oftalmol, vol. 71, no. 3, pp. 459–63, (2008).
4. Soares J.V., Leandro J.J., Cesar Jnior R.M., Jelinek H.F., Cree M.J.: Retinal vessel segmentation
using the 2-D Gabor wavelet and supervised classification. IEEE Trans Med Imaging. vol. 25,
no. 9, pp. 1214–22, (2006).
5. Mendonca A.M., Campilho A.: Segmentation of retinal blood vessels by combining the detection of centerlines and morphological reconstruction. IEEE Trans. Med. Imaging 25(9),
pp. 1200–1213, (2006).
6. Staal J.J., Abramoff M.D., Niemeijer M., Viergever M.A., Ginneken B. V.: Ridge based vessel
segmentation in color images of the retina. IEEE Transactions on Medical Imaging. vol. 23,
no. 4, pp. 501–509, (2004).
7. Leung H., Wang J.J., Rochtchina E., Wong T.Y., Klein R., Mitchell P.: Impact of current and
past blood pressure on retinal arteriolar diameter in an older population. J Hypertens. vol. 22,
no, 8, pp. 1543–9, (2004).
8. Wang J.J., Taylor B., Wong T.Y., Chua B., Rochtchina E., Klein R., Mitchell P.: Retinal vessel diameters and obesity: a population-based study in older persons. Obesity (Silver Spring).
vol. 14, no. 2, pp. 206–14, (2006).
9. Mitchell P., Leung H., Wang J.J., Rochtchina E., Lee A.J., Wong T.Y., Klein R.: Retinal vessel
diameter and open-angle glaucoma: the Blue Mountains Eye Study. Ophthalmology. vol. 112,
no. 2, pp. 245–50, (2005).
10. Foracchia M., Grisan E., Ruggeri A.: Extraction and quantitative description of vessel features
in hypertensive retinopathy fundus images. Proceedings of: Book Abstracts 2nd International
Workshop on Computer Assisted Fundus Image Analysis (CAFIA-2), Copenhagen, Denmark,
pp. 6, (2001).
11. Morello C.M.: Etiology and natural history of diabetic retinopathy: an overview. Am J Health
Syst Pharm. vol. 64, no. 17 Suppl. 12, pp. S3–7, (2007).
12. Xu J., Hu G., Huang T., Huang H., Chen B.: Using multifocal ERG responses to discriminate
diabetic retinopathy. Doc Ophthalmol. vol. 112, no. 3, pp. 201–207, (2006).
13. Jin X., Guangshu H., Tianna H., Houbin H., Bin C.: The Multifocal ERG in Early Detection
of Diabetic Retinopathy. Proceedings of IEEE Engineering in Medicine and Biology Society
Conference, United States, vol. 7, pp. 7762-5, (2005).
14. Fraz M.M., Remagnino P., Hoppe A., Uyyanonvara B., Rudnicka A.R., Owen C.G., Barman
S.A.: Blood vessel segmentation methodologies in retinal images–a survey. Comput Methods
Programs Biomed. vol. 108, no. 1, pp. 407–33, (2012).

10

Ahmed.H.Asad, Ahmad Taher Azar, Nashwa El-Bendary, Aboul Ella Hassaanien

15. Khan M.I., Shaikh H., Mansuri A.M.: A Review of Retinal Vessel Segmentation Techniques
and Algorithms. Int. J. Comp. Tech. Appl. vol. 2, no. 5, pp. 1140–1144, (2011).
16. Dorigo M., Gambardella L.M.: Ant colony system: a cooperative learning approach to the
traveling salesman problem. IEEE Trans. Evol. Comput. vol. 1, no. 1, pp. 53–66, (1997).
17. Marin D., Aquino A., Gegundez-Arias M.E., Bravo J.M.: A New Supervised Method for
Blood Vessel Segmentation in Retinal Images by Using Grey-Level and Moment InvariantsBased Features. IEEE Trans Med Imaging. vol. 30, no. 1, pp. 146–58, (2011).
18. Hu M.K.: Visual Pattern Recognition by Moment Invariants. IRE Trans. Inform. Theory.
vol. 8, no. 2, pp. 179–187, (1962).
19. Hua J.P., Tembe W.D., Dougherty E.R.: Performance of feature-selection methods in the classification of high-dimension data. Pattern Recognition, vol. 42, no. 3, pp. 409–424, (2009).
20. Blum A., Langley P.: Selection of relevant features and examples in machine learning. Artificial Intelligence. vol. 97, no. 1-2, pp. 245–271, (1997).
21. Talavera L.: An evaluation of filter and wrapper methods for feature selection in categorical
clustering. Proceeding of 6th International Symposium on Intelligent Data Analysis, Madrid,
Spain, pp. 440–451, (2005).
22. Hall M.A.: Correlation-based Feature Selection for Discrete and Numeric Class Machine
Learning. Proceedings of the Seventeenth International Conference on Machine Learning
(ICML’00), Stanford, CA, USA, pp. 359–366, (2000).
23. Hall M.A., Smith L.A.: Feature Selection for Machine Learning: Comparing a CorrelationBased Filter Approach to the Wrapper. Proceedings of the 12th International Florida Artificial
Intelligence Research Society Conference, Orlando, Florida, USA, pp. 235–239, (1999).
24. Bishop D.V.M., North T., Donlan C.: Nonword repetition as a behavioural marker for inherited
language impairment: Evidence from a twin study. Journal of Child Psychology and Psychiatry.
vol. 37, pp. 391–403, (1996).
25. Shang W, Huang H, Zhu H, Lin Y, Qu Y, Wang, Z: A novel feature selection algorithm for
text categorization. Journal of Expert Syst. Appl., vol. 33, no. 1, pp. 1–5, (2007).
26. Gini, C.: On the Measure of Concentration with Special Reference to Income and Statistics.
Colorado College Publication, General Series, no. 208, pp. 73–79, (1936).
27. Kira K., Rendell L.A.: A practical approach to feature selection. Proceedings of 9th International Conference on Machine Learning, Aberdeen, Scotland, pp. 249–256, (1992).
28. Whitney A.W.: A direct method of nonparametric measurement selection. IEEE Trans Computational. pp. 1100–1103, (1971).
29. Aha DW, Bankert R (1995) A comparative evaluation of sequential feature selection algorithms. In: proceeding fifth international workshop on artificial intelligence and statistics: 17.

