Description
2 Background
The purpose of this assignment is to use thresholding to solve a segmentation problem and to practice
some basic segmentation performance evaluation methods.
2.1 Assignment Synposis
The dataset of this assignment consists of images of leaves on a cluttered background. You’ll design an
algorithm based on thresholding suited to this dataset. You’ll implement three different segmentation
performance measures and use them to evaluate the performance of your segmentation algorithm on this
dataset.
2.2 Images
Download the archive original.zip. This archive contains 30 colour images of leaves against various
backgrounds. You will notice that there are images of three different classes (shapes) of leaves. The first
class has image numbers between 1 and 19; the second class are in the files numbered 78 through 113; and
the third class is in the images numbered between 132 and 175.
Download segmented.zip which is a set of binary images representing the “ground truth” for each of
the 30 images in original.zip. These binary images will be treated as the “right answer” when performing segmentation validation. White pixels denote the pixels that your segmentation algorithm should add
to the leaf region. Note: even ground truth information is rarely 100% correct due to differences in the
way different humans interpret different images. The situation is no different with the data that I have
given you – the provided ground truths are close, but not perfect. But you treat it as the correct answer
anyways because it’s the best that you have.
2.3 Segmentation Validation and Performance Measures
When you develop a segmentation algorithm an important question is “how well does the algorithm perform?”. This is known as segmentation validation. We will have (or maybe already have had) a lecture on
this topic, but in any case, what is written here suffices for this assignment. The quality of the segmentation is measured by comparing the segmented regions produced by the segmentation algorithm to their
“ground truth”, that is, manually determined segmentations which are the regions that we are hoping the
segmentation algorithm will produce. One method of measuring segmentation quality for segmentation
validation is the Dice similarity coefficient (DSC). Let A be the set of pixels corresponding to the region
automatically determined by your segmentation algorithm. Let G be the set of pixels in the corresponding
ground truth region. The Dice similarity coefficient is defined as follows:
DSC(A, G) = 2|A ∩ G|
|A| + |G|
This is the ratio of twice the area of (i.e. – number of pixels in) the region comprised of the overlap of
regions A and G to the sum of the areas of the two regions. This ratio ranges from 0.0 to 1.0. A Dice
coefficient of 0.0 indicates that A and G are disjoint and do not overlap; a Dice coefficient of 1.0 indicates
that A = G. Thus, values closer to 1.0 indicate a better quality segmentation.
Another way of measuring segmentation quality is with the mean squared distance (MSD) of the
segmented boundary from the ground truth boundary. Let A be the points on the segmented boundary,
and G be the points on the ground truth boundary. The mean squared distance is:
MSD(A, G) = ∑a∈A
ming∈G d
2
(a, g)
M
where M is the number of points in A and d(a, b) is the Euclidean distance between points a and b. In
other words, find the shortest squared distance between each point in A and any point in G, and take the
average of these shortest distances.
The MSD is normally used together with the Hausdorff distance (HD) to characterize segmentation
quality because HD is the maximum deviation of the segmented boundary from the ground truth. While
the mean deviation of the contour from the ground truth could be relatively low, there could be a few
points that are a lot further away from the contour than the mean. So the Hausdorff distance measure
complements the MSD. The HD is defined as:
HD(A, G) = max
max
a∈A
min
g∈G
d(a, g), max
g∈G
min
a∈A
d(g, a)
where A, G, and d are defined as for MSD. In other words this is the larger of the largest shortest distance
from a point in A to any point in G and the largest shortest distance from a point in G to any point in A.
Page
3 Problems
Question 1 ( points):
Detailed instructions are provided asn3-q1.ipynb. Sample outputs are given below.
DSC for image_0001 . png : 0.998710905737
MSD for image_0001 . png : 0.135073779796
HD for image_0001 . png : 6.32455532034
————————————————–
DSC for image_0002 . png : 0.998759405593
MSD for image_0002 . png : 0.0851565129586
HD for image_0002 . png : 4.0
————————————————–
DSC for image_0005 . png : 0.99875911561
MSD for image_0005 . png : 0.10686482661
HD for image_0005 . png : 2.82842712475
————————————————–
DSC for image_0007 . png : 0.998298494372
MSD for image_0007 . png : 17.6741134752
HD for image_0007 . png : 41.0121933088
————————————————–
DSC for image_0009 . png : 0.998697842229
MSD for image_0009 . png : 0.407928862542
HD for image_0009 . png : 12.0415945788
————————————————–
DSC for image_0010 . png : 0.998975684706
MSD for image_0010 . png : 0.0625925925926
HD for image_0010 . png : 1.41421356237
————————————————–
DSC for image_0011 . png : 0.99928954337
MSD for image_0011 . png : 0.0436766623207
HD for image_0011 . png : 2.0
————————————————–
DSC for image_0015 . png : 0.998100089207
MSD for image_0015 . png : 25.2115167482
HD for image_0015 . png : 57.0
————————————————–
DSC for image_0018 . png : 0.998344127406
MSD for image_0018 . png : 0.110636784063
HD for image_0018 . png : 3.16227766017
————————————————–
DSC for image_0019 . png : 0.998629161154
MSD for image_0019 . png : 0.0858676207513
HD for image_0019 . png : 3.0
————————————————–
DSC for image_0078 . png : 0.99925925457
MSD for image_0078 . png : 0.0776203966006
HD for image_0078 . png : 2.0
————————————————–
DSC for image_0080 . png : 0.998934666162
MSD for image_0080 . png : 0.22232601588
Page 3
HD for image_0080 . png : 6.0
————————————————–
DSC for image_0089 . png : 0.995156760863
MSD for image_0089 . png : 1.05882352941
HD for image_0089 . png : 9.05538513814
————————————————–
DSC for image_0090 . png : 0.99454017084
MSD for image_0090 . png : 4.32594936709
HD for image_0090 . png : 19.2353840617
————————————————–
DSC for image_0099 . png : 0.998766937197
MSD for image_0099 . png : 0.0922473012758
HD for image_0099 . png : 3.0
————————————————–
DSC for image_0100 . png : 0.998576509067
MSD for image_0100 . png : 0.186046511628
HD for image_0100 . png : 3.60555127546
————————————————–
DSC for image_0104 . png : 0.998037495382
MSD for image_0104 . png : 3.26882745472
HD for image_0104 . png : 14.1421356237
————————————————–
DSC for image_0105 . png : 0.99829990181
MSD for image_0105 . png : 3.3579730358
HD for image_0105 . png : 18.0277563773
————————————————–
DSC for image_0110 . png : 0.997898365188
MSD for image_0110 . png : 0.207920792079
HD for image_0110 . png : 3.60555127546
————————————————–
DSC for image_0113 . png : 0.997091237945
MSD for image_0113 . png : 0.241970963484
HD for image_0113 . png : 4.0
————————————————–
DSC for image_0132 . png : 0.998610508802
MSD for image_0132 . png : 0.15680684248
HD for image_0132 . png : 4.472135955
————————————————–
DSC for image_0160 . png : 0.998741249875
MSD for image_0160 . png : 0.185489902767
HD for image_0160 . png : 4.0
————————————————–
DSC for image_0161 . png : 0.998819324002
MSD for image_0161 . png : 0.108187134503
HD for image_0161 . png : 1.41421356237
————————————————–
DSC for image_0162 . png : 0.998533120169
MSD for image_0162 . png : 0.138584974471
HD for image_0162 . png : 2.0
————————————————–
DSC for image_0163 . png : 0.998976698931
Page 4
MSD for image_0163 . png : 0.089364844904
HD for image_0163 . png : 2.0
————————————————–
DSC for image_0165 . png : 0.998562902599
MSD for image_0165 . png : 0.132188200149
HD for image_0165 . png : 2.0
————————————————–
DSC for image_0166 . png : 0.99899770586
MSD for image_0166 . png : 0.108825481088
HD for image_0166 . png : 3.60555127546
————————————————–
DSC for image_0171 . png : 0.997679226972
MSD for image_0171 . png : 0.227767114523
HD for image_0171 . png : 5.0
————————————————–
DSC for image_0174 . png : 0.998673663572
MSD for image_0174 . png : 0.196483180428
HD for image_0174 . png : 4.472135955
————————————————–
DSC for image_0175 . png : 0.998448382262
MSD for image_0175 . png : 0.17337883959
HD for image_0175 . png : 4.24264068712
————————————————–
The mean Dice coefficient was : 0.998305615048
The std . deviation of Dice coefficient was : 0.00103013053067
The mean MSD was : 1.94934032493
The std . deviation of MSD was : 5.40515206376
The mean HD was : 8.28872342473
The std . deviation of HD was : 11.9692827962
100% of leaves were recognized .
The grading rubric is given in Appendix A.
Note there are some points for how well your algorithm performs. You should be able to achieve at a
mean DSC of at least 0.7 fairly trivially – this is the bare minimum we are expecting for accuracy and
will earn you only half of these “accuracy marks”. For full “correctness” marks for you will need to
obtain a mean DSC of at least 0.9. You will still get most of the marks for achieving a mean DSC of at
least 0.8.
Page 5
4 Files Provided
asn3-qX.ipynb: These are iPython notebooks, one for each question, which includes instructions and in
which you will do your assignment.
images.zip: Original images to be segmented.
groundtruth.zip: Binary ground truth images.
5 What to Hand In
Hand in your completed iPython notebooks, one for each question.
6 Appendix A — Grading Rubric
Grading rubric is available on Moodle.
Page 6
