arXiv:1612.07850v2 [cs.RO] 12 Feb 2017

Automatic Interpretation of Unordered Point Cloud
Data for UAV Navigation in Construction
M.D. Phung, C.H. Quach, D.T. Chu

N.Q. Nguyen

T.H. Dinh and Q.P. Ha

University of Engineering and Technology
Vietnam National University, Hanoi
Hanoi, Vietnam
Email: duongpm@vnu.edu.vn

National Institute of Information
and Communications Strategy
Hanoi, Vietnam

School of Electrical, Mechanical
and Mechatronic Systems
University of Technology Sydney
Sydney, Australia
Quang.Ha@uts.edu.au

Abstract—The objective of this work is to develop a data
processing system that can automatically generate waypoints
for navigation of an unmanned aerial vehicle (UAV) to inspect
surfaces of structures like buildings and bridges. The input
includes data recorded by two 2D laser scanners, orthogonally
mounted on the UAV, and an inertial measurement unit (IMU).
To achieve the goal, algorithms are developed to process the data
collected. They are separated into three major groups: (i) the data
registration and filtering to generate a 3D model of the structure
and control the density of point clouds for data completeness
enhancement; (ii) the surface and obstacle detection to assist the
UAV in monitoring tasks; and (iii) the waypoint generation to set
the flight path. Experiments on different data sets show that the
developed system is able to reconstruct a 3D point cloud of the
structure, extract its surfaces and objects, and generate waypoints
for the UAV to accomplish inspection tasks.

I. I NTRODUCTION
Unmanned aerial vehicles (UAVs) are expected to yield
automatic solutions for inspecting and monitoring large and
hardly accessible structures like bridges, towers, dams, wind
turbines and heritage monuments due to their flexibility in
operating space and ability to carry specialized sensory equipment. In [1], a micro air vehicle system was employed to
scan buildings using a high resolution camera. Pictures taken
were successfully stitched with sufficient quality for crack and
damage detection. In [2], an advanced UAV system were developed to evaluate the state of historical monuments including
a chimney built in early 1980th and a natural stone masonry
tower inclined 4.70 . Images captured after processing revealed
damages in both monuments. A control system for navigation
of the UAV from an initial to a final position in an unknown
3D environment was used to monitor and maintain bridges [3].
UAVs were also used to inspect and monitor oil-gas pipelines,
roads, power generation grids and other essential infrastructure
[4].
In order to complete those inspection missions, the UAV
system typically carries out three steps including creating
waypoints from coarse data of the environment, controlling
the UAV to follow waypoints and collect data of the structure,
and processing the data to detect defects or damages. Among
these steps, the generation of waypoints is still manual with
little support of automation. In [1], the UAV was directly
controlled by a pilot. In [2], the flight plan was set by the
user while work [3] focused on a control strategy without

concerning obstacles. As the result, the deployment process
is time consuming and the data collected are often redundant
and ineffective. For example, among more than 12,000 images
taken in [2] only several hundred images were finally valid for
stitching and inspection.
In this study, we introduce an automatic solution to generate
waypoints for the UAV to inspect and monitor built infrastructure. Input data includes range information acquired by
two laser scanners and orientation measured by an IMU. The
system then can align the range data into point clouds and
register them to represent a 3D model of the structure. Based
on the model, the system detects surfaces, extracts borders and
clusters obstacle objects. For each surface to be inspected, the
system will generate waypoints which are optimized for path
planning and obstacle avoidance. The total processing time,
from loading data to generating waypoint, is several minutes
for the surface with area of hundreds of squared meters.
II. M ETHODOLOGY
Figure 1 presents an overview of the system, consisting of
seven stages. Details of each stage are explained as follows.
A. Data collection
Data used for the system includes range information measured by laser scanners. Due to the limitation in payload and
energy capability, the 3D laser scanner is not suitable for the
UAV. Instead, we use two 2D laser scanners and an IMU to
collect information of the structure. The arrangement is shown
in Fig. 2. The two laser scanners are placed orthogonally to
each other and symmetrically with respect to the center of the
UAV. One scans horizontally and the other scans vertically. The
IMU is fixed at the center of the UAV. The data collection is
carried out by yawing the UAV 360◦ . During yawing, points
acquired by vertical scanning will be used to generate a 3D
point cloud of the structure.
Let (ρi , αi ) be the distance and angle of point pi measured
by the vertical scanner. Its Cartesian coordinates in the local
frame attached to the center of the scanner are given by:
x∗i = −ρi cos(αi )
yi∗ = 0
zi∗

