Method of processing 3D sensor data to provide terrain segmentation

1. A method of processing 3D sensor data associated with a terrain to provide terrain segmentation, the method comprising:

generating, by a 3D sensor, the 3D sensor data, wherein the 3D sensor data comprises a respective coordinate set for each of a series of returns detected by a 3D sensor positioned above the terrain by scanning the 3D sensor over the terrain in a known smooth, analytical scan pattern, each coordinate set corresponding to a position vector with respect to the 3D sensor of a point in the terrain giving rise to a respective return and the coordinates defining a horizontal plane;

identifying a series of returns having positions in the horizontal plane that would lie on a substantially smooth path or scan line in the horizontal plane for returns from a flat terrain and the known analytical scan pattern; and

processing the horizontal coordinates of the returns in order to identify returns having positions in the horizontal plane deviating by more than a pre-determined extent from positions of returns from a hypothetical plane;

classifying the deviating returns as non-ground returns corresponding to elevated objects in the terrain;

differentiating non-ground returns from ground returns using the classification of deviating returns;

identifying one or more further series of returns, each further series comprising further returns that would lie on a respective substantially smooth path or scan line in the horizontal plane for returns from a flat terrain and the known analytical scan pattern;

processing horizontal coordinates of the further returns in each further series to identify further returns having positions in the horizontal plane deviating by more than a pre-determined extent from the corresponding substantially smooth path or scan line; and

classifying the deviating further returns as non-ground returns corresponding to elevated objects in the terrain;

providing full terrain segmentation of the 3D sensor data using the classification of the deviating further returns to establish clear pathways for a vehicle; and

enabling displaying, by further processing, of the terrain segmentation to a pilot or driver of said vehicle,

wherein for a given set of returns, the returns are considered sequentially in order of horizontal position for correspondence to a non-ground return corresponding to an elevated object, and wherein, upon detection of a non-ground return in the set, the method further comprises the steps of:

(i) identifying a next return in the set that is subsequent in horizontal position in the set to the non-ground return and which corresponds to a ground return;

(ii) for each return in the set intermediate in horizontal position between that of the non-ground return and that of the ground return identified in step (i), evaluating the distance in the horizontal plane between that return and an adjacent scan line; and

(iii) when the distance is less than a pre-determined threshold value, classifying the corresponding return as a non-ground return from an elevated object.

2. The method of claim 1 , wherein the step of processing the horizontal coordinates of returns in a given series in order to identify returns having positions in the horizontal plane deviating by more than a pre-determined extent from the corresponding substantially smooth path or scan line is carried out by the steps of:

evaluating the distances in the horizontal plane between pairs of adjacent returns in the series; and

classifying a return as corresponding to a non-ground return from an elevated object in the terrain when the distance of the return from a neighbouring return in the series exceeds a pre-determined threshold value.

3. The method of claim 1 , wherein the step of processing the horizontal coordinates of returns in a given series in order to identify returns having positions in the horizontal plane deviating from the corresponding substantially smooth path or scan line by more than a pre-determined extent is carried out by the steps of:

calculating an average path in the horizontal plane based on the positions of the returns in the horizontal plane; and

identifying a given return in the series as corresponding to a return from an elevated object in the terrain if its distance from the average path exceeds a pre-determined threshold value.

4. The method of claim 1 , wherein the step of processing the horizontal coordinates of returns in a given series in order to identify returns having positions in the horizontal plane deviating from the corresponding smooth path or scan line by more than a pre-determined extent is carried out by the steps of:

for a return under consideration, evaluating the angle in the horizontal plane between straight lines connecting the return to respective adjacent returns in the series; and

classifying the return as a return from an elevated object in the terrain when the angle is less than a pre-determined threshold value.

5. The method of claim 1 , further comprising the steps of:

(i) mapping returns classified as ground returns and non-ground returns to an array of corresponding ground and non-ground pixels, a pixel being classified as a ground pixel in absence of a corresponding return;

(ii) identifying any ground pixel that is adjacent in the horizontal plane to a non-ground pixel;

(iii) for each pixel identified in step (ii), evaluating the difference between its height value and that of the adjacent non-ground pixel;

(iv) for each pixel identified in step (ii), evaluating the difference between its height value and that of the lowest ground pixel in the 3D data; and

(v) re-classifying a pixel identified in step (i) as a non-ground pixel if the difference found in step (iii) is less than the difference found in step (iv).

6. The method of claim 1 , wherein for each return in the 3D data set, a corresponding position vector makes an angle with the horizontal plane of less than 45 degrees.

7. The method of claim 1 , wherein the 3D sensor data is pre-processed to eliminate noise resulting from artifacts caused by the 3D sensor or environmental artifacts.

8. The method of claim 1 , wherein the 3D sensor data is pre-processed to limit potential terrain measurements by taking into account only the final measured distance in the case of multiple returns from a single angular position with respect to the 3D sensor.

9. A non-transitory computer-readable medium comprising program instructions, which when executed by a computer cause the computer to:

generate, using a 3D sensor, 3D sensor data associated with a terrain, wherein the 3D sensor data comprises a respective coordinate set for each of a series of returns detected by a 3D sensor positioned above the terrain by scanning the 3D sensor over the terrain in a known smooth, analytical scan pattern, each coordinate set corresponding to a position vector with respect to the 3D sensor of a point in the terrain giving rise to a respective return and the coordinates defining a horizontal plane;

identify a series of returns having positions in the horizontal plane that would lie on a substantially smooth path or scan line in the horizontal plane for returns from a flat terrain and the known analytical scan pattern; and

process the horizontal coordinates of the returns in order to identify returns having positions in the horizontal plane deviating by more than a pre-determined extent from positions of returns from a hypothetical plane;

classify the deviating returns as non-ground returns corresponding to elevated objects in the terrain;

differentiate non-ground returns from ground returns using the classification of deviating returns;

identify one or more further series of returns, each further series comprising further returns that would lie on a respective substantially smooth path or scan line in the horizontal plane for returns from a flat terrain and the known analytical scan pattern;

process horizontal coordinates of the further returns in each further series to identify further returns having positions in the horizontal plane deviating by more than a pre-determined extent from the corresponding substantially smooth path or scan line; and

classify the deviating further returns as non-ground returns corresponding to elevated objects in the terrain; and

provide full terrain segmentation of the 3D sensor data using the classification of the deviating further returns to establish clear pathways for a vehicle; and

enabling displaying, by further processing, of the terrain segmentation to a pilot or driver of said vehicle,

wherein for a given set of returns, the returns are considered sequentially in order of horizontal position for correspondence to a non-ground return corresponding to an elevated object, and wherein, upon detection of a non-ground return in the set, the program instructions when executed by a computer further cause the computer to:

(i) identify a next return in the set that is subsequent in horizontal position in the set to the non-ground return and which corresponds to a ground return;

(ii) for each return in the set intermediate in horizontal position between that of the non-ground return and that of the ground return identified in step (i), evaluate the distance in the horizontal plane between that return and an adjacent scan line; and

(iii) when the distance is less than a pre-determined threshold value, classify the corresponding return as a non-ground return from an elevated object.