CMRT09: Object Extraction for 3D City Models, Road Databases and Traffic Monitoring - Concepts, Algorithms, and Evaluation
array is passed through these classifiers in turn; each
classifier eliminates the data that confidently does not belong
to the target class, the remained data is passed to the
following, more "complex" classifier, for more thorough
examination, etc.
The general idea of cascades involves detection of one target
class that implies binary classification. In our task the
cascade is applied to a problem of separating objects of two
different classes from a background; that requires three-class
classification. It is important to notice, that the background
class in our task dominates significantly over classes of lane
marking and pavement defects. This finding suggests
modifying the scheme of cascades used in (Sudakov, 2008) in
order to allow detection of several classes of objects.
Cascade workflow
At the offline stage the image had been segmented using the
method from (Paris, 2007) into homogeneous regions, and
several scales of segmentation are available. The largest scale
segmentation is used on the first layer of cascade, the most
detailed segmentation scale is used on the last layer.
Segmentation at each subsequent scale is a subdivision of
segmentation at the preceding scale, therefore we have a
sequence of enclosed segments (hierarchy). Each cascade
layer corresponds to a certain scale of hierarchy of
segmentation and a binary classifier.
Those segments that have not been rejected at the preceding
layers of cascade are classified into two classes: objects of
interest (including lane marking and road surface defects) and
background. The goal of classification is to reject the
segments that do not contain pixels of objects of interest. For
this purpose the threshold on the classifier output is set up so
that the detection rate is close to 100 %.
This procedure is repeated up to the last cascade layer and
then multi-class classification is applied. Segmentation
corresponding to the last cascade layer is detailed enough to
capture precise bounds of lane marking and pavement
defects. Moreover, the majority of background segments are
rejected at the preceding layers, so the number of background
segments passed to the last layer approximately equals to the
number of lane marking segments and segments of road
covering defects. Therefore our cascade operational scheme
also helps to solve a problem of imbalanced classes thus
helping to achieve better classification performance. The
workflow of cascaded segmentation is illustrated in Figure 5.
6. ON-LINE LEARNING
Online learning algorithms (Domingos, 2000, Oza,2005)
process each training example once ‘on arrival’ without the
need for storage and reprocessing, and maintain a current
model that reflects all the training examples seen so far. Such
algorithms have advantages over typical batch algorithms in
situations where data arrive continuously. They are also
useful with very large data sets on secondary storage, for
which the multiple passes through the training set required by
most batch algorithms are prohibitively expensive.
In order to enable user-aided tuning of object detection we
incorporated on-line learning algorithm in the core of the
system. As long as we aim at interactive time of classification
and learning, the following requirements for the online-
learning algorithm arise. First, online classifier should not
store previously seen training examples. Second, learning
time should not depend on the number of examples already
seen by the learner. Thus we chose online random forest over
Hoeffding trees (Domingos, 2000) as it meets both these
requirements. Below we describe how online classifiers are
used in our cascaded detection method.
On-line learning of cascaded segmentation
In section 3 we described the workflow of cascaded
algorithm for object detection, supposing that all classifiers
are already trained. Here we describe the training phase of
cascaded detection method.
The main problem here is what data should be used for
training of classifier at each particular layer of cascade. There
are two difficulties with providing training data to classifiers
at cascade layers. First, we should take into account all
segments which contain target class because if we do not
provide enough samples of target class at the training stage,
classifier wouldn’t be able to detect them at classification
stage. This can lead to severe error of first kind.
The second problem is lack of target samples at all cascade
layers in comparison to number of background samples. This
class imbalance can lead to additional increase of error of
first kind. This means that cascade will miss large amount of
target objects. Therefore we need to consider special
techniques for balancing class distributions. Our solution for
both these problems is the following. We train classifier
corresponding to each cascade layer using the data passed to
a corresponding cascade layer by preceding version of
cascade which had not been adapted to last portion of data.
Then, all segments which contain marking and defects are
added to the training set on each layer. In order to better
balance classes’ distribution we use cost-sensitive online
random forest, described below.
On-line random forest
In this work we use ‘one vs all’ algorithm for multi-class
classification on the last cascade layer. This enables using
binary classifiers on the lowest tier of the system. Those
classifiers should be able to learn even some first portions of
a training set efficiently to give a reliable classification result.
Also, as mentioned above, these classifiers should handle
imbalanced classes’ data.
We use on-line random forest classifiers at all stages of
cascade. Our version of online random forest resembles an
online bagging algorithm proposed by (Oza, 2005). We
modified this algorithm in order to allow balancing the
classes. This is achieved by assigning parameters of
exponential distribution individually to each class in on-line
bagging algorithm.
This procedure akin to random resampling is equivalent to
introducing different penalty costs for misclassification of
objects of each class. In this work costs are calculated in
inverse proportion to a number of samples in the class. Also
we use a random set of features for every weak classifier like
in Random Forest algorithm (Brieman, 2001). This, together
with using Hoeffding trees (Domingos, 2000) as a weak
learner, helps to achieve stable classification results and
reduce training and classification time.
7. -EXPERIMENTS
Image base
For the experiments we used four road images. They differ in
quality and marking and relative areas of defects. We tested
our system on the first 18 parts of every road image. All parts