\chapter{Integral Channel Features}\label{ch: Chnftrs}  
\thispagestyle{myheadings}

To solve a complex vision detection problem it is necessary to perform exhaustive descriptions of the objects in order to find a set of descriptors that present significant variability in their presence. The proposed solution takes advantage of the richness of information present in multiple channels of an image, using it to assemble different detection techniques in a simple framework. By evaluating a very large number of simple features from multiple channels, this algorithm integrates normal, HOG-like, shape-based and other feature types in an indirect manner and, not only that, those features can be extracted in an optimized manner with the use of the integral images. These are the reasons as to why \textit{Integral Channel Features} (\textit{ChnFtr}) has so much potential, since it allies multi-feature analysis and speed in a relatively simple infrastructure. 
\textit{ChnFtr} is divided into three main parts:

\begin{enumerate}
  \item Computation of channels
  \item Feature extraction
  \item Classification
\end{enumerate}

In this chapter items 1 and 2 will be discussed, leaving the topic of classification for the next chapter.
%\textit{Integral Channel Features} (\textit{ChnFtr}) is a promising algorithm that 

\section{Channels}\label{sec: channels}

In the context of this work, a channel of an image is a representation of the original, where the output pixels are obtained by using linear or non-linear transformations on the input ones, thus preserving the overall image layout. A trivial channel is the grayscale representation of an image, and, likewise, the different color channels of an image can also serve as channels in this context. \newline
There are countless transformations that can be applied to an image that will result in new channels; application of filters, binary thresholds and edge detectors are just a few examples of simple ways to obtain numerous channels. However, our human perception only goes so far when it comes to realize which channels will contribute with more relevant information for detection. The only way to complete such a task is to test various channels for performance and check which are more informative by evaluating results. \newline
Fortunately, that information is already available in the original publication, where the detection performance of different channels were put against each other. As shown in figure 2.1, the conclusions that were drawn from that study were that the channels that lead to the best results are the gradient magnitude, gradient histogram (labelled \textit{Hist} in figure 2.1) and the LUV color channels. For this obvious reason, these channels were the ones used, and will be described in the following sub-sections.\newline


\begin{figure}[H]

  \centering
    \includegraphics[width=8cm]{Imagens/ComboGraph.png}
    \caption[Channel combination]{Detection performance of different channel combinations (Dollár et al., 2009 \citep{Dollar_et_al._2009}). \label{fig:combograph}}  
\end{figure}

\subsection{Gradient Magnitude}\label{subsec: gradmag}

Given an input image \textit{I}, the gradient magnitude (\textit{GM}) of \textit{I} is a representation of the strength of its edges. The channel is computed as shown in equation 2.1, in which $\displaystyle\frac{\delta I}{\delta x}$ and $\displaystyle\frac{\delta I}{\delta y}$ are respectively the horizontal and vertical gradients of \textit{I}.
\begin{equation}
 GM(x,y) = \sqrt{\left(\frac{\delta I}{\delta x}(x,y)\right)^2 + \left(\frac{\delta I}{\delta y}(x,y)\right)^2 }
\end{equation}
In terms of code implementation, the horizontal and vertical gradients are computed by applying a simple \textit{Sobel} operator. The gradients are then squared, summed and finally square rooted for the final result. Figure 2.2 describes how this is processed in the code. 

\begin{figure}[H]

  \centering
    \includegraphics[width=15cm]{Imagens/GradMag.jpg}
    \caption[Gradient magnitude computation]{Gradient magnitude computation. \label{fig:gradmag}}  
\end{figure}

\subsection{Gradient Histogram}\label{subsec: gradori}

A gradient histogram is a weighted histogram where bin index is determined by gradient angle and weighted by gradient magnitude, providing important information about edge strength under different pixel orientations. The only parameter for computing gradient histogram is the number of bin orientations, knowing that each bin generates a separate channel. This parameter is set to 6, which is the number from which the results stop improving, as shown in picture 2.3.

\begin{figure}[H]

  \centering
    \includegraphics[width=8cm]{Imagens/binnumber.png}
    \caption[Detection performance of different numbers of bin orientations]{Detection performance of different numbers of bin orientations (Dollár et al., 2009 \citep{Dollar_et_al._2009}). \label{fig:binnumber}}  
\end{figure}

The orientation at each pixel is calculated according to equation 2.2. 
\begin{equation}
 \theta (x,y)= arctan\left( \frac{\frac{\displaystyle\delta I}{\displaystyle\delta y}(x,y)}{\frac{\displaystyle\delta I}{\displaystyle\delta x}(x,y)}\right) 
