4.2.1 Types of Learning

Machine learning algorithms can be broadly divided into supervised learning, semi-supervised learning, and unsupervised learning [5, pp. 102–105]. The division depends on the training data that is provided during the learning process. In this section the different types of learning algorithms are briefly presented. An example of training data for each method is illustrated in Fig. 4.2.

Supervised learning. In supervised learning, labeled data is provided to the learning process meaning that each example is annotated with the desired target output. The dataset for training consists of N input–target pairs,

$X=\{(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),\dots ,(x^{(N)},y^{(N)})\}.$

Each training pair consists of input data $x^{(i)}$ together with the corresponding target $y^{(i)}$. The goal of the algorithm is to learn a mapping from the input data to the target value so that the target $y^{⁎}$ for some unseen data $x^{⁎}$ can be predicted. Supervised learning can be thought of as a teacher that evaluates the performance and identifies errors during training to improve the algorithm.

Common tasks in supervised learning are classification and regression. In classification, the target is a discrete value which represents a category such as “red” and “blue” (see Fig. 4.2A). Another example is the classification of images to predict the object that is shown in the image such as for instance “car”, “plane”, or “bicycle”. In regression, the target is a real value such as “dollars” or “length”. A regression task is for instance the prediction of house prices based on data of the properties such as location or size.

Popular examples of supervised learning methods are random forests, support vector machines, and neural networks.

Semi-supervised learning. Semi-supervised learning is a mixture between supervised learning and unsupervised learning. Typically, supervised learning methods require large amounts of labeled data. Whereas the collection of data is often cheap, labeling data can usually only be achieved at enormous costs because experts have to annotate the data manually. Semi-supervised learning combines supervised learning and the usage of unlabeled data. For that, the dataset consists of N labeled examples,

$X_{\text{l}}=\{(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),\dots ,(x^{(N)},y^{(N)})\},$

together with M unlabeled examples,

$X_{\text{u}}=\{x^{(N+1)},x^{(N+2)},\dots ,x^{(N+M)}\}.$

Usually, the number of labeled examples N is much smaller than the number of unlabeled examples M. Semi-supervised learning is illustrated in Fig. 4.2B for the classification of data points.

Unsupervised learning. In unsupervised learning, unlabeled data is provided to the learning process. The aim of the learning algorithm is to find structures or relationships in the data without having information about the target. The training set consists of N training samples,

$X=\{x^{(1)},x^{(2)},\dots ,x^{(N)}\}.$

Popular unsupervised learning methods are for example k-means and mean shift. For unsupervised learning, usually, a distribution of the data has to be defined. K-means assumes that the data is convex and isotropic and requires a predefined number of classes. For mean shift a kernel along with a bandwidth is defined such as for example a Gaussian kernel. Typical tasks in unsupervised learning are density estimation, clustering, and dimensionality reduction. An example of a clustering task is shown in Fig. 4.2C.

4.2.2 Convolutional Neural Networks

Convolutional neural networks have shown great success in recent years. Especially since Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton won the ImageNet Large-Scale Visual Recognition Challenge in 2012 the topic of research has attracted much attention [6]. In this section an overview of convolutional neural networks is given. First, the origins of neural networks are described and afterwards the learning process back-propagation is explained. Finally, convolutional neural networks are presented.

4.2.2.1 Artificial neuron

Neural networks have been biologically inspired by the brain. The brain is a very efficient information-processing system which consists of single units, so-called neurons, which are highly connected with each other [7, pp. 27–30].

The first model of an artificial neuron was presented by Warren McCulloch and Walter Pitts in 1943 [8] and was called the McCulloch–Pitts model. The scientists drew a connection between the biological neuron and logical gates and developed a simplified mathematical description of the biological model. In 1957, Frank Rosenblatt developed the so-called perceptron [9], which is based on the work of McCulloch and Pitts. The model has been further generalized to a so-called artificial neuron. An artificial neuron has N inputs and one output a, as illustrated in Fig. 4.3. Each input is multiplied by a weight $w_i$. Afterwards all weighted inputs are added up together with a bias b, which gives the weighted sum z:

$z=\sum _{i=1}^N{x}_i\cdot w_i+b.$

(4.1)

Finally, the output is calculated using an activation function $\varphi (\cdot )$:

$a=\varphi (z).$

(4.2)

Early models such as the perceptron often used a step function $\mathrm{g}(x)$ as activation function where g is defined as

$\mathrm{g}(x)=\{\begin{array}{cc}1\hfill & x⩾0,\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}$

(4.3)

Another activation function that is commonly used is the sigmoid function,

$\mathrm{sig}(x)=\frac{1}{1+e^{-x}}.$

(4.4)

Different from the step function, the sigmoid function is differentiable. This is an important property for training as shown later in this chapter. In recent years, another activation function, called the rectified linear unit (ReLU) became popular, which has been proposed by Krizhevsky et al. [6]. ReLU outputs 0 if the input value x is smaller than zero and otherwise the input value x:

$\mathrm{ReLU}(x)=\max (0,x).$

(4.5)

Compared with the sigmoid function, ReLU is non-saturating for positive inputs and has shown to accelerate the training process.

