An optimal hierarchical clustering approach to
segmentation of mobile LiDAR point clouds
Sheng Xu, Ruisheng Wang, Han Zheng
Department of Geomatics Engineering, University of Calgary, Alberta, Canada

arXiv:1703.02150v2 [] 9 Nov 2017

Abstract
This paper proposes a hierarchical clustering approach for the segmentation of mobile LiDAR point clouds.
We perform the hierarchical clustering on unorganized point clouds based on a proximity matrix. The dissimilarity
measure in the proximity matrix is calculated by the Euclidean distances between clusters and the difference of
normal vectors at given points. The main contribution of this paper is that we succeed to optimize the combination
of clusters in the hierarchical clustering. The combination is obtained by achieving the matching of a bipartite
graph, and optimized by solving the minimum-cost perfect matching. Results show that the proposed optimal
hierarchical clustering (OHC) succeeds to achieve the segmentation of multiple individual objects automatically
and outperforms the state-of-the-art LiDAR point cloud segmentation approaches.
Key words: Segmentation, MLS, Hierarchical clustering, Bipartite graph.

I. I NTRODUCTION
Segmentation is the process of partitioning input data into multiple individual objects. In general, an
individual object is defined as a region with uniform attribute. In point cloud segmentation, the results
can be divided into three levels, namely the supervoxel level [1], primitive level (e.g. line [2], plane [3]
and cylinder [4]), and object level [5]–[8].
Due to the fact that point clouds are noisy, uneven and unorganized, the accuracy of the segmentation
is far from being desired, especially in the segmentation of multiple overlapping objects. This paper aims
to propose a hierarchical clustering approach for the segmentation of mobile LiDAR point clouds in the
object level. In order to obtain the optimal combination of clusters, we use the matching in a graph to
indicate the combination and achieve the optimal solution by solving the minimum-cost perfect matching
in a bipartite graph.
This paper is organized as follows. Section II reviews merits and demerits of the related segmentation
methods. Section III overviews the procedure of the proposed optimal hierarchical clustering approach.
Section IV calculates the proximity matrix to store the dissimilarity of clusters. Section V presents details
of the clustering optimization. Section VI shows experiments to evaluate the performance of the proposed
algorithm. The conclusions are outlined in Section VII.
II. R ELATED WORK
Segmentation from point clouds collected by laser sensors with an accurate 3D information plays an
important role in the environmental analysis, 3D modeling and object tracking. In the following, related
methods proposed for the segmentation of point clouds will be reviewed and analyzed.
In the work of Douillard et al. [6], they propose a Cluster-All method for the segmentation of dense
point clouds and achieve a trade-off in terms of the simplicity, accuracy and computation time. Their
Cluster-All is performed based on the k-nearest neighbors approach. The principle of KNNiPC (k-nearest
neighbors in point clouds) is to select a number of points in the nearest Euclidean distance for a given
point and assign them the same group index. To decrease the under-segmentation rate in results, the
variance and mean of the Euclidean distances of the points within a group are restricted to be less than
a preset threshold value. A similar approach is shown in the work of Klasing et al. [8]. They present
a radially nearest neighbor strategy to bound the region of neighbor points which helps enhance the
robustness of the neighbor selection. KNNiPC works well in different terrain areas and does not require

1