= −ρi sin(αi ).

(1)

Detecting surfaces
& boundaries
Raw sensor
data

Registering

Creating fly
strategy
Generating
waypoints

Pre-processing
Clustering
obstacle objects

Fig. 1: An overview of the system.

(a)

Fig. 3: Horizontal scans: (a) before applying the ICP algorithm,
and (b) after applying the ICP algorithm.

Fig. 2: Hardware configuration for data collection.
As the scanner moves during acquiring data, it is required
to map local coordinates to a fixed global frame. Let the
origin of the global frame be the center of UAV at the initial
scan, associated with x−,y−,and z− coordinates as shown in
Fig. 2. The laser scanner motion is then the combination of two
components: rotation caused by yawing and translation caused
by the external forces like wind acting on the UAV. Let R and
T be respectively the rotation and translation matrices of the
motion. The coordinate vector of point pi in the global frame,
xi = [xi yi zi ]T , is given by:
xi = Ri x∗i + Ti .

(b)

(2)

In our system, Ri is directly measured by the IMU while
T is determined by the horizontal scanner as follows: During
yawing, the horizontal scanner will scan the same surface of
the structure with small changes in position and orientation.
The scans therefore have much in common (Fig. 3a) so that we
can use the iterative closest point (ICP) algorithm [5] to match
them and extract the translation and rotation (Fig. 3b). As the
rotation is already known, we incorporate it by rotating the raw
scans before applying the ICP algorithm. This customization
can improve the accuracy of the estimation and reduce the
computation load.
B. Point cloud registration
After collecting data, point clouds recorded at different
positions need to be combined to a complete 3D model of the
structure. This process is called registration. The key idea is
to identify corresponding points between the point clouds and
to find a transformation that minimizes the distance between
them. We carry it out by first predicting the overlaps between
point clouds based on their recorded positions. We then apply

the ICP algorithm to the predicted overlaps to obtain the
transformation.
C. Pre-processing: point cloud filtering and voxelization
Due to characteristics of the laser scanner, the point cloud
generated in the registration process typically contains sparse
outliers and varies in densities. This complicates the estimation
of point cloud features such as surface normals or curvature
changes, leading to erroneous values, which, in turn, might
cause failure in further processing steps. The objective of the
pre-processing process is hence to filter sparse outliers and
equalize point densities.
The sparse outlier removal is carried out based on computation of the Gaussian distribution of distances from each
point to its neighbors. By comparing the mean, µ, and standard
deviation, σ, with pre-defined global thresholds, a point could
be considered as an outlier and trimmed from the dataset if it
falls outside the µ ± dt σ, where dt is a threshold coefficient
[6]. For density equalization, the voxelization technique is
employed. A uniformly spaced 3D voxel grid is created over
the input point cloud. All points within a voxel are then
presented by the centroid of the voxel. This process can largely
reduce the amount of points, but may introduce a small amount
of geometric error due to quantization.
Fig. 4 demonstrates an example of filtering and applying
voxelization on a dataset. Here, the number of scan points in
the original cloud was cut down from 90,396 points (left) to
80,114 points (right) while isolated points were considered as
outliers and removed.
D. Surface and boundary detection
Surfaces are the main target to be inspected so they need
to be extracted from the point cloud. We use the RANSAC

Input point
cloud

