\chapter{Experiments}
\label{sec:learnmatch_experiments}
We performed a number of experiments in order to validate the approach described in this chapter. Our method is applicable to general object models and transformations, but for the purposes of our experiments we consider the case of a planar object model detected in an image under a homography transformation.

\begin{figure}[hp]
\centering
\begin{subfigure}[b]{\textwidth}
\centering
\includegraphics[width=0.32\textwidth]{images/barbapapa/1.png}
\includegraphics[width=0.32\textwidth]{images/barbapapa/2.png}
\includegraphics[width=0.32\textwidth]{images/barbapapa/3.png}
\caption{\emph{barbapapa}}
\end{subfigure}
\begin{subfigure}[b]{\textwidth}
\centering
\includegraphics[width=0.32\textwidth]{images/comic/1.png}
\includegraphics[width=0.32\textwidth]{images/comic/3.png}
\includegraphics[width=0.32\textwidth]{images/comic/4.png}
\caption{\emph{comic}}
\end{subfigure}
\begin{subfigure}[b]{\textwidth}
\centering
\includegraphics[width=0.32\textwidth]{images/map/1.png}
\includegraphics[width=0.32\textwidth]{images/map/2.png}
\includegraphics[width=0.32\textwidth]{images/map/3.png}
\caption{\emph{map}}
\end{subfigure}
\begin{subfigure}[b]{\textwidth}
\centering
\includegraphics[width=0.32\textwidth]{images/paper/1.png}
\includegraphics[width=0.32\textwidth]{images/paper/2.png}
\includegraphics[width=0.32\textwidth]{images/paper/3.png}
\caption{\emph{paper}}
\end{subfigure}
\begin{subfigure}[b]{\textwidth}
\centering
\includegraphics[width=0.32\textwidth]{images/phone/1.png}
\includegraphics[width=0.32\textwidth]{images/phone/3.png}
\includegraphics[width=0.32\textwidth]{images/phone/4.png}
\caption{\emph{phone}}
\end{subfigure}
\caption[Example frames from our test sequences]{Example frames from our test sequences, which also show the ground-truth homography. These sequences are challenging for keypoint-based detection approaches due to the presence of many similar features in the scene.}
\label{fig:learnmatch_example_frames}
\end{figure}

We recorded a number of video sequences of a static scene observed from a moving camera, using a SLAM system to track the 3D camera pose in each frame (example frames can be seen in Figure \ref{fig:learnmatch_example_frames}). Each sequence begins with a fronto-parallel view of a planar patch, which is used in our experiments to define the object model. Using the known camera pose, we computed a ground-truth homography for the object in each video frame, which is then used for evaluating the quality of the homography estimates produced during object detection in our experiments.

Our experiments all consider the task of tracking-by-detection, as described in Section \ref{sec:learnmatch_online_learning}, in which the target object should be detected in consecutive frames of a video sequence. For this task we do not use any information about the location of the object in the previous frame when detecting the object, but we use each successful detection in order to perform an online learning step to update our object model for subsequent frames. For each sequence, we initialise a model using the fronto-parallel planar patch in the first frame, by detecting the 100 strongest features to define the locations of model keypoints $\mathcal{M}$. The weight vector $\vt{w}_j$ for each model keypoint is initialised by setting it to the descriptor extracted for each model keypoint in the first frame.

When learning with binary descriptors, we apply the feature transformation $\tilde{\vt{d}} = (\vt{d} - \vt{0.5})/0.5\sqrt{D}$, where $D$ is the dimensionality of the descriptor, which centres and normalises the descriptors, as this is known to improve the performance of stochastic gradient descent algorithms \cite{LeCun1998}. During matching this transformation can easily be handled implicitly in the binary approximation without any overhead. We fix the SVM learning rate $\lambda = 0.1$ for all experiments. We also set $\nu = 1$ for the structured model.