any prior knowledge of the location of objects. The problem is that results of KNNiPC highly depend on
the selection of a “good value” for k.
In the segmentation of point clouds, the challenging is to separate two overlapping objects. In the method
of Yu et al. [5] , they propose an algorithm for segmenting street light poles from mobile point clouds.
In order to separate a cluster with more than one object, they add the elevation information to extend
the 2D normalized-cut method [9]. Their proposed 3DNCut (3D normalized-cut) partitions input points
into two disjoint groups by minimizing the similarity within each group and maximizing the dissimilarity
between different groups. 3DNCut obtains an optimal solution of the binary segmentation problem which
demonstrates a promising method for mobile LiDAR point cloud segmentation. The shortcoming is that
the number of objects has to be preset manually in the multi-label segmentation task. In the method
of Golovinskiy et al. [7], they present a min-cut based method (MinCut) for segmenting objects from
point clouds. MinCut partitions input points into two disjoint groups, i.e. background and foreground,
by minimizing their energy function. The solution cut, which is used to separate the input scene into
background and foreground, is obtained by the graph cut method [10]. MinCut obtains competitive
segmentation results in terms of the optimum and accuracy. However, MinCut requires for the location
of each object in the multi-object segmentation task. To achieve the desired performance, users have to
set the center point and radius for different objects manually.
Clustering is a well-known technique in data mining. It aims to find borders between groups based on
defined measures, such as the density and Euclidean distance. The goal is that data in the same group
are more similar to each other than to those in other groups. If we use one called ‘object distance’
as the dissimilarity measure in the clustering, the result of the clustering will coincide with the object
segmentation in point clouds. The clustering approach may provide a new perspective in the segmentation
of individual objects.
In general, clustering methods are divided into five groups, including partitioning, hierarchical, densitybased, grid-based or combinations of these [11]. Both density-based [12], [13] and grid-based methods
[14] highly rely on the assumption that cluster centers have a higher density than their neighbors and each
center has a large distance from points with higher densities. Most density- and grid-based algorithms
require users to specify density thresholds for choosing cluster centers. However, the density of the LiDAR
data depends on the sensor and the beam travel distance. Points within an object may have various
densities, thus, density- and grid-based clustering methods are not suitable for achieving the multi-object
segmentation from LiDAR point clouds.
The classical partition method is the k-means approach, which has been used for the point cloud
segmentation in [15], [16]. The idea of KMiPC (k-means in point clouds) is to partition points into
different sets to minimize the sum of distances of each point in the cluster to the center. In the work of
Lavoue et al. [15], they use k-means for the segmentation of ROI (region of interest) from mesh points.
The problem is that KMiPC is easy to produce redundant segments as shown in [15]. Therefore, a merging
process to reduce the over-segmentation rate is required. Moreover, KMiPC asks for setting the number
of clusters manually and tends to segment groups evenly as shown in [16]. In the work of Feng et al. [17],
they propose a plane extraction method based on the agglomerative clustering approach (PEAC). They
segment planes from point clouds efficiently. PEAC can be used for the individual object segmentation
by merging clusters belonging to the same object. The shortcoming is that their input point clouds are
required to be well-organized.
This paper aims to propose a new bottom-up hierarchical clustering algorithm for the individual object
segmentation from LiDAR point clouds. Our agglomerative clustering starts with a number of clusters
and each of them contains only one point. A series of merging operations are then followed to combine
similar clusters into one cluster to move up the hierarchy. An individual object will be lead to the same
group in the top hierarchy. The proposed hierarchical clustering algorithm does not request for presetting
the number of clusters or inputting the location of each object, which is significant in the segmentation
of multiple objects. The combination of clusters in the hierarchical clustering is optimized by solving the
minimum-cost perfect matching of a bipartite graph.
2

III. M ETHODOLOGY
This section will show details of our optimal hierarchical clustering (OHC) algorithm for the point cloud
segmentation. First, we show the procedure of the proposed hierarchical clustering to give an overview of
our methodology. Then, we focus on the calculation of the dissimilarity to form the proximity matrix for
optimizing the cluster combination. Finally, we use the matching in a graph to indicate the combination
solution and achieve the optimal combination via solving the minimum-cost perfect matching in a bipartite
graph.
A. The procedure of the proposed OHC
Assume that the input point set is P = {p1 , p2 , ..., pn } and the cluster set is C = {c1 , c2 , ...ci , ..., cj , ..., ct }.
n is the number of points in P and t is the number of clusters in C. Each cluster ci contains one or more
points from P , and ci ∩ cj is Ø under i 6= j. The goal of OHC is to optimize the set C to achieve that
each ci ∈ C is a cluster of points of an individual object. A brief overview of our OHC is as follows.
(1) Start with a cluster set C and each cluster ci consists of a point pi ∈ P ;
(2) Calculate the proximity matrix by measuring the dissimilarity of clusters in C;
(3) Calculate the optimal solution for merging clusters by
X

arg min
Ω

D(Mi )

(1)

Mi ∈Ω

where Mi = {ca , cb } means a pair of clusters, and ca ∈ C and cb ∈ C. Ω = {M1 , M2 , ..., Mi , ...} is
the set of the pair of clusters and Mi ∩ Mj = Ø. D(∗) is the dissimilarity of two clusters stored in the
proximity matrix;
(4) Combine clusters in each Mi ∈ Ω into one cluster and use those combined clusters to update the
set C;
(5) Repeat (2)-(4) until C converges.
In the initialization, each cluster ci contains only one point from P , t is equal to n and the size of the
proximity matrix is t × t. In the hierarchical clustering, similar clusters are combined into one cluster and
thus the value of t will be reduced in the clustering process. The key steps in the procedure are (2) and
(3) which will be discussed in the following sections.
B. The calculation of the proximity matrix
For a set with t clusters, we define a t × t symmetric matrix called the proximity matrix. The (i, j)th
element of the matrix means the dissimilarity measure for the ith and jth clusters (i, j = 1, 2, ..., t). In
the hierarchical clustering, two clusters with a low dissimilarity are preferred to be combined into one
cluster.
In our work, the calculation of the dissimilarity contains a distance measure α (pi , pj , ci , cj ) and a
direction measure β (pi , pj , ci , cj ). The distance term α (pi , pj , ci , cj ) is formed as
α (pi , pj , ci , cj ) =

