# Algorithm on Converting a 2D Scanning LiDAR to 3D for use in Autonomous Indoor Navigation

^{*}

**Corresponding Author:**Matthew A Cooper, Air Force Institute of Technology, USA, Tel: +1 9372556565, Email: [email protected]

*
Received Date: Dec 01, 2017 /
Accepted Date: Dec 21, 2017 /
Published Date: Jan 05, 2018 *

### Abstract

Autonomous indoor navigation is synonymous with military centric autonomous navigation in GPS-denied environments. Unmanned aerial systems (UAS) are routinely connected to autonomous navigation. This combination of technology has many disparate uses such as in kids toys, photography, and military applications. For each of these areas a major concern is size, weight, and power (SWaP) in the product design. SWaP has a direct effect on the operations of an autonomous UAS such as on the flight time, the maneuverability, controllability, and the durability. This paper presents a basic algorithm describing one aspect of reducing SWaP on an autonomous quad-rotor UAS, by converting a 2D scanning LiDAR sensor to a 3D sensor, thus eliminating the need for additional sensors used to perform localization and mapping. Much that is described here is derived from the thesis work presented by Cooper. The majority of work was performed during a Master’s Thesis investigation by M. A. Cooper titled “Converting a 2D Scanning LiDAR to a 3D System for Use on Quad-Rotor UAVs in Autonomous Navigation.” The work presented here develops the generalized calibration procedure.

**Keywords:**
UAV; LADAR; SLAM; Sensor Calibration; Point Cloud Navigation

#### Introduction

Indoor navigation schemes for use in robotic applications may rely on a suite of sensors to perform essential robot localization and mapping functions. In an autonomous robotic vehicle this is even more important as a lost robot has no more utility than a simple paperweight. Additionally, a suite of navigation sensors may provide streams of data to easily navigate the environment which can include sensors such as the Velodyne HDL-64E [1,2] multiple laser Light Detection and Ranging (LiDAR) sensor, or a 4k resolution at 60 frames per second video stream such as the one on the newly released iPhone X [3]. The data throughput for these can be much more than 2MB per second. This amount of data can provide for a well defined localization and mapping solution but the small form factor of an autonomous indoor UAS may not be able to accommodate these large amounts of data. The process to fuse multiple sources or to store the large amounts of data collected can be debilitating for a small processing system such as a Rasberry PI or Arduino. This presents a need to take a minimalistic approach towards the amount of sensors and data to be collected.

Minimizing the amount of sensors used in an autonomous UAS can bring along many benefits. Benefits such as longer flight time, reduced weight, increased maneuverability, and the ability to add additional capability. In order to reduce the number of sensors an operational design must be calibrated, characterized, and evaluated against the desired operational performance characteristics.

There are two main genres of LiDAR sensor characterizations: intrinsic and extrinsic. Intrinsic calibration and characterization can be accomplished cconcurrently if the sensor equipment allows for enough access to the internal parameters. Okubo presented a quality characterization of a Hokuyo sensor in 2009 [4]. In this Okubo characterized the transfer rate of the sensor output, as well as the effect of drift, surface properties, and incident angles to the sensor measurements. He went on to describe the concept of a “mixed" pixel, which is the result of taking a range measurement from a sensor return that has landed on two distinct surfaces and the resulting range is a combination of the two. Finally, Okubo recommends to use statistical analysis on the raw LiDAR data to perform mapping.

Intrinsic calibration has been described thoroughly [4-6], while extrinsic calibration can take on many forms and has been describe extensively [7-16]. Each different application may need a distinct extrinsic calibration procedure based on the individual application, and each paper underlines the need to perform this extrinsic calibration and corresponding characterization to utilize the sensor effectively.

LiDAR types, sensing techniques, and ranging calculations will not be discussed but more information can be found [17-25].

This paper assumes that a user defined UAS sensor suite configuration used for localization and mapping is able to be minimized. The next major assumption is that a newly modified 3D scanning LiDAR capability will meet the needs of the user if calibrated properly. In addition to the previous assumptions, the final major assumption is that other forms of beam steering is impractical and that the use of a reflective superstructure will provide an avenue to the required performance parameters. The Procedure describes the overall methodology in converting a 2D scanning LiDAR sensor into an effective 3D sensor. It simultaneously discusses a relevant set of specific experiments recommended for characterization of both the original sensor and of the newly modified system. Next in the Calibration Procedure section the general calibration procedure is summarized as a conclusion to the first two sections. This paper uses an application of the recommended procedure as an example which is illustrated throughout the paper. A much more detailed application based around the Hokuyo UST-20LX 2D scanning laser rangefinder can be examined [1].