Detect surface using
RANSAC

Surface detected?

No

Yes
Segment and extract the
largest cluster

Detect boundary and
compute area

Greater than the
threshold area?

Fig. 4: Point clouds before and after filtering and voxelizing.

No

Increment counter

Yes
Save parameters

Remove the cluster from
input point cloud

Greater than
maximum number of
retries

No

Yes
Return parameters of
detected surfaces

Fig. 6: Flowchart of the surface and boundary detection.

Fig. 5: Problems related to surface and boundary detection.
(random sample consensus) method and planar model for this
task due their simplicity and robustness [7]. Since a plane
model (ax + by + cz + d = 0) is given, M = [a, b, c, d]T is
the parameter vector to be identified. The estimate procedure
is a repeat of the following steps:
• First, a random subset of the original data is selected.
• A planar model is then fitted to the selected subset.
• Remaining points are then tested against the model. A
point is considered as an inlier if its distance to the model
is smaller than a pre-defined threshold. The fitting model
is reasonable good if it has sufficient inliers.
• The fitting model is refined to better fit all found inliers.
In our system, a threshold value of 20 cm and a repeat of 200
times give compromised performance.
After detecting surfaces, their boundaries need to be de-

termined. For each surface, corresponding inliers are first
projected on the found planar model. The 2D convex hull
algorithm [8] is then employed to fit a bounding polygon to
the projected inliers.
In practice, two problems may arise during using the
RANSAC and convex hull algorithms as illustrated in Fig. 5.
First, the detected surface may contain isolated clusters causing
the boundary to be extended. Second, when detecting small
surfaces, the RANSAC may cause confusion between surfaces
belonging to the structure and objects. In order to deal with the
first problem, we require a high point density of a surface. We
therefore trim out the isolated groups by clustering the surface
and only keep the largest one. The clustering algorithm will be
presented in Section II-E. For the second problem, the inlier
quantity and density are used to compute the area of each
detected surface, which is limited to a threshold set by the
user. Fig. 6 shows a flowchart of the surface and boundary
detection.
E. Obstacle clusterization
The scanned points that do not belong to any surfaces
maintain their importance in UAV navigation. It is suggested
here to cluster them into small groups as obstacles in order to
support the path finding algorithm and UAV’s operator to have
a better vision of the environment. The clusterization is carried
out by finding the nearest neighbour that is essentially similar
to a flood fill algorithm [9], as shown in Fig. 7. We use the 3D
Kd-tree structure to speed up the neighbour searching process.
We then use the octree structure to represent the clusters for
visualization.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Data: A point cloud P
Result: A list of clusters L
Init an empty queue Q;
for each point pi ∈ P do
if pi was not processed before then
Add it to Q;
Mark it as processed;
for each point qj ∈ Q do
Search for its neighbors within a sphere of radius r < ;
for each found neighbor qjk do
if qjk was not processed before then
Add it to Q;
Mark it as processed;
end
end
end
Add Q to the end of L;
Reset Q;
end
end

Fig. 7: Pseudo code of the clustering algorithm.

waypoints by using a path finding algorithm. We implement it
by dividing the work space into a grid of voxels. Each voxel
has the free or occupied status corresponding to the existence
or not of object in that voxel. In order to consider the UAV as
a particle moving without collision between voxels, we mark
all free voxels in a sphere with the radius equal to the largest
dimension of the UAV as occupied. We then use the A-star
algorithm [10] to find the shortest path between stop points.
In each step, the cost to move from one voxel to another
surrounding neighbor is computed as:
C(α, β, γ) = a1 α2 + a2 β 2 + a3 γ 2 ,

(3)