d(pi , pj )
max(m(ci ), m(cj ))

(2)

where d(∗, ∗) is the Euclidean distances of two points. Clusters ci and cj are two different clusters in the
set C. Points pi and pj are obtained by
(pi , pj ) = arg min0 d(p, p0 ) : p ∈ ci , p0 ∈ cj
(p,p )

3

(3)

The density of LiDAR points relies on the scanner sensor and the beam travel distance, therefore, the
magnitude of distances of points are various in different groups. In the calculation of α (pi , pj , ci , cj ), we
use m(∗), which is based on a median filter Med and defined by Eq.(4), to normalized the Euclidean
distance values of points in different groups.
m(ci ) = Medp∈ci { 0 min0

p ∈ci ,p 6=p

d(p, p0 )}

(4)

For example, if we have a cluster c0 = {p1 , p2 , p3 } and the minimal distance between the point pi ∈ c0
and other points is di , our m(c0 ) is obtained by the median value of {d1 , d2 , d3 }.
Our direction measure is based on the normal vector information. In our work, the normal vector at
a point is approximated with the normal to its k-neighborhood surface by performing PCA (Principal
Component Analysis) on the neighborhoods covariance matrix [18]. The direction term β (pi , pj , ci , cj ) is
formed as
β (pi , pj , ci , cj ) = 1 − |V(pi ) · V(pj )|

(5)

where V(pi ) and V(pj ) are normal vectors estimated from the k-nearest neighbor points of pi and pj ,
respectively. Points pi and pj are obtained in Eq.(3).
According to our prior knowledge, the object’s exterior points are potential to be the overlapping points
of different objects and interior points are mostly from the same object. Thus, the proximity matrix PM
is defined as
 λ−1
 λ α (pi , pj , ci , cj ) + λ1 β (pi , pj , ci , cj ) , δpi ,pj = 1
PM(ci , cj ) = λ1 α (pi , pj , ci , cj ) + λ−1
β (pi , pj , ci , cj ) , δpi ,pj = 0
λ
 1
1
α
(p
,
p
,
c
,
c
)
+
β
(pi , pj , ci , cj ) , δpi ,pj = 0.5
i j i j
2
2

(6)

where λ is a user-defined weight coefficient to balance the distance measure α (pi , pj , ci , cj ) and the
direction measure β (pi , pj , ci , cj ). The δpi ,pj is to predict the region of the point pi and pj . If both pi and
pj are interior points, which are assumed to be in the same cluster, δpi ,pj = 1; if both of them are exterior
points, which are assumed to be in different clusters, δpi ,pj = 0; in all other conditions, δpi ,pj = 0.5. In our
work, the dissimilarity of two clusters is small if they are spatially close or normal vectors at the given
points are consistent. When both two clusters consist of interior points, the dissimilarity is dominated by
the distance measure. When both two clusters consist of exterior points, the direction measure dominates
their dissimilarity.
To calculate δpi ,pj , we propose a local 3D convex hull testing method to mark the exterior and interior
points. The proposed testing proceeds as follows: (1) initialize all input points as unlabeled points; (2)
check if a point is not labeled as an interior point; (3) pick up its k-nearest neighbor points to construct
a local 3D convex hull; (4) label all points inside the hull as interior points; (5) repeat (2)-(4) until all
input points are tested; (6) mark the rest unlabeled points as exterior points.
To implement the testing, we form a local 3D convex hull using four vertices, namely v1 , v2 , v3 and
v4 , as shown in Fig.1(a). The target is to test if a vertex v0 is an interior point or not. As shown in Fig.1,
the vector g0 = (v0 − v1 ) can be represented by the sum of vectors g1 = (v2 − v1 ), g2 = (v3 − v1 ) and
g3 = (v4 − v1 ) as
g0 = u × g1 + v × g2 + w × g3

(7)

Based on Eq.(7), one can conclude that if u ≮ 0, v ≮ 0, w ≮ 0 and u + v + w < 1, v0 will be inside the
3D convex hull. Our testing relies on values of u, v and w, which can be solved efficiently by
[u, v, w]> = [g1 , g2 , g3 ]−1 · g0
4