This model of an artificial neuron can be used to classify input data into two classes. However, this only works for data which is linearly separable. To calculate more complex functions, multiple neurons are connected as presented in the next section.

4.2.2.2 Artificial neural network

Neural networks are arranged in layers. Each network has an input layer, one or more hidden layers, and an output layer. An example of a two-hidden-layer network is presented in Fig. 4.4. The design of the input and output layer is often straightforward compared to the design of the hidden layers. The input layer is the first layer in the network. Its so-called input neurons store the input data and perform no computation. If the input is for example an image of size $32\times 32$ pixels, the number of input neurons is $1024=32\cdot 32$. The output layer is the last layer in the network and contains the output neurons. For example, if a network classifies an image into one out of ten classes, the output layer contains one neuron for each class, indicating the probability that the input belongs to this class.

Formally, a neural network has L layers where the first layer is the input layer and the Lth layer is the output layer. Neural networks with multiple layers are also called multilayer perceptrons. They are one of the simplest types of feed-forward neural networks, which means that the connected neurons build an acyclic directed graph.

Each layer l has $n_l$ neurons and a neuron is connected to all neurons in the previous layer. The weight between the kth neuron in the $(l-1)$th layer and the jth neuron in the lth layer is denoted by $w_{k,j}^l$. Similarly, the bias of the jth neuron in the lth layer is denoted by $b_j^l$. Similar to Eq. (4.1) the weighted sum $z_j^l$ of a neuron is calculated by

$z_j^l=\sum _{k=1}^{n_{l-1}}{a}_k^{l-1}\cdot w_{k,j}^l+b_j^l.$

(4.6)

Afterwards the activation function is used to calculate the output $a_j^l$ of a neuron

$a_j^l=\varphi (z_j^l).$

(4.7)

To simplify the notation, the formulas can be written in matrix form. For each layer, a bias vector $b^l$, a weighted sum vector $z^l$, and an output vector $a^l$ are defined:

$b^l={\left[\begin{array}{cccc}\hfill b_1^l\hfill & \hfill b_2^l\hfill & \hfill \dots \hfill & \hfill b_{n_l}^l\hfill \end{array}\right]}^{\text{T}},$

(4.8)

$z^l={\left[\begin{array}{cccc}\hfill z_1^l\hfill & \hfill z_2^l\hfill & \hfill \dots \hfill & \hfill z_{n_l}^l\hfill \end{array}\right]}^{\text{T}},$

(4.9)

$a^l={\left[\begin{array}{cccc}\hfill a_1^l\hfill & \hfill a_2^l\hfill & \hfill \dots \hfill & \hfill a_{n_l}^l\hfill \end{array}\right]}^{\text{T}}.$

(4.10)

The weights for each layer can be expressed by a matrix $w^l\in {\mathbb{R}}^{n_l\times n_{l-1}}$:

$w^l=\left[\begin{array}{ccc}\hfill w_{1,1}^l\hfill & \hfill \dots \hfill & \hfill w_{n_{l-1},1}^l\hfill \\ \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill w_{1,n_l}^l\hfill & \hfill \dots \hfill & \hfill w_{n_{l-1},n_l}^l\hfill \end{array}\right].$

(4.11)

The matrix has $n_l$ rows and $n_{l-1}$ columns which corresponds to the number of neurons in layer l and layer $(l-1)$. The kth row of $w^l$ contains all weights of the kth neuron in layer l connecting the neuron to all neurons in layer $(l-1)$. Using the matrix form, the weighted sum for each layer can be calculated by multiplying the weight matrix with the output of the previous layer and adding the biases:

$z^l=w^l{a}^{l-1}+b^l.$

(4.12)

Applying the activation to each element of the weighted sum vector, the output of each layer is calculated by

$a^l=\varphi (z^l).$

(4.13)

A neural network takes some input data x and calculates the output of the network $\mathrm{N}(x)$, which is defined as the output of the last layer $\mathrm{N}(x)=a^L(x)$. This is done by processing the network layer by layer. First of all the input data is passed to the input neurons $a^1(x)=x$. Afterwards all layers are processed by calculating the weighted sum and the output. Finally, the output of the network $a^L(x)$ is calculated.

4.2.2.4 Convolutional neural networks

Neural networks as explained in the last section are also called fully-connected neural networks. Every neuron is connected to every neuron in the previous layer. For a color image of size $32\times 32$ pixels with three color channels, this means that each neuron in the first hidden layer has $3072=32\cdot 32\cdot 3$ weights. Although at first glance acceptable, for large images the number of variables is extremely large. For example, a color image of size $200\times 200$ pixels with three color channels already requires $120000=200\cdot 200\cdot 3$ weights for each neuron in the first hidden layer. Additionally, fully-connected neural networks are also not taking the spatial structure into account. Neurons that are far away from another are treated equally to neurons that are close together.

Convolutional neural networks are designed to take advantage of the two-dimensional structure of an input image. Instead of learning fully-connected neurons, filters are learned that are convolved over the input image. The idea has been inspired by the visual cortex. Hubel and Wiesel [13] showed in 1962 that some neural cells are sensitive to small regions in the visual field and respond to specific features. In 1998, convolutional neural networks were popularized by Lecun, Botto, Bengio, and Haffner [14].

