\chapter{Introduction}\label{ch:introduction}                         
% \input{Cap1-intro/Cap1-intro} 
% \chapter{Enquadramento}\label{chapter:intro}
\thispagestyle{myheadings}

\section{Motivation} \label{sec: mandf}
Humans are unmistakably the most important components of a machine’s environment. Whenever people are involved in a process with any associated risks, there is a great number of special security rules that must be followed in order to assure their safety. Visual detection of humans is a field with an extensive range of applications such as robotics, entertainment, surveillance, care for the elderly and disabled, road safety and others. In all of these, the knowledge of the presence of a person allows the equipment with whom it’s interacting to act accordingly, be it sounding an alarm, stopping an operation, or any other action. The benefits of this become obvious when we think about a car being driven in an urban scenario. If the circumstances are such that the driver is always aware of the surrounding pedestrians, danger of accidents involving them would most likely decrease dramatically. One could even think of a safety mechanism that refrains a driver's action in a dangerous situation for a pedestrian.\newline
In the European Union, 21\% (European Comission, 2011 \citep{EC_2011}) of all traffic fatalities are pedestrians, indicating that we’re looking at a matter of great importance. Motivated by this, many researchers have devoted much work in developing algorithms for visual human detection, leading to extraordinary improvements in the past decade. Despite those significant improvements, there is still much room for progress due to the challenging nature of the problem. Issues like varying lighting conditions or uncertain pedestrian postures require robust solutions in order to overcome those difficulties. \newline
In this work, an algorithm capable of visually detecting pedestrians achieving close to state-of-the-art detection rate is implemented and exploited. The objective was to build a base detector to be inserted in the \textit{Atlas} project \citep{Atlas_Project}, of the Department of Mechanical Engineering of the University of Aveiro. This is an ongoing team project that started with the aim of participating in autonomous mobile robots competitions and has since then is grown into real road vehicles (Figure 1.1) with the goal of developing new Advanced Driver Assistance Systems (ADAS). Visual detection of pedestrians is an obvious and paramount feature that had yet to be incorporated in the project, making this work a significant contribution. The work presented in this document constitutes a base application that has still much room for improvement in the future, as this is a subject in constant development.


\begin{figure}[H]

  \centering
    \includegraphics[scale=0.5]{Imagens/atlascar.png}
    \caption{\textit {Atlas Car}.\label{fig:atlascar}}  
\end{figure}

    


\section{Description of the Problems}\label{sec:problems}

Visual pedestrian detection is a challenging task with a set of complex problems to overcome. In this section, an overview of some common problems associated with detecting pedestrians in individual monocular images will be presented.\newline
Computer Vision (CV) is a technology that has grown in presence on many fields of society over the past two decades. In industry, product inspection systems have significantly improved with the aid of CV by allowing inspection of parts at a major scale, a fact that lead to considerable advancements in the process of finding defects. In such environments, a careful setup is planned in order to facilitate the processing of the images outputted by the camera, since controlling the lighting level, background color and other external parameters is of utmost importance for an easy object segmentation, meaning, separating the object of interest from the background. \newline
On the contrary, it is virtually impossible to control the external factors of the images where pedestrians must be detected, precluding the possibility of segmentation and causing the need to process cluttered, random images with huge amounts of information. The unpredictability of the location where a pedestrian might come into sight also mandates the analysis of the whole scene. Moreover, the varying nature of the lighting conditions caused either by changes in the daylight, or different weather conditions further hampers the task. Another typical problem that leads to relatively high miss rates is that pedestrians often appear partially occluded by other objects in the scene, such as trees, traffic signs, bikes, and even by other pedestrians. The uncertainty of their posture also constitutes a problem, since it is obvious that an up-right pedestrian has different properties in an image than one sitting down or leaning into another object.\newline
In sum, the mission is to detect pedestrians that might or not be partially occluded, in unpredictable locations, assuming different stances, on cluttered scenes with varying lighting conditions. Such conditions demand highly robust algorithms which are typically heavy and unable to run at the frame-rates that this task demands. Figure 1.2 attempts to illustrate some of these problems.