Fig. 1. Illustration of the local 3D convex hull testing. (a) The testing of a vertex v0 . (b) A close-up view of a local 3D convex hull. (c)
Extracted exterior points (red) and interior points (blue).

If v0 is inner the 3D convex hull, it will be labeled as an interior point. Each point from the input will
be selected as a vertex and tested in a local convex hull constructed by its k-nearest neighbor points. In
building the 3D convex hull, v1 is chosen as the furthest point to v0 , v2 is the point to obtain the largest
projection of g1 on the g0 direction (i.e. arg max(|g1 | · cos < g1 , g0 >)), v3 is the furthest point to the line
v2
containing v2 and v1 , and v4 is the furthest point to the plane containing v1 , v2 and v3 . A close-up view
of a local 3D convex hull is shown in Fig.1(b) and Fig.1(c) shows the extracted interior points (blue) and
exterior points (red) from a test set.
C. The optimization of the clustering
Usually, the hierarchal clustering uses a greedy strategy in the combination of clusters. The idea is to
find the most similar two clusters based on the proximity matrix first, and then combine them into one
cluster. Repeat the above steps until all objects are grouped in the same cluster. The greedy strategy is
easy to incur a local optimization. This section targets at optimizing the combination of clusters globally.
Denote our graph as G = {Vx , Vy , E}, where the node set Vx = {c1 , c2 , ..., ci , ..., cn } describes the
current clusters in the set C and Vy shows clusters for the combination. In the hierarchical clustering,
any two clusters can be combined into one cluster, therefore, we let Vy = Vx . The edge set E =
{e1,1 , e1,2 , ...., e1,n , e2,1 , ...., e2,n , ..., ei,j , ..., en,1 , ..., en,n } shows connections between the cluster ci ∈ Vx
and cj ∈ Vy . The edge between ci and cj is denoted as ei,j : ci ↔ cj . There is no edge inside Vx or Vy ,
therefore, our graph G can be regarded as a bipartite graph as shown in Fig.2.
In each hierarchy of the hierarchical clustering, a cluster can be combined with no more than one
cluster. In our work, the combination of clusters is indicated by the perfect matching in a bipartite graph.
The matching of a graph is a set of edges without common vertices. The perfect matching means that
every cluster is connected with a different cluster in the matching. The result of the hierarchical clustering
can be determined by a perfect matching as shown in Fig.3. In our perfect-matching-based representation,
the edge ei,j : ci ↔ cj , which is between ci ∈ Vx and cj ∈ Vy under i 6= j, means that the cluster ci and
cj will be combined into one cluster and the edge ei,i : ci ↔ ci means that the cluster ci is not chosen
for the combination in the current hierarchy.
5

Fig. 2. The modeled bipartite graph G = {Vx , Vy , E}.

Fig. 3. Clustering results indicated by the perfect matching. (a) The combination solution: {c1 }, {c2 , c3 }, {c3 , c4 }, {c4 , c2 }, {c5 , c6 }. (b)
The combination solution: {c1 , c2 }, {c3 , c4 }, {c5 , c6 }. (c) The combination solution: {c1 }, {c2 }, {c3 }, {c4 }, {c5 }, {c6 }.

The above-mentioned Eq.(1) aims to find the optimal combination which achieves the minimum sum of
the dissimilarity in the clustering. In our work, the optimization is achieved by solving the minimum-cost
perfect matching in a bipartite graph G.
Denote the capacity of a perfect matching as CostP M , which determines the sum cost of the combination and is calculated as
CostP M =

X

PM (ci , cj ) , ei,j : ci ↔ cj

(8)

ei,j ∈Φ

where Φ is the set of edges in the obtained perfect matching. PM(ci , cj ) aims to calculate the cost of
merging clusters that are connected in the obtained matching. Our goal is to find the minimal CostP M for
the optimal combination in the hierarchical clustering. PM(ci , cj ) is obtained from the above-calculated
proximity matrix. It is worth noting that PM(ci , ci ) is weighted by a user-defined cutoff distance SM
rather than 0. Details of our optimal hierarchical clustering (OHC) via the minimum-cost perfect matching
are shown in Algorithm 1.
In Algorithm 1, steps 1-3 aim to model a bipartite graph G = {Vx , Vy , E}. Edges in the initialization
are in a full connection, i.e. each ci ∈ Vx is connected with all other cj ∈ Vy . The step 4 is to calculate
the dissimilarity between every two clusters to form the proximity matrix. The step 5 aims to solve the
optimization of Eq.(8). The step 6 is to combine those connected clusters in the obtained perfect matching
into one cluster. The step 7 is to update Vx based on the achieved optimal combination solution to move
up the hierarchy.
In the task of the individual object segmentation, spatially non-adjacent clusters are not expected
to be combined, thus, connections are only between two adjacent clusters. The following is a toy example of the segmentation based on the proposed Algorithm 1. As shown in Fig.4(a), the input P is
{p1 , p2 , p3 , p4 , p5 , p6 }. Step 1: initialize the node set Vx as {c1 , c2 , c3 , c4 , c5 , c6 }, where c1 = {p1 }, c2 =
{p2 }, c3 = {p3 }, c4 = {p4 }, c5 = {p5 } and c6 = {p6 }; Step 2: form the node set Vy the same as Vy ; Step
3: connect spatially adjacent clusters between Vx and Vy to form the edge set E as shown in Fig.2(b);
Step 4: calculate the proximity matrix PM as