In our experiments, we measure detection accuracy using the homography distance $d_{homography}(T,T')$ \eqref{eqn:learnmatch_homog_similarity} introduced in Section \ref{sec:learnmatch_loss_functions}. Using this distance, we are able to quantitatively assess how the predicted object homography compares with the ground-truth homography in each frame of our test sequences.

The unoptimised C++ implementation of our approach as well as the annotated videos used during our experiments are publicly available to download\footnote{\url{http://www.samhare.net/research}.}.

\section{Loss functions}\label{sec:learnmatch_results_loss}

Our first set of experiments aim to investigate which of the loss functions proposed in Section \ref{sec:learnmatch_loss_functions} results in the best tracking-by-detection performance in our framework. For these experiment we use the BRISK detector with 512-bit BRISK descriptor, without using our binary approximation method.

Figure \ref{fig:learnmatch_precision_loss} shows precision plots obtained for each of our test sequences when using the three loss functions described in Section \ref{sec:learnmatch_loss_functions}. These plots show the percentage of frames for which the homography distance $d_{homography}(T,T')$ between the detected homography and ground-truth homography is less than a particular threshold. Frames in which no detection is found are considered to have infinite distance, which is why these plots do not reach a precision of 1. From these plots we can see that overall the performance with all three loss functions is quite similar, but that the $\Delta_{inliers}$ loss function is able to consistently produce the highest detection precision on our test sequences. On the \emph{comic} sequence, in particular, this loss function results in significantly improved performance. Another advantage of this loss function is that, unlike $\Delta_{homography}$, it is valid for all classes of transformations, since it is computed in terms of correspondences only. Therefore this can be considered a general-purpose loss function for our approach.

\begin{figure}[p]
\centering
\begin{subfigure}[b]{0.47\textwidth}
\centering
\includegraphics[width=\textwidth]{images/precision_loss_barbapapa.png}
\caption{\emph{barbapapa}}
\end{subfigure}
\begin{subfigure}[b]{0.47\textwidth}
\centering
\includegraphics[width=\textwidth]{images/precision_loss_comic.png}
\caption{\emph{comic}}
\end{subfigure}

\begin{subfigure}[b]{0.47\textwidth}
\centering
\includegraphics[width=\textwidth]{images/precision_loss_map.png}
\caption{\emph{map}}
\end{subfigure}
\begin{subfigure}[b]{0.47\textwidth}
\centering
\includegraphics[width=\textwidth]{images/precision_loss_paper.png}
\caption{\emph{paper}}
\end{subfigure}

\begin{subfigure}[b]{0.47\textwidth}
\centering
\includegraphics[width=\textwidth]{images/precision_loss_phone.png}
\caption{\emph{phone}}
\end{subfigure}

\caption[Precision plots comparing loss functions]{Precision plots comparing loss functions. These plots show the percentage of frames for which the homography distance $d_{homography}(T,T')$ defined in Section \ref{sec:learnmatch_loss_functions} between the detected homography and ground-truth homography is less than a particular threshold.}
\label{fig:learnmatch_precision_loss}
\end{figure}


\section{Effect of structured learning}\label{sec:learnmatch_results_tracking_detection}

Our next set of experiments investigate the applicability of our approach to various descriptor types, and explores the contribution of our structured learning framework, compared with independent classification for keypoint matching. Based on the results of the previous section, for all these experiments we use the loss function $\Delta_{inliers}$.

To provide a baseline with which to compare our method, we implemented a modification of our framework consisting of independent online SVM classifiers for each model keypoint. This modification takes away the coupling between model points that comes from our model and trains each SVM classifier independently of one another. At run-time, this approach computes a matching score for the $j$-th model keypoint using the learned SVM classifier as $f_j(\vt{d}_k) = \langle \vt{w}_j, \vt{d}_k \rangle$ and uses this score to find the highest scoring match to construct the correspondence set for pose estimation. To update each classifier, each inlier returned from the geometric verification set is taken as a positive training example, and the next highest scoring match for the model keypoint is taken as a negative example. We then perform a stochastic gradient descent step to update the classifier.

We apply our approach using three different combinations of interest point detector and descriptor: FAST detector with 256-bit BRIEF descriptor, BRISK detector with 512-bit BRISK descriptor and SURF detector with SURF64 descriptor. These have been chosen to illustrate that our method works with a variety of feature point detectors and descriptors, but as they each have different invariances and dimensionality, our results should not be interpreted as a comparison between different descriptor types. Therefore, we are interested in relative performance figures for a particular feature point detector and descriptor combination.

To provide an additional baseline, we implemented the boosting-based classification approach proposed by Grabner \etal \cite{Grabner2007}, by making use of the publicly available online boosting code provided by the authors\footnote{\url{http://www.vision.ee.ethz.ch/boostingTrackers/onlineBoosting.htm}.}. We train these classifiers in the same manner as our independent SVM baseline.


%To assess detection performance, we define a scoring function between the ground-truth homography $T^*$ and the predicted homography $T$ as: 
%\begin{equation}
%S(T^*,T) = \frac{1}{4}\sum_{i=1}^4 \|\vt{c}_i - (T^* T^{-1})(\vt{c}_i)\|_2,
%\end{equation}
%where $\{\vt{c}_i\}_{i=1}^4 = \{(-1,-1)\transp, (1,-1)\transp, (-1,1)\transp, (1,1)\transp\}$ define the corners of a square. This score will be $0$ if the two homographies are identical. Frames for which $S(T^*,T) < 10$ are considered correct detections and we report the average over the entire sequence. 

\begin{figure}[p]
\centering
\begin{subfigure}[b]{\textwidth}
\centering
\includegraphics[width=0.32\textwidth]{images/precision_brief_barbapapa.png}
\includegraphics[width=0.32\textwidth]{images/precision_brief_comic.png}
\includegraphics[width=0.32\textwidth]{images/precision_brief_map.png}
\includegraphics[width=0.32\textwidth]{images/precision_brief_paper.png}
\includegraphics[width=0.32\textwidth]{images/precision_brief_phone.png}
\caption{FAST detector with 256-bit BRIEF descriptor}
\end{subfigure}

\begin{subfigure}[b]{\textwidth}
\centering
\includegraphics[width=0.32\textwidth]{images/precision_brisk_barbapapa.png}
\includegraphics[width=0.32\textwidth]{images/precision_brisk_comic.png}
\includegraphics[width=0.32\textwidth]{images/precision_brisk_map.png}
\includegraphics[width=0.32\textwidth]{images/precision_brisk_paper.png}
\includegraphics[width=0.32\textwidth]{images/precision_brisk_phone.png}
\caption{BRISK detector with 512-bit BRISK descriptor}
\end{subfigure}

\begin{subfigure}[b]{\textwidth}
\centering
\includegraphics[width=0.32\textwidth]{images/precision_surf_barbapapa.png}
\includegraphics[width=0.32\textwidth]{images/precision_surf_comic.png}
\includegraphics[width=0.32\textwidth]{images/precision_surf_map.png}
\includegraphics[width=0.32\textwidth]{images/precision_surf_paper.png}
\includegraphics[width=0.32\textwidth]{images/precision_surf_phone.png}
\caption{SURF detector with SURF64 descriptor}
\end{subfigure}
\caption[Precision plots for different detector/descriptor combinations]{Precision plots for different detector/descriptor combinations. For each combination we plot the results without learning (static), independently trained SVM classifiers, and our structured learning framework. Additionally, in (a) we plot the results of the boosting approach \cite{Grabner2007}.}
\label{fig:learnmatch_precision_compare}
\end{figure}


\begin{sidewaystable}[htbp]
\begin{center}
%\begin{tabular}{|l||c|c|c||c|c|c||c|c|c|c|}
%\hline
%\multirow{2}{*}{Sequence} & \multicolumn{3}{c||}{BRIEF} & \multicolumn{3}{c||}{BRISK} & \multicolumn{3}{c|}{SURF} & \multirow{2}{*}{Boosting \cite{Grabner2007}}\\
%\cline{2-10}
%          & Static & Indep & Struct & Static & Indep & Struct & Static & Indep & Struct & \\
%\hline
%barbapapa & 0.19 & \textbf{0.94} & \textbf{0.94} & 0.92 & \textbf{0.94} & \textbf{0.94} & 0.89 & 0.41 & \textbf{0.91} & 0.88 \\
%comic     & 0.41 & 0.89 & \textbf{0.95} & 0.42 & 0.61 & \textbf{0.64} & 0.83 & 0.68 & \textbf{0.89} & 0.56 \\
%map       & 0.82 & \textbf{0.99} & \textbf{0.99} & 0.79 & 0.91 & \textbf{0.92} & 0.91 & 0.11 & \textbf{0.98} & 0.83 \\
%paper     & 0.06 & 0.72 & \textbf{0.78} & 0.04 & 0.40 & \textbf{0.51} & \textbf{0.03} & 0.01 & \textbf{0.03} & 0.04 \\
%phone     & 0.88 & 0.93 & \textbf{0.97} & 0.64 & 0.81 & \textbf{0.92} & 0.92 & 0.47 & \textbf{0.96} & 0.85 \\
%\hline
%\end{tabular}


\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|}
\hline
\multirow{2}{*}{Sequence} & \multicolumn{3}{c|}{BRIEF} & \multicolumn{3}{c|}{BRISK} & \multicolumn{3}{c|}{SURF} & \multirow{2}{*}{Boost.\cite{Grabner2007}}\\
\cline{2-10}
          & Static & Indep. & Struct. & Static & Indep. & Struct. & Static & Indep. & Struct. &\\
\hline
\emph{barbapapa} & 0.19 & \textbf{0.94} & \textbf{0.94} &   0.93 & 0.93 & \textbf{0.94} &      0.89 & 0.47 & \textbf{0.92} &          0.88\\
\emph{comic}     & 0.42 & 0.90 & \textbf{0.98} &            0.42 & 0.60 & \textbf{0.76} &      0.83 & 0.67 & \textbf{0.93} &          0.56\\      
\emph{map}       & 0.82 & 0.98 & \textbf{0.99} &            0.79 & 0.91 & \textbf{0.93} &      0.91 & 0.06 & \textbf{0.99} &          0.80\\      
\emph{paper}     & 0.06 & 0.68 & \textbf{0.85} &            0.04 & 0.40 & \textbf{0.54} &      \textbf{0.03} & 0.01 & \textbf{0.03} & 0.04\\
\emph{phone}     & 0.88 & 0.93 & \textbf{0.97} &            0.64 & 0.82 & \textbf{0.92} &      0.92 & 0.44 & \textbf{0.97} &          0.87\\      
\hline
\end{tabular}
\end{center}
\caption[Average detection rates for test sequences]{Average detection rates for test sequences (the higher better). Each row represents a video sequence. Each set of columns shows a different combination of feature point detector and descriptor, while the last single column shows the results for the boosting approach. Within a feature detector/descriptor combination, we compare the results without learning (static), independently trained SVM classifiers, and our structured learning framework. The bold-face font highlights the best-performing method for a video sequence for a given detector/descriptor combination.}
\label{tbl:learnmatch_online_results}
\end{sidewaystable}

Figure \ref{fig:learnmatch_precision_compare} shows precision plots for each combination of keypoint detector and descriptor on our test sequences\footnote{Videos of these results can be found at \url{http://www.samhare.net/research}.}. To summarise these plots, Table \ref{tbl:learnmatch_online_results} shows the precision at a threshold of $d_{homography}(T,T') < 10$, which we consider to be correct detections. 

As can be seen from these results, the structured learning framework outperforms the static model (with no learning), as well as the model trained with independent SVM classifiers. Comparing the results of independent SVM classifiers and the static model highlights the fact that adapting an object model to a particular environment online helps a lot in practice. However, the highest detection rate is attained when we used our structured learning framework, in which the learning of the object model and geometric estimation are linked inside a unified formulation. It should be noted that for SURF descriptors the independent SVMs had difficulty learning an object model. We suspect that this is caused because of the continuous nature of the SURF descriptor and the fact that the number of generated keypoints is lower with the SURF keypoint detector. However, given the same settings, the structured learning approach is able to benefit fully from the adaptation process and improve upon the static model. 

For the boosting-based learning approach, it is only fair to compare results against the models where we use the BRIEF descriptor (as both of these methods use the same FAST keypoint detector). Again, one can see by comparing the boosting method with the static method that learning provides an improvement. However, the boosting-based approach is not able to outperform the independent SVM baseline and therefore also performs worse than our structured learning framework. 

\begin{figure}[htbp]
\centering
\begin{subfigure}[b]{\textwidth}
\includegraphics[width=\textwidth]{images/paper_brief.png}
\caption{Static BRIEF model}
\end{subfigure}
\begin{subfigure}[b]{\textwidth}
\includegraphics[width=\textwidth]{images/paper_brief_learned.png}
\caption{Learned BRIEF model using our structured learning formulation}
\end{subfigure}
\caption[Example of learned correspondences on the \emph{paper} sequence]{Example frame from the \emph{paper} sequence showing the top correspondence for each model keypoint. The model is displayed in a green box on the left of these images. The brightness of each line indicates the correspondence score, before any geometric verification has taken place (the brighter the higher the score). The learned model has adapted to discriminate against the many confusing keypoints in the image, resulting in a successful detection, while no detection is found with the static model.}
\label{fig:learnmatch_brief_example}
\end{figure}

The most difficult video in our set of experiments is the \emph{paper} sequence. This video sequence features highly repetitive local appearance structures and a simple static model fails in all cases. The learning-based approaches (except the boosting method), however, are able to deliver a reasonable detection rate using binary descriptors. An example frame from this sequence is shown in Figure~\ref{fig:learnmatch_brief_example}, where we also display the correspondences which have been found before geometric verification. As can be seen in the top image, because of the confusing appearance of the local image features, the static BRIEF model fails to match model keypoints reliably to the image. However, the structured learning framework which uses the same set of descriptors extracted from the input image has learned a more discriminative object model and is able to provide more correct correspondences, resulting in a successful detection. Another observation is that although the structured learning model produces some incorrect correspondences, they all have very low scores (as shown by their dark colour).



\section{Binary approximation}\label{sec:learnmatch_exp_binary}

% TODO: fix subfigures
%\begin{figure*}[htb]
%  \begin{center}
%    \subfigure[Detection rate]{\includegraphics[width=0.46\linewidth]{images/binary_components_detection_rate.png}}
%    \subfigure[Detection time]{\includegraphics[width=0.46\linewidth]{images/binary_components_detection_time.png}}
%  \end{center}
%  \caption{Behaviour of the learned BRIEF model using our structured output formulation when employing a binary approximation of each $\vt{w}_j$ as described in Section \ref{sec:binary_approx}. For $N_b \geq 2$ the detection performance is almost equivalent to the original model, whilst being approximately four times faster with our unoptimized implementation. }
%  \label{fig:binary_approx}
%\end{figure*}

To verify that the binary approximation proposed in Section \ref{sec:learnmatch_binary_approx} is reasonable when using binary
descriptors such as BRIEF and BRISK, we repeat our experiments for the BRIEF descriptor model learned in our structured framework and approximate the model keypoint weight vectors $\vt{w}_j$ with varying numbers of binary bases $N_b$. As can be seen in Figure \ref{fig:learnmatch_binary_approx}, in general the binary approximation produces detection performance comparable to the original results with $N_b \geq 2$ bases, and for the less challenging sequences even a single basis suffices. In terms of detection time, which includes the stages of generating correspondences between model and image, performing geometric verification, and updating the learner, we see that the binary approximation provides significant performance gains (approximately 4 times faster detection with our unoptimised implementation). 

\begin{figure}[htb!]
\centering
\begin{subfigure}[b]{0.49\textwidth}
\includegraphics[width=\textwidth]{images/binary_components_detection_rate.png}
\caption{Detection rate}
\end{subfigure}
\begin{subfigure}[b]{0.49\textwidth}
\includegraphics[width=\textwidth]{images/binary_components_detection_time.png}
\caption{Detection time}
\end{subfigure}
\caption[Binary approximation results]{Behaviour of the learned BRIEF model using our structured formulation when employing a binary approximation of each $\vt{w}_j$ as described in Section \ref{sec:learnmatch_binary_approx}. For $N_b \geq 2$ the detection performance is almost equivalent to the original model, whilst being approximately four times faster with our unoptimised implementation. }
\label{fig:learnmatch_binary_approx}
\end{figure}


\section{Low-powered implementation}

To demonstrate that our approach is indeed suitable of use on a low-powered device, we have ported our code to run on an Apple iPhone 4 (see Figure \ref{fig:learnmatch_ios}). On this device we observe a frame-rate of around 5fps for our approach using the proposed binary approximation with $N_b = 2$, compared with around 8fps for the static approach without learning. We therefore see that even with an unoptimised implementation, our method does not add a significant overhead to the detection pipeline and is thus suitable for real-time applications on low-powered devices.


\begin{figure}[htb]
\centering
\includegraphics[width=\textwidth]{images/lowpower.jpg}
\caption[Our method running on a low-powered device]{Our unoptimised method is able to perform real-time detection and learning on low-powered devices. Here it is shown running on an Apple iPhone 4.}
\label{fig:learnmatch_ios}
\end{figure}

%\subsection{Batch model learning}

% issue with tracking by detection is that the appearance change between frames is small, so the learner could just be drifting. batch experiments show that we can learn a model once which we then fix, and still obtain good performance

% should be able to show over epochs that we stop incurring loss on the training examples, and ultimately the detection performance on the entire video sequence improves...

%\subsection{Feature selection}
%The objective function in the second layer as described in Section \ref{sec:second_layer} regularizes $\vt{a}$ with an
%$l1$ norm, which encourages sparsity.


% Experiments to run:
%   fix binary weight vector and check it behaves like normal one (normalize by D)
%   two-layer approach but use appearance score for choosing match
%   two-layer approach with NN score or boosting score?
%   l1 feature selection with different regularizer params
%   something showing timings illustrating our approach is much faster than grabner and comparable to NN
%   use feature selection mechanism of grabner for throwing their classifiers away or weighting for PROSAC?

%   make sure error measure is taking into account detection or not


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "../learnmatch"
%%% End:
