\chapter{Classification}\label{ch: classification}  
\thispagestyle{myheadings}

Searching for an object in a scene demands for a method capable of evaluating the feature vectors that describe it. This can be done through the implementation of a Machine Learning (ML) mechanism. The purpose of ML is to turn data into information, a process that becomes fundamental when the information has to be inferred from large amounts of data, much like the case of the problem in hands. Typically, these methods attempt to model an object class from a training set of examples to then make predictions on new and unseen data, or, in other words, perform classification.\newline
There are multiple ML methods, each with its specifications and applications, so, one must choose a method that correctly fits the problem. The adopted method needs to classify between two classes, \textit{Pedestrian} and \textit{Not Pedestrian}, needs to handle thousands of features per sample and should also be fairly resistant to over-fitting. The method that best fits these requirements is AdaBoost, and a compact description will be carried out in the following section.
The basic idea behind AdaBoost, short for Adaptive Boosting, is that it is possible to generate a very accurate prediction rule, or \textit{strong classifier}, through the aggregation of rough and moderately inaccurate linear rules, \textit{weak classifiers}, provided that they perform just slightly better than a random classifier would. A graphic illustration of this is shown in figure 3.1.\newline

\begin{figure}[H]
  \centering
    \includegraphics[scale=0.7]{Imagens/Adaboost.jpg}
    \caption[Aggregation of \textit{weak classifiers}]{Aggregation of \textit{weak classifiers}: in this example, each black line represents a \textit{weak classifier} that attempts to distinguish red from blue dots. It is easy to understand that each \textit{weak classifier} doesn't perform well on its own, whereas a combination of the 5 \textit{weak classifiers} will correctly label most samples. \label{fig:adaboost}}  
\end{figure}
\section{AdaBoost}\label{sec: adaboost}
This algorithm takes as input a  training set \textit{(x$_{1}$,y$_{1}$),..., (x$_{m}$,y$_{m}$)}, where \textit{x$_{i}$} belongs to the domain \textit{X}, and refers to a feature vector; \textit{y$_{i}$} refers to the label of the corresponding sample, and belongs to \textit{Y=$\lbrace$-1, +1$\rbrace$}. AdaBoost calls a \textit{weak learning} algorithm over and over again in a series of rounds \textit{t= 1,...,T}. One of the key points of this method is to maintain a distribution set of weights over a training set, which are set uniformly in the first iteration. The weight of this distribution on a training example \textit{i} on round \textit{t} is denoted \textit{D$_t$(i)}. At the starting point, all weights are set uniformly but, on each iteration, the weights of incorrectly classified examples are increased in an attempt to force the algorithm to give them a special attention, and this is why the method is called Adpative Boosting, since it adapts iteratively to focus on hard examples. The \textit{weak learner's} function is to find a \textit{weak classifier}: \textit{h$_t$: X $\longrightarrow$ $\lbrace$-1,+1 $\rbrace$}, appropriate for the weight distribution D$_t$. A \textit{weak classifier} is evaluated by its error, calculated according the equation 3.1.
\begin{equation}
\epsilon_t = \sum_{i:h_t (x_i) \neq y_i}D_t (i)
\end{equation}
Once an hypothesis h$_t$ has been set, AdaBoost chooses a parameter $\alpha_t$, which is a measure of the importance of the learned \textit{weak classifier}, and is calculated according to the equation 3.2.
\begin{equation}
\alpha_t = \frac{1}{2}ln\left(\frac{1-\epsilon_t}{\epsilon_t}\right)
\end{equation}
 Note that $\alpha_t$ > 0 if $\epsilon_t$<1/2, meaning, a \textit{weak classifier} is only attributed with importance if it gets atleast half of the training examples right. It is also intuitive that a \textit{weak classifier} is as more important as lower its error is. The distribution D$_t$ is then updated according to the rule illustrated by equation 3.3, in which the denominator is a normalization factor used to ensure that D$_{t+1}$ is a probability distribution. 
\begin{equation}
D_{t+1}(i) = \frac{D_{t}(i) exp(-\alpha_t y_i h_t (x_i))}{\sum_i D_{t}(i) exp(-\alpha_t y_i h_t (x_i))}
\end{equation}
This rule assures that the misclassified examples are attributed with more weight so that in the next iteration they can be resolved.\newline
The final hypothesis \textit{H} is a majority weighted vote of the \textit{T} \textit{weak classifiers}, as show in equation 3.4.
\begin{equation}
H(x)=sign\left(\sum_{t=1}^T \alpha_t h_t (x)\right)
\end{equation}
Or equation 3.5 to obtain a measure of the confidence of the detector
\begin{equation}
H(x)=\sum_{t=1}^T \alpha_t h_t (x)
\end{equation}
This whole process is summed up in algorithm 1.\newline

\begin{algorithm}[H]
\caption{The boosting algorithm AdaBoost}
\textbf{Given} (x$_{1}$,y$_{1}$),..., (x$_{m}$,y$_{m}$) where x$_i$ $\in$ X, y$_i$ $\in$ Y = $\lbrace$-1,1 $\rbrace$ \newline
\textbf{Initialize} D$_1$(i)=$\displaystyle\frac{1}{m}$ \newline
\textbf{For} t=1,...,T: \newline
\begin{itemize}
\item Train weak learner using distribution D$_t$
\item Get weak hypothesis with error: \newline
\begin{center}
$\displaystyle\epsilon_t = \sum_{i:h_t (x_i) \neq y_i}D_t (i)$
\end{center}
\item Choose $\displaystyle\alpha_t = \frac{1}{2}ln\left(\frac{1-\epsilon_t}{\epsilon_t}\right)$
\item Update:\newline
\begin{center}
$\displaystyle D_{t+1}(i) = \frac{D_{t}(i) exp(-\alpha_t y_i h_t (x_i))}{\sum_i D_{t}(i) exp(-\alpha_t y_i h_t (x_i))}$
\end{center}

\end{itemize}
\textbf{Output of the final hypotheses:}
\begin{center}

$\displaystyle H(x)=sign\left(\sum_{t=1}^T \alpha_t h_t (x)\right)$
\end{center}

\end{algorithm}


\section{Training Process} \label{sec: training}

OpenCV provides an implementation of AdaBoost, so there was no need to build one from scratch. The most relevant aspects of the training process of the final classifier are discussed in this section.

\subsection{Training Samples} \label{subsec: smaples}
OpenCV's AdaBoost training method uses a matrix containing the training data as input, and outputs a classifier that can later be used to perform detection in new samples. The most convenient way to prepare the data is to write it to a text file and only later convert it into a matrix. So, simple changes had to be made to the infrastructure to enable the writing of feature vectors in file. \newline
Selecting the training samples of the final classifier is done in three stages. The first stage classifier is trained with the 2416 positive training windows available on the INRIA dataset and $\sim$5000 negative windows generated randomly from a wide variety of negative images. The resulting classifier is then tested on the same negative images, and this time $\sim$5000 false positives are added to the training data as negative examples, forcing the classifier to learn the hard examples, a process that is known as \textit{bootstrapping}. Finally, a final round of \textit{bootstrapping} is performed where more $\sim$5000 hard negatives are added to the training data. In sum, The final classifier has 2416 positives examples and $\sim$15000 negative examples, $\sim$10000 of which are samples that were incorrectly classified as positive by the first 2 stage classifiers.

\subsection{Classifier Parametrization} \label{subsec: classparms}

There are a few additional parameters important for training the classifier. The number of features to be computed per window is a key factor that has a major effect on the detector's performance. To understand how the size of the feature pool affects results, two classifiers were trained, one with 10000 features and another with 15000. Note that a classifier trained with a given number of features has to be fed with that same number of features in order to produce a response during test time.\newline
The number of \textit{weak classifiers} is also an important parameter. As explained before, each \textit{weak classifier} will contribute with a weighted vote for each decision. This parameter is set to 2000, which means that 2000 \textit{weak classifiers}  are derived from the feature pool.\newline
The final parameter is the depth of the classifier, which is set to 2. This parameters defines the number of features that constitute each \textit{weak classifier}. Depth 1 uses one feature per \textit{weak classifier} while depth 2 uses three features per \textit{weak classifier}.\newline
In practical terms, the OpenCV boost training method will go through the training data for 2000 iterations, and in each iteration will select the combination of 3 features that best classifies the training data. Table 3.1 gives a summary of the classifier's parameters.

\begin{table}[H]
\centering
\begin{tabular}{ |l|r| }
\hline
\multicolumn{2}{ |c| }{\large{\textbf{Adaboost Classifier}}} \\ \hline
Positive class & Pedestrian \\ \hline
Negative class & Non pedestrian \\ \hline
\multirow{2}{*} {Feature pool size} & 15000 \\ & 10000 \\ \hline
Positive samples & 2416 \\ \hline
Negative random samples & $\sim$5000 \\ \hline
Negative  \textit{bootstrapped} samples & $\sim$10000 \\ \hline
\textit{Weak classifiers} & 2000\\ \hline
Depth & 2\\ \hline

\end{tabular} \label{tab_class_sum}
\caption{AdaBoost parameters}
\end{table}

\section{Post Processing} \label{sec: postprocess}

In full image analysis, it is necessary to keep track of the windows that are classified as positive in order to draw rectangles around detected pedestrians. Since feature extraction and classification are processes that occur on par, it was necessary to create a data structure to accumulate the image coordinates of the positive windows, as well as the scale at which they were obtained in order to transform them to the original scale. As one would expect, in a multi-scale detection platform an object is often detected multiple times, generating multiple rectangles, as shown in figure 3.2. It was then important to find a way to group rectangles that belong to the same object together. Fortunately, since this is a common detection problem, OpenCV provides a way to merge rectangles with similar sizes and locations, and the resulting output is illustrated by figure 3.3.

\begin{figure}[H]
  \centering
    \includegraphics[width=10cm]{Imagens/good.jpg}
    \caption[Rectangles generated by the detector]{Rectangles generated by the detector. \label{fig:goodrect}}  
\end{figure}

\begin{figure}[H]
  \centering
    \includegraphics[width=10cm]{Imagens/vgood.jpg}
    \caption[Merged rectangles]{Merged rectangles. \label{fig:vgoodrect}}  
\end{figure}

\section{Computation Time} \label{sec: time}

In the original implementation of \textit{ChnFtrs}, classification is done through a cascade of boosted classifiers. Each stage of the cascade grows in complexity and evaluates more features. So, if at any point in the cascade a sample is rejected, the detector stops evaluating features and goes on to the next window. In one 640x480 image there are $\sim$60000 windows to evaluate, and, on average, less then 0.1$\%$ of those windows will be positive for pedestrian, so, it follows that if most negative windows can be rejected by evaluating a small set of features, the algorithm will speed up by multiple orders of magnitude. Indeed, the cascade of boosted classifiers is the major key point for the speed of the detector, however, a great deal of complexity lies in training one and there are no standard tools that offer a ready to use implementation. Due to the short amount of time available to develop this project, it was not possible to implement a cascade. Instead, one big boosted classifier is utilized, largely sacrificing speed since the detector evaluates the whole set of features for every single detection window. In this setting, each image takes $\sim$20 seconds to be fully processed and classified if 15000 features are extracted per window.\newline
However, given that the results in terms of detection rate do not vary much between both approaches, the validation of the method is not in question. Figure 3.4 illustrates the differences between a single boosted classifier and a cascade of boosted classifiers.

\begin{figure}[H]
  \centering
    \includegraphics[scale=0.8]{Imagens/casc.png}
    \caption[Difference between single boosted classifier and a cascade]{Difference between single boosted classifier and a cascade (Grossmann, 2004 \citep{Grossmann_2004}). \label{fig:casc}}  
\end{figure}
\newpage\null\thispagestyle{myheadings}\newpage