6

Algorithm 1 Method of the proposed OHC via the minimum-cost Perfect Matching
Input: The point cloud set: P = {p1 , p2 , p3 , ..., pn }.
Output: The cluster set C = {ci , c2 , ..., ct }.
Step 1: Initialize Vx = {c1 , c2 , ..., cn } by setting c1 = {p1 }, c2 = {p2 }, ..., cn = {pn };
Repeat
Step 2: Let Vy = Vx ;
Step 3: Connect the cluster ci ∈ Vx with cj ∈ Vy to form the edge ei,j , where 1 ≤ i, j ≤ n;
Step 4: Compute the proximity matrix PM using Eq.(6);
Step 5: Optimize Eq.(8) by solving the minimum-cost perfect matching of G = {Vx , Vy , E} using the
Kuhn-Munkres algorithm [19];
Step 6: Combine every connected clusters in Φ into one cluster;
Step 7: Update Vx using those combined clusters from Step 6;
Until Vx converges;
return C = Vx .

SM
D({c1 , c2 }) D({c1 , c3 ) D({c1 , c4 }) D({c1 , c5 })
SM
.
.
.
 D({c2 , c1 })

.
SM
.
.
D({{c3 , c1 })
PM = 
.
.
SM.
.
 D({c4 , c1 })
 D({c , c })
.
.
.
SM
5 1
D({c6 , c1 }) D({c6 , c2 }) D({c6 , c3 }) D({c6 , c4 }) D({c6 , c5 })



D({c1 , c6 })
D({c2 , c6 })

D({c3 , c6 })

D({c4 , c6 })
D({c5 , c6 })
SM
6×6

Step 5: solve the minimum-cost perfect matching of G as shown in Fig.4(c). Edges in the obtained perfect
matching is Φ = {e1,2 , e2,1 , e3,3 , e4,4 , e5,6 , e6,5 }; Step 6: combine clusters c1 ∈ Vx and c2 ∈ Vy into c1 , and
c5 ∈ Vx and c6 ∈ Vy into c4 . The cluster c3 and c4 are unchanged and renamed as c2 and c3 , respectively.
Step 7: update Vx as {c1 , c2 , c3 , c4 }; Now the first iteration is done. Repeat Step 2-7 and finally Vx
converges to {c1 , c2 , c3 } as shown in Fig.4(i); Step 8: return Vx as the clustering C. The dendrogram of
the above hierarchical clustering is shown in Fig.5
IV. E XPERIMENTAL RESULTS
A. Evaluation methods
Suppose that the cluster result is C = {c1 , c2 , ..., ci , ..., ct } and ground truth is C 0 = {c01 , c02 , ..., c0j , ..., c0t0 }.
Each ci or c0j means a cluster of points and there are t clusters in C and t0 clusters in C 0 . For the purpose
of evaluating our segmentation results, we define the completeness ncom and correctness ncor as Eq.(9).
T
t0
t
max |ci c0j |
X
1
j=1
ncom =
(
)
t i=1
|ci |
T
t
t0
|c0j ci |
1 X max
ncor = 0
( i=1 0
)
t j=1
|cj |

(9)

There are two steps in the calculation of ncom . The first step is to achieve the maximum of |ci ∩ c0j |/|ci |
where i is a constant and j is from 1 to t0 . This is the completeness of each cluster in C. The second
step is to obtain the mean of values from the first step. Similar steps are used to calculate ncor . The
completeness ncom is to measure the ratio between the correctly grouped points and the total points in
7

Fig. 4. A toy example of the proposed OHC algorithm. (a) The initial clusters. (b) The modeled bipartite graph based on (a). (c) The
minimum-cost perfect matching of (b). (d) Clusters after the combination based on (c). (e) The modeled bipartite graph based on (d). (f)
The minimum-cost perfect matching of (e). (g) Clusters after the combination based on (f). (h) The modeled bipartite graph based on (g).
(i) The minimum-cost perfect matching of (h).

Fig. 5. The dendrogram of the example clustering.

the result. The correctness ncor is to measure the ratio between the correctly grouped points and the total
points in the ground truth. Both the completeness and correctness range from 0 to 1.
Our completeness and correctness are similar to the purity index [20] which is an evaluation measure
by calculating the similar between two clusters. The difference is that we focus on the ratio of correctly
grouped points and total points which is a commonly used criterion in the segmentation evaluation as
shown in [21] [22] [23]. The problem of Eq.(9) is that if there is only one cluster in the ground truth
C 0 , ncom will be always 1, and if there is only one cluster in the result C, ncor will be always 1. In
order to address this problem, we choose the minimum of ncom and ncor as the segmentation accuracy,
i.e. nacc = min(ncom , ncor ), to measure the difference of points between C and C 0 . To combine the
completeness and correctness, the criterion F1 -score, i.e. nF 1 = 2 × (ncor · ncom )/(ncor + ncom ), is used
to favor algorithms with a higher sensitivity and challenges those with a higher specificity [24].

8

Fig. 6. Performances of different segmentation methods. (a) HouseSet. (b) BushSet. (c) LamppostSet. (d) TreeSet. (e) PowerlinesSet. Row 1:
the segmentation ground truth of each scene. Row 2: performance of KMiPC [16]. Row 3: performance of KNNiPC [6]. Row 4: performance
of 3DNCut [5]. Row 5: performance of MinCut [7]. Row 6: performance of PEAC [17]. Row 7: performance of the proposed OHC.

B. Comparisons of methods
This section will evaluate performances of KMiPC [16], KNNiPC [6], 3DNCut [5], MinCut [7], PEAC
[17] and the proposed OHC on five typical scenes to show our superiority. The selected scenes for testing
are shown in Fig.6, including the HouseSet (2 labels): a single object, the BushesSet (3 labels): two
separated sparse objects, the LamppostSet (4 labels): two connected rigid objects, the TreesSet (3 labels):
two connected non-rigid objects and the PowerlinesSet (7 labels): a complex scene with different objects.
The first row of Fig.6 shows the segmentation ground truth of each scene. The ground truth is
obtained by manually segmenting visual independent objects. From the second row to the last row are
the performance of KMiPC, KNNiPC, 3DNCut, MinCut, PEAC and the proposed OHC, respectively. In
the visualization, we use different colors to represent distinct segments. KMiPC, KNNiPC and MinCut
are implemented by the Point Cloud Library (www.pointclouds.org/), 3DNCut is extended from the
normalized-cut method (www.cis.upenn.edu/ jshi/software/). PEAC is achieved based on the software
of Feng et al. (www.merl.com/research/?research=license-request&sw=PEAC).
KMiPC is suitable for segmenting symmetric objects and works well in the BushesSet and TreesSet.
However, it fails to split connected objects. KNNiPC relies on the density heavily and causes that an object
is clustered into different groups as shown in the TreesSet. 3DNCut tries to normalize the difference of
points’ Euclidean distances in each group. Therefore, it tends to group points evenly as shown in the
HouseSet and TreesSet. MinCut performances well in most cases when the required center point and
radius of each object are set properly. PEAC clusters points based on the plane information and it asks
for a region growing process to obtain an individual object.
The proposed OHC is not sensitive to the density of points as shown in the BushesSet. Moreover,
it does not require for presetting the number of clusters and the location of each object to achieve the
9

Fig. 7. Evaluation of different methods. (a) Accuracy nacc . (b) F1 -score nF 1 .

multi-object segmentation. The attached traffic sign in the LamppostSet is segmented successfully using
the proposed OHC. The segmentation of the overlapping region between two non-rigid objects is rather
difficult due to the rapid change of normal vectors as shown in the TreesSet. The quantitative evaluation
is shown in Fig.7. One can observe that our OHC is more accurate than other methods in most experiment
scenes.
In the implementation of OHC, there are three parameters, namely the k to select the nearest neighbor
points, λ to balance the weight of the α (pi , pj , ci , cj ) and β (pi , pj , ci , cj ), and SM for calculating the
proximity matrix. A large k or SM may cause the appearance of the under-segmentation and a small k or
SM will increase the over-segmentation rate in results. A large λ works well for segmenting connected
objects and a small λ is preferred when there are less overlapping objects. Evaluation experiments of
parameters are shown in Fig.8. In our work, λ is 4, k is 40 and SM is 0.4.
For dealing with a large-scale scene, we present a framework to increase the efficiency of OHC: 1)
remove ground points using the Cloth Simulation Filter (CSF) approach [25]; 2) down-sample the offground points into a sparse point set; 3) apply the proposed OHC on the above down-sampling data; 4)
assign those unlabeled points in the original off-ground point set with the same label as their nearest
labeled point. An example is described in Fig.9. Fig.9 (a) shows the input point clouds. Fig.9 (b) and (c)
are filtered ground and off-ground points, respectively. Fig.9 (d) is the down-sampling points of Fig.9(c).
Fig.9 (e) is the performance of OHC on the down-sampling points and Fig.9 (f) is the final results of
the input scene. Fig.10 shows the performance of the proposed OHC on a large-scale residential point
set (558 MB, 12,551,837 points) which is obtained by the RIEGL scanner. Fig.11 shows our results of a
large-scale urban point set (528 MB, 10,870,886 points) collected by the Optech scanner.