\begin{figure}[H]

  \centering
    \includegraphics[width=15cm]{Imagens/imgrid.png}
    \caption[Problems associated with pedestrian detection]{Varying lighting conditions, partial occlusion and different postures are some of the problems associated with pedestrian detection. Images taken from the INRIA dataset (Dalal and Triggs, 2005 \citep{Dalal_and_Triggs_2005}).\label{fig:imgrid}}  
\end{figure}

\section{State of the Art}\label{sec:state_of_art}

A great development has been made on the subject of visual pedestrian detection in the past two decades. In this section a compact description of some notorious contributions for this area will follow. This review will focus firstly on detectors with a sliding window approach, often seen as the most promising for low and medium resolution approaches. Secondly, some multi-sensor applications for ADAS will also be analyzed.

\subsection{Sliding Window Detectors}\label{subsec:sliding_window_det}

One of the first sliding window visual object detector attempted to describe an object class in terms of an over-complete dictionary of local, oriented multi-scale intensity differences between adjacent regions; they are known as Haar Wavelets, and are applied to an example-based machine learning approach, where a model of an object class is derived implicitly from a training set of negative and positive examples (Papageorgiou et al., 2000 \citep{Papageorgiou_et_al._2000}). The specific learning engine used is a Support Vector Machine (Cortes and Vapnik, 1995 \citep{Cortes_and_Vapnik_2005}) classifier, and results for car, faces and people detection tasks are shown. Before this work, visual human detection had not yet been successfully tackled, as they would typically assume a number of restrictive assumptions in order to produce results.\newline
Building upon Papageorgiou's ideas, (Viola and Jones, 2001 \citep{Viola_and_Jones_2001}) (VJ) proposed a method that extracted Haar-like features with an highly optimized approach due to the use of integral images, which is an image transformation that allows for rectangular sums of pixels to be computed by fast arithmetic operations. In addition to this, a learning mechanism based on the AdaBoost algorithm (Freund and Schapire, 1999 \citep{Freund_and_Schapire_1999}) was utilized in order to select the most relevant features to perform classification, and a decision structure in the form of a cascade was built for efficient decision-making. This cascade works by evaluating sets of features that grow in complexity as a sample advances in the structure, an idea that stands upon the notion that a positive instance in an image is an extremely rare event. By rejecting most negative samples in the earliest stages of the cascade, this method, applied to face detection, was  able to run at 15 frames per second (FPS) with a high success detection rate. Figure 1.3 shows a schematic representation of the detection cascade.

\begin{figure}[H]

  \centering
    \includegraphics[scale=0.5]{Imagens/Cascade.png}
    \caption[Schematic depiction of a detection cascade]{ Schematic depiction of a detection cascade (Viola and Jones, 2001 \citep{Viola_and_Jones_2001}).\label{fig:cascade}}  
\end{figure}


VJ's work is a popular and widely spread approach that still serves as foundation for many modern detectors, and full implementations of the method were made available in software development tools such as OpenCV and MatLab. In figure 1.4 some example results of the VJ algorithm are shown.

\begin{figure}[H]

  \centering
    \includegraphics[width=15cm]{Imagens/VJ.jpg}
    \caption[Viola and Jones's face detection algorithm]{Viola and Jones's face detection  algorithm (Viola and Jones, 2001 \citep{Viola_and_Jones_2001}).\label{fig:VJ}}  
\end{figure}

Up until this moment, detection algorithms worked mostly on intensity images, a principle that changed when gradient-based features were introduced in the scope of pedestrian detection. Becoming widely known as Histogram of Oriented Gradient (HOG) (Dalal and Triggs, 2005 \citep{Dalal_and_Triggs_2005}), this method attempted to define a scene by dividing it into small spacial regions (cells), and accumulating for each one a local histogram of normalized gradient directions. These cells are combined over slightly larger and overlapping spacial regions (blocks), and each block is also locally normalized for better invariance to lighting conditions. The above-mentioned descriptors are then applied to a trained SVM based window classifier that identifies if a pedestrian is present in the scene or not. Figure 1.5 presents an overview of the HOG algorithm. This contribution resulted in large gains when compared to intensity based methods and, since its introduction, the number of variants of HOG has increased to the point that nearly all modern detectors use some form of these features.

