\chapter{Structured learning formulation}
\label{sec:learnmatch_method}
In this section, we describe our formulation of keypoint-based object detection as a structured learning problem. 

\section{RANSAC for structured prediction}

Given an object model $M$ and an input image $I$, the goal of object detection is to compute a transformation $T \in \mathcal{T}$ which maps $M$ to $I$. A 3D pose or 2D homography are examples of such a
transformation. 

We can think of this process as one of structured prediction, with the output space consisting of all valid transformations, along with a null transformation indicating the absence of the object. We therefore assume that there exists a function $T = f(M,I)$ and that this function can be expressed as
\begin{equation}\label{eqn:learnmatch_prediction}
  T = \argmax_{T' \in \mathcal{T}} g(M, I, T') ,
\end{equation}
where $g$ is a compatibility function, scoring all possible transformations of the object given an image.

In practice, finding a solution for the prediction function \eqref{eqn:learnmatch_prediction} under a specific model definition is generally unfeasible because the output space is very large, and evaluating image observations under different transformations of the model will be expensive. The way that this issue is usually handled is by applying an iterative robust parameter estimation algorithm such as RANSAC \cite{Fischler1981} or PROSAC \cite{Chum2005} to approximately solve \eqref{eqn:learnmatch_prediction}. These algorithms rely on a sparse representation for the model and image and use a set of correspondences between model and image points as
their input. 

Consider an object model $M$ which is based on a sparse set of keypoints $\mathcal{M} = \{u_1, \dots,
u_J\}$, with each keypoint defined by a location (2D or 3D). Similarly, let the image $I$ be represented as a sparse set
of keypoints $\mathcal{I} = \{v_1, \dots, v_K\}$. A set of correspondences $\mathcal{C} = \{ (u_j, v_k, s_{jk}) | u_j \in \mathcal{M}, v_k \in \mathcal{I}, s_{jk} \in \mathbb{R}\}$ is found between model keypoints and image keypoints, where $s_{jk}$ is a correspondence score derived from appearance information. Traditional RANSAC defines a score for a given transformation in terms of the number of inliers
\begin{equation}\label{eqn:learnmatch_ransac_score}
  g(\mathcal{C}, T) = \sum_{(u_j, v_k) \in \mathcal{C}} \mathbb{I}( \|v_k - T(u_j)\|_2 < \tau ) ,
\end{equation}
where $T(u_j)$ is the location of model keypoint $u_j$ under the transformation $T$, $\tau$ is a spatial mis-alignment threshold and $\mathbb{I}(.)$ is an indicator function. This score is then used as the compatibility function in \eqref{eqn:learnmatch_prediction} and maximised approximately by randomly sampling transformations which are compatible with minimal subsets of correspondences in $\mathcal{C}$. Variants such as PROSAC use the correspondence scores $s_{jk}$ to bias this sampling in order to reach a solution in fewer iterations.

Existing approaches have applied learning in an offline setting \cite{Taylor2009,Lepetit2006,Ozuysal2010} as well as in an online setting \cite{Ozuysal2006,Grabner2007} to encourage reliable appearance-based correspondences to be found in $\mathcal{C}$. However, in these approaches the generation and scoring of correspondences and the maximisation of \eqref{eqn:learnmatch_ransac_score} are decoupled from each other. These approaches therefore do not perform learning which takes into account the entire transformation prediction process.

To allow learning for the entire prediction process, we propose introducing a weight vector $\vt{w}_j$ for each model keypoint $u_j$. This weight vector is used to score correspondences according to $s_{jk} = \langle \vt{w}_j, \vt{d}_k \rangle$, where $\vt{d}_k$ is a descriptor extracted around image keypoint $v_k$, normalised such that $\|\vt{d}_k\|_2 = 1$. We then propose modifying the compatibility function \eqref{eqn:learnmatch_ransac_score} to include correspondence scores, such that it can be written as a linear operator
\begin{equation}\label{eqn:learnmatch_compatibility}
  \begin{aligned}
%    F_{\vt{w}}(\mathcal{M}, \mathcal{I}, T) = & \sum_j \langle \vt{w}_j, \vg{\phi}(u_j, \mathcal{I}, T) \rangle \\
%    = & \langle \vt{w}, \vg{\Phi}(\mathcal{M}, \mathcal{I}, T) \rangle
     g_{\vt{w}}(\mathcal{C}, T) = &\sum_{(u_j, v_k) \in \mathcal{C}} s_{jk}\,\mathbb{I}( \|v_k - T(u_j)\|_2 < \tau ) \\
     = & \langle \vt{w}, \vg{\Phi}(\mathcal{C}, T) \rangle,
  \end{aligned}
