Computer Science Medical
Resume:
Kockara et al. BMC Bioinformatics ****, **(Suppl *):S26
http://www.biomedcentral.com/1471-2105/11/S6/S26
PROCEEDINGS Open Access
Analysis of density based and fuzzy c-means
clustering methods on lesion border extraction
in dermoscopy images
Sinan Kockara1*, Mutlu Mete2*, Bernard Chen1, Kemal Aydin3
From Seventh Annual MCBIOS Conference. Bioinformatics: Systems, Biology, Informatics and Computation
Jonesboro, AR, USA. 19-20 February 2010
Abstract
Background: Computer-aided segmentation and border detection in dermoscopic images is one of the core
components of diagnostic procedures and therapeutic interventions for skin cancer. Automated assessment tools
for dermoscopy images have become an important research field mainly because of inter- and intra-observer
variations in human interpretation. In this study, we compare two approaches for automatic border detection in
dermoscopy images: density based clustering (DBSCAN) and Fuzzy C-Means (FCM) clustering algorithms. In the first
approach, if there exists enough density greater than certain number of points- around a point, then either a new
cluster is formed around the point or an existing cluster grows by including the point and its neighbors. In the
second approach FCM clustering is used. This approach has the ability to assign one data point into more than
one cluster.
Results: Each approach is examined on a set of 100 dermoscopy images whose manually drawn borders by a
dermatologist are used as the ground truth. Error rates; false positives and false negatives along with true positives
and true negatives are quantified by comparing results with manually determined borders from a dermatologist.
The assessments obtained from both methods are quantitatively analyzed over three accuracy measures: border
error, precision, and recall.
Conclusion: As well as low border error, high precision and recall, visual outcome showed that the DBSCAN
effectively delineated targeted lesion, and has bright future; however, the FCM had poor performance especially in
border error metric.
Introduction Dermoscopy is the major non-invasive skin imaging
Melanoma is the fifth most common malignancy in the technique that is extensively used in the diagnosis of
United States and has rapidly become one of the leading melanoma and other skin lesions. Dermoscopy improves
cancers in the world. Malignant melanoma is the most upon simple photography by revealing more of the sub-
deadly form of skin cancer and the fastest growing skin surface structures underneath the skin, and is now
cancer type in the human body. 8,441 deaths out of widely used by dermatologists. The contact dermoscopy
68,720 incidences are estimated numbers in the United technique consists of placing fluid such as mineral oil,
States in 2009 [1]. If it is detected early, melanoma can water, or alcohol on the skin lesion that is subsequently
often be cured with a simple excision operation. inspected using a digital camera and a hand-held der-
moscopy attachment such as Dermlite. The fluid placed
* Correspondence: ********@***.***; **********@****-********.*** on the lesion eliminates surface reflection and renders
1
Computer Science Department, University of Central Arkansas, Conway, AR,
the cornified layer translucent; thus, allowing a better
USA
visualization of pigmented structures within the
2
Department of Computer Science, Texas A&M University-Commerce,
Commerce, TX, USA
Full list of author information is available at the end of the article
2010 Kockara and Mete; licensee BioMed Central Ltd. This is an open access article distributed under the terms of the Creative
Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and
reproduction in any medium, provided the original work is properly cited.
Kockara et al. BMC Bioinformatics 2010, 11(Suppl 6):S26 Page 2 of 11
http://www.biomedcentral.com/1471-2105/11/S6/S26
epidermis, the dermoepidermal junction and the superfi- Dermoscopy involves optical magnification of the
cial dermis. region-of-interest, which makes subsurface structures
For early detection of melanoma, finding lesion bor- more easily visible when compared to conventional
ders is the first and key step of the diagnosis since the macroscopic images [12]. This in turn improves screen-
border structure provides life saving information for ing characteristics and provides greater differentiation
accurate diagnosis. Currently, dermatologists draw bor- between difficult lesions such as pigmented Spitz nevi
ders manually which is described as tedious and time and small, clinically equivocal lesions [13]. However, it
consuming. That is where computer-aided border detec- has also been demonstrated that dermoscopy may actu-
tion of dermoscopy images comes in to the picture. ally lower the diagnostic accuracy in the hands of an
Detecting melanoma early is critical because the mela- inexperienced dermatologists [14]. Therefore, novel
noma not detected early can be fatal. Also, speed is cri- computerized image understanding frameworks are
tical because of a lack of dermatologists to screen all the needed to minimize the diagnostic errors that result
images. Thus, physician error increases with rapid eva- from the difficulty and subjectivity of visual interpreta-
luation of cases [2]. For these very reasons, automated tions [15,16].
systems would be a significant help for dermotologists. For melanoma investigation, delineation of region-of-
The proposed method in this study is a fully automated interest is the key step in the computerized analysis of
system. By fully automated authors mean that prior to skin lesion images for many reasons. First of all, the
and during the processing there is no human interven- border structure provides important information for
tion in the system. The purpose with this system is to accurate diagnosis. Asymmetry, border irregularity, and
increase dermotologist s comfort level with his/her deci- abrupt border cutoff are a few of many clinical features
sion; however, a dermatologist always constitutes the calculated based on the lesion border. Furthermore, the
final decision on the subject. extraction of other important clinical indicators such as
atypical pigment networks, globules, and blue-white vein
Background areas critically depends on the border detection [17].
Differentiating or partitioning objects from background The blue-white veil is described as an irregular area
or other objects on an image is called image segmenta- with blended blue pigment with a ground glass haze
tion. Solutions to the image segmentation have wide- (white), as if the image were out of focus.
spread applications in various fields; including medical At the first stage for analysis of dermoscopy images,
diagnosis and treatment. Plenty of methods have been automated border detection is usually being applied
generated for grayscale and color image segmentations [16]. There are many factors that make automated bor-
[3-6]. Four popular approaches [7] for image segmenta- der detection challenging e.g. low contrast between the
tion are: edge-based methods, threshold techniques [8], surrounding skin and the lesion, fuzzy and irregular
neighborhood-based techniques, graph-based methods lesion border, intrinsic artifacts such as cutaneous fea-
[9,10], and cluster-based methods. Edge based techni- tures (air bubbles, blood vessels, hairs, and black frames)
ques investigate discontinuities in image whereas neigh- to name a few [17]. According to Celebi et al. 2009 [17],
borhood-based methods examine the similarity automated border detection can be divided into four
(neighborhoods) among different regions. Threshold sections: pre-processing, segmentation, post-processing,
methods identify different parts of an image by combin- and evaluation. Pre-processing step involves color space
ing peaks and valleys of 1D or 3D histograms (RGB). transformations [18], [19], contrast enhancement [20]
Also, there exists numerous innovative graph-based [21], and artifacts removal [22], [23], [24-28]. Segmenta-
image segmentation approaches in the literature. Shi et tion step involves partitioning of an image into disjoint
al. 1997-1998 [9,10] treated segmentation as a graph regions [29], [28],[23]. Post-processing step is used to
partitioning problem, and proposed a novel unbiased obtain the lesion border [16], [30]. Evaluation step
involves dermatologists evaluations on the border detec-
measure for segregating subgroups of a graph, known as
the Normalized Cut criterion. More recently, Felzensz- tion results.
walb et al. [11] developed another segmentation techni- Regarding boundary of clusters, Lee and Castro [31]
que by defining a predicate for the existence of introduced a new algorithm of polygonization based on
boundaries between regions, utilizing graph-based repre- boundary of resulting point clusters. Recently Nosovskiy
sentations of images. In this study; however, we focus et al. [32] used another theoretical approach to find
on cluster-based segmentation methods. In cluster- boundary of clusters in order to infer accurate boundary
based methods, individual image pixels are considered between close neighboring clusters. These two works
as general data samples and assumed correspondence principally study boundaries of finalized data groups
between homogeneous image regions and clusters in the (clusters). Schmid et al. [23] proposed an algorithm
spectral domain. based on color clustering. First, a two-dimensional
Kockara et al. BMC Bioinformatics 2010, 11(Suppl 6):S26 Page 3 of 11
http://www.biomedcentral.com/1471-2105/11/S6/S26
histogram is calculated from the first two principal com-
ponents of the CIE L*u*v* color space. The histogram is
then smoothed and initial cluster centers are obtained
from the peaks using a perceptron classifier. At the final
step, the lesion image is segmented.
In this study for computer-aided border detection we
use two clustering algorithms density based clustering
(DBSCAN) [33] and multi level fuzzy C means cluster-
ing (FCM) and compare their performances over dermo-
Figure 1 Direct density reachable (left) and density reachable
scopy images for border detection. In the context of
property of DBSCAN (right).
dermoscopic images, clustering corresponds to finding
whether each pixel in an image belongs to skin lesion
border or not. Automatic border detection makes der- the cluster (border pixels). As expected, a neighborhood
matologist s tedious manual border drawing procedure query for a border pixel returns notably less points than
faster and easier. a neighborhood query of a core pixel. Thus, in order to
include all points belonging to the same segment, we
DBSCAN should set the minimum number of pixels (MinPxl) to a
With the aim of separating background from skin lesion comparatively low value. This value, however, would not
to target possible melanoma, we cluster pixels of thre- be characteristic for the respective cluster - particularly
sholded images by using DBSCAN. It takes a binary in the presence of negative pixels (non-cluster). There-
(segmented) image, and delineates only significantly fore, we require that for every pixel p in a cluster C
important regions by clustering. The expected outcome there is a pixel q in C so that p is inside of the Eps-
of this framework is desired boundary of the lesion in a neighborhood of q and NEps(q) contains at least MinPxl
dermoscopy image. pixels: NEps(p) MinPxl and dist(p, q) Eps. A pixel
Technically, it is appropriate to tailor density based p is called density-reachable from a pixel q when there
algorithm in which cluster definition guarantees that the is a chain of pixels p1, p2, .., pn, where p1 = q, pn = p.
number of positive pixels is equal to or greater than This is illustrated in Figure 1. A cluster C (segment) in
minimum number of pixels (MinPxl) in certain neighbor- image is a non-empty subset of pixels and given as:
hood of core points. The core point is that the neighbor-
C = {p q NEps(p) MinPxl,
hood of a given radius (Eps) has to contain at least a
where q is density reachable from p. DBSCAN centers
minimum number of positive pixels (MinPxl), i.e., the
around the key idea: to form a new cluster or grow an
density in the neighborhood should exceed pre-defined
existing cluster the Eps-neighborhood of a point should
threshold (MinPxl). The definition of a neighborhood is
contain at least a minimum number of points (MinPxl).
determined by the choice of a distance function for two
Algorithm 1 DBSCAN
pixels p and q, denoted by dist(p,q). For instance, when
the Manhattan distance is used in 2D space, the shape of DBSCAN (SubImage, Eps, Minpxl)
the neighborhood would be rectangular. Note that
DBSCAN works with any distance function so that an ClusterId:=nextId(NOISE);
appropriate function can be designed for some other spe- FOR I FROM 1 To SubImage.height DO
cific applications. DBSCAN is significantly more effective FOR I FROM 1 To SubImage.width DO
in discovering clusters of arbitrary shapes. It was success- Point := SubImage.get(i,j);
fully used for synthetic dataset as well as earth science, IF point.Cid = UNCLASSIFIED AND
and protein dataset. Theoretical details of DBSCAN are Point.positive = TRUE
given in [33]. Once the two parameters Eps and MinPxl THEN
are defined, DBSCAN starts to cluster data points (pixels) IF ExpandCluster(SubImage, Point,
from an arbitrary point q as illustrated in Figure 1. ClusterId, Eps, MinPxl)
Let I be a subimage that is of dimension N N. For a THEN
pixel p, let px and py denote its position where top-left ClusterId:=nextId(ClusterId)
corner is (0, 0) of I. Let cxy represent the color at (px, END IF;
p y ). The Eps-neighborhood of a pixel p, denoted by END IF;
NEps( p ), is defined by NEps( p ) = { q I dist ( p, q) END FOR;
Eps } where dist is Euclidean distance. There can be END FOR;
found two kinds of pixels in a cluster: 1) pixels inside of
the cluster (core pixels) and 2) pixels on the border of END DBSCAN;
Kockara et al. BMC Bioinformatics 2010, 11(Suppl 6):S26 Page 4 of 11
http://www.biomedcentral.com/1471-2105/11/S6/S26
A lgorithm 1 summarizes DBSCAN for image seg- the pixels with some colors can belong partially to the
mentation. Once the two parameters Eps and MinPxl background class and/or the skin lesion. The main
are defined, DBSCAN starts to cluster data points advantage of this method is that, it does not require a
from an arbitrary point q. It begins by finding the priori knowledge about number of objects in the
neighborhood of point q, i.e., all points that are image.
directly density reachable from point q. This neighbor- Fuzzy C-Means (FCM) clustering algorithm [34,35] is
hood search is called region query. For an image, we one of the most popular fuzzy clustering algorithms.
start with left-top pixel (not necessarily a corner pixel, FCM is based on minimization of the objective function
any arbitrary pixel can be chosen for first iteration) as Fm(u, c) [35]:
our first point in the dataset (subimage). We look for
n C
( uik )m d2 ( xk, ci )
Fm ( u, c ) =
first pixel satisfying the core pixel condition as a start-
k =1 i =1
ing (seed) point. If the neighborhood is sparsely popu-
lated, i.e. it has fewer than MinPxl points, then point q
FCM computes the membership u ij and the cluster
is labeled as a noise. Otherwise, a cluster is initiated
centers cj by:
and all points in neighborhood of point q are marked
by new cluster s ID. Next the neighborhoods of all q s 1
uij =
neighbors are examined iteratively to check if they can 2
xi c j m 1
be added into the cluster. If a cluster cannot be
C
expanded any more, DBSCAN chooses another arbi-
k =1 xi c k
trary unlabeled point and repeats processes to form
another cluster. This procedure is iterated until all
data points in the dataset have been labeled as noise
u .x
N
m
or with a cluster ID. Figure 2 illustrates example clus- ij i
i =1
=
cj
ter expansion.
u
N
m
ij
i =1
Fuzzy c-means clustering
where m, the fuzzification factor which is a weighting
Clustering, a major area of study in the scope of unsu-
exponent on each fuzzy membership, is any real number
pervised learning, deals with recognizing meaningful
greater than 1, uij is the degree of membership of xi in
groups of similar items. Under the influence of fuzzy
the cluster j, x i is the i th of d-dimensional measured
logic, fuzzy clustering assigns each point with a degree
data, cj is the dimension center of the cluster, d2(xk,ci) is
of belonging to clusters, instead of belonging to exactly
a distance measure between object xk and cluster center
one cluster.
c i, and is any norm expressing the similarity
In fuzzy event modeling, pixel colors in a dermo-
between any measured data and the center.
scopy image can be viewed as probability space where
Figure 2 Example Cluster Expanding: New points (green ones in circle) are expanding cluster.
Kockara et al. BMC Bioinformatics 2010, 11(Suppl 6):S26 Page 5 of 11
http://www.biomedcentral.com/1471-2105/11/S6/S26
The FCM algorithm involves the following steps: fuzzification factor m is taken as 2. Figure 3 shows how
FCM detected area (red region) is changed by the
1. Set values for c and m change in threshold.
2. Initial membership matrix U= [uij], which is U(0)
Experiments and results
( i = number of members, j = number of clusters)
3. At k-step: calculate the centroids for each cluster The proposed methods are tested on a set of 100 der-
through equation (2) if k 0. (If k=0, initial cen- moscopy images obtained from the EDRA Interactive
troids location by random) Atlas of Dermoscopy [12]. These are 24-bit RGB color
4. For each member, calculate membership degree images with dimensions ranging from 577 397 pixels
by equation (1) and store the information in U(k) to 1921 1285 pixels. The benign lesions include nevo-
5. If the difference between U(k) and U(k+1) less than cellular nevi and dysplastic nevi. The distance function
a certain threshold, then STOP; otherwise, return to used is Euclidean distance between pixels p and q, and
step 3.
( p.x q.x )2 + ( p.y q.y )2
given as d(p, q) = where p.x
and p.y denote position of pixel p at xth column and
In the FCM, the number of classes (c in equation 1) is
yth row with respect to top-left corner (0, 0) of image.
a user input. We tried to find the number of unclassified
We run DBSCAN on each image with the eps of 5 and
data points is greater than some threshold (T) values
MinPts of 60.
(30, 40, 50, 60, and 70) in our experiments. Since the
We evaluated the border detection errors of the
number of classes is a user input in FCM, there is a risk
DBSCAN and FCM by comparing our results with
of over segmentation. For instance when the number of
physician-drawn boundaries as a ground truth. Manual
segments in a skin image is 3 and we force the number
borders were obtained by selecting a number of points
of clusters to be found by FCM to be 6, the FCM over
on the lesion border, connecting these points by a sec-
segments the image. This was one of the principal chal-
ond-order B-spline and finally filling the resulting
lenges we encountered with FCM. Thus, we ran FCM
closed curve [22]. Using the dermatologist-determined
for different number of clusters and different threshold
borders, the automatic borders obtained from the
values and found that for the value of five initial clusters
DBSCAN and FCM are compared using three quanti-
and threshold value of 30, FCM gave good accuracy in
tative error metrics: border error, precision, and recall.
segmentation. Therefore, we used these values in all of
Border error is developed by Hance et al. [18] and
our experiments. Moreover, in all of our experiments
Figure 3 Overlay images of FCM with different threshold values a) 30, b) 40, c) 50, d) 60, e) 70.
Kockara et al. BMC Bioinformatics 2010, 11(Suppl 6):S26 Page 6 of 11
http://www.biomedcentral.com/1471-2105/11/S6/S26
agree on. FN and FP are labels for missed lesion and
erroneous positive regions, respectively. Addition to bor-
der error, we also reported precision (positive predictive
value) and recall (sensitivity) for each experimental
image in Table 1 and Table 2 for results generated with
DBSCAN and FCM respectively. Precision and recall are
TP TP
defined as respectively.
and
TP + FP TP + FN
Figure 4 An exemplary dermoscopy image (left) and corresponding
Note that all definitions runs for the number of pixels
dermatologist drawn border (right)
in the particular region. Analogously, Area function
returns the number of active pixels in a binary image.
currently the most important metric for assessing qual-
Table 1 gives border error, precision and recall rates
ity of any automatic border detection algorithm, and
generated from the DBSCAN for each image whereas
given by:
Table 2 represents border error, precision and recall
rates generated from the FCM. It can be seen that the
Area ( AutomaticBorder ManualBorder )
Border Error = 100, results vary significantly across the images.
Area ( ManualBorder )
In Figure 4, an exemplary dermoscopy image, which is
determined as melanoma, and its corresponding derma-
where AutomaticBorder is the binary image obtained
from DBSCAN or FCM, ManualBorder is the binary tologist drawn border are illustrated. Figure 6 illustrates
image obtained from a dermatologist (see Figure 4 right the DBSCAN generated result in red color for the same
side). Exclusive OR operator,, essentially emphasizes image. The DBSCAN generated result is overlaid on top
disagreement between target (ManualBorder) and pre- of the dermatologist drawn border image in black color.
dicted (AutomaticBorder) regions. Referring to informa- As seen from the figure, hair is detected as false positive.
tion retrieval terminology, numerator of the border Figure 3 shows results generated from the FCM with
error means summation of False Positive (FP) and False different fuzzification factors.
For example for the melanoma image given in Figure
Negative (FN). The denominator is obtained by adding
4, FCM s precision, recall, and border error rates are
True Positive (TP) to False Negatives (FN). An illustra-
99.4%, 75.4%, and 100.4% respectively; however,
tive example is given in Figure 5.
Regarding the image in Figure 5, assume that red is DBSCAN s precision, recall, and border error rates for
drawn by a dermatologist and blue is the automated the same image are 94%, 84%, and 2.2% respectively.
line, respectively. TP indicates correct lesion region Following tables show results generated with the
found automatically. Similarly, TN shows healthy region DBSCAN and the FCM for 100 image dataset
(background) both manual and computer assessment respectively.
Since the most important metric to evaluate perfor-
mance of a lesion detection algorithm is border error
metric, border errors for DBSCAN and FCM are illu-
strated in Figure 7. In the figure, X-axis show image IDs
in random order. As seen from Figure 7, DBSCAN out-
performs FCM for lesion border detection on dermo-
scopy images: for DBSCAN overall average border error
ratio is 6.94% whereas overall average border error ratio
for FCM is 100%. As for recall and precision, DBSCAN
and FCM averaged out 76.66% and 99.26%; 55% and
100%, respectively.
Automatically drawn boundaries usually found at
more intense regions of a lesion (see Figure 8a, 8b, 8c,
8e, 8f) having promising assessment with DBSCAN. In
Figure 8(d), the DBSCAN marked also outer regions.
Obviously, the gradient region between blue and red
boundaries seems to be a major problem for the
Figure 5 Illustration of components used in accuracy and error
DBSCAN. We believe that even though inter-dermatolo-
quantification.
gist agreement on manual borders is not perfect, most
Kockara et al. BMC Bioinformatics 2010, 11(Suppl 6):S26 Page 7 of 11
http://www.biomedcentral.com/1471-2105/11/S6/S26
Table 1 DBSCAN border error, precision, and recall measures for each image in the dataset
Img. ID Border Error Precision Recall Img. ID Border Error Precision Recall
1 8.2% 0.98 0.79 51 5.1% 1.00 0.81
2 8.0% 0.93 0.86 52 6.9% 1.00 0.80
3 4.9% 0.89 0.85 53 7.4% 1.00 0.78
4 6.2% 1.00 0.82 54 1.5% 1.00 0.95
5 5.4% 1.00 0.88 55 4.2% 1.00 0.88
6 4.6% 1.00 0.83 56 14.9% 1.00 0.60
7 3.9% 0.96 0.91 57 9.4% 1.00 0.77
8 3.2% 1.00 0.87 58 5.9% 1.00 0.82
9 3.4% 1.00 0.82 59 4.6% 1.00 0.75
10 2.2% 1.00 0.91 60 2.9% 1.00 0.81
11 0.9% 1.00 0.91 61 6.5% 0.90 0.74
12 6.5% 1.00 0.61 62 5.8% 1.00 0.74
13 10.0% 1.00 0.70 63 5.6% 1.00 0.77
14 14.8% 1.00 0.70 64 2.9% 1.00 0.82
15 5.9% 1.00 0.67 65 2.2% 0.94 0.84
16 6.8% 1.00 0.76 66 8.3% 0.89 0.79
17 6.0% 1.00 0.67 67 6.3% 0.98 0.83
18 4.0% 1.00 0.86 68 3.2% 1.00 0.79
19 6.4% 1.00 0.71 69 2.4% 1.00 0.79
20 8.0% 1.00 0.80 70 4.6% 1.00 0.74
21 8.8% 1.00 0.78 71 8.8% 1.00 0.71
22 12.6% 1.00 0.73 72 3.5% 0.94 0.84
23 8.6% 1.00 0.76 73 1.8% 0.99 0.86
24 9.0% 1.00 0.72 74 2.9% 1.00 0.90
25 5.7% 1.00 0.79 75 5.9% 1.00 0.71
26 33.9% 1.00 0.51 76 9.2% 1.00 0.74
27 9.0% 1.00 0.74 77 3.3% 1.00 0.72
28 8.0% 1.00 0.65 78 13.6% 1.00 0.61
29 10.6% 1.00 0.75 79 10.4% 1.00 0.71
30 11.3% 1.00 0.74 80 6.7% 1.00 0.65
31 9.7% 1.00 0.72 81 1.8% 1.00 0.65
32 10.8% 1.00 0.77 82 7.5% 1.00 0.82
33 3.3% 1.00 0.86 83 9.9% 1.00 0.54
34 4.2% 1.00 0.88 84 3.1% 1.00 0.74
35 2.7% 1.00 0.88 85 6.4% 1.00 0.79
36 6.0% 1.00 0.79 86 7.5% 0.98 0.79
37 4.0% 1.00 0.85 87 7.2% 1.00 0.73
38 8.0% 1.00 0.71 88 5.1% 1.00 0.59
39 3.4% 1.00 0.76 89 5.5% 0.91 0.82
40 3.6% 1.00 0.82 90 17.0% 1.00 0.56
41 8.0% 1.00 0.73 91 8.1% 1.00 0.61
42 3.2% 1.00 0.85 92 4.3% 1.00 0.89
43 7.3% 1.00 0.74 93 1.7% 1.00 0.93
44 17.7% 1.00 0.70 94 14.6% 1.00 0.66
45 3.6% 1.00 0.84 95 3.0% 1.00 0.68
46 5.2% 1.00 0.88 96 7.8% 1.00 0.75
47 2.5% 1.00 0.91 97 21.8% 1.00 0.66
48 3.0% 1.00 0.87 98 4.0% 1.00 0.85
49 10.9% 1.00 0.68 99 11.5% 1.00 0.65
50 12.0% 1.00 0.68 100 3.1% 1.00 0.66
Kockara et al. BMC Bioinformatics 2010, 11(Suppl 6):S26 Page 8 of 11
http://www.biomedcentral.com/1471-2105/11/S6/S26
Table 2 FCM border error, precision, and recall measures for each image in the dataset
Img. ID Border Error Precision Recall Img. ID Border Error Precision Recall
1 99% 1 0.635 51 99.9% 0.99 0.66
2 99.98% 1 0.65 52 132.5% 1 0.5
3 100% 1 0.62 53 69.93% 1 0.45
4 101% 1 0.54 54 100% 1 0.56
5 98% 1 0.66 55 89.47% 1 0.45
6 96% 1 0.55 56 108.13% 1 0.52
7 105% 1 0.645 57 96% 0.99 0.65
8 100% 1 0.66 58 105% 1 0.62
9 89% 1 0.7 59 100% 1 0.56
10 106% 1 0.7 60 78.32% 1 0.51
11 100% 1 0.79 61 96.82% 1 0.53
12 98% 1 0.35 62 106.83% 1 0.34
13 97% 1 0.45 63 100% 1 0.71
14 99% 1 0.76 64 103.33% 0.98 0.56
15 103% 1 0.23 65 101% 1 0.47
16 98% 1 0.63 66 96.86% 0.95 0.52
17 100% 1 0.2 67 100% 1 0.65
18 89% 1 0.54 68 106.83% 1 0.62
19 99% 1 0.33 69 99% 1 0.34
20 99.9% 1 0.67 70 106.67% 1 0.49
21 92.9% 1 0.65 71 102.3% 1 0.65
22 98% 1 0.71 72 99.9% 1 0.71
23 78.3% 1 0.56 73 123% 1 0.48
24 96.8% 1 0.45 74 105.3% 1 0.53
25 106% 1 0.5 75 103.6% 1 0.5
26 123% 1 0.65 76 98% 1 0.58
27 105.4% 1 0.56 77 106.8% 1 0.45
28 104.7% 1 0.59 78 107% 1 0.76
29 98% 0.99 0.501 79 89.3% 1 0.69
30 95% 1 0.63 80 96.8% 1 0.59
31 93.7% 1 0.34 81 100% 1 0.63
32 96.8% 1 0.49 82 102.3% 1 0.34
33 100% 1 0.53 83 103.3% 1 0.56
34 101% 1 0.43 84 100% 1 0.32
35 98% 1 0.39 85 100% 1 0.67
36 103% 1 0.65 86 89% 1 0.65
37 98% 1 0.62 87 106.6% 1 0.71
38 100% 1 0.6 88 99% 1 0.56
39 89% 1 0.46 89 106.8% 0.97 0.5
40 106.6% 1 0.48 90 118.4% 1 0.48
41 93.6% 1 0.54 91 98.3% 1 0.65
42 96.8% 1 0.59 92 99.6% 1 0.62
43 100% 1 0.57 93 122.4% 1 0.45
44 89% 1 0.63 94 100% 1 0.48
45 107% 1 0.76 95 106.6% 1 0.56
46 89.3% 1 0.64 96 93.6% 1 0.43
47 96.8% 1 0.45 97 96.8% 0.99 0.51
48 106.7% 1 0.48 98 100% 1 0.53
49 99% 1 0.56 99 89% 1 0.49
50 99.9% 1 0.59 100 107% 1 0.53
Kockara et al. BMC Bioinformatics 2010, 11(Suppl 6):S26 Page 9 of 11
http://www.biomedcentral.com/1471-2105/11/S6/S26
used a subset of 100 dermoscopy image dataset (90
images). Their image IDs might be different than our
image IDs even for the same image. Therefore, for now
the mean error rate is only indication we have as a
proof that DBSCAN is better than studies given in [17]
and [22].
Conclusion
In this study, we introduced two approaches for auto-
matic detection of skin lesions. First, a fast density based
algorithm DBSCAN is introduced for dermoscopy ima-
ging. Second, the FCM is used for lesion border detec-
tion. The assessments obtained from both methods are
quantitatively analyzed over three accuracy measures:
border error, precision, and recall. As well as low border
error, high precision and recall, visual outcome showed
that the DBSCAN effectively delineated targeted lesion,
Figure 6 Overlay image of DBSCAN.
and has bright future; however, the FCM had poor per-
formance especially in border error metric. The next
step, we will focus on at more details on intra-variability
dermatologists will draw borders approximately the red
and post-assessment during performance analysis of the
borders as shown in images of Figure 8. This is because
intelligent systems. Additionally, performance of
the reddish area just outside the obvious tumor border
DBSCAN will be evaluated over different polygon-union-
is part of the lesion.
ing algorithms. In terms of border errors, we plan to
We also made a rough comparison of the DBSCAN
develop model that are more sensitive to melanoma
with prior state of the art lesion border detection meth-
lesion. A thresholding method which is well-integrated
ods proposed by Celebi et. al 2008 [22] and 2009 [17].
with clustering rationale, such as the one described in
Comparisons showed that the mean error of DBSCAN
[36], will be preferred in the future because of unex-
(6.94%) is obviously less than their results. However, we
pected difference between precision and recall rates.
cannot make image by image comparison since they
Figure 7 Border errors generated by DBSCAN (red) and FCM (green)
Kockara et al. BMC Bioinformatics 2010, 11(Suppl 6):S26 Page 10 of 11
http://www.biomedcentral.com/1471-2105/11/S6/S26
Figure 8 Sample images showing assessments of the dermatologist (red), automated frameworks DBSCAN (blue) and FCM (green) introduced in
this study.
Published: 7 October 2010
Acknowledgements
This article has been published as part of BMC Bioinformatics Volume 11
Supplement 6, 2010: Proceedings of the Seventh Annual MCBIOS References
Conference. Bioinformatics: Systems, Biology, Informatics and Computation. 1. Jemal A, Siegel R, Ward E, Hao Y, Xu J, Murray T, Thun MJ: Cancer statistics.
The full contents of the supplement are available online at A Cancer Journal for Clinicians CA 2008, 59:225-249.
http://www.biomedcentral.com/1471-2105/11?issue=S6. 2. Levy P, Berk W, Compton S, King J, Sweeny P, Kuhn G, Bock B: Effect of
Rapid Patient Evaluation on the Rate and Type of Error Citation of
Author details Emergency Physicians. Annals of Emergency Medicine 2005, 46(3):108-109.
1
Computer Science Department, University of Central Arkansas, Conway, AR, 3. Pantofaru C, Hebert M: A Comparison of Image Segmentation Algorithms.
USA. 2Department of Computer Science, Texas A&M University-Commerce, Tech. report CMU-RI-TR-05-40 Robotics Institute, Carnegie Mellon University
Commerce, TX, USA. 3Computer Science Department, University of Arkansas 2005.
at Pine Bluff, Pine Bluff, AR, USA. 4. Pathegama M, G l : Edge-end pixel extraction for edge-based image
segmentation. Transactions on Engineering, Computing and Technology
Authors contributions 130*-****-****, 2:213-216.
SK and MM have made equal contributions to this study. Both of the 5. Pal NR, Pal SK: A review of image segmentation techniques. Pattern
authors participated in the overall design of the study. MM designed the Recogn 1993, 26(9):1277-1294.
density-based algorithms. SK developed the general comparison testbed, 6. Skarbek W, Koschan A: Colour image segmentation a survey. Technical
performed data analysis, algorithm testing, statistical measurements, and report. Institute for Technical Informatics Technical University of Berlin 1994
benchmarking. BB designed and implemented the FCM. KA integrated it to [http://citeseer.nj.nec.com/skarbek94colour.html], October 1994.
the general framework. SK and MM contributed to the writing of this 7. Sezgin M, Sankur B: Image thresholding techniques: Quantitative
manuscript. All of the authors read and approved the final manuscript. performance evaluation. Journal of Electronic Imaging 2004, SPIE.
8. Shapiro LG, Stockman GC: Computer Vision,. New Jersey, Prentice-Hall0-13-
Competing interests 030***-*-****, 279-325.
The authors declare that they have no competing interests in regards to this 9. Shi J, Belongie S, Leung T, Malik J: Image and Video Segmentation: The
study. Normalized Cut Framework. Proc. of 1998 Int l Conf. on Image Processing
(ICIP 98) Chicago, IL 1998, 1:943-947.
Kockara et al. BMC Bioinformatics 2010, 11(Suppl 6):S26 Page 11 of 11
http://www.biomedcentral.com/1471-2105/11/S6/S26
10. Jianbo S, Malik J: Normalized cuts and image segmentation. IEEE Trans. on 36. Celebi ME, Iyatomi H, Schaefer G, Stoecker WV: Approximate Lesion
Pattern Analysis and Machine Intelligence 2000, 22(8):888-905. Localization in Dermoscopy Images. Skin Res Technol 2009, 15(3):314-322.
11. Felzenszwalb PF, Huttenlocher DP: Efficient graph-based image
doi:10.1186/147*-****-**-S6-S26
segmentation. International Journal of Computer Vision 2004, 59(2):167-181.
Cite this article as: Kockara et al.: Analysis of density based and fuzzy c-
12. Argenziano G, Soyer HP, De Giorgi V: Dermoscopy: A Tutorial. EDRA
means clustering methods on lesion border extraction in dermoscopy
Medical Publishing & New Media 2002.
images. BMC Bioinformatics 2010 11(Suppl 6):S26.
13. Steiner K, Binder M, Schemper M, Wolff K, Pehamberger H: Statistical
evaluation of epiluminescence dermoscopy criteria for melanocytic
pigmented lesions. Journal of the American Academy of Dermatology 1993,
29(4):581-588.
14. Binder M, Schwarz M, Winkler A, Steiner A, Kaider A, Wolff K,
Pehamberger H: Epiluminescence Microscopy: a Useful Tool For The
Diagnosis Of Pigmented Skin Lesions For Formally Trained
Dermatologists. Archives Of Dermatology 1995, 131(3):286-291.
15. Fleming MG, Steger C, Zhang J, Gao J, Cognetta AB, Pollak I, Dyer CR:
Techniques for a structural analysis of dermatoscopic imagery. Comput
Med Imaging Graph 1998, 22(5):375-389.
16. Celebi ME, Aslandogan YA, Stoecker WV, Iyatomi H, Oka H, Chen X:
Unsupervised Border Detection in Dermoscopy Images. Skin Res Technol
2007, 13(4):454-462.
17. Celebi ME, Iyatomi H, Schaefer G, Stoecker WV: Lesion Border Detection in
Dermoscopy Images. Comput Med Imaging Graph 2009, 33(2):148-153.
18. Hance GA, Umbaugh SE, Moss RH, Stoecker WV: Unsupervised color image
segmentation with application to skin tumor borders. IEEE Engineering in
Medicine and Biology 1996, 15(1):104-11.
19. Pratt WK: Digital image processing: PIKS inside. Hoboken, NJ: John Wiley
& Sons 2007.
20. Carlotto MJ: Histogram Analysis Using a Scale-Space Approach. IEEE
Transaction on Pattern Analysis and Machine Intelligence 1987, 1(9):121-129.
21. Delgado D, Butakoff C, Ersboll BK, Stoecker WV: Independent histogram
pursuit for segmentation of skin lesions. IEEE Trans on Biomedical
Engineering 2008, 55(1):157-61.
22. Celebi ME, Kingravi HA, Iyatomi H, et al: Border Detection in Dermoscopy
Images Using Statistical Region Merging. Skin Res Technol 2008,
14(3):347-353.
23. Schmid P: Segmentation Of Digitized Dermoscopic Images by Two-
Dimensional Color Clustering. IEEE Transaction on Medical Imaging 1999,
18:164-171.
24. Geusebroek J-M, Smeulders AW, van deWeijer MJ: Fast anisotropic gauss
filtering. IEEE Trans on Image Processing 2003, 12(8):938-43.
25. Perreault S, H bert P: Median filtering in constant time. IEEE Trans on
Image Processing 2007, 16(9):2389-94.
26. Lee TK, Ng V, Gallagher R: Dullrazor: A software approach to hair removal
from images. Comput Biol Med 1997, 27(6):533-543.
27. Zhou H, Chen M, Gass R, et al: Feature-preserving artifact removal from
dermoscopy images. Proceedings of the SPIE medical imaging 2008
conference 2008, 6914:69141B-69141B-9.
28. Wighton P, Lee TK, Atkins MS: Dermoscopic hair disocclusion using
inpainting. Proceedings of the SPIE medical imaging 2008, Conference
6914:691427-691427-8.
29. Sonka M, Hlavac V, Boyle R: Image processing, analysis, and machine
vision. Cengage-Engineering 2007.
30. Melli R, Grana C, Cucchiara R: Comparison of color clustering algorithms
for segmentation of dermatological images. Proceedings of the SPIE
medical imaging 2006 Conference 2006, 3S1-9S39.
31. Lee I, Estivill-Castro V: Polygonization of Point Clusters Through Cluster
Boundary Extraction For Geographical Data Mining. Proceedings of the
10th International Symposium on Spatial Data Handling 2002, 27-40.
Contact this candidate