The first difference between regular neural networks and convolutional neural networks is the arrangement of the data. In order to take into account that images or other volumetric data are processed, the data in convolutional neural networks is arranged in 3D volumes. Each data blob in a layer has three dimensions: height, width, and depth. Each layer receives an input 3D volume and transforms it to an output 3D volume.

Convolutional layer. Whereas fully-connected neurons are connect to every neuron in the previous layer, neurons in convolutional layers will be connected to only a small region of the input data. This region is called local receptive field for a hidden neuron. Instead of applying different weights and biases for every local receptive field, the neurons are using shared weights and biases. The idea behind this is that a feature that is learned at one position might also be useful at a different position. Additionally, the number of parameters will decrease significantly. The shared weights and biases are defined as filter.

The size of the filters is usually small in height and width whereas the depth always equals the depth of the input volume. For example, a filter of size $3\times 5\times 5$ is often used in the first hidden layer, i.e. 3 pixels in depth, because the input image has three color channels, 5 pixels in height, and 5 pixels in width. In general, a filter has depth $C_{\text{in}}$, height $K_{\text{h}}$, and width $K_{\text{w}}$, where $C_{\text{in}}$ is the depth of the input volume. This results in $C_{\text{in}}\cdot K_{\text{h}}\cdot K_{\text{w}}$ weights plus one bias per filter.

Convolutional layers consist of a set of K filters. Each filter is represented as a three-dimensional matrix $W_i$ of size $C_{\text{in}}\times K_{\text{h}}\times K_{\text{w}}$ and a bias $b_i$. To calculate the weighted sum Z of a layer, each filter is slided across the width and height of the input volume. Therefore the dot product between the weights of the filter $W_i$ and the input volume I at any position is computed:

$Z[i,y,x]=\sum _{c=0}^{C_{\text{in}}-1}\sum _{l=0}^{K_{\text{h}}-1}\sum _{m=0}^{K_{\text{w}}-1}{W}_i[c,l,m]I[c,y+l,x+m]+b_i$

(4.22)

where i denotes the filter index and x, y the spatial position. Each filter produces a two-dimensional feature map. These feature maps are stacked along the depth and generate a three-dimensional volume Z. Afterwards the activation output A is calculated by applying the activation function to each element of the matrix Z,

$A[i,y,x]=\varphi (Z[i,y,x]).$

(4.23)

Each convolutional layer transforms an input volume of size $C_{\text{in}}\times H_{\text{in}}\times W_{\text{in}}$ to an output volume of size $C_{\text{out}}\times H_{\text{out}}\times W_{\text{out}}$. Additional to the number of filters K and the filter size $K_{\text{h}}\times K_{\text{w}}$, further parameters of a convolutional layer are the stride S and padding P. The stride S defines the number of pixels a filter is moved when sliding a filter over the input volume. While $S=1$ refers to the standard convolution, $S>1$ will skip some pixels and lead to a smaller output size. The padding P adds additionally P pixels to the border of the input volume. For example, it can be used to create an output volume that has the same size as the input volume. In general, because the feature maps are stacked, the output depth $C_{\text{out}}$ equals the number of filters K that are used. The width and height of the output volume can be calculated by

$W_{\text{out}}=(W_{\text{in}}-K_{\text{w}}+2P)/S+1,$

(4.24)

$H_{\text{out}}=(H_{\text{in}}-K_{\text{h}}+2P)/S+1.$

(4.25)

Pooling layer. Another layer that is commonly used is the pooling layer. Usually, it is inserted directly after a convolutional layer. Pooling operates independently on every depth slice and applies a filter of size $K\times K$ to summarize the information. Similar to convolutional layers, a stride S controls the amount of pixels the filter is moved. Most frequently max pooling is used. As shown in Fig. 4.5, max pooling takes the maximum over each region and outputs a smaller feature map. For example, a filter size of $2\times 2$ is commonly used which reduces the amount of information by a factor of 4. A pooling layer keeps the information that a feature has found but leaves out the exact position. By summarizing the features the spatial size is decreased. Thus, fewer parameters are needed in later layers which reduces the amount of memory that is required and the computation time. Other types of pooling functions are average pooling and L2-norm pooling.

Dropout layer. A common problem when using neuron networks is overfitting. Because of too many parameters, a network might learn to memorize the training data and does not generalize to unseen data. Dropout is a regularization technique to reduce overfitting [15]. A dropout-ratio p is defined and during training each neuron is temporarily removed with a probability p and kept with a probability $p-1$, respectively. An example is illustrated in Fig. 4.6. This process is repeated so that in each iteration different networks are used. In general, dropout has shown to improve the performance of networks.

4.2.3 Random Forests

The random forest algorithm is a supervised learning algorithm for classification and regression. A random forest is an ensemble method that consists of multiple decision trees. The first work goes back to Ho [16] in 1995 who introduced random decision forests. Breiman [17] further developed the idea and presented the random forest algorithm in 2001.