\end{equation}
where $\vt{w} = [\vt{w}_1, \dots, \vt{w}_J]^T$ is the concatenation of model weight vectors and $\vg{\Phi}(\mathcal{C}, T) = [\vg{\phi}_1(\mathcal{C}, T), \dots, \vg{\phi}_J(\mathcal{C}, T)]^T$ is a joint feature
mapping. Each $\vg{\phi}_j$ is defined as
\begin{equation}\label{eqn:learnmatch_feature}
  \vg{\phi}_j(\mathcal{C}, T) = \left\{
    \begin{aligned} & \vt{d}_{k} && \exists (u_j,v_k) \in \mathcal{C}: \|v_k - T(u_j)\|_2 < \tau \\ 
    & \vt{0} &&
      \text{otherwise.}
    \end{aligned} \right.
\end{equation}


Our goal is to learn the compatibility function \eqref{eqn:learnmatch_compatibility} parameterised by $\vt{w}$ such that the behaviour of this function in the output space is close to the actual behaviour of RANSAC, but, because it includes information about appearance, in the process of learning we will discover which model points are the most discriminative and how best we can utilise them to predict transformations.

% In order to identify which model points are discriminative within the input image, we construct a feature vector that
% captures information regarding the local neighborhood of that point in a feature space defined by a descriptor. In
% other words, given a descriptor function, we define a feature vector which encodes the similarity of that point with
% respect to all other points in an image. This way, learning the $\vt{w}$ not only will create an adaptive model but also
% will value the discriminative points with unique appearances more that points which are repetitive.

%In order to identify which model points are discriminative within the input image, we construct a feature vector that
%captures information regarding the local neighborhood of that point in the image which is usually defined by a
%descriptor. Given a transformation $T$ and a model point $u_j$, we can estimate its image location by $T(u_j)$. Let
%$v_{k(j)} = \argmin_{v_k \in \mathcal{I}} \|v_k - T(u_j)\|_2$ be the nearest image point to $T(u_j)$. We define the
%feature vector $\vg{\phi}$ as
%\begin{equation}\label{eq:feature}
%  \vg{\phi}(u_j, \mathcal{I}, T) = \left\{
%    \begin{aligned} & \vt{d}_{v_{k(j)}} && \text{if $\|v_{k(j)} - T(u_j)\|_2 < \tau$} \\ & \vt{0} &&
%      \text{otherwise ,}
%    \end{aligned} \right.
%\end{equation}
%where $\vt{d}_{v_{k(j)}}$ is a descriptor extracted from location $v_{k(j)}$ from the image. 
%
%In practice, during the prediction phase (Eq~\eqref{eq:prediction}), we follow the same approach as standard RANSAC
%and produce a set of correspondences by matching the model points represented by $\vt{w}$ to a set of image points
%$\mathcal{I}$. To do this, for $j$-th model point $u_j$, we compute the inner product of $\vt{w}_j$ with all the
%descriptors extracted from image points and take the highest ranking one as a correspondence. Therefore, we construct
%the correspondence set
%\begin{equation}
%  \mathcal{C} = \{ (u_j, v_k, s_{jk}) | u_j \in \mathcal{M}, v_k = \argmax_{v \in \mathcal{I}} \langle \vt{w}_j , \vt{d}_{v}
%  \rangle \} ,
%\end{equation}
%where $s_{jk} = \langle \vt{w}_j , \vt{d}_{v_k} \rangle$ is the matching score which some variants of RANSAC (such as
%PROSAC) utilize to generate hypotheses.

\section{Structured SVM learning}
Now, given a set of training examples $\{ (I_i, T_i) \}_{i = 1}^N$, $\vt{w}$ can be learned in a maximum-margin structured learning framework \cite{Tsochantaridis2005}. For each training example $i$, this formulation tries to maximise the margin between the score of the true transformation $T_i$ and all alternative transformations. This can be expressed by the
following optimisation problem
\begin{equation}\label{eqn:learnmatch_structured_primal}
  \begin{aligned}
    & \underset{\vt{w},\vg{\xi}}{\min}
    & & \frac{\lambda}{2}\|\vt{w}\|^2 + \sum_{i=1}^N \xi_i \\
    & \; \text{s.t.}
    & & \forall i: \; \xi_i \geq 0 \\
    & & & \forall i, \forall T \neq T_i: \; \langle \vt{w}, \delta \vg{\Phi}_i(T) \rangle \geq \Delta(T_i, T)-\xi_i
  \end{aligned}
\end{equation}
where $\delta \vg{\Phi}_i(T) = \vg{\Phi}(\mathcal{C}_i, T_i) - \vg{\Phi}(\mathcal{C}_i, T)$, and $\lambda$ is a parameter determining the trade-off between training set accuracy and regularisation. $\Delta(T_i, T)$ is
a loss function which measures the penalty for choosing $T$ instead of the true transformation $T_i$. The loss function
$\Delta(T_i, T)$ should measure the dissimilarity of two competing transformation hypotheses and will be discussed in Section \ref{sec:learnmatch_loss_functions}.

Because we are using RANSAC to perform structured prediction and this relies on an accurate set of correspondences, we modify this formulation to also encourage each inlier correspondence to score higher than any other image correspondence. This can be realised as an additional set of ranking constraints and the formulation then becomes
\begin{equation}\label{eqn:learnmatch_structured_primal_additional_const}
  \begin{aligned}
    \underset{\vt{w},\vg{\xi},\vg{\gamma}}{\min} \ 
    & \frac{\lambda}{2}\|\vt{w}\|^2 + \sum_{i=1}^N \xi_i + \nu \sum_{i=1}^N \sum_{(u_j,v_k) \in \mathcal{C}_i^*}\gamma_{ij} \\
    \text{s.t.} \ 
    & \forall i: \; \xi_i \geq 0 \\
    & \forall i, \forall T \neq T_i: \; \langle \vt{w}, \delta \vg{\Phi}_i(T) \rangle \geq \Delta(T_i, T)-\xi_i \\
    & \forall i, \forall j: \; \gamma_{ij} \geq 0 \\
    & \forall i, \forall (u_j,v_k),\forall k' \neq k: \langle \vt{w}_j , \vt{d}_k - \vt{d}_{k'} \rangle \geq 1 - \gamma_{ij}
  \end{aligned}
\end{equation}
where $\mathcal{C}_i^* \subset \mathcal{C}_i$ is the set of inlier correspondences under $T_i$, and $\nu$ is a weighting parameter.

%$z_{ijk} = \mathbb{I}(\|v_k - T_i(u_j)\|_2 < \tau)$ is an indicator variable showing whether model point $j$
%has a true correspondences (inlier) under the true transformation, and $\nu$ is a weighting parameter.

%For loss function $\Delta(T_i, T)$ we propose to use the hamming distance between the set of inliers returned from transformation $T_i$ and $T$. This loss function is well suited for RANSAC and captures the fundamental criteria which RANSAC tries to optimize.

The learning problem presented in \eqref{eqn:learnmatch_structured_primal_additional_const} allows us to train a discriminative model in a unified way in which learning the representation of model points and performing pose estimation are combined in a single structured learning framework.

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

The optimisation problem \eqref{eqn:learnmatch_structured_primal_additional_const} requires a loss function $\Delta$ to be defined between two transformations. We consider a number of possible loss functions, which we compare experimentally in Section \ref{sec:learnmatch_results_loss}.

The first loss function we consider is designed specifically for the case where the transformations are projective homographies. Given two homographies $T$ and $T'$, we define a distance
\begin{equation}\label{eqn:learnmatch_homog_similarity}
d_{homography}(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\}$ are the corners of a square. This distance can become arbitrarily large, so we define a loss function using a truncated version:
\begin{equation}
\Delta_{homography}(T,T') = \min( d_{homography}(T,T'),\; 20 ).
\end{equation}

