# Use of GMM and SCMS for Accurate Road Centerline Extraction from the Classified Image

Authors: Zelang Miao; Bin Wang; Wenzhong Shi; Hao Wu; Yiliang Wan
Journal: Journal of Sensors
 (2015)

---

## Abstract

The extraction of road centerline from the classified image is a fundamental image analysis technology. Common problems encountered in road centerline extraction include low ability for coping with the general case, production of undesired objects, and inefficiency. To tackle these limitations, this paper presents a novel accurate centerline extraction method using Gaussian mixture model (GMM) and subspace constraint mean shift (SCMS). The proposed method consists of three main steps. GMM is first used to partition the classified image into several clusters. The major axis of the ellipsoid of each cluster is extracted and deemed to be taken as the initial centerline. Finally, the initial result is adjusted using SCMS to produce precise road centerline. Both simulated and real datasets are used to validate the proposed method. Preliminary results demonstrate that the proposed method provides a comparatively robust solution for accurate centerline extraction from a classified image.


---

## Body

## 1. Introduction

Very High Resolution (VHR) satellite images have become increasingly available in recent year with the advent of modern sensors, such as QuickBird, Pleiades, and WorldView. Road centerline delineation from these images has a variety of real applications (e.g., change detection, Geographic Information System (GIS) database updating, image registration, etc.). Massive approaches have been developed over the past decades to address the road extraction issue. Mena [1] and Das et al. [2] have presented good reviews of road extraction methods. Generally speaking, road centerline extraction commonly consists of two main steps: (
1
) road areas extraction and (
2
) centerline extraction from the road areas.The first step focuses on the extraction of road areas from the satellite images. In this field, most commonly used methods rely on the classification technology. The most traditional classification methods are pixelwise [3] that rely on spectral information only. Such pixelwise methods always meet the “salt-and-pepper” phenomenon [4] and there is large room to improve classification accuracy. In recent years, with the development of VHR satellite images, road geometrical features are derived and explored to integrate with spectral information to meet the challenge of the “salt-and-pepper” phenomenon. To do so, a variety of road shape features are integrated with spectral information to improve road extraction accuracy, including smoothness, compactness [5], shape index [6, 7], second order moment [2, 8], and mathematical morphology [9, 10]. To improve the classification, numerous algorithms have been proposed, such as sparse representation and low-rank constraint [11] and band subset-based clustering and fusion method [12]. Except the classification methods, there are also some other road areas extraction methods, including the segmentation method [13–16], active contour (i.e., “snake” model) [17, 18], and level set [19, 20].The second step involves centerline extraction from road areas extracted in the first step. The commonly used method is the thinning algorithm [21]. Despite its computational efficiency, the result of the thinning algorithm always produces undesired objects (i.e., spurs) that reduce the smoothness and accuracy of the centerline. To tackle this limitation to some extent, a self-organized clustering method [22] was designed. This method firstly extracted initial points using K-medians clustering, followed by the linking algorithm to create the central line. Radon and Hough transform [23, 24] were also introduced to extract the centerline from the classified image. Strong peak locations in the transform matrix are taken to be straight line pixels in the original image. Radon and Hough transform are suitable for straight line extraction and generally fail to process curvilinear cases. Recently, in the area of computer vision, a so-called subspace constrained mean shift (SCMS) method [25–27] was proposed to extract accurate centerline from point clouds. First, the probability that a pixel is located on the centerline is computed using the kernel density estimation (KDE). Then, all discrete points are iteratively projected onto the centerline based on mean shift. Despite its good performance, when the number of points is large, SCMS becomes very slow, which limits its real applications. To improve the computational efficiency of SCMS, feature points-based SCMS (F-SCMS) [28] was proposed. F-SCMS firstly detected feature points (i.e., end and junction points) from the classified image, followed by the connection of feature points by the geodesic method to create the central lines to formulate the road network. Although F-SCMS can largely improve the speed of SCMS, it cannot process the classified image with closed form, such as circle. The aforementioned discussions indicate that the extraction of accurate road centerline from the classified image is not well resolved and this topic is still open and challenging.There are also many other interesting studies on road extraction from a different viewpoint, such as Kalman filtering [29], road footprint [30], and dynamic programming [31]. Although most of the aforementioned studies focus on multispectral satellite images, other sources of information can also be used to extract road networks, such as Synthetic Aperture Radar (SAR) [18, 32, 33], LiDAR [34–36], and hyperspectral images [6, 37, 38]. This paper focuses on the accurate road centerline extraction from the classified image. It is worthy to point out that this focus will not weaken the proposed method, which is also suitable for centerline extraction from road areas extracted from other sources.The main objectives of this paper are as follows:(i)
improving the efficiency of SCMS;
(ii)
proposing a method for accurate road centerline extraction from the classified image with high generalization ability.The remainder of this paper is organized as follows. The new approach is presented in Section2. The experimental results are given and discussed in Section 3. Finally, Section 4 concludes the paper.


## 2. Methodology

The objective of this study is to devise a computationally efficient approach with high general ability to extract accurate centerlines from classified images. Figure1 summarizes the proposed method.Figure 1
Flowchart of the proposed method.The proposed method consists of the three following steps.(1)
The classified image is partitioned using the Gaussian mixture model (GMM) method.
(2)
The major axis is subsequently extracted from the ellipsoid of each Gaussian.
(3)
The major axis is adjusted based on SCMS to produce accurate road centerline.In the following subsections, details of each step are described.


