This week I begun to explore techniques on speeding up the registration
process. The main idea of the techniques is to focus in on relevant
feature of occupancy grids and only compare those areas against the
case library.  The goal is to decrease the time require to register
grids without comprimising accuracy.

To focus in on "relevant" areas, I have concentrated on highlighting
areas of high differentials of probability.  Trying a Gaussian filter
didn't seem to yield good results, so I resorted to a simple derivative
function over the the grid.  An additional bonus for simplicity is that
we want our transformation to be quick as well, otherwise we might as
well use the old registration techniques.  Preliminary experiments show
that a simple derivitative grid work quiet well.

Once a grid has been "derivitize," we would like to zoom in on only the
areas of high relevance.  Again, we would like such an algorithm to be
simple (to keep the speed advantage).  A simple technique that I am currently
using involves finding the longest contigous line of high differentials
in both the x and y directions, then forming a bounding rectangle and
call that the area of relevance.  This algorithm has several features:
1)  Worst case could have a bounding rectangle that is the whole grid
2)  Natural environments (like walls) fall in natural lines.  We find lines
    of high diffrentials of occupancy like between a solid wall and the
    clear spaces immediately adjacent to it.  Unlike previous researchers,
    we make use of BOTH occupied information AND unoccupied info.
3)  It's a simple and quick algorithm... more sophistacated algorithm can
    be substituted here.
This is only done for the incoming sample grids.  This is based on the
assumption that the case library represents typical samples and that
information should not be thrown out.  Speed can be increased if we
run the above "zoom" feature on the case library grids, but accuracy
may suffer.  (This will be tested.)

Preliminary experiments shows that the new algorithm runs in about half
of the time that it takes the old, exhaustive registration (and that
includes the above processing.  Conceivably, more time can be shaved if
one were to pre-compute the transformations for the case-library before
the comparisons).  Accuracy also does not appear be harmed (our algorithm
only makes mistakes when the old algorithm would have made similar mistakes).
We can increase our confidence in the algorithm by incorporating checks (i.e.,
once we have run a quick pass through our case library, we may opt to run
a more exhaustive check of the most likely candidates).  To increase the
speed of our algorithm, we may opt to select smaller bounding areas
(like long lines that lies closer together).

More experiments needs to be done to affirm the hypothesis.  But it looks
fairly viable.  That's for the coming week.  Exact experimental conditions
are probably going to be difficult, since we are talking about measuring
time intervals on diversly loaded machines.  Maybe a different measure
(number of computations?) may be needed to measure actual performance.

Sample trial run:

Identification (noise0) of 1.6.1-sweep from ?.6.1-sweep:
Old Algorithm -			New Algorithm -
Place IDed: 1			Place IDed: 1
Time to ID: 8.3 minutes		Time to ID: 3.8 minutes