A potential issue with this loss function is that since the compatibility function $g_{\vt{w}}(\mathcal{C}, T)$ sums over those correspondences in $\mathcal{C}$ which are inliers under $T$, transformations with more inliers are likely to score higher than those with a smaller number of inliers. For this reason we also consider loss functions which take into account the fact that transformations will have different numbers of inliers. We define two such loss functions, which are applicable for all classes of transformations (\ie\ not only homographies):
\begin{enumerate}
\item
Hamming distance on inliers:
\begin{equation}
\Delta_{hamming}(T,T') = \sum_{(u_j,v_k) \in \mathcal{C}} \mathbb{I} \bigl( z(u_j,v_k,T) \neq z(u_j,v_k,T') \bigr),
\end{equation}
where $z(u_j,v_k,T) = \mathbb{I}(\|v_k - T(u_j)\|_2 < \tau)$. This loss function aims to penalise transformations having different inlier sets.
\item
Difference in number of inliers:
\begin{equation}
\Delta_{inliers}(T,T') = |g(\mathcal{C},T) -g(\mathcal{C},T')|,
\end{equation}
where $g$ is the RANSAC scoring function \eqref{eqn:learnmatch_ransac_score}. This loss function aims to penalise transformations with different numbers of inliers, similar in spirit to the traditional RANSAC approach.

