Grid-based coding of terrain maps for localization

1 . A computer-implemented method of improving a robustness to noise and reduce a localization error encoding terrain maps, the method comprising using a number of processors to perform the steps of:

receiving a digital elevation model (DEM) of a terrain;

encoding the DEM into a number of grid cells in a phase space parameterized by spatial scale, orientation, and a 2D offset;

aggregating grid cells with shared spatial scale and orientation into grid modules, wherein the 2D offset remains a free parameter;

identifying a number of locations from the DEM that correspond to a given elevation to produce a contour line of locations that fall within the given elevation;

calculating 2D phase codes for each grid module to produce a phase candidate dictionary, wherein a subset of the 2D phase codes comprise phase candidates that correspond to locations from the contour line for the given elevation;

while receiving streaming sensor data along a trajectory over the terrain, wherein the sensor data comprises elevation readings, performing the steps of;

querying the phase candidate dictionary based on the sensor data, wherein each grid module obtains a set of phase candidates;

correcting the phase candidates for relative displacement from a given reference point;

summing corrected phase candidates and producing a coincidence map over the DEM; and

identifying, using the coincidence map, a current location estimate over the terrain.

2 . The method of claim 1 , wherein the steps of receiving the sensor data, querying the phase candidate dictionary, correcting the phase candidates, and summing the corrected phase candidates are performed for multiple trajectories with respective sensor data.

3 . The method of claim 1 , wherein calculating the 2D phase codes of the grid modules comprises performing an affine transform of Cartesian coordinate followed by a modulo operation.

4 . The method of claim 1 , wherein the 2D offset may be scaled to phases on a torus with a reference point as a corner of the DEM.

5 . The method of claim 1 , wherein odometry information to correct the phase candidates for relative displacement is provided by an inertial measurement unit.

6 . The method of claim 1 , wherein summing the corrected phase candidates comprises summing phase candidates across multiple grid modules over the DEM randomly selected with distinct spatial scale and orientation.

7 . The method of claim 1 , wherein each grid module has its own phase space, and wherein linear displacements in Cartesian coordinate space corresponds to phase shifts in a phase space according to a parameterization of that phase space.

8 . A system for configured to increase a robustness to noise and reduce a localization error in encoded terrain maps, wherein the system comprises:

a storage device that stores program instructions; and

one or more processors operably connected to the storage device and configured to execute the program instructions to cause the system to:

receive a digital elevation model (DEM) of a terrain;

encode the DEM into a number of grid cells in a phase space parameterized by spatial scale, orientation, and a 2D offset;

aggregate grid cells with shared spatial scale and orientation into grid modules, wherein the 2D offset remains a free parameter;

identify a number of locations from the DEM that correspond to a given elevation to produce a contour line of locations that fall within the given elevation;

calculate 2D phase codes for each grid module to produce a phase candidate dictionary, wherein a subset of the 2D phase codes comprise phase candidates that correspond to locations from the contour line for the given elevation;

receive a stream of sensor data along a trajectory over the terrain, wherein the sensor data comprises elevation readings, and based upon the stream execute the following;

query the phase candidate dictionary based on the sensor data, wherein each grid module obtains a set of phase candidates;

correct the phase candidates for relative displacement from a given reference point;

sum corrected phase candidates and produce a coincidence map over the DEM and

identify, based upon the coincidence map, a current location estimate over the terrain.

9 . The system of claim 8 , wherein the steps of receiving the sensor data, querying the phase candidate dictionary, correcting the phase candidates, and summing the corrected phase candidates are performed for multiple trajectories with respective sensor data.

10 . The system of claim 8 , wherein calculating the 2D phase codes of the grid modules comprises performing an affine transform of Cartesian coordinate followed by a modulo operation.

11 . The system of claim 8 , wherein the 2D offset may be scaled to phases on a torus with a reference point as a corner of the DEM.

12 . The system of claim 8 , wherein odometry information to correct the phase candidates for relative displacement is provided by an inertial measurement unit.

13 . The system of claim 8 , wherein summing the corrected phase candidates comprises summing phase candidates across multiple grid modules over the DEM randomly selected with distinct spatial scale and orientation.

14 . The system of claim 8 , wherein each grid module has its own phase space, and wherein linear displacements in Cartesian coordinate space corresponds to phase shifts in a phase space according to a parameterization of that phase space.

15 . A computer program product configured to increase a robustness to noise and reduce a localization error in encoded terrain maps, wherein the computer program product comprises a computer-readable storage medium that comprises program instructions embodied thereon configured to perform the steps of:

receiving a digital elevation model (DEM) of a terrain;

encoding the DEM into a number of grid cells in a phase space parameterized by spatial scale, orientation, and a 2D offset;

aggregating grid cells with shared spatial scale and orientation into grid modules, wherein the 2D offset remains a free parameter;

identifying a number of locations from the DEM that correspond to a given elevation to produce a contour line of locations that fall within the given elevation;

calculating 2D phase codes for each grid module to produce a phase candidate dictionary, wherein a subset of the 2D phase codes comprise phase candidates that correspond to locations from the contour line for the given elevation;

while receiving streaming sensor data along a trajectory over the terrain, wherein the sensor data comprises elevation readings, performing the steps of;

querying the phase candidate dictionary based on the sensor data, wherein each grid module obtains a set of phase candidates;

correcting the phase candidates for relative displacement from a given reference point;

summing corrected phase candidates and producing a coincidence map over the DEM; and

identifying, using the coincidence map, a current location estimate over the terrain.

16 . The computer program product of claim 15 , wherein the steps of receiving the sensor data, querying the phase candidate dictionary, correcting the phase candidates, and summing the corrected phase candidates are performed for multiple trajectories with respective sensor data.

17 . The computer program product of claim 15 , wherein calculating the 2D phase codes of the grid modules comprises performing an affine transform of Cartesian coordinate followed by a modulo operation.

18 . The computer program product of claim 15 , wherein the 2D offset may be scaled to phases on a torus with a reference point as a corner of the DEM.

19 . The computer program product of claim 15 , wherein odometry information to correct the phase candidates for relative displacement is provided by an inertial measurement unit.

20 . The computer program product of claim 15 , wherein summing the corrected phase candidates comprises summing phase candidates across multiple grid modules over the DEM randomly selected with distinct spatial scale and orientation.