### 2.1. Image Partition Using GMM

Road pixels in the classified map can be represented as 2D discrete joint random variables. We can partition the classified image into multiple segments by taking road pixels as observations. To do so, the Gaussian mixture model (GMM) is used to implement image clustering. The reason of selecting GMM is that the Gaussian models used by the expectation-maximization (EM) algorithm are flexible and the EM result is able to accommodate clusters of variable size. This is because EM benefits from the Gaussian distribution present in the dataset. Therefore, GMM is able to capture the complex spatial structure. In other words, GMM is able to simplify the classified road map as well as retain its spatial topology. The concepts of GMM are briefly introduced as follows.GMM can be written as a linear superposition ofK Gaussians that leads to a probability density in the form(1)
s
K
,
ν
,
Σ
,
w
x
=
∑
k
=
1
K
π
k
Φ
ν
k
,
Σ
k
x
,where π
k
k
=
1
K are mixture weights subject to 0
≤
π
k
≤
1, ∑
k
=
1
K
π
k
=
1, and Φ
· is a multivariate Gaussian probability distribution of mean ν
k and covariance matrix Σ
k. Consider (2)
Φ
ν
,
Σ
x
=
1
2
π
Σ
e
-
1
/
2
x
-
ν
T
Σ
-
1
x
-
ν
.The expected value of the indicator variables under the posterior distribution is then given by(3)
γ
z
i
j
=
π
j
Φ
ν
j
,
Σ
j
x
i
∑
k
=
1
K
π
k
Φ
ν
k
,
Σ
k
x
i
.The log-likelihood function is defined as(4)
ln
⁡
p
x
,
z
∣
Φ
=
∑
i
=
1
N
∑
k
=
1
K
γ
z
i
j
ln
⁡
π
k
Φ
ν
k
,
Σ
k
x
i
.The parameters of each component are updated using the expectation-maximization (EM) algorithm as follows:(5)
π
k
=
1
N
∑
i
=
1
N
γ
z
i
j
,
μ
j
=
1
∑
i
=
1
N
γ
z
i
j
∑
i
=
1
N
γ
z
i
j
x
i
,
Σ
j
=
1
∑
i
=
1
N
γ
z
i
j
∑
i
=
1
N
γ
z
i
j
x
i
-
μ
j
x
i
-
μ
j
T
.The EM step is iteratively repeated until convergence. It is worthy of pointing out that initial estimates for the parameters (Φ
·) are necessary for the first EM iteration. To this end, the k-Means algorithm is selected to initialize such parameters involving running. The spatial cluster number for k-Means is estimated by(6)
K
=
A
R
W
×
M
L
,where · means to round the number to the nearest integer greater than or equal to this number, A is the area of the classified image, R
W is the average road width of the classified image, and M
L is the minimum area of a spatial cluster.Details of the image partition using GMM are illustrated in Algorithm1. Figure 2 gives a conceptual example. Figure 2(a) is the classified image and its corresponding spatial partition result using GMM is shown in Figure 2(b).Algorithm 1:Image partition using GMM.
Input: The classified image.
Output: The mean μ and covariance matrix Σ.
(1)  Compute the spatial cluster number K using (6).
(2)  Initial the parameters of EM using k-Means.
(3)  Run the EM algorithm to segment the classified image until convergence.
(4)
for  i
=
1
,
…
,
K  do
(5)   compute the mean μ
i and covariance matrix Σ
i of ith Gaussian.
(6)
end forFigure 2
(a) The classified road map. (b) The spatial partition result using GMM.
(a)
(b)


### 2.2. Extraction of Initial Road Centerlines

After the spatial partition using GMM in Section2.1, the mean μ and covariance matrix Σ for each mixture are produced. The ellipsoids of each Gaussian can be defined using μ and Σ. In this study, the major axis of each ellipsoid is taken as the approximate initial centerline. Σ is a square matrix that can be factorized as(7)
Σ
=
U
Λ
U
T
,where U is the eigenvector matrix and Λ is the diagonal matrix whose diagonal elements are the corresponding eigenvalues. The inverse matrix of Σ is given by(8)
Σ
-
1
=
U
-
T
Λ
-
1
U
-
1
=
U
Λ
-
1
U
=
∑
i
=
1
p
1
λ
i
u
→
i
u
→
i
T
.The inverse matrixΣ
-
1 can be rewritten as(9)
x
→
-
u
→
T
Σ
-
1
x
→
-
u
→
=
x
→
-
u
→
T
∑
i
=
1
p
1
λ
i
u
→
i
u
→
i
T
x
→
-
u
→
=
∑
i
=
1
p
1
λ
i
x
→
-
u
→
T
u
→
i
u
→
i
T
x
→
-
u
→
=
∑
i
=
1
p
y
i
2
λ
i
,where y
i
≜
u
→
i
T
x
→
-
u
→. The y variables define a new coordinate system that is shifted (by u
→) and rotated (by U) with respect to the original x coordinates: y
→
=
U
x
→
-
u
→. Recall that the equation for an ellipse in 2D is(10)
y
1
2
λ
1
+
y
2
2
λ
2
=
1
.Equation (10) indicates that the contours of equal probability density of a Gaussian lie along ellipse. Figure 3 demonstrates an example of the ellipsoid generated by the mean and covariance matrix.Figure 3
An example of the ellipsoid derived by the mean and covariance matrix.For each Gaussian mixture, the major axis of the ellipse is estimated. After that, all major axis will compose of a coarse road centerline network that has a similar spatial topology with the true one, as shown in Figure4.Figure 4
(a) Ellipse of each Gaussian. (b) The major axis which is shown in red.
(a)
(b)


