ABSTRACT
this dissertation a Clonal Selection Algorithm (CSA) based system that detected multiple
instances of circles, quadrilaterals and triangles in an image scene was developed. CSA models
how B-cell antibodies of the immune system protect the body from invading antigens. The
developed system eliminated the need for separate implementations of the CSA for detecting
the different shapes in an image. The implementation of the system was done using MATLAB
2015a, the edges and corners in the image scene were first extracted using Canny edge and
Harris corner detectors and the edge-only image was used as the antigen. A candidate solution
was formed by random selection of three (3) edge points to form a circle, four (4) corner points
to form a quadrilateral and three (3) corner points to form a triangle. The CSA iterated until
either an optimal solution (fitness of 1.0) is attained or when a maximum of 100 iterations is
reached. The antibodies with high fitness (above the set threshold of 0.9 on synthetic images
and 0.5 on real images) were then analysed using a distinctness factor to detect all instances of
the desired shapes and eliminate duplicate detections. A repository of five (5) synthetic images
generated with MATLAB 2015a and six (6) real images captured with digital camera were
used to test the performance of the algorithm. Simulation results showed sub pixel accuracy
with Mean Absolute Error (MAE) between 0.44 and 0.52, Mean Squared Error (MSE) between
0.4722 and 0.5208 and Peak Signal to Noise Ratio (PSNR) between 56.9233 and 57.2381 on
the synthetic test images. False Positive Rate (FPR) of 0% and False Negative Rate (FNR) of
3% were gotten on the synthetic images while the FPR and FNR on real images were 4.76% and
3.82% respectively. The implemented CSA had a mean error score of 0.14 for circle detection
compared to 0.36 and 0.34 for Circle CSA and Learning Automata (LA) representing 61.11%
and 58.82% improvements respectively.
TABLE OF CONTENTS
TITLE PAGE i
DECLARATION ii
CERTIFICATION iii
DEDICATION iv
ACKNOWLEDGEMENT v
ABSTRACT vi
LIST OF FIGURES xii
LIST OF TABLES xiii
LIST OF ABBREVIATIONS xiv
CHAPTER ONE INTRODUCTION 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Aim and Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.6 Dissertation Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
CHAPTER TWO LITERATURE REVIEW 7
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Review of Fundamental Concepts . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.1 Definition of shapes to be detected . . . . . . . . . . . . . . . . . . . . 7
2.2.2 Midpoint Line Algorithm (MLA) . . . . . . . . . . . . . . . . . . . . 9
2.2.3 Midpoint Circle Algorithm (MCA) . . . . . . . . . . . . . . . . . . . 10
2.2.4 Canny edge detector . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.5 Harris corner detector . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.6 Gaussian filtering of images . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.7 Artificial Immune System (AIS) . . . . . . . . . . . . . . . . . . . . . 12
2.2.8 Performance evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Review of Similar Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
CHAPTER THREE MATERIALS AND METHODS 27
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Test Images Repository . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.1 Generating synthetic images with MATLAB . . . . . . . . . . . . . . 28
3.2.2 Acquisition of real images . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3 Preprocessing Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.1 Creating edge image and edge map . . . . . . . . . . . . . . . . . . . 32
3.3.2 Creating corner image and corner map . . . . . . . . . . . . . . . . . . 33
3.4 Implementation of the CSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4.1 Antibody representation . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4.2 Collinearity check . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.3 Vertex arrangement for quadrilateral . . . . . . . . . . . . . . . . . . . 38
vii
3.4.4 Fitness calculation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.5 Implementation of the CSA algorithmic steps . . . . . . . . . . . . . . 39
3.5 Extraction of all Distinct Shapes Detected . . . . . . . . . . . . . . . . . . . . 43
3.5.1 Fitness threshold . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.5.2 Distinctness factor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.5.3 Drawing detected shapes . . . . . . . . . . . . . . . . . . . . . . . . . 46
CHAPTER FOUR RESULTS AND DISCUSSION 47
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2 Detecting Desired Shapes on Synthetic Images . . . . . . . . . . . . . . . . . 47
4.2.1 Detecting circles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.2.2 Detecting triangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2.3 Detecting quadrilaterals . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.2.4 Detecting multiple shapes . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3 Detecting Shapes on Real Images . . . . . . . . . . . . . . . . . . . . . . . . . 56
CHAPTER FIVE SUMMARY, CONCLUSION AND RECOMMENDATIONS 62
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.2 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.3 Problems Encountered . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.4 Significant Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.6 Recommendations for Future Work . . . . . . . . . . . . . . . . . . . . . . . . 63
APPENDICES 71
CHAPTER ONE
INTRODUCTION
1.1 Background
The detection of objects and shapes is an important research area in image analysis, attracting
a large number of publications yearly. The successful detection and classification of shapes has
been applied for automatic detection of road signs, inspection of manufactured products, aided
vectorization of drawings, target detection and many other applications (Cuevas et al., 2012a,
Jiang, 2012, Akinlar and Topal, 2013, Li, 2014). Object or shape detection involves searching
images for objects or shapes of interest in order to extract high-level information from the scene
under analysis (Ramirez et al., 2011). The images are usually fed into the system via cameras,
after which the system or algorithm analyses the image to extract relevant information from it
(i.e. the presence or absence of a desired object or shape).
An algorithm for detecting shapes/objects in a scene is considered efficient (Akinlar and Topal,
2013) if it:
1. is able to detect multiple instances of the object(s) of interest in an image;
2. is robust, detecting occluded or overlapping shapes, that is partially complete image of
the desired shape;
3. discriminates between the various shapes present in the image;
4. is robust to noise, being able to detect the presence of the desired object(s) in the presence
of noise;
5. is able to perform its task with little memory requirement, at least the relationship between
image size or dimension and memory requirement should be linear and not exponential;
6. is fast, able to detect the presence or absence of object(s) of interest in real time if possible.
1
Object detection can broadly be classified into detection of non-geometric and geometric shapes.
a) Detection of objects with non-geometric shapes
This involves detection of objects whose physical shape cannot be analysed geometrically.
Example of such objects include features like maps, mountains and trees. Detecting
such shapes or objects can be infeasible using geometrical analysis. It is best
detected using template matching, where an algorithm is trained to detect a template of
the real object. The effectiveness of the algorithm is then tested by presenting test images
of these objects to it. Another strategy is to break down the image of the object into
smaller shapes or features that are characteristic to the particular object and training the
algorithm to detect these smaller features. When presented with an image, the algorithm
searches for these features in the image. Artificial Neural Networks (ANN) has been
used for template matching of non-geometric shapes (Chaki and Parekh, 2011).
b) Detection of objects with geometric shapes
Man-made features like windows, doors, traffic signs, boxes, balls and walls have geometric
shapes. This category deals with the detection of these shapes which can be
easily analysed geometrically. The properties of these shapes can be fully described by
geometric theorems, for example the distance from the centre of a circle to any point on
its circumference is a constant known as the radius of that circle. Methods for detecting
these shapes make use of these properties to check for their existence in a scene. Though
template matching can also be used for detecting these shapes/objects (Gavrila, 1998),
detection based on geometric properties of these shapes have found wide interests among
researchers. A particular advantage of using the latter is that it eliminates the need for
training the system/algorithm. Hough Transform (HT) based methods are among the
earliest methods used for detection of geometric shapes. However, the memory requirement
of the algorithm increases tremendously when the dimension of the shape is greater
than two (for example circle dimension is three) (Dasgupta et al., 2010). This has led
to various methods to improve its performance and exploration of other approaches to
shape detection. Some of other approaches to shape detections include: Random Hough
Transform (RHT) (Jiang, 2012), Genetic Algorithm (GA) (Ramirez et al., 2011), Arti-
2
ficial Immune System (AIS) (Cuevas et al., 2012a), Learning Automata (LA) (Cuevas
et al., 2012b) and Clustering-Based algorithms (Scitovski and Maroˇsevi´c, 2015).
This research uses an Artificial Immune System (AIS) based algorithm known as the Clonal
Selection Algorithm (CSA), to detect the presence of geometric shapes (circles, triangles and
quadrilaterals) in an image. The immune system can detect several antigens with different
characteristics and has memory of past encounters with antigens for more aggressive response
when similar antigens are encountered in the future. These properties make the AIS suitable for
solving multi-objective, pattern recognition and multi-modal problems (Ulutas and Kulturel-
Konak, 2011) – detecting multiple shapes in this case.
1.2 Motivation
The state of the art in automatic detection of geometric shapes involves the development of
algorithms capable of detecting a single shape type. The motivation for this research springs
from the need to have a single system that is capable of detecting multiple shape types in an
image. Such a system eliminates the need of implementing separate algorithms for detecting the
different shape types; and makes the process of multiple shape types detection more efficient
and less time consuming.
1.3 Problem Statement
After extensive search in literature on detection of shapes based on geometric properties, it
has been observed that most researchers focused on the detection of single shapes or multiple
instances of that shape in an image. This means, a user intending to apply these methods for
detecting multiple shape types will have to use separate detection system per shape. This is
inefficient and time consuming when applied to scenarios where multiple shapes need to be
identified and classified.
3
1.4 Aim and Objectives
The aim of the research is the development of a Clonal Selection Algorithm (CSA) based
system for detection of multiple shapes.
The objectives of the research are as follows:
1. To develop a CSA based system for detection of multiple shapes (circles, triangles and
quadrilaterals) irrespective of their positions, sizes and orientations in an image;
2. To enhance the developed system in 1. to be able to detect multiple instances of these
shapes during a single run of the CSA algorithm and be robust in the presence of noise;
3. To implement the system developed in 1. and 2.; validate by computing the MSE, PSNR,
MAE, and error score on five (5) synthetic images developed using MATLAB; and computing
the False Positive Rate (FPR) and False Negative Rate (FNR) on the synthetic
images and six (6) real image scenes captured on digital camera.
1.5 Methodology
The steps taken to achieve the Clonal Selection Algorithm (CSA) for detecting multiple shapes
are:
1. Prepare a repository of images:
(a) Generate, using MATLAB, three (3) synthetic images of multiple circles, quadrilaterals
and triangles in which the shapes are of varying dimensions, positions and
orientation in the image scene and two (2) synthetic images containing a mixture of
the desired and undesired shapes.
(b) Save the locations of the pixels used to generate the shapes. These are used as
ground truth for the images.
(c) Save the generated images in Joint Photographic Experts Group (JPEG) format.
4
(d) Capture images of circular, triangular and quadrilateral objects using a digital camera
and save them on the computer.
2. Develop CSA based systems for detection of circles, triangles and quadrilaterals:
(a) Develop CSA that detects a circle in an image scene.
(b) Develop CSA that detects a triangle in an image scene.
(c) Develop CSA that detects a quadrilateral in an image scene.
3. Enhance the developed CSA systems to detect multiple instances of desired shapes in a
single CSA algorithm:
(a) Develop a system of analysing the CSA memory to extract other detected circles,
that is other antibodies with fitness higher than a set threshold, and compute the
MSE and PSNR when detecting synthetic circles of 1(a).
(b) Apply the system developed in 3(a) for multiple triangles in an image and compute
the MSE and PSNR when detecting synthetic triangles of 1(a).
(c) Apply the system developed in 3(a) for detecting multiple quadrilaterals in an image
and compute the MSE and PSNR when detecting synthetic quadrilaterals of 1(a).
(d) Combine the antibody pools of circle, triangle and quadrilateral detectors.
(e) Develop a CSA that utilizes the antibody pool of 3(d) for detecting antigens (desired
shapes) in an image scene.
(f) Test the developed CSA of 3(e) with synthetic images of 1(a) by computing its
MSE, PSNR, MAE and error score on these images.
4. Use the CSA implementation of 3 for detecting the desired shapes in real images using
the captured images in 1(d).
5. Compute the False Positive Rate (FPR) and False Negative Rate (FNR) on detection of
the whole test images (both synthetic and real images).
5
1.6 Dissertation Organization
The background and introduction to the project has been provided in chapter one. Chapter
two provides the relevant theories incorporated into the research for multiple shapes detection
and a review of literature in the field. The detailed design decisions made in implementing the
CSA system for multiple shapes detection is provided in chapter three. Results and analysis
of the results is provided in chapter four while chapter five provides concluding remarks and
recommendations for future research.
6
IF YOU CAN'T FIND YOUR TOPIC, CLICK HERE TO HIRE A WRITER»