#### Procedure

**Characterization of Base Sensor**

This first major step is to characterize the original sensor to establish a baseline model with which to base any modifications upon. In this instance the Hokuyo UST-20LX has been chosen as seen in **Figure 1** [24]. This particular model scans in a 270 planar area using 1081 measurements at 40 scans per second.

In order to characterize the sensor a motion capture system, such as a VICON chamber, is recommended to reduce error in measurements. Once a base sensor system and position collection technique is implemented a series of tests can then be performed. The parameters of the most interest are the mean and standard deviation of the range returns, the beam divergence rate, the effect color has on the range returns, and how the effect the target orientation has on the range returns.

Sometimes, only a small percentage of a LiDAR beam will land on the object being ranged. This depends on the size of the object, distance to the object, and the beam divergence angle. Only a fraction of the photons reaching the illuminated target will make it back to the sensor as described by the equation in eqn. (1) as simplified by Richard and Cain [19].

(1)

where *P _{detector}* is the power received by the LiDAR detector,

*τ*=atmospheric transmission rate,

_{a}*τ*is the transmission rate of the optics,

_{o}*D*is the receiving aperture diameter of the detector,

_{R}*ρ*=target surface reflectivity,

_{t}*P*=Laser transmitted power,

_{t}*θ*=laser transmitted beam angular divergence,

_{d}*θ*=the target surface angular dispersion. dA is the smaller of the angular area of the target, area of the field of view of the sensor, or the area of the beam on the target, and R is the distance between the source and the target.

_{R}If enough photons land on the sensor then a range measurement can be taken. The range function, which can be seen in eqn. (2), is a function of the target coordinates, *P _{P}*, and some unknown noise,

*v*. The result is the estimated range, .

(2)

Taking eqn. (2) and applying the range error associated with target angle, *E _{a}*, target color, Ec, and target range,

*E*, then gives a correctable range, as seen in eqn. (3)

_{r}(3)

where is the error corrected result of the range function estimate, .

Because of these relationships it’s important to understand the beam divergence angle. An example test scenario and beam spot shape is shown in **Figure 2**, which may have similar results as drawn in **Figure 3** and in **Table 1**.

Distance (m) | Height (mm) | Width (mm) |
---|---|---|

0.50 | 3.2 | 15.9 |

.00 | 4.0 | 33.3 |

.00 | 4.8 | 55.6 |

.00 | 5.6 | 98.4 |

.00 | 6.3 | 136.5 |

**Table 1:** Triple beam size at multiple distances for UST-20LX.

At each of the test scenes identified in this paper there is also an opportunity to collect data and evaluate the statistics. Recording the range data collected during this test for the Hokuyo UST-20LX sensor resulted in the statistics shown in **Table 2**.

Range | 0.50 m | 2.00 m | 4.00 m | |||
---|---|---|---|---|---|---|

Mean | STD | Mean | STD | Mean | STD | |

Trial 1 | -0.0017 | 0.0041 | 0.0070 | 0.0038 | 0.0008 | 0.0047 |

Trial 2 | -0.0032 | 0.0041 | 0.0058 | 0.0039 | -0.0004 | 0.0046 |

Trial 3 | -0.0036 | 0.0042 | 0.0054 | 0.0039 | -0.0007 | 0.0046 |

**Table 2:** Mean error and standard deviation of UST-20LX.

The next major experimental test scene is the test to quantify the effects of target angle, with respect to the sensor, on the returned LiDAR sensor range. The resulting error may give an error function proportional to the cosine of the angle such as in egn. (4)

(4)

Where *E _{a}* is the range error caused by the target angle,

*A*is a proportionality constant,

_{a}*B*is a constant offset, and

_{a}*θ*is the angle between the target normal and the LiDAR beam. An example test scenario is presented in

_{N}**Figure 4**which shows multiple LiDAR beam paths contacting the target boards. The target boards represent a spectrum of orientation angles ranging between -80° to 80° with respect to the LiDAR beam.

Using a position measuring device such as a calibrated VICON chamber, the error by the LiDAR sensor due to the target angle can be measured. And example can be seen in **Table 3**.

