Astudy has been undertaken to evaluate a method of detecting change in a three-dimensional (3D) terrain map generated from data acquired by an imaging ladar system carried aboard a moving unmanned ground vehicle (UGV) on patrol. The proposed method involves the use of an evidence grid (described below) in comparing data acquired on a second patrol with data acquired on the first patrol along the same route, in order to determine which, if any, volume elements (voxels) in a 3D map representing the terrain have changed from free space to occupied or vice versa. For the purpose of the method, it is assumed that the terrain is static during each patrol and the only changes of interest occur between patrols. It was recognized in the study that these assumptions are unlikely to hold in realistic scenarios. This study was intended to be a precursor to a study of a method for recognizing a moving obstacle C, particularly a moving pedestrian C during a patrol by an autonomous UGV.

Each Grid Square Represents a Voxel in this simplified representation of a 3D map generated by an imaging-ladar scan of terrain from a moving UGV. The change in each voxel between patrols is calculated to generate a change map, wherein green signifies small change, orange signifies intermediate change, and red signifies large change.
An imaging ladar (equivalently, lidar) system performs a laser raster scan of its surroundings at an angular resolution somewhat less than that of a typical video camera but at a rate comparable to video frame rates. From the instantaneous pointing direction of the laser beam and the instantaneous time of flight of pulsed laser light reflected from that direction, the system measures the direction and distance to the nearest object in that direction. The resulting distance and direction data from repeated scans along the patrol route are combined with position and orientation data from the navigation system of the UGV to generate a digital 3D map of the terrain along the route. The voxels in the digital 3D map are defined by a Cartesian grid having a resolution (typically 0.1 m) that is fine enough to enable detection of most changes of interest, yet coarse enough to reflect the limit on accuracy of the ladar data and to reduce the volume of ladar data that must be acquired and processed.

Because the path traveled by the UGV does not repeat precisely on subsequent patrols, a direct comparison of data points or voxels in maps generated on a first and a second patrol would not be adequate for detecting change and avoiding false alarms. In the present method, one detects change by use of an evidence grid C, a scheme in which voxels are not simply classified as occupied or unoccupied, but, instead, are used to store evidence (data) indicative of the probability that the cell is occupied or unoccupied.

In this scheme, one endeavors to classify a voxel as changed or unchanged depending on whether there has been a specified minimum amount of change between patrols, in the evidence that the voxel is occupied or unoccupied. A number indicative that the voxel is occupied is incremented for each scan during which a ray-trace nominally coincident with the laser beam terminates in that voxel. Similarly, a number indicative of non-occupation is incremented for every voxel through which the ray passes without encountering an object.

Then, evidence of a voxel being occupied during a patrol is quantified (in effect, a probability of occupation of that voxel is calculated) as the ratio between the number of times the voxel was discovered to be occupied and the number of times the voxel was encountered. The absolute value of the difference between the values of this ratio as calculated for the first and second patrols is taken as a measure of change (see figure): if the magnitude of the difference exceeds a specified threshold value, then the status of the voxel is classified as changed from unoccupied to occupied or vice versa. To reduce the incidence of outliers, voxels classified as changed are aggregated into change regions. Any voxel classified as changed that lies within a specified threshold distance of the centroid of a pre-existing change region is assigned to the region, and the centroid is recomputed. In a cleanup step, if two change regions overlap, the smaller one is absorbed into the larger one.

In the study, the method was tested by use of data from pairs of patrols on a wooded terrain and along a dirt road between tree lines. The intentional change between first and second patrols of each pair was, variously, the introduction of a person or the introduction of a person and a small lunch box. The results of the tests were found to be insufficient to enable drawing of any firm conclusions concerning the effectiveness of the method in detecting changes between patrols. However, the results were found to indicate promise for the intended future study of a method of detecting pedestrians or moving objects. The concept of operating on voxelized and normalized processed sensor data, rather than on raw sensor data, was found to be effective in identifying regions of change, at least in the circumstances of this study.

This work was done by Gary A. Haas of the Army Research Laboratory. For further information, download the free white paper at  under the Photonics category. ARL-0001

This Brief includes a Technical Support Package (TSP).
Detecting Change in 3D by Use of an Evidence Grid

(reference ARL-0001) is currently available for download from the TSP library.

Don't have an account? Sign up here.