\end{equation}
Concerning the code implementation, the horizontal and vertical gradients obtained before are used to compute quotients between the gradients, which are stored in a new data structure. Then, the orientation for each pixel is calculated and a heuristic structure is built to accumulate the previously computed gradient magnitude values on different bins depending on the value of $\theta$. A schematic description of how gradient histogram bins are processed in the code is shown on figure 2.4.

\begin{figure}[H]

  \centering
    \includegraphics[width=15cm]{Imagens/OriGrad.jpg}
    \caption[Gradient histogram computation]{Gradient histogram computation.  \label{fig:histcomp}}  
\end{figure}

\subsection{LUV color channels}\label{subsec: luv}

Color is an important cue for detection. In respect of this, different color spaces were compared against in order to find out which is more informative; this a comparison lead to the conclusion that the LUV color channels are the ones that provide the best results, as show in figure 2.5. \newline
Obtaining these channels is done with few lines of code, since OpenCV provides a straightforward way to convert images between color spaces. Figure 2.6 illustrates how the channels are computed code-wise.


\begin{figure}[H]

  \centering
    \includegraphics[width=8cm]{Imagens/colochn.png}
    \caption[Detection performance of different color channels]{Detection performance of different color channels (Dollár et al., 2009 \citep{Dollar_et_al._2009}). \label{fig:colorchn}}  
\end{figure}

\begin{figure}[H]

  \centering
    \includegraphics[width=10cm]{Imagens/LUV.jpg}
    \caption[LUV color channels computation]{LUV color channels computation. \label{fig:luvcomp}}  
\end{figure}


\section{Integral Images}\label{sec: integralim}

There is a middle step between computation of channels and feature extraction. Since a scene description is done through the computation of great amounts of rectangular sums of pixels, it is convenient to use a optimized way for computing local sums. This is done with the use of the integral image, and is a key point of the algorithm.\newline
The integral image is an image transformation that allows efficient generation of sums of pixel values in a rectangular subset of an image. Given an input image \textit{I}, the value at any point (x,y) in the integral image \textit{Int} is just the sum of all pixels above and to the left of (x,y), as illustrated in equation 2.3.

\begin{equation}
 Int(x,y)= \sum_{\substack{
   x'\leq x \\
   y'\leq y
  }}
 I(x',y')
\end{equation}
Then, the sum of any rectangular region of the image can be calculated by a simple arithmetic operation, as illustrated in figure 2.7.
\begin{figure}[H]

  \centering
    \includegraphics[width=5cm]{Imagens/intim.jpg}
    \caption[Finding the sum of a rectangular region]{Finding the sum of a rectangular region (Viola and Jones, 2001 \citep{Viola_and_Jones_2001}). In this example, the value of the summed pixels in area \textit{D} is \textit{Int(4)+Int(1)-Int(2)-Int(3).}\label{fig:intim}}  
\end{figure}

OpenCV already provides a way for computing integral images automatically, making it unnecessary to implement this operator by hand. The 10 channels (1 gradient magnitude, 6 bins of orientation and 3 color channels) are transformed into integral images, and the resulting transformations are referred as \textit{Integral Channels}.

\section{Feature extraction}\label{sec: ftrext}

Sliding window detection is performed by applying a Detection Window (DW) over the image, evaluating a set of features, and then sliding it to an adjacent place to repeat the process. The DW has constant dimensions (64x128 as in most sliding window detection methods), so, in order to find pedestrians with different sizes the image has to be rescaled and re-analysed multiple times. This compact description of a generic multi-scale sliding window detector shows that defining how a DW is analysed is a major key point for detection. This section will focus on feature extraction from DWs.\newline
There are distinct approaches for describing a DW. Some researchers opt to generate a fine tuned pool of features  that are subject to tests until they achieve good results. This is the case of the HOG algorithm, where features are made of local sums calculated over a dense overlapping grid in the DW. On the contrary, rather then carefully designing a feature space, \textit{ChnFtrs} generates random features from the channels, knowing that a good characterization of the DW is most likely granted if the feature pool is large enough.\newline
In the context of this work, a feature is no more than a rectangular sum of pixels, and each feature has the following random parameters: the channel where it is calculated, the starting position of the rectangle and its dimensions. To make this more clear, an illustration of 20 possible random features is shown in figure 2.8. One is inclined to think that thousands of random features are likely to lead to a strong and robust characterization of a DW.

\begin{figure}[H]
  \centering
    \includegraphics[width=10cm]{Imagens/Ftrs.jpg}
    \caption[Examples of random features]{Examples of random features: in this illustration, the black rectangles represent the DW over the 10 channels, and the red rectangles represent examples of random rectangles over which local sums are calculated. \label{fig:ftrs}}  
\end{figure}

