\documentclass[10pt,a4paper]{article}
\usepackage[pdftex]{graphicx}
\usepackage{fullpage}
\usepackage{url}
\usepackage{amssymb,amsmath}

\begin{document}

\begin{center}
Principal Component Analysis \\
Computer Vision, Lab Exercise 3 \\
Andreas van Cranenburgh (0440949), Willem Bressers (5687063) \\
{\em \today}
\end{center}

\abstract{This report discusses the use of Principal Component Analysis to
estimate the position of an image using a training set.}

\tableofcontents
\listoffigures

%\section{Problem specification}

\input{PCA}

\section{Positioning}
After having done the Principal Component Analysis we can now try to compare an
arbitrary image to the images from the training set. The image that best
matches it provides an indication of where it was made.

Positioning might appear trivial with GPS being so ubiquitous nowadays, but
consider indoor locations with poor reception, or even space and planetary
explorations, where GPS is unavailable.

\subsection{Reduced representation}
Using the PCA just performed we can create a reduced representation of all
images in the training set. With $n$ images, for all $i$ in $n$ the reduced
representation is obtained by:

\begin{equation}
g_i = U^T \cdot x_i
\end{equation}

\subsection{Nearest neighbor}
Now we can turn to an algorithm for approximating the location of an image. We
will first convert the image to the reduced representation as above. Then we
estimate the `distance' between that and each image of the training set (or
inversely their similarity) thus\footnote{For completeness, $norm(X) =
\sqrt{\sum \vec{x}^2}$ with $x$ being a column vector, for our purposes}:

\begin{equation}
dist_i = norm(g_i - (U^T \cdot image))
\end{equation}

Where $image$ is a column vector with the mean calculated before subtracted
from it. After obtaining the distances between the image and each of the
training set images, the one closest to it provides the estimated position of
the image.

\subsection{Evaluation}

This method can be evaluated by comparing the estamited positions with their
actual positions, as given in the test set. Once again we calculate the
distance (but now of real world coordinates and not of image data), between the
estimated and actual positions:

\begin{equation}
dist_i = norm(est_i - pos_i)
\end{equation}

Running this on all images of the test set enables us to see how well the
algorithm performs. For our purposes we will consider a distance of less than
150 units to be a correct estimate. This is because the images in the data set
have been taken with about 50 units in between.

Using the first 20 principal components the following score is obtained:

\begin{verbatim}
>> testPositioning(images)
[...]
correct =

   174

wrong =

    76

Elapsed time is 1.325647 seconds.
>>
\end{verbatim}

Experimentally we discovered that for a number of components between 30 and 44
the optimal score of 175 correct can be obtained, after which the accuracy goes
to 174 again. This shows that 20 is a good tradeoff in terms of speed versus
accuracy.

When the number is decreased the accuracy decreases gracefully, eg.\ 164
correct with only 10 components.

\subsection{Without PCA}
As a further benchmark, we tried the positioning without the use of PCA, and instead comparing every picture directly:

\begin{verbatim}
correct =

   187

wrong =

    63

Elapsed time is 14.043909 seconds.
\end{verbatim}

\subsection{PCA Using the \texttt{SVD}}
Instead of using the function \texttt{eigs} to calculate eigenvectors, it is also possible to use the \texttt{svd}. For comparison, we implemented this in \texttt{PCAsvd.m}. 

\begin{verbatim}
correct =

   178

wrong =

    77

Elapsed time is 3.385796 seconds.
\end{verbatim}

This score was obtained using 108 principal components. A value arrived at by repeated guessing.

\subsection{Even more precision}
To further improve the accuracy of this method it might be useful to take into
account that the images are omnidirectional. In fact the image is a flat
representation of a hemisphere, so perhaps the theory of manifolds can help in
this regard. Comparing the distance between two images in a way that is
rotationally invariant might improve the accuracy, but we have not pursued this
yet.

\end{document}