\begin{figure}[H]

  \centering
    \includegraphics[width=15cm]{Imagens/HOG.png}
    \caption[Overview of HOG detection algorithm]{Overview of HOG detection algorithm (Dalal and Triggs, 2005 \citep{Dalal_and_Triggs_2005}).\label{fig:HOG}}  
\end{figure}

Interpretation of shape is also an important cue to the subject. In general terms, shape-based methods work by generating templates of the desired object and finding matches for them in visual data. The work developed by (Gravila and Philomin, 1999 \citep{Gravila_and_Philomin_1999}) was one of the first to adopt this approach in the domain of pedestrian detection. It uses the Hausdorff distance transform and a template hierarchy to rapidly match image edges to a set of shape templates, and tests were made for pedestrian and traffic sign detection with satisfactory results, as shown in figure 1.6. 

\begin{figure}[H]

  \centering
    \includegraphics[scale=0.8]{Imagens/template.jpg}
    \caption[Example results of the shape-based pedestrian detection method]{Example results of the shape-based pedestrian detection method (Gravila and Philomin, 1999) \citep{Gravila_and_Philomin_1999}.\label{fig:template}}  
\end{figure}

Still on this note, (Sabzmeydani and Mori, 2007 \citep{Sabzmeydani_and_Mori_2007}) used gradient-based HOG-like features combined with an AdaBoost engine to learn head, torso, legs and full body shapes. In this approach two kinds of features are used for classification: the low-level features, which are simple and reminiscent to Haar-like features, and mid-level features that are learned part models for template matching. This method is documented to outperform HOG by a considerable margin. \newline
Some researchers have used motion features to further improve detection results. The basic idea is that in an usual situation people are in motion, rather then sitting still. Therefore it is natural to think that if the circumstances are such that detection of motion is achievable, important clues as to the possibility of the presence of pedestrians will be found. It is, however, a challenging task to incorporate motion features into detectors given a moving camera. Given a static camera, (Viola et al., 2005 \citep{Viola_and_Jones_2005}) proposed a similar approach to their previous work, but applied to the result of the difference of two sequential frames, resulting in large performance gains. For non-static imaging setups, camera motion has to be factored out, as did (Dalal et al., 2006 \citep{Dalal_and_Triggs_2006}) when they attempted to model motion statistics based on an optical flow's (Fleet and Weiss, 2006 \citep{Fleet_and_Weiss_2005}) internal differences, thereby compensating for uniform motion locally. \newline
Although HOG has not been outperformed by any single feature, some researchers hypothesized that assembling multiple types of features could provide important complementary information. To prove this, (Wojek and Schiele, 2008 \citep{Wojek_and_Schiele_2008}) combined Haar-like features, shapelets, shape context, and HOG features to compare the resultant detector with each of the features performing on their own, demonstrating that the combo outperforms any single feature detector, as shown in figure 1.7. This framework was later extended to include the above-mentioned motion features in (Walk et al, 2010 \citep{Walk_et_al._2010}), further improving the detection results.

\begin{figure}[H]

  \centering
    \includegraphics[scale=0.5]{Imagens/multiftr.png}
    \caption[Multi-feature detector performance]{Multi-feature detector performance (Wojek and Schiele, 2008 \citep{Wojek_and_Schiele_2008}).\label{fig:multiftr}}  
\end{figure}

Using a different course of action, (Dollár et al., 2009 \citep{Dollar_et_al._2009}) extracted Haar-like features from various channels, including gradient magnitude, LUV color channels and gradient magnitude quantized by orientation, providing a simple framework for integrating multiple feature types. Examples of possible channels are shown in image 1.8. In the author's approach, a large pool of features is extracted from random regions of the channels to guarantee a good characterization of the scene. A decision structure similar to the VJ's method is utilized with the purpose of selecting the most relevant features and performing efficient classification. This method became known as \textit{Integral Channel Features}. A significant optimization was made to this algorithm when the authors hypothesized that features could be approximated at nearby scales with little sacrifice to results (Dollár et al., 2010 \citep{Dollar_et_al._2010}). By eliminating the need to extract features at every scale, this algorithm is documented to perform multi-scale detection at 6 FPS and ranks among the best found in literature. A still better version of this framework was introduced in (Dollár et al., 2012 \citep{Dollar_et_al._2012}), in which an even more efficient decision structure was proposed. In this brand new \textit{Crosstalk Cascades} method, it is established that nearby decision windows have correlated responses. By creating a mean of communication between detector's responses, this method achieves similar detection rates as the \textit{Integral Channel Features} while increasing speed by an order of magnitude.

\begin{figure}[H]

  \centering
    \includegraphics[width=15cm]{Imagens/chn.png}
    \caption[Examples of channels computed from an image]{Examples of channels computed from an image (Dollár et al., 2009 \citep{Dollar_et_al._2009}). \label{fig:chn}}  
\end{figure}

Some authors have made an effort to modify learning engines to improve their speed, as did (Tuzel et al., 2008 \citep{Tuzel_et_al_2008}) by utilizing covariance matrices computed locally over a large diversity of features as object descriptors. The learning data doesn't lie on the vector space, thus improving the learning/testing performance. Non-linear SVM applied to sliding window detection was made possible when (Maji et al., 2008 \citep{Maji_et_al_2008}) found that the use of the learning algorithm with an approximation to the histogram intersection kernel lead to substantial gains in terms of speed.

\subsection{Multi-sensor Detectors}\label{subsec:multi_sensor_det}

Visual data has great potential due to the richness of information it holds. However, it may be a challenging task to build a robust detector to be implemented in an ADAS relying solely on camera output as a result of the problems discussed in the previous section. To overcome those difficulties, some try to ally different type of sensor information to create robust and more reliable detectors.\newline
Infra-red image and laser data were used by (Fardi et al. 2005 \citep{Fardi_et_al._2005}) to generate regions of interest where pedestrians might be at sight. A first-step classification is obtained by evaluating a set of descriptors based on the Euclidean distance of Fourier between objects and reference sets on infra-red visual data, a classification that is later refined by motion features acquired using egomotion sensors and optical flow. \newline
On a different approach, radar, color and infra-red information is fused in (Milch et al., 2005 \citep{Milch_et_al._2001}). In this work, hypothesis are generated through the evaluation of vision-based local histograms on edges, computed both on color and infra-red visual data. Neural Networks is the learning engine used for a preliminary classification, and its output undergoes further verification by a fusion between radar and tracking information.\newline
Combining infra-red and visual spectra from the two camera types was proposed by (Bertozzi et al., 2006-2007 \citep{Bertozzi_et_al_2007}). In the author's work, foreground segmentation is carried out by overlapping 2D and 3D information from both sensors and, finally, symmetry and template matching are used to classify, verify and refine final detections. \newline
Laserscanner-based tracking of points was the strategy chosen by (Premebida et al. 2007 \citep{Premebida_et_al_2007}) to generate candidate regions of interest for further analysis. Objects were defined by laser and visual features, and AdaBoost was utilized for generating responses.\newline
These systems were built in scientific research environments where information is usually made accessible for anyone. That is not the case in industrial environments where, for commercial reasons, conducted research is kept in absolute secret, a circumstance that makes it hard to find reliable sources about the state of this technology in industry. It seems granted, however, that the on of first pedestrian detection system to be commercialized will be launched in 2014 by Mercedes and will be based on stereo camera images (Mercedes press information, 2013 \citep{Mercedes_Press_Information}). A study made by Mercedes shows that their safety mechanism based on pedestrian detection could avoid 6$\%$ of pedestrian accidents and reduce the severity of a further 41$\%$. Volvo was the first, and only to this date, to launch a real pedestrian detection application (Volvo Mobileye Pedestrian Collision Warning, 2012 \citep{Volvo_mob}) to the market. Their mechanism uses monocular image and radar to perform detection, and issues a warning to the driver when there is risk of collision, giving him over two seconds to avoid it. 