Estimated angle | 0.0° | 20.0° | -45.0° | RMS |
---|---|---|---|---|

Calculated Angle | 0.9° | 18.5° | -44.7° | Error |

Trial 1 | 0.0099 | 0.0271 | 0.0354 | 0.0309 |

Trial 2 | 0.0088 | 0.0274 | 0.0357 | 0.0300 |

Trial 3 | 0.0090 | 0.0277 | 0.0330 | 0.0293 |

**Table 3:** Mean error between range return and actual target distances.

The last major error source is caused by the target’s color. This part of the characterization can be exhaustive but is recommended to tailor it to the materials and color of the target to be used to calibrate the modified sensor.

*E _{c}=A_{c}R+B_{c}* (5)

where *A _{c}* is the proportionality constant, and

*B*is a constant offset. Eqn. (5) assumes a linear error profile along the operational range of interest.

_{c}The recommended test setup is to mimic the beam divergence scenario in **Figure 2**. **Table 4** shows an example data set used when evaluating the Hokuyo UST-20LX sensor.

Distance | Pure white | Antique white | Pencil grey | Jet black |
---|---|---|---|---|

0.493 m | 4.39 mm | 3.96 mm | 3.85 mm | 5.37 mm |

.011 m | 4.64 mm | 4.69 mm | 4.71 mm | 6.06 mm |

.600 m | 3.52 mm | 3.43 mm | 3.96 mm | 5.29 mm |

.007 m | 3.71 mm | 3.55 mm | 4.18 mm | 5.00 mm |

Mean | 4.09 mm | 3.94 mm | 4.19 mm | 5.44 mm |

**Table 4:** Standard deviation of sensor returns for gray level test.

Once the characterization of the original sensor is finalized, a study on the required operational needs and what modifications are needed can be done.

**Identify effects of modification**

The effects of the modification will depend greatly on the modifications imposed and a recommended set of tests for every case would be too large for this paper to list. **Figure 5** represents a possible modification. The base sensor is in the center and colored gray. The superstructure is in a lighter gray with the mirrored surfaces highlighted in red.

From the prototype design, the modifications may limit the original sensor’s field of regard so a new field of regard needs to be identified as in **Figure 6** in green. To develop the new field of regard, the characterization process outlined in Section I-A should be repeated using the proposed modifications.

**Develop parameter estimation for extrinsic characteristics**

For each element within the identified field of regard of the modified sensor, some additional steps need to be taken in order to transform the raw data of the sensor into something usable. The sensor itself may not be programmable to incorporate the effects of the modification into the sensor output and therefore some post processing needs to occur. The first step is to calculate a range equation due to a potentially different beam path caused to the sensor modifications.

The range function, as seen in eqn. (6), is now a function of the target coordinates, *PP*, the base azimuth of the beam from the sensor origin, *θB*, the azimuth of the deflection angle due to the mirror, *θa*, the elevation of the deflection angle, *φ*, the distance to the deflection point on the superstructure mirror from the sensor origin, *d*, and some unknown noise, *v*. The result is the estimated range for the modified sensor, .

(6)

**Figures 7** and **8** represent a planar view of the X-Y, and X-Z planes, respectively, each describing the range function from a different view.

**Figure 7** shows the base azimuth angle, *θ _{B}*, in green that ends at point

*P*, which is the starting point of the intercept vector of the target.

_{L1}*P*is also the point of deflection at distance

_{L1}*d*from the origin. The deflection angles,

*θ*, and

_{a}*φ*are shown in

**Figure 8**.

*P*is used to create a vector from

_{L2}*P*which intercepts a target board described by

_{L1}*P*, and

_{P1}, P_{P3}*P*at an unknown point

_{P3}*P*.

_{target}Taking this point-plane intercept concept [26,27] a little further it is possible to create another relevant test. **Figure 9** shows an example test scenario using the laser source, bouncing the LiDAR beam off a mirror and intercepting a multitude of target boards. Only one target should be ranged against at a time, but each range measurement needs to range against a target at a different orientation. These range measurements , along with the orientation of the target board, *θ*, can be used to create a Jacobian matrix, *H*, as seen in eqn. (7)

(7)

*δθ*, and *δφ* are small perturbations on the scale of 1 × 10^{-3}, and *n* is the number of target board orientations ranged against. A standard Recursive Least Squares parameter estimation technique [27-29] can now be developed using this Jacobian as in eqn. (8)