4.2.3.1 Decision tree

A decision tree consists of split nodes ${\mathcal{N}}^{\text{Split}}$ and leaf nodes ${\mathcal{N}}^{\text{Leaf}}$. An example is illustrated in Fig. 4.7. Each split node $s\in {\mathcal{N}}^{\text{Split}}$ performs a split decision and routes a data sample x to the left child node $\mathrm{cl}(s)$ or to the right child node $\mathrm{cr}(s)$. When using axis-aligned split decisions the split rule is based on a single split feature $\mathrm{f}(s)$ and a threshold value $\theta (s)$:

$x\in \mathrm{cl}(s)\iff x_{\mathrm{f}(s)}<\theta (s),$

(4.26)

$x\in \mathrm{cr}(s)\iff x_{\mathrm{f}(s)}⩾\theta (s).$

(4.27)

The data sample x is routed to the left child node if the value of feature $f(s)$ of x is smaller than a threshold $\theta (s)$ and to the right child node otherwise. All leaf nodes $l\in {\mathcal{N}}^{\text{Leaf}}$ store votes for the classes $y^l=(y_1^l,\dots ,y_C^l)$, where C is the number of classes.

Decision trees are grown using training data. Starting at the root node, the data is recursively split into subsets. In each step the best split is determined based on a criterion. Commonly used criteria are Gini index and entropy:

$\mathit{\text{Gini index:}}\mathrm{G}(E)=1-\sum _{j=1}^C{p^2}_j,$

(4.28)

$\mathit{\text{entropy:}}\mathrm{H}(E)=-\sum _{j=1}^C{p}_j\log p_j.$

(4.29)

The algorithm for constructing a decision tree works as follows:

1. 1.  Randomly sample n training samples with replacement from the training dataset.
2. 2.  Create a root node and assign the sampled data to it.
3. 3.  Repeat the following steps for each node until all nodes consists of a single sample or samples of the same class:
   1. a.  Randomly select m variables out of M possible variables.
   2. b.  Pick the best split feature and threshold according to a criterion, for example Gini index or entropy.
   3. c.  Split the node into two child nodes and pass the corresponding subsets.

For images, the raw image data is usually not used directly as input for the decision trees. Instead, features such as for instance HOG features or SIFT features are calculated for a full image or image patch. This additional step represents an essential difference between decision trees and convolutional neural networks. Convolutional neural networks in comparison are able to learn features automatically.

4.2.3.2 Random forest

The prediction with decision trees is very fast and operates on high-dimensional data. On the other hand, a single decision tree has overfitting problems as a tree grows deeper and deeper until the data is separated. This will reduce the training error but potentially results in a larger test error.

Random forests address this issue by constructing multiple decision trees. Each decision tree uses a randomly selected subset of training data and features. The output is calculated by averaging the individual decision tree predictions. As a result, random forests are still fast and additionally very robust to overfitting. An example of a decision tree and a random forest is shown in Fig. 4.8.

4.4.1 Feature Learning

We learn features by training a convolutional neural network ${\mathrm{CNN}}^{\text{F}}$. The patch size is $32\times 32$. We adopt the network architecture of Springenberg et al. [35], which yields good results on datasets like CIFAR-10, CIFAR-100, and ImageNet. The model ALL-CONV-C performed best and is used in this work. The network has a simple regular structure consisting of convolution layers only. Instead of pooling layers convolutional layers with stride of two are used. Additionally, the fully-connected layers that are usually at the end of a convolutional neural network, are replaced by $1\times 1$ convolutional layers followed by an average pooling layer. Thus the output of the last layer has a spatial size of $1\times 1$ and a depth C, where C equals the number of classes.

Because we have only very little labeled data available, we train the network on the larger dataset GTSRB [1]. After training, the resulting network ${\mathrm{CNN}}^{\text{F}}$ can be used to generate feature vectors by passing an input image to the network and performing a forward pass. The feature vectors can be extracted from the last convolutional layer or the last convolutional layer before the $1\times 1$ convolutional layers, respectively. In our network this corresponds to the seventh convolutional layer, denoted by ${\mathrm{CNN}}_{\mathit{\text{relu7}}}^{\text{F}}(x)$.

4.4.2 Random Forest Classification

Usually, neural networks perform very good in classification. However, if the data is limited, the large amount of parameters to be trained causes overfitting. Random forests [17] have shown to be robust classifiers even if few data are available. A random forest consists of multiple decision trees. Each decision tree uses a randomly selected subset of features and training data. The output is calculated by averaging the individual decision tree predictions.

After creating a feature generator, we calculate the feature vector $f^{(i)}={\mathrm{CNN}}_{\mathit{\text{relu7}}}^{\text{F}}(x^{(i)})$ for every input vector $x^{(i)}$. Based on the feature vectors we train a random forest that predicts the target values $y^{(i)}$. By combining the feature generator ${\mathrm{CNN}}^{\text{F}}$ and the random forest, we construct a classifier that predicts the class probabilities for an image patch. This classifier can be used to process a full input image patch-wisely. Calculating the class probabilities for each image patch produces an output probability map.

