\documentclass{article}        
\usepackage{html,makeidx,color}
\usepackage{graphicx}
\newcommand{\mfile}[1]{ \textbf{ \texttt{\htmladdnormallink{#1}{../#1}}}}

\begin{document}                 % The start of the document
\title{A Matlab implementation of HSM}
\author{Andrea Censi}
\date{\today}
\maketitle
\tableofcontents        

\section{Introduction}

This document describes the Matlab implementation of an algorithm
called \emph{Hough Scan Matching}. 
The algorithm's goal is to find the roto-translation
which makes two sets of bidimensional data overlap.

More information about HSM is in
\begin{itemize}
	\item 
		\htmladdnormallink{A. Censi}{http://www.dis.uniroma1.it/~censi},
		\htmladdnormallink{L. Iocchi}{http://www.dis.uniroma1.it/~iocchi},
		G. Grisetti,
		\emph{Scan matching in the Hough Domain},
		in Proceedings of the IEEE Int. Conference on Robotics and Automation (ICRA) 2005, Barcelona
		(\htmladdnormallink{PDF}{http://www.dis.uniroma1.it/~acensi/pub/research/censi-hsm.pdf},
		\htmladdnormallink{ppt slides}{http://www.dis.uniroma1.it/~acensi/pub/research/censi-hsm-barcelona.ppt})
	\item extended paper:
		A. Censi, Bachelor Thesis
		(\htmladdnormallink{PDF}{http://www.dis.uniroma1.it/~acensi/pub/research/censi-thesis.pdf})
\end{itemize}

The online version of this file and of the software package
is at \htmladdnormallink{at my home page}
{http://www.dis.uniroma1.it/\%7ecensi/}
(or see the mirror at \htmladdnormallink{censi.org}{http://censi.org})


\subsection{About the code}

I am by no means a Matlab expert and when I had to choose I maximized
readability over speed. Therefore it runs incredibly slow with respect to
the original C++ implementation.

I wrote the code on Matlab 7; it should not need any additional toolbox, with
the exception of the Image Processing toolbox to read an image from file 
in one of the examples.

\section{Contents of the package}
	There are some small test-$\star$ files which produce some nice output: I suggest
	to read them in order.
	\begin{itemize}
		\item \mfile{test1.m} shows the computation of the Hough
		Transform and Hough Spectrum
		\item \mfile{test2.m} shows how hypotheses for $\phi$ can
		be found by correlating the spectra.
		\item \mfile{testEllipse.m} complete HSM example: commented later.
		\item \mfile{testPoints.m} complete HSM example: commented later.
		\item \mfile{testImageHolmes.m} complete HSM example: commented later.
	
	\end{itemize}
	
	This is where the action takes place:
	\begin{itemize}
		\item\mfile{doHSM.m} the complete algorithm; it's (I hope)
		well commented.
	\end{itemize}
	
	These files are support files used by \mfile{doHSM.m}
	\begin{itemize}
		\item \mfile{computeHoughTransform.m} 
			Computes the Hough Transform of a set of points.	
		\item \mfile{computeHoughSpectrum.m} 
			Computes the Hough Spectrum from the Hough Transform.
			
		\item \mfile{findLocalMaxima.m}
			Finds the local maxima in a sequence.
		\item \mfile{findLocalMaxima2.m}
			Finds the local maxima in a matrix.
		\item \mfile{findLocalMaximaCircular.m}
			Finds the local maxima in a ring.
			
		\item \mfile{normalize.m}
			Linearly normalizes a vector in the $[0,1]$ range.
		\item \mfile{normalize2.m}
			Linearly normalizes a matrix in the $[0,1]$ range.

		\item \mfile{simpleLowPassFilter.m}
			Applies a gaussian filter to a sequence.
		\item \mfile{simpleLowPassFilterCircular.m}
			Applies a gaussian filter to a ring.
		\item \mfile{simpleLowPassFilter2.m}
			Applies a gaussian filter to a matrix.

		\item \mfile{circularRotation.m}
			Circularly rotates a ring.
		\item \mfile{circularCrossCorrelation.m}
			Performs the circular cross correlation of two rings.
			
		\item \mfile{rad2degi.m}
			Simple radians to (integer) degree conversion.
		\item \mfile{rotationMatrix.m}
			Generates a 2D rotation matrix.
		
			
	\end{itemize}

	Test pattern generation:
	\begin{itemize}
		\item \mfile{patternEllipse.m} generates an ellipse pattern.
	\end{itemize}

	Graphics routines:
	\begin{itemize}
		\item \mfile{displayHSMResult.m} displays all the steps in the HSM algorithm.
		\item \mfile{plotHoughSpectrum.m} nice plot of the Hough Spectrum.
		\item \mfile{plotHoughTransform.m} nice plot of the Hough Transform.
	\end{itemize}

	
\section{Commented experiments}

	I would like to comment on some of the experiments. Every test file produces
	both EPS and PNG output. You see in this document the PNG output.
	I suggest when running the examples to look at the EPS output which
	is much better than the on-screen figures.
	
	\subsection{\mfile{testEllipse.m}}
	The goal of this test is to show that even tough the algorithm operates in the Hough Domain
	it doesn't rely on the presence of lines.
	
	Note the two symmetric hypotheses for $\phi$; this is a limitation of the
	algorithm which reports the correct solution $\phi$ AND the solution at $\phi+180^\circ$
	In this case it is also an ambiguity in the data.
	
	 \includegraphics{testEllipse-phi.png}
	 \includegraphics{testEllipse-t.png}
	 
	\subsection{\mfile{testPoints.m}}
	The goal of this test is to show how the algorithm performs with very sparse and noisy data.
	
	 \includegraphics{testPoints-phi.png}
	 \includegraphics{testPoints-t.png}
	 
	\subsection{\mfile{testImageHolmes.m}}
	Altough we developed HSM for localization, laser range finder data
	is boring. This shows how the algorithm performs with image-like data sets.
	
	Note the effect of the gaussian noise of the input data on the Hough Spectrum.
	
	 \includegraphics{testImageHolmes-phi.png}
	 \includegraphics{testImageHolmes-t.png}
	 
	 
\end{document}