\end{enumerate}

%We now describe our approach for learning the model online. In an online setting, we assume that the model is defined in
%the first frame of the video. We set the initial $\vt{w}_0$ to be the descriptors extracted from the model at the first
%frame.

\section{Online learning}\label{sec:learnmatch_online_learning}

While \eqref{eqn:learnmatch_structured_primal_additional_const} can be solved offline as a batch problem, we are interested in applying our approach for adaptive tracking-by-detection, and therefore need a means for updating $\vt{w}$ online. Because we are using a linear structured SVM, this can be readily achieved using stochastic gradient descent. We first rewrite the optimisation problem \eqref{eqn:learnmatch_structured_primal_additional_const} in unconstrained form as
\begin{equation}\label{eqn:learnmatch_structured_primal_unconstrained}
  \begin{split}
    \underset{\vt{w}}{\min} \Big\{ \frac{\lambda}{2}\|\vt{w}\|^2 + \sum_{i=1}^N \bigl( \max_{T \neq T_i}\{\Delta(T_i, T) -
    \langle \vt{w}, \delta \vg{\Phi}_i(T) \rangle\} \bigr)_+ + \\
     \nu \sum_{i=1}^N \sum_{(u_j,v_k) \in \mathcal{C}_i^*} 
    \bigl( \max_{k' \neq k} \{1 - \langle \vt{w}_j , \vt{d}_k - \vt{d}_{k'} \rangle \}
    \bigr)_+ \Big\} 
  \end{split}
\end{equation}
where $(.)_+ = \max \{0, .\}$ is the hinge function. Given a training example $(I_t, T_t)$ at time $t$, a subgradient of \eqref{eqn:learnmatch_structured_primal_unconstrained} is found
with respect to $\vt{w}$, and a gradient descent step is then performed according to
\begin{equation}\label{eqn:learnmatch_update}
  \begin{split}
    \vt{w}_j^{t+1} \leftarrow & (1-\eta_t\lambda)\vt{w}_j^t + \\
    & \mathbb{I}(\max_{T \neq T_t}\{\Delta(T_t, T) - \langle \vt{w}^t, \delta \vg{\Phi}_t(T) \rangle\} > 0) \eta_t \vg{\alpha}_j^t + \\
    & \mathbb{I}(u_j \in \mathcal{C}_t^*) \; \mathbb{I}(\max_{k' \neq k} \{ 1 - \langle \vt{w}^t_j , \vt{d}_k - \vt{d}_{k'} \rangle \} > 0) \eta_t \nu \vg{\beta}_j^t,
  \end{split}