### 2.3. Adjustment of Initial Road Centerline Using SCMS

The major axis produced by GMM in Section2.2 can be regarded as the initial road centerline that is commonly coarse. For the purpose of accurate road centerline result, it is promising to obtain accurate road centerline using the adjustment techniques. To this end, subspace constrained mean shift (SCMS) is selected to align the major axis. However, SCMS is iteratively implemented on the whole classified road pixels, which leads to high computational load. On the other hand, the major axis can also be taken as the simplification case of the classified road map that only accounts for small size pixels. In other words, GMM finds the representative points of the classified road pixels to be used in principal curve projection; and therefore, GMM followed by SCMS, termed as GMM-SCMS, provides a new means to lower the computational load. The SCMS method is briefly introduced as follows.Considering ad-variate random sample X
1
,
X
2
,
…
,
X
n drawn from a population with its density function f, the kernel density estimator (KDE) is defined as(11)
f
^
x
;
Σ
=
n
-
1
∑
i
=
1
n
K
Σ
x
-
X
i
,where x
=
x
1
,
x
2
,
…
,
x
d
T and X
i
=
X
i
1
,
X
i
2
,
…
,
X
i
d
T, i
=
1,2
,
…
,
n. In addition, the symmetric positive definite d
×
d matrix Σ is the bandwidth matrix, which critically determines the performance of the KDE function f
^. K is a d-variate kernel function defined as(12)
K
Σ
x
=
Σ
-
1
/
2
K
Σ
-
1
/
2
xwhich satisfies ∫
K
x
d
x
=
1. Here, · indicates the determinant operation, and the common choice of Gaussian KDE functions is adopted; K
x
=
2
π
-
d
/
2
exp
⁡
(
-
1
/
2
x
T
x
).By generalizing Scott’s rule of thumb, bandwidth matrixΣ
-
1
=
n
2
/
(
d
+
4
)
Σ
^
-
1 is chosen here (see Ahamada and Flachaire [39] for details). Consequently, the kernel density estimator is constructed above as (13)
p
x
;
Σ
=
1
n
2
π
d
/
2
Σ
1
/
2
∑
i
=
1
n
e
x
p
-
1
2
x
-
X
i
T
Σ
-
1
x
-
X
i
.In consideration of the numerical stability when solving the principle curve, the logarithm of the density functionp
x
;
Σ is involved: (14)
f
p
x
=
log
⁡
p
x
.The corresponding gradient and Hessian matrices for KDE are(15)
g
f
x
=
f
′
p
x
∇
p
x
T
=
p
x
-
1
g
x
,
H
f
x
=
f
′
′
p
x
∇
p
x
T
∇
p
x
f
′
p
x
∇
2
p
x
=
f
′
′
p
x
g
x
g
x
T
+
f
′
p
x
H
x
=
-
p
x
-
2
g
x
g
x
T
p
x
-
1
H
x
.Thus, we get the fixed-point update rule for adjusting the coarse initial point:(16)
m
Σ
x
=
∑
i
=
1
n
exp
⁡
-
1
/
2
x
-
X
i
T
Σ
-
1
x
-
X
i
X
i
∑
i
=
1
n
exp
⁡
-
1
/
2
x
-
X
i
T
Σ
-
1
x
-
X
i
-
x
.On account of the similarity of the above iteration formula to the mean-shift algorithm, thus it has the name of subspace constrained mean shift (SCMS) method, which is presented in Algorithm2. An example of adjusting coarse points to produce accurate centerline utilizing SCMS is illustrated in Figure 5.Algorithm 2:Subspace constrained mean shift.
Input: The coarse road centerline derived from the major axis X
1
,
X
2
,
…
,
X
n
Output: The adjusted discrete points X
1
new
,
X
2
new
,
…
,
X
n
new
(1)  Provide the band width matrix Σ
-
1
=
n
2
/
(
d
+
4
)
Σ
^
-
1 (i.e., the kernel covariance).
(2)
for  i
=
1
,
…
,
K  do
(3)
P
=
I
-
q
q
T and s
=
P
m
Σ
(
x
)
(4)
while  s
<
e
t
h
r
e  do
(5)
X
i
t
+
1
=
X
i
t
+
s
(6)
end while
(7)
X
i
new
=
X
i
t
+
1
+
s
(8)
end forFigure 5
An example of a principal curve. (a) Noisy input points. (b) The estimated probability density map. (c) The principal curve over the probability density map where the principal curve is shown in green. (d) The principal curve projected back onto the plane of original points.
(a)
(b)
(c)
(d)


## 2.1. Image Partition Using GMM