\section{Proposed Solution}\label{sec:solution}
Although great advantages arise from fusing different type of sensor information, a multi-sensor approach also has its issues, such as difficulties in fusing and correlating different sensor data, higher registration demands, more complex system implementations, accumulation of errors generated from different sensors, and others. Despite these problems, it is obvious that any real and full-functional pedestrian detector will, most certainly, require the use of multiple sensors as a result of the extremely demanding nature of the task in hands.\newline
However, creating such complex application is a large engineering effort that requires a great deal of know-how, expensive equipment and time, especially when the application is being built from scratch. Although much useful equipment already exists in the laboratory, as well as a staff with a comprehensive knowledge and set of skills, building a full-functional, multi-sensory system cannot the objective due to the short amount of time available to complete this work. The goal was to build a reliable, generic and simple vision-based pedestrian detection framework that leaves the possibility for future development and integration in more complex systems. It was decided then that the implementation of a sliding window algorithm was the way to go, since one can be modified to work with other sensors in future development. \newline
In order to define a course of action, two premises were established: the implemented algorithm should rank among the best in terms of detection performance and should also leave space for future improvements. In respect of this, (Dollár et al, 2012 \citep{Dollar_et_al_2012_survey}) made an extensive survey of existing sliding window detectors, where 16 algorithms were compared against each other in a carefully designed evaluation platform. Out of all the evaluated algorithms, \textit{Integral Channel Features} (\textit{ChnFtr}) proved to be the most interesting for several reasons. Firstly, the only method that slightly outperforms it uses motion and gradient-based features, a computationally heavy approach that is documented to run 50 times slower than \textit{ChnFtr}, rendering it uninteresting. On the contrary, the authors of \textit{ChnFtr} have largely improved its performance in later work, to the point of enabling multi-scale detection at 30 FPS \citep{Dollar_et_al._2010} \citep{Dollar_et_al._2012}. Secondly, the method provides a relatively simple framework in terms of code implementation when compared to other approaches. Since this implementation fitted perfectly with the proposed goal, it was the chosen way to go for this project. \newline
A detailed explanation of \textit{ChnFtr} is presented in chapter 2.


\section{Development Tools}\label{sec:DevTools}

It has become clear that this was mainly a software development project, and, as one would expect, most work involved designing, implementing and testing code. The programming language used was C++ under Linux platform, and, in addition to this, a set of indispensable development tools were utilized, all of which will be enumerated and described in this section.

\subsection{Robotic Operation System}\label{subsec:ROS}

The Robot Operating System (ROS) (Quigley et al., 2009 \citep{Quigley_et_al._2009}) provides a software development framework that is designed for the creation of robot software. This application has several built-in components prepared to handle the output of different types of sensors, such as cameras, lasers, actuators, contacts and other common elements in a robotic environment. \newline
ROS also allows for an easy way to establish communication between different software modules (\textit{nodes}), which permits the elaboration of an infrastructure that can communicate with any running process. This communication works in three steps: first, a \textit{node} advertises a \textit{ROS Topic}. Once that topic of communication is advertised, the same \textit{node} is able to publish messages on that topic, and finally, those messages can be listened by any \textit{node} that subscribes to the same topic. Such messages can be of any kind, from simple strings of characters to visual and laser data. Figure 1.9 tries to illustrate a very simple ROS communication architecture. It is easy to understand that this information exchanging structure has a great potential when applied to robotics, since an uniform and standardized communication between sensors facilitates the development of complex multi-sensor applications. \newline

\begin{figure}[H]

  \centering
    \includegraphics[width=10cm]{Imagens/ROSTopic.jpeg}
    \caption{Schematic of a simple ROS communication architecture.\label{fig:ROSTopic}}  
\end{figure}

Another important feature that ROS provides is the possibility to record data logs (\textit{rosbags}) that can be replayed later. This allows for data to be collected in real scenery, to be later treated in a laboratory environment as if it was on the field. \newline
Recently, to standardize the work developed for the \textit{Atlas} project, an effort has been made to migrate every application to ROS environment and, for this reason, the work presented in this document was also developed in ROS.

