# A Stereo Vision Based Mapping Algorithm for Detecting Inclines, Drop-offs, and Obstacles for Safe Local Navigation
Paper - https://web.eecs.umich.edu/~kuipers/papers/Murarka-iros-09.pdf

Reasons for not using camera in place of laser-range finders for range information
* sensitivity of cameras to environmental conditions and
* the difficulty in reliably interpreting images.

Cameras provide more information than a LIDAR

Used for
* navigation
* detecting objects
* recognizing places

algorithm identifies safe and unsafe regions in the robot’s local surroundings and represents this information using an annotated 2D grid map called a local safety map. The 2D local safety map can be used by the robot to plan safe local paths using standard planning algorithms

**Process**:

A. A depth (or disparity) map is computed from the stereo image pair (Fig. 1). The depth readings are transformed into global coordinates (i.e., map coordinates).

B. A 3D model consisting of a 3D grid and 3D point cloud is updated with the new depth readings using an occupancy grid algorithm (Fig. 2).

C. Planes are fit to potentially traversable ground segments in the 3D model. The process consists of segmenting the 3D grid followed by fitting planes to points corresponding to the segments using linear least squares (Fig. 3).

D. Finally, the segments and planes are analyzed for safety to yield the local safety map (Fig. 4).

### Stereo-depth maps

* multi-scale correlation stereo method for computing disparity maps - http://www.videredesign.com/
* 3DOF SLAM to find robot's pose followed by computation of 3D coordinates of point in global frame

### Updating 3D Model

* 3D model comprising of point cloud and occupancy grid
* fixed size grid for local reconstruction
* a ray is cast from the camera to the 3D point and voxels along the ray have their log odds probability (LOP) of occupancy updated; updates -- increment or decrement in LOP by the likelihood of voxel producing the range point

> A voxel starts off with a LOP of zero. Finding the correct sensor model amounts to tuning the relative values of the increment and decrement parameters

* effect of correlation is reduced by updating the grid for only one point per voxel per timestep


* voxels having high occupancy probability are identified to build 3D occupancy grid
* output of this step is a 3D grid of occupied voxels plus the list of points (the 3D point cloud) associated with the occupied voxels

### Segmenting and Plane Fitting to 3D Model

* done to find traversable and non-traversable region
* segmentation involves finding regions of same height
* this is followed by plane fitting by linear least squares fit
* output from this step is the list of ground segments, their associated plane parameters, and also the list of nontraversable voxel columns.

### Building Local Safety Map

* robot's current located segment is marked safe
* all reachable segments - safe; unreachable segments - non ground/unsafe

> The local safety map is then obtained by creating a 2D grid (with the same (u, v) dimensions as the 3D grid) and assigning the same labels to the cells as the labels of their corresponding segments.