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