\subsection{OpenCV}\label{subsec:OpenCV}

OpenCV is a popular open source computer vision library written in C and C++ that was designed for high computational efficiency and with a strong focus on real-time image processing applications. It provides an infrastructure to help people build fairly sophisticated vision applications, and contains hundreds of functions that span many areas of application, like factory product inspection, security, medical imaging, robotics and many others. This is a well documented, very complete library with a huge and collaborative user community that is in constant growth. Such a healthy and knowledge-sharing environment is a positive aspect that largely contributed for the development of the project. \newline 
In this work many useful OpenCV functions are used for several purposes. Resizing images, computing gradients, converting images between colors spaces or selecting sub-windows from images are just a few examples of operations provided by OpenCV that are absolutely necessary for most visual pedestrian detection applications.

\subsection{INRIA Dataset}\label{subsec:INRIA}

In order to develop detection applications of objects in complex scenes, where segmentation and other similar approaches are not an option, the use of a learning machine algorithm is absolutely necessary.  In a nutshell, these algorithms work by exhaustive learning of positive and negative instances of the problem in question, and once the learning process is finished, they are able to predict on new unseen data. So, in order to develop a detection application, the developer must possess a set of positive examples of the object to be detected, and, to ensure that the learning engine is correctly trained, the number of positive examples usually needs to be large. Acquiring hundreds, sometimes thousands, of positive instances of an object is obviously a slow and time-consuming task, even more when the data needs to be treated and labelled in laboratory. Fortunately, a handful of pedestrian datasets were made public by the scientific community, and anyone is free to use them. \newline
The INRIA dataset was acquired by (Dalal and Triggs, 2005 \citep{Dalal_and_Triggs_2005}) with the objective of setting a challenging framework to test the HOG algorithm. Since then, this dataset has been used by most pedestrian detection researchers, as did the authors of \textit{ChnFtr}. \newline
This dataset provides a training set with 1218 images where no pedestrians appear (negative images), and 2416 positive training windows, meaning, pedestrian images cropped from the original scene in which they appear. The fact that the positive examples are already cropped out of the original images largely facilitated the training process. The dataset also provides a different set of images, with 1132 positive windows and 462 negative images to test the detector performance.\newline
This dataset was of utmost importance for the development of this work, as it not only allowed for a facilitated training/testing process, but also for the implementation of a meaningful evaluation platform to compare results between the original algorithm and the ones achieved in this work. Image 1.10 shows a set of example positive windows from the INRIA dataset.

\begin{figure}[H]

  \centering
    \includegraphics[width=10cm]{Imagens/croptiles.png}
    \caption[Examples of  positive windows]{Examples of positive windows used for training a classifier. In this dataset people appear on a wide variety of backgrounds. \label{fig:croptiles}}  
\end{figure}

\section{Experimental Setup}\label{sec:setup}

The tools described on the previous section integrate an experimental setup that was the base for all the development. A schematic representation of the experimental setup is shown in figure 1.11.\newline 
Having in mind that the end goal of this project was to build an application to run on the \textit{Atlas Car}, it was an important pre-requisite for the setup to be generic enough to allow for full development in laboratory environment, and also be easily set to run on the field.\newline
To fulfill that important pre-requisite, two \textit{nodes} were created. The image server is responsible for advertising an \textit{image transport} topic, loading images from file and publishing those images on the topic. The image client subscribes to that topic and, the event of an image being sent over triggers a callback function that processes and analyses the image using OpenCV.\newline
To test the application on another setting, be it with camera output or \textit{rosbag} replay, one just needs to set the image client to subscribe to the topic in which those instances are publishing. 

\begin{figure}[H]

  \centering
    \includegraphics[width=15cm]{Imagens/ExpSetup.jpeg}
    \caption[Schematic representation of the experimental setup]{Schematic representation of the experimental setup. \label{fig:exp-setup}}  
\end{figure}