(8)

Where *Δθ* and *Δφ* are from the current estimates. The error between the estimated range and the measured range from the sensor using eqn. (8) where is the error corrected range measurements given by the sensor and are the residuals between the estimated range and the sensor measured range. The RLS algorithm will iteratively minimize *x* until a user defined threshold.

**Figure 10** shows a series of 10 trials estimating the azimuth, *θ _{B}*, in blue, and the elevation,

*φ*, in magenta for one of the deflecting mirrors illustrated in the prototype in

**Figure 5**. In this instance the correction factors,

*Ec, Ea*, and

*Er*are applied and the results are shown in bold. It can be seen that the corrections applied do in fact alter the mean and decrease the variance of the parameters.

Once this is performed for each individual element identified in **Figure 6** then the final step in performing a transformation of each point along the original two-dimensional X-Y plane to the newly deflected LiDAR ranging location in 3D space can be completed. The resulting transformations will lead to a 3D point cloud comprised of all the usable elements as seen in eqns. (9) and (10).

(9)

(10)

where is the rotation matrix in a 3-2 sequence for the *n ^{th}* beam,

*P*is the coordinate of the

_{0}[n]*n*range element, and

^{th}*P*is the translation of the

_{L1}[n]*n*range element from the sensor beam frame to the new frame.

^{th}*P*corresponds to the

_{C1}[n]*n*point of the resulting 3D point cloud,

^{th}*PC*, relating to the

_{1}*n*beam element of the sensor range returns.

^{th}#### Calibration Procedure

The calibration procedure is the retelling of the results of the previous steps in the methodology to include the characterization of the sensor, data filtering, and the validation of the range and RLS functions. The algorithm is intended to wrap all the previous steps into a generalized, but sufficiently detailed, pattern to be able to replicate the process with new and unique modifications.

**Calibration algorithm**

1. Characterize the operationally relevant parameters of the original sensor to form a baseline.

2. Take the fabricated mirror structure and attach to the 2D scanning LiDAR sensor. Arrange a placement of VICON markers on the structure such that minimal or no erroneous reflections will be seen on the sensor. Create a VICON object from these points using the corresponding chamber and markers.

3. Take initial measurements of each expected deflection point of the laser on the structure. It is preferable to take range measurements before any reflective surfaces are attached to the structure and then to add an offset to the returned range measurements due to the thickness of the reflective surface being added.

4. Run data collection (10k+ data points) in a known environment using the estimated *d, φ,* and *θ* to calculate the initial range vector measurements, r. Eliminate any range scan elements that return with abnormal or inconsistent range statistics.

5. Establish the transformation between the sensor object inside the fabricated mirror structure and the point of origin of the laser source (laser base frame).

6. Convert target board coordinates with respect to the laser base frame.

7. Place target in desired location that allows for the first set of elements in the sensor laser beam to intercept the target near the center of mass. Collect range and position data. Adjust target to a new unique orientation such that the same elements of the sensor laser beam fall near the center of mass of the target. Repeat for a minimum of three target positions.

8. Move target to a new location such that the next series of elements in the sensor beam intercept near the target’s center of mass.

9. Adjust target to a new unique orientation such that the same elements of the sensor laser beam fall near the center of mass of the target. Repeat for a minimum of three target positions then move to the next series of elements in the sensor beam.

10. Repeat the previous step until all desired elements of the laser scan field of regard have data collected as intercepted at a minimum of three targets in unique positions.

11. Run RLS algorithm, separately for each beam to calculate the estimated *φ*, and .

12. Calculated the transformation for each scan element using the measured *d*, and the calculated *φ*, and *θ* from the RLS algorithm.

13. Implement the transformations calculated and verify the expected output. Original 2-dimensional planar point cloud results from the sensor output should be realized as the 3-dimensional point cloud of the target environment.

#### Disclaimer

The views expressed in this paper are those of the authors, and do not reflect the official policy or position of the United States Air Force, Department of Defense, or U.S. Government.

#### References