Road pixels in the classified map can be represented as 2D discrete joint random variables. We can partition the classified image into multiple segments by taking road pixels as observations. To do so, the Gaussian mixture model (GMM) is used to implement image clustering. The reason of selecting GMM is that the Gaussian models used by the expectation-maximization (EM) algorithm are flexible and the EM result is able to accommodate clusters of variable size. This is because EM benefits from the Gaussian distribution present in the dataset. Therefore, GMM is able to capture the complex spatial structure. In other words, GMM is able to simplify the classified road map as well as retain its spatial topology. The concepts of GMM are briefly introduced as follows.GMM can be written as a linear superposition ofK Gaussians that leads to a probability density in the form(1)
s
K
,
ν
,
Σ
,
w
x
=
∑
k
=
1
K
π
k
Φ
ν
k
,
Σ
k
x
,where π
k
k
=
1
K are mixture weights subject to 0
≤
π
k
≤
1, ∑
k
=
1
K
π
k
=
1, and Φ
· is a multivariate Gaussian probability distribution of mean ν
k and covariance matrix Σ
k. Consider (2)
Φ
ν
,
Σ
x
=
1
2
π
Σ
e
-
1
/
2
x
-
ν
T
Σ
-
1
x
-
ν
.The expected value of the indicator variables under the posterior distribution is then given by(3)
γ
z
i
j
=
π
j
Φ
ν
j
,
Σ
j
x
i
∑
k
=
1
K
π
k
Φ
ν
k
,
Σ
k
x
i
.The log-likelihood function is defined as(4)
ln
⁡
p
x
,
z
∣
Φ
=
∑
i
=
1
N
∑
k
=
1
K
γ
z
i
j
ln
⁡
π
k
Φ
ν
k
,
Σ
k
x
i
.The parameters of each component are updated using the expectation-maximization (EM) algorithm as follows:(5)
π
k
=
1
N
∑
i
=
1
N
γ
z
i
j
,
μ
j
=
1
∑
i
=
1
N
γ
z
i
j
∑
i
=
1
N
γ
z
i
j
x
i
,
Σ
j
=
1
∑
i
=
1
N
γ
z
i
j
∑
i
=
1
N
γ
z
i
j
x
i
-
μ
j
x
i
-
μ
j
T
.The EM step is iteratively repeated until convergence. It is worthy of pointing out that initial estimates for the parameters (Φ
·) are necessary for the first EM iteration. To this end, the k-Means algorithm is selected to initialize such parameters involving running. The spatial cluster number for k-Means is estimated by(6)
K
=
A
R
W
×
M
L
,where · means to round the number to the nearest integer greater than or equal to this number, A is the area of the classified image, R
W is the average road width of the classified image, and M
L is the minimum area of a spatial cluster.Details of the image partition using GMM are illustrated in Algorithm1. Figure 2 gives a conceptual example. Figure 2(a) is the classified image and its corresponding spatial partition result using GMM is shown in Figure 2(b).Algorithm 1:Image partition using GMM.
Input: The classified image.
Output: The mean μ and covariance matrix Σ.
(1)  Compute the spatial cluster number K using (6).
(2)  Initial the parameters of EM using k-Means.
(3)  Run the EM algorithm to segment the classified image until convergence.
(4)
for  i
=
1
,
…
,
K  do
(5)   compute the mean μ
i and covariance matrix Σ
i of ith Gaussian.
(6)
end forFigure 2
(a) The classified road map. (b) The spatial partition result using GMM.
(a)
(b)


## 2.2. Extraction of Initial Road Centerlines

After the spatial partition using GMM in Section2.1, the mean μ and covariance matrix Σ for each mixture are produced. The ellipsoids of each Gaussian can be defined using μ and Σ. In this study, the major axis of each ellipsoid is taken as the approximate initial centerline. Σ is a square matrix that can be factorized as(7)
Σ
=
U
Λ
U
T
,where U is the eigenvector matrix and Λ is the diagonal matrix whose diagonal elements are the corresponding eigenvalues. The inverse matrix of Σ is given by(8)
Σ
-
1
=
U
-
T
Λ
-
1
U
-
1
=
U
Λ
-
1
U
=
∑
i
=
1
p
1
λ
i
u
→
i
u
→
i
T
.The inverse matrixΣ
-
1 can be rewritten as(9)
x
→
-
u
→
T
Σ
-
1
x
→
-
u
→
=
x
→
-
u
→
T
∑
i
=
1
p
1
λ
i
u
→
i
u
→
i
T
x
→
-
u
→
=
∑
i
=
1
p
1
λ
i
x
→
-
u
→
T
u
→
i
u
→
i
T
x
→
-
u
→
=
∑
i
=
1
p
y
i
2
λ
i
,where y
i
≜
u
→
i
T
x
→
-
u
→. The y variables define a new coordinate system that is shifted (by u
→) and rotated (by U) with respect to the original x coordinates: y
→
=
U
x
→
-
u
→. Recall that the equation for an ellipse in 2D is(10)
y
1
2
λ
1
+
y
2
2
λ
2
=
1
.Equation (10) indicates that the contours of equal probability density of a Gaussian lie along ellipse. Figure 3 demonstrates an example of the ellipsoid generated by the mean and covariance matrix.Figure 3
An example of the ellipsoid derived by the mean and covariance matrix.For each Gaussian mixture, the major axis of the ellipse is estimated. After that, all major axis will compose of a coarse road centerline network that has a similar spatial topology with the true one, as shown in Figure4.Figure 4
(a) Ellipse of each Gaussian. (b) The major axis which is shown in red.
(a)
(b)