10

Fig. 8. Parameters setting. k is chosen from {15, 25, 40, 65} and SM is chosen from {0.1, 0.15, 0.25, 0.4, 0.65}. (a) λ = 1. (b) λ = 2.
(c) λ = 3. (d) λ = 4. (e) λ = 5.

11

Fig. 9. An example of segmenting a large-scale point set. (a) Input scene. (b) Ground points. (c) Off-ground points. (d) Down-sampling
data (10% points of (c)). (e) Performance of the proposed OHC on (d). (f) Segmentation results of (a).

Fig. 10. Results of a large-scale residential point set.

12

Fig. 11. Results of a large-scale urban point set.

C. Discussion of the proposed OHC
The proposed OHC algorithm works automatically in the multi-object segmentation. We do not need
to preset any parameters manually, e.g. the initial number of clusters or the location of each object.
Our performance is competitive against the state-of-the-art methods. The proposed optimal hierarchical
clustering is general in the segmentation of point clouds but can be a disadvantage in terms of speed.
The complexity of OHC relies on the Kuhn-Munkres algorithm which is O(N 3 ). The above-mentioned
experiments were done on a Windows 10 Home 64-bit, Intel Core i7-4790 3.6GHz processor with 16 GB
of RAM and computations were carried on Matlab R2017a. It took us around four hours to achieve the
segmentation of the large-scale residential point set (12,551,837 points) and the urban point set (10,870,886
points).
V. C ONCLUSIONS
This paper investigates a new optimal hierarchical clustering method (OHC) for segmenting multiple
individual objects from 3D mobile LiDAR point clouds. The combination of clusters is represented by the
matching of a graph. The optimal combination solution is obtained by solving the minimum-cost perfect
matching of a bipartite graph. The proposed algorithm succeeds to achieve the multi-object segmentation
automatically. We test our OHC on both a residential point set and an urban point set. Experiments show
that the proposed method is effective in different scenes and superior to the state-of-the-art methods in
terms of the accuracy.
Future work will focus on adding the dissimilarity measure of the intensity and color information of
points in the calculation of the proximity matrix. Besides, we will try to improve the efficiency of the
combination by using the supervoxel technique in the clustering.