- Cooper MA (2017) Converting a 2d scanning LiDAR to a 3d system for use on quad-rotor UAVs in autonomous navigation.
- Velodyne Acoustics (2017) Velodyne LiDAR- HDL-64E.
- iPhone x.
- Okubo Y, Borenstein J, Ye C (2009) Characterization of the Hokuyo URG- 04LX Laser Rangefinder for Mobile Robot Obstacle Negotiation. SPIE Proceedings 7332: 1-10.
- Adams MD (2000) Lidar design, use, and calibration concepts for correct environmental detection. IEEE Transactions on Robotics and Automation 16: 753-761.
- Muhammad N, Lacroix S (2010) Calibration of a rotating multi-beam Lidar. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp: 5648-5653.
- Choi DG, Kim JS, Bok Y (2016) Extrinsic Calibration of 2-D Lidars Using Two Orthogonal Planes. IEEE Transactions on Robotics 32: 83-98.
- Chen W, Xiong W, Wang Y, Chia S, Du J, et al., (2016) A Noise-Tolerant Algorithm for Robot-Sensor Calibration Using a Planar Disk of Arbitrary 3-D Orientation. IEEE Transactions on Automation Science and Engineering 15: 1-14.
- He M, Davoine F, Zhao H (2013) Pairwise LIDAR Calibration Using Multi-Type 3D Geometric Features in Natural Scene. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp: 1828-1835.
- Jonathan, Brookshire Seth T (2011) Automatic Calibration of Multiple Coplanar Sensors. Proceedings of Robotics: Science and Systems, pp: 33-40.
- Quenzel J, Papenberg N, Behnke S (2016) Robust Extrinsic Calibration of Multiple Stationary Laser Range Finders. 12th IEEE International Conference on Automation Science and Engineering (CASE), pp: 1332-1339.
- Debattisti S, Mazzei L, Panciroli M (2013) Automated extrinsic laser and camera inter-calibration using triangular targets. IEEE Intelligent Vehicles Symposium, Proceedings, pp: 696-701.
- Pandey G, Mcbride JR, Savarese S, Eustice RM (2012) Automatic Targetless Extrinsic Calibration of a 3D Lidar and Camera by Maximizing Mutual Information. Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, pp: 2053-2059.
- Huang PS, Hong WC, Chen CY, Chein HJ (2013) Extrinsic calibration of a multi-beam lidar system with improved intrinsic laser parameters using v-shaped planes and infrared images. IVMSP Workshop 11: 3-6.
- Guo CX, Roumeliotis SI (2013) An analytical least-squares solution to the line scan LIDAR-camera extrinsic calibration problem. IEEE International Conference on Robotics and Automation pp: 2943-2948.
- Lin CC, Luo WJ, Liao YD (2013) Calibration Method for Extending Single-Layer LIDAR to Multi layer LIDAR. IEEE/SICE International Symposium on System Integration (SII), pp: 677-681.
- Bachman CG (1979) Laser Radar Systems and Techniques. Artech House.
- Jelalian AV (1992) Laser Radar Systems. Artech House.
- Richmond RD, Cain SC (2010) Direct-Detection LADAR Systems. SPIE Press.
- Greenfeld J (2015) Terrestrial and mobile lidar mapping systems: Understanding the technology, applications and opportunities.
- Nasa (2010) Flash lidar technology overview. Advanced Scientific Concepts Inc Presentation Posted by NASA.
- John SC, Christian A (2014) A survey of lidar technology and its use in spacecraft relative navigation. In: Survey of Current Technology. American Institute of Aeronautics and Astronautics.
- Romano ME (2015) Commercial geiger mode lidar. Harris Radio Corp: Public Presentaion.
- Ust-10lx/20lx product page.
- Edwards CH, Penney DE (2002) Multivariable Calculus. 6th (edn.), Lebanon. In: Prentice Hall.
- Bowyer A, Woodwark J (1983) A Programmer’s Geometry. Butterworths.
- Slotine JJ, Li W (1991) Applied nonlinear control. Prentice-Hall Englewood Cliffs, NJ.
- Luenberger DG (1979) Introduction to Dynamic Systems: Theory, Models, & Applications. John Wiley & Sons, p: 446.
- Fossen TI (1993) Comments on hamiltonian adaptive control on spacecraft. In: IEEE Transactions on Automaic Control 38: 671-672.

Citation: Cooper MA, Raquet JF, Patton R (2018) Algorithm on Converting a 2D Scanning LiDAR to 3D for use in Autonomous Indoor Navigation. Adv Robot Autom 7: 184. DOI: 10.4172/2168-9695.1000184

Copyright: © 2018 Cooper MA, et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.