## 2.3. Adjustment of Initial Road Centerline Using SCMS

The major axis produced by GMM in Section2.2 can be regarded as the initial road centerline that is commonly coarse. For the purpose of accurate road centerline result, it is promising to obtain accurate road centerline using the adjustment techniques. To this end, subspace constrained mean shift (SCMS) is selected to align the major axis. However, SCMS is iteratively implemented on the whole classified road pixels, which leads to high computational load. On the other hand, the major axis can also be taken as the simplification case of the classified road map that only accounts for small size pixels. In other words, GMM finds the representative points of the classified road pixels to be used in principal curve projection; and therefore, GMM followed by SCMS, termed as GMM-SCMS, provides a new means to lower the computational load. The SCMS method is briefly introduced as follows.Considering ad-variate random sample X
1
,
X
2
,
…
,
X
n drawn from a population with its density function f, the kernel density estimator (KDE) is defined as(11)
f
^
x
;
Σ
=
n
-
1
∑
i
=
1
n
K
Σ
x
-
X
i
,where x
=
x
1
,
x
2
,
…
,
x
d
T and X
i
=
X
i
1
,
X
i
2
,
…
,
X
i
d
T, i
=
1,2
,
…
,
n. In addition, the symmetric positive definite d
×
d matrix Σ is the bandwidth matrix, which critically determines the performance of the KDE function f
^. K is a d-variate kernel function defined as(12)
K
Σ
x
=
Σ
-
1
/
2
K
Σ
-
1
/
2
xwhich satisfies ∫
K
x
d
x
=
1. Here, · indicates the determinant operation, and the common choice of Gaussian KDE functions is adopted; K
x
=
2
π
-
d
/
2
exp
⁡
(
-
1
/
2
x
T
x
).By generalizing Scott’s rule of thumb, bandwidth matrixΣ
-
1
=
n
2
/
(
d
+
4
)
Σ
^
-
1 is chosen here (see Ahamada and Flachaire [39] for details). Consequently, the kernel density estimator is constructed above as (13)
p
x
;
Σ
=
1
n
2
π
d
/
2
Σ
1
/
2
∑
i
=
1
n
e
x
p
-
1
2
x
-
X
i
T
Σ
-
1
x
-
X
i
.In consideration of the numerical stability when solving the principle curve, the logarithm of the density functionp
x
;
Σ is involved: (14)
f
p
x
=
log
⁡
p
x
.The corresponding gradient and Hessian matrices for KDE are(15)
g
f
x
=
f
′
p
x
∇
p
x
T
=
p
x
-
1
g
x
,
H
f
x
=
f
′
′
p
x
∇
p
x
T
∇
p
x
f
′
p
x
∇
2
p
x
=
f
′
′
p
x
g
x
g
x
T
+
f
′
p
x
H
x
=
-
p
x
-
2
g
x
g
x
T
p
x
-
1
H
x
.Thus, we get the fixed-point update rule for adjusting the coarse initial point:(16)
m
Σ
x
=
∑
i
=
1
n
exp
⁡
-
1
/
2
x
-
X
i
T
Σ
-
1
x
-
X
i
X
i
∑
i
=
1
n
exp
⁡
-
1
/
2
x
-
X
i
T
Σ
-
1
x
-
X
i
-
x
.On account of the similarity of the above iteration formula to the mean-shift algorithm, thus it has the name of subspace constrained mean shift (SCMS) method, which is presented in Algorithm2. An example of adjusting coarse points to produce accurate centerline utilizing SCMS is illustrated in Figure 5.Algorithm 2:Subspace constrained mean shift.
Input: The coarse road centerline derived from the major axis X
1
,
X
2
,
…
,
X
n
Output: The adjusted discrete points X
1
new
,
X
2
new
,
…
,
X
n
new
(1)  Provide the band width matrix Σ
-
1
=
n
2
/
(
d
+
4
)
Σ
^
-
1 (i.e., the kernel covariance).
(2)
for  i
=
1
,
…
,
K  do
(3)
P
=
I
-
q
q
T and s
=
P
m
Σ
(
x
)
(4)
while  s
<
e
t
h
r
e  do
(5)
X
i
t
+
1
=
X
i
t
+
s
(6)
end while
(7)
X
i
new
=
X
i
t
+
1
+
s
(8)
end forFigure 5
An example of a principal curve. (a) Noisy input points. (b) The estimated probability density map. (c) The principal curve over the probability density map where the principal curve is shown in green. (d) The principal curve projected back onto the plane of original points.
(a)
(b)
(c)
(d)


## 3. Experiment

In this section, several experiments that test the proposed method are described. The proposed method is also compared with other methods in the literature to show the advantages and disadvantages of the proposed method. In this study, MATLAB was used as the coding environment on a PC that has an Intel Core2Quad processor with 2.83 GHz clock speed.


### 3.1. Tests of Parameters