13

R EFERENCES
[1] H. Wang, C. Wang, H. Luo, P. Li, Y. Chen, and J. Li, “3-d point cloud object detection based on supervoxel neighborhood with hough
forest framework,” IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, vol. 8, no. 4, pp. 1570–1581,
2015.
[2] S. Xia and R. Wang, “A fast edge extraction method for mobile lidar point clouds,” IEEE Geoscience and Remote Sensing Letters,
vol. 14, no. 8, pp. 1288–1292, 2017.
[3] L. Nan and P. Wonka, “Polyfit: Polygonal surface reconstruction from point clouds,” in Proceedings of the IEEE Conference on
Computer Vision and Pattern Recognition, 2017, pp. 2353–2361.
[4] R. Qiu, Q.-Y. Zhou, and U. Neumann, “Pipe-run extraction and reconstruction from point clouds,” in European Conference on Computer
Vision. Springer, 2014, pp. 17–30.
[5] Y. Yu, J. Li, H. Guan, C. Wang, and J. Yu, “Semiautomated extraction of street light poles from mobile lidar point-clouds,” Geoscience
and Remote Sensing, IEEE Transactions on, vol. 53, no. 3, pp. 1374–1386, 2015.
[6] B. Douillard, J. Underwood, N. Kuntz, V. Vlaskine, A. Quadros, P. Morton, and A. Frenkel, “On the segmentation of 3d lidar point
clouds,” in Robotics and Automation (ICRA), 2011 IEEE International Conference on. IEEE, 2011, pp. 2798–2805.
[7] A. Golovinskiy, V. G. Kim, and T. Funkhouser, “Shape-based recognition of 3d point clouds in urban environments,” in Computer
Vision, 2009 IEEE 12th International Conference on. IEEE, 2009, pp. 2154–2161.
[8] K. Klasing, D. Wollherr, and M. Buss, “A clustering method for efficient segmentation of 3d laser data.” in ICRA, 2008, pp. 4043–4048.
[9] J. Shi and J. Malik, “Normalized cuts and image segmentation,” Pattern Analysis and Machine Intelligence, IEEE Transactions on,
vol. 22, no. 8, pp. 888–905, 2000.
[10] Y. Boykov and G. Funka-Lea, “Graph cuts and efficient nd image segmentation,” International journal of computer vision, vol. 70,
no. 2, pp. 109–131, 2006.
[11] J. Han, J. Pei, and M. Kamber, Data mining: concepts and techniques. Elsevier, 2011.
[12] M. Du, S. Ding, and H. Jia, “Study on density peaks clustering based on k-nearest neighbors and principal component analysis,”
Knowledge-Based Systems, vol. 99, pp. 135–145, 2016.
[13] J. Xie, H. Gao, W. Xie, X. Liu, and P. W. Grant, “Robust clustering by detecting density peaks and assigning points based on fuzzy
weighted k-nearest neighbors,” Information Sciences, vol. 354, pp. 19–40, 2016.
[14] Z. Yanchang and S. Junde, “Gdilc: a grid-based density-isoline clustering algorithm,” in Info-tech and Info-net, 2001. Proceedings.
ICII 2001-Beijing. 2001 International Conferences on, vol. 3. IEEE, 2001, pp. 140–145.
[15] G. Lavoué, F. Dupont, and A. Baskurt, “A new cad mesh segmentation method, based on curvature tensor analysis,” Computer-Aided
Design, vol. 37, no. 10, pp. 975–987, 2005.
[16] R. A. Kuçak, E. Özdemir, and S. Erol, “The segmentation of point clouds with k-means and ann (artifical neural network),” ISPRS
- International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, vol. XLII-1/W1, pp. 595–598,
2017. [Online]. Available: http://www.int-arch-photogramm-remote-sens-spatial-inf-sci.net/XLII-1-W1/595/2017/
[17] C. Feng, Y. Taguchi, and V. R. Kamat, “Fast plane extraction in organized point clouds using agglomerative hierarchical clustering,”
in Robotics and Automation (ICRA), 2014 IEEE International Conference on. IEEE, 2014, pp. 6218–6225.
[18] R. B. Rusu, “Semantic 3d object maps for everyday manipulation in human living environments,” KI-Künstliche Intelligenz, vol. 24,
no. 4, pp. 345–348, 2010.
[19] J. Munkres, “Algorithms for the assignment and transportation problems,” Journal of the Society for Industrial and Applied Mathematics,
vol. 5, no. 1, pp. 32–38, 1957.
[20] D. Manning, “Introduction,” in Introduction to Industrial Minerals. Springer, 1995, pp. 1–16.
[21] B. Yang, L. Fang, and J. Li, “Semi-automated extraction and delineation of 3d roads of street scene from mobile laser scanning point
clouds,” ISPRS Journal of Photogrammetry and Remote Sensing, vol. 79, pp. 80–93, 2013.
[22] A. Boyko and T. Funkhouser, “Extracting roads from dense point clouds in large scale urban environment,” ISPRS Journal of
Photogrammetry and Remote Sensing, vol. 66, no. 6, pp. S2–S12, 2011.
[23] P. Kumar, C. P. McElhinney, P. Lewis, and T. McCarthy, “An automated algorithm for extracting road edges from terrestrial mobile
lidar data,” ISPRS Journal of Photogrammetry and Remote Sensing, vol. 85, pp. 44–55, 2013.
[24] C. Goutte and E. Gaussier, “A probabilistic interpretation of precision, recall and f-score, with implication for evaluation,” in Advances
in information retrieval. Springer, 2005, pp. 345–359.
[25] W. Zhang, J. Qi, P. Wan, H. Wang, D. Xie, X. Wang, and G. Yan, “An easy-to-use airborne lidar data filtering method based on cloth
simulation,” Remote Sensing, vol. 8, no. 6, p. 501, 2016.

14