\end{equation}
where $\eta_t = 1/{\lambda t}$ is the step size. Let $\hat{T} = $ $\argmax_{T \neq T_t} \{\Delta(T_t, T) -
\langle \vt{w}^t, \delta \vg{\Phi}_t(T) \rangle\}$ and $\hat{k} = \argmax_{k' \neq k} \{ 1 - \langle \vt{w}^t_j ,
\vt{d}_k - \vt{d}_{k'} \rangle \}$. Then $\vg{\alpha}_j^t$ and $\vg{\beta}_j^t$ are defined as
\begin{equation}
  \vg{\alpha}_j^t = \vg{\phi}_j(\mathcal{C}_t, T_t) - \vg{\phi}_j(\mathcal{C}_t, \hat{T}),
\end{equation}
and
\begin{equation}
  \vg{\beta}_j^t = \vt{d}_k - \vt{d}_{\hat{k}} .
\end{equation}

To estimate $T_t$ for the current image, we use the prediction of \eqref{eqn:learnmatch_prediction} given the old model
representation $\vt{w}_{t-1}$, and we then update the model representation by performing a single stoachastic gradient descent step according to \eqref{eqn:learnmatch_update}, as shown in Figure \ref{fig:learnmatch_tracking_loop}. Furthermore, when performing RANSAC in order to optimise the prediction function \eqref{eqn:learnmatch_prediction} we will also be exploring and scoring other transformations, which gives us a mechanism for identifying any margin violations which have occurred, the largest of which will contribute to the gradient descent step \eqref{eqn:learnmatch_update}. In this way, our online learning approach can re-use the intermediate results of estimating $T_t$ and thus adds only a small amount of overhead compared to detection alone.


\begin{figure}[htb]
\centering
\includegraphics[width=0.8\textwidth]{images/tracking_loop.pdf}
\caption[Adaptive tracking-by-detection loop]{Adaptive tracking-by-detection loop. At time $t$, the model $\vt{w}_{t-1}$ from the previous frame is used in order to estimate the transformation $T_t$, which is subsequently used as a training example to give an updated model $\vt{w}_t$.}
\label{fig:learnmatch_tracking_loop}
\end{figure}

\section{Binary approximation of model}\label{sec:learnmatch_binary_approx}
An important goal of our method is to be real-time and suitable for low-powered devices, and we would therefore like to take advantage of binary descriptors. Although these descriptors are very compact when represented as bitsets, to use a linear SVM requires converting them into high-dimensional real vectors. While this is acceptable when updating the learner, it would be very computationally expensive at the matching stage, which requires exhaustive evaluation of every model classifier with every image keypoint. To avoid this, we propose approximating each $\vt{w}_j$ in terms of a set of basis vectors
\begin{equation}\label{eqn:learnmatch_binary_approx}
  \vt{w}_j \approx \sum_{i=1}^{N_b} \beta_i \vt{b}_i
\end{equation}
where $\vt{b}_i \in \{-1,1\}^D$, and $D$ is the dimensionality of the descriptor. This approximation must be updated each time $\vt{w}_j$ changes, so we choose to use a
simple greedy method as described in Algorithm \ref{alg:learnmatch_binary_approx}.

\begin{algorithm}[h]
\begin{algorithmic}
  \REQUIRE $\vt{w}_j$, $N_b$
  \STATE $\vt{r} = \vt{w}_j$ \emph{(initialise residual)}
  \FOR{$i = 1$ to $N_b$}
  \STATE $\vt{b}_i = \text{sign}(\vt{r})$
  \STATE $\beta_i = \dotp{\vt{b}_i}{\vt{r}} / \|\vt{b}_i\|^2$ \emph{(project $\vt{r}$ onto $\vt{b}_i$)}
  \STATE $\vt{r} \leftarrow \vt{r} - \beta_i\vt{b}_i$ \emph{(update residual)}
  \ENDFOR
  \RETURN $\{\beta_i\}_{i=1}^{N_b}$, $\{\vt{b}_i\}_{i=1}^{N_b}$
\end{algorithmic}
\caption[Binary approximation of $\vt{w}_j$]{Binary approximation of $\vt{w}_j$.}
\label{alg:learnmatch_binary_approx}
\end{algorithm}

Using this approximation, we can efficiently compute the scalar product $\langle \vt{w}_j, \vt{d} \rangle$ using
only bitwise operations. To do so, we represent each $\vt{b}_i$ using a binary vector and its complement: $\vt{b}_i =
\vt{b}^+_i - \overline{\vt{b}^+_i}$, where $\vt{b}^+_i \in \{0,1\}^D$. We then rewrite
\begin{equation}
\langle \vt{w}_j, \vt{d} \rangle \approx \sum_{i=1}^{N_b} \beta_i 
(\langle \vt{b}^+_i, \vt{d} \rangle - \langle \overline{\vt{b}^+_i}, \vt{d} \rangle),
\end{equation}
and note that each scalar product inside the summation can be computed very efficiently using a bitwise AND followed by a
bit-count. This can be computed even more efficiently if we have precomputed the bit-count of $\vt{d}$, since $\langle \vt{b}^+_i, \vt{d} \rangle - \langle \overline{\vt{b}^+_i}, \vt{d} \rangle = 2\langle \vt{b}^+_i, \vt{d} \rangle - |\vt{d}|$. This means that by approximating $\vt{w}_j$ with $N_b$ components, our correspondence score is roughly $N_b$ times more expensive to evaluate than a binary Hamming distance. In practice, we find it sufficient to set $N_b = 2$, see Section \ref{sec:learnmatch_exp_binary} for experimental results.




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