To extract any number of random features, it is necessary to generate their parameters first. In terms of code implementation, a vector data structure was created in which each element has information about the 5 random parameters necessary to define a rectangle:
\begin{itemize}
  \item Channel index
  \item Width
  \item Height
  \item X coordinate of the upper-left corner of the rectangle
  \item Y coordinate of the upper-left corner of the rectangle
\end{itemize}
Then, a function to initialize the vector with N random parameters was created. Keeping in mind that even if the parameters are random, it is vital that the program is able to reproduce the same parameter vector any number of times. To achieve this, OpenCV provides an \textit{RNG} (Random Number Generator) class that is initialized with a seed. If the seed is the same, the random parameters generated will also be the same.\newline
For each element of the vector, the following random parameters are generated:
\begin{itemize}
  \item Random(0,9) - channel index
  \item Random(5,DW width) - rectangle width
  \item Random(5,DW height) - rectangle height
  \item Random(0,DW width-rectangle width) - X coordinate
  \item Random(0,DW height-rectangle height) - Y coordinate
\end{itemize}
This process occurs once when the program is initiated, and the resulting parameter vector's elements are accessed when a DW is processed.\newline
The integral channels and feature parameter information is all that is necessary to compute features over a DW. In what concerns the code implementation, for every random parameter, a rectangle is defined and the local sum is computed and stored in a feature vector. The resulting vector characterizes the DW feature-wise.

\section{Multi-scale Image Analysis}\label{sec: multi-scale }

Once feature extraction from DWs is set, the next step is to build an architecture for full image analysis. As it was mentioned before, it is essential to analyse not only the entire image, but the same image at multiple scales to find pedestrians with multiple sizes. It is then necessary to build a dense image pyramid (figure 2.9) for analysis.
\begin{figure}[H]
  \centering
    \includegraphics[scale=0.68]{Imagens/imgpyr.png}
    \caption[Dense image pyramid]{Dense image pyramid (Dollár et al., 2010 \citep{Dollar_et_al._2010}). The green rectangle represents the DW of constant dimensions. \label{fig:imgpyr}}  
\end{figure}

There are a few parameters for building this pyramid, all of which are easily changeable.\newline
At each step the image is rescaled depending on the number of scales per octave (\textit{nPerOct}), and its default value is set to 8. An octave is the necessary scaling to rescale the image by a factor of 2. So, each downsampled image is rescaled according to equation 2.4, and for upsampling the logic is the same (equation 2.5).

\begin{equation}
 DownScale=2^\frac{-1}{nPerOct}
\end{equation}

\begin{equation}
 UpScale=2^\frac{1}{nPerOct}
\end{equation}
For 640x480 images, upsampling becomes a computationally heavy operation that is performed when detection of far scale pedestrians is a requisite, so, it is turned off by default. Downsampling goes on until the image reaches a parametrizable minimum size, which default value is set to the same of the DW (64x128). \newline
All that remains is to slide a DW through all the images in the pyramid and store a feature vector for every DW analysed. The default value for the step by which the DW slides through an image is set to 4 (in both directions), which is the step used in the original implementation.\newline
With the default parameters described in this section, each 640x480 image has $\sim$60000 DWs and takes $\sim$0.8 seconds to be processed if 1000 features are extracted per DW, in an Intel core i7 processor. The processing time grows fairly linearly with the number of features computed, taking $\sim$1.6 seconds for 2000 features and so on.\newline
Regarding the code implementation, a cyclic architecture described by figure 2.10 was built.

\begin{figure}[H]
  \centering
    \includegraphics[width=15cm]{Imagens/multicycle.jpeg}
    \caption[Multi-scale image processing]{Multi-scale image processing. \label{fig:multicycle}}  
\end{figure}

\section{Parametrization Summary}\label{sec: summary }

For an easy overview of the work so far, this section provides a table that summarizes the parametrization of the algorithm.

\begin{table}[H]
\centering
\begin{tabular}{ |l|r| }
\hline
\multicolumn{2}{ |c| }{\large{\textbf{ Integral Channel Features}}} \\ \hline
\multirow{3}{*} {Channel types} & Gradient magnitude \\ & Gradient histogram \\ & LUV color\\ \hline
DW size (w x h) & 64 x 128 \\ \hline
min. feature size (w x h) & 5 x 5 \\ \hline
max. feature size (w x h) & 64 x 128 \\ \hline
Number of scales per octave & 8\\ \hline
max. scaled image size (w x h) & 640 x 480\\ \hline
min. scaled image size (w x h) & 64 x 128\\ \hline
Sliding DW step & 4\\ \hline

\end{tabular} \label{tab_sum}
\caption{Default parametrization summary }
\end{table}

These parameters are default values that are defined in a header file. The program is prepared to run cleanly for any parametrization. So, for running the application with different parameters, one just needs to change the header file definitions.\newline