4.4.3 RF to NN Mapping

Here, we present a method for mapping random forests to two-hidden-layer neural networks introduced by Sethi [31] and Welbl [32]. The mapping is illustrated in Fig. 4.9. Decision trees have been introduced in Sect. 4.2.3.1. A decision tree consists of split nodes ${\mathcal{N}}^{\text{Split}}$ and leaf nodes ${\mathcal{N}}^{\text{Leaf}}$. Each split node $s\in {\mathcal{N}}^{\text{Split}}$ evaluates a split decision and routes a data sample x to the left child node $\mathrm{cl}(s)$ or to the right child node $\mathrm{cr}(s)$ based on a split feature $f(s)$ and a threshold value $\theta (s)$:

$x\in \mathrm{cl}(s)\iff x_{f(s)}<\theta (s),$

$x\in \mathrm{cr}(s)\iff x_{f(s)}⩾\theta (s).$

The data sample x is routed to the left child node if the value of feature $f(s)$ of x is smaller than a threshold $\theta (s)$ and to the right child node otherwise. All leaf nodes $l\in {\mathcal{N}}^{\text{Leaf}}$ store votes for the classes $y^l=(y_1^l,\dots ,y_C^l)$, where C is the number of classes. For each leaf a unique path $\mathrm{P}(l)=(s_0,\dots ,s_d)$ from root node $s_0$ to leaf l over a sequence of split nodes ${\{s_i\}}_{i=0}^d$ exists, with $l\subseteq s_d\subseteq \dots \subseteq s_0$. By evaluating the split rules for each split node along the path $\mathrm{P}(l)$ the leaf membership can be expressed as