where coordinates α, β, γ ∈ {−1, 0, 1} indicate the position of
neighbor, and the coefficient ai assign a particular weight to
each direction.
III. E XPERIMENTS
The system was evaluated on various sets of data recording
different structures like an office, a building or a bridge. The
UAV used is a quadcopter with the size of 60 cm × 60 cm ×
40 cm equipped with a camera mounted on a two degreeof-freedom gimbal, two laser scanners, an IMU and other
electronic boards.
The laser scanner used is Hokuyo UTM-30LX with the
scanning range of 30 m, detection angle of 270◦ , angular
resolution of 0.25◦ and scan period of 25 ms. The IMU
is Xsense Mti-10 outputting the rotation matrix with the
frequency of 2 KHz, accuracy of 0.5◦ , and no accumulated
error. The software is written in C++ and run on a PC with
the processor Intel Core2 Dual 2.53 GHz and 4 GB RAM.

Fig. 8: A flight strategy to take photos of surfaces for inspection.
F. Flight strategy creation
A flight strategy is a set of positions at which the UAV has
to pause to collect data. In order to create a flight strategy, it
is required to know the assigned tasks, requirements on data
collected, and capability of the sensory devices. For instance,
a common situation would be taking photos of a structure and
sticking them together for defect or damage detection. In this
case, requirements may include the minimum resolution of
photos, at which defects are still detectable and the overlap
percentage between consecutive photos feasible for sticking
and mosaicking. For this, the capability of a sensory device
includes the resolution of the camera, its open angle and the
number of degrees of freedom of the mechanism on which the
camera is mounted. Given those requirements and parameters,
we can compute the area that each photo captures, positions
to take photo, their order, number of positions needed to cover
the surface and thus the flight strategy, as illustrated in Fig. 8.
G. Waypoint generation
The final stage in our system is the generation of waypoints.
They are intermediate points the UAV follows to complete
a flight strategy. Given the flight strategy, we can determine

A. Experiments on hypothesis data sets
Experiments are first carried out on hypothesis data sets
to evaluate the behavior of system in regular and irregular
cases. They include the point clouds containing a single point,
a single line, a single surface, a single cube and a cube with
crossed planes. For the two first cases, no surface is detected.
For the two later cases, all surfaces and their boundaries are
detected.
The flight strategy and waypoints for each surface are also
created as shown in Fig. 9a and Fig. 9b. For the last case, all
surfaces and boundaries are detected, but waypoints are not
generated because the surfaces are blocked by cross planes
(Fig. 9c).
B. Experiments on real data sets
After evaluating the behavior of system on hypothesis data,
experiments on real data sets are carried out. Fig. 10 shows
results of aligning raw scans into four point clouds (Fig. 10a–
Fig. 10d) and registering them to become a complete part of
the bridge with the size of 22 m × 10 m × 4.5 m (Fig. 10e).
The alignment error, measured by yawing 360◦ and comparing
the first and last scans, is 10 cm. Fig. 11 represents the planes
and objects detected with the area threshold of 2 m2 .
Besides planes created by grasses and trees, all main planes
including the bridge surface, pier, sides and land surface are

(a)

(b)

(c)

Fig. 9: Experiments on hypothesis data sets: (a) a single surface, (b) a single cube, and (c) a cube with crossed planes.

(a)

(b)

(d)

(c)

(e)

Fig. 10: Point cloud registration: (a)-(d) registered point clouds from raw data, and (e) merged point cloud.

(a)

(b)

Fig. 11: Surface and obstacle detection: (a) planar surfaces, and (b) obstacle objects.

(a)

(b)