To test the minimum areaM
L influence on the road centerline extraction accuracy, we adjusted its value automatically from 5 to 30 with an increment of 5 for each step. The test results are presented in Figure 6. The performance of the M
L influence is quantitatively evaluated in terms of the computational time and accuracy. Here, three accuracy measures, (
1
) Completeness, (
2
) Correctness, and (
3
) Quality [40], were used.(17)
C
o
m
p
l
e
t
e
n
e
s
s
=
T
P
T
P
+
F
N
,
C
o
r
r
e
c
t
n
e
s
s
=
T
P
T
P
+
F
P
,
Q
u
a
l
i
t
y
=
T
P
T
P
+
F
P
+
F
N
,where TP, FN, and FP represent true positive, false negative, and false positive, respectively. In this study, the ground truth dataset is produced by hand drawing method and the buffer width is fixed to 8 pixels.Figure 6
Road centerline extraction results with different minimum area values. (a) 100. (b) 120. (c) 140. (d) 160. (e) 180. (f) 200. The road centerline extraction results are shown in red.
(a)
(b)
(c)
(d)
(e)
(f)Figure7 reports quantitative evaluation results with different minimum area values. Figure 7(a) indicates that the computational efficiency steadily improved with the increase of the minimum area value. This is because large M
L will result in initial road centerline with small number of points, which in turn reduce the computational load of the adjustment using SCMS. Figure 7(b) illustrates the influence of M
L on the accuracy. It can be seen that when M
L is increased from 100 to 180, there is a slight change of the accuracy, which indicates that M
L has a weak effect on the accuracy in this range of values. However, the accuracy declines dramatically when M
L is exceeding 180. The reason for this phenomenon is that the large M
L cannot produce the initial road centerline with the correct spatial topology as the classified image, as shown in Figure 6(f). To achieve the best balance between the computational efficiency and the accuracy, this study fixed M
L to 180 throughout the tests.Figure 7
The evaluation results of the minimum area influence. (a) Computational load. (b) Accuracy.
(a)
(b)


### 3.2. Experiments on Simulated Images

The proposed method is tested on three simulated images, including circle image, spiral image, and snow image, as shown in Figure8(a). The intermediate results using GMM are shown in Figure 8(b) and the corresponding precise centerline results using SCMS are given in Figure 8(c).Figure 8
(a) The test images. (b) The major axis of GMM partitioning result. (c) The adjustment results using SCMS.
(a)
(b)
(c)The proposed method is compared with two existing methods in literature:(
1
) SCMS and (
2
) F-SCMS. The comparison results are illustrated by Figure 9. From Figure 9, it can be seen that F-SCMS well works in spiral and snow cases but fails to process circle case. By contrast, both SCMS and GMM-SCMS are capable of extracting centerline from three test images, which indicates that SCMS and GMM-SCMS are more general than F-SCMS.Figure 9
(a), (b), and (c) show SCMS, F-SCMS, and GMM-SCMS results, respectively. The centerline extracted are shown in red.
(a)
(b)
(c)The comparison results are quantitatively evaluated in terms of computation time and three accuracy measures. Table1 reports the computational time of three methods on test images. It can be seen that F-SCMS and GMM-SCMS generally achieve higher computational efficiency than SCMS. F-SCMS is more efficient than GMM-SCMS in snow case. In spiral case, GMM-SCMS, however, is more efficient than F-SCMS. It seems that the efficiency of GMM-SCMS and F-SCMS is influenced by points number. F-SCMS is more efficient with the large points number while GMM-SCMS in small points number. The accuracy results are given in Table 2. From the practical prospective, circle and spiral cases are too easy and the snow case is more similar to the real-world issue. Therefore, the accuracy is just compared in snow case. It can be seen that F-SCMS produces the highest accuracy among these three methods and SCMS and GMM-SCMS achieve a similar accuracy.Table 1
Comparison of computation time for different centerline extraction methods.
Experiment
Number of
Computation time (s)
points
SCMS
F-SCMS
GMM-SCMS
Circle case
5953
20.38
Fail
1.76
Spiral case
18828
114.52
11.24
8.53
Snow case
11807
146.78
8.36
16.42Table 2
Quantitative evaluation of different centerline extraction methods.
Method
Circle case
Spiral case
Snow case
Completeness
Correctness
Quality
Completeness
Correctness
Quality
Completeness
Correctness
Quality
(%)
(%)
(%)
(%)
(%)
(%)
(%)
(%)
(%)
SCMS
100
100
100
84.13
85.61
73.71
81.03
90.53
74.70
F-SCMS
Fail
Fail
Fail
93.56
94.75
88.95
90.58
98.84
86.92
GMM-SCMS
100
100
100
96.94
97.74
94.82
78.77
92.36
73.96


### 3.3. Experiments on Real Satellite Images

