A Matlab implementation of HSM

Andrea Censi

June 8, 2005

Contents

• Introduction
  • About the code
  
  
• Contents of the package
• Commented experiments
  • testEllipse.m
  • testPoints.m
  • testImageHolmes.m

Introduction

This document describes the Matlab implementation of an algorithm called 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

• A. Censi, L. Iocchi, G. Grisetti, Scan matching in the Hough Domain, in Proceedings of the IEEE Int. Conference on Robotics and Automation (ICRA) 2005, Barcelona (PDF, ppt slides)
• extended paper: A. Censi, Bachelor Thesis (PDF)

The online version of this file and of the software package is at at my home page (or see the mirror at censi.org)

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.

Contents of the package

There are some small test-$\star$ files which produce some nice output: I suggest to read them in order.

• test1.m shows the computation of the Hough Transform and Hough Spectrum
• test2.m shows how hypotheses for $\phi$ can be found by correlating the spectra.
• testEllipse.m complete HSM example: commented later.
• testPoints.m complete HSM example: commented later.
• testImageHolmes.m complete HSM example: commented later.

This is where the action takes place:

• doHSM.m the complete algorithm; it's (I hope) well commented.

These files are support files used by doHSM.m

• computeHoughTransform.m Computes the Hough Transform of a set of points.
• computeHoughSpectrum.m Computes the Hough Spectrum from the Hough Transform.

• findLocalMaxima.m Finds the local maxima in a sequence.
• findLocalMaxima2.m Finds the local maxima in a matrix.
• findLocalMaximaCircular.m Finds the local maxima in a ring.

• normalize.m Linearly normalizes a vector in the $[0,1]$ range.
• normalize2.m Linearly normalizes a matrix in the $[0,1]$ range.

• simpleLowPassFilter.m Applies a gaussian filter to a sequence.
• simpleLowPassFilterCircular.m Applies a gaussian filter to a ring.
• simpleLowPassFilter2.m Applies a gaussian filter to a matrix.

• circularRotation.m Circularly rotates a ring.
• circularCrossCorrelation.m Performs the circular cross correlation of two rings.

• rad2degi.m Simple radians to (integer) degree conversion.
• rotationMatrix.m Generates a 2D rotation matrix.

Test pattern generation:

• patternEllipse.m generates an ellipse pattern.

Graphics routines:

• displayHSMResult.m displays all the steps in the HSM algorithm.
• plotHoughSpectrum.m nice plot of the Hough Spectrum.
• plotHoughTransform.m nice plot of the Hough Transform.

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.

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.

testPoints.m

The goal of this test is to show how the algorithm performs with very sparse and noisy data.

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.

About this document ...

A Matlab implementation of HSM

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -dir html-docs -split 0 -up_url 'http://www.dis.uniroma1.it/%7ecensi/' -up_title 'To my home page' index.tex

The translation was initiated by Andrea Censi on 2005-06-08