Recognition of Road Signs using Support Vector Machine and Approximated Invariant Method

Abstract
The main goal of this project was to build Matlab based system for detection of road signs in the input images.
Such road signs recognition system could be used as a part of automatic car system.
The project currently supports detection of three types of road signs: STOP, NO ENTRANCE and WAIT.
Project contain database of road signs images (~300 images).

Problem of road signs recognition could be generalized as the Target Detection Problem, i.e. the problem of finding specific target object from the wide range of inputs. The solution offered in the project is based on two classification algorithms.

• Support Vector Machine (SVM)
• Approximated Invariant Method (AIM)

Introduction
The classification algorithms above belong to the family of Example Based Classifiers. The main idea behind is that system could be trained to recognize required targets.

The classification algorithms above belong to the family of Example Based Classifiers. The main idea behind is that system could be trained to recognize required targets.

• Example Based Classifier system always involve two stages:
  • Training Stage
  • Classifying Stage

The purpose of the Training Stage of the algorithm is to learn properties of the objects (vectors) that should be detected. At this stage, system gets as input big amount of example vectors and learns to detect class of each one. The output of the Training Stage is a set of parameters that enable to detect class of the input vectors. We used to call this set of parameters Classifier.
At the Classifying Stage system uses parameters built during Training Stage in order to recognize class of the input vectors.

• Two types of classifiers can be defined:
  • 2-Class Classifier – classifier used to detect two classes of vectors
  • N-Class Classifier – classifier used to detect N >2 classes of vectors

Classifier operation could be described in terms of its decision.
function C(x). Given vector decision function returns its type.

• For 2-Class Classifier:
• For N-Class Classifier:

Approximated Invariant Method (AIM) Algorithm
AIM algorithm is an example based classification algorithm.
Similar to all example-based systems it has two stages: Training Stage
and Classifier Stage.

AIM Training Stage:
Training algorithm gets as its input group of the example
vectors (in ) . Training process executed in iterative manner.
In each iteration, projection vector in space is selected.
On the direct defined by the projection vector defined three ranges:
Target range, Clutter range and Unknown range. (Definition of projection vector and ranges above, done for each iteration and is based on current set of examples vectors).
Classification idea: Classification of the input vector performed by its projection on projection vector and checking the range the result was fall to. If projection result is in Target range vector class is Target, if it falls to Clutter range its class is Clutter. In the case when Target and Clutter ranges have non zero intersection and the result above falls to that region, its class can’t be detected and it is classified as Unknown.

Before going to the next iteration Training algorithm updates group of examples vectors. This is done by performing classification of each example, when last calculated projection vector and ranges limits are used. If system succeeds to classify example (result class is not Unknown) it is removed from example vectors group. This way, in each iteration, algorithm learns to classify vectors which type was not recognized before. Training process finishes when no unclassified examples left or in two successive iterations no new examples were recognized. The output of the Training algorithm is set of project vectors and correspondent Target/Clatter/Unknown regions.

AIM Classifier Stage:
Classifier Stage receives as input parameters calculated by Training Stage and set of the input vectors that require class detection. Similar to learning process, classification performed in iterative manner .In each iteration system tries to detect class of all input vectors using projection vector and correspondent Target/Clatter/Unknown regions (as described above). Process finishes after all iterations were executed.

Support Vector Machine
Basic SVM algorithm is able to recognize two different types of objects (vectors). The algorithm offers to do classification by building hyperplane in the vector space and checking at which side found each vector. This operation may be described by decision function:
C(x) = w*x + b (w – vector orthogonal to hyperplane, b – distance from hyperplane to the origin.
If sgn(w*x + b) > 0 => vector is Target.
If sgn(w*x + b) < 0 => vector is Clutter.

SVM Training Stage:
SVM Training algorithm gets as input set of example vectors from each of two classes. Based on this information the separating hyperplane parameters (w, b) are calculated.

SVM Classifier Stage:
In order to classify input vector x, decision function sgn(w*x + b) is applied.

Multiple Classes Case:
If there are more then two different types of vectors, Multiple Classes SVM algorithm is used. N-class SVM classifier is built from N 2-class SVM classifiers (N separating hyperplanes ). Each separating hyperplane is built to separate one class of vectors from all other classes. In order to detect vector type N – classifiers are applied. Final decision about class of the vector received using following rule:

Road Sign Recognition
In order to detect road signs inside the input image, following steps are performed:
1) If input is a color image, special transform applied converting it to
enhanced intensity image (see documentation below).
2) Input image is partitioned to rectangular segments with controllable
steps in x and y directions. (Segments size equal to the size of searched
road signs).
3) Classification algorithm is applied to each segment. As a result every
segment marked with its detected class.
See detailed explanation in project documentation below.

Bibliography
1. Face Detection By the Approximated Invariant Method (AIM)
Michael Elad, Yacov Hel-Or, Renato Keshet, Hewlet-Packard Laboratories Israel

2. A Tutorial on Support Vector Machines for pattern Recognition
Cristopher Burges, Bell Laboratories, Lucent Technologies

3. Support Vector Learning, (Bernhard Scholkopf, University of Berlin)

4. Training Support Vector Machines: Application to Face Detection
Edgar Osuna, Robert Freund, Federico Girosi, Center for Biological
and Computational Learning, Massachusetts Institute of Technology

5. Gentle Guide for Support Vector Machines, Ming-Hsuan Yang

6. Matlab Help Desk.

Acknowledgments
We would like to thank our supervisor Shie Manor for his support and
guidance throughout this project.