The proposed method was tested on four multispectral satellite images used in a previous work [28]. The test images are shown in Figure 10, where the ground truth datasets are shown in red. The corresponding classified images are presented in Figure 11. The proposed GMM-SCMS method is compared with two existing methods in literature: SCMS and F-SCMS. The comparison results are reported in Figure 12. The performances of three methods are quantitatively evaluated in terms of the computational efficiency and the accuracy, as shown in Table 3 and Figure 13.Table 3
Comparison of computation time for different centerline extraction methods.
Experiment
Number of
Computation time (s)
points
SCMS
F-SCMS
GMM-SCMS
1
35177
1142.95
73.48
110.68
2
11578
58.77
2.18
6.51
3
8009
35.73
1.97
8.84
4
16503
172.99
67.93
15.36Figure 10
(a), (b), (c), and (d) show four test images, respectively. The ground truth datasets are shown in red.
(a)
(b)
(c)
(d)Figure 11
(a), (b), (c), and (d) show classified images of the test images in Figure9, respectively.
(a)
(b)
(c)
(d)Figure 12
Comparison results of different road centerline extraction methods. (a) SCMS results. (b) F-SCMS results. (c) GMM-SCMS results. The centerlines are shown in red for display.
(a)
(b)
(c)Figure 13
(a), (b), (c), and (d) show quantitative evaluation results of different centerline extraction methods for Cases1, 2, 3, and 4, respectively.
(a)
(b)
(c)
(d)From Table3, it can be seen that the computational load of SCMS is highest among these three methods. By contrast, both F-SCMS and GMM-SCMS produce higher computation efficiency than SCMS. In general, F-SCMS achieves better computational performance than GMM-SCMS, such as Cases 1–3. However, Table 3 also shows an interesting phenomenon that GMM-SCMS shows higher computational efficiency than F-SCMS [28] in Case 4. The phenomenon indicates that the number of connected components (CCs) influences the F-SCMS performance. For instance, the numbers of CCs in Cases 1–4 are 3, 1, 1, and 8, respectively. It seems that when the number of connected components is high, GMM-SCMS is more efficient than F-SCMS. The main reason is that F-SCMS detects feature points (i.e., end and junction points) and then links these points iteratively for each connected component. Detection of feature points from the classified image costs a lot of time. Therefore, high number of CCs decreases the performance of F-SCMS.Figure13 demonstrates the accuracy of three methods. As can be seen, SCMS produces the lowest accuracy while F-SCMS the highest. In general, GMM-SCMS achieves the modest accuracy among these three methods.By comparing the proposed method with two existing methods on simulated and real datasets, it can be seen that the proposed method produces the best balance between the computational complexity, accuracy, and generalization ability among these three methods. Thus, GMM-SCMS is more practical for accurate and efficient road centerline extraction from classified images.


## 3.1. Tests of Parameters

To test the minimum areaM
L influence on the road centerline extraction accuracy, we adjusted its value automatically from 5 to 30 with an increment of 5 for each step. The test results are presented in Figure 6. The performance of the M
L influence is quantitatively evaluated in terms of the computational time and accuracy. Here, three accuracy measures, (
1
) Completeness, (
2
) Correctness, and (
3
) Quality [40], were used.(17)
C
o
m
p
l
e
t
e
n
e
s
s
=
T
P
T
P
+
F
N
,
C
o
r
r
e
c
t
n
e
s
s
=
T
P
T
P
+
F
P
,
Q
u
a
l
i
t
y
=
T
P
T
P
+
F
P
+
F
N
,where TP, FN, and FP represent true positive, false negative, and false positive, respectively. In this study, the ground truth dataset is produced by hand drawing method and the buffer width is fixed to 8 pixels.Figure 6
Road centerline extraction results with different minimum area values. (a) 100. (b) 120. (c) 140. (d) 160. (e) 180. (f) 200. The road centerline extraction results are shown in red.
(a)
(b)
(c)
(d)
(e)
(f)Figure7 reports quantitative evaluation results with different minimum area values. Figure 7(a) indicates that the computational efficiency steadily improved with the increase of the minimum area value. This is because large M
L will result in initial road centerline with small number of points, which in turn reduce the computational load of the adjustment using SCMS. Figure 7(b) illustrates the influence of M
L on the accuracy. It can be seen that when M
L is increased from 100 to 180, there is a slight change of the accuracy, which indicates that M
L has a weak effect on the accuracy in this range of values. However, the accuracy declines dramatically when M
L is exceeding 180. The reason for this phenomenon is that the large M
L cannot produce the initial road centerline with the correct spatial topology as the classified image, as shown in Figure 6(f). To achieve the best balance between the computational efficiency and the accuracy, this study fixed M
L to 180 throughout the tests.Figure 7
The evaluation results of the minimum area influence. (a) Computational load. (b) Accuracy.
(a)
(b)


## 3.2. Experiments on Simulated Images