$x\in l\iff \forall s\in \mathrm{P}(l):\{\begin{array}{cc}{x}_{f(s)}<\theta (s)\hfill & \text{if }l\in \mathrm{cl}(s),\hfill \\ x_{f(s)}⩾\theta (s)\hfill & \text{if }l\in \mathrm{cr}(s).\hfill \end{array}$

First hidden layer. The first hidden layer computes all split decisions. It is constructed by creating one neuron ${\mathrm{H}}_1(s)$ per split node evaluating the split decision $x_{f(s)}⩾\theta (s)$. The activation output of the neuron should approximate the following function:

$\mathrm{a}({\mathrm{H}}_1(s))=\{\begin{array}{cc}-1,\hfill & \text{if }{x}_{f(s)}<\theta (s),\hfill \\ +1,\hfill & \text{if }{x}_{f(s)}⩾\theta (s),\hfill \\ \hfill \end{array}$

where −1 encodes a routing to the left child node and +1 a routing to the right child node. Therefore the $f(s)$th neuron of the input layer is connected to ${\mathrm{H}}_1(s)$ with weight $w_{f(s),{\mathrm{H}}_1(s)}={\text{c}}_{\text{split}}$, where ${\text{c}}_{\text{split}}$ is a constant. The bias of ${\mathrm{H}}_1(s)$ is set to $b_{{\mathrm{H}}_1(s)}=-{\text{c}}_{\text{split}}\cdot \theta (s)$. All other weights and biases are zero. As a result, the neuron ${\mathrm{H}}_1(s)$ calculates the weighted sum,

$z_{{\mathrm{H}}_1(s)}={\text{c}}_{\text{split}}\cdot x_{\mathrm{f}(s)}-{\text{c}}_{\text{split}}\cdot \theta (s),$

which is smaller than zero when $x_{f(s)}<\theta (s)$ is fulfilled and greater than or equal to zero otherwise. The activation function $\mathrm{a}(\cdot )=\tanh (\cdot )$ is used which maps the weighted sum to a value between −1 and +1 according to the routing. The constant ${\text{c}}_{\text{split}}$ controls the sharpness of the transition from −1 to +1.

Second hidden layer. The second hidden layer combines the split decisions from layer ${\mathrm{H}}_1$ to indicate the leaf membership $x\in l$. One leaf neuron ${\mathrm{H}}_2(l)$ is created per leaf node. It is connected to all split neurons ${\mathrm{H}}_1(s)$ along the path $s\in \mathrm{P}(l)$ as follows:

$w_{{\mathrm{H}}_1(s),{\mathrm{H}}_2(l)}=\{\begin{array}{cc}-{\text{c}}_{\text{leaf}}\hfill & \text{if }l\in \mathrm{cl}(s),\hfill \\ +{\text{c}}_{\text{leaf}}\hfill & \text{if }l\in \mathrm{cr}(s),\hfill \end{array}$

where ${\text{c}}_{\text{leaf}}$ is a constant. The weights are sign matched according to the routing directions, i.e. negative when l is in the left subtree from s and positive otherwise. Thus, the activation of ${\mathrm{H}}_2(l)$ is maximized when all split decisions routing to l are satisfied. All other weights are zero. To encode the leaf to which a data sample x is routed, the bias is set to

$b_{{\mathrm{H}}_2(l)}=-{\text{c}}_{\text{leaf}}\cdot (|\mathrm{P}(l)|-1),$

so that the weighted sum of neuron ${\mathrm{H}}_2(l)$ will be greater than zero when all split decisions along the path are satisfied and less than zero otherwise. By using the activation function $\mathrm{a}(\cdot )=\mathit{\text{sigmoid}}(\cdot )$, the active neuron ${\mathrm{H}}_2(l)$ with $x\in l$ will map close to 1 and all other neurons close to 0. Similar to ${\text{c}}_{\text{split}}$, a large value for ${\text{c}}_{\text{leaf}}$ approximates a step function, whereas smaller values can relax the tree hardness.

Output layer. The output layer contains one neuron ${\mathrm{H}}_3(c)$ for each class and is fully-connected to the previous layer ${\mathrm{H}}_2$. Each neuron ${\mathrm{H}}_2(l)$ indicates whether $x\in l$. The corresponding leaf node l in the decision tree stores the class votes $y_c^l$ for each class c. To transfer the voting system, the weights are set proportional to the class votes:

$w_{{\mathrm{H}}_2(l),{\mathrm{H}}_3(c)}={\text{c}}_{\text{output}}\cdot y_c^l,$

where ${\text{c}}_{\text{output}}$ is a scaling constant to normalize the votes as explained in the following section. All biases are set to zero.

Random forest. Extending the mapping to random forests with T decision trees is simply done by mapping each decision tree and concatenating the neurons of the constructed neural networks for each layer. The neurons for each class in the output layer are created only once. They are fully-connected to the previous layer and by setting the constant ${\text{c}}_{\text{output}}$ to $1/T$ the outputs of all trees are averaged. We denote the resulting neural network as ${\mathrm{NN}}^{\text{RF}}$. It should be noted that the memory size of the mapped neural network grows linearly with the total number of split and leaf nodes. A possible network splitting strategy for very large random forests has been presented by Massiceti et al. [33].

4.4.4 Fully Convolutional Network

Mapping the random forest to a neural network allows one to join the feature generator and the classifier. For that we remove the classification layers from ${\mathrm{CNN}}^{\text{F}}$, i.e. all layers after relu7, and append all layers from ${\mathrm{NN}}^{\text{RF}}$. The constructed network ${\mathrm{CNN}}^{\text{F+RF}}$ processes an image patch and outputs the class probabilities. The convolutional neural network ${\mathrm{CNN}}^{\text{F+RF}}$ is converted to a fully convolutional network ${\mathrm{CNN}}^{\text{FCN}}$ by converting the fully-connected layers into convolutional layers, similar to [36]. The fully convolutional network operates on input images of any size and produces corresponding (possibly scaled) output maps. Compared with patch-wise processing, the classifier is naturally slided over the image evaluating the class probabilities at any position. At the same time the features are shared so that features in overlapping patches can be reused. This decreases the amount of computation and significantly accelerates the processing of full images.

4.4.5 Bounding Box Prediction

The constructed fully convolutional network processes a color image $I\in {\mathbb{R}}^{W\times H\times 3}$ of size $W\times H$ with three color channels and produces an output $O={\mathrm{CNN}}^{\text{FCN}}(I)$ with $O\in {\mathbb{R}}^{W^{\prime }\times H^{\prime }\times C}$. The output consists of C-dimensional vectors at any position which indicate the probabilities for each class. Due to stride and padding parameters, the size of the output map can be decreased. To detect objects of different sizes, we process the input image in multiple scales $S=\{s_1,\dots ,s_m\}$.

We extract potential object bounding boxes by identifying all positions in the output maps where the probability is greater than a minimal threshold $t_{\text{min}}=0.2$. We describe a bounding box by

$b=(b_{\text{x}},b_{\text{y}},b_{\text{w}},b_{\text{h}},b_{\text{c}},b_{\text{s}}),$

where $(b_{\text{x}},b_{\text{y}})$ is the position of the center, $b_{\text{w}}\times b_{\text{h}}$ the size, $b_{\text{c}}$ the class, and $b_{\text{s}}$ the score. The bounding box size corresponds to the field of view which is equal to the size of a single image patch. All values are scaled according to the scale factor. The score $b_{\text{s}}$ is equal to the probability in the output map.

For determining the final bounding boxes, we process the following three steps. First, we apply non-maximum suppression on the set of bounding boxes for each class to make the system more robust and accelerate the next steps. For that we iteratively select the bounding box with the maximum score and remove all overlapping bounding boxes. Second, traffic signs are special classes since the subject of one traffic sign can be included similarly in another traffic sign as illustrated in Fig. 4.10. We utilize this information by defining a list of parts that can occur in each class. A part is found when a bounding box $b^{\prime }$ with the corresponding class and an intersection over union (IoU) greater than 0.2 exists. If this is the case, we increase the score by $b_{\text{s}}^{\prime }\cdot 0.2/P$, where P is the number of parts. Third, we perform non-maximum suppression on the set of all bounding boxes by iteratively selecting the bounding box with the maximum score and removing all bounding boxes with IoU >0.5. The final predictions are determined by selecting all bounding boxes that have a score $b_{\text{s}}$ greater than or equal to a threshold $t_c$ for the corresponding class.

4.7.1 Data Capturing

We developed an app for data recording which can be installed onto the smart phone. Using a bicycle mount, the smart phone is attached to the bike oriented in the direction of travel. While cycling, the app captures images and data from multiple sensors. Images of size $1080\times 1920$ pixels are taken with a rate of one image per second. Sensor data is recorded from the built-in accelerometer, gyroscope, and magnetometer with a rate of ten data points per second. Furthermore, geoinformation is added using GPS. The data is recorded as often as the GPS-data is updated.

4.7.2 Filtering

After finishing a tour, the images are filtered to reduce the amount of data. Especially monotonous routes, e.g. in rural areas, produce many similar images. However, the rate with which images are captured cannot be reduced because this increases the risk of missing interesting situations.

We therefore introduce an adaptive filtering of the images. The objective is to keep images of potentially interesting situations that help to analyze traffic situations, but to remove redundant images. For instance, interesting situations could be changes in direction, traffic jams, bad road conditions, or obstructions like construction works or other road users. For filtering, we integrate motion information and apply a twofold filtering strategy based on decreases in speed and acceleration:

We filter the images by removing images if none of the two criteria indicate an interesting situation. The filtering process reduces the amount of data by a factor of 5 on average. Subsequently, the data is transferred to a server.

4.8.1 Training and Test Data

Ten different traffic signs that are interesting for cyclists are selected. Because the signs differ from traffic signs for cars, the availability of labeled data is very limited. Some classes come with little labeled data but for some classes no labeled data is available. To have ground truth data of our classes for training and testing, we manually annotated 524 bounding boxes of traffic signs in the images. The data is split into a training set and a test set using a split ratio of 50/50. In Fig. 4.14, the number of samples per class is shown. The training data consists of 256 samples for all 10 classes which corresponds to less than 26 samples per class on average. Please note that some traffic signs are very rare. Class 1000-32, for example, has only five examples for training. Additionally, $2000$ background examples are randomly sampled for training and testing. The splitting is repeated multiple times and the results are averaged.

4.8.2 Classification

The first experiment evaluates the performance of the classification on patches. The evaluation is performed in two steps. First, the training for learning features is examined and, secondly, the classification on the target task.

For feature learning, the GTSRB [1] dataset is used since it is similar to our task and has a large amount of labeled data. The dataset consists of $39209$ examples for training and $12630$ examples for testing over 43 classes. After training, the convolutional neural network ${\mathrm{CNN}}^{\text{F}}$ achieves an accuracy of 97.0% on the test set.

In the next step, the learned features are used to generate a feature vector of each training example of our dataset, and then to train a random forest. For evaluation, the test data is processed similarly. A feature vector is generated for each example from the test set using the learned feature generator ${\mathrm{CNN}}^{\text{F}}$ and classified by the random forest subsequently.

Since the class distribution is imbalanced, we report the overall accuracy and the mean accuracy. The mean accuracy calculates the precision for each class independently and averages the results. The random forest classification achieves an accuracy of 96.8% and a mean accuracy of 94.8% on the test set. The confusion matrix is shown in Fig. 4.15. Six classes are classified without errors. All other classes, except from the background class, only contain a single, two, or three misclassified examples. Class 1000-32 which consist of five examples has larger error. Additionally, some background examples are classified as traffic signs and vice versa. Please refer to Fig. 4.15 for more information about the traffic signs the classes correspond to.

4.8.3 Object Detection

The next experiment is conducted to demonstrate the recognition performance of the proposed system. The task is to detect the position, size, and type of all traffic signs in an image. The images have a high diversity with respect to different perspectives, different lighting conditions, and motion blur.

The recognition system is constructed by extending the CNN for patch-wise classification to a fully convolutional network so that fast processing of full images is enabled. A filtering strategy is applied subsequently to predict bounding boxes. No additional training data is required during this process so that only 256 examples over 10 classes are used for training the recognition system. We process the images in eight different scales. Starting with the scale $s_0=1$, the image size is decreased from scale to scale by a factor of 1.3.

To evaluate the recognition performance, we process all images in the test set and match the predicted bounding boxes with the ground truth data. Each estimated bounding box is assigned to the ground truth bounding box with the highest overlap. The overlap is measured using the IoU and only overlaps with an IoU >0.5 are considered.

All bounding boxes come with a score and the class specific threshold $t_{\text{c}}$ determines if a bounding box is accepted or rejected as described in Sect. 4.4.5. For each class, the threshold $t_{\text{c}}$ is varied and precision and recall are calculated. Precision measures the accuracy of the predictions i.e. how many of the predicted objects are correct. It is defined as

$\mathrm{Precision}=\frac{\text{TP}}{\text{TP}+\text{FP}},$

where TP is the number of true positives and FP the number of false positives. Recall measures the amount of objects that are found relative to the total number of objects that are available and is defined as follows:

$\mathrm{Recall}=\frac{\text{TP}}{\text{TP}+\text{FN}},$

where TP is the number of true positives and FN the number of false negatives. The resulting precision-recall curves are shown in Fig. 4.16. To facilitate understanding these results, two graphs are shown. In the first, the precision-recall curves of a group of standard traffic signs are plotted. The results are good. Some classes are detected almost perfectly. In the second graph, the precision-recall curves of a different group of traffic signs are plotted. These signs are much more difficult to recognize as they are black and white and do not have a conspicuous color. The performance of each class correlates with the number of examples that are available for training. Class 9001 with 35 training examples performs best, class 1022-10 with 22 training examples second best, and class 1000-32 with only 5 training examples worst. In Fig. 4.17 failure cases for class 267 are shown. Patches with similar appearance are extracted due to the limited variability with few training samples and missing semantic information since the broader context is not seen from the patch-wise classifier. To summarize the performance on each class the average precision (AP) is calculated. The results are presented in Table 4.1. In total, the recognition system achieves a good mean average precision (mAP) of 0.713.

Table 4.1

Average precision of each class on the test dataset.

class	237	239	240	241	242.1	244.1	267	1000-32	1022-10	9001
AP	0.901	0.930	0.964	0.944	0.801	0.996	0.677	0.023	0.215	0.679

In the last step, the final bounding box predictions are determined. The threshold $t_{\text{c}}$ of each class is selected by calculating the F1 score,

$\mathrm{F1}=2\cdot \frac{\text{precision}\cdot \text{recall}}{\text{precision}+\text{recall}},$

for each precision-recall pair and choosing the threshold with the maximum F1 score. Some qualitative results are presented in Fig. 4.18. In each column, examples of a particular class are chosen at random. Examples that are recognized correctly are shown in the first three rows, examples which are recognized as traffic sign but in fact belong to the background or a different class are shown in the next two rows. These bounding box patches can have a similar color or structure. Examples that are not recognized are shown in the last two rows on the bottom. Some of these examples are twisted or covered by stickers.

4.8.4 Computation Time

In the third experiment we evaluate the computation time. Random forests are fast at test time for the classification of a single feature vector. When processing a full image, the random forest is applied to every patch in the feature maps. For an image of size $1080\times 1920$ the feature maps are produced relatively fast using ${\mathrm{CNN}}^{\text{F}}$ and have a size of $268\times 478$ so that $124399$ patches have to be classified to build the output probability map. The images are processed in eight different scales. All together, we measured an average processing time of more than 10 hours for a single image. Although the computation time could be reduced by using a more efficient language than Python, the time to access the memory represents a bottleneck due to a large overhead for accessing and preprocessing each patch.

For processing all in one pipeline, we constructed the fully convolutional network ${\mathrm{CNN}}^{\text{FCN}}$. The network combines feature generation and classification and processes full images in one pass. The time for processing one image in eight different scales is only 4.91 seconds on average. Compared with the patch-wise processing using random forest, using the fully convolutional network reduces the processing time significantly.

4.8.5 Precision of Localizations

The last experiment is designed to demonstrate the localization performance. The localization maps the predicted bounding boxes in the image to positions on the map. Position and heading of a traffic sign are calculated based on the geoinformation of the image and the position and size of the bounding boxes.

For evaluation, we generate ground truth data by manually labeling all traffic signs on the map that are used in our dataset. In the next step, correctly detected traffic signs are matched with the ground truth data. The distance between two GPS-positions is calculated using the haversine formula [40]. The maximal possible difference of the heading is ${90}^{\circ }$ because larger differences would show a traffic sign from the side or from the back. Each traffic sign is assigned to the ground truth traffic sign that has the minimum distance and a heading difference within the possible viewing area of ${90}^{\circ }$. The median of the localization error, i.e. the distance between the estimated position of the traffic sign and its ground truth position, is 6.79 m. Since the recorded GPS-data also includes the inaccuracies of each GPS-position, we can remove traffic signs which are estimated by more inaccurate GPS-positions. If traffic signs with a GPS-inaccuracy larger than the average of 3.79 m are removed, then the median of the localization error decreases to 6.44 m.

The errors of the localizations (y-axis) with respect to the GPS-inaccuracies (x-axis) are plotted in Fig. 4.19A. The orange dots indicate estimated positions of traffic signs. The black lines indicate the medians, the upper and bottom ends of the blue boxes the first and third quantiles. It can be seen that the localization error does not depend on the precision of the GPS-position as it does not increase with the latter. The localization errors (y-axis) with respect to the distances between the positions of the traffic signs and the GPS-positions (x-axis) are shown in Fig. 4.19B. It can be seen that the errors depend on the distance between traffic sign and bicycle as they increase with these distances. This can be explained by the fact that the original inaccuracies of the GPS-position are extrapolated, i.e. the larger the distances, the more the GPS-inaccuracies perturb the localizations.

Since smart phones are used as recording devices, the precision of the GPS-coordinates is lower than those used in GPS-sensors integrated in cars or in high-end devices. As the inaccuracies of the GPS-positions have a large influence on the localizations, we identify multiple observations of the same traffic sign in a clustering process to reduce the localization error. The performance is evaluated as before. The overall median of the localization error improves to 5.75 m. When measuring the performance for all traffic signs which have multiple observations the median of the localization error even decreases to 5.13 m.