Fig. 12: Waypoints generated to navigate the UV to take photos: (a) bridge surface, and (b) pier.
detected. The boundaries are reliable for the convex surfaces.
However, for the concave surfaces like pier, extra areas should
be accounted for. We deal with this problem by adding a
function to allow manually modification of the boundary. In
practice, this function is useful for not only the concave but
also convex surfaces as it allows the operator to ensure the
accuracy of detected boundaries before generating waypoints
for inspection.
Figure 12a shows the flight strategy and waypoints generated for the task of taking photos of the bridge surface
with the coverage of 60 cm × 40 cm for each photo and the
overlap of 20% between consecutive photos. A total of 1,146
stop points and 6,699 waypoints were generated to cover the
area of 220 m2 . The path generated does not collide with any
obstacles appearing in scans. The result is similar for the pier
surface with 75 stopover points and 891 waypoint generated
(Fig. 12b). The processing time for a surface, from loading
raw data to generating waypoints, averages 3 minutes in which
83% is consumed on aligning and registering point clouds.
This result is very encouraging because manually defining
waypoints for a surface often takes a lot of time or even
becomes impractical for large structures like kilometer-long
bridges. The waypoint generation will be further improved in
a future work involving the deployment of a group of UAVs
[11] in coordinated formation [12] to enhance the scanning
coverage.
IV. C ONCLUSION
In this study, we have introduced a paradigm to collect
and process data for automatic navigation of UAVs in built
infrastructure inspection. A hardware configuration was proposed to acquire sufficient information to reconstruct the 3D
model of the structure while feasible to equip on a micro UAV.
The stages necessary to process point cloud data and extract
semantic information from them are introduced. At each stage,
we have presented details of algorithms used and customization to enhance the performance. Through experiments, it is
shown that the proposed system provides a quick and reliable

solution for the automatic operation of the UAV used in built
infrastructure inspection.
ACKNOWLEDGMENT
The first author would like to acknowledge an Endeavours
Research Fellowship by the Australian Government for the
support (ERF PDR 142403 2015), in part, for this work.
R EFERENCES
[1] C. Eschmann, C.-H. Kuo, C.-M. Kuo, C. Boller, Unmanned aircraft
systems for remote building inspection and monitoring, In Proceedings
of the 6th European Workshop on Structural Health Monitoring (2012)
1–8.
[2] N. Hallermann, G. Morgenthal, Un-manned aerial vehicles (uav) for the
assessment of existing structures, In Proceedings of the 36th IABSE
Symposium 101 (14) (2013) 266–267.
[3] N. Metni, T. Hamel, A uav for bridge inspection: Visual servoing control
law with orientation limits, Automation in Construction 17 (1) (2007)
3–10.
[4] S. Rathinam, Z. Kim, R. Sengupta, Vision-based monitoring of locally linear structures using an unmanned aerial vehicle, Journal of Infrastructure
Systems 14 (1) (2008) 52–63.
[5] P. Besl, N. McKay, A method for registration of 3d shapes, IEEE
Transactions on Pattern Analysis and Machine Intelligence 14 (2) (1992)
239–254.
[6] R. Rusu, Z. Marton, N. Blodow, M. Dolha, M. Beetz, Towards 3d
point cloud based object maps for household environments, Robotics and
Autonomous Systems 56 (11) (2008) 279–941.
[7] M. Fischler, R. Bolles, Random sample consensus: A paradigm for model
fitting with application to image analysis and automated cartography,
Communications of the ACM 24 (6) (1981) 381–395.
[8] C. Barber, D. Dobkin, H. Huhdanpaa, The quick hull algorithm for convex
hulls, ACM Transactions on Mathematical Software 22 (4) (1996) 469–
483.
[9] R. Rusu, Semantic 3d object maps for everyday manipulation in human
living environments, Doctoral Dissertation, Computer Science department,
Technische Universitaet Muenchen, Germany.
[10] P. Hart, N. Nilsson, B. Raphael, A formal basis for the heuristic
determination of minimum cost paths, IEEE Transactions on Systems
Science and Cybernetics 4 (2) (1968) 100–107.
[11] A. Woods, H. La, Q. Ha, A novel extended potential field controller
for use on aerial robots, In Proceedings of the 12th IEEE International
Conference on Automation Science and Engineering (2016) 21–24.
[12] A. Nguyen, Q. Ha, S. Huang, S. Trinh, Observer-based decentralized
approach to robotic formation control, In Proceedings of the 2004 Australasian Conference on Robotics and Automation (2004) 1–8.