The proposed method is tested on three simulated images, including circle image, spiral image, and snow image, as shown in Figure8(a). The intermediate results using GMM are shown in Figure 8(b) and the corresponding precise centerline results using SCMS are given in Figure 8(c).Figure 8
(a) The test images. (b) The major axis of GMM partitioning result. (c) The adjustment results using SCMS.
(a)
(b)
(c)The proposed method is compared with two existing methods in literature:(
1
) SCMS and (
2
) F-SCMS. The comparison results are illustrated by Figure 9. From Figure 9, it can be seen that F-SCMS well works in spiral and snow cases but fails to process circle case. By contrast, both SCMS and GMM-SCMS are capable of extracting centerline from three test images, which indicates that SCMS and GMM-SCMS are more general than F-SCMS.Figure 9
(a), (b), and (c) show SCMS, F-SCMS, and GMM-SCMS results, respectively. The centerline extracted are shown in red.
(a)
(b)
(c)The comparison results are quantitatively evaluated in terms of computation time and three accuracy measures. Table1 reports the computational time of three methods on test images. It can be seen that F-SCMS and GMM-SCMS generally achieve higher computational efficiency than SCMS. F-SCMS is more efficient than GMM-SCMS in snow case. In spiral case, GMM-SCMS, however, is more efficient than F-SCMS. It seems that the efficiency of GMM-SCMS and F-SCMS is influenced by points number. F-SCMS is more efficient with the large points number while GMM-SCMS in small points number. The accuracy results are given in Table 2. From the practical prospective, circle and spiral cases are too easy and the snow case is more similar to the real-world issue. Therefore, the accuracy is just compared in snow case. It can be seen that F-SCMS produces the highest accuracy among these three methods and SCMS and GMM-SCMS achieve a similar accuracy.Table 1
Comparison of computation time for different centerline extraction methods.
Experiment
Number of
Computation time (s)
points
SCMS
F-SCMS
GMM-SCMS
Circle case
5953
20.38
Fail
1.76
Spiral case
18828
114.52
11.24
8.53
Snow case
11807
146.78
8.36
16.42Table 2
Quantitative evaluation of different centerline extraction methods.
Method
Circle case
Spiral case
Snow case
Completeness
Correctness
Quality
Completeness
Correctness
Quality
Completeness
Correctness
Quality
(%)
(%)
(%)
(%)
(%)
(%)
(%)
(%)
(%)
SCMS
100
100
100
84.13
85.61
73.71
81.03
90.53
74.70
F-SCMS
Fail
Fail
Fail
93.56
94.75
88.95
90.58
98.84
86.92
GMM-SCMS
100
100
100
96.94
97.74
94.82
78.77
92.36
73.96


## 3.3. Experiments on Real Satellite Images

The proposed method was tested on four multispectral satellite images used in a previous work [28]. The test images are shown in Figure 10, where the ground truth datasets are shown in red. The corresponding classified images are presented in Figure 11. The proposed GMM-SCMS method is compared with two existing methods in literature: SCMS and F-SCMS. The comparison results are reported in Figure 12. The performances of three methods are quantitatively evaluated in terms of the computational efficiency and the accuracy, as shown in Table 3 and Figure 13.Table 3
Comparison of computation time for different centerline extraction methods.
Experiment
Number of
Computation time (s)
points
SCMS
F-SCMS
GMM-SCMS
1
35177
1142.95
73.48
110.68
2
11578
58.77
2.18
6.51
3
8009
35.73
1.97
8.84
4
16503
172.99
67.93
15.36Figure 10
(a), (b), (c), and (d) show four test images, respectively. The ground truth datasets are shown in red.
(a)
(b)
(c)
(d)Figure 11
(a), (b), (c), and (d) show classified images of the test images in Figure9, respectively.
(a)
(b)
(c)
(d)Figure 12
Comparison results of different road centerline extraction methods. (a) SCMS results. (b) F-SCMS results. (c) GMM-SCMS results. The centerlines are shown in red for display.
(a)
(b)
(c)Figure 13
(a), (b), (c), and (d) show quantitative evaluation results of different centerline extraction methods for Cases1, 2, 3, and 4, respectively.
(a)
(b)
(c)
(d)From Table3, it can be seen that the computational load of SCMS is highest among these three methods. By contrast, both F-SCMS and GMM-SCMS produce higher computation efficiency than SCMS. In general, F-SCMS achieves better computational performance than GMM-SCMS, such as Cases 1–3. However, Table 3 also shows an interesting phenomenon that GMM-SCMS shows higher computational efficiency than F-SCMS [28] in Case 4. The phenomenon indicates that the number of connected components (CCs) influences the F-SCMS performance. For instance, the numbers of CCs in Cases 1–4 are 3, 1, 1, and 8, respectively. It seems that when the number of connected components is high, GMM-SCMS is more efficient than F-SCMS. The main reason is that F-SCMS detects feature points (i.e., end and junction points) and then links these points iteratively for each connected component. Detection of feature points from the classified image costs a lot of time. Therefore, high number of CCs decreases the performance of F-SCMS.Figure13 demonstrates the accuracy of three methods. As can be seen, SCMS produces the lowest accuracy while F-SCMS the highest. In general, GMM-SCMS achieves the modest accuracy among these three methods.By comparing the proposed method with two existing methods on simulated and real datasets, it can be seen that the proposed method produces the best balance between the computational complexity, accuracy, and generalization ability among these three methods. Thus, GMM-SCMS is more practical for accurate and efficient road centerline extraction from classified images.


## 4. Conclusions

In conclusions, an automatic method, so-called Gaussian mixture model based subspace constrained mean shift (GMM-SCMS), was developed for road centerline extraction from the classified image. The GMM-SCMS method can extract smooth road centerlines with high accuracy. Benefited from GMM, the proposed method can represent the classified images using a small number of points while retaining the correct spatial topology, which in turn improves the computational efficiency. By using SCMS, the approximate points are iteratively adjusted to produce the accurate road centerline.The proposed method was compared with cutting-edge SCMS and feature points-based SCMS (F-SCMS). The experimental results indicate that(
1
) GMM-SCMS is more efficient than SCMS and (
2
) GMM-SCMS has a higher generalization ability than F-SCMS. In other words, GMM-SCMS can process the classified image with arbitrary shape. By full consideration of efficiency, accuracy, and generalization ability, it can be concluded that GMM-SCMS can provide a practical solution for delineating road centerlines from classified images.



---

*Source: 784504-2015-10-21.xml*