\section{Skeleton uniqueness}
\label{sec:uniqueness}

The most obvious concern raised by trying to use skeletons to
recognize people is their uniqueness. Are skeletons consistently
and sufficiently pairwise distinct to have reasonable hope of using
them for people recognition?

\subsection{Face recognition benchmark}

A good way to understand the uniqueness of a metric is to look at how
well an algorithm based on it performs in the \emph{pair-matching
problem}. In this problem you are given two measurements of the metric
and you want to decide whether they come from the same individual
(matched pair) or from two different individuals (unmatched pair).

The \emph{Labeled Faces in the wild} \cite{lfw} database is
specifically suited to study the face pair matching problem and has
been used to benchmark several face recognition algorithms. Raw data
of this benchmark is publicly available and has been derived as
follows: the database is split into 10 subsets. From each of these
subsets, 300 matched pairs and 300 unmatched pairs are randomly
chosen. Each algorithm runs 10 separate leave-one-out cross-validation
experiments on these sets of pairs. Averaging the number of true
positives and false positives across the 10 experiments for a given
threshold then yields one point on the receiver operating
characteristic curve (ROC curve: this is the curve of the
true-positive rate vs. the false-positive rate as the threshold of the
algorithm varies). Note that in this benchmark the identity
information of the individuals appearing in the pairs is not
available, which means that the algorithms cannot form additional
images pair from the input data. This is referred to as the
\emph{Image-restricted} setting in the LFW benchmark.

\subsection{Experiment design}

In order to run an experiment similar to the one used in the face
pair-matching problem, we use the Goldman Osteological Data Set
\cite{deadbodies}. This data set consists of osteometric measurements
of 1538 skeletons dating from throughout the Holocene. We keep from
these measurements the lengths of six bones (radius, humerus, femur,
tibia, left coxae, right coxae). Because of missing values, this
reduces the size of the dataset to 1191.

From this data set, 1191 matched pairs and 1191 unmatched pairs are
generated. In practice, the exact measurements of the bones are never
directly accessible, but are always perturbed by a noise whose
variance depends on the collection protocol. This is accounted for by
adding independent random Gaussian noise to each constituents of the
pairs.

\subsection{Results}

The pair-matching problem is then solved by using a proximity
threshold algorithm: for a given threshold, a pair will be classified
as \emph{matched} if the Euclidean distance of its two constituents is
lower than the threshold and \emph{unmatched} otherwise. Formally, let
$(s_1,s_2)$ be an input pair of the algorithm
($s_i\in\mathbf{R}_+^{6}$, these are the measurements of the six
bones), the output of the algorithm for the threshold $\delta$ is
defined as:
\begin{displaymath}
  A_\delta(s_1,s_2) = \begin{cases}
    1 & \text{if $d(s_1,s_2) < \delta$}\\
    0 & \text{otherwise}
  \end{cases}
\end{displaymath}

\begin{figure}
  \begin{center}
    \includegraphics[width=10cm]{data/pair-matching/roc.pdf}
  \end{center}
  \caption{Receiver operating characteristic (true positive rate
  vs. false positive rate) for several standard deviations of the
  noise and for the state-of-the-art \emph{Associate-Predict} face
  detection algorithm.}
  \label{fig:roc}
\end{figure}

Figure \ref{fig:roc} shows the ROC curve of the proximity threshold
algorithm for different values of the standard deviation of the noise,
as well as the ROC of the best performing face detection algorithm in
the Image-restricted LFW benchmark: \emph{Associate-Predict}
\cite{associate}.

The results show that with a standard deviation of 3mm, skeleton
proximity thresholding performs quite similarly to face detection at
low false-positive rate. At this noise level, the error is smaller
than 1cm with 99.9\% probability smaller. Even with a standard
deviation of 5mm, it is still possible to detect 90\% of the matched
pairs with a false positive rate of 6\%.

This experiment gives an idea of the noise variance level above which
it is not possible to consistently distinguish skeletons. This noise
level can be interpreted as follows in the person identification
setting. For this problem, a classifier can be built be first learning
a \emph{skeleton profile} for each individual from all the
measurements in the training set. Then, given a new skeleton
measurement, the algorithm classifies it to the individual whose
skeleton profile is closest to the new measurement. In this case,
there are two distinct sources of noise:
\begin{itemize}
\item the absolute deviation of the estimator: how far is the
  estimated profile from the exact skeleton profile of the person.
\item the noise of the new measurement: this comes from the device
  doing the measurement.
\end{itemize}

We will come back in section \label{sec:kinect} on the structure of
the noise and its relation to the noise represented on the ROC curves.

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "kinect"
%%% End: